# Find gcd($2^{19} + 1$; $2^{86} + 1$)

Find gcd($$2^{19} + 1$$; $$2^{86} + 1$$)

It would be easy to give a formal proof for any gcd($$2^{n} + 1$$; $$2^{m} + 1$$) based on Proving that $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n )} - 1$ if $$m$$, $$n$$ were uneven but the problem is: $$86$$ is an even number. What to do then? Can i solve it without finding an ultimate solution for any n, m? (Like, an easier way for this exact problem)

• The problem with that solution is not that $86$ is even, it's that it's not $-1$, but $+1$. – Don Thousand Oct 17 at 20:58
• Well, i could follow the same logic? The difference would be that $2^m ≡$ -1(mod d) and $2^n ≡$ -1(mod d). But when we try to prove the fact that $2^p + 1 | 2^m + 1$ if $p | m$ we figure out that it is true only when $m$ is uneven and the same for $n$ (because of the abbreviation formula) – mhmhhmhmhm Oct 17 at 21:05

Let $$d$$ be the gcd. Note: $$d\mid 2^{67}(2^{19}+1)-(2^{86}+1)=2^{67}-1\\ d\mid 2^{48}(2^{19}+1)-(2^{67}-1)=2^{48}+1\\ d\mid 2^{29}(2^{19}+1)-(2^{48}+1)=2^{29}-1\\ d\mid 2^{10}(2^{19}+1)-(2^{29}-1)=2^{10}+1\\ d\mid 2^{9}(2^{10}+1)-(2^{19}+1)=2^{9}-1\\ d\mid (2^{10}+1)-2^{1}(2^{9}-1)=3\\ d\in \{1,3\}\\ 2^{86}+1\equiv (-1)^{86}+1\equiv 2 \pmod{3} \Rightarrow 3\not\mid 2^{86}+1$$ Hence, $$\gcd(2^{19}+1,2^{86}+1)=1$$.

So both numbers are odd, so there is no common factor $$2$$.

Any common factor divides the difference $$2^{86}-2^{19}=2^{19}\left(2^{67}-1\right)$$ and hence (by the earlier remark) $$2^{67}-1$$

Now any common factor of $$2^{19}+1$$ and $$2^{67}-1$$ divides their sum and hence $$2^{67}+2^{19}=2^{19}\left(2^{48}+1\right)$$ and hence $$2^{48}+1$$.

Note that this shows you can reduce $$86$$ by $$2\times 19$$.

In fact you can also exploit the fact that $$2^{19}+1$$ is a factor of $$2^{38}-1$$ and $$2^{86}+1$$ is a factor of $$2^{172}-1$$ and you can compute the common factor of these larger numbers with what you already know.

I reckon that is enough of a clue to get you started (there are other things you might notice too).

Note that by FLT, and the fact that $$\mathbb Z/p\mathbb Z$$ is a field, we have that for any odd prime $$p$$ and any $$k\in\mathbb N$$,

$$p\mid2^{\frac{(2k-1)\cdot(p-1)}2}+1$$

So, for both $$19$$ and $$86$$, we are looking for odd primes $$p$$ such that there exists a $$k\in\mathbb N$$ with $$2x=(2k-1)\cdot(p-1)$$($$x$$ is the exponent here).

For $$2x=38$$, $$p-1$$ has to be $$38$$ or $$2$$. However, $$p=39$$ isn't prime, so we are left with $$p=3$$. So, we know that $$3|2^{19}+1$$. In fact, this tells us that $$3$$ is the only prime less than $$\sqrt{2^{19}+1}$$ that is a factor.

This makes the remainder of the question pretty easy. Can you take it from here? Hint: 3 isn't a factor of $$2^{86}+1$$, so there are only two possible answers left.

• What do you mean "x is the exponent here"? i'm only in 10th form so i'm not sure what is it – mhmhhmhmhm Oct 17 at 21:20
• ah got it, sorry, mistranslated – mhmhhmhmhm Oct 17 at 21:21