Difference between revisions of "Fermat's Little Theorem"

m (category)
m (proof)
Line 8: Line 8:
  
 
Note: This theorem is a special case of [[Euler's Totient Theorem]].
 
Note: This theorem is a special case of [[Euler's Totient Theorem]].
 +
 +
== Proof ==
 +
Let <math>S = \{1,2,3,\cdots, p-1\}</math>. Then, we note that <math>S = \{1a, 2a, \cdots, (p-1)a\} \pmod{p}</math>. Clearly none of the <math>ai</math> may be divisible by <math>p</math>, so it suffices to show that all of the elements in the latter set are distinct. If <math>ai \equiv aj \pmod{p}</math> for <math>\text{gcd}\, (a,p) = 1</math>, then by the cancellation rule, <math>i \equiv j \pmod{p}</math>. Thus, the product of the elements of <math>S</math> written in two ways, taken <math>\mod{p}</math>, gives <math>1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots p-1 \pmod{p}</math>. Cancelling again, we have <math>a^{p-1} \equiv 1 \pmod{p}</math>.
 +
 +
A similar version can be used to prove [[Euler's Totient Theorem]], if we let <math>S = \{\text{natural numbers relatively prime and less than}\ n\}</math>.
  
 
== Corollary ==
 
== Corollary ==

Revision as of 13:23, 28 January 2009

This is an AoPSWiki Word of the Week for July 25-July 31

Fermat's Little Theorem is highly useful in number theory for simplifying computations in modular arithmetic (which students should study more at the introductory level if they have a hard time following the rest of this article).

Statement

If ${a}$ is an integer, ${p}$ is a prime number and ${a}$ is not divisible by ${p}$, then $a^{p-1}\equiv 1 \pmod {p}$.

Note: This theorem is a special case of Euler's Totient Theorem.

Proof

Let $S = \{1,2,3,\cdots, p-1\}$. Then, we note that $S = \{1a, 2a, \cdots, (p-1)a\} \pmod{p}$. Clearly none of the $ai$ may be divisible by $p$, so it suffices to show that all of the elements in the latter set are distinct. If $ai \equiv aj \pmod{p}$ for $\text{gcd}\, (a,p) = 1$, then by the cancellation rule, $i \equiv j \pmod{p}$. Thus, the product of the elements of $S$ written in two ways, taken $\mod{p}$, gives $1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots p-1 \pmod{p}$. Cancelling again, we have $a^{p-1} \equiv 1 \pmod{p}$.

A similar version can be used to prove Euler's Totient Theorem, if we let $S = \{\text{natural numbers relatively prime and less than}\ n\}$.

Corollary

A frequently used corollary of Fermat's Little Theorem is $a^p \equiv a \pmod {p}$. As you can see, it is derived by multipling both sides of the theorem by a. The restated form is nice because we no longer need to restrict ourselves to integers ${a}$ not divisible by ${p}$.

Sample Problem

One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that $133^5+110^5+84^5+27^5=n^5$. Find the value of ${n}$. (AIME 1989/9)

By Fermat's Little Theorem, we know ${n^{5}}$ is congruent to $n$ modulo 5. Hence,

$3 + 0 + 4 + 7 \equiv n\pmod{5}$
$4 \equiv n\pmod{5}$



Continuing, we examine the equation modulo 3,

$-1 + 1 + 0 + 0 \equiv n\pmod{3}$
$0 \equiv n\pmod{3}$




Thus, $n$ is divisible by three and leaves a remainder of four when divided by 5. It's obvious that $n>133$, so the only possibilities are $n = 144$ or $n = 174$. It quickly becomes apparent that 174 is much too large, so $n$ must be 144.

Credit

This theorem is credited to Pierre Fermat.

See also