¿Qué es 3 ^ 9999 mod 10,000?

Answer 1

Observe que [matemáticas] 9999 = 10000–1 [/ matemáticas]. Esto debería jugar algún papel.

[matemáticas] 10000 = 2 ^ 4 \ veces 5 ^ 4. [/ matemáticas]

[matemáticas] \ phi (2 ^ 4) = 2 ^ 3 [/ matemáticas], [matemáticas] \ phi (5 ^ 4) = 5 ^ 3 \ veces 4 [/ matemáticas], donde [matemáticas] \ phi [/ matemáticas ] es la función totient de Euler. Según el teorema de Euler, [matemáticas] 3 ^ {\ phi (2 ^ 4)} = 1 [/ matemáticas] (mod [matemáticas] 2 ^ 4 [/ matemáticas]), y [matemáticas] 3 ^ {\ phi (5 ^ 4)} = 1 [/ matemáticas] (mod 5 [matemáticas] ^ 4 [/ matemáticas]).

Dado que [matemáticas] 2 ^ 3 [/ matemáticas] y [matemáticas] 5 ^ 3 \ por 4 [/ matemáticas] divide [matemáticas] 10000, [/ matemáticas] tenemos [matemáticas] 3 ^ {10000} = 1 [/ matemática] (mod [matemática] 2 ^ 4 [/ matemática]) y [matemática] 3 ^ {10000} = 1 [/ matemática] (mod 5 [matemática] ^ 4 [/ matemática]). Como resultado, [matemática] 3 ^ {10000} = 1 [/ matemática] (mod [matemática] 10000 [/ matemática]).

Deje [math] x = 3 ^ {9999} [/ math] (mod [math] 10000 [/ math]). Entonces [math] x [/ math] es un número natural menor que [math] 10000 [/ math], de ahí que [math] 3x <30000. [/ Math] Además, obtuvimos [math] 3x = 1 [/ math] (mod [matemática] 10000 [/ matemática]). Dado que [matemática] 1 [/ matemática] y [matemática] 10001 [/ matemática] no son múltiplos de [matemática] 3 [/ matemática], la única solución es [matemática] x = 20001/3 = 6667. [/ Matemática]

Answer 2

¿Qué es 3 ^ 9999 mod 10,000?

Puede encontrar R [matemáticas] \ left (\ frac {3 ^ {9999}} {10000} \ right) [/ math] usando aritmética modular, pero eso es muy largo y propenso a errores.

Si está utilizando Windows, puede encontrar el resto utilizando la calculadora de Microsoft en modo científico utilizando las teclas [math] x ^ y [/ math] y Mod.

Simplemente ingrese:

[matemáticas] 3x ^ y9999 [/ matemáticas] Mod [matemáticas] 10000 = 6667 [/ matemáticas]

El resto es 6667.

Answer 3

[matemáticas] \ phi (10000) = 4000. [/ matemáticas]

[math] \ Rightarrow \ qquad 3 ^ {9999} \ pmod {10000} = 3 ^ {8000 + 1999} \ pmod {10000} = 3 ^ {1999} \ pmod {10000}. [/ math]

[matemáticas] 1999 = 133 \ veces 15 + 4. [/ matemáticas]

[matemáticas] 3 ^ {15} \ pmod {10000} = 14348907 \ pmod {10000} = -1093. [/ matemáticas]

[matemáticas] \ Rightarrow \ qquad 3 ^ {1999} \ pmod {10000} = 3 ^ {133 \ times 15 + 4} \ pmod {10000} = (3 ^ {15}) ^ {133} .3 ^ 3) \ pmod {10000} [/ matemáticas]

[matemáticas] = (-1093) ^ {133} \ veces 81 \ pmod {10000}. [/ matemáticas]

[matemáticas] (- 1093) ^ {2} \ pmod {10000} = 4649. [/ matemáticas]

[math] \ Rightarrow \ qquad (-1093) ^ {4} \ pmod {10000} = (4649) ^ {2} \ pmod {10000} = 3201. [/ math]

[math] \ Rightarrow \ qquad (-1093) ^ {8} \ pmod {10000} = (3201) ^ {2} \ pmod {10000} = 6401. [/ math]

[matemática] \ Rightarrow \ qquad (-1093) ^ {16} \ pmod {10000} = (6401) ^ {2} \ pmod {10000} = 2801. [/ math]

[matemática] \ Rightarrow \ qquad (-1093) ^ {32} \ pmod {10000} = (2801) ^ {2} \ pmod {10000} = 5601. [/ math]

[math] \ Rightarrow \ qquad (-1093) ^ {64} \ pmod {10000} = (5601) ^ {2} \ pmod {10000} = 1201. [/ math]

[math] \ Rightarrow \ qquad (-1093) ^ {128} \ pmod {10000} = (1201) ^ {2} \ pmod {10000} = 2401. [/ math]

[matemáticas] \ Rightarrow \ qquad (-1093) ^ {133} \ veces 81 \ pmod {10000} = (-1093) ^ {128 + 4 + 1} \ veces 81 \ pmod {10000} [/ matemáticas]

[matemáticas] = (-1093) ^ {128} \ veces (-1093) ^ 4 \ veces (-1093) ^ 1 \ veces 81 \ pmod {10000} [/ matemáticas]

[matemáticas] = (2401 \ veces 3201) \ veces (-1093 \ veces 81) \ pmod {10000} [/ matemáticas]

[matemáticas] = (7685601) \ veces (-88533) \ pmod {10000} [/ matemáticas]

[matemáticas] = (5601) \ veces (1467) \ pmod {10000} [/ matemáticas]

[matemáticas] = 8216667 \ pmod {10000} = 6667. [/ matemáticas]

[matemáticas] \ Rightarrow \ qquad 3 ^ {9999} \ pmod {10000} = 6667. [/ matemáticas]