Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

4 Answers 4

up vote 12 down vote accepted

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

share|improve this answer

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.

share|improve this answer
1  
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

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.