5.2: Método de Euler

Definición 5.2

Un conjunto completo de residuos\(C\) módulo\(b\) es un conjunto de\(b\) enteros en\(\mathbb{Z}\), tal\(C\) tiene exactamente un entero en cada clase de congruencia (módulo\(b\)).

Un conjunto reducido de residuos\(R\) módulo\(b\) es un conjunto de\(\varphi (b)\) enteros en\(\mathbb{Z}\), tal\(R\) tiene exactamente un entero en cada clase congruente a\(p \in \{1, \cdots b-1\}\) (módulo\(b\)) tal que\(p\) es relativamente primo a\(b\).

Lema 5.3

Supongamos\(\gcd (a,b) = 1\). Si los números\(\{x_{i}\}\) forman un conjunto completo de residuos módulo\(b\) (un conjunto reducido de residuos módulo\(b\)), entonces\(\{ax_{i}\}\) es un conjunto completo de residuos módulo\(b\) (conjunto\(a\) reducido de residuos módulo\(b\)).

Prueba

Dejar\(\{x_{i}\}\) ser un conjunto completo de residuos módulo\(b\). Entonces los\(b\) números\(\{ax_{i}\}\) forman conjunto completo de residuos a menos que dos de ellos sean congruentes. Pero eso es imposible por el Teorema 2.7.

Dejar\(\{x_{i}\}\) ser un conjunto reducido de residuos módulo\(b\). Entonces, como antes, no hay dos de los\(\varphi (b)\) números\(\{ax_{i}\}\) congruentes módulo\(b\). Además, Lema 2.18 implica que si\(\gcd (a,b) = 1\) y\(\gcd (x_{i}, b) = 1\), entonces\(\gcd (ax_{i}, b) = 1\). Por lo tanto, el conjunto\(\{ax_{i}\}\) es un conjunto reducido de residuos módulo\(b\).

Teorema 5.4 (Euler)

Dejar\(a\) y\(b\) mayor que\(0\) y\(\gcd(a, b) = 1\). Entonces\(a^{\varphi (b)} = _{b} 1\), donde\(\varphi\) denota la función phi o totiente de Euler (Definición 4.9).

Prueba

Dejar\(\{x_{i}\}_{i=1}^{\varphi(b)}\) ser un conjunto reducido de módulos de residuos\(b\). Entonces por Lemma 5.3,\(\{ax_{i}\}_{i=1}^{\varphi(b)}\) ser un conjunto reducido de módulo de residuos\(b\). Porque la multiplicación es conmutativa, tenemos

\[\prod_{i=1}^{\varphi (b)} x_{i} = b \prod_{i=1}^{\varphi (b)} ax_{i} = _{b} a^{\varphi(b)} \prod_{i=1}^{\varphi (b)} x_{i} \nonumber\]

Ya que\(\gcd (x_{i}, a) = 1\), Lema 2.18 implica eso\(\gcd (\prod_{i=1}^{\varphi (b)} x_{i}, a) = 1\). El teorema de cancelación aplicado a la igualdad entre el primer y tercer término prueba el resultado.

El teorema de Euler dice que\(\varphi (b)\) es un múltiplo de\(\mbox{Ord}_{b}^{\times} (a)\). Pero no dice qué múltiplo. De hecho, en la práctica, esa cuestión es difícil de decidir. Es de importancia teórica decidir cuándo los dos son iguales.

Definición 5.5

Dejar\(a\) y intgers\(b\) positivos con\(\gcd (a,b) = 1\). Si\(\mbox{Ord}_{b}^{\times} a = \varphi (b)\), entonces\(a\) se llama una raíz primitiva de\(b\) (o un módulo raíz primitiva\(b\)).

Por ejemplo, el entero más pequeño\(k\) para el que\(3^k = _{7} 1\) es\(6\). Ya que\(\varphi (7) = 6\), vemos que\(3\) es raíz primitiva de\(7\). Dado que la multiplicación está bien definida en\(\mathbb{Z}_{7}\), se deduce que\((3+7k)^{6} = _{7} 3^{6} = _{7} 1\). Así,\(\{\cdots, -4, 3, 10, \cdots \}\) son todas las raíces primitivas de\(7\). La única otra raíz primitiva no congruente de\(7\) es\(5\). No todos los números tienen raíces primitivas. Por ejemplo, no\(8\) tiene ninguno.

Esto tiene interesante conexión con la aritmética del día a día, es decir, la expresión de números racionales en base\(10\).

Proposición 5.6

Dejar\(a\) y\(n\) mayor que\(0\) y\(\gcd (a,n) = \gcd (10,n) = 1\). La expansión decimal de\(\frac{a}{n}\) es no terminante y eventualmente periódica con un punto\(p\), donde\((1) p = \mbox{Ord}_{n}^{\times} (10)\) y\((2) p | \varphi (n)\).

Prueba

La prueba procede excusando una división larga, cada paso de la cual utiliza el algoritmo de división, Comience reduciendo\(a\) módulo\(n\) y llame al resultado\(r_{0}\).

\[a = n q_{0}+r_{0} \nonumber\]

donde\(r_{0} \in \{0, \cdots, n-1\}\). Lema 3.1 implica eso\(\gcd (a,n) = \gcd (r_{0}, n) = 1\). Entonces en particular,\(r_{0} \ne 0\). La parte entera de\(\frac{a}{n}\) es\(q_{0}\). El siguiente paso de la división larga es:

\[10 r_{0} = nq_{1}+r_{1} \nonumber\]

donde otra vez elegimos\(r_{1} \in \{0, \cdots, n-1\}\).

Tenga en cuenta eso\(0 \le 10r_{0} < 10n\) y así\(q_{1} \in \{0,\cdots 9\}\). Ahora registramos el primer dígito “después del punto decimal” de la expansión decimal:\(q_{1}\). Por Lemma 3.1, tenemos\(\gcd (10r_{0}, n) = \gcd(r_{1}, n)\). A su vez, esto implica vía Lema 2.18 eso\(\gcd (r_{0}, n) = \gcd (r_{1}, n)\). Y otra vez, eso lo vemos\(r_{1} \ne 0\).

El proceso ahora se repite.

\[\underbrace{10(10r_{0}-nq_{1})}_{r_{1}} = nq_{2}+r_{2} \nonumber\]

y registramos el segundo dígito después del punto decimal,\(q_{2} \in \{0, \cdots 9\}\). Por el mismo razonamiento,\(\gcd (r_{2}, n) = 1\) y así\(r_{2} \ne 0\). Uno continúa y demuestra por inducción que\(\gcd (r_{i}, n) = 1\). En particular,\(r_{i} \ne 0\), por lo que la expansión no termina.

Dado que los restos\(r_{i}\) están en\(\{1, \cdots n-1\}\), la secuencia debe ser eventualmente periódica con periodo (menos positivo)\(p\). En ese punto, tenemos

\[10^{k+p}r_{0} = _{n} 10^{k}r_{0} \nonumber\]

Por Teorema 2.7, podemos cancelar los factores comunes\(10^k\) y\(r_{0}\), y lo obtenemos\(10^{p} = _{n} 1\). Dado que\(p\) es el menor número de este tipo (positivo), hemos probado parte (1). La parte (2) sigue directamente del Teorema de Euler.

Por supuesto, esta proposición se generaliza fácilmente a cálculos en cualquier otra base\(b\). A modo de ejemplo, mencionamos que si\(\gcd (a, n) = 1\) y\(b\) es una raíz primitiva de\(n\), entonces la expansión de\(\frac{a}{b}\) tiene periodo\(\varphi (n)\).

El siguiente resultado es una consecuencia inmediata del teorema de Euler. Se sigue fijando\(y = x+k \varphi (b)\). Tiene importantes aplicaciones en criptografía.

Corolario 5.7

Dejar\(a\) y\(b\) ser coprime con\(b \ge 0\). Si\(x = _{\varphi (b)} y\), entonces\(a^{x} = _{b} a^y\).