Advanced book on Mathematics Olympiad

Number Theory 709

βto the customer. The customer computesβk(modn). By Euler’s theorem, this isα.
Success!

784.As before, letpandqbe two large prime numbers known by the United Nations
experts alone. Let alsokbe an arbitrary secret number picked by these experts with the
property that gcd(k, (p− 1 )(q− 1 ))=1. The numbern=pqand the inversemofk
moduloφ(n)=(p− 1 )(q− 1 )are provided to both the country under investigation and
to the United Nations.
The numerical dataαthat comprises the findings of the team of experts is raised
to the powerk, then reduced modulon. The answerβis handed over to the country.
Computingβmmodulon, the country can read the data. But it cannot encrypt fake data,
since it does not know the numberk.

785.We are to find the smallest positive solution to the system of congruences

x≡ 1 (mod 60),

x≡ 0 (mod 7).

The general solution is 7b 1 + 420 t, whereb 1 is the inverse of 7 modulo 60 andtis an
integer. Sinceb 1 is a solution to the Diophantine equation 7b 1 + 60 y=1, we find it
using Euclid’s algorithm. Here is how to do it: 60= 8 · 7 +4, 7= 1 · 4 +3, 4= 1 · 3 +1.
Then

1 = 4 − 1 · 3 = 4 − 1 ·( 7 − 1 · 4 )= 2 · 4 − 7 = 2 ·( 60 − 8 · 7 )− 7

= 2 · 60 − 17 · 7.

Henceb 1 =−17, and the smallest positive number of the form 7b 1 + 420 tis− 7 · 17 +
420 · 1 =301.
(Brahmagupta)

786.Letp 1 ,p 2 ,...,p 2 nbe different primes. By the Chinese Remainder Theorem there
existsxsuch that

x≡ 0 (modp 1 p 2 ),

x≡− 1 (modp 3 p 4 ),

···

x≡−n+ 1 (modp 2 n− 1 p 2 n).

Then the numbersx+k,0≤k≤n−1, are each divisible byp 2 k+ 1 p 2 k+ 2 , and we
are done.

Remark.This problem shows a nontrivial way in which there exist arbitrarily long arith-
metic progressions containing no prime numbers.