Dejemos que $( \sqrt{2} + 1)^{1000} = a + b \sqrt{2}$ donde a y b son números enteros. Encuentra el mayor factor común de b y 81.

Question

Dejemos que $( \sqrt{2} + 1)^{1000} = a + b \sqrt{2}$ , donde $a$ y $b$ son números enteros. Encuentra el mayor factor común de $b$ y $81$ .
¿Cómo se puede resolver esta cuestión? He intentado utilizar el teorema del binomio, pero no ha funcionado. ¿Cómo se resolvería este problema si se presentara en una Olimpiada de Matemáticas?

Sé que la respuesta es una de:

(A) 1 (B) 3 (C) 9 (D) 27 (E) 81.

Según uno de los miembros de Stack Exchange, la respuesta es la 3. Se encontró utilizando Python.

Answer 1

Es un poco molesto, pero ciertamente factible, calcular la respuesta elevando repetidamente al cuadrado en $(\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}.$$

Ahora en binario, $1000 = 1111101000_2$ o en otras palabras, $1000 = 512 + 256 + 128 + 64 + 32 + 8.$ Por lo tanto, para cualquier $a$ $$a^{1000} = a^{8}a^{32}a^{64}a^{128}a^{256}a^{512},$$ y podemos calcular este producto para $a=(1+\sqrt{2})$ utilizando la tabla anterior: $$(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}$$ y $(51,81)=3.$

Answer 2

Esto es muy largo para un comentario:

Nosotros decimos $ ( \sqrt{2} + 1)^{n} = a_n + b_n \sqrt{2}$ y $a_n,b_n$ son números enteros. Por lo tanto, $( 1- \sqrt{2})^{n} = a_n - b_n \sqrt{2}$ . Para un valor impar positivo de $n=2k-1$ por producto

$-1=( \sqrt{2} + 1)^{n} ( 1- \sqrt{2} )^{n}= (a_n + b_n \sqrt{2})(a_n - b_n \sqrt{2})$ .

Por lo tanto, $a_n^2 - 2b_n^2= -1$ . $a^2-2b^2=-1$ es la ecuación de Pell negativa y la solución mínima es $(a_1,b_1)=(1,1)$ . Otras soluciones: $a_{n+2}+b_{n+2}\sqrt 2= (a_n + b_n \sqrt 2)\cdot (1+\sqrt 2)^2$ y luego

$$a_{n+2}= 3a_n + 4b_n$$ $$ b_{n+2} = 2a_n + 3b_b$$

Por ejemplo $(a_3,b_3)=(7,5)$ . Así que, $$a_{n+2} \equiv b_n \pmod{3}$$ $$b_{n+2} \equiv 2a_n \equiv 2b_{n-2}\pmod{3}$$

Desde $b_1=1$ no es divisible por $3$ , entonces para todos los impar $n$ , $b_n$ no es divisible por $3$ . De la misma manera, $a_n$ no es divisible por $3$ .

En $ ( \sqrt{2} + 1)^{999} = a_{999} + b_{999} \sqrt{2}$ , $a_{999}$ y $b_{999}$ no puede ser divisible por $3$ . Sin embargo, no dije nada sobre $b_{1000}$ . Pensaré en los valores pares de $n$ .

Answer 3

He encontrado una solución muy rápida con el uso de relaciones de recursión lineales.

Digamos que $( \sqrt{2} + 1)^{n} = a_n + b_n \sqrt{2}$ . Aquí $n\ge 1$ y $a_n,b_n,n$ son enteros positivos. Entonces $( - \sqrt{2} + 1)^{n} = a_n - b_n \sqrt{2}$ . Por lo tanto,

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

Por $(1)$ , $b_1=1$ y $b_2=2$ . Ahora, podemos escribir el polinomio característico de $b_n$ . Por $(1)$ las raíces del polinomio característico son $r_1=1+\sqrt{2}$ y $r_2=1-\sqrt{2}$ . Por lo tanto, el polinomio característico de $b_n$ es

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

y encontramos

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

Examinemos los términos de $b_n$ en $\mod 9$ .

$b_1 \equiv 1 \pmod{9}$ , $b_2 \equiv 2 \pmod{9}$ . Tenemos que encontrar el más pequeño positivo $m$ entero tal que $b_{m+1}=1$ y $b_{m+2}=2$ . Vamos a buscarlo:

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

Ahora $b_{25} \equiv 1 \pmod{9}$ y $b_{26} \equiv 2 \pmod{9}$ . Por lo tanto, $b_n$ es periódica en $\mod 9$ y el periodo de la misma es $m=24$ . Así, $1000 \equiv 16 \pmod{24}$ y

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

Por lo tanto, $3 \mid b_{1000}$ pero $9 \not\mid b_{1000}$ . Finalmente $\gcd(81,b_{1000})=3$ .

Nota: Este método es muy potente. Un ejemplo, $n=1234567890$ y $n\equiv 18 \pmod{24}$ . Así, $b_{1234567890}\equiv b_{18}\equiv 2 \pmod{9}$ y $3 \not\mid b_{1234567890}$ . (Para mayor claridad, escribí los detalles de la solución. Mi solución manual es corto y en la imagen).