Sistemas completos de residuos#
Introducción#
En este capítulo vamos a extender las ideas vistas en el capítulo anterior. Veremos lo que es un sistema de representantes y algunos ejemplos para comprender mejor la idea. Partiendo de ese concepto, pasaremos a definir un sistema completo de residuos y finalmente veremos algunas propiedades de estos sistemas. Estas ideas nos serán de utilidad para comprender mejor el siguiente capítulo.
Sistemas de representantes#
Definición 31 (Sistema de representantes)
Si \(A\) es un conjunto y \(\sim\) es una relación de equivalencia en \(A\), un sistema de representantes es un subconjunto \(R\) de \(A\) tal que:
Cualquier elemento de \(A\) está relacionado con algún elemento de \(R\).
Ningún par de elementos distintos de \(R\) está relacionado entre sí.
Ejemplo 82
Regresemos al Ejemplo 73, en donde vimos una relación sobre las rectas en el plano cartesiano. La relación que dimos fue que dos rectas \(l_1\) y \(l_2\) se relacionan si son paralelas, es decir si tienen la misma pendiente.
Supongamos que tenemos el siguiente conjunto de rectas \(A = \{ y = mx + b \mid m\in \{1,2,3,4\}, b \in \mathbb{R} \}\).
Entonces tendríamos los siguientes conjuntos.
El conjunto de las rectas que tienen pendiente \(1\), \(A_1 = \{y = x + b \mid b \in \mathbb{R} \}\).
El conjunto de las rectas que tienen pendiente \(2\), \(A_2 = \{y = 2x + b \mid b\in \mathbb{R} \}\).
El conjunto de las rectas que tienen pendiente \(3\), \(A_3 = \{y = 3x + b \mid b\in \mathbb{R} \}\).
El conjunto de las rectas que tienen pendiente \(4\), \(A_4 = \{y = 4x + b \mid b\in \mathbb{R} \}\).
De cada uno de estos conjuntos podemos tomar un elemento que represente al conjunto. Con ellos formamos al conjunto \(R = \{y = x , y = 2x, y = 3x, y = 4x \}\).
Podemos observar que para cualquier recta que tomemos del conjunto \(A\), ésta se relaciona con algún elemento de \(R\) y además ningún par de los elementos de \(R\) se relacionan entre ellos. Por lo tanto \(R\) es un sistema de representantes.
Ejemplo 83
Tomemos la partición que planteamos en el Ejemplo 79 y definamos la siguiente relación que resulta ser de equivalencia como consecuencia del Teorema 26.
Para \(a,b \in \mathbb{N}\) se tiene que,
\(a \sim b\) si \(a = b = 1\).
\(a \sim b\) si \(a\) y \(b\) son primos.
\(a \sim b\) si \(a\) y \(b\) son compuestos.
Con lo anterior podemos tomar como un posible sistema de representantes al conjunto \(R = \{1, 7, 8 \}\).
Proposición 25
Si \(A\) es un conjunto, \(\sim\) una relación de equivalencia en \(A\) y \(R\) un sistema de representantes, entonces \(\{[r] \mid r\in R\}\) es una partición de \(A\).
Demostración. Sea \(P = \{[r] \mid r \in R \}\).
Vamos a probar las \(3\) propiedades de la Definición 29 de partición.
Ningún \([r] \in P\) es vacío.
Esta propiedad se cumple directamente, ya que \(r \in [r]\).
Si \([r_i],[r_j] \in P\), debe suceder que \([r_i] \cap [r_j] = \emptyset\) si \(i\neq j\).
Supongamos que \(a \in [r_i] \cap [r_j]\) esto quiere decir que \(a \sim r_i\) y \(a \sim r_j\). Por la Definición 28 de relación de equivalencia tenemos que \(r_i \sim a\) y \(a \sim r_j\) por lo tanto \(r_i \sim r_j\), lo cual es falso por la Definición 31 de sistemas de representantes. Por lo tanto \([r_i] \cap [r_j] = \emptyset\) si \(i\neq j\).
\(A = \bigcup \{ [r] \mid r \in R \}\).
Por la Definición 31, para cualquier \(a \in A\), hay un \(r \in R\) tal que \(a \sim r\). Esto quiere decir que \(a \in [r]\) para algún \(r \in R\). Con esto probamos que \(A \subseteq \bigcup \{ [r] \mid r \in R \}\).
Por otro lado, por la Definición 30, se cumple que \([r] = \{ a \in A \mid a \sim r \}\), por lo que cada \([r] \subseteq A\).
Entonces tenemos que \(\bigcup \{ [r] \mid r \in R \} \subseteq A\).
Por lo tanto, el conjunto \(\{[r] \mid r\in R\}\) es una partición de \(A\). \(\square\)
Sistemas completos de residuos#
Definición 32 (Sistema completo de residuos)
Un sistema completo de residuos con respecto a \(n\) es un sistema de representantes de la relación en \(\mathbb{Z}\) dada por \(a\sim b\) si y sólo si \(a\) y \(b\) dejan el mismo residuo al dividirse entre \(n\).
Primero veamos un ejemplo pequeño, en donde en lugar de trabajar con todo el conjunto \(\mathbb{Z}\), lo reemplazamos por un conjunto reducido.
Ejemplo 84
Recordemos el Ejemplo 81, en donde teníamos el conjunto \(A = \{1, 2, 3, \ldots , 19, 20 \}\) y la siguiente relación, para \(a,b \in A = \{1, 2, 3, \ldots , 19, 20 \}\) se tiene que \(a \sim b\), si y solo si, \(a\) y \(b\) dejan el mismo residuo al dividirse entre \(4\).
Observemos que por el Teorema 3 cualquier número entero \(a\) dividido entre \(4\) lo podemos escribir de la forma \(a = 4q + r\), en donde \(0 \le r < 4\). Es decir, que tenemos los siguientes \(4\) casos:
Esto nos permite ver las siguientes clases de equivalencia
Si tomamos un elemento de cada una de las clases formaríamos el siguiente conjunto \(R = \{12,7,18,13\}\), el cual es un sistema de representantes.
Veamos que ningún elemento de \(R\) está relacionado entre sí ya que no dejan el mismo residuo al ser divididos entre \(4\).
Además, para toda \(a \in A\) existe un \(r \in R\) tal que \(a \sim r\).
Por lo tanto, el conjunto \(\{12,7,18,13 \}\) es un sistema completo de residuos.
Ejemplo 85
Da un sistema completo de residuos con respecto a \(7\) compuesto enteramente por múltiplos de \(11\).
Solución.
La relación de la Definición 32 nos da las siguientes clases de equivalencia.
Ahora, para formar el sistema completo de residuos necesitamos tomar un representante de cada clase, cada unos de éstos representantes debe cumplir con ser múltiplo de \(11\).
Para la clase \([0]\) es sencillo, ya que \(0\) es múltiplo de cualquier número y deja residuo cero al dividirse entre \(7\).
Para las demás clases podemos hacer lo siguiente.
Tomemos la clase \([1]\) y veamos que para ser múltiplo de \(11\) se debe cumplir que \(7q + 1 = 11k\) para algún entero \(k\). Esto lo podemos ver como la ecuación diofantina \(11k - 7q = 1\), la cual tiene solución ya que \((11,7) = 1\) y \(1|1\). Resolvamos la ecuación con el algoritmo de Euclides
Ahora, usamos las ecuaciones para encontrar las soluciones.
Por lo tanto, tenemos que \(11\cdot 2 - 7\cdot 3 = 1\). Es decir, que el elemento de la clase \([1]\) es \(11\cdot 2 = 7\cdot 3 + 1 = 22\).
Luego con la igualdad \(11\cdot 2 = 7\cdot 3 + 1\) podemos generar los elementos de las clases restantes multiplicando la igualdad por \(2,3,4,5,6\).
Así, obtenemos que el conjunto \(R = \{ 0, 22, 44, 66, 88, 110, 132 \}\) es un sistema completo de residuos con respecto a \(7\), donde todos sus elementos son múltiplos de \(11\).
Ejemplo 86 (Otros ejemplos)
Sean \(a,b \in \mathbb{Z}\), tenemos que \(a\sim b\), si y solo si, \(a\) y \(b\) dejan el mismo residuo al dividirse entre \(n\).
Si \(n = 7\).
Un sistema completo de residuos sería \(\{ 0,2,4,6,8,10,12 \}\).
Si \(n = 8\).
Un sistema completo de residuos sería \(\{ 0,3,6,9,12,15,18,21\}\).
si \(n = m\).
Un sistema completo de residuos sería \(\{ 0,1,2, \ldots , m-2, m-1\}\).
Como vimos en los ejemplos anteriores, podemos tener un sistema completo de residuos \(\{a_1, a_2, \ldots, a_n \}\) con respecto a \(n\) donde los valores no están en algún orden en específico, pero con la siguiente definición pondremos orden a estos conjuntos.
Definición 33 (Sistema completo de residuos mínimo)
Diremos que el conjunto \(\{0,1,2, \ldots , n-1 \}\) es un sistema completo de residuos mínimo con respecto a \(n\), si para cualquier \(r\) que está en el sistema de residuos, se cumple que \(0\le r < n\).
Proposición 26
Si \(R\) es un sistema completo de residuos con respecto a \(n\), entonces \(R\) tiene exactamente \(n\) elementos, los cuales dejan todos los posibles residuos \(0,1,\ldots,n-1\) al dividirlos por \(n\).
Demostración. Primero notemos que, gracias al Teorema 3 si tomamos dos enteros positivos \(a\) y \(n\) existen \(r\) y \(q\) enteros únicos tales que \(a = qn + r\) en donde \(0 \le r < n\). Esto quiere decir que cada entero \(a\) tiene una representación única en términos del residuo cuando es dividido entre \(n\).
Consideremos el siguiente sistema completo de residuos con respecto a \(n\), \(R = \{a_1,a_2,a_3, \ldots , a_m\}\).
Supongamos que \(m < n\).
Entonces sucedería que para alguna \(b\) en \(\{ 0,1,2, \ldots, n-1 \}\), se tendría que \(b \not\sim a_j\), donde \(j = 1,2, \ldots ,m\), pues hay más posibilidades para \(b\) que las que pueden dar las \(a_j\). Es decir que \(b\) no tiene un representante en \(R\). Por lo tanto, no se cumpliría la Definición 31. Así, \(R\) no sería un sistema de residuos completo con respecto a \(n\).
Ahora, supongamos que \(m > n\).
Como \(|R| > n\), tendríamos que para \(a_1, a_2 \in R\) existiría \(b = 0,1,2, \ldots ,n-1\) tal que \(b \sim a_1\) y \(b \sim a_2\). Entonces por la simetría, tenemos que \(a_1 \sim b\) y \(b \sim a_2\), luego por la transitividad tenemos que \(a_1 \sim a_2\). Por lo cual, se contradice la Definición 31. Así, \(R\) no sería un sistema de residuos completo.
Por lo tanto, \(n = m\) y el conjunto \(R\) tiene cardinalidad \(n\).
Por definición, sabemos que si \(i\neq j\) y \(a_i,a_j \in R\) entonces \(a_i\not\sim a_j\), es decir que al dividirlos entre \(n\) no dejan el mismo residuo. Resulta que, para cada \(a_k \in R\), por el algoritmo de la divisón tendremos que \(a_k = qn + r_k\), donde \(0 \le r_k < n\) y como cada \(r_k\) es diferente, tendremos todos los posibles residuos \(0,1,2, \ldots ,n-1\). \(\square\)
Definición 34 (Sistema de residuos reducido)
Un sistema de residuos reducido con respecto a \(n\) es un conjunto de enteros \(r_i\) tales que \((r_i,n) = 1\), en donde \(r_i\) no se relaciona con \(r_j\) si \(i \neq j\), además todo \(x\in \mathbb{Z}\) que sea primo relativo con \(n\) se relaciona con algún \(r_i\).
Veamos un ejemplo de cómo podemos formar estos sistemas de residuos reducidos.
Ejemplo 87
Tomemos el siguiente sistema completo de residuos con respecto a \(18\).
De este conjunto necesitamos eliminar los elementos que no cumplan con ser primos relativos con \(18\). Es decir, que el sistema de residuos reducido sería
Notemos que podemos usar la función \(\varphi(n)\) de Euler para calcular cuántos elementos tienen estos conjuntos. Observemos que \(\varphi(18) = 6\).
Código para verificar si un conjunto es un sistema completo de residuos con respecto a \(n\)#
El siguiente código nos dirá si dado un entero \(n\), un conjunto es un sistema completo de residuos.
def sistema_completo(conjunto,n):
if len(conjunto) != n:
return print(f"El conjunto {conjunto} no tiene {n} elementos \nno puede ser un sistema completo de residuos con respecto a {n}.")
else:
residuos = {}
for i in conjunto:
r = i%n
if r not in residuos:
residuos[r] = i
if len(residuos.keys()) != n:
residuos_faltantes = []
for i in range(0,n):
if i not in residuos:
residuos_faltantes.append(i)
return print(f"El conjunto {conjunto} no es un sistema completo de residuos con respecto a {n} \nno aparecen los residuos {residuos_faltantes}.")
else:
residuos_ordenados = sorted(residuos.keys())
print(f"El conjunto {conjunto} si es un sistema completo de residuos con respecto a {n}.")
for i in residuos_ordenados:
print(f"El número {residuos[i]} genera el residuo {i}.")
conjunto = [2,4,6,8,10,11]
sistema_completo(conjunto, 4)
El conjunto [2, 4, 6, 8, 10, 11] no tiene 4 elementos
no puede ser un sistema completo de residuos con respecto a 4.
conjunto = [12,13,14,15,16,17]
sistema_completo(conjunto, 6)
El conjunto [12, 13, 14, 15, 16, 17] si es un sistema completo de residuos con respecto a 6.
El número 12 genera el residuo 0.
El número 13 genera el residuo 1.
El número 14 genera el residuo 2.
El número 15 genera el residuo 3.
El número 16 genera el residuo 4.
El número 17 genera el residuo 5.
conjunto = [23,87,34,76,12,89,2]
sistema_completo(conjunto, 7)
El conjunto [23, 87, 34, 76, 12, 89, 2] no es un sistema completo de residuos con respecto a 7
no aparecen los residuos [0, 1, 4].
conjunto = [109,123,137,151,165,166,180,194,208,222,236,250,264]
sistema_completo(conjunto,13)
El conjunto [109, 123, 137, 151, 165, 166, 180, 194, 208, 222, 236, 250, 264] si es un sistema completo de residuos con respecto a 13.
El número 208 genera el residuo 0.
El número 222 genera el residuo 1.
El número 236 genera el residuo 2.
El número 250 genera el residuo 3.
El número 264 genera el residuo 4.
El número 109 genera el residuo 5.
El número 123 genera el residuo 6.
El número 137 genera el residuo 7.
El número 151 genera el residuo 8.
El número 165 genera el residuo 9.
El número 166 genera el residuo 10.
El número 180 genera el residuo 11.
El número 194 genera el residuo 12.
Algunas propiedades aritméticas de sistemas completos de residuos#
Proposición 27
Si \(\{ r_1,\ldots,r_n \}\) es un sistema completo de residuos con respecto a \(n\) y \(m\) es primo relativo con \(n\), entonces \(\{ mr_1,\ldots,mr_n \}\) también es un sistema completo de residuos con respecto a \(n\).
Demostración. Denotemos como \(R_m = \{ mr_1, mr_2,\ldots,mr_n \}\) y como \(R = \{ r_1, r_2,\ldots,r_n \}\) a dichos conjuntos. Tenemos que demostrar que \(R_m\) es un sistema completo de residuos.
Vamos a probar que se cumple la Definición 31.
Primero vamos a demostrar que ningún par de elementos de \(R_m\) está relacionado.
Procedamos por contradicción. Supongamos que para \(mr_i, mr_j \in R_m\) se tiene que \(mr_i \sim mr_j\) en donde \(1 \le i < j \le n\). De lo anterior tenemos que, al dividir \(mr_i\) y \(mr_j\) entre \(n\) obtendremos el mismo residuo, es decir que por el Teorema 3 tenemos que,
Podemos despejar \(k\) de cada una de las igualdades,
Entonces tendremos lo siguiente,
Por hipótesis tenemos que \(m\) y \(n\) son primos relativos, es decir que \((m,n) = 1\). Entonces por el Corolario 2, sucede que \(n|(r_i - r_j)\). Y por la Proposición 24, \(r_i \sim r_j\). Esto no puede ser ya que \(r_i, r_j \in R\) y \(R\) es un sistema completo de residuos. Por lo tanto los elementos del conjunto \(R_m\) no están relacionados entre sí.
Ahora tendríamos que ver que cualquier elemento \(a \in \mathbb{Z}\) esta relacionado con algún \(mr_i\in R_m\).
Si tomamos el elemento \(a\) y lo dividimos entre \(n\), entonces por el Teorema 3 existen \(q\) y \(k\) enteros tales que \(a = qn + k\), en donde \(0\le k < n\).
Por la Proposición 26 sabemos que \(R\) tiene exactamente \(n\) elementos, entonces \(R_m\) también tiene \(n\) elementos los cuales dejan todos los posibles residuos \(0,1,2, \ldots , n-1\) al dividirlos entre \(n\), esto porque ningún \(mr_i\) está relacionado con otro.
Luego, como \(a\) deja residuo \(k\), en donde \(0\le k < n\) existe un \(mr_i \in R_m\) que también deja residuo \(k\), y por lo tanto \(a \sim mr_i\). \(\square\)
Ejemplo 88
Exhibe un sistema completo de residuos con respecto a \(11\) que esté compuesto por múltiplos de \(4\).
Solución.
Podemos tomar el sistema completo de residuos mínimo con respecto a \(11\) es decir,
Luego por la Proposición 27 podemos tomar \(m = 4\) y se cumple que \((4,11) = 1\). Entonces basta multiplicar los elementos del conjunto anterior por \(4\) para obtener lo deseado, y así el sistema completo de residuos con respecto a \(11\) y compuesto por múltiplos de \(4\) sería
Proposición 28
Sea \(R\) un sistema completo de residuos con respecto a \(n\), y sea \(m\) un entero positivo primo relativo con \(n\). Entonces para cualquier entero positivo \(b\) se tiene que el conjunto \(S = mR + b = \{mr + b \mid r \in R \}\) es un sistema completo de residuos.
Demostración. Tenemos que probar que \(S\) cumple con la Definición 31. Sea \(R = \{r_1, r_2, \ldots , r_n \}\).
Veamos que ningún par de elementos de \(S\) están relacionados.
Vamos a proceder por contradicción. Supongamos que \(s_i\) está relacionado con \(s_j\), es decir que dejan el mismo residuo al dividirse entre \(n\). Entonces por el Teorema 3 tendríamos que existen \(q_1,q_2\) y \(k\) enteros tales que
Luego, podemos despejar el valor de \(k\) de ambas ecuaciones para tener que
Por hipótesis tenemos que \(m\) y \(n\) son primos relativos, es decir que \((m,n) = 1\). Entonces por el cor-primrelative1, sucede que \(n|(r_i - r_j)\). Y por la Proposición 24, tenemos que \(r_i \sim r_j\) lo cual no puede ser ya que \(r_i, r_j \in R\) y \(R\) es un sistema completo de residuos. Por lo tanto, los elementos del conjunto \(S\) no están relacionados entre sí.
Ahora veamos que cualquier elemento \(a \in \mathbb{Z}\) esta relacionado con algún \(s_i\in S\).
Si tomamos el elemento \(a\) y lo dividimos entre \(n\), entonces por el Teorema 3 existen \(q\) y \(k\) enteros tales que \(a = qn + k\), en donde \(0\le k < n\).
Por la Proposición 26 sabemos que \(R\) tiene exactamente \(n\) elementos. Entonces \(S\) también tiene \(n\) elementos los cuales dejan todos los posibles residuos \(0,1,2, \ldots , n-1\) al dividirlos entre \(n\), esto porque ningún \(s_i\) esta relacionado con otro.
Luego, como \(a\) deja residuo \(k\), en donde \(0\le k < n\), existe un \(s_i \in S\) que también deja residuo \(k\), y por lo tanto \(a \sim s_i\). \(\square\)
De la Proposición 28 tenemos el siguiente corolario.
Corolario 7
Sean \(m\) y \(n\) enteros primos relativos, \(b\) un entero cualquiera y \(R\) un sistema completo de residuos con respecto a \(n\). Entonces los elementos del sistema completo de residuos con respecto a \(n\), \(S = mR + b = \{mr + b \mid r \in R \}\), se relacionan con los elementos del sistema completo de residuos con respecto a \(n\), \(\{ 0,1,2,3, \ldots, n-1 \}\) en algún orden.
Ejemplo 89
Tomemos \(m = 7\), \(n = 10\) y \(b = 6\), entonces tendríamos el siguiente sistema completo de residuos con respecto a \(n\),
Entonces tendríamos los residuos \(6,3,0,7,4,1,8,5,2,9\), los cuales son los elementos del sistema completo de residuos con respecto a \(10\), \(\{ 0,1,2,3,4,5,6,7,8,9\}\).
Explicación del código#
Veamos cómo funciona el código para verificar si un conjunto es un sistema completo de residuos con respecto a \(n\).
def sistema_completo(conjunto,n):
if len(conjunto) != n:
return print(f"El conjunto {conjunto} no tiene {n} elementos \nno puede ser un sistema completo de residuos con respecto a {n}.")
else:
residuos = {}
for i in conjunto:
r = i%n
if r not in residuos:
residuos[r] = i
if len(residuos.keys()) != n:
residuos_faltantes = []
for i in range(0,n):
if i not in residuos:
residuos_faltantes.append(i)
return print(f"El conjunto {conjunto} no un sistema completo de residuos \nno aparecen los residuos {residuos_faltantes}.")
else:
residuos_ordenados = sorted(residuos.keys())
print(f"El conjunto {conjunto} sí es un sistema completo de residuos con respecto a {n}.")
for i in residuos_ordenados:
print(f"El número {residuos[i]} genera el residuo {i}.")
Definimos una función llamada «sistema_completo» la cual recibe como argumentos dos valores. El primer argumento es la variable «conjunto» la cual es una lista con números enteros. El segundo argumento es «n» la cual debe ser un número entero positivo.
def sistema_completo(conjunto,n):
Luego, con un condicional
ifrevisamos la longitud del conjunto. Por el Proposición 26, sabemos que el conjunto debe tener exactamente \(n\) elementos. Si no se cumple esta condición, entonces el código nos imprime en la consola que el conjunto dado no tiene \(n\) elementos y por tanto no puede ser un sistema completo de residuos.
if len(conjunto) != n:
return print(f"El conjunto {conjunto} no tiene {n} elementos \nno puede ser un sistema completo de residuos")
Si el conjunto tiene \(n\) elementos, el código pasa al condicional
else. Dentro de este condicional creamos la variable «residuos» la cual es un diccionario vacío. Luego, con un cicloforrecorremos los valores dentro de la variable «conjunto». Para cada valor se calcula el residuo al ser divido entre \(n\) y se guarda este valor en la variable «r». Después, con un condicionalif, revisamos si el residuo «r» no está en el diccionario «residuos». Si la clave «r» no está en el diccionario, se agrega y como valor se guarda el número correspondiente. Con esto logramos guardar en el diccionario «residuos», los residuos que generan los números en el conjunto.
else:
residuos = {}
for i in conjunto:
r = i%n
if r not in residuos:
residuos[r] = i
Luego creamos un condicional
if. Si el número de elementos en el diccionario «residuos» es diferente de «n», entonces se reproduce el código dentro del condicional.
Se crea la variable «residuos_faltantes», la cual es una lista vacía. Luego, con un cicloforrecorremos los valores en el rango de \(0\) a \(n-1\). Con un condicionalif, revisamos si cada uno de los valores no están en el diccionario «residuos». Si no están, entonces se agregan a la lista «residuos_faltantes». Con esto logramos obtener los residuos que faltarían para que el conjunto sea un sistema completo de residuos. Así, el código nos imprime en la consola que el conjunto no es un sistema completo de residuos y nos dice qué residuos hacen falta.
if len(residuos.keys()) != n:
residuos_faltantes = []
for i in range(0,n):
if i not in residuos:
residuos_faltantes.append(i)
return print(f"El conjunto {conjunto} no un sistema completo de residuos \nno aparecen los residuos {residuos_faltantes}")
Si el diccionario «residuos» si tiene «n» elementos, se reproduce el código dentro del coindicional
else. Creamos la variable «residuos_ordenados» la cual contiene la lista de residuos ordenada de menor a mayor. Luego, el código nos imprime en la consola que el conjunto sí es un sistema completo de residuos con respecto a «n». Además, nos dice qué residuo genera cada uno de los elementos del conjunto.
else:
residuos_ordenados = sorted(residuos.keys())
print(f"El conjunto {conjunto} sí es un sistema completo de residuos con respecto a {n}")
for i in residuos_ordenados:
print(f"El número {residuos[i]}, genera el residuo {i}")
Ejercicios de práctica#
Da un sistema completo de residuos con respecto a \(17\) compuesto enteramente por múltiplos de \(3\).
Da un sistema de residuos reducido con respecto a \(12\).
Da un sistema de residuos reducido con respecto a \(7\) compuesto enteramente por potencias de \(3\).
Muestra que \(2,4,6,\ldots, 2m\) es un sistema completo de residuos con respecto a \(m\), si \(m\) es impar.
Muestra que \(1^2, 2^2, \ldots , m^2\) no es un sistema completo de residuos con respecto a \(m\) si \(m > 2\).
Sea \(p\) un número primo mayor que \(2\). Si \(r_1, r_2, \ldots , r_p\) y \(r'_1, r'_2, \ldots , r'_p\) son sistemas completos de residuos con respecto a \(p\), demuestra que \(r_1r'_1, r_2r'_2, \ldots , r_pr'_p\) no puede ser un sistema completo de residuos con respecto \(p\).