# Let $a=2^{2^{35}} +1,b=2^{2^{21}} +1$ , then the greatest common divisor of $a$ and $b$ is…?

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.

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

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

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.

• I don't know Euclid ,I am just new with mod can you explain bit more . – Aakash Kumar Jul 31 '16 at 15:42
• @AakashKumar You don't know $\,A \equiv a\pmod b\,\Rightarrow\, (A,b) = (a,b),\,$ the reduction step in the Euclid's gcd algorithm? – Bill Dubuque Jul 31 '16 at 15:45
• No,I don't know this – Aakash Kumar Jul 31 '16 at 15:50
• @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. – Bill Dubuque Jul 31 '16 at 15:59
• I have tried with another approach , now tell me how to do after this . – Aakash Kumar Jul 31 '16 at 16:20