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

Below are sketches of $3$ proofs. The latter $2$ essentially repeat inline variations on the descent-based proof of the order reduction lemma used in the first proof.

Hint $ $ by Euler's $\phi$ Theorem & mod order reduction $\,{\rm ord}_n a = r,\ a^{\phi(n)}\equiv 1\pmod{\!n}\Rightarrow r\mid \phi(n)$

Or $\ \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 in prior proof $\,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.