Prime Numbers
Integers greater than 1 that have no positive divisors other than 1 and themselves are called prime numbers. Integers greater than 1 that are not prime are called composite numbers.
The set of positive divisors of 11 is $\{1, 11\}$. Since it has no positive divisors other than 1 and itself, 11 is a prime number. As can easily be seen, there is no even prime number other than 2. That is, except for 2, all prime numbers are odd numbers. Some of the prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, … etc.
The positive divisors of a number that are prime are called the prime factors of that number. For example, the set of positive divisors of 30 is $\{1, 2, 3, 5, 6, 10, 15, 30\}$. Among the elements of this set, the numbers 2, 3, and 5 are the prime factors of 30.
Prime Factorization of a Number:
When factoring a number into its prime components, division is performed starting from the smallest prime number that divides this number. The resulting quotient is again divided by the smallest prime number that divides it. This division process is continued in this manner until the quotient becomes 1.
As an example, let us decompose the number 480 into its prime factors.
\[ \begin{array}{r|l}480 & 2 \\240 & 2 \\120 & 2 \\60 & 2 \\30 & 2 \\15 & 3 \\5 & 5 \\1 & \\\end{array} \]
$$2, 3, \quad \text{and} \quad 5 \quad \text{are the prime factors of 480, and the prime factorization of 480 is:}$$
$$480 = 2^5 \cdot 3 \cdot 5$$
Coprime Numbers (Relatively Prime):
Numbers that have no positive common divisor other than 1 are called coprime numbers. For example, the pairs
$$7 \quad \text{and} \quad 11$$
$$11 \quad \text{and} \quad 15$$
$$8 \quad \text{and} \quad 21$$
are coprime.
For a group of numbers to be coprime, it is not necessary for the numbers themselves to be prime. For instance, even though 8 and 21 are not prime numbers, 8 and 21 are coprime to each other.
Notice: Coprime numbers cannot be simplified between themselves. Accordingly, if a fraction is in its simplest form, the numerator and denominator of this fraction are coprime. For example, the fraction $\frac{8}{14}$ is equivalent to the fraction $\frac{4}{7}$, and the simplest form of $\frac{8}{14}$ is $\frac{4}{7}$. Here, 4 and 7 are coprime.
Example:
The expressions $2x-y$ and $x-y$ are coprime numbers. Given that \[\frac{2x-y}{x-y}=\frac{6}{10}\] let us find the value of the product $x \cdot y$.
Since $2x-y$ and $x-y$ are coprime, the fraction $$\frac{2x-y}{x-y}$$ must be in its simplest form.
Therefore, $$\frac{2x-y}{x-y}=\frac{6}{10}=\frac{3}{5}$$
From this, the system of equations $$2x-y = 3$$ $$x-y = 5$$ is obtained. If this system of equations is solved, the values $x = -2$ and $y = -7$ are found. Thus, $x \cdot y = (-2) \cdot (-7) = 14$.
Question 9
$a$ and $b$ are two coprime numbers. Given that $a^b = 64$, what is the sum of the distinct possible values of the product $a \cdot b$?
\[A) 12\quad B) 24\quad C) 64\quad D) 70\quad E)76\quad\]
Solution:
If we write the number 64 in the form of $a^b$:
$$64 = (64)^1 \Rightarrow a = 64, \quad b = 1 \quad \text{64 and 1 are coprime.}$$
$$64 = (8)^2 \Rightarrow a = 8, \quad b = 2 \quad \text{8 and 2 are not coprime.}$$
$$64 = (4)^3 \Rightarrow a = 4, \quad b = 3 \quad \text{4 and 3 are coprime.}$$
$$64 = (2)^6 \Rightarrow a = 2, \quad b = 6 \quad \text{2 and 6 are not coprime.}$$
Therefore, the number pairs $(a, b)$ suitable for the conditions given in the question are $(64, 1)$ or $(4, 3)$. Accordingly, the sum of the values of their products is:
$$a \cdot b = 64 \cdot 1 + 4 \cdot 3 = 76$$
\(\textbf{Answer: E}\)
Question 10:
Given that $n$ is a positive integer, what is the smallest value that $n$ can take for the product $90 \cdot n$ to be a perfect cube?
\[A) 100\quad B) 200\quad C) 300\quad D) 800\quad E)2400\quad\]
Solution:
If we decompose the number 90 into its prime factors,
$$90 = 2 \cdot 3^2 \cdot 5$$
It can be seen from this product that if we multiply 90 by at least $$2^2 \cdot 3 \cdot 5^2$$, it will be equal to a perfect cube. Therefore, the smallest value of $n$ is:
$$2^2 \cdot 3 \cdot 5^2 = 300$$
\(\textbf{Answer: C}\)
Positive Divisors of an Integer:
Let $P_1, P_2, P_3, \dots, P_n$ be prime numbers and $a_1, a_2, a_3, \dots, a_n \in \mathbb{N}^+$. The prime factorization of an integer $A$ is represented as:
$A = P_1^{a_1} \cdot P_2^{a_2} \cdot P_3^{a_3} \cdots P_n^{a_n}$
Then, the number of positive divisors of the integer $A$ is:
$$ (a_1+1) \cdot (a_2+1) \cdot (a_3+1) \cdots (a_n+1) $$
Since this number has as many negative divisors as its positive divisors, the total number of all divisors of the integer $A$ is:
$$ 2 \cdot (a_1+1) \cdot (a_2+1) \cdot (a_3+1) \cdots (a_n+1) $$
Examples:
- The set of positive divisors of 72 is $\{1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72\}$.
As seen, 72 has 12 positive divisors. We can find this with the help of the formula:
$$ 72 = 2^3 \cdot 3^2 \quad \Rightarrow \quad (3+1) \cdot (2+1) = 12 $$
- Let us find the total number of all divisors of 144.
If written in the form $$144 = 2^4 \cdot 3^2$$, the total number of all divisors is found as:
$$\quad 2 \cdot (4+1) \cdot (2+1) = 30$$
- Let us find the number of non-prime divisors of 360.
If $$360 = 2^3 \cdot 3^2 \cdot 5^1$$, the total number of all divisors of 360 is:
$$ 2 \cdot (3+1) \cdot (2+1) \cdot (1+1) = 48 $$
Since the numbers 2, 3, and 5 are the prime divisors of 360, the number of non-prime divisors of 360 is:
$$48 – 3 = 45$$
Question 11:
What is the ratio of the number of non-prime divisors of 112 to its prime divisors?
\[A) 10\quad B) 9\quad C) 8\quad D) 5\quad E)4\quad\]
Solution:
If $112 = 2^4 \cdot 7$, the total number of divisors of 112 is $2 \cdot (4 + 1) \cdot (1 + 1) = 20$. Since the number of prime divisors is 2, the number of non-prime divisors is $20 – 2 = 18$. Therefore, the ratio of the number of non-prime divisors of 112 to the number of prime divisors is:
$$\frac{18}{2} = 9$$
$$\text{Answer: B}$$
Question 12:
If the number of non-prime positive divisors of $6^{4n}$ is 623, what is $n$?
\[A) 3\quad B) 4\quad C) 5\quad D) 6\quad E)8\quad\]
Solution:
$$6^{4n} = (2 \cdot 3)^{4n} = 2^{4n} \cdot 3^{4n}$$
Accordingly, the number $6^{4n}$ has 2 prime divisors. Therefore, the total number of positive divisors of this number is $623 + 2 = 625$. In that case,
$$625 = (4n+1) \cdot (4n+1)$$
$$ \Rightarrow (25)^2 = (4n+1)^2$$
$$\Rightarrow 25 = |4n+1|$$
$$\text{Since } 4n+1 > 0:$$
$$25 = 4n + 1 \Rightarrow 4n = 24 \Rightarrow n = 6$$
$$\text{Answer: D}$$
Question 13:
How many natural numbers can be written in place of $x$ so that the expression \[ \frac{x^2 – 7x + 60}{x} \] is an integer?
\[A) 24\quad B) 16\quad C) 12\quad D) 10\quad E)8\quad\]
Solution:
Since \[ \frac{x^2 – 7x + 60}{x} = x – 7 + \frac{60}{x} \]
for this expression to be an integer, the fraction $\frac{60}{x}$ must be an integer. That is, the number 60 must be exactly divisible by $x$. Since we are looking for the number of natural number values of $x$, it will be sufficient to find the number of positive divisors of 60. According to this,
\[ 60 = 2^2 \cdot 3 \cdot 5 \quad \Rightarrow \quad \text{The number of positive divisors of 60 is:} \] \[ (2+1) \cdot (1+1) \cdot (1+1) = 12 \]
Therefore, there are 12 natural number values that can be written in place of $x$.
$$\textbf{Answer: C}$$
The Sum and Product of Positive Divisors of an Integer:
If the prime factorization of an integer $A$ is given by \[ A = P_1^{a_1} \cdot P_2^{a_2} \cdot P_3^{a_3} \cdots P_n^{a_n} \]
- Sum of the Positive Divisors of Integer A:
\[ \frac{1 – P_1^{a_1 + 1}}{1 – P_1} \cdot \frac{1 – P_2^{a_2 + 1}}{1 – P_2} \cdot \frac{1 – P_3^{a_3 + 1}}{1 – P_3} \cdots \frac{1 – P_n^{a_n + 1}}{1 – P_n } \] and
- Product of the Positive Divisors of Integer A:
\[ \text{Let } x = \frac{(a_1 + 1) \cdot (a_2 + 1) \cdot (a_3 + 1) \cdots (a_n + 1)}{2}, \quad \text{the product is } A^x. \]
Examples:
- Since the number 48 is factored as $48 = 2^4 \cdot 3$, the sum and product of its positive divisors are respectively:
\[ \frac{1 – 2^5}{1 – 2} \cdot \frac{1 – 3^2}{1 – 3} = 124 \quad \text{and} \quad \left( 48 \right)^{\frac{(4+1) \cdot (1+1)}{2}} = (48)^5 \]
- Since the number 12 is factored as $12 = 2^2 \cdot 3$, the sum and product of its positive divisors are respectively:
\[ \frac{1 – 2^3}{1 – 2} \cdot \frac{1 – 3^2}{1 – 3} = 28 \quad \text{and} \quad \left( 12 \right)^{\frac{(2+1) \cdot (1+1)}{2}} = (12)^3 \]
Example:
Let us find the sum of the non-prime positive divisors of 54.
\[ 54 = 2 \cdot 3^3 \quad \Rightarrow \quad \text{The sum of the positive divisors of 54 is:} \]
\[ \frac{1 – 2^2}{1 – 2} \cdot \frac{1 – 3^4}{1 – 3} = 120 \]
Since the sum of the prime divisors of 54 is $2 + 3 = 5$, the sum of the non-prime positive divisors of 54 is found as:
\[ 120 – 5 = 115 \]
Numbers Smaller Than a Total Integer A and Coprime to A:
Under this condition, the number of positive integers smaller than $A$ and coprime to $A$ (Euler’s totient function) is given by:
Example:
Let us find how many positive numbers are smaller than 144 and coprime to 144.
Since $144 = 2^4 \cdot 3^2$, the count of numbers smaller than 144 and coprime to it is: