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

  • MHB
  • Thread starter lfdahl
  • Start date
  • Tags
    Gcd
In summary, the GCD (Greatest Common Divisor) of $(1+\sqrt2)^{2017}$ is 1, as there is no other number that can divide it without leaving a remainder. To find the GCD, we can use the Euclidean Algorithm by continuously dividing the larger number by the smaller number until the remainder is 0. The GCD of a number is always unique and a positive integer, so it cannot be a complex number. The GCD of $(1+\sqrt2)^{2017}$ may not have any significant practical use, but it can be useful in various mathematical calculations.
  • #1
lfdahl
Gold Member
MHB
749
0
Find the greatest common divisor of the natural numbers, $a$ and $b$, satisfying:
$$\left(1+\sqrt{2}\right)^{2017} = a + b \sqrt{2}.$$
 
Mathematics news on Phys.org
  • #2
lfdahl said:
Find the greatest common divisor of the natural numbers, $a$ and $b$, satisfying:
$$\left(1+\sqrt{2}\right)^{2017} = a + b \sqrt{2}.$$

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
 
  • #3
kaliprasad said:
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:

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$.
 
Last edited:

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

What is the GCD of $(1+\sqrt2)^{2017}$?

The GCD (Greatest Common Divisor) of a number is the largest number that divides both the given number and the other number without leaving a remainder. In this case, the GCD of $(1+\sqrt2)^{2017}$ would be 1, as there is no other number that can divide it without leaving a remainder.

How is the GCD of $(1+\sqrt2)^{2017}$ calculated?

To find the GCD of a given number, we can use the Euclidean Algorithm. This involves dividing the larger number by the smaller number and then using the remainder as the new divisor, until the remainder is 0. In the case of $(1+\sqrt2)^{2017}$, since the remainder is always 1, the GCD would be 1.

Is the GCD of $(1+\sqrt2)^{2017}$ unique?

Yes, the GCD of a number is always unique. This means that for any given number, there is only one largest number that can divide it without leaving a remainder.

Can the GCD of $(1+\sqrt2)^{2017}$ be a complex number?

No, the GCD of a number is always a positive integer. Complex numbers involve both real and imaginary parts, which are not considered when finding the GCD. In this case, the GCD would simply be 1.

Why do we need to find the GCD of $(1+\sqrt2)^{2017}$?

Finding the GCD of a number can be useful in many mathematical calculations, such as simplifying fractions or finding common factors. It can also help in determining if two numbers are relatively prime (have no common factors other than 1). However, in the case of $(1+\sqrt2)^{2017}$, the GCD is simply 1 and may not have any significant practical use.

Similar threads

Replies
2
Views
1K
Replies
4
Views
2K
Replies
1
Views
750
Replies
2
Views
1K
Replies
5
Views
2K
Replies
2
Views
1K
Replies
8
Views
1K
Back
Top