[Lambda]

¡Hola!

He tratado de realizar el siguiente problema:

Demostrar que  los últimos 6 dígitos de \( 7^{9999} \) son \( 857143 \)

Mi idea era demostrar un equivalente que sería el siguiente:

\( 7^{9999} \equiv{} 857143   (10^6) \)

En un principio traté de aplicar el Teorema de Euler - Fermat pero lo que obtuve fue la siguiente igualdad

\( 7^{\phi(10^6)} \equiv{} 1 (10^6)  \)

, es decir

\( 7^{4*10^5} \equiv{} 1 (10^6)  \)

, hecho que no me ha ayudado mucho.

Lo que detecto es que 7 * 857143 = 6.000.001 y creo que ahí puede estar la clave, pero no lo termino de ver. Agradecería cualquier ayuda al respecto.

Saludos,

[robinlambada]

Hola:

¡Hola!

He tratado de realizar el siguiente problema:

Demostrar que  los últimos 6 dígitos de \( 7^(9999) \) son \( 857143 \)

Mi idea era demostrar un equivalente que sería el siguiente:

\( 7^{9999} \equiv{} 857143   (10^6) \)

En un principio traté de aplicar el Teorema de Euler - Fermat pero lo que obtuve fue la siguiente igualdad

\( 7^{\phi(10^6)} \equiv{} 1 (10^6)  \)

, es decir

\( 7^{4*10^5} \equiv{} 1 (10^6)  \)

, hecho que no me ha ayudado mucho.

Lo que detecto es que 7 * 857143 = 6.000.001 y creo que ahí puede estar la clave, pero no lo termino de ver. Agradecería cualquier ayuda al respecto.

Saludos,

Hay que demostrar que \( 7^{9999} - 857143 \equiv{}0 (10^6)  \)

O lo que es lo mismo \( \dfrac{7^{10^5} - 6\cdot{}10^6-1 }{7}\equiv{}0 (10^6)  \) es decir:

\( 7^{10^5} - 6\cdot{}10^6-1 \equiv{}0 (10^6) \Leftrightarrow{}7^{10^5} -1 \equiv{}0 (10^6)  \)

Pero la fórmula de Euler dice: \( 7^{4*10^5}-1 \equiv{} 0 (10^6) \Leftrightarrow{}(7^{10^5})^4-1\equiv{} 0 (10^6) \)
Solo faltaría demostrar que $$(7^{10^5})^4-1\equiv{} 0 (10^6)\Rightarrow{}7^{10^5}-1\equiv{} 0 (10^6)$$

Saludos.

[robinlambada]

Dejo la terminación en el spoiler.

Spoiler

Sea $$a= 7^{10^5}$$ , Por Euler $$a^4-1\equiv{}0\Leftrightarrow{} (a^2+1)(a+1)(a-1)\equiv{} 0 (10^6)$$

Basta demostrar que ni $$(a^2+1)$$ ni $$(a+1)$$ son múltiplos de 10, por tanto  tampoco lo serán de un millón.

$$7^{10^5}+1\equiv{}((-3)^{10^5}+1 \rightarrow{}(-1)^{5^52^4}+1 \equiv{}1+1\,(mod\, 10)$$ (1)

De igual forma se hace con $$(a^2+1)$$,   $$(a^2+1)\equiv{}1+1\,(mod\,10)$$ (2)

*(añadido) Esta última conclusión no se obtiene de lo anterior, como ha notado geometracat
Por tanto $$ 7^{10^5}-1\equiv{}0 \,(mod\,10^6)$$
-------------------------------------------------------------------------------------

Continuo:
De (1) y (2) se observa que ambos factores son pares pero no múltiplos de 5 por terminar en 2 ( por ello $$(a-1)$$ es múltiplo de  $$5^6$$ .
 A continuación demuestro que $$(a-1)$$ es múltiplo de $$2^6=64$$

Por el teorema de Euler $$7^{32}\equiv{}1 \, mod\, 64$$

$$10^5=3125\cdot{}32\Leftrightarrow{}7^{10^5}-1\equiv{}  1^{3125} -1\equiv{0}\, mod\, 64$$

[cerrar]

Saludos.

[manooooh]

Hola

Otra alternativa más "algorítmitca" propuesta por Ignacio Larrosa:

https://foro.rinconmatematico.com/index.php?topic=101000.msg403166#msg403166

Allí se pedía lo mismo pero buscando los últimos 3 dígitos. La base es la misma. No sé qué tienen con el número \( 7 \)...

Saludos

EDITADO No sirve.

[geómetracat]

Dejo la terminación en el spoiler.

Spoiler

Sea $$a= 7^{10^5}$$ , Por Euler $$a^4-1\equiv{}0\Leftrightarrow{} (a^2+1)(a+1)(a-1)\equiv{} 0 (10^6)$$

Basta demostrar que ni $$(a^2+1)$$ ni $$(a+1)$$ son múltiplos de 10, por tanto  tampoco lo serán de un millón.

$$7^{10^5}+1\equiv{}((-3)^{10^5}+1 \rightarrow{}(-1)^{5^52^4}+1 \equiv{}1+1\,(mod\, 10)$$

De igual forma se hace con $$(a^2+1)$$,   $$(a^2+1)\equiv{}1+1\,(mod\,10)$$

Por tanto $$ 7^{10^5}-1\equiv{}0 \,(mod\,10^6)$$

[cerrar]

Saludos.

Cuidado con eso, porque al no ser \( 10^6 \) primo la cosa no es tan sencilla. Por ejemplo, a priori podrías tener que esa descomposición fuera \( 2 \cdot 2 \cdot 250000 \equiv 0 \mod \; 10^6 \), de manera que ninguno de los primeros dos factores es múltiplo de \( 10 \), pero el último no es múltiplo de \( 10^6 \).

[robinlambada]

Hola manoooh

Hola

Otra alternativa más "algorítmitca" propuesta por Ignacio Larrosa:

https://foro.rinconmatematico.com/index.php?topic=101000.msg403166#msg403166

Allí se pedía lo mismo pero buscando los últimos 3 dígitos. La base es la misma. No sé qué tienen con el número \( 7 \)...

Saludos

El método de descomponer en potencias de 2  el exponente, se podría usar , pero no es factible, habría que descomponer 100.000 en base 2 y además es módulo un millón, tendrías que multiplicar demasiadas potencias al cuadrado de números de 6 cifras. Creo que sería la muerte a pellizcos.

Saludos.

[robinlambada]

Hola geómetracat.

Dejo la terminación en el spoiler.

Spoiler

Sea $$a= 7^{10^5}$$ , Por Euler $$a^4-1\equiv{}0\Leftrightarrow{} (a^2+1)(a+1)(a-1)\equiv{} 0 (10^6)$$

Basta demostrar que ni $$(a^2+1)$$ ni $$(a+1)$$ son múltiplos de 10, por tanto  tampoco lo serán de un millón.

$$7^{10^5}+1\equiv{}((-3)^{10^5}+1 \rightarrow{}(-1)^{5^52^4}+1 \equiv{}1+1\,(mod\, 10)$$

De igual forma se hace con $$(a^2+1)$$,   $$(a^2+1)\equiv{}1+1\,(mod\,10)$$

Por tanto $$ 7^{10^5}-1\equiv{}0 \,(mod\,10^6)$$

[cerrar]

Saludos.

Cuidado con eso, porque al no ser \( 10^6 \) primo la cosa no es tan sencilla. Por ejemplo, a priori podrías tener que esa descomposición fuera \( 2 \cdot 2 \cdot 250000 \equiv 0 \mod \; 10^6 \), de manera que ninguno de los primeros dos factores es múltiplo de \( 10 \), pero el último no es múltiplo de \( 10^6 \).

Tienes toda la razón, no había caído.
Hay que hilar más fino.
Muchas gracias por el vistazo , lo corrijo ahora.

[robinlambada]

Una aclaración, también se podría haber demostrado que $$7^{10^5}-1 $$ es múltiplo de $$10^6$$ , sin usar:

$$7^{4\cdot{}10^5}-1\equiv{}0 \,mod \, 10^6$$

Se puede demostrar usando también que $$7^{10^5}-1\equiv{}0 \,mod \, 5^6$$  con la igualdad de Euler:  $$7^{4\cdot{}5^5}-1\equiv{}0 \,mod \, 5^6$$

Saludos.

[geómetracat]

Una aclaración, también se podría haber demostrado que $$7^{10^5}-1 $$ es múltiplo de $$10^6$$ , sin usar:

$$7^{4\cdot{}10^5}-1\equiv{}0 \,mod \, 10^6$$

Se puede demostrar usando también que $$7^{10^5}-1\equiv{}0 \,mod \, 5^6$$  con la igualdad de Euler:  $$7^{4\cdot{}5^5}-1\equiv{}0 \,mod \, 5^6$$

Saludos.

Sí, creo que ese es el camino más sencillo. Con eso demuestras que \( 7^{4\cdot 10^5} -1 \) es múltiplo de \( 5^6 \) (pero todavía no está claro que sea múltiplo de \( 10^6 \)).
Ahora bien, por otro lado, nuevamente de Euler, \( 7^{2^5}-1 \) es múltiplo de \( 2^6 \), luego \( 7^{10^5} \) es múltiplo de \( 2^6 \).

Como \( 7^{10^5} \) es múltiplo de \( 2^6 \) y de \( 5^6 \) a la vez, y éstos son coprimos, se sigue que es múltiplo de \( 10^6 \).

[robinlambada]

Una aclaración, también se podría haber demostrado que $$7^{10^5}-1 $$ es múltiplo de $$10^6$$ , sin usar:

$$7^{4\cdot{}10^5}-1\equiv{}0 \,mod \, 10^6$$

Se puede demostrar usando también que $$7^{10^5}-1\equiv{}0 \,mod \, 5^6$$  con la igualdad de Euler:  $$7^{4\cdot{}5^5}-1\equiv{}0 \,mod \, 5^6$$

Saludos.

Sí, creo que ese es el camino más sencillo. Con eso demuestras que \( 7^{4\cdot 10^5} -1 \) es múltiplo de \( 5^6 \)

Si, también pienso que es más sencillo.

Use  \( 7^{4 \cdot 10^5} -1 \, mod\,10^6 \) , por que es el camino que empezó Lambda

En un principio traté de aplicar el Teorema de Euler - Fermat pero lo que obtuve fue la siguiente igualdad

\( 7^{\phi(10^6)} \equiv{} 1 (10^6)  \)

, es decir

\( 7^{4*10^5} \equiv{} 1 (10^6)  \)

, hecho que no me ha ayudado mucho.

Para mostrar que se puede demostrar usándola.

(pero todavía no está claro que sea múltiplo de \( 10^6 \)).
Ahora bien, por otro lado, nuevamente de Euler, \( 7^{2^5}-1 \) es múltiplo de \( 2^6 \), luego \( 7^{10^5} \) es múltiplo de \( 2^6 \).

Como \( 7^{10^5} \) es múltiplo de \( 2^6=64 \) y de \( 5^6 \) a la vez, y éstos son coprimos, se sigue que es múltiplo de \( 10^6 \).

Si claro , ya mostré en el primer spoiler  que  \( 7^{10^5} \) es múltiplo de \( 2^6 \), no lo puse por no repetirme ( la verdad es que no he sido muy claro en el último mensaje, debí haber añadido que \( 7^{10^5} \) es múltiplo de \( 2^6 \),pero lo di por hecho)