Difference between revisions of "Fermat's Little Theorem"

(added first paragraph)
m (proofreading)
Line 14: Line 14:
  
 
=== Sample Problem ===
 
=== Sample Problem ===
One of Euler's conjectures was disproved in then 1960s by three American mathematicians when they showed there was a positive integer such that <math>133^5+110^5+84^5+27^5=n^5</math>. Find the value of <math>{n}</math>. ([[AIME]] 1989/9)<br><br>
+
One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that <math>133^5+110^5+84^5+27^5=n^5</math>. Find the value of <math>{n}</math>. ([[AIME]] 1989/9)<br><br>
  
 
By Fermat's Little Theorem, we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5.  Hence,<br>
 
By Fermat's Little Theorem, we know <math>{n^{5}}</math> is congruent to <math>n</math> [[modulo]] 5.  Hence,<br>

Revision as of 12:53, 19 June 2006

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 and ${p}$ is a prime number, then $a^{p-1}\equiv 1 \pmod {p}$.

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

Corollary

A frequently used corolary 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.

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 de Fermat.

See also

Invalid username
Login to AoPS