Difference between revisions of "Fermat's Little Theorem"

m
Line 2: Line 2:
  
  
=== Statement ===
+
== Statement ==
  
 
If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{p-1}\equiv 1 \pmod {p}</math>.
 
If <math>{a}</math> is an [[integer]], <math>{p}</math> is a [[prime number]] and <math>{a}</math> is not [[divisibility|divisible]] by <math>{p}</math>, then <math>a^{p-1}\equiv 1 \pmod {p}</math>.
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]].
  
=== Corollary ===
+
== Corollary ==
  
 
A frequently used corollary of Fermat's Little Theorem is <math> a^p \equiv a \pmod {p}</math>.
 
A frequently used corollary of Fermat's Little Theorem is <math> a^p \equiv a \pmod {p}</math>.
 
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 <math>{a}</math> not divisible by <math>{p}</math>.
 
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 <math>{a}</math> not divisible by <math>{p}</math>.
  
=== Sample Problem ===
+
== 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 <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>
  
Line 27: Line 27:
 
Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5.  It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n = 174</math>.  It quickly becomes apparent that 174 is much too large, so <math>n</math> must be 144.
 
Thus, <math>n</math> is divisible by three and leaves a remainder of four when divided by 5.  It's obvious that <math>n>133</math>, so the only possibilities are <math>n = 144</math> or <math>n = 174</math>.  It quickly becomes apparent that 174 is much too large, so <math>n</math> must be 144.
  
=== Credit ===
+
== Credit ==
  
 
This theorem is credited to [[Pierre de Fermat]].
 
This theorem is credited to [[Pierre de Fermat]].
  
=== See also ===
+
== See also ==
  
 
* [[Number theory]]
 
* [[Number theory]]

Revision as of 09:15, 8 November 2007

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.

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

See also