704 Number Theory
We conclude that ifais a perfect square but not a fourth power modulo 37, and is− 1
modulo 3, thenak≡− 1 (mod 3× 37 )andak×^3 ×^37 ≡− 1 (mod 3^2 × 372 ). The answer
to the problem is the residue classes
11 , 41 , 62 , 65 , 77 , 95 , 101 , 104 , 110modulo 111.
(Indian Team Selection Test for the International Mathematical Olympiad, 2004,
proposed by S.A. Katre)
769.Ifn+1 is composite, then each prime divisor of(n+ 1 )!is less thann, which also
dividesn!. Then it does not dividen!+1. In this case the greatest common divisor is 1.
Ifn+1 is prime, then by the same argument the greatest common divisor can only be
a power ofn+1. Wilson’s theorem implies thatn+1 dividesn!+1. However,(n+ 1 )^2
does not divide(n+ 1 )!, and thus the greatest common divisor is(n+ 1 ).
(Irish Mathematical Olympiad, 1996)
770.We work modulo 7. None of the six numbers is divisible by 7, since otherwise
the product of the elements in one set would be divisible by 7, while the product of the
elements in the other set would not.
By Wilson’s theorem, the product of the six consecutive numbers is congruent to− 1
modulo 7. If the partition existed, denote byxthe product of the elements in one set.
Then
x^2 =n(n+ 1 )···(n+ 5 )≡− 1 (mod 7).But this is impossible since−1 is not a quadratic residue modulo 7.
(12th International Mathematical Olympiad, 1970)
771.Consider all pairs of numbersiandjwithij≡a(modp). Because the equation
x^2 ≡a(modp)has no solutions,iis always different fromj. Since every nonzero
element is invertible inZp, the pairs exhaust all residue classes modulop. Taking the
product of all such pairs, we obtain
ap− 21
≡(p− 1 )!(modp),which by Wilson’s theorem is congruent to−1, as desired.
772.We claim that ifp≡ 1 (mod 4), thenx =(p− 21 )!is a solution to the equation
x^2 ≡− 1 (modp). Indeed, by Wilson’s theorem,
− 1 ≡(p− 1 )!= 1 · 2 ···(
p− 1
2)(
p+ 1
2)
···(p− 1 )≡ 1 · 2 ···
(
p− 1
2)(
p−
p− 1
2)
·(p− 1 )≡(− 1 )p− 21[(
p− 1
2)
!
] 2
(modp).