# Show that $a^i \equiv a^j \pmod{m}$ iff $i \equiv j \pmod{d}$

I've been given the following problem to solve:

Let $a$ be an integer and $m$ and $d$ natural numbers. Assume $a^d \equiv 1 \pmod{m}$, and that $d$ is the smallest possible number for which this holds. In that case, show that $a^i \equiv a^j \pmod{m}$ if and only if $i \equiv j \pmod{d}$ for all natural numbers $i$ and $j$.

If we assume that $a^d \equiv 1 \pmod{m}$ and $a^i \equiv a^j \pmod{m}$, then we can write \begin{align} mx = (a^d - 1) \\ my = (a^i - a^j) \end{align} for some $x$ and $y$. But I don't seem to get anywhere by comparing these expressions for $m$.
If we assume $i \equiv j \pmod{d}$, then we may write \begin{align} dz = (i-j) \end{align} for some $z$. I can use this to make an expression for $i = dz +j$ and insert into $a^i$, but I don't seem to get anywhere there either.

I'm really confused by this problem. Any help is much appreciated.

I show only the non-trivial part of iff. From the definition of $d$ it follows that $a$ is invertible $\bmod m,\;$ so $a^{-j}\pmod m$ is defined. Assume without loss of generality that $i>j;\;$ then $$a^i=a^{j} \pmod m$$ implies $$1\equiv a^ia^{-j}\equiv a^{i-j}\pmod m$$ Therefore from the minimal property of $d\;$ it follows that $i-j$ is a multiple of $d,\;$ i.e. $i\equiv j \pmod d$
• What do you mean by $a^{-j} \pmod{m}$ is defined? – SBS Oct 12 '16 at 10:34
• Defined means that you can multiply the congruence by $a^{-j}$. If $a^d\equiv 1$ then $a$ is invertible and you have $a^{-j}\equiv (a^{-1})^j \pmod m.$ The step $$a^i \equiv a^{j} \pmod m \Longrightarrow 1\equiv a^ia^{-j}\equiv a^{i-j}\pmod m$$ is generally not valid if $a$ is not invertible. E.g. $3^6 \equiv 3^2 \equiv 9 \pmod {15}$ but $3^{6-2}=3^4 \equiv 6 \pmod {15}$ – gammatester Oct 12 '16 at 10:53
• So you mean that because $a$ is invertible modulo $m$, $a^{-j}$ must exist? And you use that to show that $a^{i-j}$ must be congruent to 1 modulo $m$? – SBS Oct 12 '16 at 11:08