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 2n-1 ≡ 1 (mod (n))

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

n primo => 2n-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,

ap-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:
    ap-1 ≡ 1 (mod (p)) => a·ap-2 ≡ 1 (mod (p))
    a·a-1 ≡ 1 (mod (p))

    Entonces podemos ver por igualdad que:
    a-1 = ap-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.

Print Friendly, PDF & Email