¿Cuál es el resto para {10 ^ 100/19}?

Debe aplicar el teorema de Fermat “pequeño”, que dice que si p es primo, entonces x ^ p y x tienen el mismo resto cuando se divide por p (y 19 es primo). Por lo tanto, dado que 100 = 19 × 5 + 5, 10 ^ 100 tiene el mismo resto que 10 ^ 10

Ahora aplico otro truco. Tomo la representación binaria del exponente 10, 1010 y reemplazo 1 con SM, 0 con S: SM S SM S.

S significa cuadrado, M significa multiplicar por 10; y cada vez tomo el resto de la división por 19. Comienzo con 1 y hago: SMSSMS

1 S = 1

1 M = 10

10 S = 100 = 5

5 S = 25 = 6

6 M = 60 = 3

3 S = 9

Entonces el resultado es 9 (como han dicho otros).

¿Por qué funciona el truco S / M? El procedimiento puede explicarse recursivamente de la siguiente manera:

  • si n es par, n = 2m, entonces x ^ n = (x ^ m) ^ 2
  • si n es impar, n = 2m + 1, entonces x ^ n = (x ^ m) ^ 2 × x
  • ¿Cómo calculo la representación binaria? Si n es par, apilo un 0 y divido n entre 2; si n es impar, apilo un 1 y divido n-1 entre 2. Hasta que obtenga 0. Entonces, con la expansión binaria del exponente, simplemente transformo una llamada recursiva en una operación en línea.

(Reconozco que la explicación puede ser un poco difícil, y no proporcioné una prueba del pequeño teorema de Femat, que sin embargo es fácil, por ejemplo, por inducción, usando la expansión binomial).

Tomar 95 (el quinto múltiplo de 19) de 100 nos deja con 5.

10 ^ 100 es lo mismo que 100 ^ 50 por reglas de exponente ya que 100 = 10 ^ 2. Comenzaré usando esta idea y continuaré con ideas similares. Vea si puede seguirlo. Cuando uso ~ quiero decir que las dos cosas a su alrededor tienen el mismo resto cuando se dividen entre 19.

10 ^ 100 = 100 ^ 50 ~ 5 ^ 50 = 25 ^ 25 ~ 6 ^ 25 = 6 * 6 ^ 24 ~ 6 * 36 ^ 12 ~ 6 * (-2) ^ 12 = 6 * 16 ^ 3 ~ 6 * ( -3) ^ 3 = 6 * -27 ~ 6 * 11 = 66 ~ 9

Entonces la respuesta es 9 .

Probablemente hay mejores maneras de hacerlo, pero esta es la forma que me vino a la mente.

10 ^ 100

= (10²) ^ 50

= {19 × 5 + 5} ^ 50

≡5 ^ 50

= (5²) ^ 25

= {19 + 6} ^ 25

≡6 ^ 25

= 6 × (6²) ^ 12

≡6 × (38–2) ^ 12

≡6 × (2) ^ 12

= 6 × {2 ^ 4) ³

= 6 × {19–3} ³

= -6 × 3 × 9

= —3 × 54

= —3 × {57–3}

≡ 9 【mod19】

Como 19 es primo y 10 no es divisible entre 19, según el pequeño teorema de Fermat:

[matemática] 10 ^ {19–1} [/ matemática] [matemática] \ equiv [/ matemática] [matemática] 1 [/ matemática] [matemática] mod [/ matemática] [matemática] 19 [/ matemática]

[matemática] => [/ matemática] [matemática] 10 ^ {18} [/ matemática] [matemática] \ equiv [/ matemática] [matemática] 1 [/ matemática] [matemática] mod [/ matemática] [matemática] 19 [/matemáticas]

[matemática] => [/ matemática] [matemática] 10 ^ {90} [/ matemática] [matemática] = [/ matemática] [matemática] 10 ^ {18 * 5} [/ matemática] [matemática] \ equiv [/ matemática] [matemática] 1 ^ 5 [/ matemática] [matemática] \ equiv [/ matemática] [matemática] 1 [/ matemática] [matemática] mod [/ matemática] [matemática] 19 [/ matemática]

[matemáticas] => [/ matemáticas] [matemáticas] 10 ^ {100} [/ matemáticas] [matemáticas] = [/ matemáticas] [matemáticas] 10 ^ {10} * 10 ^ {90} [/ matemáticas] [matemáticas] \ equiv [/ matemática] [matemática] 1 * 10 ^ {10} [/ matemática] [matemática] mod [/ matemática] [matemática] 19 [/ matemática]

[matemática] => [/ matemática] [matemática] 10 ^ {100} [/ matemática] [matemática] \ equiv [/ matemática] [matemática] 100 ^ 5 \ equiv 5 ^ 5 [/ matemática] [matemática] mod [ / matemáticas] [matemáticas] 19 [/ matemáticas]

[matemática] ([/ matemática] como [matemática] 100 [/ matemática] [matemática] mod [/ matemática] [matemática] 19 [/ matemática] [matemática] = [/ matemática] [matemática] 5 [/ matemática] [ matemáticas]) [/ matemáticas]

[matemática] => [/ matemática] [matemática] 10 ^ {100} [/ matemática] [matemática] \ equiv [/ matemática] [matemática] 25 * 25 * 5 [/ matemática] [matemática] mod [/ matemática] [matemáticas] 19 [/ matemáticas]

[matemáticas] => [/ matemáticas] [matemáticas] 10 ^ {100} [/ matemáticas] [matemáticas] \ equiv [/ matemáticas] [matemáticas] 6 * 6 * 5 [/ matemáticas] [matemáticas] mod [/ matemáticas] [matemáticas] 19 [/ matemáticas]

[matemática] ([/ matemática] como [matemática] 25 [/ matemática] [matemática] mod [/ matemática] [matemática] 19 [/ matemática] [matemática] = [/ matemática] [matemática] 6 [/ matemática] [ matemáticas]) [/ matemáticas]

[matemática] => [/ matemática] [matemática] 10 ^ {100} [/ matemática] [matemática] \ equiv [/ matemática] [matemática] 11 * 6 [/ matemática] [matemática] \ equiv [/ matemática] [ matemáticas] 66 [/ matemáticas] [matemáticas] \ equiv [/ matemáticas] [matemáticas] 9 [/ matemáticas] [matemáticas] mod [/ matemáticas] [matemáticas] 19 [/ matemáticas]

Entonces la respuesta es [matemáticas] 9 [/ matemáticas]

usando [matemáticas] 10 ^ {18} \ equiv 1 \ mod 19 [/ matemáticas]

[matemáticas] 10 ^ {100} = 10 ^ {18 \ veces 5 + 10} \ equiv 10 ^ {10} \ equiv 100 ^ 5 \ equiv 5 ^ 5 \ equiv 25 \ veces 25 \ veces 5 \ equiv 6 \ veces 6 \ por 5 \ equiv 36 \ por 5 \ equiv (-2) \ por 5 \ equiv 9 \ mod 19 [/ matemática]