Let $( \sqrt{2} + 1)^{1000} = a + b \sqrt{2}$, where a and b are integers. Find the greatest common factor of b and 81. Let $( \sqrt{2} + 1)^{1000} = a + b \sqrt{2}$, where $a$ and $b$ are integers. Find the greatest common factor of $b$ and $81$.
How would one solve this question? I tried to use the binomial theorem but that approach did not work. How would one solve this problem if it were to appear on a Math Olympiad?  
I know the answer is one of:
(A) 1 (B) 3 (C) 9 (D) 27 (E) 81.
According to one of the Stack Exchange members, the answer is 3. It was found using Python.  
 A: This is so long for a comment:
We say $ ( \sqrt{2} + 1)^{n} = a_n + b_n \sqrt{2}$ and $a_n,b_n$ are integers. Therefore $( 1- \sqrt{2})^{n} = a_n - b_n \sqrt{2}$. For positive odd value of $n=2k-1$, by product
$-1=( \sqrt{2} + 1)^{n} ( 1- \sqrt{2} )^{n}= (a_n + b_n \sqrt{2})(a_n - b_n \sqrt{2})$.
Hence $a_n^2 - 2b_n^2= -1$. $a^2-2b^2=-1$ is negative Pell equation and minimal solution is $(a_1,b_1)=(1,1)$. Other solutions: $a_{n+2}+b_{n+2}\sqrt 2= (a_n + b_n \sqrt 2)\cdot (1+\sqrt 2)^2$ and then
$$a_{n+2}= 3a_n + 4b_n$$ $$ b_{n+2} = 2a_n + 3b_b$$
For example $(a_3,b_3)=(7,5)$. So, $$a_{n+2} \equiv b_n \pmod{3}$$ $$b_{n+2} \equiv 2a_n \equiv 2b_{n-2}\pmod{3}$$
Since $b_1=1$ is not divisible by $3$, then for all odd $n$, $b_n$ is not divisible by $3$. Similarly, $a_n$ is not divisible by $3$.
In $ ( \sqrt{2} + 1)^{999} = a_{999} + b_{999} \sqrt{2}$, $a_{999}$ and $b_{999}$ can't divisible by $3$. Yet, I didn't say anything about $b_{1000}$. I will think about even values of $n$.
A: It is a bit annoying, but certainly feasible, to compute the answer by repeated squaring in $(\mathbb{Z}/81\mathbb{Z})[\sqrt{2}]$.
$$(1+\sqrt{2})^2 \equiv 3+2\sqrt{2}$$
$$(1+\sqrt{2})^4 \equiv 17+12\sqrt{2}$$
$$(1+\sqrt{2})^8 \equiv 10+3\sqrt{2}$$
$$(1+\sqrt{2})^{16} \equiv 37+60\sqrt{2}$$
$$(1+\sqrt{2})^{32} \equiv 64+66\sqrt{2}$$
$$(1+\sqrt{2})^{64} \equiv 10 + 24\sqrt{2}$$
$$(1+\sqrt{2})^{128} \equiv 37 + 75\sqrt{2}$$
$$(1+\sqrt{2})^{256} \equiv 64 + 42\sqrt{2}$$
$$(1+\sqrt{2})^{512} \equiv 10 + 30\sqrt{2}.$$
Now in binary, $1000 = 1111101000_2$, or in other words, $1000 = 512 + 256 + 128 + 64 + 32 + 8.$ Therefore for any $a$
$$a^{1000} = a^{8}a^{32}a^{64}a^{128}a^{256}a^{512},$$
and we can calculate this product for $a=(1+\sqrt{2})$ using the table above:
$$(1+\sqrt{2})^{40}\equiv 64+42\sqrt{2}$$
$$(1+\sqrt{2})^{104}\equiv 64+12\sqrt{2}$$
$$(1+\sqrt{2})^{232}\equiv 37+60\sqrt{2}$$
$$(1+\sqrt{2})^{488}\equiv 37+48\sqrt{2}$$
$$(1+\sqrt{2})^{1000}\equiv 10+51\sqrt{2}$$
and $(51,81)=3.$
