# Difference between revisions of "Fermat's Little Theorem"

(→See also: fixed euler link) |
IntrepidMath (talk | contribs) |
||

Line 21: | Line 21: | ||

<center><math>0 \equiv n\pmod{3}</math></center> | <center><math>0 \equiv n\pmod{3}</math></center> | ||

− | <br><br><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. | + | <br><br><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 15:32, 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,

Continuing, we examine the equation modulo 3,

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.