Problem 11789
(American Mathematical Monthly, Vol.121, AugustSeptember 2014) Proposed by G. Alperin (USA) and Y. J. Ionin (USA).
Let a and b be positive integers. Prove that for every positive integer m there exists a positive integern such that m divides ban+ n.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
We will show a more general statement.
Leta and b be positive integers. If m is a positive integer then for any j = 0, 1, . . . , m − 1, there exists an arbitrarily large positive integernj(m) such that
banj(m)+ nj(m) ≡ j (mod m).
We proceed by induction on m. If m = 1 then it trivially holds. For m = 2, let nj(2) ≡ j − ba (mod 2). Now assume that the statement holds for 1, 2 . . . , m − 1. Due to Euler-Fermat theorem, the sequence {an}n≥1 is eventually periodic modulo m. Let T be the least positive integer such that an ≡ an+T (mod m) for all sufficiently large integer n. Note that T ≤ ϕ(m) < m, because an+ϕ(m)≡ an (mod m) for all n ≥ m − ϕ(m).
Let d = gcd(m, T ) ≤ min(m, T ) < m. Then, by the inductive hypothesis, we are able to consider the following set of positive integers
{banj(d)+kT + (nj(d) + kT ) : j = 0, . . . , d − 1, k = 0, . . . , m/d − 1}.
It suffices to show that these integers are all distinct modulo m and therefore they cover all the d(m/d) = m possible remainders.
If for some 0 ≤ k1≤ k2< m/d, and for some 0 ≤ j1≤ j2< d, we have
banj1(d)+k1T + (nj1(d) + k1T ) ≡ banj2(d)+k2T+ (nj2(d) + k2T ) (mod m), then
(banj1(d)+ nj1(d)) − (banj2(d)+ nj2(d)) ≡ (k2− k1)T (mod m).
i) If j1< j2, then 0 < j2− j1< d and we obtain the following contradiction
0 6≡ j1− j2≡ (banj1(d)+ nj1(d)) − (banj2(d)+ nj2(d)) ≡ (k2− k1)T ≡ 0 (mod d).
ii) On the other hand, if j1= j2 and k1< k2, then
(k2− k1)T ≡ 0 (mod m).
which implies that the positive integer (k2− k1)T is a multiple of both T and m, which is impossible because (k2− k1)T < (m/d)T = lcm(m, T ).