Fermat's Little Theorem

Revision as of 03:07, 27 February 2010 by Azjps (talk | contribs) (expansion)

Fermat's Little Theorem is highly useful in number theory for simplifying the computation of exponents in modular arithmetic (which students should study more at the introductory level if they have a hard time following the rest of this article). This theorem is credited to Pierre de Fermat.


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

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

This theorem is a special case of Euler's Totient Theorem, which states that if $a$ and $n$ are integers, then $a^{\varphi(n)} \equiv 1 \pmod{p}$, where $\varphi(n)$ denotes Euler's totient function. In particular, $\varphi(p) = p-1$ for prime numbers $p$.

Proof

We offer several proofs using different techniques to prove the statement $a^p \equiv a \pmod{p}$. If $\text{gcd}\,(a,p) = 1$, then we can cancel a factor of $a$ from both sides and retrieve the first version of the theorem.

Proof 1 (Induction)

The most straightforward way to prove this theorem is by by applying the induction principle. We fix $p$ as a prime number. The base case, $1^p \equiv 1 \pmod{p}$, is obviously true. Suppose the statement $a^p \equiv a \pmod{p}$ is true. Then, by the binomial theorem,

\[(a+1)^p = a^p + {p \choose 1} a^{p-1} + {p \choose 2} a^{p-2} + \cdots + {p \choose p-1} a + 1.\]

Note that $p$ divides into any binomial coefficient of the form ${p \choose k}$ for $1 \le k \le p-1$. This follows by the definition of the binomial coefficient as ${p \choose k} = \frac{p!}{k! (p-k)!}$; since $p$ is prime, then $p$ divides the numerator, but not the denominator.

Taken $\mod p$, all of the middle terms disappear, and we end up with $(a+1)^p \equiv a^p + 1 \pmod{p}$. Since we also know that $a^p \equiv a\pmod{p}$, then $(a+1)^p \equiv a+1 \pmod{p}$, as desired.

Proof 2 (Inverses)

Let $S = \{1,2,3,\cdots, p-1\}$. Then, we claim that the set $a \cdot S$, consisting of the product of the elements of $S$ with $a$, taken modulo $p$, is simply a permutation of $S$. In other words,

\[S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}.\]


Clearly none of the $ia$ for $1 \le i \le p-1$ are divisible by $p$, so it suffices to show that all of the elements in $a \cdot S$ are distinct. Suppose that $ai \equiv aj \pmod{p}$ for $i \neq j$. Since $\text{gcd}\, (a,p) = 1$, by the cancellation rule, that reduces to $i \equiv j \pmod{p}$, which is a contradiction.

Thus, $\mod{p}$, we have that the product of the elements of $S$ is

\[1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}.\]


Cancelling the factors $1, 2, 3, \ldots, p-1$ from both sides, we are left with the statement $a^{p-1} \equiv 1 \pmod{p}$.

A similar version can be used to prove Euler's Totient Theorem, if we let $S = \{\text{natural numbers relatively prime to and less than}\ n\}$.

Proof 3 (Combinatorics)

[asy]  real r = 0.3, row1 = 3.5, row2 = 0, row3 = -3.5; void necklace(pair k, pen colors[]){  draw(shift(k)*unitcircle);   for(int i = 0; i < colors.length; ++i){   pair p = k+expi(pi/2+2*pi*i/colors.length);   fill(Circle(p,r),colors[i]);   draw(Circle(p,r));  } }  pen BEADS1[] = {red,red,red},BEADS2[] = {blue,blue,blue},BEADS3[] = {red,red,blue},BEADS4[] = {blue,red,red},BEADS5[] = {red,blue,red},BEADS6[] = {blue,blue,red},BEADS7[] = {red,blue,blue},BEADS8[] = {blue,red,blue}; necklace((-1.5,row1),BEADS1);necklace((1.5,row1),BEADS2);necklace((-2.5,row2),BEADS3);necklace((0,row2),BEADS4);necklace((2.5,row2),BEADS5);necklace((-2.5,row3),BEADS6);necklace((0,row3),BEADS7);necklace((2.5,row3),BEADS8); [/asy]
An illustration of the case $a=2,p=3$.

Consider a necklace with $p$ beads, each bead of which can be colored in $a$ different ways. There are $a^p$ ways to pick the colors of the beads. $a$ of these are necklaces that consists of beads of the same color. Of the remaining necklaces, for each necklace, there are exactly $p-1$ more necklaces that are rotationally equivalent to this necklace. It follows that $a^p-a$ must be divisible by $p$. Written in another way, $a^p \equiv a \pmod{p}$.

Proof 4 (Geometry)

We imbed a hypercube of side length $a$ in $\mathbb{R}^p$ (the $p$-th dimensional Euclidean space), such that the vertices of the hypercube are at $(\pm a/2,\pm a/2, \ldots, \pm a/2)$. A hypercube is essentially a cube, generalized to higher dimensions. This hypercube consists of $a^p$ separate unit hypercubes, with centers consisting of the points

\[P(x_1, x_2, \ldots, x_n) = \left(a + \frac 12 - x_1, a + \frac 12 - x_2, \ldots, a + \frac 12 - x_p\right),\]


where each $x_i$ is an integer from $1$ to $a$. Besides the $a$ centers of the unit hypercubes in the main diagonal (from $(-a/2, -a/2, \ldots, -a/2)$ to $(a/2, a/2, \ldots, a/2)$), the transformation carrying

\[P(x_1, x_2, \ldots, x_n) \mapsto P(x_2, x_3, \ldots, x_n, x_1)\]

maps one unit hypercube to a distinct hypercube. Much like the combinatorial proof, this splits the non-main diagonal unit hypercubes into groups of size $p$, from which it follows that $a^p \equiv a \pmod{p}$. Thus, we have another way to visualize the above combinatorial proof, by imagining the described transformation to be, in a sense, a rotation about the main diagonal of the hypercube.

Problems

Introductory

  • Compute some examples, for example find $3^{31} \pmod{7}, 29^{25} \pmod{11}$, and $128^{129} \pmod{17}$, and check your answers by calculator where possible.
    • For the first example, we have $3^6 \equiv 1 \pmod{7}$ by FLT (Fermat's Little Theorem). It follows that $3^{31} = 3 \cdot 3^{30} = 3 \cdot \left(3^{6}\right)^5 \equiv 3 \cdot 1^5 \equiv 3 \pmod{7}$

Intermediate

  • 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}$. (1989 AIME, #9)

To solve this problem, it would be nice to know some information about the remainders $n$ can have after division by certain numbers. 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.

Advanced

  • Show that if $p$ is a prime number, and $k$ is an integer $2 \le k \le p$, then the sum of the products of each $k$-element subset of $\{1, 2, \ldots, p\}$ is divisible by $p$.

See also