17
$\begingroup$

Somewhere on Stack Exchange I saw the equation

$$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1.$$

I had never seen this before, so I started trying to prove it. Without success...

Can anyone explain me (so actually prove) why this equation is true?

And can we say the same when replacing the '$2$' by any integer number '$a$'?

$\endgroup$
  • 3
    $\begingroup$ Let $m\lt n$. We have $2^n-1=2^{n-m}(2^m-1)+(2^{n-m}-1)$. So our $\gcd$ is $\gcd(2^{n-m}-1, 2^m-1)$. Note how this mirrors the Euclidean Algorithm, subtraction version. $\endgroup$ – André Nicolas Oct 30 '12 at 16:53
  • 1
    $\begingroup$ Related: math.stackexchange.com/questions/7473 $\endgroup$ – rabota Feb 20 '15 at 9:06
18
$\begingroup$

In general, if $p=\gcd(m,n)$ then $p=mx+ny$ for some integers $x,y$.

Now, if $d = \gcd(2^m-1,2^n-1)$ then $2^m \equiv 1 \pmod d$ and $2^n \equiv 1\pmod d$ so $$2^p = 2^{mx+ny} = (2^m)^x(2^n)^y \equiv 1 \pmod d$$

So $d\mid 2^p-1$.

On the other hand, if $p\mid m$ then $2^p-1\mid 2^m-1$ so $2^p-1$ is a common factor.

And yes, you can replace $2$ with any $a$.

$\endgroup$
  • $\begingroup$ Thanks, this explains it. It's of course the first part of the proof that was the problem: proving that $d|2^p-1$. $\endgroup$ – rabota Oct 30 '12 at 16:29
  • $\begingroup$ To anyone who doesn't know about why if $p \mid m, 2^p-1 \mid 2^m-1$. $\endgroup$ – Ning Wang Mar 18 '18 at 10:02
2
$\begingroup$

Suppose $x$, $m$ and $n$ are positive integers with $m$ and $n$ coprime. First let us show that $$r = 1 + x + {x^2} + \ldots + {x^{m - 1}}$$ and $$s = 1 + x + {x^2} + \ldots + {x^{n - 1}}$$ are relatively prime. If $d$ is a common divisor of $r$ and $s$, then $d$ is relatively prime to $x$ because $r$ and $s$ are one more than a multiple of $x$. Let $m$ be greater than $n$ (or vice versa) and consider $$r - s = {x^n} + {x^{n - 1}} + \ldots + {x^{m - 2}} + {x^{m - 1}} = {x^n}(1 + x + \ldots + {x^{m - n - 1}})$$ and notice that $d$ divides $r - s$ and so must be a divisor of $1 + x + \ldots + {x^{m - n - 1}}$. Observe that $m - n$ is relatively prime to both $m$ and $n$, so we can likewise use geometric sums which eventually becomes shorter and shorter until we conclude that $d$ must divide 1 i.e. $d = 1$. Now if we let $$d' = \gcd (m',n')$$ with $m' = md'$ and $n' = nd'$, then $m$ and $n$ are coprime and $${2^{m'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(m - 1)d'}})$$ $${2^{n'}} - 1 = ({2^{d'}} - 1)(1 + {2^{d'}} + {2^{2d'}} + \cdots + {2^{(n - 1)d'}})$$ which are geometric sums with $x = {2^{d'}}$ and we showed that $\gcd (r,s) = 1$. This completes the proof.

$\endgroup$
  • $\begingroup$ "..., so we can likewise use geometric sum which eventually becomes shorter and shorter until we conclude that d must divide 1...". You may mean this: $d|\frac{x^{m-n}-1}{x-1}$. Let $a=m-n$, then we have $d|1+x+...+x^a$ and $d|1+x+...+x^n$, so we can repeat this over and over, letting $b=|n-a|$, ... Right? (Nice alternative solution, but I must confess I prefer Thomas' proof. Anyway, +1) $\endgroup$ – rabota Oct 30 '12 at 16:39
2
$\begingroup$

Hint $\rm\bmod d\!:\ a^{\large m}\!\equiv 1\equiv a^{\large n}\!\iff order(a)\mid m,n\iff order(a)\mid(m,n)\iff a^{\large (m,n)}\!\equiv 1$

Therefore $\rm\ \ d\mid a^{\large m}\!-1,\,a^{\large n}\!-1$ $\iff$ $\rm\:d\mid a^{\large (m,n)}\!-1,\ \,$ hence $\rm\,\ \ (a^{\large m}\!-1,\,a^{\large n}\!-1)\, =\, a^{\large (m,n)}-1$

$\endgroup$
1
$\begingroup$

Yes, you can say the same when replacing $2$ with an integer $a \geqslant 2$.

Lemma. Suppose that $a \geqslant 2$, $m, n \in \mathbb{N}$ and $\gcd(m, n)=1$. Then $\gcd(a^m-1, a^n-1)=a-1$.

Proof. It is obvious that $(a-1) | \gcd(a^m-1, a^n-1)$. So, we only need to prove that $\gcd(a^m-1, a^n-1) | (a-1)$.

It is well known that if $\gcd(m, n)=1$, then there exist $k, l \in \mathbb{N}$ such that $mk-nl=1$. If is obvious that $(a^n-1)|(a^{nl}-1)$, therefore $$ \gcd(a^m-1, a^n-1) | (a^{nl}-1), $$ and for the same reason $$ \gcd(a^m-1, a^n-1) | (a^{mk}-1). $$

Now we just observe that $$ (a^{mk}-1)-a\cdot(a^{nl}-1) = (a^{nl+1}-1)-(a^{nl+1}-a) = a - 1, $$ therefore $$ \gcd(a^m-1, a^n-1) | (a-1), $$ QED.

Now we can prove the main statement: for $b \geqslant 2$ we have: $$ \gcd(b^m-1, b^n-1) = b^{\gcd(m,n)}-1. $$ Proof. Set $a = b^{\gcd(m, n)}$, $m'=m/\gcd(m,n)$ and $n'=n/\gcd(m,n)$. Clearly, $\gcd(m',n')=1$, and by the lemma we have $$ \gcd(a^{m'}-1,a^{n'}-1) = a-1, $$ which is exactly what we need, QED.

$\endgroup$
0
$\begingroup$

let (m,n)=p, then p|m, and p|n, then $m=m_1p$, $n=n_1p$, $(m_1,n_1)=1$, then $(2^{m_1p}-1,2^{n_1p}-1)=((2^{p})^{m_1}-1,(2^{p})^{n_1}-1)=((2^{p}-1)(.....),(2^{p}-1)(.....))=(2^{p}-1)$

$\endgroup$
  • $\begingroup$ I don't understand the last step. Why can't $(...)$ and $(...)$ have a common divisor? (I do know what the dots mean) $\endgroup$ – rabota Oct 30 '12 at 16:12
  • $\begingroup$ The dots are an unspecified polynomial, which is the remainder after factorising out $2^p-1$. They cannot have a common divisorsince otherwise $(m_1, n_1) \neq 0$ (i.e. we could factorise the power of 2 again). $\endgroup$ – Simon Hayward Oct 30 '12 at 16:15
  • $\begingroup$ So it is a polynomial of the form $2^{m_1}+(\text{lower order terms})$ $\endgroup$ – Simon Hayward Oct 30 '12 at 16:21
  • 1
    $\begingroup$ You've only shown that $2^p-1$ is a common factor, not the greatest common factor. $\endgroup$ – Thomas Andrews Oct 30 '12 at 16:22
  • 1
    $\begingroup$ How do you know that there are no other common factors? You've just asserted without proof that the terms in the ellispes ($\dots$) have no common factor. $\endgroup$ – Thomas Andrews Oct 30 '12 at 17:59

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.