Gaussianos

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.

2 comentarios

Trackback para este post

1. 

   fede - 31 de Octubre de 2006 17:05

   neok
   acabo de descubrir que está disponible en la red, en castellano, la maravillosa primera obra del patrón de los Gaussianos, “Disquisitiones Arithmeticae”.
   En alguna parte leí que Sophie Germain dormía con ella debajo de la almohada.
   En I.2 aparece por primera vez en la historia el símbolo de congruencia.
   Seguramente ya lo sabías, pero se lo tenía que contar a alguien…

2. 

   neok - 31 de Octubre de 2006 21:22

   ¡Oh! Muy bueno ese enlace, muchas gracias.