Maths Olympiad Prep

Library / South-Afrika /48 of 64

South-Afrika, 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)=(n−3)(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)=(n−3)(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)=pa−1(p−1)ϕ(m)σ(n)=σ(pa)σ(m)=(pa+1−1p−1)σ(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)=pa−1(pa+1−1)ϕ(m)σ(m). \phi(n)\sigma(n) = p^{a-1}(p^{a+1} - 1)\phi(m)\sigma(m).
If a≥2a \ge 2, it follows that, modulo pa−1p^{a-1},
0≡ϕ(n)σ(n)=(n−3)(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=9p1p2…pkn = 9p_1p_2\dots p_k, then
ϕ(n)σ(n)=78(p12−1)(p22−1)…(pk2−1)≡90, \phi(n)\sigma(n) = 78(p_1^2 - 1)(p_2^2 - 1)\dots(p_k^2 - 1) \equiv_9 0,
since p12≡31p_1^2 \equiv_3 1 for every prime pi≠3p_i \neq 3, but
(n−3)(n+1)≡9−3. (n-3)(n+1) \equiv_9 -3.
Hence n=p1p2…pkn = 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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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