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

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.

• We are talking about any two positive odd integers here, so $b$ can be anything despite what $a$ is, so $\gcd(a, b)$ can be any divisor of $a$. Since $a$ is odd, this divisor must also be odd. Therefore, we can rephrase the question as: $$\gcd\left(2^{m(2k+1)}+1, 2^{2k+1}-1\right)$$ – Noble Mushtak Jun 24 '16 at 12:57
• Which makes it trivial :) – almagest Jun 24 '16 at 12:59
• @Puzzled417 $\gcd(a, b)$ must be a divisor of $a$, so $a=m\gcd(a,b)$ for some $m \in \Bbb{Z}$. – Noble Mushtak Jun 24 '16 at 13:01
• @NobleMushtak m should be odd – miracle173 Jun 24 '16 at 13:03
• @NobleMushta: maybe not relevant to your answer but relevant to the statement "we can rephrase the question as ..." – miracle173 Jun 24 '16 at 13:14

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.

• This holds for all $a,b$ and not necessarily odd? – Puzzled417 Jun 24 '16 at 13:19
• @Puzzled417 I'm also not using the fact that $a,b$ are odd in my answer anymore. – Noble Mushtak Jun 24 '16 at 13:23
• Yes, this holds even when $a,b$ are not necessarily odd. – awllower Jun 24 '16 at 13:24

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$.

• $2^{2k+1}-1$ is a factor of $2^{m(2k+1)}-1$. So if $p$ divides $\gcd(2^{m(2k+1)}+1,2^{2k+1}-1)$ it must also divide 2. – almagest Jun 24 '16 at 13:11
• @almagest I've added your top to the beginning of my answer. – Noble Mushtak Jun 24 '16 at 13:18
• @almagest Note that it becomes more intuitive arithmetically by using congruences - see my answer. This eliminates relations (divisibility) by translating into equivalent arithmetic operations (generally we have better intuition on operations than relations). – Bill Dubuque Jun 24 '16 at 15:59

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.

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$.

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.

• Yes, I just think the result is completely obvious once you grasp the idea of comparing $2^a-1$ and $2^c-1$. But that leap cannot be obvious to everyone or the OP would not have written the question! – almagest Jun 24 '16 at 16:05
• @almagest It's not clear what you mean by "compare". But the above proof is a congruence analog of the other divisibility proofs, and the congruence language makes it more obvious, i.e. you need only recognize that $\,2^{CN}\!\equiv (\color{#c00}{2^C})^N\,$ vs. $\,2^C-1\mid 2^{CN}-1.\,$ The former is obvious even if one does not know the latter. This is but one simple example of how congruences simplify divisibility relations. – Bill Dubuque Jun 24 '16 at 18:03