If $a^\phi = 1$ then the order of $a$ divides $\phi$

Solution 1:

Hint: Let $\phi(n)=xq+r$, where $0\le r<x$. Show that $a^r\equiv 1 \pmod{n}$. This contradicts the definition of $x$, unless $r=0$.

Solution 2:

Elaboration yields much conceptual insight by viewing it as a special case of a fundamental result characterizing the period (cycles) of powers in modular arithmetic. Note: below the modulus is fixed and not notated (so $\,\rm n\,$ does not denote the modulus).

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

$$\rm \color{#90f}n>\color{#0a0}m\,\in\,{\cal O}\,\Rightarrow\ \color{#c00}{n\!-\!m}\,\in\,{\cal O}\ \ \ {\rm by}\ \ \ 1\equiv \color{#90f}{a^{\large n}} \equiv a^{\large n-m}\, \color{#0a0}{a^{\large m}} \equiv a^{\large\color{#c00}{n-m}}\, $$

So, by the 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$.

Remark $ $ This immediately yields the following very useful

Corollary $\ $ If $\,\color{#0a0}{a^{\large \ell}\equiv 1}\,$ then $\ \ell\mid n\,\Rightarrow\, a^{\large n}\!\equiv 1,\, $ and conversely if $\,a\,$ has order $\,\ell$

Proof $\ \ (\Rightarrow)\ \ n =\ell k\,\Rightarrow\, a^{\large n}\! \equiv (\color{#0a0}{a^{\large \ell}})^{\large k}\!\equiv \color{#0a0}{\bf 1}^k\equiv 1.\ $ $\,(\Leftarrow)\ $ Follows by the Theorem.

Corollary' $\ \ a\,$ has $\,\color{}{{\rm order}\,\ \ell}$ $\iff \big[ a^{\large n}\! \equiv 1\!\iff\! \ell\mid n\big] $

Proof $\ (\Rightarrow)\,$ By the Corollary. $\ (\Leftarrow)\ $ By the equivalence the least positive $n$ with $\,a^n\equiv 1$ equals the least positive multiple of $\,\ell,\,$ which is $\,\ell$

See here for elaboration on the Theorem, including other proofs. For more on the key innate algebraic structure see this post on order ideals / groups and denominator ideals.