Purpose of Fermat's Little Theorem

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.