Tengo que demostrar que $17$ divide $\underbrace{1111111111111111}_{\text{16 1's}}$ y no divide $\underbrace{11111111}_{\text{8 1's}}$ utilizando la congruencia.
Sé que $\underbrace{1111111111111111}_{\text{16 1's}}= \frac{10^{16}-1}{9}$ y que $10^{15}\equiv{1}\pmod {17}$ . Pero, ¿cómo puedo utilizar estos dos hechos para averiguar si $17$ divide $1111111111111111$ ?
1/17=tiene una ocurrencia decimal periódica de 0,0588235294117647 = un factor principal de $10^{-n}*5882352941176470588$ veces $(10^{-16}+(10^{-16})^2+…)$ con el límite de $1/(1-10^{-16})=10^{16}/(10^{16}-1)$ Se deduce que 588235294117647*17 nos da los 16 nueves.
¿Sabe usted que $a^{p-1}-1$ es siempre divisible por $p$ cuando $p$ es primo y $a$ no es divisible por $p$ ? Es un resultado famoso. Tome $a=10$ y $p=17$ para conseguir $9999999999999999$ . Y dividiendo $9$ no cambiará la divisibilidad por $17$ .
$11111111$ es demasiado fácil para un factor de peso. Es claramente divisible por $11$ que es primo ( $11\cdot01010101$ ). Y también por $101$ que es primo ( $101\cdot00110011$ ). Después de dividir estos dos factores primos, se tiene $$11111111=11\cdot101\cdot10001$$ Para el factor restante de $10001$ , tenga en cuenta que es $100^2+1$ . Eso no es útil para el factoring. Pero pasar a calcular es $101^2-200$ . Sigue sin ser útil. $102^2-403$ . $103^2-608$ . $104^2-815$ . $105^2-1024$ . Aha. Así que es $105^2-32^2=(105-32)(105+32)=73\cdot137$ . Así que tienes $$11111111=11\cdot73\cdot101\cdot137$$
Nunca he visto este método de factorización. (la parte "aha"). ¿Se repite el proceso hasta que el segundo término es un cuadrado perfecto?
@TonyEnnis No hay garantía de que esa parte funcione. Desde una perspectiva, va a ser tan lento en general como comprobar los primos que empiezan por $2,3,\ldots$ . Esto es algo así como la comprobación de los divisores primos empezando por el centro en lugar de por la parte inferior. En este caso, sin embargo, dada la procedencia del número, mi corazonada era que cualquier divisor primo restante sería grande. Y como teníamos $100^2+1$ de la empresa, era fácil saber por dónde empezar este proceso. Aun así, insisto, no hay garantía de que esto dé sus frutos. Quizás $10001$ resultaría de primera.
@TonyEnnis La idea aquí también es utilizada por el Algoritmo de factorización Quadratic Sieve para factorizar números grandes.
Dejemos que $1111111111111111 \equiv k \pmod {17}$ .
Entonces $9999999999999999 \equiv 9k\pmod {17}$
Y $10000000000000000 =10^{16} \equiv 9k + 1\pmod {17}$ .
Y sino el pequeño teorema de Fermat:
$9k + 1 \equiv 10^{16} \equiv 1 \pmod{17}$
así que $9k \equiv 0 \pmod 17$ .
No $2\cdot 9 = 18 \equiv 1 \pmod {19}$ así que $9^{-1} \equiv 2 \pmod {17}$ y podemos hacerlo:
Así que $2\cdot 9k \equiv 2\cdot 0 \pmod {17}$
$k \equiv 0 \pmod 7$ .
Así que $1111111111111111 \equiv 0 \pmod {17}$ y hemos terminado. $17$ divide $1111111111111111$
Mientras tanto, si $11111111\equiv m \pmod{17}$ entonces
$99999999 \equiv 9m\pmod {17}$
$10^8 \equiv 9m + 1 \pmod {17}$ .
Y ser sucesivo cuadrando $10^2 \equiv 100=6*17-2\equiv -2 \pmod {17}$ . $10^4\equiv (-2)^2\equiv 4\pmod{17}$ y $10^8 \equiv 4^2 =16\equiv -1 \pmod {17}$ .
SO $9m + 1 \equiv -1\pmod{17}$
$9m \equiv -2 \pmod {17}$
$m\equiv 2\cdot 9m \equiv -2\cdot 2 \equiv -4 \equiv 13 \pmod {17}$ .
Y hemos terminado $17$ no divide $11111111$ y, efectivamente, tendremos un remanente de $13$ si lo intentamos.
$11111098= 653594\times 17$ y $11111111=653594\times 17 + 13$ .
$$ 1111111111111111 = \sum_0^{15} 10^ i $$
Como 17 es primo, los 16 valores $10^0$ , $10^1$ , ..., $10^{15}$ son distintos y no nulos mod 17. (En caso contrario, tenemos $10^m = 17k$ para algunos enteros $k$ , $0\leq m < 17$ en la que 17 es un factor del lado derecho pero no del lado izquierdo).
Así,
$$ 1111111111111111 = \sum_0^{15} 10^i $$
$$ = 1 + 2 + 3 + ... + 16 \mod 17 $$
$$ = (1 + 16) + (2 + 15) + ... + (8 + 9) \mod 17 $$
$$ = 8 \times 17 \mod 17 $$
$$ = 0 \mod 17 $$
Es cierto que 10^0..10^15 son todos distintos módulo 17, pero no es cierto para cada valor módulo 17.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Es $10^{16}\equiv1\pmod{17}$ y no $10^{15}$ . O puedes hacer una división larga.
0 votos
Pero $10^16\equiv{1} (mod 17)$ es igual a 100000000000000000
0 votos
1/17=tiene una ocurrencia decimal periódica de 0,0588235294117647 = un factor principal de $10^{-n}*5882352941176470588$ veces $(10^{-16}+(10^{-16})^2+…)$ con el límite de $1/(1-10^{-16})=10^{16}/(10^{16}-1)$ Se deduce que 588235294117647*17 nos da los 16 nueves.