Difference between revisions of "Fermat's Little Theorem"
Djshowdown2 (talk | contribs) (→Sample Problem) |
Djshowdown2 (talk | contribs) (→Sample Problem) |
||
Line 14: | Line 14: | ||
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> | ||
− | <center><math>3 + 0 + 4 + 7 \equiv n\pmod{5}</math></center | + | <center><math>3 + 0 + 4 + 7 \equiv n\pmod{5}</math></center> |
− | <center><math>4 \equiv n\pmod{5}</math></center><br> | + | <center><math>4 \equiv n\pmod{5}</math></center> |
− | Continuing, we examine the equation modulo 3, | + | |
− | <center><math>-1 + 1 + 0 + 0 \equiv n\pmod{3}</math></center | + | <br>Continuing, we examine the equation modulo 3, |
− | <center><math>0 \equiv n\pmod{3}</math></center><br> | + | <center><math>-1 + 1 + 0 + 0 \equiv n\pmod{3}</math></center> |
− | 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. | + | <center><math>0 \equiv n\pmod{3}</math></center> |
+ | |||
+ | <br>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 === |
Revision as of 14:31, 18 June 2006
Statement
If is an integer and
is a prime number, then
.
Note: This theorem is a special case of Euler's totient theorem.
Corollary
A frequently used corolary of Fermat's little theorem is .
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 then 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.