0
$\begingroup$

The question is as follows:

Let $a, b, c$ be three positive integers. Prove that $\gcd{(a^b-1,a^c-1)}=a^{\gcd{(b, c)}}-1$.

This is a homework assignment. I've tried using Bezout's theorem. But, to no avail. Also, it's easy to show that the R.H.S. divides the L.H.S., but I can't show the converse. Hints are welcome.

$\endgroup$
1
$\begingroup$

To avoid any discussion about the meaning of $\gcd (0,0),$ assume $a>1.$ Let $b=b'x$ and $c=c'x$ where $x=\gcd (b,c).$ So $b'$ and $c'$ are co-prime positive integers. Let $d=a^x.$ Now $d-1$ divides both $d^{b'}-1$ and $d^{c'}-1,$ so $$\bullet \quad \gcd (a^b-1,a^c-1)=\gcd (d^{b'}-1, d^{c'}-1)\geq d-1=a^x-1=a^{\gcd (b,c)}-1.$$ On the other hand, since $\gcd (b',c')=1$, take integers $x, y$ with $b'x+c'y=1.$ For brevity let $z=\gcd (d^{b'}-1,d^{c'}-1).$ We have $$d^{b'}\equiv d^{c'}\equiv 1 \pmod z.$$ Therefore $$d-1\equiv d^{b'x+c'y}-1\equiv (d^{b'})^x(d^{c'})^y-1\equiv 1^x1^y-1\equiv 0\pmod z.$$ That is, $z|(d-1).$ So $z\leq d-1,$ and $$\bullet \quad \gcd (a^b-1,a^c-1)=z\leq d-1=a^{\gcd (b,c)}-1.$$

$\endgroup$
  • $\begingroup$ Like this solution $\endgroup$ – S. Y Sep 21 '16 at 5:04
1
$\begingroup$

Show the L.H.S. is a factor of $a^{b-c}-1$, then take another look at Euclid's Algorithm.

$\endgroup$

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.