# Purpose of Fermat's Little Theorem

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

#### Solutions Collecting From Web of "Purpose of Fermat's Little Theorem"

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.

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.