Difference between revisions of "Fermat's Little Theorem"

Revision as of 16:24, 26 July 2008

This is an AoPSWiki Word of the Week for July 25-July 31

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 ${a}$ is an integer, ${p}$ is a prime number and ${a}$ is not divisible by ${p}$ , then $a^{p-1}\equiv 1 \pmod {p}$ .

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

Corollary

A frequently used corollary 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. The restated form is nice because we no longer need to restrict ourselves to integers ${a}$ not divisible by ${p}$ .

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

Revision as of 09:15, 8 November 2007 (view source) Minsoens (talk \| contribs) m ← Older edit		Revision as of 16:24, 26 July 2008 (view source) Mrosett (talk \| contribs) Newer edit →
Line 1:		Line 1:
		+	{{WotWAnnounce\|week=July 25-July 31}}
		+
		+
	'''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).		'''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).

Page

Toolbox

Search