Teoría de números elemental: Aritmética modular II

Vamos a terminar ya con la teoría de números elemental, que se me está haciendo demasiado larga.

Números pseudoprimos

Los matemáticos Chinos de la antigüedad creían que:

n primo 2^n-1 ≡ 1 (mod (n))

Sin embargo se equivocaron y su condición sólo es válida en un sentido:

n primo => 2^n-1 ≡ 1 (mod (n))

A los números que sin ser primos, cumplen la propiedad se les conoce como pseudoprimos.

Teorema pequeño de Fermat

Sea “p” primo y a ∈ Z no divisible por “p”. Entonces,

a^p-1 ≡ 1 (mod (p))

Como podéis ver no es más que una mejora de la propiedad de los números pseudoprimos.

(Más información en Wikipedia)

Congruencias lineales

Ahora vamos a pasar a trabajar de verdad con las congruencias, y es que nos disponemos a resolver ecuaciones con congruencias.

Queremos resolver “a·x + b ≡ c (mod (m))” donde a, b, c ∈ Z y m ∈ N (m>1) y todos son datos. Resolver esta ecuación es lo mismo que resolver “a·x ≡ c – b (mod (m))”, por tanto es lo mismo que resolver “a·x ≡ d (mod (m))” (siendo d = c – b).

• Dado a ∈ Z, a ≠ 0. Se dice que a^-1 ∈ Z es un inverso de “a mod (m), si a·a^-1 ≡ 1 (mod (m))
• Si existe a^-1, entonces cualquier elemento de la clase de equivalencia de a^-1 es un inverso de “a”. Por tanto, en caso de existir inverso, existen infinitos inversos de “a” que difieren entre sí en múltiplos de “m”.
• Sabemos que si MCD (a, m) = 1, entonces existen inversas de “a (mod (m))”. Para resolver “a·x ≡ d (mod (m)), siendo “a^-1” un inverso de “a (mod (m))”. Entonces:
  a·a^-1·x ≡ d (mod (m))
  a·a^-1 ≡ 1 (mod (m)) => a·a^-1·x ≡ x (mod (m))
  Por tanto, la solución a la ecuación “a·x ≡ d (mod (m))” es:
  x ≡ a^-1·d (mod (m))

Supongo que ahora la pregunta que surge es: ¿Cómo calculamos a^-1?

Pues hay unos cuantos trucos:

• Usando el teorema pequeño de Fermat:
  a^p-1 ≡ 1 (mod (p)) => a·a^p-2 ≡ 1 (mod (p))
  a·a^-1 ≡ 1 (mod (p))
  Entonces podemos ver por igualdad que:
  a^-1 = a^p-2
  Lo malo de este método es que solo vale con ecuaciones que cumplen las condiciones del teorema pequeño de Fermat.
• Usando el indicador de euler:
  Se puede demostrar que a^Φ(n) ≡ 1 (mod (n)), siendo Φ(n) el indicador de euler del número “n”, y que se calcula como viene explicado en el enlace anterior. Y viendo la ecuación anterior, podemos deducir fácilmente:
  a^Φ(n) ≡ 1 (mod (n)) [Sacando factor común de “a”] => a·a^{Φ(n) – 1} ≡ 1 (mod (n))
  a·a^-1 ≡ 1 (mod (n))
  Por tanto, como antes, por igualdad tenemos que:
  a^-1 = a^{Φ(n) – 1} (mod (n))
  Como podéis apreciar este método es mejor que el anterior al no tener ninguna condición referente a la ecuación.

Bueno, existe un tercer método basado en el teorema de la división euclídea pero me parece muy largo de explicar. Así que con esto me despido, y dejo la teoría de números elemental (casi, falta el teorema chino del resto) terminada.