Fermat's Little Theorem, Example, Proof

Fermat's Little Theorem is also known as Fermat's Theorem. This theorem illustrates that, if 'p' is prime, there does not exist a base, such that it possesses a nonzero residue modulo.

Fermat's Little Theorem, Example, Proof

Statement
This theorem states that, if 'p' is a prime number and 'a' is an interger then ap-1 ≡ 1 (mod p).

Proof
Consider 'a' is positive and not divisible by 'p'. So, we can write the sequence of numbers as a, 2a, 3a, ..., (p-1)a, reduce each one modulo p.
The resulting sequence rearrangement of the form is, 1, 2, 3, ..., (p-1).

By the FERMAT'S theorem,
Multiply the numbers in each sequence, the result must be identical modulo of p,
a × 2a × 3a × ... × (p-1)a ≡ 1 × 2 × 3 × ... × (p-1) (mod p)
( 1 × 2 × 3 × ... × p-1) × (a × a × a × ... × a) ≡ 1 × 2 × 3 × ... × (p-1) (mod p)
(p-1)! ap-1 ≡ (p-1)! (mod p),

Cancellation of (p-1)! , on both sides in the above equation which gives,
ap-1 ≡ 1 (mod p)

Example
Let us consider, a = 8, p = 9
The sequence of numbers are,
8, 16, 24, 32, 40, 48, 56, 64

Reduce mod 9, then the sequence of numbers are,
8, 7, 6, 5, 4, 3, 2, 1
By rearranging the above sequence,
1, 2, 3, 4, 5, 6, 7, 8

From the theorem,
8 × 16 × 24 × 32 × 40 × 48 × 56 × 64 ≡ 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 (mod 9)
(8×8×8×8×8×8×8×8) × (1 × 2 × 3 × 4 × 5 × 6 × 7 × 8) ≡ 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 (mod 9)
88 × (1 × 2 × 3 × 4 × 5 × 6 × 7 × 8) ≡ 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 (mod 9)
Cancelling on both sides,
88 ≡ 1 (mod 9). [By the theorem ap-1 ≡ 1 (mod p) ]

Hence the Fermat's Little Theorem is proved.
Code to add this calci to your website Expand embed code Minimize embed code

english Calculators and Converters