Computer Science 70: Discrete Mathematics

The Chinese Remainder Theorem

The purpose of this note is to justify in detail our “formal” computation that

100^{50^{25^{10^{5}}}} ≡ 27 (mod 47).

Our main tool will be Euler’s theorem, which we recall here:

Theorem (Euler’s Theorem). Let a be relatively prime to N. Then

a^{φ(N)} ≡ 1 (mod N),

where φ denotes the Euler totient function^{1}.

You proved this result, which is a straightforward generalization of Fermat’s Theorem, in HW 4. We will need one other fact about modular arithmetic:

Theorem (Chinese Remainder Theorem). If m and n are relatively prime positive integers, the system of congruences

x ≡ a (mod m)
x ≡ b (mod n)

has a unique solution (modulo mn).

Proof. We will prove uniqueness first. Suppose x_{0} and x_{1} are both solutions to the above system of congruences. Then

x_{0} ≡ a ≡ x_{1} (mod m)
x_{0} ≡ b ≡ x_{1} (mod n),

so in particular m divides x_{0} − x_{1} and n divides x_{0} − x_{1}. Since m and n are relatively prime, this implies that mn divides x_{0} − x_{1} (check that you know why this is true), so x_{0} ≡ x_{1} (mod mn).

To show existence, we will construct a solution x_{0} explicitly. Since gcd(m, n) = 1, m has an inverse x modulo n and n has an inverse y modulo m. Let

x_{0} = any + bmx.

Then reducing this modulo m, we have

x_{0} ≡ any ≡ a (mod m)

since ny ≡ 1 (mod m), and similarly for the reduction of x_{0} modulo n. Thus x_{0} is the desired solution, and this proves the theorem. □

1Recall that φ(N) is the number of positive integers n ≤ N that are relatively prime to N

Remark. The Chinese Remainder Theorem easily generalizes to the case in which we have k linear congruences with the moduli of the congruences pairwise relatively prime. As an exercise, formulate precisely this generalization and prove your result.

We are now in a position to compute (“rigorously”) the value of

100^{50^{25^{10^{5}}}} (mod 47),

which we do in steps:

(1) We reduce the base modulo 47, so we’re left with the computation of

6^{50^{25^{10^{5}}}} (mod 47).

(2) Subproblem. We can reduce the exponent modulo 46 by Fermat’s theorem (since p = 47 is prime), so we want to compute

50^{25^{10^{5}}} ≡ 4^{25^{10^{5}}} (mod 46).

While we’d like to compute this by reducing the exponent 25^{10^{5}} mod φ(46) = 22, we can’t exactly do this since Euler’s theorem doesn’t apply—46 and 4 are not relatively prime. Instead, we solve the system of linear congruences given by

x ≡ 4^{25^{10^{5}}} (mod 23)
x ≡ 4^{25^{10^{5}}} (mod 2).

(3) Subproblem. To compute

4^{25^{10^{5}}} (mod 23)

we can apply Fermat’s theorem to reduce 25^{10^{5}} modulo 22, and to compute this we can apply Euler’s theorem to reduce 10^{5} modulo φ(22) = (11 − 1)(2 − 1) = 10. But 10^{5} ≡ 0 (mod 10), so 25^{10^{5}} ≡ 1 (mod 22), so

4^{25^{10^{5}}} ≡ 4 (mod 23).

(4) Since

4 ≡ 4^{25^{10^{5}}} (mod 2)

trivially, we know that 4 is a solution to the system of linear congruences. Since

4^{25^{10^{5}}}

is also a solution, we can conclude (by the uniqueness statement of the Chinese Remainder Theorem) that

4^{25^{10^{5}}} ≡ 4 (mod 46).

(5) Thus, back at the highest level, we’re left with the computation of

6^{4} (mod 47),

which one easily finds is 27. Since we didn’t discuss it in class, you weren’t expected to know the

Chinese Remainder Theorem for the midterm: continually applying Euler’s theorem (without regard to the technicality in step 2 above) would have given you the same answer, and this is what we had wanted you to do.