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$. 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
 A: 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) $$
A: 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$.
A: 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.
A: 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$. 
A: 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.)
