Fermat's and Euler's Theorems

Fermat's and Euler's Theorems

Two theorems that play important roles in public-key cryptography are Fermat's theorem and Euler's theorem.

---

[Page 239]

Fermat's Theorem^[4]

^[4] This is sometimes referred to as Fermat's little theorem.

Fermat's theorem states the following: If p is prime and a is a positive integer not divisible by p, then

Equation 8-2

Proof: Consider the set of positive integers less than p:{1,2,..., p 1} and multiply each element by a, modulo p, to get the set X = {a mod p, 2a mod p, . . . (p 1)a mod p}. None of the elements of X is equal to zero because p does not divide a. Furthermore no two of the integers in X are equal. To see this, assume that ja ka(mod p) where 1 j < k p 1. Because a is relatively prime^[5] to p, we can eliminate a from both sides of the equation [see Equation (4.3)] resulting in: j k(mode p). This last equality is impossible because j and k are both positive integers less than p. Therefore, we know that the (p 1) elements of X are all positive integers, with no two elements equal. We can conclude the X consists of the set of integers {1,2,..., p 1} in some order. Multiplying the numbers in both sets and taking the result mod p yields

^[5] Recall from Chapter 4 that two numbers are relatively prime if they have no prime factors in common; that is, their only common divisor is 1. This is equivalent to saying that two numbers are relatively prime if their greatest common divisor is 1.

a x 2a x ... x (p 1) [(1 x 2 x ... x (p 1)](mode p)

a^{p1(p 1)!} (p 1)!(mod p)

We can cancel the (p 1)! term because it is relatively prime to p [see Equation (4.3)]. This yields Equation (8.2).

a = 7, p = 19
72 = 49 11(mod 19)
74 121 7(mod 19)
78 49 7(mod 19)
716 121 7(mod 19)
ap1 = 718 = 716 x 72 7 x 11 1(mod 19)

An alternative form of Fermat's theorem is also useful: If p is prime and a is a positive integer, then

Equation 8-3

Note that the first form of the theorem [Equation (8.2)] requires that a be relatively prime to p, but this form does not.

p = 5,a = 3	ap = 35 = 243 3(mod 5) = a(mod p)
p = 5, a = 10	ap = 105 = 100000 10(mod 5) = 0(mod 5) = a(mod p)