2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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)$$ $\endgroup$ – Noble Mushtak Jun 24 '16 at 12:57
  • $\begingroup$ Which makes it trivial :) $\endgroup$ – almagest Jun 24 '16 at 12:59
  • $\begingroup$ @Puzzled417 $\gcd(a, b)$ must be a divisor of $a$, so $a=m\gcd(a,b)$ for some $m \in \Bbb{Z}$. $\endgroup$ – Noble Mushtak Jun 24 '16 at 13:01
  • 1
    $\begingroup$ @NobleMushtak m should be odd $\endgroup$ – miracle173 Jun 24 '16 at 13:03
  • 1
    $\begingroup$ @NobleMushta: maybe not relevant to your answer but relevant to the statement "we can rephrase the question as ..." $\endgroup$ – miracle173 Jun 24 '16 at 13:14
1
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ $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. $\endgroup$ – almagest Jun 24 '16 at 13:11
  • $\begingroup$ @almagest I've added your top to the beginning of my answer. $\endgroup$ – Noble Mushtak Jun 24 '16 at 13:18
  • $\begingroup$ @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). $\endgroup$ – Bill Dubuque Jun 24 '16 at 15:59
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – almagest Jun 24 '16 at 16:05
  • $\begingroup$ @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. $\endgroup$ – Bill Dubuque Jun 24 '16 at 18:03

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.