5.2 Arithmetic 257741.The positive divisors of an integern>1 are 1=d 1 <d 2 <···<dk=n. Let
s=d 1 d 2 +d 2 d 3 + ··· +dk− 1 dk. Prove thats<n^2 and find allnfor whichs
dividesn^2.
742.Prove that there exist functionsf, g:{ 0 , 1 , 2 ,...}×{ 0 , 1 , 2 ,...}→{ 0 , 1 , 2 ,...}
with the property that an odd numbern>1 is prime if and only if there do not exist
nonnegative integersaandbsuch thatn=f(a,b)−g(a, b).
743.Letn≥ 2 be an integer. Prove that ifk^2 +k+nis a prime number for all
0 ≤k≤
√n
3 , thenk(^2) +k+nis a prime number for all 0≤k≤n−2.
The following formula is sometimes attributed to Legendre.
Polignac’s formula.Ifpis a prime number andna positive integer, then the exponent
ofpinn!is given by
⌊
n
p
⌋
+
⌊
n
p^2⌋
+
⌊
n
p^3⌋
+···.
Proof.Each multiple ofpbetween 1 andncontributes a factor ofpton!. There are
n/psuch factors. But the multiples ofp^2 contribute yet another factor ofp, so one
should addn/p^2 . And then come the multiples ofp^3 and so on.
Example.Letmbe an integer greater than 1. Prove that the product ofmconsecutive
terms in an arithmetic progression is divisible bym!if the ratio of the progression is
coprime tom.
Solution.Letpbe a prime that dividesn!. The exponent ofpinn!is given by Polignac’s
formula. On the other hand, in the producta(a+r)(a+ 2 r)···(a+(m− 1 )r)ofm
consecutive terms in a progression of ratior, with gdc(r, m)=1, at leastm/piterms
are divisible bypi. It follows that the power ofpin this product is greater than or equal
to the power ofpinm!. Because this holds true for any prime factor inm!, the conclusion
follows.
All problems below are based on Polignac’s formula.744.Find all positive integersnsuch thatn!ends in exactly 1000 zeros.
745.Prove thatn!is not divisible by 2nfor any positive integern.
746.Show that for each positive integern,
n!=∏ni= 1lcm( 1 , 2 ,...,n/ i),where lcm denotes the least common multiple.