Difference between revisions of "Fermat's Little Theorem"
m |
|||
Line 2: | Line 2: | ||
− | + | == 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 == | |
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 == | |
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 == | |
This theorem is credited to [[Pierre de Fermat]]. | This theorem is credited to [[Pierre de Fermat]]. | ||
− | + | == See also == | |
* [[Number theory]] | * [[Number theory]] |
Revision as of 10: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 is an integer,
is a prime number and
is not divisible by
, then
.
Note: This theorem is a special case of Euler's Totient Theorem.
Corollary
A frequently used corollary of Fermat's Little Theorem is .
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
not divisible by
.
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 . Find the value of
. (AIME 1989/9)
By Fermat's Little Theorem, we know is congruent to
modulo 5. Hence,
![$3 + 0 + 4 + 7 \equiv n\pmod{5}$](http://latex.artofproblemsolving.com/9/a/e/9ae6c19669910fdcb79f9ce3947ec835f29f0733.png)
![$4 \equiv n\pmod{5}$](http://latex.artofproblemsolving.com/0/1/3/01340d89f298149cc82f56f121d194fd13476f30.png)
Continuing, we examine the equation modulo 3,
![$-1 + 1 + 0 + 0 \equiv n\pmod{3}$](http://latex.artofproblemsolving.com/c/4/c/c4ce449e7b124ba4e09da16e3c97742a85d3ad9c.png)
![$0 \equiv n\pmod{3}$](http://latex.artofproblemsolving.com/1/2/d/12dfbd3baa056d0fc22f91f6486c78285ec22d0b.png)
Thus, is divisible by three and leaves a remainder of four when divided by 5. It's obvious that
, so the only possibilities are
or
. It quickly becomes apparent that 174 is much too large, so
must be 144.
Credit
This theorem is credited to Pierre de Fermat.