Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Fermat's Little Theorem"

(→‎Sample Problem)
m (→‎See also)
Line 32: Line 32:
 
* [[Number theory]]
 
* [[Number theory]]
 
* [[Modular arithmetic]]
 
* [[Modular arithmetic]]
−
* [[Euler's phi function]]
+
* [[Euler's totient function]]
 
* [[Euler's Totient Theorem]]
 
* [[Euler's Totient Theorem]]

Revision as of 14:38, 18 June 2006

Statement

If ${a}$ is an integer and ${p}$ is a prime number, then $a^{p-1}\equiv 1 \pmod {p}$.

Note: This theorem is a special case of Euler's Totient Theorem.

Corollary

A frequently used corolary 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.

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 $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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Fermat%27s_Little_Theorem&oldid=2740"