0
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ The problem with that solution is not that $86$ is even, it's that it's not $-1$, but $+1$. $\endgroup$ – Don Thousand Oct 17 at 20:58
  • $\begingroup$ 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) $\endgroup$ – mhmhhmhmhm Oct 17 at 21:05
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

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

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.