Fermat’s Little Theorem

OldTrout, Going Postal

\(2^{37} – 1 = 137,438,953,471\)

Fermat was able to factorise large numbers, such as the above, long before the days of calculators and computers by making use of his little theorem.  One could try trial division by primes less than \(2^{37} – 1\) or just some of them.

He had noticed a pattern in geometric progressions.

Consider the following non-zero residue classes modulo \(7\) :

\(
\begin{array}{c|cccccc}
mod \,7\\
\hline
a & 1&2&3&4&5&6\\
a^2&1&4&2&2&4&1\\
a^3&1&1&6&1&6&6\\
a^4&1&2&4&4&2&1\\
a^5&1&4&5&2&3&6\\
a^6&1&1&1&1&1&1
\end{array}
\)

Each row always contains a residue of \(1\) and the last row has residues all equal to \(1\).

Fermat had realised that if a prime \(p\) divides \(2^{37} – 1\), then \(37\) must divide \(p\, – 1\).

Let :

\(
\begin{align}p\,- 1& = 37n\\
p &= 37n + 1
\end{align}
\)

But :

\(p\) is an odd prime

So :

\(p = 37(2k) + 1 = 74k +1\)

where \(n\) and \(k\) are natural numbers.

Therefore, rather than trying to divide by all primes, one just tries to divide by primes of the form \(74k + 1\).

When \(k = 1,\; 75\) is not prime.

When \(k = 2,\; 149\) is prime but does not divide \(2^{37} – 1\).

When \(k =3,\; 223\) is prime and

\(223\cdot616,318,177 = 137,438,953,471\)

 

Fermat’s Little Theorem

If \(p\) is a prime and \(a\) is any integer with gcd\((a, p) = 1\), then

\(a^{p-1}\equiv 1\pmod p\)

Proof :

We consider the set of \(p\, – 1\) integers

{\(a, 2a, 3a, …, (p\, – 1)a\)}.

These \(p\, – 1\) numbers are congruent, in some order, to the numbers in the set

{\(1, 2, 3, …, p\, – 1\)}

consisting of the least positive residues of \(p\), excluding zero.

Multiplying all the numbers in each set together

\(a \times 2a \times 3a \times … \times(p\, – 1)a \equiv 1 \times 2 \times 3 \times … \times(p\, – 1) \pmod p\)

Gives

\(a^{p-1} \times (p\, – 1)! \equiv (p\, – 1)! \pmod p\)

 

Since \(p\) does not divide \((p\, – 1)!\) the latter can be cancelled on both sides of the congruence leaving \(a^{p-1} \equiv 1 \pmod p\).
 

© OldTrout 2018