s
Section 5.6 The Mighty Mod Function
445
This result is known as Fermat’s little theorem (as opposed to the very famous Fermat’s last theorem mentioned in Section 2.4).
Let S = 50, a, 2a, …, (p − 1)a6, T = 50, 1, 2, …, (p − 1)6. Let f be given by f (ka) = (ka) mod p;
that is, f computes the residue modulo p.
a. Prove that f is a one-to-one function from S to T.
b. Prove that f is an onto function.
c. Prove that 3a # 2a c (p − 1)a4 mod p = (p − 1)! mod p
d. Prove that a
p−1
≡ 1 (mod p)
e. Let a = 4 and p = 7. Compute the set of residues modulo p of 54, 8, 12, …, 246.
f. Let a = 4 and p = 7. Show by direct computation that 4
6
≡ 1(mod 7).
40. Let m 1 , m 2 , …, m n be pairwise relatively prime positive integers (that is, gcd(m i , m k ) = 1 for
1 ≤ i, k ≤ n, i ∙ k), let m = m 1 m 2 c m n , and let a 1 , a 2 , c, a n be any integers. Then there is an integer
x such that
x ≡ a 1 (mod m 1 )
x ≡ a 2 (mod m 2 )
(
x ≡ a n (mod m n )
and any other integer y that satisfies these relations is congruent to x modulo m. This result is known as
the Chinese remainder theorem (based on work done by the Chinese mathematician Sun-Tsu in the first
century ad). The following steps will prove the Chinese remainder theorem.
a. Let s and t be positive integers with gcd (s, t) = 1. Prove that there exists an integer w such that
sw ≡ 1 (mod t).
b. For each i, 1 ≤ i ≤ n, let M i = m∙m i . Prove that gcd(M i , m i ) = 1.
c. Prove that there is an integer x i such that M i x i ≡ 1 (mod m i ) and a i M i x i ≡ a i (mod m i ).
d. Prove that a k M k x k ≡ 0 (mod m i ) for all k ∙ i.
e. Let x = a 1 M 1 x 1 + a 2 M 2 x 2 + c + a n M n x n . Prove that for 1 ≤ i ≤ n, x ≡ a i (mod m i ).
f. Let y be such that y ≡ a i (mod m i ), 1 ≤ i ≤ n. Prove that x ≡ y (mod m). (Hint: Use the fundamental
theorem of arithmetic and write m as a product of distinct primes, m = p
k 1
1 p
k 2
2 … p
k t
t ).
41. The remaining step in the proof of the RSA algorithm is to show that if d # e ≡ 1 mod w(n), then
T
ed
mod n = T .
a. Prove that T
ed
can be written as T(T
p−1
)
k(q−1)
or as T(T
q−1
)
k(p−1)
for some integer k.
b. Prove that if T is not divisible by p, then T
ed
≡ T (mod p), and if T is not divisible by q, then
T
ed
≡ T (mod q).
c. Prove that if p 0 T , then T
ed
≡ T (mod p) and T is not divisible by q, so T
ed
≡ T (mod q) by part (b).
d. Prove that if q 0 T , then T
ed
≡ T (mod q) and T is not divisible by p, so T
ed
≡ T (mod p) by part (b).
e. From parts (b)–(d ) T
ed
≡ T (mod p) and T
ed
≡ T (mod q) in all cases. Prove that T
ed
mod n = T .