# Purpose of Fermat's Little Theorem

What is the purpose of using Fermat's Little Theorem, and a proof of it?

-
Did you try en.wikipedia.org/wiki/Fermat's_little_theorem ? –  lhf Apr 20 '11 at 10:37
There are a full 6 proofs on wikipedia. –  mixedmath Apr 20 '11 at 16:39
What do you mean by "purpose?" –  Thomas Andrews Apr 20 '11 at 19:48

Below is what Weil wrote on proofs of Fermat's little theorem, from p. 56 of his Number theory: An approach through history. As for its purpose, it helps serve to reveal the multiplicative structure of $\rm\:\mathbb Z/p\:,\:$ and problems in $\rm\:\mathbb Z\:$ are often best solved by reducing them to much simpler problems in its finite images $\rm\:\mathbb Z/p\:,\:$ e.g. so-called "local-global" principles. No doubt a search on "Fermat little" will uncover many applications - both here and elsewhere.

-

In modular arithmetic e.g. mod m you can reduce big numbers down to numbers between 0 and m.

Fermat's little theorem lets you reduce the exponents (of numbers of the form $b^e$) down to numbers between 0 and $\varphi(m)$ (without knowing anything about the base).

For example of the first, $x = 0,1,2$ or $3$ mod 4 so the number $x^2$ must be equal to 0 or 1 mod 4. So $x^2$ is of the form 4k or 4k+1.

For an example of the second, if p is prime $\varphi(p) = p-1$ then $p^2 = 1$ mod p-1 so $x^{(p^2)} = x$ mod p. I just made that up but you can probably see from it that you can use this for lots of things.

-
Surprisingly, Euler's extension of Fermat's Little Theorem plays a crucial role in modern cryptography. –  lhf Apr 20 '11 at 10:38

We prove by fermat's little theorem by induction. Firstly, the base case tells us that

$1^{p} \equiv 1$ (mod $p$), which is true.

Assume true for $a=k$, namely that we assume $k^{p} \equiv k$ (mod $p$).

Then for $a = k+1$, we observe that $(k+1)^p - (k^p +1) = pk$ + $p \choose 2$ $k^2$ + $\ldots$ $k^{p-1}$ $p\choose p-1$.

I leave it as an exercise to check that the R.H.S. is divisible by $p$, and so we have the chain of congruences (using the induction hypothesis) that $(k+1)^p \equiv k^p + 1 \equiv k+1$ (mod $p$). So the statement of fermat's little theorem is true for $a = 1$, $a = k$ and $a = k+1$ and hence is true for all natural numbers $k$.

$\hspace{6in}\blacksquare$

Ben

-

Fermat's little theorem states that, for a prime $p$:

$$a^p \equiv a \pmod{p}$$

alternatively:

$$a^{p-1} \equiv 1 \pmod{p}$$

The easiest proof that I've seen is as follows: Consider any integer, $g$, that is relatively prime to $p$. Let $x$ be the product of all of the (distinct) integers $\pmod{p}$. i.e.:

$$x = 1 \cdot 2 \cdot 3 \dots (p-1) \pmod{p}$$

Now, multiply each term on the right by $g$:

$$g^{p-1} x = (g \cdot 1) (g \cdot 2) (g \cdot 3) \dots (g \cdot (p-1)) \pmod{p}$$

Since multiplication is 1-1 and onto, all this does is permute the values involved in the product on the right to give back $x$. So:

$$g^{p-1} x = x \pmod{p}$$ $$g^{p-1} = 1 \pmod{p}$$

One needs to prove multiplication is 1-1 and onto (for $p$ prime), but once that's done, the proof above is (in my opinion) straight forward and simple.

EDIT: I originally restricted the product, $x$, to be the product of powers of a generator, $g$. As lhf points out, this can be any number. I've changed the above to reflect this.

-
No need to use a generator. Consider the product of $ax$ for $x=1,\dots,p-1$. –  lhf Apr 20 '11 at 11:57
Wow, that's not "easy" because knowing that there is a generator for the multiplicative group is non-trivial, isn't it? And if you are gonna jump to group theory, you know that $g^{|G|}=1$ for all $g\in G$ for any group $G$, so you don't really need a generator. –  Thomas Andrews Apr 20 '11 at 19:26
@lhf, you are absolutely right. @Thomas, the above proof without the generator condition is now much simpler. –  user4143 Apr 21 '11 at 1:13