Maths Olympiad Prep

Library / /53 of 69

, 2011

Number theory Difficulty 6.0 National Olympiad Prove it South Africa

Prove that the positive integer nn is the product of exactly two primes that differ by 2 if and only if
ϕ(n)σ(n)=(n3)(n+1). \phi(n)\sigma(n) = (n-3)(n+1).
(Recall that ϕ(n)\phi(n) equals the number of positive integers less than or equal to nn, relatively prime to nn, and σ(n)\sigma(n) equals the sum of the positive divisors of nn, including 1 and nn.)

Solution

Let ϕ(n)σ(n)=(n3)(n+1)\phi(n)\sigma(n) = (n-3)(n+1), and let prime pp divide nn such that n=pamn = p^a m for some mm not divisible by pp. Then we have
ϕ(n)=ϕ(pa)ϕ(m)=pa1(p1)ϕ(m)σ(n)=σ(pa)σ(m)=(pa+11p1)σ(m), \begin{align*} \phi(n) &= \phi(p^a)\phi(m) = p^{a-1}(p-1)\phi(m) \\ \sigma(n) &= \sigma(p^a)\sigma(m) = \left(\frac{p^{a+1}-1}{p-1}\right)\sigma(m), \end{align*}
so
ϕ(n)σ(n)=pa1(pa+11)ϕ(m)σ(m). \phi(n)\sigma(n) = p^{a-1}(p^{a+1} - 1)\phi(m)\sigma(m).
If a2a \ge 2, it follows that, modulo pa1p^{a-1},
0ϕ(n)σ(n)=(n3)(n+1)3. 0 \equiv \phi(n)\sigma(n) = (n-3)(n+1) \equiv -3.
Hence a=2a = 2 and p=3p = 3. Thus either a=1a = 1 or a=2a = 2 and p=3p = 3.
However, if n=9n = 9 does not satisfy the given equality, and if n=9p1p2pkn = 9p_1p_2\dots p_k, then
ϕ(n)σ(n)=78(p121)(p221)(pk21)90, \phi(n)\sigma(n) = 78(p_1^2 - 1)(p_2^2 - 1)\dots(p_k^2 - 1) \equiv_9 0,
since p1231p_1^2 \equiv_3 1 for every prime pi3p_i \neq 3, but
(n3)(n+1)93. (n-3)(n+1) \equiv_9 -3.
Hence n=p1p2pkn = p_1p_2 \dots p_k for some distinct primes pip_i.

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.