5.5: División en\(\mathbb{Z}_{b}\)

¡El siguiente resultado es un cambio de juego! Nos dice que hay un elemento único\(a^{-1}\) tal que\(aa^{-1} = _{b} 1\) si y sólo si\(a\) está en el conjunto reducido de residuos (módulo\(b\)). Por lo tanto, la división está bien definida en el módulo de conjunto reducido de residuos\(b\). Esto sirve como una señal clara para enfatizar dos estructuras algebraicas distintas. Un anillo es una estructura con suma y su resta inversa más multiplicación, pero donde la multiplicación puede no tener una inversa. Un campo es casi lo mismo, pero ahora la multiplicación siempre tiene una inversa: la división. Una descripción más detallada de estas construcciones algebraicas se da en la Sección?? . Los números\(1\) y\(-1\) están siempre en el conjunto reducido de residuos módulo\(b\). Este conjunto a veces se llama el conjunto de unidades (ver Definición?? ) de\(\mathbb{Z}_{b}\).

Proposición 5.16

Dejar\(\mathbb{R}\) ser un conjunto reducido de residuos módulo\(b\). Entonces

1. para cada\(a \in \mathbb{R}\), hay un único\(a'\) en\(\mathbb{R}\) tal que\(a′a = _{b} aa′ = _{b} 1\)
2. para cada\(a \notin \mathbb{R}\), no existe\(x \in \mathbb{Z}_{b}\) tal que\(ax = _{b} 1\)
3. vamos\(\mathbb{R} = \{x_{i}\}_{i=1}^{\varphi (b)}\), entonces también\(\mathbb{R} = \{x-1\} _{i=1}^{\varphi (b)}\).

Prueba

Declaración 1: La existencia de una solución se desprende inmediatamente del Lema de Be ́zout, es decir,\(a′ = _{b} x\) resuelve for\(x\) in\(ax+by = 1\). Esta solución debe estar en\(\mathbb{R}\), porque\(a\), a su vez, es la solución de\(a′x + by = 1\) y así lo implica Lemma de Be ́zout\(\gcd (a',b) = 1\). Supongamos que tenemos dos soluciones\(ax = _{b} 1\) y\(ay = _{b} 1\), entonces la singularidad se desprende de aplicar el Teorema de cancelación 2.7 a la diferencia de estas ecuaciones.

Declaración 2: Por hipótesis,\(\gcd (a,b) > 1\). Tenemos que\(ax = _{b} 1\) es equivalente a\(ax+by = 1\), lo que contradice el Lema de Be ́zout.

Declaración 3: Esto es similar al Lema 5.3. Por (1), sabemos que todos los inversos están adentro\(R\). Entonces, si la declaración es falsa, debe haber dos elementos de\(R\). Entonces, si la sentencia es falsa, debe haber dos elementos de\(R\) con la misma inversa:\(ax = _{b} cx\). Esto es imposible por cancelación.

Lema 5.17

\(p\)Déjese ser prime. Entonces\(a^2 = _{p} 1\) si y solo si\(a = _{p} \pm 1\)

Prueba

Tenemos

\[a^2 = _{p} 1 \Leftrightarrow a^{2}-1 = _{p} (a+1)(a-1) = _{p} 0 \Leftrightarrow p | (a+1)(a-1) \nonumber\]

Porque\(p\) es primo, Corolario 2.12 dice que o bien\(p | a+1\) (y así\(a = _{p} -1\)) o\(p | a-1\) (y así\(a = _{p} +1\)).

Quizás, sorprendentemente, este último lema es falso si no\(p\) es primo. Por ejemplo,\(4^2 = _{15} 1\), pero\(4 \ne _{15} \pm 1\).

Teorema 5.18 (Teorema de Wilson)

Si\(p\) prime en\(\mathbb{Z}\), entonces\((p-1)! = _{p} -1\). Si\(b\) es compuesto, entonces\((b-1)! \ne _{b} -1\)

Prueba

Esto es cierto para\(p = 2\). Si\(p > 2\), entonces la Proposición 5.16 (3) y Lema 5.17 implican que cada factor\(a_{i}\) en el producto\((p-1)!\) distinto\(-1\) o\(1\) tiene un inverso único\(a_{i}'\) diferente de sí mismo. Los factores\(a_{i}'\) atraviesan todos los factores\(2\)\(p-2\) exactamente una vez. Así, en el producto, podemos emparejar cada uno\(a_{i}\) diferente de\(\pm 1\) con su inverso. Esto da

\[(p-1)! = _{p} (+1)(-1) \prod a_{i}a_{i}' = _{p} -1 \nonumber\]

La segunda parte es más fácil. Si\(b\) es compuesto, hay menos residuos\(a\) y\(b\) mayores\(1\) que eso\(ad = _{b} 0\). Ahora o bien podemos elegir\(a\) y\(b\) distinto y luego\((b-1)!\) contiene el producto\(ad\), y así equivale a cero mod\(b\). O de lo contrario esto es impssible y\(b = a^2\). Pero entonces aún\(\gcd ((b-1)!, b) \ge a\). Por Be ́zout, debemos tener\((b-1)!\) mod\(b\) debe ser un múltiplo de\(a\).

El teorema de Wilson podría ser utilizado para probar la primalidad de un número\(n\). No obstante, esto lleva\(n\) multiplicaciones, que en la práctica es más caro que tratar de dividir\(n\) por todos los números menos que\(\sqrt{n}\). Tenga en cuenta, sin embargo, que si desea calcular una lista de todos los primos entre\(1\) y\(N\), el teorema de Wilson se puede utilizar de manera mucho más eficiente. Después de calcular\((k-1)! = _{k}\) para determinar si\(k\) es primo, solo se necesita\(1\) multiplicación y\(1\) división para determinar si\(k+1\) es primo.

Aquí está la comida para llevar que será importante para Capítulo?? . Más en particular, tenemos el siguiente resultado.

Corolario 5.19

\(p\)Déjese ser prime.

Por cada uno\(a \in \mathbb{Z}_{p}\) hay un único\(a′ = _{p} -a\) tal que\(a+a′ = _{p} 0\).

Para cada\(a \in \mathbb{Z}_{p}\) y\(a \ne 0\), hay un único\(a′ = a^{-1}\) para que\(aa′ = _{p} 1\).

La suma y la multiplicación están bien definidas en\(\mathbb{Z}_{b}\) (ver ejercicios 5.1 y 5.2). Así, cuando\(p\) es primo, podemos sumar, multiplicar, restar y dividirnos\(\mathbb{Z}_{p}\). En palabras de Capítulo?? , cuando\(p\) es un primo, entonces\(\mathbb{Z}_{p}\) es un campo. Es un dato interesante que lo mismo no es cierto para un número compuesto\(b\). Según la Proposición 5.16, necesitamos el conjunto reducido de residuos para que la multiplicación sea invertible. Al mismo tiempo, para que el conjunto se cierre bajo multiplicación, necesitamos de todo\(\mathbb{Z}_{b}\) (piense en\(1+1+\dots\)). De esta manera las operaciones de suma y multiplicación en\(\mathbb{Z}_{b}\) colaborar entre sí sólo si\(b\) es un prime.