11.4: Los mayores divisores comunes y los enteros Modulo n

En esta sección se introduce la mayor operación común de divisor, y se introduce una importante familia de grupos concretos, los enteros módulo\(n\text{.}\)

Los mejores divisores comunes

Comenzamos con un teorema sobre la división entera que es intuitivamente claro. Dejamos la prueba como ejercicio.

Teorema \(\PageIndex{1}\): The Division Property for Integers

Si\(m, n\in \mathbb{Z}\text{,}\)\(n>0\text{,}\) entonces existen dos enteros únicos,\(q\) (el cociente) y\(r\) (el resto), tal que\(m = n q + r\) y\(0 \leq r < n\text{.}\)

Nota\(\PageIndex{1}\)

El inmueble de división dice que si\(m\) se divide por\(n\text{,}\) usted obtendrá un cociente y un resto, donde el resto es menor que\(n\text{.}\) Este es un hecho que la mayoría de los estudiantes de primaria aprenden cuando se les introduce a la división larga. Al hacer el problema de división\(1986 \div 97\text{,}\) se obtiene un cociente de 20 y un resto de 46. Este resultado podría ser escrito\(\frac{1986}{97}= 20+\frac{46}{97}\) o\(1986 = 97\cdot 20 + 46\text{.}\) La última forma es como normalmente se expresa la propiedad de división en matemáticas superiores.

Lista\(\PageIndex{1}\)

Ahora recordamos al lector alguna terminología intercambiable que se utiliza cuando\(r=0\text{,}\) i. e.,\(a = b q\text{.}\) Todos los siguientes dicen lo mismo, solo desde puntos de vista ligeramente diferentes.

divide

\(b\)divide\(a\)

múltiples

\(a\)es un múltiplo de\(b\)

factor

\(b\)es un factor de\(a\)

divisor

\(b\)es un divisor de\(a\)

Usamos la notación\(b \mid a\) si\(b\) divide\(a\text{.}\)

Por ejemplo\(2\mid 18\) y\(9\mid 18\), pero\(4\nmid 18\text{.}\)

Precaución: No confunda el símbolo de “divide” con el símbolo “dividido por”. El primero es vertical mientras que el segundo está inclinado. Observe sin embargo que la afirmación\(2 \mid 18\) está relacionada con el hecho de que\(18/2\) es un número entero.

Definición \(\PageIndex{1}\): Greatest Common Divisor

Dados dos enteros,\(a\) y\(b\text{,}\) no ambos cero, el mayor divisor común de\(a\) y\(b\) es el entero positivo\(g=\gcd(a,b)\) tal que\(g \mid a\text{,}\)\(g\mid b\text{,}\) y

\ start {ecuación*} c\ mediados a\ textrm {y} c\ mid b\ Rightarrow c\ mid g\ end {ecuación*}

Una forma un poco más sencilla de pensar\(\gcd(a,b)\) es como el entero positivo más grande que es un divisor de ambos\(a\) y\(b\text{.}\) Sin embargo, nuestra definición es más fácil de aplicar al probar propiedades de los mayores divisores comunes.

Para números pequeños, una forma sencilla de determinar el divisor más común es usar la factorización. Por ejemplo, si queremos el mayor divisor común de 660 y 350, puedes factorizar los dos enteros:\(660=2^2\cdot 3\cdot 5\cdot 11\) y Los factores\(350 = 2 \cdot 5^2\cdot 7\text{.}\) individuales de 2 y 5 son los únicos que aparecen en ambas factorizaciones, por lo que el divisor más común es\(2\cdot 5 =10\text{.}\)

Algunos pares de números enteros no tienen divisores comunes que no sean 1. Tales pares se llaman pares relativamente primos.

Definición\(\PageIndex{2}\): Relatively Prime

Un par de números enteros,\(a\) y\(b\text{,}\) son relativamente primos si\(\gcd(a, b)=1\)

Por ejemplo,\(128=2^7\) y\(135=3^3\cdot 5\) son relativamente primos. Observe que ni 128 ni 135 son primos. En general,\(a\) y no es\(b\) necesario ser prime para ser relativamente prime. No obstante, si comienzas con un prime, como 23, por ejemplo, será relativamente primo para todo menos sus múltiplos. Este teorema, que posteriormente probamos generaliza esta observación.

Teorema\(\PageIndex{2}\)

Si\(p\) es un primo y\(a\) es cualquier entero tal que\(p\nmid a\) entonces\(\gcd(a, p) = 1\)

Algoritmo euclidiano

Ya en la época de Euclides se sabía que la factorización no era la mejor manera de calcular los mayores divisores comunes.

El Algoritmo Euclidiana se basa en las siguientes propiedades del divisor más común.

\[\label{eq:1}\gcd(a,0)=a\text{ for }a\neq 0\]

\[\label{eq:2}\gcd(a,b)=\gcd(b,r)\text{ if }b\neq 0\text{ and }a=bq+r\]

Para computar\(\gcd(a,b)\text{,}\) nos\(b\) dividimos en\(a\) y obtenemos un resto\(r\) tal que\(0\leq r <\lvert b\rvert \text{.}\) Por la propiedad anterior,\(\gcd(a, b)= \gcd(b, r)\text{.}\) Repetimos el proceso hasta que obtengamos cero para un resto. El último número distinto de cero que es la segunda entrada en nuestros pares es el mayor divisor común. Esto es inevitable porque el segundo número de cada par es menor que el anterior. En la tabla se\(\PageIndex{1}\) muestra un ejemplo de cómo se puede realizar sistemáticamente este cálculo.

Tabla\(\PageIndex{1}\): Una tabla para calcular\(\gcd(99,53)\)

\(q\)	\(a\)	\(b\)
\ (q\) ">-	\ (a\) ">\(99\)	\ (b\) ">\(53\)
\ (q\) ">\(1\)	\ (a\) ">\(53\)	\ (b\) ">\(46\)
\ (q\) ">\(1\)	\ (a\) ">\(46\)	\ (b\) ">\(7\)
\ (q\) ">\(6\)	\ (a\) ">\(7\)	\ (b\) ">\(4\)
\ (q\) ">\(1\)	\ (a\) ">\(4\)	\ (b\) ">\(3\)
\ (q\) ">\(1\)	\ (a\) ">\(3\)	\ (b\) ">\(1\)
\ (q\) ">\(3\)	\ (a\) ">\(1\)	\ (b\) ">\(0\)

Aquí hay un cálculo de Sage para verificar que\(\gcd(99, 53) = 1\text{.}\) En cada línea, el valor de\(a\) se divide por el valor de\(b\text{.}\) El cociente se coloca en la siguiente línea junto con el nuevo valor del\(a\text{,}\) cual es el anterior\(b\text{;}\) y el resto, que es el nuevo valor de\(b\text{.}\) Recordemos que en Sage, a%b es el resto al dividir b en a.

a=99
b=53
while b>0:
    print('computing gcd of '+str(a)+' and '+str(b))
    [a,b]=[b,a%b]
print('result is '+str(a))

Investigación\(\PageIndex{1}\)

Si se te permitiera escoger dos números menos de 100, ¿cuál elegirías para obligar a Euclides a trabajar más duro? Aquí hay una pista: El tamaño del cociente en cada paso determina qué tan rápido disminuyen los números.

Solución

Si el cociente en división es 1, entonces obtenemos la finalización más lenta posible. Si\(a = b + r\text{,}\) entonces se trabaja hacia atrás, cada resto sería la suma de los dos restos anteriores. Esto describió una secuencia como la secuencia de Fibonacci y de hecho, el mayor divisor común de dos números consecutivos de Fibonacci dará los mayores pasos para alcanzar un valor final de 1.

Para valores fijos de\(a\) y\(b\text{,}\) considerar enteros de la forma\(a x+b y\) donde\(x\) y\(y\) puede ser cualquiera de dos enteros. Por ejemplo si\(a\) = 36 y\(b\) = 27, algunos de estos resultados se tabulan a continuación con\(x\) valores a lo largo de la columna izquierda y\(y\) los valores en la parte superior.

Figura\(\PageIndex{1}\): Combinaciones lineales de\(36\) y\(27\)

¿Notaste algún patrón? ¿Cuál es el valor positivo más pequeño que ve en esta tabla? ¿Cómo se conecta a 36 y 27?

Teorema\(\PageIndex{3}\)

Si\(a\) y\(b\) son enteros positivos, el valor positivo más pequeño de\(a x + b y\) es el divisor más común de\(a\) y\(b\text{,}\)\(\gcd(a,b)\text{.}\)

Prueba

Si\(g = \gcd(a, b)\text{,}\) desde\(g \mid a\) y\(g \mid b\text{,}\) sabemos que\(g \mid (a x + b y)\) para cualquier enteros\(x\) y\(y\text{,}\) así no\(a x + b y\) puede ser menor que\(g\text{.}\) Para demostrar que\(g\) es exactamente el valor menos positivo, mostramos que se\(g\) puede lograr extendiendo el Algoritmo Euclideano. Realizar el algoritmo extendido implica construir una tabla de números. La forma en que se construye mantiene una invariante, y por El Teorema de la Relación Invariante, Teorema 17.1.2.1. podemos estar seguros de que los valores deseados de\(x\) y\(y\) se producen.

Para ilustrar el algoritmo, Tabla\(\PageIndex{2}\) muestra cómo calcular\(\gcd(152,53)\text{.}\) En la\(r\) columna, encontrarás 152 y 53, y luego los sucesivos restos de división. Entonces cada número en\(r\) después de los dos primeros es el resto después de dividir el número inmediatamente por encima de él en el siguiente número hacia arriba. A la izquierda de cada resto se encuentra el cociente de la división. En este caso la tercera fila de la tabla nos dice que\(152 = 53\cdot 2 + 46\text{.}\) El último valor distinto de cero en\(r\) es el mayor divisor común.

Tabla\(\PageIndex{2}\): El algoritmo euclidiano extendido para calcular\(\gcd(152,53)\)

\(q\)	\(r\)	\(s\)	\(t\)
\ (q\) ">—	\ (r\) ">\(152\)	\ (s\) ">\(1\)	\ (t\) ">\(0\)
\ (q\) ">—	\ (r\) ">\(53\)	\ (s\) ">\(0\)	\ (t\) ">\(1\)
\ (q\) ">\(2\)	\ (r\) ">\(46\)	\ (s\) ">\(1\)	\ (t\) ">\(-2\)
\ (q\) ">\(1\)	\ (r\) ">\(7\)	\ (s\) ">\(-1\)	\ (t\) ">\(3\)
\ (q\) ">\(6\)	\ (r\) ">\(4\)	\ (s\) ">\(7\)	\ (t\) ">\(-20\)
\ (q\) ">\(1\)	\ (r\) ">\(3\)	\ (s\) ">\(-8\)	\ (t\) ">\(23\)
\ (q\) ">\(1\)	\ (r\) ">\(1\)	\ (s\) ">\(15\)	\ (t\) ">\(-43\)
\ (q\) ">\(3\)	\ (r\) ">\(0\)	\ (s\) ">\(-53\)	\ (t\) ">\(152\)

Las columnas “\(s\)” y “\(t\)” son nuevas. Los valores de\(s\) y\(t\) en cada fila se mantienen de manera que\(152s + 53t\) sea igual al número en la\(r\) columna. Observe que

Tabla\(\PageIndex{3}\): Invariante en computación\(\gcd(152,53)\)

\(152 = 152\cdot 1+ 53\cdot 0\)

\(53 =152\cdot 0 + 53\cdot 1\)

\(46 = 152\cdot 1 + 53\cdot (-2)\)

\(\vdots\)

\(1 = 152\cdot 15 + 53\cdot (-43)\)

\(0 = 152 \cdot (-53) + 53\cdot 152\)

¡La siguiente a la última ecuación es lo que estamos buscando al final! El principal problema es identificar cómo determinar estos valores después de las dos primeras filas. Las dos primeras filas en estas columnas siempre serán las mismas. Veamos el caso general de la computación\(\gcd(a,b)\text{.}\) Si los\(t\) valores\(s\) y en filas\(i - 1\) y\(i - 2\) son correctos, tenemos

\ begin {ecuación*} (A)\ textrm {}\ left\ {\ begin {array} {c} a s_ {i-2} +b t_ {i-2} =r_ {i-2}\\ a s_ {i-1} +b t_ {i-1} =r_ {i-1}\\ end {array}\ derecho. \ end {ecuación*}

Además, sabemos que

\ begin {ecuación*} r_ {i-2} =r_ {i-1} q_i+r_i\ textrm {}\ Rightarrow\ textrm {} r_i=r_ {i-2} -r_ {i-1} q_i\ end {ecuación*}

Si sustituye las expresiones para\(r_{i-1}\) y\(r_{i-2}\) desde (A) en esta última ecuación y luego recoge los\(b\) términos\(a\) y por separado, obtiene

\ begin {ecuación*} r_i= a\ izquierda (s_ {i-2} - q_is_ {i-1}\ derecha) + b\ izquierda (t_ {i-2} - q_it_ {i-1}\ derecha)\ end {ecuación*}

o

\ begin {ecuación*} s_ {i} =s_ {i-2} - q_es_ {i-1}\ textrm {y} t_i= t_ {i-2} - q_it_ {i-1}\ final {ecuación*}

Mire de cerca las ecuaciones para\(r_i, s_i, \textrm{ and } t_i\text{.}\) Sus formas son todas iguales. Con un poco de práctica deberías ser capaz de calcular\(s\) y\(t\) valorar rápidamente.

Aritmética Modular

Te recordamos la relación sobre los enteros que llamamos Congruencia Modulo\(n\), Definición 6.3.7. Si dos números,\(a\) y\(b\text{,}\) difieren por un múltiplo de\(n\text{,}\) decimos que son congruentes módulo\(n\text{,}\) denotado\(a \equiv b\pmod{n}\text{.}\) Por ejemplo,\(13 \equiv 38\pmod{5}\) porque\(13-38 = -25\text{,}\) que es un múltiplo de 5.

Definición \(\PageIndex{3}\): Modular Addition

Si\(n\) es un entero positivo, definimos el módulo de suma\(n\)\(\left(+_n\right.\)) de la siguiente manera. Si\(a, b \in \mathbb{Z}\text{,}\)

\ begin {ecuación*} a +_n b =\ textrm {el resto después de} a + b\ textrm {se divide por} n\ end {ecuación*}

Definición \(\PageIndex{4}\): Modular Multiplication

Si\(n\) es un entero positivo, definimos módulo de multiplicación\(n\)\(\left(\times_n\right.\)) de la siguiente manera. Si\(a, b \in \mathbb{Z}\text{,}\)

\ begin {ecuación*} a\ times_n b =\ textrm {el resto después} a\ cdot b\ textrm {se divide por} n\ end {ecuación*}

Nota\(\PageIndex{2}\)

1. El resultado de hacer módulo aritmético\(n\) es siempre un entero entre 0 y\(n-1\text{,}\) por la propiedad de división. Esta observación implica que\(\{0, 1,\dots, n-1\}\) se cierra bajo módulo\(n\) aritmético.
2. Siempre es cierto que\(a +_n b \equiv (a + b) \pmod{n}\) y\(a\times_n b \equiv (a \cdot b) \pmod{n}\text{.}\) Por ejemplo,\(4 +_7 5 = 2 \equiv 9 \pmod{7}\) y\(4 \times_7 5 = 6 \equiv 20 \pmod{7}\text{.}\)
3. Usaremos la notación\(\mathbb{Z}_n\) para denotar el conjunto\(\{0, 1, 2,. . ., n-1\}\text{.}\)

Ejemplo\(\PageIndex{1}\): Some Examples

1. Todos estamos algo familiarizados\(\mathbb{Z}_{12}\) ya que las horas del día se cuentan utilizando este grupo, excepto por el hecho de que se usa 12 en lugar de 0. El tiempo militar usa el sistema mod 24 y comienza en 0. Si alguien inició un viaje de cuatro horas a la hora 21, la hora a la que llegaría es\(21 +_{24} 4 = 1\text{.}\) Si un satélite orbita la tierra cada cuatro horas e inicia su primera órbita a la hora 5, terminaría su primera órbita en el momento\(5 +_{24}4 =9\text{.}\) Su décima órbita terminaría a las\(5 +_{24} 10\times_{24}4 =21\) horas en el reloj
2. Prácticamente todas las computadoras representan enteros sin signo en forma binaria con un número fijo de dígitos. Una computadora muy pequeña podría reservar siete bits para almacenar el valor de un entero. Sólo hay\(2^7\) diferentes valores que se pueden almacenar en siete bits. Dado que el valor más pequeño es 0, representado como 0000000, el valor máximo se\(2^7 - 1 = 127\text{,}\) representará como 1111111. Cuando se da un comando para agregar dos valores enteros, y los dos valores tienen una suma de 128 o más, se produce desbordamiento. Por ejemplo, si tratamos de sumar 56 y 95, la suma es un entero binario de ocho dígitos 10010111. Un procedimiento común es retener los siete dígitos de menor orden. El resultado de sumar 56 y 95 sería la aritmética\(0010111_{\textrm{ two}} = 23 \equiv 56 + 95\pmod{128}\text{.}\) Entero con esta computadora en realidad sería aritmética de módulo 128.

Propiedades de la Aritmética Modular

Teorema\(\PageIndex{4}\)

Si\(a \in \mathbb{Z}_n\text{,}\)\(a\neq 0\text{,}\) entonces la inversa aditiva de a es\(n - a\text{.}\)

Prueba

\(a + (n - a) =n\equiv 0(\textrm{ mod } n)\text{,}\)ya que\(n = n\cdot 1 + 0\text{.}\) Por lo tanto,\(a+_n(n-a)=0\text{.}\)

\(n\)El módulo de adición es siempre conmutativo y asociativo; 0 es la identidad para\(+_n\) y cada elemento de\(\mathbb{Z}_n\) tiene una inversa aditiva. Estas propiedades se pueden resumir señalando que para cada uno\(n\geq 1\text{,}\)\(\left[\mathbb{Z}_n; +_n\right]\) es un grupo.

Definición \(\PageIndex{5}\): The Additive Group of Integers Modulo \(n\)

El Grupo Aditivo de Enteros Modulo\(n\) es el grupo con dominio\(\{0, 1, 2, \dots, n-1\}\) y con la operación de\(n\) adición mod. Se denota como\(\mathbb{Z}_n\text{.}\)

\(n\)El módulo de multiplicación es siempre conmutativo y asociativo, y 1 es la identidad para\(\times_n\text{.}\)

Observe que las propiedades algebraicas de\(+_n\) y\(\times_n\) on\(\mathbb{Z}_n\) son idénticas a las propiedades de adición y multiplicación en\(\mathbb{Z}\text{.}\)

Observe que no se puede formar un grupo a partir de todo el conjunto\(\{0, 1, 2, \dots, n-1\}\) con\(n\) multiplicación mod ya que cero nunca tiene un inverso multiplicativo. Dependiendo del valor de puede\(n\) haber otras restricciones. El siguiente grupo será explorado en Ejercicio\(\PageIndex{9}\).

Definición \(\PageIndex{6}\): The Multiplicative Group of Integers Modulo \(n\)

El Grupo Multiplicativo de Enteros Modulo\(n\) es el grupo con dominio\(\{k\in \mathbb{Z} \vert 1 \leq k \leq n-1 \textrm{ and }\gcd(n,k)=1\}\) y con la operación de\(n\) multiplicación mod. Se denota como\(\mathbb{U}_n\text{.}\)

Ejemplo\(\PageIndex{2}\): Some Operation Tables

Aquí hay ejemplos de mesas de operación para grupos modulares. Observe que aunque 8 es mayor que 5, los dos grupos\(\mathbb{U}_5\) y\(\mathbb{U}_8\) ambos tienen orden 4. En el caso de\(\mathbb{U}_5\text{,}\) dado que 5 es primo se incluyen todos los elementos distintos de\(\mathbb{Z}_5\) cero de. Como 8 no es primo no incluimos enteros que comparten un factor común con 8, los enteros pares en este caso.

Tabla\(\PageIndex{4}\): Mesa de operaciones para el grupo\(\mathbb{Z}_{5}\)

\(+_{5}\)	\(0\)	\(1\)	\(2\)	\(3\)	\(4\)
\ (+_ {5}\)” alcance="fila"> \(0\)	\ (0\) ">\(0\)	\ (1\) ">\(1\)	\ (2\) ">\(2\)	\ (3\) ">\(3\)	\ (4\) ">\(4\)
\ (+_ {5}\)” alcance="fila"> \(1\)	\ (0\) ">\(1\)	\ (1\) ">\(2\)	\ (2\) ">\(3\)	\ (3\) ">\(4\)	\ (4\) ">\(0\)
\ (+_ {5}\)” alcance="fila"> \(2\)	\ (0\) ">\(2\)	\ (1\) ">\(3\)	\ (2\) ">\(4\)	\ (3\) ">\(0\)	\ (4\) ">\(1\)
\ (+_ {5}\)” alcance="fila"> \(3\)	\ (0\) ">\(3\)	\ (1\) ">\(4\)	\ (2\) ">\(0\)	\ (3\) ">\(1\)	\ (4\) ">\(2\)
\ (+_ {5}\)” alcance="fila"> \(4\)	\ (0\) ">\(4\)	\ (1\) ">\(0\)	\ (2\) ">\(1\)	\ (3\) ">\(2\)	\ (4\) ">\ (3

Tabla\(\PageIndex{5}\): Mesa de operaciones para el grupo\(\mathbb{U}_{5}\)

\(\times_{5}\)	\(1\)	\(2\)	\(3\)	\(4\)
\ (\ times_ {5}\)” alcance="fila"> \(1\)	\ (1\) ">\(1\)	\ (2\) ">\(2\)	\ (3\) ">\(3\)	\ (4\) ">\(4\)
\ (\ times_ {5}\)” alcance="fila"> \(2\)	\ (1\) ">\(2\)	\ (2\) ">\(4\)	\ (3\) ">\(1\)	\ (4\) ">\(3\)
\ (\ times_ {5}\)” alcance="fila"> \(3\)	\ (1\) ">\(3\)	\ (2\) ">\(1\)	\ (3\) ">\(4\)	\ (4\) ">\(2\)
\ (\ times_ {5}\)” alcance="fila"> \(4\)	\ (1\) ">\(4\)	\ (2\) ">\(3\)	\ (3\) ">\(2\)	\ (4\) ">\(1\)

Tabla\(\PageIndex{6}\): Mesa de operaciones para el grupo\(\mathbb{U}_{8}\)

\(\times_{8}\)	\(1\)	\(3\)	\(5\)	\(7\)
\ (\ times_ {8}\)” alcance="fila"> \(1\)	\ (1\) ">\(1\)	\ (3\) ">\(3\)	\ (5\) ">\(5\)	\ (7\) ">\(7\)
\ (\ times_ {8}\)” alcance="fila"> \(3\)	\ (1\) ">\(3\)	\ (3\) ">\ 91\)	\ (5\) ">\(7\)	\ (7\) ">\(5\)
\ (\ times_ {8}\)” alcance="fila"> \(5\)	\ (1\) ">\(5\)	\ (3\) ">\(7\)	\ (5\) ">\(1\)	\ (7\) ">\(3\)
\ (\ times_ {8}\)” alcance="fila"> \(7\)	\ (1\) ">\(7\)	\ (3\) ">\(5\)	\ (5\) ">\(3\)	\ (7\) ">\(1\)

Nota Sage Math - Aritmética Modular

Sage hereda las funciones básicas de división de enteros de Python que computan un cociente y un resto en la división entera. Por ejemplo, aquí se explica cómo dividir 561 en 2017 y obtener el cociente y el resto.

a=2017
b=561
[q,r]=[a//b,a%b]
[q,r]

En Sage,\(gcd\) es la mayor función divisor común. Se puede utilizar de dos maneras. Para el gcd de 2343 y 4319 podemos evaluar la expresión\(gcd(2343,4319)\text{.}\) Si estamos trabajando con un módulo fijo\(m\) que tenga un valor establecido en su sesión de Sage, la expresión\(m.gcd(k)\) para computar el mayor divisor común de\(m\) y cualquier valor entero\(k\text{.}\) El euclidiano extendido algoritmo también puede ser llamado con\(xgcd\text{:}\)

a=2017
b=561
print(gcd(a,b))
print(xgcd(a,b))

Sage tiene una herramienta extremadamente poderosa para trabajar con grupos. Los números enteros\(n\) están representados por la expresión\(Integers(n)\) y las tablas de suma y multiplicación se pueden generar de la siguiente manera.

R = Integers(6)
print(R.addition_table('elements'))
print(R.multiplication_table('elements'))

Una vez que hayamos asignado\(R\) un valor de\(Integers(6)\text{,}\) podemos hacer cálculos\(R()\) envolviendo los enteros del 0 al 5. Aquí hay una lista que contiene la suma mod 6 y el producto, respectivamente, de 5 y 4:

[R(5)+R(4), R(5)*R(4)]

Generar la tabla de multiplicación para la familia de grupos\(\mathbb{U}_n\) requiere un poco más de código. Aquí restringimos las entradas permitidas para que sean enteros de 2 a 64.

def U_table(n):
    if n.parent()!=2.parent() or n < 2 or n > 64:
        return "input error/out of range"
    R=Integers(n)
    els=[]
    for k in filter(lambda k:gcd(n,k)==1,range(n)):
        els=els+[str(k)]
    return R.multiplication_table(elements=els,names="elements")
    
U_table(18)

Ejercicios

Ejercicio\(\PageIndex{1}\)

Determinar los mayores divisores comunes de los siguientes pares de enteros sin usar ninguna asistencia computacional.

1. \(2^3 \cdot 3^2\cdot 5\)y\(2^2 \cdot 3 \cdot 5^2\cdot 7\)
2. \(7! \)y\(3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\)
3. \(19^4\)y\(19^5\)
4. 12112 y 0

Contestar

1. \(\displaystyle 2^2 \cdot 3 \cdot 5\)
2. \(\displaystyle 3^2 \cdot 5\cdot 7\)
3. \(\displaystyle 19^4\)
4. 12112

Ejercicio\(\PageIndex{2}\)

Encuentra todos los valores posibles de lo siguiente, asumiendo que\(m\) es un entero positivo.

1. \(\displaystyle \gcd(m+1,m)\)
2. \(\displaystyle \gcd(m+2,m)\)
3. \(\displaystyle \gcd(m+4,m)\)

Ejercicio\(\PageIndex{3}\)

Calcular:

1. \(\displaystyle 7 +_8 3\)
2. \(\displaystyle 7 \times_8 3\)
3. \(\displaystyle 4\times_8 4\)
4. \(\displaystyle 10+_{12} 2\)
5. \(\displaystyle 6\times_8 2 +_8 6\times_8 5 \)
6. \(\displaystyle 6\times_8 \left(2 +_85\right)\)
7. \(\displaystyle 3 \times_5 3 \times_5 3 \times_5 3 \equiv 3^4 (\textrm{ mod} 5)\)
8. \(\displaystyle 2 \times_{11}7\)
9. \(\displaystyle 2 \times_{14}7\)

Contestar

1. \(2\)
2. \(5\)
3. \(0\)
4. \(0\)
5. \(2\)
6. \(2\)
7. \(1\)
8. \(3\)
9. \(0\)

Ejercicio\(\PageIndex{4}\)

Enumere las inversas aditivas de los siguientes elementos:

1. 4, 6, 9 in\(\mathbb{Z}_{10}\)
2. 16, 25, 40 in\(\mathbb{Z}_{50}\)

Ejercicio\(\PageIndex{5}\)

En el grupo\(\mathbb{Z}_{11}\), cuáles son:

1. 3 (4)?
2. 36 (4)?
3. ¿Cómo podría calcular de manera eficiente\(m(4)\text{,}\)\(m \in \mathbb{Z}\text{?}\)

Contestar

1. 1
2. 1
3. \(m(4) = r(4)\text{,}\)donde\(m = 11 q + r\text{,}\)\(0 \leq r < 11\)

Ejercicio\(\PageIndex{6}\)

Demostrar que\(\{1, 2, 3, 4\}\) es un grupo bajo la operación\(\times_5 \text{.}\)

Ejercicio\(\PageIndex{7}\)

Se pide a un alumno que resuelva las siguientes ecuaciones bajo el requisito de que toda la aritmética se haga en\(\mathbb{Z}_2\text{.}\) Listar todas las soluciones.

1. \(x^2 + 1 = 0\text{.}\)
2. \(x^2 + x + 1 = 0\text{.}\)

Contestar

Ya que las soluciones, si existen, deben provenir de la\(\mathbb{Z}_2\text{,}\) sustitución es el enfoque más fácil.

1. 1 es la única solución, ya que\(1^2+_21=0\) y\(0^2+_21=1\)
2. Sin soluciones, desde\(0^2+_2 0+_2 1=1\text{,}\) y\(1^2+_2 1+_2 1=1\)

Ejercicio\(\PageIndex{8}\)

Determinar las soluciones de las mismas ecuaciones que en Ejercicio\(\PageIndex{5}\) en\(\mathbb{Z}_5\text{.}\)

Ejercicio\(\PageIndex{9}\)

1. Escribe la mesa de operaciones para\(\times_8\) encendido\(\{1,3,5,7\}\text{,}\) y convencerte a ti mismo de que se trata de un grupo.
2. \(\mathbb{U}_{n}\)Dejen ser los elementos de\(\mathbb{Z}_{n}\) que tienen inversas con respecto a\(\times_{n}\text{.}\) Convénzate que\(\mathbb{U}_{n}\) es un grupo bajo\(\times_{n}\text{.}\)
3. Demostrar que los elementos de\(\mathbb{U}_{n}\) son aquellos elementos\(a\in \mathbb{Z}_{n} \) tales que\(\gcd(n,a)=1\text{.}\) Usted podrá utilizar Teorema\(\PageIndex{3}\) en esta prueba.

Ejercicio\(\PageIndex{10}\)

Demostrar la propiedad de división, Teorema\(\PageIndex{1}\).

Pista

Demuestra por inducción sobre\(m\) que puedes dividir cualquier entero positivo en Es\(m\text{.}\) decir, deja\(p(m)\) ser “Para todos\(n\) mayores que cero, existen enteros únicos\(q\) y\(r\) tal que”\(\dots\). En la etapa de inducción, divídalo\(n\) en\(m - n\text{.}\)

Ejercicio\(\PageIndex{11}\)

Supongamos\(f:\mathbb{Z}_{17}\to \mathbb{Z}_{17}\) tales\(f(i)=a \times_{17} i +_{17} b \) donde\(a\) y\(b\) son constantes enteras. Además, supongamos que\(f(1)=11\) y\(f(2)=4\text{.}\) Encuentre una fórmula para\(f(i)\) y también encuentre una fórmula para la inversa de\(f\text{.}\)

Contestar

Las condiciones dadas se pueden convertir en un sistema de ecuaciones lineales:

\ begin {ecuación*}\ begin {array} {c} f (1) =11\ Rightarrow a +_ {17} b = 11\\ f (2) =4\ Rightarrow 2\ times_ {17} a +_ {17} b =4\\ end {array}\ end {ecuación*}

Si restamos la primera ecuación de la segunda, obtenemos\(a = 4 +_{17} (-11) = 4 +_{17} 6= 10\text{.}\) Esto implica que\(b=1\text{,}\) y\(f(i) = 10\times+{17}i + 1\text{.}\) Para obtener una fórmula para la inversa de\(f\) resolvemos\(f(j)=i\) por\(j\text{,}\) usar el hecho de que la inversa multiplicativa de 10 (mod 17) es 12.

\ begin {equation*}\ begin {split} f (j) =i &\ Rightarrow 10\ times+ {17} j + 1 = i\\ &\ Rightarrow 10\ times+ {17} j = i +_ {17} 16\\ &\ Rightarrow j = 12\ times_ {17} (i +_ {17} 16)\\ end {split}\ end {equación}\ final {equación}\ final {equación}\ final {*}

Por lo tanto\(f^{-1}(i) = 12\times_{17}( i +_{17} 16) = 12\times_{17} i +_{17} 5\text{.}\)

Ejercicio\(\PageIndex{12}\)

Escribe la tabla de operaciones para multiplicar mod 10 en\(T=\{0,2,4,6,8\}\text{.}\) ¿Es\([T;\times_{10}]\) un monoide? ¿Es un grupo?

Contestar

Este sistema es un monoide con identidad 6 (¡sorpresa!). Sin embargo no es un grupo ya que 0 no tiene inversa.