pág 262-273

Yunga T. Sandra M.

Enero del 2022

0.1. A) CONJUNTO DE LAS CLASES DE RESTOS MÓDULO M 1

UNIVERSDIDAD CENTRAL DEL ECUADOR

MATEMÁTICA Y FÍSICA

MATEMÁTICA DISCRETA

INTEGRANTES: Albarrán Jessica- Yunga Mariela DOCENTE: MSc. Aules Hernán

SEMESTRE: 8-B FECHA DE ENTREGA: 30 de noviembre 2022 TALLER GRUPAL 01

0.1. a) Conjunto de las Clases de Restos Módulo m

En este apartado veremos que la relación de congruencia es de equivalencia y calcularemos el conjunto cociente, al
cual llamaremos Zm. Este conjunto será {[0],[1], . . . ,[m-1]},

donde

[0] ={. . . ,-2m,-m,0, m,2m, . . .}

[1] ={. . . ,-2m+ 1,-m+ 1,1, m+ 1,2m+ 1, . . .} y así sucesivamente

Con esta interpretación, cada elemento de Zm es considerado como el conjunto de todos los enteros congruentes
con un enteroi tal que 0 i 1.

Esta es la razón de que la propiedad cíclica de las congruencias sea tan importante. Si contamos desde 0 a 10 en
base decimal, originamos un ciclo desde 0 a 9 y volvemos al 0:

EJEMPLOS:

1. El cuentakilómetros de un coche es una instrumentación física de esta propiedad.

2. Los dígitos desde el 0 hasta el 9 se sitúan en un círculo, y cuando éste gira, tiene lugar la cuenta.

3. Cuando un círculo pasa desde el 9 hasta el 0, elsiguiente círculo a su izquierda se incrementa en 1.

Relación de Equivalencia

Dado un entero m > 0, la relación de congruencia módulo m es una relación de equivalencia en el conjunto de los
números enteros

Clases de Equivalencia

Dado un número entero cualquiera a, su clase de equivalencia es el conjunto formado por todos los enteros que dan
el mismo resto quea al dividirlos entre m.
2

Demostración
Recordemos que la clase de equivalencia de un elemento es el conjunto formado por todos los elementos relacionados
con él.
Pues bien, sea a un número entero cualquiera. Entonces,

[a] = fx 2 Z : x a(modm)g

Por otra parte, el teorema de existencia y unicidad de cociente y resto, asegura que existen q’y r, enteros y únicos
tales que

a = mq0 + r;con 0 r<m

[a] = fx 2 Z : x = mq 0 + r;con q 2 Zg

Finalmente tendremos que [a] estará formada por todos los enteros que den resto r al dividirlos entre m

0.1.1. Ejemplos

1. En el conjunto de los números enteros se considera la clase de equivalencia módulo 5. Hallar las
clases de equivalencia del 22; 6; 0; 3; 5; 7; 18y20:

Solución:
-El resto dividir-22 entre 5 es 3, luego

[ 22] = f5q + 3 : q 2 Zg = f:::; 17; 12; 7; 2; 3; 8; 13; 18; 23; :::g

-El resto de dividir-6 entre 5 es 4, luego

[3] = f5q + 4 : q 2 Zg = f:::; 16; 11; 6; 1; 4; 9; 14; 19; 24; :::g

-El resto de dividir 0 entre 5 es 0, luego,

[0] = f5q : q 2 Zg = f:::; 20; 15; 10; 5; 0; 5; 10; 15; 20; :::g

-El resto de dividir 3 entre 5 es 3, luego

[5] = [3]

-El resto de dividir 5 entre 5 es 0, luego

[5] = [0]

-El resto de dividir 7 entre 5 es 2, luego

[7] = f5q + 2 : q 2 Zg = f:::; 18; 13; 8; 3; 2; 7; 12; 17; 22; :::g

-El resto de dividir 18 entre 5 es 3, luego

[18] = [3]

-El resto de dividir 20 entre 5 es 0, luego

[20] = [0]
0.2. B) CONJUNTO COCIENTE 3

2. Demostrar que 13 y 3 son congruentes módulo 5

Solución:

En primer lugar escribimos en notación modular, así:

13 3(mod5)

luego,

10
13 3(mod5) ssi 5j13 3, es decir 5j10 =) 5 =2

Por lo tanto 13 y 3 son congruentes módulo 5

3.Demostrar que 17 y 9 son congruentes módulo 8

Solución:

En primer lugar escribimos en notación modular, así:

17 9(mod8)

luego,

8
17 9(mod8) ssi 8j17 9, es decir 8j8 =) 8 =1

Por lo tanto 17 y 9 son congruentes módulo 8

0.2. b) Conjunto Cociente

Al conjunto formado por las clases de equivalencia, es decir al conjunto cociente, lo llamaremos conjunto de las
clases de restos módulo m, lo notaremos por Zm y es Zm = f[0]; [1]; :::; [m 1]g

0.2.1. Demostración

Sean a y b dos enteros cualesquiera. Entonces,

[a] = [b]en Zm () a y b dan el mismo resto al dividirlos por m en Z () a b(modm)en Z.

de donde se sigue que

[a] 6= [b] en Zm () ayb dan distinto resto al dividirlos por m en Z () a 6= b(modm) en Z.

Como al dividir cualquier número entero por m pueden aparecer m restos distintos(0; 1; ; m 1), querrá esto decir
que habrá unicamente m clases distintas. Si tomamos el resto como representante de cada clase, es decir,

[r] = fx 2 Z : x = mq + r; conq 2 Zgel conjunto cociente será Zm = f[0]; [1]; ; [m 1]g

0.2.2. Ejemplos

1. En el conjunto de los números enteros se considera la relación de equivalencia módulo 5. Hallar

el conjunto cociente.

Solución:
4

Según hemos visto, Z5 = f[0]; [1]; [2]; [3]; [4]g

donde,

[0] = f:::; 20 15; 10; 5; 0; 5; 10; 15; 20:::g

[1] = f:::; 19; 14; 9; 4; 1; 6; 11; 16; 21:::g

[2] = f:::; 18; 13; 8; 3; 2; 7; 12; 17; 22:::g

[3] = f:::; 17; 12; 7; 2; 3; 8; 13; 18; 23:::g

[4] = f:::; 16; 11; 6; 1; 4; 9; 14; 19; 24:::g

Veamos ahora que el conjunto de enteros{10,-9,12,8,19}origina el mismo conjunto cociente. En efecto,

10 6= 9(mod5) en Z () [10]6 = [ 9]en Z5

10 6= 12(mod5) en Z () [10]6 = [12] en Z5

10 6= 8(mod5) en Z () [10]6 = [8] en Z5

10 6= 19(mod5) en Z () [10]6 = [19] en Z5

9 6= 12(mod5) en Z () [ 9]6 = [12] en Z5

9 6= 8(mod5) en Z () [ 9]6 = [8] en Z5

9 6= 19(mod5) en Z () [ 9]6 = [19] en Z5

12 6= 8(mod5) en Z () [12]6 = [8]en Z5

12 6= 19(mod5) en Z () [12]6 = [19] en Z5

8 6= 19(mod5) en Z () [8]6 = [19] en Z5

luego, Z5 = f[10]; [ 9]; [12]; [8]; [19]g

y naturalmente,

[10] = [0]

[-9] = [1]

[12] = [2]

[8] = [3]

[19] = [4]

2. Hallar un x modulo 3, que sea congruente con 4.

Solución:

Primero escribimos en notación modular, asi

4 x(mod3)

Por los teorema vistos el conjutno de residuos son equivalentes a la teoria establecida, por lo tanto planteamos el
conjunto solución y comprobamos:

CS = f::: 8; 5; 2; 1; :::g

Por probar que:

12
4 8(mod3) ssi 3j4 ( 8); luego 3j12, entonces 3 = 4. por lo tanto 8 si es parte del conjunto solución.
0.3. ¿QUÉ ES EL SISTEMA BINARIO? 5

9
4 5(mod3) ssi 3j4 ( 5); luego 3j9, entonces 3 = 3. por lo tanto 8 si es parte del conjunto solución.
6
4 2(mod3) ssi 3j4 ( 2); luego 3j6, entonces 3 = 2. por lo tanto 8 si es parte del conjunto solución.
3
4 1(mod3) ssi 3j4 (1); luego 3j3, entonces 3 = 1. por lo tanto 8 si es parte del conjunto solución.

El conjunto solución es f::: 8; 5; 2; 1; :::g ya que todos los números de la lista tienen como resto 1 al dividir
entre 3

0.3. ¿Qué es el Sistema Binario?

El sistema binario es un sistema de numeración en el que los números se representan utilizando las cifras 0 y 1, es
decir solo 2 dígitos (bi = dos).

Esto en informática y en electrónica tiene mucha importancia ya que las computadoras trabajan internamente con
2 niveles: hay o no hay de Tensión, hay o no hay corriente, pulsado o sin pulsar, etc.

Esto provoca que su sistema de numeración natural sea el binario, por ejemplo 1 para encendido y 0 para apagado.
También se utiliza en electrónica y en electricidad (encendido o apagado, activado o

desactivado, etc.). El lenguaje binario es muy utilizado en el mundo de la tecnología.

0.3.1. Operaciones con números binarios

0.3.2. Suma de números Binarios

Las posibles combinaciones al sumar dos bits son

0+0=0

0+1=1

1+0=1

1 + 1 = 10

Ejemplo

Operamos como en el sistema decimal: comenzamos a sumar desde la derecha, en nuestro ejemplo,1 + 1 = 10,
entonces escribimos 0 en la …la del resultado y llevamos 1 (este "1"se llama arrastre). A continuación se suma el
acarreo a la siguiente columna: 1 + 0 + 0 = 1, y seguimos hasta terminar todas la columnas (exactamente como
en decimal).

0.3.3. Resta de números binarios

El algoritmo de la resta en binario es el mismo que en el sistema decimal. Pero conviene repasar la operación de
restar en decimal para comprender la operación binaria, que es más sencilla. Los términos que intervienen en la
resta se llaman minuendo, sustraendo y diferencia.

Las restas básicas 0 0; 1 0y1 1 son evidentes:

0-0=0

1-0=1
6

1-1=0

0 - 1 = no cabe o se pide prestado al proximo.

La resta 0 - 1 se resuelve, igual que en el sistema decimal, tomando una unidad prestada de la posición siguiente:
10 1 = 1 y me llevo 1, lo que equivale a decir en decimal, 2 1 = 1. Esa unidad prestada debe devolverse,
sumándola, a la posición siguiente. Veamos algunos ejemplos:

A pesar de lo sencillo que es el procedimiento, es fácil confundirse. Tenemos interiorizado el sistema decimal y
hemos aprendido a restar mecánicamente, sin detenernos a pensar en el signi…cado del arrastre. Para simpli…car
las restas y reducir la posibilidad de cometer errores hay varias soluciones:

Dividir los números largos en grupos. En el siguiente ejemplo, vemos cómo se divide una resta larga en tres
restas cortas:

Utilizando el complemento a dos. La resta de dos números binarios puede obtenerse sumando al minuendo el
complemento a dos del sustraendo. Veamos algunos ejemplos. Hagamos la siguiente

resta, 91 46 = 45, en binario:

En el resultado nos sobra un bit, que se desborda por la izquierda. Pero, como el número resultante no puede ser
más largo que el minuendo, el bit sobrante se desprecia.

Y, despreciando el bit que se desborda por la izquierda, llegamos al resultado correcto:11000100 en binario, 196 en
decimal.

Utilizando el complemento a 1. La resta de dos números binarios puede obtenerse sumando al minuendo el
complemento a uno del sustraendo y a su vez sumarle el bit de over‡ow (bit que se

desborda).

0.3.4. Producto de números binarios

El algoritmo del producto en binario es igual que en números decimales; aunque se lleva cabo con más sencillez, ya
que el 0 multiplicado por cualquier número da 0, y el 1 es el elemento neutro del producto.

Por ejemplo, multipliquemos 10110 por 1001:

En sistemas electrónicos, donde se suelen utilizar números mayores, no se utiliza este método sino otro llamado
algoritmo de Booth.

0.3.5. División de números binarios

La división en binario es similar a la decimal, la única diferencia es que a la hora de hacer las restas, dentro de la
división, estas deben ser realizadas en binario.
0.4. C) ARITMÉTICA EN ZM 7

Por ejemplo, vamos a dividir 100010010

(274)entre1101(13) :

0.4. c) Aritmética en Zm

0.5. Suma

Dados dos enteros cualesquieraayb, de…nimos la suma enZmen la forma siguiente: [a] + [b] = [a + b]

La suma está bien de…nida, es decir, no depende de los representantes que se elijan en cada clase, en el sentido de
que si [a] = [a0]y[b] = [b0]; entonces[a] + [b] = [a0] + [b0]:

0.5.1. Demostración

En efecto,

[a] = [a0 ] () a a0 (modm)y [b] = [b0 ] () b b0 (modm)

entonces:

a+b a0 + b0 (modm) ) [a + b] = [a0 + b0 ] () [a] + [b] = [a0 ] + [b0 ]

La suma en Zm es asociativa y conmutativa.

0.5.2. Elemento Neutro para la Suma

El elemento neutro para la suma en Zm es la clase [0].

Demostración
8

Sea [a] cualquiera de Zm y sea [e] el neutro para la suma. Entonces,

[e] + [a] = [a] () [e + a] = [a]

() e + a a(modm)

() e a a(modm)

() e 0(modm)

() [e] = [0]

0.5.3. Ejemplos:

1. Sumar en el conjunto de las clases de restos módulo 5, Z5 , las clases [31]y[58]:

Solución:

Según la de…nición que acabamos de ver:

[31] + [58] = [89] = fx 2 Z : x = 5q + 4; conq 2 Zg = f:::; 16; 11; 6; 1; 4; 9; 14; 19; 24:::g = [4]

Obsérvese que en Z5 las clases [16]y[63] son iguales, respectivamente, a las clases [31]y[58], por lo tanto su suma ha
de ser igual a la calculada en el ejemplo anterior.

En efecto:

[16] + [63] = [79] = fx 2 Z : x = 5q + 4; conq 2 Zg = f:::; 16; 11; 6; 1; 4; 9; 14; 19; 24:::g = [4]

2. Calcular (1234 + 5678)mod10

(1234 + 5678)mod10 = ((1234mod10) + (5678mod10)) mod 10

= (4 + 8)mod10

= 12mod10

=2

0.5.4. Elemento Inverso

Un elemento [a] de Zm admite inverso si, y sólo si, a y m son primos entre si.

Demostración

En efecto, sea [a’] el inverso de [a] en Zm. Entonces:

[a0 ] [a] = [1] () [a0 a] = [1]

() a0 a 1(modm)

() a0 a = 1 + mq; conq 2 Z

() aa0 mq = 1

y esta ecuación lineal con coe…cientes enteros tiene solución si, y sólo si m:c:d:(a; m) = 1
0.5. SUMA 9

0.5.5. Ejemplo:

1. Hallar los inversos de 2 en Z11

Como 11 es primo, todos los elementos de Z11, excepto el cero, tienen inverso. Sea, pues, x el inverso de 2 en Z11.
Entonces,

x es el inverso de 2enZ11 () 2x = 1enZ11

() 2x 1(mod11)enZ

() 11j2x 1enZ

() 9y 2 Z : 2x 11y = 1

Obtendremos la solución general de esta ecuación diofántica utilizando el algoritmo de Euclides,

52

1121

10

luego m:c:d:(2; 11) = 1. Además,

1 = 11 2 5 = ( 5) 2 + ( 1)( 11)

de aquí que x = 1( 5)1 + k( 11)1; conk 2 Z = 5 11k = 6 11 11k = 11( 1 k) + 6 = 11q + 6,tomando
q= 1 k

es decir, x = 6enZ11

luego el inverso de 2 en Z11es 6

2. Probar que el número inmediatamente posterior a cualquier potencia de 5 es múltiplo de 2 pero no de 4.

Solución:

Bibliografía:

Operaciones con números binarios. (s/f). Xunta.es. http://centros.edu.xunta.es/iesmanuelchamosolamas/electricidade/fotos/n

Morales Hernández, Y., Calvache, J. A., Cifuentes Aguilera, J., & Murcia Berdugo, N. (2017). Algoritmo matemático
de la separación de un sistema binario mediante electrodiálisis. Revista de

investigación, 10(1), 161–172. https://doi.org/10.29097/2011-639x.74

Include Poetry - Code. (2020, 7 de abril). Aritmética modular. Obtenido de https://www.include-poetry.com/Code/C++/Mat

de-numeros/Aritmetica-modular/