2
$\begingroup$

Prove that if $r$ is a primitive root modulo $m$, and $(a, m) = (b, m) = 1$, then $r^a \equiv r^b \pmod{m}$ implies $a \equiv b \pmod{φ(m)}$.

Any hints will be appreciated. Thanks so much.

$\endgroup$
  • $\begingroup$ Note that the hypotheses that $(a,m)=(b,m)=1$ are completely unnecessary. (Indeed, it never makes sense to consider exponents modulo the modulus.) $\endgroup$ – Greg Martin Nov 1 '16 at 6:01
0
$\begingroup$

As $r$ is a primitive root modulo $m$, then $r^{\varphi(m)}\equiv 1 \pmod{m}$, also $\varphi(m)$ is the less natural number $k$ such that $r^k\equiv 1 \pmod{m}$. This implies that if $r^s\equiv 1 \pmod{m}$, then $\varphi(m)|s$.

By other hand, $r^a\equiv r^b \pmod{m}$. WLOG $a\ge b$ then: $$r^a-r^b\equiv 0 \pmod{m}$$ $$r^b[r^{a-b}-1]\equiv 0 \pmod{m}$$ $$r^{a-b}-1\equiv 0 \pmod{m} \to r^{a-b}\equiv 1 \pmod{m}$$

We can conclude $\varphi(m)|a-b$ this means $a\equiv b \pmod{\varphi(m)}$.

$\endgroup$
0
$\begingroup$

Suppose that $r^{a} - r^{b}$ is a multiple of $m$. This is equivalent to $r^{a-b} - 1$ being a multiple of $m$, since $r$ is co-prime to $m$, so we can remove the $r^b$ out.

Now, by Euler's theorem, $r^{\phi(m)} \equiv 1 \mod m$. However, there is a stronger fact: $\phi(m)$ is in fact the order of $r \mod m$, given that $r$ is a primitive root. Hence, $\phi(m) | (a-b)$ because if it doesn't, then the remainder $d$ of the division would be smaller than $\phi(m)$ and satisfy $r^{d} \equiv 1 \mod m$, and this would contradict the definition of order.

$\endgroup$
  • $\begingroup$ A quibble: the definition of order only says that $\phi(m) \le (a-b)$. The fact that $\phi(m)$ actually divides $a-b$ is a theorem/lemma about the order, not part of the definition. $\endgroup$ – Greg Martin Nov 1 '16 at 6:02
  • $\begingroup$ @GregMartin Thank you for the point out. It is a theorem, a non-trivial fact for sure. I will edit my post. $\endgroup$ – астон вілла олоф мэллбэрг Nov 1 '16 at 6:05

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.