# Let $r$ be the smallest positive integer such that $a^r \equiv 1 \bmod{n}$. Prove $r \mid \phi(n)$.

Let $a \in \mathbb {Z}$, $n > 1$ a natural number with $\gcd(a, n) = 1$, and let $r$ be the smallest positive integer such that $a^r \equiv 1 \bmod{n}$. Prove that $r \mid \phi(n)$.

Euler's generalization of Fermat's Little Theorem: If $n \in \mathbb {N}$ and $m \in \mathbb{Z}$ such that $\gcd(m, n) = 1$, then $m^{\phi(n)} \equiv 1\bmod(n)$.

By Euler's generalization I would have $a^{\phi(n)} \equiv 1\bmod{n}$.

Then I could say $a^r \equiv a^{\phi(n)} \equiv 1 \bmod{n}$. At this point I can see that $r$ clearly must be some multiple of $\phi(n)$.

If I want to show that $r \mid \phi(n)$, then I can show that $\phi(n) = rk$, for some $k \in \mathbb {Z}$.

However, I am a bit stuck about how to make this last step showing that $\phi(n) = rk$, where $k \in \mathbb {Z}$.

• If $r$ does not divide $\phi(n)$, show that there is a smaller $r'>0$ such that $a^{r'}\equiv 1$. So it is proof by contradiction... Mar 20 '14 at 3:39

Hint $$\ \color{#c00}{a^{\large k}\equiv 1\equiv a^{\large r}}\Rightarrow\,a^{\large (r,k)}\equiv 1\,$$ since by Bezout the gcd $$\,(k,r) = ik\!+\!jr,\,$$ for some $$\, i,j\in\Bbb Z.\,$$ Thus with $$\,k= \phi,\$$ if $$\,\ r\nmid \phi\,\$$ then $$\ (\phi,r) < r\,$$ and $$\, a^{\large (\phi,r)}\!\equiv 1,\,$$ contra minimality of $$\,r = {\rm ord}\, a.\,$$ Indeed $$\,a^{(\phi,r)} = a^{i\phi+jr}\equiv (\color{#c00}{a^{\phi}})^i (\color{#c00}{a^r})^j\equiv \color{#c00}1^i \color{#c00}1^j\equiv 1$$.

Or, instead of descending $$\,\phi \to (r,\phi) < r\,$$ using $$\rm gcd\,$$ (= iterated $$\!\color{#0a0}{\bmod}\!$$ descents) we can instead descend $$\,\phi\to \phi\bmod r < r\,$$ by a single $$\!\color{#0a0}{\bmod}\!$$ step, i.e. $$\,\color{#c00}{a^{\phi}\equiv 1\equiv a^r}$$ $$\Rightarrow a^{\large \phi\ {\rm mod}\ r}\equiv 1,\,$$ since $$\,\phi \bmod r = \phi -j\!\:r,\,$$ for some $$\,j\in\Bbb Z\,$$ so, as above, $$\,a^{\phi-j\:\!r} \equiv \color{#c00}{a^{\phi}}(\color{#c00}{a^r})^{-j}\equiv \color{#c00}1(\color{#c00}1)^{-j}\equiv 1$$.

Remark  The key idea that lies at the heart of all of proofs like the above is essentially as follows: the set $$E$$ of exponents $$\,n\,$$ with $$\,a^n\equiv 1\,$$ is closed under subtraction, so also under mod (= iterated subtractions), so also under gcd (= iterated mods), thus the least positive element of $$E$$ divides all elements of $$E.\,$$ Said in ring (or group) language, $$E$$ is an ideal (or subgroup) of $$\,\Bbb Z\,$$ which is principal (generated by any $$\rm\color{#0a0}{least\ magnitude}$$ element $$\,\color{#0a0}{0\neq r}\in E$$), since $$\,\Bbb Z\,$$ is Euclidean $$\Rightarrow$$ PID. From this viewpoint, the above proof is a special case of the proof that all ideals of $$\,\Bbb Z\,$$ are principal, using descent by the (Euclidean) Division Algorithm (or the equivalent group form that subgroups of $$\Bbb Z$$ are cyclic, generated by a least positive element or $$\,0).\,$$ For, as above if $$\,\phi\in E\,$$ and $$\,r\nmid \phi\,$$ then dividing $$\,\phi \div r\,$$ yields remainder $$\,\bar r := \phi\bmod r = \phi - q\:\!r\in E\,$$ and $$\,0 < \bar r < r,\,$$ contra $${\color{#0a0}{{\rm minimality\ of\ } r}}.$$

This structural result (principality or cyclicity) is at the heart of many basic results in algebra and number theory, not only the above order divisibility property, but also the property that the least denominator divides all denominators, and Euclids Lemma $$\,(a,b)=1,\ a\mid bc\Rightarrow a\mid c\,$$ (which is equivalent to uniqueness of prime factorizations), etc, cf. this answer.

For reasons that will soon become clear, I would prefer to use a letter other than $f$. So let $e$ be the smallest positive be the smallest positive integer such that $a^e\equiv 1\pmod{n}$.

We show that $e$ divides $\varphi(n)$.

By the Division "Algorithm," there exist integers $q$ and $r$, with $0\le r\lt e$, such that $$\varphi(n)=eq+r.$$ It follows that $$a^{\varphi(n)}=(a^e)^q a^r.$$ Since $a^{\varphi(n)}\equiv 1\pmod{n}$ and $a^e\equiv 1\pmod{n}$, it follows that $a^r\equiv 1\pmod{n}$.

Since $0\le r\lt e$, this contradicts the definition of $e$ unless $r=0$.

• This is the alternative method mentioned in the remark in my answer, namely descending from $\,\phi,e\in S\$ to $\ \phi\ {\rm mod}\ e\,\in S\,$ (vs. $\,\gcd(\phi,e)\in S),\,$ where $\,S\,$ is the set (= ideal) of $\,n\,$ with $\,a^n\equiv 1.\ \$ Mar 20 '14 at 4:21
• Yes, your solutions will give a student an opportunity to deepen her insight. Mar 20 '14 at 4:33

It's well known and straight forward to prove that in a group, $$g^n=e\implies |g|\mid n$$.

Now all that is left is to notice that, by Euler's theorem, in $$\mathbb Z_n^×$$ we have that $$a^{\phi (n)}\equiv 1$$.

Since $$1\in\mathbb Z_n^×$$ is the identity element, and the least positive integer $$r$$ such that $$a^r=1$$ describes the order of $$a$$, we are done.

Another way to say it: since $$|\mathbb Z_n^×|=\phi (n)$$, this is just Lagrange's theorem.