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 Answer 1

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$
5
  • 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$ Feb 23, 2019 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$
    – Mjoseph
    Feb 23, 2019 at 23:10
  • $\begingroup$ and g=bx+cy comes from the fact that g=gcd(b,c) $\endgroup$
    – Mjoseph
    Feb 23, 2019 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$ Feb 23, 2019 at 23:14
  • $\begingroup$ Ah yeah of course, thanking you for pointing out that subtlety. $\endgroup$
    – Mjoseph
    Feb 23, 2019 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.