686 Number Theory
Remark.The casek=1 was given at the 20th International Mathematical Olympiad,
1978; the idea of the solution was taken from I.J. Schoenberg,Mathematical Time Expo-
sures(MAA, 1982).
724.If we multiplied the fraction by 8, we would still get an integer. Note that
8
n^3 − 3 n^2 + 4
2 n− 1
= 4 n^2 − 10 n− 5 +27
2 n− 1.
Hence 2n−1 must divide 27. This happens only when 2n− 1 =± 1 ,± 3 ,± 9 ,±27,
that is, whenn=− 13 ,− 4 ,− 1 , 1 , 2 , 5 ,14. An easy check shows that for each of these
numbers the original fraction is an integer.
725.The factor to be erased is 50!. Indeed, using the equality( 2 k)!=( 2 k− 1 )!· 2 k,we
see that
P=( 1 !)^2 · 2 ·( 3 !)^2 · 4 ·( 5 !)^2 · 6 ···( 99 !)^2 · 100 =( 1 !· 3 !· 5 !··· 99 !)^2 · 2 · 4 · 6 ··· 100
=( 1 !· 3 !· 5 !··· 99 !)^2 · 250 · 50 !=( 1 !· 3 !· 5 !··· 99 !· 225 )^2 · 50 !.It is noteworthy thatPitself is not a perfect square, since 50!is not, the latter because 47
appears to the first power in 50!.
(first stage of the Moscow Mathematical Olympiad, 1995–1996)
726.For any integerm, we have gcd(am,a 2 m)=gcd( 2 m, m)=m, and somdividesam.
It follows that for any other integern,mdividesanif and only if it divides gcd(am,an)=
gcd(m, n). Henceanhas exactly the same divisors asn, so it must equaln, for alln.
(Russian Mathematical Olympiad, 1995)
727.Because gcd(a, b)divides bothaandb, we can factorngcd(a,b)−1 from bothna− 1
andnb−1. Therefore,ngcd(a,b)−1 divides gcd(na− 1 ,nb− 1 ).
On the other hand, using Euclid’s algorithm we can find positive integersxandy
such thatax−by=gcd(a, b). Thenna−1 dividesnax−1 andnb−1 dividesnby−1.
In order to combine these two, we use the equality
nby(ngcd(a,b)− 1 )=(nax− 1 )−(nbx− 1 ).Note that gcd(na− 1 ,nb− 1 )divides the right-hand side, and has no common factor with
nby. It therefore must dividengcd(a,b)−1. We conclude thatngcd(a,b)− 1 =gcd(na−
1 ,nb− 1 ), as desired.
728.We use the particular casen=2 of the previous problem as a lemma. To obtain the
negative signs we incorporate 2a+1 and 2b+1 into 2^2 a−1 and 2^2 b−1, then apply the
lemma to these two numbers. We have
2 gcd(^2 a,^2 b)− 1 =gcd( 22 a− 1 , 22 b− 1 )=gcd(
( 2 a− 1 )( 2 a+ 1 ), ( 2 b− 1 )( 2 b+ 1 )