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

m (→See also) |
(added first paragraph) |
||

Line 1: | Line 1: | ||

+ | '''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 === | === Statement === | ||

## Revision as of 23:45, 18 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 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.