0
$\begingroup$

Let $a=2^{2^{35}} +1, b=2^{2^{21}} +1 $. Then $\gcd(a,b)$ is

My little work :

$$a -2 =(2^{2^{22}})^K -1$$ where $K=2^{14}$.

$(2^{2^{22}})^K -1$ is divisible by$(2^{2^{22}}) -1$ $$\implies a-2= (2^{2^{22}} -1)m ,$$ where $m$ is some integer

$$\implies a-2= ((2^{2^{21}})^2 -1 )m $$

$$\implies a-2=((2^{2^{21}}) -1 )bm $$ Help me to figure out things after this.

$\endgroup$
  • $\begingroup$ you defined a twice still ? $\endgroup$ – onurcanbektas Jul 31 '16 at 15:16
  • $\begingroup$ there is still two a $\endgroup$ – onurcanbektas Jul 31 '16 at 15:17
  • $\begingroup$ @Leth Thanks for your careful observation $\endgroup$ – Aakash Kumar Jul 31 '16 at 15:21
3
$\begingroup$

Hint: Let $p\mid b$. What is $a\pmod p$?

$\endgroup$
3
$\begingroup$

Let $\ c = 2^{\large 2^{\Large 21}}$ so $\ 2^{\large 2^{\Large 35}}\! = (2^{\large 2^{\Large 21}})^{\large 2^{\Large 14}}\! =\, c^{{\large 2^{\Large 14}}}\!.\ $ By one step of the Euclidean gcd algorithm

our gcd is $\,(\color{#c00}c^{\large 2^{\Large 14}}\!\!+1,c\!+\!1)\, =\, ((\color{#c00}{-1})^{\large 2^{\large 14}}\!\!+1,c\!+\!1) = (2,c\!+\!1) = 1\,$ by $\,c\!+\!1\,$ odd,

by $\,{\rm mod}\ c\!+\!1\!:\,\ \color{#c00}{c\equiv -1}\,\Rightarrow\, \color{#c00}c^N\equiv (\color{#c00}{-1})^N\ $

Remark $\ $ If Euclid's algorithm or mod are unfamiliar you can instead use divisibility

$$ c\!+\!1\mid c^2\!-\!1\mid c^{2N}\!-1\ \ \ {\rm so} \ \ \ c\!+\!1 \mid (c^{2N}\!-\!1)+2\iff \,c\!+\!1\mid 2$$


Or, using orders, if prime $\,p\mid 2^{\large 2^{\Large 35}}\!\!-1\,$ then $\,{\rm mod}\ p\!:\ 2^{\large 2^{\Large 35}}\!\equiv -1\,$ so squaring shows $\,2\,$ has order $\,2^{\large 36}$ by the Order Test. Hence $\,2^{\large 2^{\Large N}}\!\!\not\equiv 1\,$ for all $\,N < 36,\,$ so $\,p\nmid 2^{\large 2^{\Large N}}\!\!-1.\,$ Generally this argument proves that Fermat numbers with distinct indices are coprime.

$\endgroup$
  • $\begingroup$ I don't know Euclid ,I am just new with mod can you explain bit more . $\endgroup$ – Aakash Kumar Jul 31 '16 at 15:42
  • $\begingroup$ @AakashKumar You don't know $\,A \equiv a\pmod b\,\Rightarrow\, (A,b) = (a,b),\,$ the reduction step in the Euclid's gcd algorithm? $\endgroup$ – Bill Dubuque Jul 31 '16 at 15:45
  • $\begingroup$ No,I don't know this $\endgroup$ – Aakash Kumar Jul 31 '16 at 15:50
  • $\begingroup$ @Aakash You can find a simple proof here. and many other answers. This is a fundamental fact about gcds that you should be sure to know well before attacking gcd problems like this. $\endgroup$ – Bill Dubuque Jul 31 '16 at 15:59
  • $\begingroup$ I have tried with another approach , now tell me how to do after this . $\endgroup$ – Aakash Kumar Jul 31 '16 at 16:20

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.