number theory - Problem in proof of: Show the order $d$ of $a$ modulo $m$ exists and $dmidphi(m)$

Theorem: Let $m\in\mathbb{N}$ and $a\in\mathbb{Z}$ satisfy $(a,m)=1$. Then the order $d$ of $a$ modulo $m$ exists, and $d\mid\phi(m)$.

Proof: By Euler's theorem, one has $a^{\phi(m)}\equiv 1\pmod{m}$, and so the order of $a$ modulo $m$ clearly exists.

Suppose then that $d$ is the order of $a$ modulo $m$, and further that $a^k\equiv 1\pmod{m}$.

Then it follows from the division algorithm that there exists integers $q$ and $r$ with $k=dq+r$ and $0\leq r

But then we obtain $a^k=(a^d)^qa^r\equiv a^r\equiv 1\pmod{m}$,

therefore $r=0$.

Thus we have $d\mid k$ and in particular $d\mid\phi(m)$

Point of contention: I understand that $a^k=(a^d)^qa^r$ and that $a^d\equiv 1\pmod{m}$ since it is the order of $a$ modulo $m$, therefore $(a^d)^q\equiv 1\pmod{m}$.

But I dont understand how $a^r\equiv 1\pmod{m}$

I understand the rest of the argument after this.

Answer

Since $(a^d)^q \equiv 1 \pmod{m}$ it follows that $a^r \equiv a^k \equiv 1 \pmod{m}$, where the second $\equiv$ is by hypothesis.