• Non ci sono risultati.

If m is a positive integer then for any j = 0, 1

N/A
N/A
Protected

Academic year: 2021

Condividi "If m is a positive integer then for any j = 0, 1"

Copied!
1
0
0

Testo completo

(1)

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 ).



Riferimenti

Documenti correlati

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma,