Advanced book on Mathematics Olympiad

5.2 Arithmetic 269

Proof.For anyj,1≤j≤k, the numberm/mjis coprime tomjand hence invertible
with respect tomj. Letbjbe the inverse. Then

x 0 =

m

m 1

b 1 a 1 +

m

m 2

b 2 a 2 +···+

m

mk

bkak

is a solution to the system. For any other solutionx, the differencex−x 0 is divisible by
m. It follows that the general solution is of the formx 0 +mt, withtan integer. 

We illustrate the use of the Chinese Remainder Theorem with an example from the
classic book of W. Sierpinski, 250 ́ Problems in Elementary Number Theory(Panstwowe ́
Wydawnictwo Naukowe, Warsawa, 1970).

Example.Prove that the system of Diophantine equations

x 12 +x 22 +x 32 +x^24 =y^5 ,

x 13 +x 23 +x 33 +x^34 =z^2 ,

x 15 +x 25 +x 35 +x^54 =t^3

has infinitely many solutions.

Solution.Leta= 12 + 22 + 32 + 42 ,b= 13 + 23 + 33 + 43 ,c= 15 + 25 + 35 + 45. We look
for solutions of the formx 1 =ambncp,x 2 = 2 ambncp,x 3 = 3 ambncp,x 4 = 4 ambncp.
These satisfy

x^21 +x 22 +x 32 +x^24 =a^2 m+^1 b^2 nc^2 p,

x^31 +x 23 +x 33 +x^34 =a^3 mb^3 n+^1 c^3 p,

x^51 +x 25 +x 35 +x^54 =a^5 mb^5 nc^5 p+^1.

We would like the right-hand sides to be a fifth, second, and third power, respectively.
Reformulating, we want to show that there exist infinitely manym, n, psuch that

2 m+ 1 ≡ 2 n≡ 2 p≡ 0 (mod 5),

3 m≡ 3 n+ 1 ≡ 3 p≡ 0 (mod 2),

5 m≡ 5 n≡ 5 p+ 1 ≡ 0 (mod 3).

But this follows from the Chinese Remainder Theorem, and we are done. 

785.An old woman went to the market and a horse stepped on her basket and smashed
her eggs. The rider offered to pay for the eggs and asked her how many there were.
She did not remember the exact number, but when she had taken them two at a time
there was one egg left, and the same happened when she took three, four, five, and
six at a time. But when she took them seven at a time, they came out even. What
is the smallest number of eggs she could have had?