Number Theory 697Sinces≡b(moda), there existsnsuch thats=an+b, and sosis a term of the
arithmetic progression that can be written as a sum ofmkth powers of integers. Varying
the parameterss 1 ,s 2 ,...,sn, we obtain infinitely many terms with this property.
(proposed by E. Just forMathematics Magazine)
755.Denote the sum from the statement bySn. We will prove a stronger inequality,
namely,
Sn>n
2(log 2 n− 4 ).The solution is based on the following obvious fact: no odd number but 1 divides 2n
evenly. Hence the residue of 2nmodulo such an odd number is nonzero. From here we
deduce that the residue of 2nmodulo a number of the form 2m( 2 k+ 1 ),k>1, is at least
2 m. Indeed, if 2n−m=( 2 k+ 1 )q+r, with 1≤r< 2 k+1, then 2n= 2 m( 2 k+ 1 )q+ 2 mr,
with 2m< 2 mr< 2 m( 2 k+ 1 ). And so 2mris the remainder obtained by dividing 2nby
2 m( 2 k+ 1 ).
Therefore,Sn≥ 1 ×(the number of integers of the form 2k+1,k>1, not exceeding
n)+ 2 ×(the number of integers of the form 2( 2 k+ 1 ),k>1, not exceedingn)+ 22 ×( the
number of integers of the form 2^2 ( 2 k+ 1 ),k>1, not exceedingn)+···.
Let us look at the(j+ 1 )st term in this estimate. This term is equal to 2jmultiplied
by the number of odd numbers between 3 and 2 nj, and the latter is at least^12 ( 2 nj− 3 ).We
deduce that
Sn≥∑
j2 j
n− 3 · 2 j
2 j+^1=
∑
j1
2
(
n− 3 · 2 j)
,
where the sums stop when 2j· 3 >n, that is, whenj=log 2 n 3 . Settingl=log 2 n 3 ,
we have
Sn≥(l+ 1 )n
2−
3
2
∑lj= 02 i>(l+ 1 )n
2−
3 · 2 l+^1
2.
Recalling the definition ofl, we conclude that
Sn>
n
2log 2
n
3−n=
n
2(
log 2
n
3− 2
)
>
n
2(log 2 n− 4 ),and the claim is proved. The inequality from the statement follows from the fact that for
n>1000,^12 (log 2 n− 4 )>^12 (log 21000 − 4 )>2.
(Kvant(Quantum), proposed by A. Kushnirenko, solution by D. Grigoryev)
756.First, observe that all terms of the progression must be odd. Letp 1 <p 2 <···<pk
be the prime numbers less thann. We prove the property true forpiby induction oni.