Hay varios métodos que se pueden aplicar para intentar resolver problemas de este tipo:
$x \equiv n^a$ (mod $m$ )
- 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:
-
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.
- 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.