Let $ n>4$ be a positive integer such that $ n$ is composite (not a prime) and divides $ \varphi (n) \sigma (n) +1$, where $ \varphi (n)$ is the Euler's totient function of $ n$ and $ \sigma (n)$ is the sum of the positive divisors of $ n$. Prove that $ n$ has at least three distinct prime factors.
Problem
Source: 11th CHKMO 2009
Tags: function, Euler, algebra, polynomial, Vieta, quadratics, number theory
TTsphn
15.12.2008 06:26
brianchung11 wrote: Let $ n > 4$ be a positive integer such that $ n$ is composite (not a prime) and divides $ \varphi (n) \sigma (n) + 1$, where $ \varphi (n)$ is the Euler's totient function of $ n$ and $ \sigma (n)$ is the sum of the positive divisors of $ n$. Prove that $ n$ has at least three distinct prime factors. Because $ \varphi(n)\equiv 0 (\mod 2),\forall n > 4$ so we have $ \varphi(n).\sigma(n) + 1$ is an odd number . It follows that $ n$ must be an odd number . It is easy to check that $ n$ must be a square free number .If not ,then there exist a prime p such that $ v_p(n) > 1$ .From the formulas of Euler function we have $ p|\varphi(n)$ ,therefore $ p$ can not be a divisor of number $ \varphi(n).\sigma (n) + 1$ . Thus $ n$ must be a square free number . Suppose $ n$ has less than three prime divisor . And because $ n$ is not a prime so it must be product of two different primes .Let $ n = pq$ and $ p > q$ . Then \[ \varphi(n) = (p - 1)(q - 1) \] \[ \sigma(n) = (p + 1)(q + 1) \] And from the condition we have : $ pq|(p + 1)(q + 1)(q - 1)(q + 1) + 1$ Thus $ p|q^2-2,q|p^2-2$ ,it gives contradiction . Problem has been proved .
brianchung11
15.12.2008 07:21
$ pq|(p + 1)(q + 1)(q - 1)(q + 1) + 1$<- i believe that you've made some mistakes here... and $ p|q^2 - 2$ instead of $ p|q^2$... i think the simplest way to tackle the case of $ n=pq$ is vieta jumping.
The QuattoMaster 6000
15.12.2008 08:50
If $ n$ is a perfect prime power, then let $ n = p^l$ where $ l > 1$. This means that $ p|\varphi (n)$, so $ p$ cannot divide $ \varphi (n)\sigma (n) + 1$, which is a contradiction since $ p^l$ divides it. Thus, we have a contradiction, so $ n$ may not be a perfect prime power.
Assume that there are only two prime factors of $ n$, namely $ p$ and $ q$. If $ p^r||n$ and $ r > 1$, then we see that $ p|\varphi (n)$, so $ p$ may not divide $ \varphi (n)\sigma (n) + 1$, which is a contradiction as $ pq$ must divide $ \varphi (n)\sigma (n) + 1$. Thus, $ r = 1$. Similarly, $ q||n$. It follows that $ n = pq$. Notice that $ \varphi (n) = (p - 1)(q - 1)$ and $ \sigma (n) = (p + 1)(q + 1)$, so the condition turns into $ \frac {(p - 1)(q - 1)(p + 1)(q + 1) + 1}{pq}$ must be an integer, so $ \frac {(p^2 - 1)(q^2 - 1) + 1}{pq}$ is an integer, so $ \frac {p^2 + q^2 - 2}{pq}$ is an integer. Let this value be $ k$. It follows that $ p^2 - p(kq) + (q^2 - 2) = 0$. Now, allow $ (a, b)$ to be the solution with minimal $ a + b$ ($ a$ and $ b$ do not have to be prime anymore). Let $ a\ge b$. If we look at this equation as a quadratic in $ a$, then we may notice that $ (\frac {b^2 - 2}{a}, b)$ is a solution. Since this is symmetric in $ a$ and $ b$, it follows that $ (b, \frac {b^2 - 2}{a})$ is a solution. This means that $ a + b \le b + \frac {b^2 - 2}{a}$, so $ a^2 \le b^2 - 2\implies a < b$, which is a contradiction, so $ n$ has at least $ 3$ divisors.
CatCatHead
20.09.2024 09:03
how can p|q^2-2 and q|p^2-2 make a contraction? I just get that p and q must be both congruent to 1 or 7 when mod 8.