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

Reset to default
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$
    – Bill Dubuque
    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$
    – Bill Dubuque
    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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .