Maths Olympiad Prep

Library / /27 of 94

Number theory Difficulty 5.5 AIME, harder Prove it Hong Kong

Let n>4n > 4 be a positive integer such that nn is composite (not a prime) and divides φ(n)σ(n)+1\varphi(n)\sigma(n) + 1, where φ(n)\varphi(n) is the Euler's totient function of nn and σ(n)\sigma(n) is the sum of the positive divisors of nn. Prove that nn has at least three distinct prime factors.

Solution

If p2np^2 \mid n for some prime pp, then pφ(p2)φ(n)p \mid \varphi(p^2) \mid \varphi(n). This implies pφ(n)σ(n)+1p \mid \varphi(n)\sigma(n) + 1, and hence pn+φ(n)σ(n)+1p \mid n + \varphi(n)\sigma(n) + 1. Therefore, nn must be squarefree.

If n=pqn = pq for some distinct primes pp and qq, then
φ(pq)σ(pq)+1=(p1)(q1)(p+1)(q+1)+1=p2q2p2q2+2. \varphi(pq)\sigma(pq) + 1 = (p-1)(q-1)(p+1)(q+1) + 1 = p^2q^2 - p^2 - q^2 + 2.
This is a multiple of pqpq if and only if pqp2+q22pq \mid p^2 + q^2 - 2. We now prove that aba2+b22ab \mid a^2 + b^2 - 2 has no solution in distinct integers a,b>1a, b > 1 using Vieta's jumping.

Suppose on the contrary that the divisibility is solvable. Let (a,b)(a, b) be a solution such that a>b>1a > b > 1 and bb is the smallest possible. Let a2+b22=kaba^2 + b^2 - 2 = kab for some positive integer kk. Rewrite this equation as
a2kba+(b22)=0. a^2 - kba + (b^2 - 2) = 0.
This is a quadratic equation in aa. Let aa' be another solution to this equation. Since a+a=kba + a' = kb, aa' is an integer. Since aa=b22>0aa' = b^2 - 2 > 0, aa' is positive. Also, we have
a=b22a<b2a<b<a. a' = \frac{b^2 - 2}{a} < \frac{b^2}{a} < b < a.
This shows (x,y)=(b,a)(x, y) = (b, a') is another pair of solution to xyx2+y22xy \mid x^2 + y^2 - 2 such that x>y>0x > y > 0. As a<ba' < b, by the minimality of bb, we must have a=1a' = 1. But then the divisibility becomes b1+b22b \mid 1 + b^2 - 2, i.e. b1b \mid 1. This is impossible since b>1b > 1. Thus, there is no solution.

It follows that nn must have at least 3 distinct prime divisors.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.