6
$\begingroup$

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

  • 2
    What do you mean by "purpose?"2011-04-20

4 Answers 4

14

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.

enter image description here enter image description here

3

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.

  • 0
    @lhf: Actually Fermat's little theorem is enough for RSA, and Euler's theorem is not needed. The reason is that given distinct primes $p,q$ and $jk = a(p-1)(q-1)+1$ we have $x^{jk} \equiv (x^{a(p-1)})^{q-1} \cdot x \equiv x \pmod{q}$ (using Fermat's little theorem if $q \nmid x$), and by symmetry $x^{jk} \equiv x \pmod{p}$, and hence $p,q \nmid x^{jk}-x$, and the proof is finished using Euclid's lemma. =)2017-02-02
2

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.

  • 0
    @lhf, you are absolutely right. @Thomas, the above proof without the generator condition is now much simpler.2011-04-21
1

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