Introduction to Cryptography with Open-Source Software

Basic num ber theory 43

• φ(37). Since 37 is prime, φ(37) = 36.

• φ(77). Since 77 = 7 ×11, then φ(77) = φ(7)φ(11) = 6 × 10 = 60.

• φ(243). Since 24 3 = 3

5

then φ(243) = 3

4

(3 − 1) = 81 × 2 = 162.

• φ(49, 000). Since 49, 000 = 2

3

× 5

3

× 7

2

then

φ(49, 000) = 2

2

(2 − 1) × 5

2

(5 − 1) × 7

1

(7 − 1) = 16, 800.

Euler’s generalization of Fermat’s theorem states that for any integ e rs a

and n with gcd(a, n) = 1, then

a

φ(n)

= 1 (mod n).

For example, take n = 15. Then φ(15) = 8 and since gcd(4, 15) = 1, the

theorem claims that

4

8

= 1 (mod 15)

and this is in fact true, as can easily be checked. The proof follows the same

line as for that of Fermat’s theorem. Let r

1

, r

2

, . . . , r

φ(n)

be the numbers

less then n and relatively prime to n. Then the residues r

1

a, r

2

a, . . . , r