**Fermat’s Theorem**: Let p be a prime and suppose that p ∤ a. Then a^{p }– 1 ≡ 1(mod p)

**Proof**: We start by considering the first that p – 1 positive multiplies of a; that is the integers

a, 2a, 3a, …, (p – 1)a

None of this numbers is congruent to modulo p to any other, nor is any congruent to zero. Indeed, if it happen that

ra ≡ sa (mod p) 1 ≤ r < s ≤ p – 1

Then a could be cancelled to give r ≡ s (mod p), which is impossible. Therefore, the previous set of integers must be congruent modulo p to 1, 2, 3,…, p – 1 , taken in some order. Multiplying all this congrunces together, we find that

- 2a. 3 … (p – 1 )a ≡ 1. 2. 3 … (p – 1) (mod p)

whence

a^{p – 1 }(p – 1) ! ≡ (p – 1) ! (mod p)

Once (p – 1) ! is cancelled from both sides of he preceding congruence , our line of reasoning cultimaes in the statement that a^{p – 1 }≡ 1 (mod p), which is fermat’s theorem. (Proved)

**Corollary**: If p is a prime, then a^{p} ≡ a(mod p) for any integer a.

**Proof**: When p | a, the statement obviously holds; for in this setting, a^{p} ≡0≡a(mod p). If p ∤ a , the according to Fermat’s theorem, we have a^{p – 1 }≡ a(mod p), when this congruent is multiplied by a, the conclusion a^{p} ≡ a(mod p). (Proved)

**Theorem**: If n is an odd peseudoprime, then M_{n} = 2^{n} – 1 is larger one.

**Proof**: Since n is a composite number, we can write n = rs, with1 < r ≤ s < n. Then 2^{r} – 1 | 2^{n} – 1 , or equivalently 2^{r} – 1 | M_{n, }making M_{n} composite. By our hypothesis 2^{n} ≡ 2(mod n); hence 2^{n} – 2 = kn for some integer k. It follows that

2^{M}_{n} – 1 = 2^{2^n – 2} = 2^{kn}

This yields

2^{M}_{n} – 1= 2^{kn} – 1

= (2^{n} – 1 ) (2^{n(k – 1 )} + 2^{n(k – 2 )} + … + 2^{n} + 1)

= M_{n} (2^{n(k – 1 )} + 2^{n(k – 2 )} + … + 2^{n} + 1)

≡ 0 (mod M_{n})

We see immediately that 2^{M}_{n} – 1≡ 0(mod M_{n}), in light of which M_{n} is a peseudoprime. (Proved)