Álgebra Superior II

José Alejandro Lara Rodrı́guez

Facultad de Matemáticas
Universidad Autónoma de Yucatán

17 de mayo de 2017

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 1 / 82

Contenido

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 2 / 82

Contenido

1 El anillo de los enteros: Divisibilidad

Divisibilidad
El máximo común divisor
El Algoritmo de la División
El mı́nimo común múltiplo
Ecuaciones diofantinas
El Teorema Fundamental de la Aritmética
Los enteros módulo n y la aritmética modular

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 3 / 82

Definiciones básicas

Definición

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 4 / 82

Definiciones básicas

Definición
1 a, b ∈ Z. Se dice que a divide a b, si b = ac para algún c ∈ Z.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 4 / 82

Definiciones básicas

Definición
1 a, b ∈ Z. Se dice que a divide a b, si b = ac para algún c ∈ Z.
2 a | b significa a divide a b.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 4 / 82

Definiciones básicas

Definición
1 a, b ∈ Z. Se dice que a divide a b, si b = ac para algún c ∈ Z.
2 a | b significa a divide a b.
3 Si a | b, se dice que

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 4 / 82

Definiciones básicas

Definición
1 a, b ∈ Z. Se dice que a divide a b, si b = ac para algún c ∈ Z.
2 a | b significa a divide a b.
3 Si a | b, se dice que
1 a es un divisor de b

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 4 / 82

Definiciones básicas

Definición
1 a, b ∈ Z. Se dice que a divide a b, si b = ac para algún c ∈ Z.
2 a | b significa a divide a b.
3 Si a | b, se dice que
1 a es un divisor de b
2 a es un factor de b

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 4 / 82

Definiciones básicas

Definición
1 a, b ∈ Z. Se dice que a divide a b, si b = ac para algún c ∈ Z.
2 a | b significa a divide a b.
3 Si a | b, se dice que
1 a es un divisor de b
2 a es un factor de b
3 b es un múltiplo de a

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 4 / 82

Definiciones básicas

Definición
1 a, b ∈ Z. Se dice que a divide a b, si b = ac para algún c ∈ Z.
2 a | b significa a divide a b.
3 Si a | b, se dice que
1 a es un divisor de b
2 a es un factor de b
3 b es un múltiplo de a
4 b es divisible entre a.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 4 / 82

Ejemplos

Ejemplo

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 5 / 82

Ejemplos

Ejemplo
1) 3 | 12 y −2 | 8.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 5 / 82

Ejemplos

Ejemplo
1) 3 | 12 y −2 | 8.
2) ¿5 divide 0?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 5 / 82

Ejemplos

Ejemplo
1) 3 | 12 y −2 | 8.
2) ¿5 divide 0?
3) ¿0 | 5?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 5 / 82

Ejemplos

Ejemplo
1) 3 | 12 y −2 | 8.
2) ¿5 divide 0?
3) ¿0 | 5?
4) ¿Cuáles son los enteros que dividen al cero?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 5 / 82

Ejemplos

Ejemplo
1) 3 | 12 y −2 | 8.
2) ¿5 divide 0?
3) ¿0 | 5?
4) ¿Cuáles son los enteros que dividen al cero?
5) ¿Cuál o cuáles son los enteros al que el cero divide?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 5 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6=

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 = 6 · 0 + 10 · 1

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 = 6 · 0 + 10 · 1
42 =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 = 6 · 0 + 10 · 1
42 = 6 · 2 + 10 · 3

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 = 6 · 0 + 10 · 1
42 = 6 · 2 + 10 · 3
4=

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 = 6 · 0 + 10 · 1
42 = 6 · 2 + 10 · 3
4 = 6 · (−1) + 10 · 1

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 = 6 · 0 + 10 · 1
42 = 6 · 2 + 10 · 3
4 = 6 · (−1) + 10 · 1
2=

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 = 6 · 0 + 10 · 1
42 = 6 · 2 + 10 · 3
4 = 6 · (−1) + 10 · 1
2 = 6 · 2 + 10 · (−1)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 = 6 · 0 + 10 · 1
42 = 6 · 2 + 10 · 3
4 = 6 · (−1) + 10 · 1
2 = 6 · 2 + 10 · (−1)
− 70 =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Combinaciones lineales

Definición
Una combinación lineal de los enteros a y b es un entero de la forma
ax + by donde x, y son enteros.

Ejemplo
Los siguientes números son combinaciones lineales de 6 y 10

6 = 6 · 1 + 10 · 0
10 = 6 · 0 + 10 · 1
42 = 6 · 2 + 10 · 3
4 = 6 · (−1) + 10 · 1
2 = 6 · 2 + 10 · (−1)
− 70 = 6 · (−5) + 10 · (−4)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 6 / 82

Propiedades básicas de la divisibilidad

Teorema

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 7 / 82

Propiedades básicas de la divisibilidad

Teorema

1) Propiedad reflexiva: Si a ∈ Z, a, a | a.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 7 / 82

Propiedades básicas de la divisibilidad

Teorema

1) Propiedad reflexiva: Si a ∈ Z, a, a | a.
2) Propiedad transitiva: Si a | b y b | c, entonces a | c.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 7 / 82

Propiedades básicas de la divisibilidad

Teorema

1) Propiedad reflexiva: Si a ∈ Z, a, a | a.
2) Propiedad transitiva: Si a | b y b | c, entonces a | c.
3) Un entero c divide a los enteros a y b si y solamente si c divide a
cualquier combinación lineal de a y b:

c | a y c | b ⇔ c | (ax + by) para cualesquiera enteros x, y.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 7 / 82

Propiedades básicas de la divisibilidad

Teorema

1) Propiedad reflexiva: Si a ∈ Z, a, a | a.
2) Propiedad transitiva: Si a | b y b | c, entonces a | c.
3) Un entero c divide a los enteros a y b si y solamente si c divide a
cualquier combinación lineal de a y b:

c | a y c | b ⇔ c | (ax + by) para cualesquiera enteros x, y.

4) a | b y b | a si y solamente si a = ub, donde u es una unidad en Z.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 7 / 82

Propiedades básicas de la divisibilidad

Teorema

1) Propiedad reflexiva: Si a ∈ Z, a, a | a.
2) Propiedad transitiva: Si a | b y b | c, entonces a | c.
3) Un entero c divide a los enteros a y b si y solamente si c divide a
cualquier combinación lineal de a y b:

c | a y c | b ⇔ c | (ax + by) para cualesquiera enteros x, y.

4) a | b y b | a si y solamente si a = ub, donde u es una unidad en Z.

5) Sea m 6= 0 un entero. Entonces

a|b ⇐⇒ ma | mb

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 7 / 82

Ejemplo

Ejemplo

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 8 / 82

Ejemplo

Ejemplo
1 ¿Es 64 es combinación lineal de a = 15 y b = 20?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 8 / 82

Ejemplo

Ejemplo
1 ¿Es 64 es combinación lineal de a = 15 y b = 20?
2 Sea c = 5. Entonces c | a y c | b.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 8 / 82

Ejemplo

Ejemplo
1 ¿Es 64 es combinación lineal de a = 15 y b = 20?
2 Sea c = 5. Entonces c | a y c | b.
3 5 | ax + by para toda x, y ∈ Z.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 8 / 82

Ejemplo

Ejemplo
1 ¿Es 64 es combinación lineal de a = 15 y b = 20?
2 Sea c = 5. Entonces c | a y c | b.
3 5 | ax + by para toda x, y ∈ Z.
4 5 | 64 (Contradicción)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 8 / 82

Propiedades básicas de la divisibilidad

Corolario

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 9 / 82

Propiedades básicas de la divisibilidad

Corolario

1) Si a | b, entonces a | bx para cualquier entero x.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 9 / 82

Propiedades básicas de la divisibilidad

Corolario

1) Si a | b, entonces a | bx para cualquier entero x.

2) Si c | a y c | b, entonces c | (±a ± b).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 9 / 82

Divisibilidad y valor absoluto

Teorema
Sean a, b ∈ Z.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 10 / 82

Divisibilidad y valor absoluto

Teorema
Sean a, b ∈ Z.
1) Entonces a | |a| y |a| | a.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 10 / 82

Divisibilidad y valor absoluto

Teorema
Sean a, b ∈ Z.
1) Entonces a | |a| y |a| | a.
2) Las siguientes condiciones son equivalentes:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 10 / 82

Divisibilidad y valor absoluto

Teorema
Sean a, b ∈ Z.
1) Entonces a | |a| y |a| | a.
2) Las siguientes condiciones son equivalentes:
a) a | b

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 10 / 82

Divisibilidad y valor absoluto

Teorema
Sean a, b ∈ Z.
1) Entonces a | |a| y |a| | a.
2) Las siguientes condiciones son equivalentes:
a) a | b
b) |a| | |b|.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 10 / 82

Divisibilidad y orden

Teorema
Si a y b son enteros con b 6= 0 y a | b, entonces |a| ≤ |b|.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 11 / 82

Divisibilidad y orden

Teorema
Si a y b son enteros con b 6= 0 y a | b, entonces |a| ≤ |b|.

Corolario
Si a ∈ Z y a 6= 0, entonces

{b ∈ Z : b | a}

es un conjunto finito.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 11 / 82

Contenido

1 El anillo de los enteros: Divisibilidad

Divisibilidad
El máximo común divisor
El Algoritmo de la División
El mı́nimo común múltiplo
Ecuaciones diofantinas
El Teorema Fundamental de la Aritmética
Los enteros módulo n y la aritmética modular

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 12 / 82

Máximo común divisor

Definición
El máximo común divisor de los enteros a y b es
(
máx{d ∈ Z : d | a y d | b} si a 6= 0 o b 6= 0
mcd(a, b) =
0 si a = 0 = b

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 13 / 82

Máximo común divisor

Definición
El máximo común divisor de los enteros a y b es
(
máx{d ∈ Z : d | a y d | b} si a 6= 0 o b 6= 0
mcd(a, b) =
0 si a = 0 = b

Observaciones

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 13 / 82

Máximo común divisor

Definición
El máximo común divisor de los enteros a y b es
(
máx{d ∈ Z : d | a y d | b} si a 6= 0 o b 6= 0
mcd(a, b) =
0 si a = 0 = b

Observaciones
1) mcd(a, b) = mcd(b, a).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 13 / 82

Máximo común divisor

Definición
El máximo común divisor de los enteros a y b es
(
máx{d ∈ Z : d | a y d | b} si a 6= 0 o b 6= 0
mcd(a, b) =
0 si a = 0 = b

Observaciones
1) mcd(a, b) = mcd(b, a).
2) mcd(a, b) = mcd(±a, ±b).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 13 / 82

Ejemplos

Ejemplo

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 14 / 82

Ejemplos

Ejemplo
1 mcd(6, 10) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 14 / 82

Ejemplos

Ejemplo
1 mcd(6, 10) =
2 mcd(−4, 6) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 14 / 82

Ejemplos

Ejemplo
1 mcd(6, 10) =
2 mcd(−4, 6) =
3 mcd(3, 0) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 14 / 82

Ejemplos

Ejemplo
1 mcd(6, 10) =
2 mcd(−4, 6) =
3 mcd(3, 0) =
4 mcd(0, −3) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 14 / 82

Ejemplos

Ejemplo
1 mcd(6, 10) =
2 mcd(−4, 6) =
3 mcd(3, 0) =
4 mcd(0, −3) =
5 mcd(a, 0) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 14 / 82

Teorema
Si a y b son enteros, entonces

mcd(a, b) = mcd(a, b − a) = mcd(a, a + b).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 15 / 82

Teorema
Si a y b son enteros, entonces

mcd(a, b) = mcd(a, b − a) = mcd(a, a + b).

Corolario
Sean a, b, n ∈ Z. Entonces mcd(a, b) = mcd(a, b − an).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 15 / 82

Contenido

1 El anillo de los enteros: Divisibilidad

Divisibilidad
El máximo común divisor
El Algoritmo de la División
El mı́nimo común múltiplo
Ecuaciones diofantinas
El Teorema Fundamental de la Aritmética
Los enteros módulo n y la aritmética modular

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 16 / 82

Algoritmo de la División

Teorema
Si a, b ∈ Z y b 6= 0, entonces existen q, r ∈ Z, únicos, tales que

a = bq + r con 0 ≤ r < |b| .

r es el residuo, q el cociente.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 17 / 82

Calculo del residuo y del cociente

Corolario
Sean a, b ∈ Z con b 6= 0. Sea

a/b
 si ba/bc = a/b,
q = ba/bc si b > 0,

ba/bc + 1 si b < 0


y r = a − bq. Entonces

a = bq + r , con 0 ≤ r < |b| ,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 18 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r=

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

q = b14/20c

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

q = b14/20c = 0

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

q = b14/20c = 0
r = a − bq

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

q = b14/20c = 0
r = a − bq = 14

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

q = b14/20c = 0
r = a − bq = 14

3 Si a = 80 y b = −35, entonces

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

q = b14/20c = 0
r = a − bq = 14

3 Si a = 80 y b = −35, entonces

q = b80/(−35)c + 1

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

q = b14/20c = 0
r = a − bq = 14

3 Si a = 80 y b = −35, entonces

q = b80/(−35)c + 1 = −2

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

q = b14/20c = 0
r = a − bq = 14

3 Si a = 80 y b = −35, entonces

q = b80/(−35)c + 1 = −2
r = 80 − (−35)(−2)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = 20 y b = 3, entonces

q = b20/3c = b6 + 2/3c = 6
r = a − bq = 20 − 18 = 2

2 Si a = 14 y b = 20, entonces

q = b14/20c = 0
r = a − bq = 14

3 Si a = 80 y b = −35, entonces

q = b80/(−35)c + 1 = −2
r = 80 − (−35)(−2) = 10

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 19 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

q = b−35/ − 80c + 1

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

q = b−35/ − 80c + 1 = 1

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

q = b−35/ − 80c + 1 = 1
r = −35 − (−80) · 1

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

q = b−35/ − 80c + 1 = 1
r = −35 − (−80) · 1 = 45

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

q = b−35/ − 80c + 1 = 1
r = −35 − (−80) · 1 = 45

2 Si a = −42 y b = −13, entonces

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

q = b−35/ − 80c + 1 = 1
r = −35 − (−80) · 1 = 45

2 Si a = −42 y b = −13, entonces

q = b(−42)/(−13)c + 1

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

q = b−35/ − 80c + 1 = 1
r = −35 − (−80) · 1 = 45

2 Si a = −42 y b = −13, entonces

q = b(−42)/(−13)c + 1 = 4

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

q = b−35/ − 80c + 1 = 1
r = −35 − (−80) · 1 = 45

2 Si a = −42 y b = −13, entonces

q = b(−42)/(−13)c + 1 = 4
r = a − bq = −42 − (−13)(4)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejemplos

1 Si a = −35 y b = −80, entonces

q = b−35/ − 80c + 1 = 1
r = −35 − (−80) · 1 = 45

2 Si a = −42 y b = −13, entonces

q = b(−42)/(−13)c + 1 = 4
r = a − bq = −42 − (−13)(4) = 10

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 20 / 82

Ejercicio

Ejercicio
Sean a, b, q, r enteros tales que

a = bq + r .

Pruebe que el conjunto de divisores de a y b es igual al conjunto de

divisores de b y r .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 21 / 82

Cálculo del mcd

Ejemplo

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)
581 = 147 · 3 + 140,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)
581 = 147 · 3 + 140, mcd(581, 147) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)
581 = 147 · 3 + 140, mcd(581, 147) = mcd(147, 140)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)
581 = 147 · 3 + 140, mcd(581, 147) = mcd(147, 140)
147 = 140 · 1 + 7,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)
581 = 147 · 3 + 140, mcd(581, 147) = mcd(147, 140)
147 = 140 · 1 + 7, mcd(147, 140) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)
581 = 147 · 3 + 140, mcd(581, 147) = mcd(147, 140)
147 = 140 · 1 + 7, mcd(147, 140) = mcd(140, 7)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)
581 = 147 · 3 + 140, mcd(581, 147) = mcd(147, 140)
147 = 140 · 1 + 7, mcd(147, 140) = mcd(140, 7)
140 = 7 · 20 + 0,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)
581 = 147 · 3 + 140, mcd(581, 147) = mcd(147, 140)
147 = 140 · 1 + 7, mcd(147, 140) = mcd(140, 7)
140 = 7 · 20 + 0, mcd(140, 7) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Cálculo del mcd

Ejemplo
1) Calcular mcd(4655, 1309).

4655 = 1309 · 3 + 728, mcd(4655, 1309) = mcd(1309, 728)

1309 = 728 · 1 + 581, mcd(1309, 728) = mcd(728, 581)
728 = 581 · 1 + 147, mcd(728, 581) = mcd(581, 147)
581 = 147 · 3 + 140, mcd(581, 147) = mcd(147, 140)
147 = 140 · 1 + 7, mcd(147, 140) = mcd(140, 7)
140 = 7 · 20 + 0, mcd(140, 7) = mcd(7, 0) = 7.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 22 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 ,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 ,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 , 0 ≤ r1 < r0 , (1)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 , 0 ≤ r1 < r0 , (1)
r0 = r1 q2 + r2 ,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 , 0 ≤ r1 < r0 , (1)
r0 = r1 q2 + r2 , 0 ≤ r2 < r1 , (2)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 , 0 ≤ r1 < r0 , (1)
r0 = r1 q2 + r2 , 0 ≤ r2 < r1 , (2)
..
.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 , 0 ≤ r1 < r0 , (1)
r0 = r1 q2 + r2 , 0 ≤ r2 < r1 , (2)
..
.
rn−2 = rn−1 qn + rn ,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 , 0 ≤ r1 < r0 , (1)
r0 = r1 q2 + r2 , 0 ≤ r2 < r1 , (2)
..
.
rn−2 = rn−1 qn + rn , 0 ≤ rn < rn−1 , (n)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 , 0 ≤ r1 < r0 , (1)
r0 = r1 q2 + r2 , 0 ≤ r2 < r1 , (2)
..
.
rn−2 = rn−1 qn + rn , 0 ≤ rn < rn−1 , (n)
rn−1 = rn qn+1 , (n+1)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 , 0 ≤ r1 < r0 , (1)
r0 = r1 q2 + r2 , 0 ≤ r2 < r1 , (2)
..
.
rn−2 = rn−1 qn + rn , 0 ≤ rn < rn−1 , (n)
rn−1 = rn qn+1 , (n+1)

donde rn es el último residuo distinto de cero

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82

Algoritmo de Euclides para el cálculo del mcd(a, b)
1 Mediante la aplicación repetida del Algoritmo de la División se
obtiene una sucesión de cocientes y residuos
a = bq0 + r0 , 0 ≤ r0 < |b| , (0)
b = r0 q1 + r1 , 0 ≤ r1 < r0 , (1)
r0 = r1 q2 + r2 , 0 ≤ r2 < r1 , (2)
..
.
rn−2 = rn−1 qn + rn , 0 ≤ rn < rn−1 , (n)
rn−1 = rn qn+1 , (n+1)

donde rn es el último residuo distinto de cero

2 Entonces rn = mcd(a, b)
Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 23 / 82
Ejercicio

Ejercicio
Usando el algoritmo de Euclides, calcule el máximo común divisor de
a = 2431 y b = 4807.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 24 / 82

El mcd(a, b) es una combinación lineal de a y b

Teorema
Si a, b ∈ Z, entonces existen enteros x, y tales que

mcd(a, b) = ax + by .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 25 / 82

El mcd(a, b) es una combinación lineal de a y b

Teorema
Si a, b ∈ Z, entonces existen enteros x, y tales que

mcd(a, b) = ax + by .

Corolario
Un entero c es combinación lineal de a y b si y solamente si
mcd(a, b) | c.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 25 / 82

Expresión del mcd(a, b) como combinación lineal

1 Se tiene

4655 = 1309 · 3 + 728, (0)

1309 = 728 · 1 + 581, (1)
728 = 581 · 1 + 147, (2)
581 = 147 · 3 + 140, (3)
147 = 140 · 1 + 7, (4)
140 = 7 · 20. (5)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 26 / 82

Expresión del mcd(a, b) como combinación lineal

1 Se tiene

4655 = 1309 · 3 + 728, (0)

1309 = 728 · 1 + 581, (1)
728 = 581 · 1 + 147, (2)
581 = 147 · 3 + 140, (3)
147 = 140 · 1 + 7, (4)
140 = 7 · 20. (5)

2 mcd(4655, 1309) = 7.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 26 / 82

Expresión del mcd(a, b) como combinación lineal

1 Se tiene

4655 = 1309 · 3 + 728, (0)

1309 = 728 · 1 + 581, (1)
728 = 581 · 1 + 147, (2)
581 = 147 · 3 + 140, (3)
147 = 140 · 1 + 7, (4)
140 = 7 · 20. (5)

2 mcd(4655, 1309) = 7.
3 mcd(4655, 1309) = 4655(9) + 1309(−32)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 26 / 82

Ejercicios

1 Exprese el mcd(a, b) de como combinación lineal de a y b:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 27 / 82

Ejercicios

1 Exprese el mcd(a, b) de como combinación lineal de a y b:

1 a = 17670, b = 6290

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 27 / 82

Ejercicios

1 Exprese el mcd(a, b) de como combinación lineal de a y b:

1 a = 17670, b = 6290
2 a = 3026, b = 9962

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 27 / 82

Ejercicios

1 Exprese el mcd(a, b) de como combinación lineal de a y b:

1 a = 17670, b = 6290
2 a = 3026, b = 9962
2 Solución:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 27 / 82

Ejercicios

1 Exprese el mcd(a, b) de como combinación lineal de a y b:

1 a = 17670, b = 6290
2 a = 3026, b = 9962
2 Solución:

mcd(17670, 6290) = 10

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 27 / 82

Ejercicios

1 Exprese el mcd(a, b) de como combinación lineal de a y b:

1 a = 17670, b = 6290
2 a = 3026, b = 9962
2 Solución:

mcd(17670, 6290) = 10
10 = 17670(152) + 6290(−427)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 27 / 82

Ejercicios

1 Exprese el mcd(a, b) de como combinación lineal de a y b:

1 a = 17670, b = 6290
2 a = 3026, b = 9962
2 Solución:

mcd(17670, 6290) = 10
10 = 17670(152) + 6290(−427)

mcd(3026, 9962) = 34

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 27 / 82

Ejercicios

1 Exprese el mcd(a, b) de como combinación lineal de a y b:

1 a = 17670, b = 6290
2 a = 3026, b = 9962
2 Solución:

mcd(17670, 6290) = 10
10 = 17670(152) + 6290(−427)

mcd(3026, 9962) = 34
34 = 3026(−79) + 9962(24)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 27 / 82

Combinaciones lineales y el mcd

1 ¿Cualquier combinación lineal de a y b es un máximo común

divisor?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 28 / 82

Combinaciones lineales y el mcd

1 ¿Cualquier combinación lineal de a y b es un máximo común

divisor?
2 ¿Como saber que una combinación lineal es el máximo común
divisor?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 28 / 82

Combinaciones lineales y el mcd

1 ¿Cualquier combinación lineal de a y b es un máximo común

divisor?
2 ¿Como saber que una combinación lineal es el máximo común
divisor?
3 Si a = 2210 y b = 980, ¿Es alguno de los siguientes números un
mcd?

20 = a · 4 + b · (−9),

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 28 / 82

Combinaciones lineales y el mcd

1 ¿Cualquier combinación lineal de a y b es un máximo común

divisor?
2 ¿Como saber que una combinación lineal es el máximo común
divisor?
3 Si a = 2210 y b = 980, ¿Es alguno de los siguientes números un
mcd?

20 = a · 4 + b · (−9), 10 = a · (−47) + b · 106

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 28 / 82

Combinaciones lineales y el mcd

1 ¿Cualquier combinación lineal de a y b es un máximo común

divisor?
2 ¿Como saber que una combinación lineal es el máximo común
divisor?
3 Si a = 2210 y b = 980, ¿Es alguno de los siguientes números un
mcd?

20 = a · 4 + b · (−9), 10 = a · (−47) + b · 106

30 = a · (−43) + b · 97,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 28 / 82

Combinaciones lineales y el mcd

1 ¿Cualquier combinación lineal de a y b es un máximo común

divisor?
2 ¿Como saber que una combinación lineal es el máximo común
divisor?
3 Si a = 2210 y b = 980, ¿Es alguno de los siguientes números un
mcd?

20 = a · 4 + b · (−9), 10 = a · (−47) + b · 106

30 = a · (−43) + b · 97, 40 = a · 8 + b · (−18),

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 28 / 82

Combinaciones lineales y el mcd

1 ¿Cualquier combinación lineal de a y b es un máximo común

divisor?
2 ¿Como saber que una combinación lineal es el máximo común
divisor?
3 Si a = 2210 y b = 980, ¿Es alguno de los siguientes números un
mcd?

20 = a · 4 + b · (−9), 10 = a · (−47) + b · 106

30 = a · (−43) + b · 97, 40 = a · 8 + b · (−18),
50 = a · (−39) + b · (88),

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 28 / 82

Combinaciones lineales y el mcd

1 ¿Cualquier combinación lineal de a y b es un máximo común

divisor?
2 ¿Como saber que una combinación lineal es el máximo común
divisor?
3 Si a = 2210 y b = 980, ¿Es alguno de los siguientes números un
mcd?

20 = a · 4 + b · (−9), 10 = a · (−47) + b · 106

30 = a · (−43) + b · 97, 40 = a · 8 + b · (−18),
50 = a · (−39) + b · (88), 60 = a · 12 + b · (−27).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 28 / 82

El mcd(a, b) es la combinación lineal positiva mı́nima

Teorema
Si a y b son enteros positivos y d = ax + by es su combinación lineal
positiva mı́nima, entonces d = mcd(a, b).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 29 / 82

El mcd(a, b) es la combinación lineal positiva mı́nima

Teorema
Si a y b son enteros positivos y d = ax + by es su combinación lineal
positiva mı́nima, entonces d = mcd(a, b).

Ejemplo

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 29 / 82

El mcd(a, b) es la combinación lineal positiva mı́nima

Teorema
Si a y b son enteros positivos y d = ax + by es su combinación lineal
positiva mı́nima, entonces d = mcd(a, b).

Ejemplo
1 Sean a = 2210 y b = 980. Se tiene

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 29 / 82

El mcd(a, b) es la combinación lineal positiva mı́nima

Teorema
Si a y b son enteros positivos y d = ax + by es su combinación lineal
positiva mı́nima, entonces d = mcd(a, b).

Ejemplo
1 Sean a = 2210 y b = 980. Se tiene

20 = a · 4 + b · (−9)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 29 / 82

El mcd(a, b) es la combinación lineal positiva mı́nima

Teorema
Si a y b son enteros positivos y d = ax + by es su combinación lineal
positiva mı́nima, entonces d = mcd(a, b).

Ejemplo
1 Sean a = 2210 y b = 980. Se tiene

20 = a · 4 + b · (−9)
10 = a · (−47) + b · 106

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 29 / 82

El mcd(a, b) es la combinación lineal positiva mı́nima

Teorema
Si a y b son enteros positivos y d = ax + by es su combinación lineal
positiva mı́nima, entonces d = mcd(a, b).

Ejemplo
1 Sean a = 2210 y b = 980. Se tiene

20 = a · 4 + b · (−9)
10 = a · (−47) + b · 106
30 = a · (−43) + b · 97

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 29 / 82

El mcd(a, b) es la combinación lineal positiva mı́nima

Teorema
Si a y b son enteros positivos y d = ax + by es su combinación lineal
positiva mı́nima, entonces d = mcd(a, b).

Ejemplo
1 Sean a = 2210 y b = 980. Se tiene

20 = a · 4 + b · (−9)
10 = a · (−47) + b · 106
30 = a · (−43) + b · 97

2 ¿Es 30 el máximo común divisor de a y b?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 29 / 82

El mcd(a, b) es la combinación lineal positiva mı́nima

Teorema
Si a y b son enteros positivos y d = ax + by es su combinación lineal
positiva mı́nima, entonces d = mcd(a, b).

Ejemplo
1 Sean a = 2210 y b = 980. Se tiene

20 = a · 4 + b · (−9)
10 = a · (−47) + b · 106
30 = a · (−43) + b · 97

2 ¿Es 30 el máximo común divisor de a y b?

3 ¿Se puede saber cuál es el máximo común divisor de a y b?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 29 / 82

Ejemplo

1 Sean a = 1463 y b = 5083.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 30 / 82

Ejemplo

1 Sean a = 1463 y b = 5083.

2 Se tiene

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 30 / 82

Ejemplo

1 Sean a = 1463 y b = 5083.

2 Se tiene

75 = a · 7 + b · (−2),

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 30 / 82

Ejemplo

1 Sean a = 1463 y b = 5083.

2 Se tiene

75 = a · 7 + b · (−2),
1 = a · (−271) + b · 78

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 30 / 82

Ejemplo

1 Sean a = 1463 y b = 5083.

2 Se tiene

75 = a · 7 + b · (−2),
1 = a · (−271) + b · 78
2 = a · (9624) + b · (−2770)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 30 / 82

Ejemplo

1 Sean a = 1463 y b = 5083.

2 Se tiene

75 = a · 7 + b · (−2),
1 = a · (−271) + b · 78
2 = a · (9624) + b · (−2770)

3 ¿Cuál es el máximo común divisor de a y b?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 30 / 82

Equivalencias del mcd

Teorema
Sean a, b y d > 0 enteros. La siguientes afirmaciones son
equivalentes:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 31 / 82

Equivalencias del mcd

Teorema
Sean a, b y d > 0 enteros. La siguientes afirmaciones son
equivalentes:
1) d = mcd(a, b).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 31 / 82

Equivalencias del mcd

Teorema
Sean a, b y d > 0 enteros. La siguientes afirmaciones son
equivalentes:
1) d = mcd(a, b).
2) d es la combinación lineal positiva mı́nima de a y b.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 31 / 82

Equivalencias del mcd

Teorema
Sean a, b y d > 0 enteros. La siguientes afirmaciones son
equivalentes:
1) d = mcd(a, b).
2) d es la combinación lineal positiva mı́nima de a y b.
3) d | a, d | b, y si c | a y c | b, entonces c | d.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 31 / 82

Equivalencias del mcd

Teorema
Sean a, b y d > 0 enteros. La siguientes afirmaciones son
equivalentes:
1) d = mcd(a, b).
2) d es la combinación lineal positiva mı́nima de a y b.
3) d | a, d | b, y si c | a y c | b, entonces c | d.
4) d | a, d | b, y d es combinación lineal de a y b.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 31 / 82

Ejemplo

Ejemplo

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 32 / 82

Ejemplo

Ejemplo
1 Sean a = 2210 y b = 980. Se tiene

20 = a · 4 + b · (−9)
10 = a · (−47) + b · 106
30 = a · (−43) + b · 97

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 32 / 82

Ejemplo

Ejemplo
1 Sean a = 2210 y b = 980. Se tiene

20 = a · 4 + b · (−9)
10 = a · (−47) + b · 106
30 = a · (−43) + b · 97

2 ¿Se puede saber cuál es el máximo común divisor de a y b?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 32 / 82

Números primos relativos

1 Dos enteros a y b son primos relativos, primos entre sı́ o coprimos

si su máximo común divisor es 1.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 33 / 82

Números primos relativos

1 Dos enteros a y b son primos relativos, primos entre sı́ o coprimos

si su máximo común divisor es 1.
2 ¿Son 2 y 3 primos relativos?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 33 / 82

Números primos relativos

1 Dos enteros a y b son primos relativos, primos entre sı́ o coprimos

si su máximo común divisor es 1.
2 ¿Son 2 y 3 primos relativos?
3 ¿Son 6 y 35 primos relativos?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 33 / 82

Números primos relativos

1 Dos enteros a y b son primos relativos, primos entre sı́ o coprimos

si su máximo común divisor es 1.
2 ¿Son 2 y 3 primos relativos?
3 ¿Son 6 y 35 primos relativos?
4 ¿Son 6 y 10 primos relativos?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 33 / 82

Números primos relativos

1 Dos enteros a y b son primos relativos, primos entre sı́ o coprimos

si su máximo común divisor es 1.
2 ¿Son 2 y 3 primos relativos?
3 ¿Son 6 y 35 primos relativos?
4 ¿Son 6 y 10 primos relativos?
5 Los números a = 2683 y b = 5284 satisfacen la relación

1 = a(1611) + b(−818).

¿Son a y b primos relativos?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 33 / 82

Números primos relativos

1 Dos enteros a y b son primos relativos, primos entre sı́ o coprimos

si su máximo común divisor es 1.
2 ¿Son 2 y 3 primos relativos?
3 ¿Son 6 y 35 primos relativos?
4 ¿Son 6 y 10 primos relativos?
5 Los números a = 2683 y b = 5284 satisfacen la relación

1 = a(1611) + b(−818).

¿Son a y b primos relativos?

6 ¿Es posible escribir 1 como combinación lineal de 66 y 35?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 33 / 82

Primos relativos

Teorema
Los enteros a y b son primos relativos si y solamente si existen
enteros x, y tales que

1 = ax + by .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 34 / 82

Primos relativos

Teorema
Los enteros a y b son primos relativos si y solamente si existen
enteros x, y tales que

1 = ax + by .

Teorema
Si a | bc y mcd(a, b) = 1, entonces a | c.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 34 / 82

Primos relativos

Teorema
Los enteros a y b son primos relativos si y solamente si existen
enteros x, y tales que

1 = ax + by .

Teorema
Si a | bc y mcd(a, b) = 1, entonces a | c.

Ejercicio
Pruebe que si a y b son primos relativos y a | c y b | c, entonces ab | c.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 34 / 82

Contenido

1 El anillo de los enteros: Divisibilidad

Divisibilidad
El máximo común divisor
El Algoritmo de la División
El mı́nimo común múltiplo
Ecuaciones diofantinas
El Teorema Fundamental de la Aritmética
Los enteros módulo n y la aritmética modular

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 35 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b ⇐⇒ b = aq, q ∈ Z

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b ⇐⇒ b = aq, q ∈ Z

2 Sean a, b ∈ Z. ¿Existen múltiplos comunes de a y b?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b ⇐⇒ b = aq, q ∈ Z

2 Sean a, b ∈ Z. ¿Existen múltiplos comunes de a y b?

3 Si a = 5 y b = −7, el conjunto de múltiplos comunes es

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b ⇐⇒ b = aq, q ∈ Z

2 Sean a, b ∈ Z. ¿Existen múltiplos comunes de a y b?

3 Si a = 5 y b = −7, el conjunto de múltiplos comunes es

{. . . , −70, −35, 0, 35, 70, . . . }

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b ⇐⇒ b = aq, q ∈ Z

2 Sean a, b ∈ Z. ¿Existen múltiplos comunes de a y b?

3 Si a = 5 y b = −7, el conjunto de múltiplos comunes es

{. . . , −70, −35, 0, 35, 70, . . . }

4 si a = 0 y b = 2, el conjunto de múltiplos comunes es

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b ⇐⇒ b = aq, q ∈ Z

2 Sean a, b ∈ Z. ¿Existen múltiplos comunes de a y b?

3 Si a = 5 y b = −7, el conjunto de múltiplos comunes es

{. . . , −70, −35, 0, 35, 70, . . . }

4 si a = 0 y b = 2, el conjunto de múltiplos comunes es

{0}

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b ⇐⇒ b = aq, q ∈ Z

2 Sean a, b ∈ Z. ¿Existen múltiplos comunes de a y b?

3 Si a = 5 y b = −7, el conjunto de múltiplos comunes es

{. . . , −70, −35, 0, 35, 70, . . . }

4 si a = 0 y b = 2, el conjunto de múltiplos comunes es

{0}

5 Si a 6= 0 6= b, ¿Existen múltiplos comunes de a y b?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b ⇐⇒ b = aq, q ∈ Z

2 Sean a, b ∈ Z. ¿Existen múltiplos comunes de a y b?

3 Si a = 5 y b = −7, el conjunto de múltiplos comunes es

{. . . , −70, −35, 0, 35, 70, . . . }

4 si a = 0 y b = 2, el conjunto de múltiplos comunes es

{0}

5 Si a 6= 0 6= b, ¿Existen múltiplos comunes de a y b?

6 Si a = y b 6= 0, ¿Existen múltiplos comunes de a y b?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 Recordatorio: b múltiplo de a si

a|b ⇐⇒ b = aq, q ∈ Z

2 Sean a, b ∈ Z. ¿Existen múltiplos comunes de a y b?

3 Si a = 5 y b = −7, el conjunto de múltiplos comunes es

{. . . , −70, −35, 0, 35, 70, . . . }

4 si a = 0 y b = 2, el conjunto de múltiplos comunes es

{0}

5 Si a 6= 0 6= b, ¿Existen múltiplos comunes de a y b?

6 Si a = y b 6= 0, ¿Existen múltiplos comunes de a y b?
7 Si a = 0 = b, ¿Existen múltiplos comunes?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 36 / 82

El mı́nimo común múltiplo

1 El mı́nimo común múltiplo de los enteros a y b es

(
mı́n{m ∈ Z+ : a | m y b | m} si ab 6= 0
mcm(a, b) =
0 otro caso

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 37 / 82

El mı́nimo común múltiplo

1 El mı́nimo común múltiplo de los enteros a y b es

(
mı́n{m ∈ Z+ : a | m y b | m} si ab 6= 0
mcm(a, b) =
0 otro caso

2 Si ab 6= 0, mcm(a, b) = mı́n{m ∈ Z+ : a | m} ∩ {m ∈ Z+ : b | m}.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 37 / 82

El mı́nimo común múltiplo

1 El mı́nimo común múltiplo de los enteros a y b es

(
mı́n{m ∈ Z+ : a | m y b | m} si ab 6= 0
mcm(a, b) =
0 otro caso

2 Si ab 6= 0, mcm(a, b) = mı́n{m ∈ Z+ : a | m} ∩ {m ∈ Z+ : b | m}.

3 De la definición es inmediato que mcm(a, b) = mcm(b, a).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 37 / 82

El mı́nimo común múltiplo

1 El mı́nimo común múltiplo de los enteros a y b es

(
mı́n{m ∈ Z+ : a | m y b | m} si ab 6= 0
mcm(a, b) =
0 otro caso

2 Si ab 6= 0, mcm(a, b) = mı́n{m ∈ Z+ : a | m} ∩ {m ∈ Z+ : b | m}.

3 De la definición es inmediato que mcm(a, b) = mcm(b, a).
4 Otra notación para mcm(a, b) es [a, b]

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 37 / 82

Ejemplo

1 Si a = −4 y b = 6, el conjunto de los múltiplos positivos comunes

es

{4, 8, 12, 16, 20, 24, . . . } ∩ {6, 12, 18, 24, 30, 36 . . . }
= {12, 24, 36, . . . }

2 mcm(a, b) = 12.
3 Con la ayuda de SageMath:

sage: lcm(-4,6)
12

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 38 / 82

Caracterización del mcm

Teorema
Sean a, b ∈ Z − {0}. El mı́nimo común múltiplo de a y b es el único
entero positivo m que satisface las siguientes condiciones:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 39 / 82

Caracterización del mcm

Teorema
Sean a, b ∈ Z − {0}. El mı́nimo común múltiplo de a y b es el único
entero positivo m que satisface las siguientes condiciones:
1 a | m y b | m;

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 39 / 82

Caracterización del mcm

Teorema
Sean a, b ∈ Z − {0}. El mı́nimo común múltiplo de a y b es el único
entero positivo m que satisface las siguientes condiciones:
1 a | m y b | m;
2 Si a | m0 y b | m0 , entonces m | m0 .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 39 / 82

Relación entre el mcd y el mcm

Teorema
Si a y b son enteros positivos, entonces

ab = mcd(a, b) mcm(a, b)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 40 / 82

Contenido

1 El anillo de los enteros: Divisibilidad

Divisibilidad
El máximo común divisor
El Algoritmo de la División
El mı́nimo común múltiplo
Ecuaciones diofantinas
El Teorema Fundamental de la Aritmética
Los enteros módulo n y la aritmética modular

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 41 / 82

Soluciones enteras de ax + by = c

Teorema

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 42 / 82

Soluciones enteras de ax + by = c

Teorema
1 La ecuación Diofantina

ax + by = c (a, b, c ∈ Z) (*)

tiene solución entera si y solamente si mcd(a, b) | c.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 42 / 82

Soluciones enteras de ax + by = c

Teorema
1 La ecuación Diofantina

ax + by = c (a, b, c ∈ Z) (*)

tiene solución entera si y solamente si mcd(a, b) | c.

2 Si a 6= 0 o b 6= 0, mcd(a, b) | c y mcd(a, b) = ar + bs, una
solución de (*) es
rc sc
x0 = , y0 =
mcd(a, b) mcd(a, b)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 42 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.
2 Si tiene solución, encuentre una solución particular.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.
2 Si tiene solución, encuentre una solución particular.
1 6x + 8y = 30

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.
2 Si tiene solución, encuentre una solución particular.
1 6x + 8y = 30
2 6x + 8y = 3

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.
2 Si tiene solución, encuentre una solución particular.
1 6x + 8y = 30
2 6x + 8y = 3
3 −18x + 10y = 28

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.
2 Si tiene solución, encuentre una solución particular.
1 6x + 8y = 30
2 6x + 8y = 3
3 −18x + 10y = 28
4 2x + 3y = 0

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.
2 Si tiene solución, encuentre una solución particular.
1 6x + 8y = 30
2 6x + 8y = 3
3 −18x + 10y = 28
4 2x + 3y = 0
5 ax + by = 0

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.
2 Si tiene solución, encuentre una solución particular.
1 6x + 8y = 30
2 6x + 8y = 3
3 −18x + 10y = 28
4 2x + 3y = 0
5 ax + by = 0
6 3x = 18

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.
2 Si tiene solución, encuentre una solución particular.
1 6x + 8y = 30
2 6x + 8y = 3
3 −18x + 10y = 28
4 2x + 3y = 0
5 ax + by = 0
6 3x = 18
7 4x = 18

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Determine cuál o cuales de las siguientes ecuaciones diofantinas

tiene solución.
2 Si tiene solución, encuentre una solución particular.
1 6x + 8y = 30
2 6x + 8y = 3
3 −18x + 10y = 28
4 2x + 3y = 0
5 ax + by = 0
6 3x = 18
7 4x = 18
8 ax + 0y = c

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 43 / 82

Ejemplos

1 Si una ecuación tiene solución, la solución no necesariamente es

única.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 44 / 82

Ejemplos

1 Si una ecuación tiene solución, la solución no necesariamente es

única.
2 La ecuación 6x + 8y = 30 tiene más de una solución:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 44 / 82

Ejemplos

1 Si una ecuación tiene solución, la solución no necesariamente es

única.
2 La ecuación 6x + 8y = 30 tiene más de una solución:

6(1) + 8(3) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 44 / 82

Ejemplos

1 Si una ecuación tiene solución, la solución no necesariamente es

única.
2 La ecuación 6x + 8y = 30 tiene más de una solución:

6(1) + 8(3) = 30

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 44 / 82

Ejemplos

1 Si una ecuación tiene solución, la solución no necesariamente es

única.
2 La ecuación 6x + 8y = 30 tiene más de una solución:

6(1) + 8(3) = 30
6(−15) + 8(15) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 44 / 82

Ejemplos

1 Si una ecuación tiene solución, la solución no necesariamente es

única.
2 La ecuación 6x + 8y = 30 tiene más de una solución:

6(1) + 8(3) = 30
6(−15) + 8(15) = 30

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 44 / 82

Ejemplos

1 Si una ecuación tiene solución, la solución no necesariamente es

única.
2 La ecuación 6x + 8y = 30 tiene más de una solución:

6(1) + 8(3) = 30
6(−15) + 8(15) = 30
6(−7) + 8(9) =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 44 / 82

Ejemplos

1 Si una ecuación tiene solución, la solución no necesariamente es

única.
2 La ecuación 6x + 8y = 30 tiene más de una solución:

6(1) + 8(3) = 30
6(−15) + 8(15) = 30
6(−7) + 8(9) = 30

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 44 / 82

Ejemplos

1 Si una ecuación tiene solución, la solución no necesariamente es

única.
2 La ecuación 6x + 8y = 30 tiene más de una solución:

6(1) + 8(3) = 30
6(−15) + 8(15) = 30
6(−7) + 8(9) = 30

Ejercicio
Sean a, b ∈ Z no ambos cero y sea d = mcd(a, b). Pruebe que a/d y
b/d son primos relativos.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 44 / 82

Conjunto solución

Teorema
Si la ecuación diofantina ax + by = c tiene solución, entonces el
conjunto de todas las soluciones es

b a
x = x0 + t , y = y0 − t , t ∈ Z,
mcd(a, b) mcd(a, b)

donde (x0 , y0 ) es una solución particular. También se escribe

   
b a
S = (x0 , y0 ) + t ,− |t ∈Z
mcd(a, b) mcd(a, b)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 45 / 82

Ejemplo

1 Encuentre todas las soluciones de la ecuación 2x − 4y = 4.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 46 / 82

Ejemplo

1 Encuentre todas las soluciones de la ecuación 2x − 4y = 4.

1 mcd(2, −4) = 2 = 2(1) + 4(0)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 46 / 82

Ejemplo

1 Encuentre todas las soluciones de la ecuación 2x − 4y = 4.

1 mcd(2, −4) = 2 = 2(1) + 4(0)
2 Solución particular (x0 , y0 ) = ( 1·4 0·4
2 , 2 ) = (2, 0).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 46 / 82

Ejemplo

1 Encuentre todas las soluciones de la ecuación 2x − 4y = 4.

1 mcd(2, −4) = 2 = 2(1) + 4(0)
2 Solución particular (x0 , y0 ) = ( 1·4 0·4
2 , 2 ) = (2, 0).
3 El conjunto solución:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 46 / 82

Ejemplo

1 Encuentre todas las soluciones de la ecuación 2x − 4y = 4.

1 mcd(2, −4) = 2 = 2(1) + 4(0)
2 Solución particular (x0 , y0 ) = ( 1·4 0·4
2 , 2 ) = (2, 0).
3 El conjunto solución:

S = {(x, y) ∈ Z × Z : x = 2 − 2t, y = −t, t ∈ Z}

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 46 / 82

Ejemplo

1 Encuentre todas las soluciones de la ecuación 2x − 4y = 4.

1 mcd(2, −4) = 2 = 2(1) + 4(0)
2 Solución particular (x0 , y0 ) = ( 1·4 0·4
2 , 2 ) = (2, 0).
3 El conjunto solución:

S = {(x, y) ∈ Z × Z : x = 2 − 2t, y = −t, t ∈ Z}

= {(2 − 2t, −t) : t ∈ Z}

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 46 / 82

Ejemplo

1 Encuentre todas las soluciones de la ecuación 2x − 4y = 4.

1 mcd(2, −4) = 2 = 2(1) + 4(0)
2 Solución particular (x0 , y0 ) = ( 1·4 0·4
2 , 2 ) = (2, 0).
3 El conjunto solución:

S = {(x, y) ∈ Z × Z : x = 2 − 2t, y = −t, t ∈ Z}

= {(2 − 2t, −t) : t ∈ Z}
= (2, 0) + {t(−2, −1) | t ∈ Z}

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 46 / 82

Gráfica del conjunto solución de 2x − 4y = 4

y
3

2x − 4y = 4 2

(6, 2)
1

(4, 1)
−6 −4 −2
(2, 0)
6
x
(0, −1)

(−2, −2)
−3

(−4, −3)
−4

(−6, −4)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 47 / 82

Contenido

1 El anillo de los enteros: Divisibilidad

Divisibilidad
El máximo común divisor
El Algoritmo de la División
El mı́nimo común múltiplo
Ecuaciones diofantinas
El Teorema Fundamental de la Aritmética
Los enteros módulo n y la aritmética modular

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 48 / 82

Los números primos

1 Los números primos son los bloques básicos de construcción de

los números (y de los números racionales, reales, etc)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 49 / 82

Los números primos

1 Los números primos son los bloques básicos de construcción de

los números (y de los números racionales, reales, etc)
2 Teorema Fundamental de la Aritmética Cada entero distinto de 1
y −1 se puede escribir como un producto de números primos.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 49 / 82

Los números primos

1 Los números primos son los bloques básicos de construcción de

los números (y de los números racionales, reales, etc)
2 Teorema Fundamental de la Aritmética Cada entero distinto de 1
y −1 se puede escribir como un producto de números primos.
3 Es fácil multiplicar números.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 49 / 82

Los números primos

1 Los números primos son los bloques básicos de construcción de

los números (y de los números racionales, reales, etc)
2 Teorema Fundamental de la Aritmética Cada entero distinto de 1
y −1 se puede escribir como un producto de números primos.
3 Es fácil multiplicar números.
4 Es difı́cil factorizar números

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 49 / 82

Los números primos

1 Los números primos son los bloques básicos de construcción de

los números (y de los números racionales, reales, etc)
2 Teorema Fundamental de la Aritmética Cada entero distinto de 1
y −1 se puede escribir como un producto de números primos.
3 Es fácil multiplicar números.
4 Es difı́cil factorizar números
5 ¿No lo creen?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 49 / 82

Los números primos

1 Los números primos son los bloques básicos de construcción de

los números (y de los números racionales, reales, etc)
2 Teorema Fundamental de la Aritmética Cada entero distinto de 1
y −1 se puede escribir como un producto de números primos.
3 Es fácil multiplicar números.
4 Es difı́cil factorizar números
5 ¿No lo creen?
6 Veamos un ejemplo en SageMath con la instrucción
random prime()

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 49 / 82

Don Zagier (1975)

1 “Hay dos hechos sorprendentes acerca de la distribución de los

números primos.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 50 / 82

Don Zagier (1975)

1 “Hay dos hechos sorprendentes acerca de la distribución de los

números primos.
2 El primero es que, a pesar de su definición tan simple y su papel
como los bloques a partir de los cuales se construyen los
números naturales, son los objetos más arbitrarios y engañosos
estudiados por los matemáticos: crecen como hierba entre los
números naturales, y parece que no obedecen ninguna ley
excepto a la casualidad, y nadie puede predecir donde brotará el
siguiente número primo.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 50 / 82

Don Zagier (1975)

1 “Hay dos hechos sorprendentes acerca de la distribución de los

números primos.
2 El primero es que, a pesar de su definición tan simple y su papel
como los bloques a partir de los cuales se construyen los
números naturales, son los objetos más arbitrarios y engañosos
estudiados por los matemáticos: crecen como hierba entre los
números naturales, y parece que no obedecen ninguna ley
excepto a la casualidad, y nadie puede predecir donde brotará el
siguiente número primo.
3 El segundo hecho es aún más increı́ble, porque es exactamente
opuesto al primero: los números primos exhiben una regularidad
impresionante ası́ que hay leyes que gobiernan su
comportamiento, y que obedecen a estas leyes con precisión casi
militar”.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 50 / 82

La función zeta
1 La función zeta está definida por la serie
1 1 1
ζ(s) = 1 + + s + s + ···
2s 3 4

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 51 / 82

La función zeta
1 La función zeta está definida por la serie
1 1 1
ζ(s) = 1 + + s + s + ···
2s 3 4
2 Fórmula del producto de Euler
∞ Y 1 −1

X 1
ζ(s) = = 1− s ,
ns p
p
n=1

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 51 / 82

La función zeta
1 La función zeta está definida por la serie
1 1 1
ζ(s) = 1 + + s + s + ···
2s 3 4
2 Fórmula del producto de Euler
∞ Y 1 −1

X 1
ζ(s) = = 1− s ,
ns p
p
n=1

3 La función zeta codifica información de los números enteros y de

los números primos.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 51 / 82

La función zeta
1 La función zeta está definida por la serie
1 1 1
ζ(s) = 1 + + s + s + ···
2s 3 4
2 Fórmula del producto de Euler
∞ Y 1 −1

X 1
ζ(s) = = 1− s ,
ns p
p
n=1

3 La función zeta codifica información de los números enteros y de

los números primos.
4 Riemman observó que la frecuencia de los números primos se
relaciona con la función zeta.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 51 / 82

La función zeta
1 La función zeta está definida por la serie
1 1 1
ζ(s) = 1 + + s + s + ···
2s 3 4
2 Fórmula del producto de Euler
∞ Y 1 −1

X 1
ζ(s) = = 1− s ,
ns p
p
n=1

3 La función zeta codifica información de los números enteros y de

los números primos.
4 Riemman observó que la frecuencia de los números primos se
relaciona con la función zeta.
5 La hipótesis de Riemman:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 51 / 82

La función zeta
1 La función zeta está definida por la serie
1 1 1
ζ(s) = 1 + + s + s + ···
2s 3 4
2 Fórmula del producto de Euler
∞ Y 1 −1

X 1
ζ(s) = = 1− s ,
ns p
p
n=1

3 La función zeta codifica información de los números enteros y de

los números primos.
4 Riemman observó que la frecuencia de los números primos se
relaciona con la función zeta.
5 La hipótesis de Riemman:
Todas las soluciones no triviales de la ecuación ζ(s) = 0
están sobre la recta s = 1/2.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 51 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59.

5 Algunos números compuestos:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59.

5 Algunos números compuestos:

4,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59.

5 Algunos números compuestos:

4, 6,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59.

5 Algunos números compuestos:

4, 6, 8,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59.

5 Algunos números compuestos:

4, 6, 8, 9,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59.

5 Algunos números compuestos:

4, 6, 8, 9, 10,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59.

5 Algunos números compuestos:

4, 6, 8, 9, 10, 12,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Definición de número primo

1 Un entero p > 1 es un número primo si sus únicos divisores

positivos son 1 y p.
2 Un número n > 1 es un número compuesto si no es un número
primo.
3 Los números 1 y −1 no son ni números primos ni números
compuestos.
4 Algunos números primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37, 41, 43, 47, 53, 59.

5 Algunos números compuestos:

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 52 / 82

Propiedades de los números primos

Teorema
Sea p un número primo y a, b ∈ Z. Si p | ab, entonces p | a o p | b.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 53 / 82

Propiedades de los números primos

Teorema
Sea p un número primo y a, b ∈ Z. Si p | ab, entonces p | a o p | b.

Ejercicio
Pruebe por inducción:

Si p | a1 . . . an entonces p | ai para algún i

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 53 / 82

Teorema Fundamental de la Aritmética

Teorema
Todo número natural se puede expresar en forma única, salvo el
orden, como un producto finito de números primos.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 54 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=3

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=3
2·3+1=

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=3
2·3+1=7

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=3
2·3+1=7
2·3·7+1=

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=3
2·3+1=7
2 · 3 · 7 + 1 = 43

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=3
2·3+1=7
2 · 3 · 7 + 1 = 43
2 · 3 · 7 · 43 + 1 =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=3
2·3+1=7
2 · 3 · 7 + 1 = 43
2 · 3 · 7 · 43 + 1 = 1807

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=3
2·3+1=7
2 · 3 · 7 + 1 = 43
2 · 3 · 7 · 43 + 1 = 1807 = 13 · 139

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82

Euclides: Hay infinidad de números primos
1 Euclides probó que existe una infinidad de primos.
2 Idea: Si p1 , . . . , pn son primos se construye un primo que no está
en la lista.
3 Ese primo proviene de la factorización en primos de
N = p1 p2 · · · pn + 1
4 Se empieza con 2 que es primo.

2+1=3
2·3+1=7
2 · 3 · 7 + 1 = 43
2 · 3 · 7 · 43 + 1 = 1807 = 13 · 139

5 La factorización de N contiene al menos un primo q que no

pertenece al conjunto de primos que se usaron en su
construcción.
Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 55 / 82
Euclides: Hay infinidad de números primos

Teorema (Teorema de Euclides)

Existe un número infinito de números primos.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 56 / 82

La criba de Eratóstenes

1 Eratóstenes dio un método para encontrar números primos

consecutivos menores que n

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 57 / 82

La criba de Eratóstenes

1 Eratóstenes dio un método para encontrar números primos

consecutivos menores que n
2 Se forma una tabla con todos los números comprendidos entre 2
yn

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 57 / 82

La criba de Eratóstenes

1 Eratóstenes dio un método para encontrar números primos

consecutivos menores que n
2 Se forma una tabla con todos los números comprendidos entre 2
yn
3 Se van tachando los números que no son primos de la siguiente
manera:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 57 / 82

La criba de Eratóstenes

1 Eratóstenes dio un método para encontrar números primos

consecutivos menores que n
2 Se forma una tabla con todos los números comprendidos entre 2
yn
3 Se van tachando los números que no son primos de la siguiente
manera:
1 Comenzando con el 2 se tachan todos sus múltiplos.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 57 / 82

La criba de Eratóstenes

1 Eratóstenes dio un método para encontrar números primos

consecutivos menores que n
2 Se forma una tabla con todos los números comprendidos entre 2
yn
3 Se van tachando los números que no son primos de la siguiente
manera:
1 Comenzando con el 2 se tachan todos sus múltiplos.
2 Se repite el proceso con el primer número que no haya sido
tachado, ese número es primo

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 57 / 82

La criba de Eratóstenes

1 Eratóstenes dio un método para encontrar números primos

consecutivos menores que n
2 Se forma una tabla con todos los números comprendidos entre 2
yn
3 Se van tachando los números que no son primos de la siguiente
manera:
1 Comenzando con el 2 se tachan todos sus múltiplos.
2 Se repite el proceso con el primer número que no haya sido
tachado, ese número es primo
3 se tachan todos sus múltiplos, y ası́ sucesivamente.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 57 / 82

La criba de Eratóstenes

1 Eratóstenes dio un método para encontrar números primos

consecutivos menores que n
2 Se forma una tabla con todos los números comprendidos entre 2
yn
3 Se van tachando los números que no son primos de la siguiente
manera:
1 Comenzando con el 2 se tachan todos sus múltiplos.
2 Se repite el proceso con el primer número que no haya sido
tachado, ese número es primo
3 se tachan todos sus múltiplos, y ası́ sucesivamente.
4 Ver animación

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 57 / 82

Factorización prima

1 Si n > 1, existen p1 , . . . , pr números primos distintos y enteros

αi ≥ 1 tales que

n = p1α1 · · · prαr .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 58 / 82

Factorización prima

1 Si n > 1, existen p1 , . . . , pr números primos distintos y enteros

αi ≥ 1 tales que

n = p1α1 · · · prαr .

2 Si a = 22 · 53 · 19 y b = 34 · 52 · 13, escribimos

a = 22 · 30 · 53 · 130 · 19
b = 20 · 34 · 52 · 13 · 190 .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 58 / 82

Factorización prima

1 Si n > 1, existen p1 , . . . , pr números primos distintos y enteros

αi ≥ 1 tales que

n = p1α1 · · · prαr .

2 Si a = 22 · 53 · 19 y b = 34 · 52 · 13, escribimos

a = 22 · 30 · 53 · 130 · 19
b = 20 · 34 · 52 · 13 · 190 .

3 En general, si a y b son números enteros, existen primos

p1 , p2 , . . . , pr tales que

a = ±p1α1 p2α2 · · · prαr , αi ≥ 0,

b = ±p1β1 p2β2 · · · prβr , βi ≥ 0.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 58 / 82

Contenido

1 El anillo de los enteros: Divisibilidad

Divisibilidad
El máximo común divisor
El Algoritmo de la División
El mı́nimo común múltiplo
Ecuaciones diofantinas
El Teorema Fundamental de la Aritmética
Los enteros módulo n y la aritmética modular

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 59 / 82

Congruencias módulo un entero n

Definición

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 60 / 82

Congruencias módulo un entero n

Definición
1 Sea n ≥ 0 un entero.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 60 / 82

Congruencias módulo un entero n

Definición
1 Sea n ≥ 0 un entero.
2 Sean a, b ∈ Z. a es congruente con b módulo n si n | a − b:

a ≡ b mód n ⇔ n | a − b.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 60 / 82

Ejemplos

¿7 ≡ 3 mód 4?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 61 / 82

Ejemplos

¿7 ≡ 3 mód 4?
¿21 ≡ 1 mód 4?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 61 / 82

Ejemplos

¿7 ≡ 3 mód 4?
¿21 ≡ 1 mód 4?
¿ − 9 ≡ −1 mód 4?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 61 / 82

Ejemplos

¿7 ≡ 3 mód 4?
¿21 ≡ 1 mód 4?
¿ − 9 ≡ −1 mód 4?
¿5 ≡ 2 mód 4?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 61 / 82

Ejemplos

¿7 ≡ 3 mód 4?
¿21 ≡ 1 mód 4?
¿ − 9 ≡ −1 mód 4?
¿5 ≡ 2 mód 4?
¿5 ≡ 2 mód 0?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 61 / 82

Ejemplos

¿7 ≡ 3 mód 4?
¿21 ≡ 1 mód 4?
¿ − 9 ≡ −1 mód 4?
¿5 ≡ 2 mód 4?
¿5 ≡ 2 mód 0?
¿107 ≡ 3 mód 8?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 61 / 82

Ejemplos

¿7 ≡ 3 mód 4?
¿21 ≡ 1 mód 4?
¿ − 9 ≡ −1 mód 4?
¿5 ≡ 2 mód 4?
¿5 ≡ 2 mód 0?
¿107 ≡ 3 mód 8?
¿ − 10 ≡ 14 mód 8?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 61 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ = {b ∈ Z : b ≡ a mód n}

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ = {b ∈ Z : b ≡ a mód n}
= {a + nk : k ∈ Z}

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ = {b ∈ Z : b ≡ a mód n}
= {a + nk : k ∈ Z}
= {a, a ± n, a ± 2n, a ± 3n, . . . }.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ = {b ∈ Z : b ≡ a mód n}
= {a + nk : k ∈ Z}
= {a, a ± n, a ± 2n, a ± 3n, . . . }.

3 Clase del 0:

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ = {b ∈ Z : b ≡ a mód n}
= {a + nk : k ∈ Z}
= {a, a ± n, a ± 2n, a ± 3n, . . . }.

3 Clase del 0:

nZ

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ = {b ∈ Z : b ≡ a mód n}
= {a + nk : k ∈ Z}
= {a, a ± n, a ± 2n, a ± 3n, . . . }.

3 Clase del 0:

nZ = {nk : k ∈ Z}

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ = {b ∈ Z : b ≡ a mód n}
= {a + nk : k ∈ Z}
= {a, a ± n, a ± 2n, a ± 3n, . . . }.

3 Clase del 0:

nZ = {nk : k ∈ Z} = {0, ±n, ±2n, ±3n, . . . }

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ = {b ∈ Z : b ≡ a mód n}
= {a + nk : k ∈ Z}
= {a, a ± n, a ± 2n, a ± 3n, . . . }.

3 Clase del 0:

nZ = {nk : k ∈ Z} = {0, ±n, ±2n, ±3n, . . . }

4 El conjunto de los enteros módulo n es

Z/nZ = {a + nZ : a ∈ Z}

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

La congruencia es una relación de equivalencia

1 La congruencia módn es una relación de equivalencia en Z.

2 Describir la clase de congruencia módulo n de a ∈ Z.

a mód n = a + nZ = {b ∈ Z : b ≡ a mód n}
= {a + nk : k ∈ Z}
= {a, a ± n, a ± 2n, a ± 3n, . . . }.

3 Clase del 0:

nZ = {nk : k ∈ Z} = {0, ±n, ±2n, ±3n, . . . }

4 El conjunto de los enteros módulo n es

Z/nZ = {a + nZ : a ∈ Z}

5 ¿Cuántos elementos tiene este conjunto?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 62 / 82

Ejemplo

1 Considere el anillo de los enteros módulo 4:

Z/4Z = {a + 4Z : a ∈ Z}

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 63 / 82

Ejemplo

1 Considere el anillo de los enteros módulo 4:

Z/4Z = {a + 4Z : a ∈ Z}

2 Proporcionar ejemplos de elementos en Z/4Z.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 63 / 82

Ejemplo

1 Considere el anillo de los enteros módulo 4:

Z/4Z = {a + 4Z : a ∈ Z}

2 Proporcionar ejemplos de elementos en Z/4Z.

1 + 4Z

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 63 / 82

Ejemplo

1 Considere el anillo de los enteros módulo 4:

Z/4Z = {a + 4Z : a ∈ Z}

2 Proporcionar ejemplos de elementos en Z/4Z.

1 + 4Z 2 + 4Z

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 63 / 82

Ejemplo

1 Considere el anillo de los enteros módulo 4:

Z/4Z = {a + 4Z : a ∈ Z}

2 Proporcionar ejemplos de elementos en Z/4Z.

1 + 4Z 2 + 4Z 11 + 4Z

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 63 / 82

Ejemplo

1 Considere el anillo de los enteros módulo 4:

Z/4Z = {a + 4Z : a ∈ Z}

2 Proporcionar ejemplos de elementos en Z/4Z.

1 + 4Z 2 + 4Z 11 + 4Z −28 + 4Z

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 63 / 82

Ejemplo

1 Considere el anillo de los enteros módulo 4:

Z/4Z = {a + 4Z : a ∈ Z}

2 Proporcionar ejemplos de elementos en Z/4Z.

1 + 4Z 2 + 4Z 11 + 4Z −28 + 4Z

3 ¿Es única la representación de los elementos en Z/4Z?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 63 / 82

Ejemplo

1 Considere el anillo de los enteros módulo 4:

Z/4Z = {a + 4Z : a ∈ Z}

2 Proporcionar ejemplos de elementos en Z/4Z.

1 + 4Z 2 + 4Z 11 + 4Z −28 + 4Z

3 ¿Es única la representación de los elementos en Z/4Z?

4 No, la representación no es única.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 63 / 82

Ejemplo

1 Considere el anillo de los enteros módulo 4:

Z/4Z = {a + 4Z : a ∈ Z}

2 Proporcionar ejemplos de elementos en Z/4Z.

1 + 4Z 2 + 4Z 11 + 4Z −28 + 4Z

3 ¿Es única la representación de los elementos en Z/4Z?

4 No, la representación no es única.
5 ¿Cuántos es la cardinalidad de Z/4Z?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 63 / 82

El anillo de los enteros módulo n

Teorema

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 64 / 82

El anillo de los enteros módulo n

Teorema
1 El conjunto Z/nZ junto con las operaciones

(a + nZ) + (b + nZ) = (a + b) + nZ,

(a + nZ) · (b + nZ) = (a · b) + nZ.

es un anillo conmutativo con unitario.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 64 / 82

El anillo de los enteros módulo n

Teorema
1 El conjunto Z/nZ junto con las operaciones

(a + nZ) + (b + nZ) = (a + b) + nZ,

(a + nZ) · (b + nZ) = (a · b) + nZ.

es un anillo conmutativo con unitario.

2 La representación canónica es

Z/nZ = {0 + nZ, 1 + nZ, . . . , n − 1 + nZ}.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 64 / 82

El anillo de los enteros módulo n

Teorema
1 El conjunto Z/nZ junto con las operaciones

(a + nZ) + (b + nZ) = (a + b) + nZ,

(a + nZ) · (b + nZ) = (a · b) + nZ.

es un anillo conmutativo con unitario.

2 La representación canónica es

Z/nZ = {0 + nZ, 1 + nZ, . . . , n − 1 + nZ}.

3 La cardinalidad de Z/nZ es n.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 64 / 82

La representación de un entero módulo n no es única

1 Abusando de la notación se escribe a o a en vez de a + nZ.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 65 / 82

La representación de un entero módulo n no es única

1 Abusando de la notación se escribe a o a en vez de a + nZ.

2 De esta manera

Z/nZ = {0, 1, . . . , n − 1}.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 65 / 82

La representación de un entero módulo n no es única

1 Abusando de la notación se escribe a o a en vez de a + nZ.

2 De esta manera

Z/nZ = {0, 1, . . . , n − 1}.

3 Como los elementos son conjuntos, la representación no es única.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 65 / 82

La representación de un entero módulo n no es única

1 Abusando de la notación se escribe a o a en vez de a + nZ.

2 De esta manera

Z/nZ = {0, 1, . . . , n − 1}.

3 Como los elementos son conjuntos, la representación no es única.

4 En Z/6Z, 1 = 7 = −11

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 65 / 82

La representación de un entero módulo n no es única

1 Abusando de la notación se escribe a o a en vez de a + nZ.

2 De esta manera

Z/nZ = {0, 1, . . . , n − 1}.

3 Como los elementos son conjuntos, la representación no es única.

4 En Z/6Z, 1 = 7 = −11
5 Es decir,
1 + 6Z = 7 + 6Z = −11 + 6Z

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 65 / 82

Potencias módulo n
1 Sea a un entero y m un entero positivo.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 66 / 82

Potencias módulo n
1 Sea a un entero y m un entero positivo.
2 Calcular el resto que se obtiene al dividir am entre n.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 66 / 82

Potencias módulo n
1 Sea a un entero y m un entero positivo.
2 Calcular el resto que se obtiene al dividir am entre n.
3 Se puede proceder como sigue:

am mód n = a
| · a{z
· · · · a} módn
m veces
= (a mód n) · (a mód n) · · · (a mód n)
| {z }
m veces
m
= (a mód n) .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 66 / 82

Potencias módulo n
1 Sea a un entero y m un entero positivo.
2 Calcular el resto que se obtiene al dividir am entre n.
3 Se puede proceder como sigue:

am mód n = a
| · a{z
· · · · a} módn
m veces
= (a mód n) · (a mód n) · · · (a mód n)
| {z }
m veces
m
= (a mód n) .
4 Por ejemplo

332014 mód 8 = (33 mód 8)2014 = (1 mód 8)2014 = 1 mód 8.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 66 / 82

Potencias módulo n
1 Sea a un entero y m un entero positivo.
2 Calcular el resto que se obtiene al dividir am entre n.
3 Se puede proceder como sigue:

am mód n = a
| · a{z
· · · · a} módn
m veces
= (a mód n) · (a mód n) · · · (a mód n)
| {z }
m veces
m
= (a mód n) .
4 Por ejemplo

332014 mód 8 = (33 mód 8)2014 = (1 mód 8)2014 = 1 mód 8.

5 También es válido decir que, en Z/8Z se tiene:

332014 = 33 · · · 33 = 1 · · · 1 = 1.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 66 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 =

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,
117 ≡ 71 mód 100,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,
117 ≡ 71 mód 100, 118 ≡ 81 mód 100,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,
117 ≡ 71 mód 100, 118 ≡ 81 mód 100, 119 ≡ 91 mód 100,

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,
117 ≡ 71 mód 100, 118 ≡ 81 mód 100, 119 ≡ 91 mód 100,
1110 ≡ 1 mód 100.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,
117 ≡ 71 mód 100, 118 ≡ 81 mód 100, 119 ≡ 91 mód 100,
1110 ≡ 1 mód 100.
6 Se escribe 45 = 10 · 4 + 5.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82

Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,
117 ≡ 71 mód 100, 118 ≡ 81 mód 100, 119 ≡ 91 mód 100,
1110 ≡ 1 mód 100.
6 Se escribe 45 = 10 · 4 + 5.
7 Se tiene a = 1145 =
Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82
Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,
117 ≡ 71 mód 100, 118 ≡ 81 mód 100, 119 ≡ 91 mód 100,
1110 ≡ 1 mód 100.
6 Se escribe 45 = 10 · 4 + 5.
7 Se tiene a = 1145 = (1110 )4 · 115
Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82
Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,
117 ≡ 71 mód 100, 118 ≡ 81 mód 100, 119 ≡ 91 mód 100,
1110 ≡ 1 mód 100.
6 Se escribe 45 = 10 · 4 + 5.
7 Se tiene a = 1145 = (1110 )4 · 115 = 14 · 115
Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82
Potencias módulo n
1 Calcular los últimos dos dı́gitos de a = 1145 .
2 La descomposición en base de 10 de a

a = a0 + a1 10 + a2 102 + · · ·
3 Se quiere determinar a0 y a1 (¿no que los últimos dı́gitos?)
4 Reducción módulo 100: a mód 100 = (a0 + a1 10) mód 100.
5 Se observa

111 ≡ 11 mód 100, 112 ≡ 21 mód 100, 113 ≡ 31 mód 100,

114 ≡ 41 mód 100, 115 ≡ 51 mód 100, 116 ≡ 61 mód 100,
117 ≡ 71 mód 100, 118 ≡ 81 mód 100, 119 ≡ 91 mód 100,
1110 ≡ 1 mód 100.
6 Se escribe 45 = 10 · 4 + 5.
7 Se tiene a = 1145 = (1110 )4 · 115 = 14 · 115 = 51.
Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 67 / 82
Reglas de divisibilidad

Teorema

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 68 / 82

Reglas de divisibilidad

Teorema

1) Un número natural a es divisible por 2 ⇐⇒ el dı́gito de las unidades

es par.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 68 / 82

Reglas de divisibilidad

Teorema

1) Un número natural a es divisible por 2 ⇐⇒ el dı́gito de las unidades

es par.
2) Un número natural a es divisible por 3 ⇐⇒ la suma de sus dı́gitos
es divisible por 3.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 68 / 82

Reglas de divisibilidad

Teorema

1) Un número natural a es divisible por 2 ⇐⇒ el dı́gito de las unidades

es par.
2) Un número natural a es divisible por 3 ⇐⇒ la suma de sus dı́gitos
es divisible por 3.
3) Un número natural a es divisible por 5 ⇐⇒ el dı́gito de las unidades
es 0 o 5.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 68 / 82

Solución de ax = b módulo n

Teorema

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 69 / 82

Solución de ax = b módulo n

Teorema
1) La ecuación lineal ax ≡ b mód n tiene solución ⇐⇒ mcd(a, n) | b.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 69 / 82

Solución de ax = b módulo n

Teorema
1) La ecuación lineal ax ≡ b mód n tiene solución ⇐⇒ mcd(a, n) | b.
2) Si mcd(a, n) | b, una solución de ax ≡ b mód n es

b
x0 = r , donde mcd(a, n) = ar + ns,
mcd(a, n)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 69 / 82

Solución de ax = b módulo n

Teorema
1) La ecuación lineal ax ≡ b mód n tiene solución ⇐⇒ mcd(a, n) | b.
2) Si mcd(a, n) | b, una solución de ax ≡ b mód n es

b
x0 = r , donde mcd(a, n) = ar + ns,
mcd(a, n)

3) El conjunto solución de ax ≡ b mód n es

n
x0 + k (k ∈ Z)
mcd(a, n)

donde x0 es una solución particular.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 69 / 82

Solución de ax = b módulo n

Teorema
1) La ecuación lineal ax ≡ b mód n tiene solución ⇐⇒ mcd(a, n) | b.
2) Si mcd(a, n) | b, una solución de ax ≡ b mód n es

b
x0 = r , donde mcd(a, n) = ar + ns,
mcd(a, n)

3) El conjunto solución de ax ≡ b mód n es

n
x0 + k (k ∈ Z)
mcd(a, n)

donde x0 es una solución particular.

4) Si mcd(a, n) = 1, entonces ax ≡ b mód n tiene solución, y la
solución es única módulo n.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 69 / 82

Ejemplo

1 Determine si la ecuación 1380x ≡ 8645 mód 539 tiene solución.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 70 / 82

Ejemplo

1 Determine si la ecuación 1380x ≡ 8645 mód 539 tiene solución.

2 En caso de tenerla, halle una solución.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 70 / 82

Ejemplo

1 Determine si la ecuación 1380x ≡ 8645 mód 539 tiene solución.

2 En caso de tenerla, halle una solución.
3 d = mcd(a, n) = 1 = a(141) + n(−361).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 70 / 82

Ejemplo

1 Determine si la ecuación 1380x ≡ 8645 mód 539 tiene solución.

2 En caso de tenerla, halle una solución.
3 d = mcd(a, n) = 1 = a(141) + n(−361).
4 La ecuación tiene solución y además es única (módulo 539)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 70 / 82

Ejemplo

1 Determine si la ecuación 1380x ≡ 8645 mód 539 tiene solución.

2 En caso de tenerla, halle una solución.
3 d = mcd(a, n) = 1 = a(141) + n(−361).
4 La ecuación tiene solución y además es única (módulo 539)
5 Una solución es x0 = rb/d = 141(8645) = 1218945

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 70 / 82

Ejemplo

1 Determine si la ecuación 1380x ≡ 8645 mód 539 tiene solución.

2 En caso de tenerla, halle una solución.
3 d = mcd(a, n) = 1 = a(141) + n(−361).
4 La ecuación tiene solución y además es única (módulo 539)
5 Una solución es x0 = rb/d = 141(8645) = 1218945
6 El conjunto solución es clase de congruencia de 1218945:

1218945 + 539Z = 266 + 539Z.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 70 / 82

Ejemplo

Ejemplo SageMath
El comando solve mod(eqn,modulo) calcula las soluciones de la
ecuación lineal.

sage: solve_mod(1380 * x== 8645, 539)

[(266,)]

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 71 / 82

Solución de ax = b

1 Determine el conjunto solución de ax ≡ b mód n tiene solución,

donde a = 14014, b = 476 y n = 140.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 72 / 82

Solución de ax = b

1 Determine el conjunto solución de ax ≡ b mód n tiene solución,

donde a = 14014, b = 476 y n = 140.
2 d = mcd(a, n) = 14 = a(1) + n(−100).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 72 / 82

Solución de ax = b

1 Determine el conjunto solución de ax ≡ b mód n tiene solución,

donde a = 14014, b = 476 y n = 140.
2 d = mcd(a, n) = 14 = a(1) + n(−100).
3 d | 14014.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 72 / 82

Solución de ax = b

1 Determine el conjunto solución de ax ≡ b mód n tiene solución,

donde a = 14014, b = 476 y n = 140.
2 d = mcd(a, n) = 14 = a(1) + n(−100).
3 d | 14014.
4 x0 = rb/d = 34.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 72 / 82

Solución de ax = b

1 Determine el conjunto solución de ax ≡ b mód n tiene solución,

donde a = 14014, b = 476 y n = 140.
2 d = mcd(a, n) = 14 = a(1) + n(−100).
3 d | 14014.
4 x0 = rb/d = 34.
5 El conjunto solución es

140
34 + k = 34 + 10k, k ∈ Z.
14

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 72 / 82

Solución de ax = b

1 Determine el conjunto solución de ax ≡ b mód n tiene solución,

donde a = 14014, b = 476 y n = 140.
2 d = mcd(a, n) = 14 = a(1) + n(−100).
3 d | 14014.
4 x0 = rb/d = 34.
5 El conjunto solución es

140
34 + k = 34 + 10k, k ∈ Z.
14
6 Las soluciones diferentes módulo 140 son:

34, 44, 54, 64, 74, 84, 94, 104, 114, 124, 134, 4, 14, 24.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 72 / 82

Solución de ax = b

Ejemplo SageMath
Con sage

sage: solve_mod(14014*x == 476, 140)

[(84,), (64,), (44,), (24,), (4,), (124,), (104,),
(14,), (134,), (114,), (94,), (74,), (54,), (34,)]

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 73 / 82

Unidades del anillo Z/nZ

1 Si R es un anillo, el grupo multiplicativo de las unidades es

R ∗ = {a ∈ R : Existe b ∈ R tal que ab = ba = 1}.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 74 / 82

Unidades del anillo Z/nZ

1 Si R es un anillo, el grupo multiplicativo de las unidades es

R ∗ = {a ∈ R : Existe b ∈ R tal que ab = ba = 1}.
2 Se sabe que ax ≡ 1 mód n si y sólo si (a, n) | 1.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 74 / 82

Unidades del anillo Z/nZ

1 Si R es un anillo, el grupo multiplicativo de las unidades es

R ∗ = {a ∈ R : Existe b ∈ R tal que ab = ba = 1}.
2 Se sabe que ax ≡ 1 mód n si y sólo si (a, n) | 1.
3 Por lo tanto,

(Z/nZ)∗ = {a + nZ ∈ Z/nZ : mcd(a, n) = 1}.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 74 / 82

Unidades del anillo Z/nZ

1 Si R es un anillo, el grupo multiplicativo de las unidades es

R ∗ = {a ∈ R : Existe b ∈ R tal que ab = ba = 1}.
2 Se sabe que ax ≡ 1 mód n si y sólo si (a, n) | 1.
3 Por lo tanto,

(Z/nZ)∗ = {a + nZ ∈ Z/nZ : mcd(a, n) = 1}.

4 La función φ de Euler Si n es un entero positivo,

φ(n) = #{a | mcd(a, n) = 1, 1 ≤ a < n} = |(Z/nZ)∗ | .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 74 / 82

Ejemplo

1 φ(90) = |(Z/90Z)∗ | = 24
2 Las unidades son

sage: n = 90; R = Integers(n); R

Ring of integers modulo 90
sage: R.unit_group_order() # Cardinalidad de (Z/nZ)ˆ*
24
sage: euler_phi(90)
24
sage: [a for a in R if gcd(ZZ(a),n)==1]
[1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 5
59, 61, 67, 71, 73,77, 79, 83, 89]

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 75 / 82

Ley de la cancelación multiplicativa en Z/nZ

Teorema

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 76 / 82

Ley de la cancelación multiplicativa en Z/nZ

Teorema
1 Si mcd(a, n) = 1 y ab ≡ ac mód n, entonces b ≡ c mód n.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 76 / 82

Ley de la cancelación multiplicativa en Z/nZ

Teorema
1 Si mcd(a, n) = 1 y ab ≡ ac mód n, entonces b ≡ c mód n.
2 Equivalentemente, en Z/nZ,

ab = ac, a una unidad ⇒ b = c.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 76 / 82

Solución del sistema de congruencias ax = b y cx = d

1 Resolver el sistema

x ≡ 8 mód 3, (1)
x ≡ 4 mód 5. (2)

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 77 / 82

Solución del sistema de congruencias ax = b y cx = d

1 Resolver el sistema

x ≡ 8 mód 3, (1)
x ≡ 4 mód 5. (2)

2 ¿Es posible encontrar un x ∈ Z que sea solución de ambas

congruencias?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 77 / 82

Solución del sistema de congruencias ax = b y cx = d

1 Resolver el sistema

x ≡ 8 mód 3, (1)
x ≡ 4 mód 5. (2)

2 ¿Es posible encontrar un x ∈ Z que sea solución de ambas

congruencias?
3 8 satisface (1).

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 77 / 82

Solución del sistema de congruencias ax = b y cx = d

1 Resolver el sistema

x ≡ 8 mód 3, (1)
x ≡ 4 mód 5. (2)

2 ¿Es posible encontrar un x ∈ Z que sea solución de ambas

congruencias?
3 8 satisface (1).
4 El conjunto solución de (1) es 8 + 3k , k ∈ Z .

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 77 / 82

Solución del sistema de congruencias ax = b y cx = d

1 Resolver el sistema

x ≡ 8 mód 3, (1)
x ≡ 4 mód 5. (2)

2 ¿Es posible encontrar un x ∈ Z que sea solución de ambas

congruencias?
3 8 satisface (1).
4 El conjunto solución de (1) es 8 + 3k , k ∈ Z .
5 ¿existe algún entero k tal que 8 + 3k ≡ 4 mód 5?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 77 / 82

Solución del sistema de congruencias ax = b y cx = d

1 Resolver el sistema

x ≡ 8 mód 3, (1)
x ≡ 4 mód 5. (2)

2 ¿Es posible encontrar un x ∈ Z que sea solución de ambas

congruencias?
3 8 satisface (1).
4 El conjunto solución de (1) es 8 + 3k , k ∈ Z .
5 ¿existe algún entero k tal que 8 + 3k ≡ 4 mód 5?
6 La última ecuación es equivalente a

3k ≡ −4 mód 5.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 77 / 82

Solución del sistema de congruencias ax = b y cx = d

1 Resolver el sistema

x ≡ 8 mód 3, (1)
x ≡ 4 mód 5. (2)

2 ¿Es posible encontrar un x ∈ Z que sea solución de ambas

congruencias?
3 8 satisface (1).
4 El conjunto solución de (1) es 8 + 3k , k ∈ Z .
5 ¿existe algún entero k tal que 8 + 3k ≡ 4 mód 5?
6 La última ecuación es equivalente a

3k ≡ −4 mód 5.

7 Una solución común es x = 8 + 3(12) = 44.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 77 / 82

El Teorema Chino del Residuo

Teorema

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 78 / 82

El Teorema Chino del Residuo

Teorema
1 Sean a, b ∈ Z y sean m y n enteros positivos primos relativos.
Entonces el sistema de congruencias

x ≡a mód m
x ≡b mód n

tiene solución.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 78 / 82

El Teorema Chino del Residuo

Teorema
1 Sean a, b ∈ Z y sean m y n enteros positivos primos relativos.
Entonces el sistema de congruencias

x ≡a mód m
x ≡b mód n

tiene solución.
2 De hecho, x = a + rm(b − a) es una solución, donde 1 = mr + ns.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 78 / 82

El Teorema Chino del Residuo

Teorema
1 Sean a, b ∈ Z y sean m y n enteros positivos primos relativos.
Entonces el sistema de congruencias

x ≡a mód m
x ≡b mód n

tiene solución.
2 De hecho, x = a + rm(b − a) es una solución, donde 1 = mr + ns.
3 La solución es única módulo mn.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 78 / 82

Ejemplo

1 Encuentre la solución del sistema de congruencias lineales

x ≡ 8 mód 10,
x ≡ 10 mód 21.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 79 / 82

Ejemplo

1 Encuentre la solución del sistema de congruencias lineales

x ≡ 8 mód 10,
x ≡ 10 mód 21.

2 mcd(10, 21) = 1 = (−2)m + n

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 79 / 82

Ejemplo

1 Encuentre la solución del sistema de congruencias lineales

x ≡ 8 mód 10,
x ≡ 10 mód 21.

2 mcd(10, 21) = 1 = (−2)m + n

3 Una solución al sistema de ecuaciones es 8 + (−2)(10)(2) = −32.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 79 / 82

Ejemplo

1 Encuentre la solución del sistema de congruencias lineales

x ≡ 8 mód 10,
x ≡ 10 mód 21.

2 mcd(10, 21) = 1 = (−2)m + n

3 Una solución al sistema de ecuaciones es 8 + (−2)(10)(2) = −32.
4 En efecto 10 divide a −40 y 21 divide a −42.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 79 / 82

Ejemplo

1 Use el Teorema Chino y resuelva la congruencia

x ≡ 24 mód 35

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 80 / 82

Ejemplo

1 Use el Teorema Chino y resuelva la congruencia

x ≡ 24 mód 35

2 Observe que 35 = 5 × 7

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 80 / 82

Ejemplo

1 Use el Teorema Chino y resuelva la congruencia

x ≡ 24 mód 35

2 Observe que 35 = 5 × 7
3 La congruencia anterior se convierte en el sistema de
congruencias:

x ≡ 4 mód 5
x ≡ 3 mód 7

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 80 / 82

Residuos cuadráticos x 2 ≡ a mód n

1 ¿Tiene solución la ecuación x 2 ≡ 3 mód 7?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 81 / 82

Residuos cuadráticos x 2 ≡ a mód n

1 ¿Tiene solución la ecuación x 2 ≡ 3 mód 7?

2 ¿Tiene solución la ecuación x 2 ≡ 2 mód 7?

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 81 / 82

Residuos cuadráticos x 2 ≡ a mód n

1 ¿Tiene solución la ecuación x 2 ≡ 3 mód 7?

2 ¿Tiene solución la ecuación x 2 ≡ 2 mód 7?

Ejercicio

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 81 / 82

Residuos cuadráticos x 2 ≡ a mód n

1 ¿Tiene solución la ecuación x 2 ≡ 3 mód 7?

2 ¿Tiene solución la ecuación x 2 ≡ 2 mód 7?

Ejercicio
1 Sean p, q primos distintos. Pruebe que x 2 ≡ a mód pq tiene
solución si y solo si el sistema

x 2 ≡ a mód p
x 2 ≡ a mód q

tiene solución.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 81 / 82

Residuos cuadráticos x 2 ≡ a mód n

1 ¿Tiene solución la ecuación x 2 ≡ 3 mód 7?

2 ¿Tiene solución la ecuación x 2 ≡ 2 mód 7?

Ejercicio
1 Sean p, q primos distintos. Pruebe que x 2 ≡ a mód pq tiene
solución si y solo si el sistema

x 2 ≡ a mód p
x 2 ≡ a mód q

tiene solución.
2 Usando (1), determine si la ecuación x 2 ≡ 11 mód 35 tiene
solución.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 81 / 82

Teorema Chino del Residuo

Ejercicio
Pruebe que el sistema de congruencias

x ≡ a mód m
x ≡ b mód n

tiene solución si y solamente si mcd(m, n) | b − a.

Alejandro Lara (Fmat- Uady) Álgebra Superior II 17 de mayo de 2017 82 / 82