Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$

Question

Let $a$ and $b$ be two odd positive integers. Prove that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1$.

I tried rewriting it to get $\gcd(2^{2k+1}+1,2^{\gcd(2k+1,2n+1)}-1)$, but I didn't see how this helps.

Answer 1

Consider $r=\gcd(a,b)$ and write $a=rs$. Then you are reduced to finding $$ \gcd(2^{rs}+1,2^r-1)=\gcd(2^{rs}+2^r,2^r-1) $$ Since $2^r-1$ is odd and $2^{rs}+2^r=2^r(2^{rs-r}+1)$, we have $$ \gcd(2^{rs}+2^r,2^r-1)=\gcd(2^{r(s-1)}+1,2^r-1) $$ If $s=1$, we are done. Otherwise we apply the same argument to conclude $$ \gcd(2^{r(s-1)}+1,2^r-1)=\gcd(2^{r(s-2)}+1,2^r-1) $$ and go on.

Turn it into a proper proof by induction.

Answer 2

If $p$ is a prime dividing $2^{\gcd(a,b)}-1,$ then $2^{\gcd(a,b)}\equiv1\pmod p.$ Since $\gcd(a,b)\mid a,$ we also have $2^a+1\equiv(2^{gcd(a,b)})^{a/\gcd(a,b)}+1\equiv1+1=2\pmod p.$ Since $2^{\gcd(a,b)}+1$ is odd, $p$ is odd too, thus $p$ does not divide $2^a+1.$ This shows that $\gcd(2^{a}+1,2^{\gcd(a,b)}-1)=1.$

Hope this helps.

Answer 3

We $\gcd(a, b)$ is a divisor of $a$, so we have $a=m\gcd(a, b)$. Therefore, we can rephrase the question as: $$\gcd\left(2^{m\gcd(a, b)}+1, 2^{\gcd(a, b)}-1\right)$$

Now, since $1$ is a zero for $x^m-1$, so we know that: $$(x-1) \mid (x^m-1)$$ Substitute $x=2^{\gcd(a, b)}$: $$(2^{\gcd(a, b)}-1) \mid (2^{m\gcd(a, b)}-1)$$

Subtract the latter part of this statement from the former part of the $\gcd$: $$\gcd(2, 2^{\gcd(a, b)})$$ The latter part is clearly odd, so the $\gcd$ is $1$.

Answer 4

Any divisor of $2^{\gcd(a,b)}-1$ is a divisor of $2^a-1$ since $a$ is a multiple of $\gcd(a,b)$ by definition.

Hence $\;\gcd(2^a+1, 2^{\gcd(a,b)}-1)=\gcd(2^a+1, 2^a-1) =1$.

Answer 5

Let $\ \ d\, =\, (\color{#0a0}{2^A+\ 1},\,\ \ \color{#c00}{2^C\:-\:1}).\, $ $\ A\, =\, C\,N\,\ $ by $\,\ C = (A,B)\mid A,\ $ so

${\rm mod}\ d\!:\: \color{#0a0}{{-}1\equiv}{\color{#0a0}{ 2^A}\!\equiv (\color{#c00}{2^C})^N}\!\equiv\! \color{#c00}{1}^N\!\equiv 1\:\Rightarrow\:d\mid 2\:\Rightarrow\: d=1\:$ by $\,d\,$ odd.