78
Chapter 3. Basic Number T heory
x = 1 x = —1 x = -1
(mod 5), (mod 5), (mod 5),
x = —1
x = 1
x = —1
(mod 7)
(mod 7)
(mod 7)
— ►
— ►
— »
x = G
x = 29
x = 34
(mod 35),
(mod 35),
(mod 35).
So the solutions of x2 = 1 (mod 35) are x = 1,6,29,34 (mod 35).
In general, if n = p\pi •–pr is the product of r distinct odd primes, then
x2 = 1 (mod n) has 2r solutions. This is a consequence of the following.
Chinese Remainder Theorem (General Form). Let
be integers with gcd(ml,mj) = 1 whenever i ^ j. Given integers ol, …, at, there exists exactly one solution x (mod mi ••■m^) to the simultaneous congruences
x = aj (mod mj), x = a2 (mod rnn), x = (mod mu).
For example, the theorem guarantees there is a solution to the simulta
neous congruences
x = I (mod 11), x = —1 (mod 13), x = 1 (mod 17).
In fact, x s 1871 (mod 11 •13 •17) is the answer.
Exercise 24 gives a method for computing the number x in the theorem.
3.5 Modular Exponentiation
Throughout this book, we will be interested in numbers of the form
xa (mod n).
In this and the next couple of sections, we discuss some properties of numbers raised to a power modulo an integer.
Suppose we want to compute 2123,1 (mod 789). If we first compute 2123,1, then reduce mod 789, we’ll be working with very large numbers, even though the final answer has only 3 digits. We should therefore perform each multipli cation and then calculate the remainder. Calculating the consecutive powers of 2 would require that we perform the modular multiplication 1233 times. Tliis is method is too slow to be practical, especially when the exponent becomes very large. A more efficient way is the following (all congruences will be mod 789).
3.6. Fermat and Euler 79
We start with 22 = 4 (mod 789) and repeatedly square both sides to obtain the following congruences:
2’17 42=16
28 = 162E=256
2io 232 2