Advanced book on Mathematics Olympiad

Number Theory 687

Because 2a−1 and 2a+1 are coprime, and so are 2b−1 and 2b+1, this is further
equal to

gcd( 2 a− 1 , 2 b− 1 )·gcd( 2 a− 1 , 2 b+ 1 )·gcd( 2 a+ 1 , 2 b− 1 )·gcd( 2 a+ 1 , 2 b+ 1 ).

It follows that gcd( 2 a+ 1 , 2 b+ 1 )divides 2gcd(^2 a,^2 b)−1. Of course,

2 gcd(^2 a,^2 b)− 1 = 2 2 gcd(a,b)− 1 =( 2 gcd(a,b)− 1 )( 2 gcd(a,b)+ 1 ),

so gcd( 2 a+ 1 , 2 b+ 1 )divides the product( 2 gcd(a,b)− 1 )( 2 gcd(a,b)+ 1 ). Again because
gcd( 2 a+ 1 , 2 a− 1 )=gcd( 2 b+ 1 , 2 b− 1 )=1, it follows that gcd( 2 a+ 1 , 2 b+ 1 )and
2 gcd(a,b)−1 do not have common factors. We conclude that gcd( 2 a+ 1 , 2 b+ 1 )divides
2 gcd(a,b)+1.

729.We computea 2 =(k+ 1 )^2 −k(k+ 1 )+k =(k+ 1 )+k =a 1 +k,a 3 =
a 2 (a 2 −k)+k =a 2 a 1 +k,a 4 =a 3 (a 3 −k)+k =a 3 a 2 a 1 +k, and in general if
an=an− 1 an− 2 ···a 1 +k, then

an+ 1 =an(an−k)+k=anan− 1 an− 2 ···a 1 +k.

Therefore,an−kis divisible byam, for 1≤m<n. On the other hand, inductively we
obtain thatamandkare relatively prime. It follows thatamandan=(an−k)+kare
also relatively prime. This completes the solution.
(Polish Mathematical Olympiad, 2002)

730.By hypothesis, all coefficients of the quadratic polynomial

P(x)=(x+a)(x+b)(x+c)−(x−d)(x−e)(x−f)

=(a+b+c+d+e+f)x^2 +(ab+bc+ca−de−ef−fd)x

+(abc+def)

are divisible byS =a+b+c+d+e+f. EvaluatingP(x)atd, we see that
P(d)=(a+d)(b+d)(c+d)is a multiple ofS. This readily implies thatSis composite
because each ofa+d,b+d, andc+dis less thanS.
(short list of 46th International Mathematical Olympiad, 2005)

731.The polynomial

P (n)=n(n− 1 )^4 + 1 =n^5 − 4 n^4 + 6 n^3 − 4 n^2 +n+ 1

does not have integer zeros, so we should be able to factor it as a product a quadratic and
a cubic polynomial. This means that

P (n)=(n^2 +an+ 1 )(n^3 +bn^3 +cn+ 1 ),