Problem 12021
(American Mathematical Monthly, Vol.125, February 2018) Proposed by O. Sonebi (Morocco).
Letϕ be the Euler totient function. Given a ∈ Z+ andb ∈ Z+, show that there existsn ∈ Z+ such thatan + b is not in the range of ϕ.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
Solution. Let m := gcd(a, b), A := a/m and B := b/m. Let d1, d2, . . . , drbe all the positive divisors of m and the primes pi for i = 1, . . . , r such that max(a, b) < p1 < p2 < · · · < pr. Consider the system of congruences
(x ≡ B (mod A),
xdi≡ −1 (mod pi) for i = 1, . . . , r.
Since gcd(di, pi) = 1 (because pi > di), and A, p1, p2, . . . , pr are pairwise coprime, by the Chinese remainder theorem, there exists a positive integer x0= Ak0+ B such that for all k ∈ Z,
xk = Ap1· · ·prk + x0
is a solution of the system of congruences.
Notice that gcd(Ap1· · ·pr, x0) = 1 and by Dirichlet’s theorem the arithmetic progression (xk)k≥0
contains infinitely many primes. Hence there is a positive integer k such that p := xk > pr is a prime.
It remains to verify that
mp = m(Ap1· · ·prk + x0) = m(Ap1· · ·prk + Ak0+ B) = an + b where n := p1· · ·prk + k0 is not in the range of ϕ.
Assume that ϕ(y) =Qs
j=1qjαj−1(qj−1) = mp for some positive integer y =Qs
j=1qjαj then we have two cases.
i) p = qj for some j with αj > 1. Then p(p − 1) divides ϕ(y) = mp and therefore p − 1 divides m. Hence p ≤ m + 1 which contradicts p > p1> m.
ii) p divides qj−1 for some j. Then p < qj. Moreover pd = qj−1 divides ϕ(y) = mp, which implies that d is a divisor of m, that is d = di for some i. Since p is a solution of the above system of congruences, it follows that pi divides pdi+ 1 = qj which means that pi = qj. This contradicts qj> p > pi.
