Evaluar

Question

El problema es evaluar$\lfloor (3 + \sqrt{5})^{34} \rfloor \pmod {100}$

No se permiten calculadoras.

Creo que tengo que deshacerme de$\sqrt{5}$ de alguna manera ya que es irracional y haría difícil encontrar el piso sin hacerlo numéricamente. Pero no estoy seguro de cómo.

Answer 1

Sugerencia: Agregar $(3 - \sqrt{5})^{34}$ dentro de la planta soportes y utilizar el teorema del binomio para cancelar los términos. Tenga en cuenta que $0 < (3 - \sqrt{5})^{34} < 1$.

---

Solución:

Por el teorema del binomio y siguientes de la pista, tenemos que $\lfloor (3 + \sqrt{5})^{34} + (3 - \sqrt{5})^{34} \rfloor = \lfloor 2(3^{34} + {34 \choose 2} 3^{32} 5^1 + {34 \choose 4} 3^{30} 5^2 + \dots {34 \choose 4} 3^{4} 5^{15} + {34 \choose 2} 3^2 5^{16} + 5^{17}) \rfloor$.

El interior es un número entero, por lo que podemos caer al suelo entre corchetes.

Reclamo: La suma de los términos no incluidos los dos primeros, es divisible por $100$.

Prueba: Nos encontramos con que ${34 \choose 2n}$ es incluso para $2 \leq n \leq 8$ por mano de cheques. Tenemos un segundo factor de dos de las $2$ multiplicando en el exterior. A continuación, todos los términos con al menos $5^2$ como un factor y un coeficiente binomial son divisibles por $100$. Se ocupa de todos los términos, excepto para los dos últimos. Podemos ver que los dos últimos términos (sin ser multiplicado por el externo $2$) son ambos impares, por lo que su suma es par. Ambos tienen al menos $5^2$ como un factor, así que cuando se multiplica por la externa $2$ su suma es divisible por $100$.

Así, examinamos los dos primeros términos. Tenga en cuenta que $3^4 \equiv 81, 3^8 \equiv 61, 3^{12} \equiv 41, 3^{16} \equiv 21, 3^{20} \equiv 1 \pmod {100}$. Por lo $3^{34} \equiv 69 \pmod {100}$$3^{32} \equiv 41 \pmod {100}$. Así que tenemos $2(69 + 33 * 17 * 41 * 5) \equiv 2(69 + 61 * 5) \equiv 48 \pmod {100}$

Así que tenemos que $(3 + \sqrt{5})^{34} + (3 - \sqrt{5})^{34} \equiv 48 \pmod {100}$. Desde $(3 - \sqrt{5})^{34}$ entre $0$ y $1$, $(3 + \sqrt{5})^{34}$ se entre $47$$48 \pmod {100}$, por lo que su piso se $\boxed{47}$.

Esto es un poco de cálculo pesado, si alguien puede encontrar una manera que es menos, así que voy a ser feliz.

Answer 2

Esta respuesta inspirada en la secuencia de Fibonacci, en la que $$F_n = \frac{\varphi^n - \overline{\varphi}\,^n}{\sqrt 5} = \frac{\lfloor{\varphi^n}\rfloor + 1}{\sqrt 5} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n\,_{2,1}$$

lo que nos da una manera fácil de calcular $\lfloor \varphi^n \rfloor$ usando la matriz. Por lo que intentar encontrar una matriz que permite el cálculo de $\lfloor\phi^n\rfloor$$\phi = 3 + \sqrt 5$$\overline \phi = 3 - \sqrt 5$, considere la matriz:

$$M = \begin{bmatrix} A & B \\ C & D \end{bmatrix} \tag 1$$

Se ha ecuación característica

$$P(x) = x^2 - (D+A)x + AD - BC \tag 2$$

que para tener los valores propios, la ecuación característica también debe ser:

$$P(x) = (x - \phi)(x - \overline \phi) = x^2 - 6x + 4 \tag 3$$

La eliminación de las variables de $C$ $D$ entre (1) (2) y (3), de hojas:

$$M = \begin{bmatrix} A & B \\ \frac{(6-A)A - 4}{B} & 6 - A \end{bmatrix} \tag 4$$

Ahora, cualquier elección de $A$ $B$ va a trabajar, pero de elegir algo fácil, considere la posibilidad de $A = 3$ para hacer la diagonal agradable y $B=1$ a hacer el resto de niza:

$$M = \begin{bmatrix} 3 & 1 \\ 5 & 3 \end{bmatrix}$$

con el autovalor de la descomposición:

$$M = \begin{bmatrix} 1 & 1 \\ \sqrt{5} & -\sqrt{5}\end{bmatrix} \begin{bmatrix} 3 + \sqrt{5} & 1 \\ 0 & 3 - \sqrt{5}\end{bmatrix} \begin{bmatrix} 1 & 1 \\ \sqrt{5} & -\sqrt{5}\end{bmatrix}^{-1} $$

y es de la siguiente manera:

$$M^n = \begin{bmatrix} 1 & 1 \\ \sqrt{5} & -\sqrt{5}\end{bmatrix} \begin{bmatrix} \phi^n & 1 \\ 0 & \overline \phi\,^n\end{bmatrix} \begin{bmatrix} 1 & 1 \\ \sqrt{5} & -\sqrt{5}\end{bmatrix}^{-1} = \begin{bmatrix} \frac{\phi^n + \overline \phi\,^n}{2} & \frac{\phi^n + \overline \phi\,^n}{2\sqrt{5}} \\ \frac{\phi^n + \overline \phi\,^n}{2 / \sqrt{5}} & \frac{\phi^n + \overline \phi\,^n}{2} \\ \end{bmatrix} $$

Así que tenemos $2 M^n\,_{1,1} = \phi^n + \overline \phi\,^n = \lfloor \phi^n \rfloor + 1$, con un total de:

$$\lfloor(3 + \sqrt{5})^n\rfloor = 2 {\begin{bmatrix} 3 & 1 \\ 5 & 3 \end{bmatrix}^n}_{1,1} - 1$$ $$\downarrow$$ $$\boxed{\lfloor(3 + \sqrt{5})^n\rfloor \equiv 2 {\begin{bmatrix} 3 & 1 \\ 5 & 3 \end{bmatrix}^n}_{1,1} - 1 \pmod{100}} \tag{!!}$$

Matriz de exponenciación modular con números enteros es bastante fácil de hacer con la repetición de la escuadra:

$$ \begin{array} {|c|c|} \hline M^1 & \begin{bmatrix} 3 & 1 \\ 5 & 3 \end{bmatrix} \\ \hline M^2 = (M^1)^2 & \begin{bmatrix} 14 & 6 \\ 30 & 14 \end{bmatrix} \\ \hline M^4 = (M^2)^2 & \begin{bmatrix} 76 & 68 \\ 40 & 76 \end{bmatrix} \\ \hline M^8 = (M^4)^2 & \begin{bmatrix} 96 & 36 \\ 80 & 96 \end{bmatrix} \\ \hline M^{16} = (M^8)^2 & \begin{bmatrix} 96 & 12 \\ 60 & 96 \end{bmatrix} \\ \hline M^{32} = (M^{16})^2 & \begin{bmatrix} 36 & 4 \\ 30 & 36 \end{bmatrix} \\ \hline M^{34} = M^{32}M^2 & \begin{bmatrix} 24 & 70 \\ 60 & 24 \end{bmatrix} \\ \hline \end{array}$$

Por lo $\lfloor(3 + \sqrt{5})^{34}\rfloor \equiv 2 \times 24 - 1 \equiv 47 \pmod{100}$

---

Parece que usando el argumento de estilo, se puede decir en general que si $0 < X - \sqrt{Y} < 1$, entonces el seguimiento de identidad se tiene:

$$\lfloor (X + \sqrt{Y})^n \rfloor = 2{\begin{bmatrix} X & Y \\ 1 & X \end{bmatrix}^n}_{1,1} - 1$$

Me pregunto si esto es un conocido de la identidad?

Answer 3

Utilizamos una ligera modificación de Michael T enfoque que reduce los cálculos necesarios y el número de argumentos técnicos . Tenga en cuenta que $(3+\sqrt{5})^2=14+6\sqrt{5}$. Ahora $$\lfloor(3+\sqrt{5})^{34}\rfloor=\lfloor(14+6\sqrt{5})^{17}\rfloor=\lfloor(14+6\sqrt{5})^{17}+(14-6\sqrt{5})^{17}\rfloor-1$$ desde $14-6\sqrt{5}<1$.

Ahora de expansión con el binomio da

$$(14+6\sqrt{5})^{17}+(14-6\sqrt{5})^{17}=2(14^{17}+{17\choose 2}14^{15}6^25+{17\choose 4}14^{13}6^45^2+\ldots+6^{16}5^8)$$

Desde $6^45^2$ es un múltiplo de a $100$, de inmediato nos encontramos con que sólo la primera $2$ condiciones de la materia. Nota para la siguiente que $7^4=2401\equiv1\pmod{100}$.

Primer plazo: $14^{17}2\equiv7^{17}2^{18}\equiv7^{4(4)+1}2^{9(2)}\equiv7(12)^2\equiv7(44)\equiv308\equiv8\pmod{100}$,

Segundo plazo: $2(17)(8)14^{15}6^25=10(17)(8)14^{15}6^2$, por lo que podemos deshacernos de un factor de $10$, y

$17(8)14^{15}6^2\equiv(7)2^37^{15}2^{15}2^23^2\equiv2^{20}7^{16}3^2\equiv4^2(1)(-1)\equiv-6\equiv4\pmod{10}$.

Por lo tanto la suma de los dos primeros términos es $8+10*4=48 \pmod{100}$, y llegamos a la conclusión de que $\lfloor(3+\sqrt{5})^{34}\rfloor\pmod{100}=48-1=47$.