1
$\begingroup$

Let $b,c,$ and $m$ be positive integers and suppose $a$ is relatively prime to $m$. Furthermore, assume $a^b\equiv a^c\equiv 1\pmod{m}$ and that $g=\gcd(b,c)$.

I know that since $g=\gcd(b,c)$ it follows that $g|b$ and $g|c$. So one could write $b=gx$ and $c=gy$ for some $x,\;y\;\epsilon\;\mathbb Z$. I then have $a^b\equiv a^{gx}\equiv (a^{g})^x\equiv 1\pmod{m}$. I don't quite understand how to prove $a^g\equiv 1\pmod{m}$. I'm wondering if I should be utilizing the fact that the order of $a$ divides any power, $k$, such that $a^k\equiv 1\pmod{m}$. Or if I was on the right track just need to manipulate $b$ and $c$ slightly differently. Any help would be much appreciated.

$\endgroup$
1
$\begingroup$

Hint $\,\ a^{\large b}\equiv 1\equiv a^{\large c}\iff {\rm ord}\,a\mid b,c\iff {\rm ord}\,a\mid \gcd(b,c)\iff a^{\large \gcd(b,c)}\equiv 1$

$\endgroup$
  • 1
    $\begingroup$ See here for the ${\rm ord}$ law used above, and see here for the $\gcd$ law used. We could instead use the Bezout identity for the gcd, but that is less conceptual (and less general). $\endgroup$ – Bill Dubuque Feb 23 at 22:59
  • $\begingroup$ Can I use the fact that g=bx+cy to rewrite this as $a^g \equiv a^{bx+cy}\equiv a^{bx}a^{cy}\equiv (a^b)^x(a^c)^y\equiv 1^x*1^y \equiv 1 \pmod{m}$ $\endgroup$ – joseph Feb 23 at 23:10
  • $\begingroup$ and g=bx+cy comes from the fact that g=gcd(b,c) $\endgroup$ – joseph Feb 23 at 23:11
  • 1
    $\begingroup$ @mjoseph Yes, that's the Bezout-based method that I alluded to above. Note that some exponents are negative so you need to remark that $a$ is invertible because $\ldots$ $\endgroup$ – Bill Dubuque Feb 23 at 23:14
  • $\begingroup$ Ah yeah of course, thanking you for pointing out that subtlety. $\endgroup$ – joseph Feb 23 at 23:17

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.