Consider the equation $a_n +b_n\sqrt{2} = (1+\sqrt{2})^n$ where $a_n, b_n \in \mathbb{Z} \ge 1$. Prove that $\gcd(a_n, b_n) = 1$.

Question

Consider the equation $a_n +b_n\sqrt{2} = (1+\sqrt{2})^n$ where $a_n, b_n \in \mathbb{Z} \ge 1$. Prove that $\gcd(a_n, b_n) = 1$.

I know that $(1+2\sqrt{3}) = 1^3 + 3(1)^2(\sqrt{2})^2 + 3(1)(\sqrt{2})^2 + (\sqrt{2})^3 = 7+5\sqrt{2}$

so $a_n = 7, b_n = 5$ by binomial expansion.

So my strategy is to prove this via mathematical induction. The base case is easy. What I need for the inductive step is to get the relation between $(a_n+1, bn+1)$ to $(a_n, b_n)$. So we get:

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

So we have $a_{n+1} = a_n + 2b_n, b_{n+1} = a_n + b_n$

So now I'm trying to use the euclidean algorithm to show that $\gcd(a_{n+1}, b_{n+1}) = 1$. So we get:

$\gcd(a_{n+1}, b_{n+1}) = (a_n + 2b_n,a_n + b_n)=$

$a_n+2b_n= 1 *(a_n + b_n) + b_n =$

$a_n + b_n = 1 * (b_n) + a_n$

$b_n = 0 * (a_n) + bn$

But, where do I go from here?

Any help would be appreciated!

-IdleMathGuy

Answer 1

Here is an alternative approach. You have $$a_n-b_n\sqrt{2}=(1-\sqrt{2})^n\,.$$ That is, $$\begin{align}a_n^2-2b_n^2&=\big(a_n-b_n\sqrt2\big)(a_n+b_n\sqrt2\big)\\&=\big((1-\sqrt2)(1+\sqrt2)\big)^n=(-1)^n\,.\end{align}$$ Thus, $$x_n\,a_n+y_n\,b_n=1\,,$$ where $x_n:=(-1)^n\,a_n$ and $y_n:=-2\,(-1)^n\,b_n$ are integers. Thus, $\gcd(a_n,b_n)=1$.

Answer 2

Your inductive approach is fine.

Suppose that $d\in\mathbb{N}\setminus\{1\}$ is such that $d\mid a_{n+1}$ and $d\mid b_{n+1}$. Then $d\mid a_{n+1}-b_{n+1}=b_n$ and $d\mid2b_{n+1}-a_{n+1}=a_n$. With this observation, it's easy to complete an inductive proof.

Answer 3

Let $d=\gcd(a_{n+1},b_{n+1})$ then $$d\mid a_n+2b_n\;\;\;{\rm and}\;\;\; d\mid a_n+b_n$$

so $$d\mid (a_n+2b_n)-(a_n+b_n) = b_n$$

but then $$ d\mid (a_n+b_n)-b_n = a_n$$

so $d=1$.

Answer 4

worth emphasizing that multiplying a (column) vector of integers by an integer (square) matrix with integer inverse (so determinant is $\pm 1$) preserves the gcd of the vector... Your (row) vector $(a,b)$ is mapped to $(a+2b, a+b);$ as columns, the matrix is $$ \left( \begin{array}{cc} 1 & 2 \\ 1 & 1 \end{array} \right) $$ with determinant $-1$

If I demand $$ \left( \begin{array}{cc} 1 & 2 \\ 1 & 1 \end{array} \right) \left( \begin{array}{c} u \\ v \end{array} \right) = \left( \begin{array}{c} x \\ y \end{array} \right) $$ it is obvious that $\gcd(u,v)$ divides both $x,y$ so that $\gcd(u,v) | \gcd(x,y).$ If I then point out that $$ \left( \begin{array}{cc} -1 & 2 \\ 1 & -1 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left( \begin{array}{c} u \\ v \end{array} \right) $$ we see that $\gcd(x,y) | \gcd(u,v),$ therefore $$\gcd(x,y) = \gcd(u,v) $$

Answer 5

We have $$ \pmatrix{a_{n+1} \\ b_{n+1}} = \pmatrix{1 & 2 \\ 1 & 1} \pmatrix{a_n \\ b_n} $$ and so $$ \pmatrix{a_n \\ b_n} = \pmatrix{1 & 2 \\ 1 & 1}^n \pmatrix{a_0 \\ b_0} = \pmatrix{1 & 2 \\ 1 & 1}^n \pmatrix{1 \\ 0} $$ Therefore, $\pmatrix{a_n \\ b_n}$ is the first column of $\pmatrix{1 & 2 \\ 1 & 1}^n$. Write $$ \pmatrix{1 & 2 \\ 1 & 1}^n = \pmatrix{a_n & c_n \\ b_n & d_n} $$ Taking determinants, we get $$ (-1)^n = a_n d_n - b_n c_n $$ which implies $\gcd(a_n, b_n) = 1$.

(It turns out and easily proved by induction that $d_n=a_n$ and $c_n=2b_n$, which is nice but not relevant here.)