7
$\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$
8
  • 1
    $\begingroup$ I don't think the answer can be written as a closed form in terms of $m,n$ $\endgroup$ Commented Aug 25, 2019 at 10:38
  • $\begingroup$ It is a factor of $2^{2n}-1$. I don't know if that helps. $\endgroup$
    – Empy2
    Commented Aug 25, 2019 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$
    – user668217
    Commented Aug 25, 2019 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
    Commented Aug 25, 2019 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
    Commented Aug 26, 2019 at 7:33

2 Answers 2

3
$\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$
4
  • $\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$
    – MafPrivate
    Commented Aug 26, 2019 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
    Commented Aug 26, 2019 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$
    – MafPrivate
    Commented Aug 26, 2019 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
    Commented Aug 27, 2019 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$
3
  • $\begingroup$ There are a lot of small mistakes in this proof but it doesn't affect the result. Please correct it $\endgroup$
    – MafPrivate
    Commented Aug 26, 2019 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
    Commented Aug 26, 2019 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
    Commented Aug 26, 2019 at 22:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .