1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ What do you mean by $a^{-j} \pmod{m}$ is defined? $\endgroup$ – SBS Oct 12 '16 at 10:34
  • 1
    $\begingroup$ 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}$ $\endgroup$ – gammatester Oct 12 '16 at 10:53
  • $\begingroup$ 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$? $\endgroup$ – SBS Oct 12 '16 at 11:08
  • $\begingroup$ Yes, that's right. $\endgroup$ – gammatester Oct 12 '16 at 11:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.