Demuestra que 17 divide a 11111111111111 (16 1's) y no divide a 11111111

Question

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

Answer 1

$1111111111111111=10^{15} + ... + 1 = \large{(10^{16} -1)\over9}$

$10^2 \equiv -2\pmod {17}$

$10^{16} - 1 = (-2)^8 - 1 = 256 -1 \equiv 1 -1 = 0\pmod {17}$

$11111111= \large{(10^8 -1 )\over9}$

$10^2 \equiv -2\pmod {17}$

$10^8 - 1 \equiv (-2)^4 - 1 = 15 \pmod {17}$

Answer 2

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

Answer 3

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

Answer 4

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