Let $( \sqrt{2} + 1)^{1000} = a + b \sqrt{2}$, where a and b are integers. Find the greatest common factor of b and 81.

Question

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.

Answer 1

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.$

Answer 2

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$.

Answer 3

I found a very fast solution with using linear reccurence relations.

Let's say $( \sqrt{2} + 1)^{n} = a_n + b_n \sqrt{2}$. Here $n\ge 1$ and $a_n,b_n,n$ are positive integers. Then $( - \sqrt{2} + 1)^{n} = a_n - b_n \sqrt{2}$. Hence

$$b_n = \dfrac{1}{2\sqrt2} \left[ ( 1+\sqrt{2})^{n} - ( 1-\sqrt{2})^{n} \right] \tag{1}$$

By $(1)$, $b_1=1$ and $b_2=2$. Now, we can write characteristic polynomial of $b_n$. By $(1)$, roots of the characteristic polynomial are $r_1=1+\sqrt{2}$ and $r_2=1-\sqrt{2}$. Therefore characteristic polynomial for $b_n$ is

$$r^2-2r-1=0 \tag{2}$$

and we find

$$b_{n+2}=2b_{n+1}+b_n \tag{3}$$

Let's examine the terms of $b_n$ in $\mod 9$.

$b_1 \equiv 1 \pmod{9}$, $b_2 \equiv 2 \pmod{9}$ . We have to find smallest positive $m$ integer such that $b_{m+1}=1$ and $b_{m+2}=2$. Let's search it:

$b_3 = 2b_2+b_1 \equiv 5 \pmod{9}$, $b_4 = 2b_3+b_2 \equiv 3 \pmod{9}$, $b_5 \equiv 2 \pmod{9}$, $b_6 \equiv 7 \pmod{9}$, $b_7 \equiv 7 \pmod{9}$, $b_8 \equiv 3 \pmod{9}$, $b_9 \equiv 4 \pmod{9}$, $b_{10} \equiv 2 \pmod{9}$, $b_{11} \equiv 8 \pmod{9}$, $b_{12} \equiv 0 \pmod{9}$, $b_{13} \equiv 8 \pmod{9}$, $b_{14} \equiv 7 \pmod{9}$, $b_{15} \equiv 4 \pmod{9}$, $b_{16} \equiv 6 \pmod{9}$, $b_{17} \equiv 7 \pmod{9}$, $b_{18} \equiv 2 \pmod{9}$, $b_{19} \equiv 2 \pmod{9}$, $b_{20} \equiv 6 \pmod{9}$, $b_{21} \equiv 5 \pmod{9}$, $b_{22} \equiv 7 \pmod{9}$, $b_{23} \equiv 1 \pmod{9}$, $b_{24} \equiv 0 \pmod{9}$.

Now $b_{25} \equiv 1 \pmod{9}$ and $b_{26} \equiv 2 \pmod{9}$. Therefore $b_n$ is periodic in $\mod 9$ and period of it is $m=24$. Thus $1000 \equiv 16 \pmod{24}$ and

$$b_{1000} \equiv b_{16} \equiv 6 \pmod{9}$$

Hence $3 \mid b_{1000}$ but $9 \not\mid b_{1000}$. Finally $\gcd(81,b_{1000})=3$.

Note: This method is very powerful. An example, $n=1234567890$ and $n\equiv 18 \pmod{24}$. Thus $b_{1234567890}\equiv b_{18}\equiv 2 \pmod{9}$ and $3 \not\mid b_{1234567890}$. (For clearness, I wrote details of solution. My manual solution is short and it in the picture.)