Calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$ [closed]

Question

How to calculate the great common factor between $2^{2n+1}-1$ and $2^{4m+2}+1$, where $n$ and $m$ are positive numbers.

We guess that: the great common factor is $1$.

Answer 1

Suppose that $p$ is a prime number that divides $2^{2n+1}-1$. This means that $2^{2n+1}\equiv 1\pmod{p}$. Consequently, the order of $2$ modulo $p$ must be an odd number dividing $2n+1$.

On the other hand, if $q$ is a prime number that divides $2^{4m+2}+1$, then this means $2^{4m+2}\equiv -1\pmod{q}$. Hence $2^{8m+4}\equiv 1\pmod{q}$. Thus, the order of $2$ modulo $q$ must be of the form $4k$ for some $k\mid (2m+1)$.

Thus, your two numbers cannot share any prime divisors.

Answer 2

In general we have $$\gcd(2^a + 1, 2^b - 1) = \frac{2^{\gcd(2a,b)}-1}{2^{\gcd(a,b)}-1},$$ which is evaluates to $1$ for $a=4m+2$ and $b=2n+1$.