# A proof using Fermat's Little Theorem?

Let $p$ be prime and let $a\in Z$ such that p doesn't divide a (sorry I couldn't find the symbol for it in MathJaX). Prove that if $k$ is the smallest integer such that $a^k\equiv 1 \pmod p$, then $k|(p-1)$.

I feel like i have to use the division algorithm. And also that the easiest way to approach this would be by way of contradiction. Any ideas?

• p \nmid a $p \nmid a$ (you should also use \mid for "divides": $k \mid (p+1)$). – fkraiem Mar 11 '14 at 22:45

Hint $\$ With only slightly more effort one can view this as a special case of a basic result.

The set $\,\cal O\,$ of integers $\rm\:n >0\:$ such that $\rm\:a^n \equiv 1\:$ is closed under positive subtraction, i.e.

$$\rm \color{#0A0}n>\color{#C00}m\,\in\,{\cal O}\ \Rightarrow\ 1\equiv \color{#0A0}{a^n} \equiv a^{n-m}\, \color{#C00}{a^m} \equiv a^{n-m}\, \Rightarrow\ n\!-\!m\,\in\,{\cal O}$$

Thus, by theorem below, every element of $\rm\,\cal O\,$ is divisible by its least element $\rm\:\ell\ \!$ := order of $\rm\,a.$

Theorem $\ \$ If a nonempty set of positive integers $\rm\,\cal O\,$ satisfies $\rm\ n > m\, \in\, {\cal O} \ \Rightarrow\ n\!-\!m\, \in\, \cal O$
then every element of $\rm\,\cal O\,$ is a multiple of the least element $\rm\:\ell \in\cal O.$

Proof $\$ If not there's a least nonmultiple $\rm\:n\in \cal O,\:$ contra $\rm\:n\!-\!\ell \in \cal O\:$ is a nonmultiple of $\rm\:\ell. \,$ QED

For more on the key innate structure see this post on order ideals and denominator ideals.

you know that $$a^{p-1}=1\mod p$$ Write p-1 = kq + r, then

$$1 = a^{p-1}= a^{kq} a ^r = a^r \mod p$$and as $r<k$, $r=0$.

There's also a group theoretical proof. The group of invertible elements in $\mathbb{Z}/p\mathbb{Z}$ has order $p-1$. By Lagrange's theorem, the order of each element is a divisor of the group order.

Indeed, let $G$ be a finite group; if $g\in G$, the least positive integer $k$ such that $g^k=1$ equals the cardinality of $\langle g\rangle=\{g^n:n\in\mathbb{Z}\}$, which is a subgroup of $G$.