Advanced book on Mathematics Olympiad

264 5 Number Theory

767.Letf(x 1 ,x 2 ,...,xn)be a polynomial with integer coefficients of total degree less

thann. Show that the number of orderedn-tuples(x 1 ,x 2 ,...,xn)with 0≤xi≤ 12

such thatf(x 1 ,x 2 ,...,xn)≡ 0 (mod 13)is divisible by 13.

768.Determine all integersasuch thatak+1 is divisible by 12321 for some appropriately

chosen positive integerk>1.

5.2.5 Wilson’s Theorem........................................

Another result about prime numbers is known as Wilson’s theorem.

Wilson’s theorem.For every primep, the number(p− 1 )!+ 1 is divisible byp.

Proof.We group the residue classes 1, 2 ,...,p−1 in pairs(a, b)such thatab ≡

1 (modp). Let us see whena=bin such a pair. The congruencea^2 ≡ 1 (modp)

is equivalent to the fact thata^2 − 1 =(a− 1 )(a+ 1 )is divisible byp. This happens

only whena=1ora=p−1. For all other residue classes the pairs contain distinct

elements. So in the product 2· 3 ···(p− 2 )the factors can be paired such that the product

of the numbers in each pair is congruent to 1. Therefore,

1 · 2 ···(p− 2 )·(p− 1 )≡ 1 ·(p− 1 )≡− 1 (modp).

The theorem is proved. 

The converse is also true, sincenmust divide(n− 1 )!for compositen. And now an

application.

Example.Letpbe an odd prime. Prove that

12 · 32 ···(p− 2 )^2 ≡(− 1 )

p+ 21

(modp)

and

22 · 42 ···(p− 1 )^2 ≡(− 1 )

p+ 21

(modp).

Solution.By Wilson’s theorem,

( 1 · 3 ···(p− 2 ))( 2 · 4 ···(p− 1 ))≡− 1 (modp).

On the other hand,

1 ≡−(p− 1 )(modp), 3 ≡−(p− 3 )(modp),...,p− 2 ≡−(p−(p− 2 ))(modp).

Therefore,

1 · 3 ···(p− 2 )≡(− 1 )

p− 21

( 2 · 4 ···(p− 1 )) (modp).

Multiplying the two congruences and canceling out the product 2· 4 ···(p− 1 ),weob-

tain the first congruence from the statement. Switching the sides in the second and multi-

plying the congruences again, we obtain the second congruence from the statement.