Euler’s Theorem-Fermat’s Theorem

Theorem 2.1.13 Let n ≥ 2 be an integer.

1. (Euler’s Theorem)If a Є Z*n, then a^φ(n)≡1 (mod n).

2. If n is a pro duct of distinct primes, and if r ≡ s (mod φ(n)), then a^r ≡ a^s (mod n)

for all integers a. In other words, when working modulo such an n exponents can

be reduced modulo φ(n).

Definition 2.1.12 Let a, b Є Zn. The multiplicative inverse of a modulo n is an integer

x Є Zn such that ax ≡ 1(mod n). If such an x exists, then it is unique, and a is said to

be invertible,or a unit; the inverse of a is denoted by a^-1.

Theorem 2.1.14 Let a Є Zn. Then a is invertible if and only if gcd(a, n)=1.

Proof First, if gcd(a, n) were greater than 1, we could not have ab =1(mod n) for any b,

because that would imply that d divides ab - 1 and hence divides 1.

A special case of Euler’s theorem is Fermat’s (little) theorem.

Theorem 2.1.15 Let p be a prime.

1. (Fermat’s Theorem) If gcd(a, p) = 1, then a^p-1 ≡ 1(mod p).

2. In particular, a^p ≡ a (mod p) for all integers a.

Definition 2.1.13 Let a Є Z*n. The order of a, is denoted ord(a), is the least positive

integer t such that a^t ≡ 1(mod n).

Theorem 2.1.16 If the order of a Є Z*n is t, and a^s ≡ 1(mod n), then t divides s.In

particular, t| φ(n).

Definition 2.1.14 Let a Є Z*n. If the order of g is φ(n), then g is said to be a generator

or a primitive element of Z*n.If Z*n has a generator, then Z* is said to be cyclic.