# Find the greatest common divisor of $2^m+1$ and $2^n+1$ that $m,n$ are positive integers.

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

• I don't think the answer can be written as a closed form in terms of $m,n$ – Peter Foreman Aug 25 '19 at 10:38
• It is a factor of $2^{2n}-1$. I don't know if that helps. – Empy2 Aug 25 '19 at 10:58
• 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 – Borna Ahmadzade Aug 25 '19 at 13:05
• 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. – Ingix Aug 25 '19 at 13:06
• 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. – Peter Aug 26 '19 at 7:33

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.

• 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. – Isaac YIU Math Studio Aug 26 '19 at 10:44
• 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$ – Empy2 Aug 26 '19 at 10:59
• I make an edit of my post and I found that it may be 1 if m and n contain different powers of 2 – Isaac YIU Math Studio Aug 26 '19 at 12:39
• @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! – Ingix Aug 27 '19 at 9:03

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

• There are a lot of small mistakes in this proof but it doesn't affect the result. Please correct it – Isaac YIU Math Studio Aug 26 '19 at 16:31
• @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. – W-t-P Aug 26 '19 at 19:00
• @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)$. – Ingix Aug 26 '19 at 22:02