1 votos

Congruencia aritmética modular de restos como $98765 ^ {54321} \bmod 7$

Estoy tratando de averiguar cómo encontrar el resto de los números grandes que no están en mod 10 haciendo diferentes ejemplos.

Algo en lo que estoy trabajando es $98765 ^ {54321}$ (mod 7).

¿Puede alguien ayudarme a encontrar una forma general de hacer este tipo de problemas?

1voto

Master Shuriken Puntos 48

Hay varios métodos que se pueden aplicar para intentar resolver problemas de este tipo:

$x \equiv n^a$ (mod $m$ )

  1. En primer lugar, se puede tratar de encontrar el menor positivo $y \equiv n$ (mod $m$ ), y sustituir $n$ con $y$ en la congruencia original. Nótese que a veces es útil sustituirlo por $y-m$ en lugar de $y$ si $|y-m|<y$ .

Por ejemplo, si $x \equiv 11^a$ (mod 4), entonces se puede sustituir el 11 por -1 o 3, como $11 \equiv 3 \equiv -1$ (mod 4).

En este caso, probablemente sería más útil utilizar -1, ya que su valor absoluto es menor que 3, y por tanto es más fácil tomar potencias de -1 que de 3.

$x \equiv 11^a \equiv (3(4)-1)^a \equiv (3(0)-1)^a \equiv -1^a$ (mod 4)

Así que usando este método, ahora tienes:

$x \equiv y^a$ (mod $m$ ), donde $y$ es un número relativamente pequeño.

Si $a$ es grande, y el número del que se toman las potencias no es 1 o -1, entonces hay 2 métodos que se suelen utilizar para anular la congruencia:

  1. Si $m$ es un primo, $p$ Entonces puedes usar el pequeño teorema de Fermat para simplificar la congruencia:

    $a^p \equiv a$ (mod $p$ )

    o más útil:

    $a^{p-1} \equiv 1$ (mod $p$ ) si $a$ no es divisible por $p$ .

https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

Por ejemplo, si $x \equiv 3^{1000}$ (mod 7), entonces usando el pequeño teorema de Fermat, sabes que: $3^6 \equiv 1$ (mod 7).

Entonces puedes reescribir la congruencia como $x \equiv 3^{6(166) + 4}\equiv {(3^{6})}^{166} \times 3^4 \equiv {1}^{166} \times 3^4 \equiv 3^4$ (mod 7).

Esto a menudo puede permitirle simplificar la congruencia a algo que pueda calcular.

  1. Por otro lado, si el pequeño teorema de Fermat no ayuda (o no te ayuda a simplificarlo a números pequeños y manejables), entonces prueba a tomar potencias de $y$ (mod $m$ ), y ver si estos resultan en números pequeños.

Por ejemplo, si $x \equiv 5^{101}$ (mod 12), entonces no se puede utilizar el pequeño teorema de Fermat ya que 6 no es primo.

Sin embargo, observe que $5^2 \equiv 1$ (mod 12).

Por lo tanto: $x \equiv 5^{2(50) + 1} \equiv (5^2)^{50} \times 5^1 \equiv 1^{50} \times 5 \equiv 5$ (mod 12).

Espero que esto ayude.

0voto

Browning Puntos 309

Primero reduce la base mod 7. Como $98765\equiv 2\mod 7$ queremos encontrar $$2^{54321}\mod 7$$

Como 2 y 54321 son relativamente primos, utilizando el teorema de Euler, podemos reducir 54321 mod $\phi(7)$ . Desde $54321 \equiv 3 \mod 6$ queremos encontrar $$2^3 \mod 7$$

La respuesta en este caso es 1.

i-Ciencias.com

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.

Powered by:

X