8
$\begingroup$

I am confused of a question that needs to know the greatest common divisor of $2^m+1$ and $2^n+1$ ($m,n$ are positive integers), but I don't really know. I am pretty sure that the greatest common divisor of $2^m-1$ and $2^n-1$ ($m,n$ are positive integers) is $2^{\gcd\left(m,n\right)}-1$, even I can prove it by the Euclidean algorithm. However, it is hard to use it in this problem, so I want you guys to help me. Thanks!

P.S.

I created an excel and I observed the answer (maybe?) from it, but I can't prove or disprove it. Here is my conclusion from the excel: $$\gcd\left(2^m+1,2^n+1\right)=\begin{cases} 2^{\gcd\left(m,n\right)}+1 \\ 1 \end{cases}\begin{matrix} \text{when }m,n\text{ contain the exact same power of }2 \\ \text{otherwise} \end{matrix}$$ Hope it will help me and you guys solving this quesion :D

The link of The excel

$\endgroup$
  • 1
    $\begingroup$ I don't think the answer can be written as a closed form in terms of $m,n$ $\endgroup$ – Peter Foreman Aug 25 at 10:38
  • $\begingroup$ It is a factor of $2^{2n}-1$. I don't know if that helps. $\endgroup$ – Empy2 Aug 25 at 10:58
  • $\begingroup$ It would be great if someone could run a program to find the GCD for small values of $n$ and $m$ to see if there’s a pattern. I feel like if there indeed exists a closed-form formula, it could be proven using induction $\endgroup$ – Borna Ahmadzade Aug 25 at 13:05
  • $\begingroup$ From your formulation it is unclear if this is the complete question posed somewhere else, or just a question that "would be nice to know the general answer to" while you solved some related problem. For example, when both $m,n$ are odd, the answer is $2^{\gcd(m,n)}+1$. So any additional conditions you might have on $m$ and $n$ would be nice to know. $\endgroup$ – Ingix Aug 25 at 13:06
  • 1
    $\begingroup$ What we can say that a common divisor must divide $2^{2m}-1$ and $2^{2n}-1$, hence must divide $2^{\gcd(2m,2n)}-1$ , hence the greatest common divisor divides $2^{\gcd(2m,2n)}-1$, but I do not think that we can achieve a better result in general. $\endgroup$ – Peter Aug 26 at 7:33
2
$\begingroup$

This started as a partial solution, trying to bundle up what's been said in the comments and a bit more. After some more comments (esp. from Empy2) it is now a complete solution.

Proposition 1 gives an upper bound for the gcd. Proposition 2 then shows that this upper bound is actually assumed under certain conditions on $m,n$. Proposition 3 then shows that if those conditions are not fullfilled, the gcd is $1$.

Proposition 1:

$$\gcd(2^{m}+1,2^{n}+1) | 2^{\gcd(m,n)}+1.$$

Proof:

Let $d$ be a common divisior of $2^m+1$ and $2^n+1$.

We have $2^m+1|2^{2m}-1$ and $2^n+1|2^{2n}-1$, so it follows that $d|\gcd(2^{2m}-1,2^{2n}-1)$ and we know that $$\gcd(2^{2m}-1,2^{2n}-1) = 2^{\gcd(2m,2n)}-1 = 2^{2\gcd(m,n)}-1 = (2^{\gcd(m,n)}-1)(2^{\gcd(m,n)}+1),$$

so

$$d|(2^{\gcd(m,n)}-1)(2^{\gcd(m,n)}+1). \tag{1} \label{eq1}$$

Let $p$ be a prime divisor of $2^{\gcd(m,n)}-1$. That means

$$2^{\gcd(m,n)} \equiv 1 \pmod p$$

and if we raise each side to the $\frac{m}{\gcd(m,n)}$-th power, we obtain

$$2^m \equiv 1 \pmod p \Longrightarrow 2^m+1 \equiv 2 \pmod p$$

Because $m > 0$, $2^m+1$ is odd, so $p \neq 2$ and hence $2^m+1 \neq 0 \pmod p$.

That means no prime divisor of $2^{\gcd(m,n)}-1$ can be a divisor of $2^m+1$, so $d$ and $2^{\gcd(m,n)}-1$ are coprime and we get from \eqref{eq1} that

$$d|2^{\gcd(m,n)}+1$$

and Proposition 1 follows.


Proposition 2: When $m$ and $n$ contain the exact same power of $2$:

$$m=2^km', n=2^kn';\quad m'\equiv n'\equiv1 \pmod 2,$$

then

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

Proof:

In this case we also set $m'=\gcd(m',n')m''$ and $n'=\gcd(m',n')n''$ and find

$$2^m+1=2^{2^km''\gcd(m',n')}+1=\left(2^{2^k\gcd(m',n')}\right)^{m''}+1$$

and the equivalent for $n$:

$$2^n+1=2^{2^kn''\gcd(m',n')}+1=\left(2^{2^k\gcd(m',n')}\right)^{n''}+1.$$

Since $m''$ and $n''$ are odd, that means that $2^{2^k\gcd(m',n')} +1$ divides both terms (as per $(a+b)|(a^r+b^r)$ for any odd $r$).

Since $2^k\gcd(m',n') = \gcd(m,n)$, this proves Proposition 2.


The hard case seems to be when $m$ and $n$ contain different powers of $2$. I see no good way to attack that question in a general way, but maybe others do.

ADDED: It turns out that the comment by Empy2 below actually solves that problem, it just took me a while to realize that.

Proposition 3:

Let $m=\gcd(m,n)m'$ and $n=\gcd(m,n)n'$. If $m'$ is even and $n'$ is odd, then

$$\gcd(2^m+1,2^n+1)=1.$$

Proof: The conditions on $m'$ and $n'$ are equivalent to $m$ and $n$ containing different powers of $2$, where I assumed w.l.o.g. that $m$ was the one containing the higher power of $2$.

We have ${\rm{lcm}}(m,n)=\gcd(m,n)m'n'$ so

$$2^{{\rm lcm}(m,n)}+1=2^{\gcd(m,n)m'n'}+1 =\left(2^{\gcd(m,n)m'}\right)^{n'}+1 = \left(2^{m}\right)^{n'}+1.$$

Since $n'$ is odd, we find that

$$2^m+1|\left(2^{m}\right)^{n'}+1 = 2^{{\rm lcm}(m,n)}+1.$$

Doing the same for $n$ we get

$$2^{{\rm lcm}(m,n)}+1=2^{\gcd(m,n)m'n'}+1 =\left(2^{\gcd(m,n)n'}\right)^{m'}+1 = \left(2^{n}\right)^{m'}+1.$$

We finally have $$2^n+1|(2^n)^2-1|(2^n)^{m'}-1=2^{{\rm lcm}(m,n)}-1,$$ where the second divisibility follows because $m'$ is a multiple of $2$ (it was even).

So, as Empy 2 said, we have

$$2^m+1| 2^{{\rm lcm}(m,n)}+1,$$ $$2^n+1| 2^{{\rm lcm}(m,n)}-1,$$

so any common divisor of $2^m+1$ and $2^n+1$ must be a divisor of $2$. Since $m,n$ were both assumed to be positive, only $1$ can be a such common divisor.


$\endgroup$
  • $\begingroup$ Though it is not finished, it is great to have some process in this question! At least there is one case that can be proven is good for me actually. $\endgroup$ – Isaac YIU Math Studio Aug 26 at 10:44
  • 1
    $\begingroup$ If they have different powers of two, then one is a factor of $2^{lcm}+1$ and the other a factor of $2^{lcm}-1$ $\endgroup$ – Empy2 Aug 26 at 10:59
  • $\begingroup$ I make an edit of my post and I found that it may be 1 if m and n contain different powers of 2 $\endgroup$ – Isaac YIU Math Studio Aug 26 at 12:39
  • $\begingroup$ @Empy2 Thanks for your comment, that solved the remaning part from my approach (which I added in). Also, please look at the solution by W-t-P, who uses a different approach! $\endgroup$ – Ingix Aug 27 at 9:03
3
$\begingroup$

Your conjectured formula is correct; here is the proof.

For integer $m,n\ge 0$, let $d(m,n):=\gcd(2^m+1,2^n+1)$. Assuming for definiteness $m\ge n$, we have \begin{align*} d(m,n) &= \gcd(2^m-2^n,2^n+1) \\ &= \gcd(2^n(2^{m-n}-1),2^n+1) \\ &= \gcd(2^{m-n}-1,2^n+1) \\ &= \gcd(2^{m-n}+2^n,2^n+1). \end{align*} If $m\ge 2n$, then this can be taken a little further, by factoring out $2^n$, to get $$ d(m,n) = \gcd(2^{m-2n}+1,2^n+1); $$ if $m\le 2n$, then factoring out $2^{m-n}$ instead of $2^n$ we get $$ d(m,n) = \gcd(2^{2n-m}+1,2^n+1). $$ In any case, we have the recursive relation $$ d(m,n) = d(|m-2n|,n),\quad m\ge n. \tag{$\ast$} $$

Let $\nu(k)$ denote the $2$-adic valuation of an integer $k\ne 0$; that is, $\nu(k)$ is the largest integer such that $2^{\nu(k)}$ divides $k$. I claim that

(1) If $m>n>0$, then $\max\{|m-2n|,n\}<\max\{m,n\}$;

(2) if $m>0$ or $n>0$, then $\gcd(|m-2n|,n)=\gcd(m,n)$;

(3) if $m\ne 2n$, then $\nu(m)=\nu(n)$ if and only if $\nu(m-2n)=\nu(n)$.

The first two assertions are easy to verify. For the last one, let $k:=\nu(n)$ and $l:=\nu(m)$ and consider two cases:

If $k>l$ then $2^{l+1}\nmid m-2n$ while $2^{l+1}\mid n$, whence $\nu(n)\ne\nu(m-2n)$, as wanted.

If $k<l$ then $2^{k+1}\mid m-2n$ while $2^{k+1}\nmid n$, implying $\nu(n)\ne\nu(m-2n)$ in this case, too.

To complete the proof, we use straightforward induction by $m=\max\{m,n\}$ distinguishing the following cases: $n=0$, $m=n$, $m=2n$, and the "general case" where none of these holds.

$\endgroup$
  • $\begingroup$ There are a lot of small mistakes in this proof but it doesn't affect the result. Please correct it $\endgroup$ – Isaac YIU Math Studio Aug 26 at 16:31
  • $\begingroup$ @IsaacYIUMathStudio: There were a couple of small typos which, hopefully, are now fixed. I have also modified the proof to cover the case where $m$ and $n$ have the same $2$-adic valuation. $\endgroup$ – W-t-P Aug 26 at 19:00
  • 1
    $\begingroup$ @W-t-P Good job: +1. It took me a while to understand that your reduction scheme terminates (produces a trivial identity) either when both arguments are the same or one argument becomes $0$. The former happens for $\nu(m)=\nu(n)$, the latter for $\nu(m)\neq \nu(n)$. $\endgroup$ – Ingix Aug 26 at 22:02

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.