Advanced book on Mathematics Olympiad

Number Theory 711

from the(k+ 2 )nd term onward, the terms of the sequence are nontrivial multiples of
pk+ 1 , and therefore must be composite. This completes the proof.
(Czech and Slovak Mathematical Olympiad, 1997)

790.We construct such a sequence recursively. Suppose thata 1 ,a 2 ,...,amhave been
chosen. Sets =a 1 +a 2 + ··· +am, and letnbe the smallest positive integer that
is not yet a term of the sequence. By the Chinese Remainder Theorem, there existst
such thatt ≡−s(mod(m+ 1 )), andt≡−s−n(mod(m+ 2 )). We can increase
tby a suitably large multiple of(m+ 1 )(m+ 2 )to ensure that it does not equal any
ofa 1 ,a 2 ,...,am. Thena 1 ,a 2 ,...,am,t,nis also a sequence with the desired property.
Indeed,a 1 +a 2 +···+am+t=s+tis divisible bym+1 anda 1 +···+am+t+n=s+t+n
is divisible bym+2. Continue the construction inductively. Observe that the algorithm
ensures that 1,...,mall occur among the first 2mterms.
(Russian Mathematical Olympiad, 1995)

791.First, let us fulfill a simpler task, namely to find aksuch thatk· 2 n+1 is composite
for everynin an infinite arithmetic sequence. Letpbe a prime, andbsome positive
integer. Chooseksuch thatk· 2 b≡− 1 (modp)(which is possible since 2bhas an
inverse modulop), and such thatk· 2 b+ 1 >p. Also, letabe such that 2a≡ 1 (modp).
Thenk· 2 am+b+1 is divisible bypfor allm≥0, hence is composite.
Now assume that we were able to find a finite set of triples(aj,bj,pj),1≤j≤s,
with 2aj≡ 1 (modpj)and such that for any positive integernthere existmandjwith
n=ajm+bj. We would like to determine aksuch thatk· 2 ajm+bj+1 is divisible bypj,
1 ≤j≤s,m≥0. Using the Chinese Remainder Theorem we can usekas a sufficiently
large solution to the system of equations

k≡− 2 −bj(modpj), 0 ≤j≤s.

Then for everyn,k· 2 n+1 is divisible by one of thepj’s,j= 0 , 1 ,...,s, hence is
composite.
An example of such a family of triples is( 2 , 0 , 3 ),( 3 , 0 , 7 ),( 4 , 1 , 5 ),( 8 , 3 , 17 ),
( 12 , 7 , 13 ),( 24 , 23 , 241 ).
(W. Sierpinski, 250 ́ Problems in Elementary Number Theory,Pa ́nstwowe Wydaw-
nictwo Naukowe, Warsawa, 1970)

792.Assume the contrary and consider a primepthat does not divideb−a. By the
Chinese Remainder Theorem we can find a positive integernsuch that

n≡ 1 (modp− 1 ),

n≡−a(modp).

Then by Fermat’s little theorem,

an+n≡a+n≡a−a≡ 0 (modp)