number theory - 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}$.