# 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... – Thomas Andrews Mar 20 '14 at 3:39

Hint $\$ Generally, by Bezout $\, a^{\large r}\equiv 1\equiv a^{\large k}\,\Rightarrow\,a^{\large (r,k)}\equiv 1\,$ since $\,(r,k) = ir\!+\!jk,\,\ i,j\in\Bbb Z.\,$ Hence, with $\,\ k= \phi,\$ if $\,\ r\nmid \phi\,\$ then $\ (r,\phi) < r\$ and $\,\ a^{\large (r,\phi)}\equiv 1,\,$ contra minimality of $\,r = {\rm ord}\, a.$

Remark $\$ Alternatively one could descend using $\,a^{\large \phi\ {\rm mod}\ r}\equiv 1.\$ The key idea is that the set of exponents $\,n\,$ such that $\,a^n\equiv 1\,$ is closed under subtraction, so also under mod, so also under gcd, so the least positive element divides every element. Said in ring language, the set forms an ideal, which is principal since $\,\Bbb Z\,$ is Euclidean $\Rightarrow$ PID. From that viewpoint, the above proof is just a special case of the proof that every ideal of $\,\Bbb Z\,$ is principal, by descent using the Division Algorithm.

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.\ \$ – Bill Dubuque Mar 20 '14 at 4:21
• Yes, your solutions will give a student an opportunity to deepen her insight. – André Nicolas Mar 20 '14 at 4:33