MHB Finding GCD of $(1+\sqrt2)^{2017}$

[lfdahl]

Find the greatest common divisor of the natural numbers, $a$ and $b$, satisfying:
$$\left(1+\sqrt{2}\right)^{2017} = a + b \sqrt{2}.$$

 

[kaliprasad]

Find the greatest common divisor of the natural numbers, $a$ and $b$, satisfying:
$$\left(1+\sqrt{2}\right)^{2017} = a + b \sqrt{2}.$$

Spoiler

first let us see the relationship of gcd(a,b) and gcd(c,d) where $(c+d\sqrt{2}) = (a+b\sqrt{2})(1+\sqrt{2})$
we get by mutiplication $c= a + 2b , d= a+b)$
so $gcd(c ,d) = gcd(a+2b, a + b) = gcd(a+b,b) = gcd(a,b)$
starting with power 1 we have $a= 1, b= 1$ so gcd 1
just to cross check for power 2 we have $(1+\sqrt{2})^2 = 3+ 2\sqrt{2})$ and gcd = 1
so we get the result as 1 using above rule repeatedly

 

[lfdahl]

Spoiler

first let us see the relationship of gcd(a,b) and gcd(c,d) where $(c+d\sqrt{2}) = (a+b\sqrt{2})(1+\sqrt{2})$
we get by mutiplication $c= a + 2b , d= a+b)$
so $gcd(c ,d) = gcd(a+2b, a + b) = gcd(a+b,b) = gcd(a,b)$
starting with power 1 we have $a= 1, b= 1$ so gcd 1
just to cross check for power 2 we have $(1+\sqrt{2})^2 = 3+ 2\sqrt{2})$ and gcd = 1
so we get the result as 1 using above rule repeatedly

Well done, kaliprasad!
Below are two alternative solutions:

Spoiler

Solution I.

Note, that $(1+\sqrt{2})^{2017}(1-\sqrt{2})^{2017}=-1$.

If we expand $(1+\sqrt{2})^{2017}$ and $(1-\sqrt{2})^{2017}$ by Newton´s binomial formula, we readily see, that $(1-\sqrt{2})^{2017} = a-b\sqrt{2}$, since irrational terms of the expansions are terms with odd power of $\sqrt{2}$.
Therefore, $(1+\sqrt{2})^{2017}(1-\sqrt{2})^{2017}=(a+b\sqrt{2})(a-b\sqrt{2})=a^2-2b^2.$ Thus, $a^2-2b^2=-1$. Now, if $d$ is a greatest common divisor of $a$ and $b$, then $d|a^2$ and $d|b^2$, and therefore
$d|(a^2-2b^2)=-1$. Thus, $d=1$.

Solution II (induction).

For $n = 1,2,.. $ define the natural numbers $a_n$ and $b_n$ by $(1+\sqrt{2})^n=a_n+b_n\sqrt{2}.$ We prove, that the greatest common divisor of $a_n$ and $b_n$ is equal to $1$ for every $n = 1,2,...$.
Clearly, $a_1 = b_1 = 1$. From

\[a_{n+1}+b_{n+1}\sqrt{2}=(1+\sqrt{2})^{n+1}=(1+\sqrt{2})^n(1+\sqrt{2}) \\\\=(a_n+b_n\sqrt{2})(1+\sqrt{2}) = a_n+2b_n+(a_n+b_n)\sqrt{2}\]

it follows, that

\[a_{n+1} = a_n+2b_n, \: \: \: b_{n+1} = a_n+b_n\]

Now, any common divisor of $a_{n+1}$ and $b_{n+1}$ also divides $2b_{n+1}-a_{n+1} = a_n$ and $a_{n+1}-b_{n+1}= b_n$ and so is a common divisor of $a_n$ and $b_n$. Therefore, gcd$(a_{n+1},b_{n+1})= 1$, whenever gcd$(a_{n},b_{n})= 1$. Since, gcd$(a_1,b_1)= 1$, it follows by induction, that gcd$(a_{n},b_{n})= 1$ for all positive integers $n$. Particularly, gcd$(a,b)=$ gcd$(a_{2017},b_{2017})= 1$.