Notas de clase

Teorı́a de Números
B 2020 − 2

Profesor
Jorge E. Gómez Rı́os

UNIVERSIDAD INDUSTRIAL DE SANTANDER

Escuela de Matemáticas
Bucaramanga
Actualizado: 8 de marzo de 2021
Índice general

1. Números Enteros 3
1.1. Propiedades fundamentales . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Relación de orden en los enteros Z. . . . . . . . . . . . . . . . . . . . . 5
1.3. Principio del Buen Orden . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4. Formas equivalentes del Principio de Inducción Matemática . . . . . . . 9

2. Teorı́a de la divisibilidad de los números enteros 15

2.1. Algoritmo de la división . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2. Máximo común divisor . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3. Mı́nimo Común Múltiplo. . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4. Teorema Fundamental de la Aritmética . . . . . . . . . . . . . . . . . . 34
2.5. Números Primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3. Congruencias 48
3.1. Definición y algunas propiedades . . . . . . . . . . . . . . . . . . . . . 48
3.2. Criterios de Divisibilidad . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3. Ecuaciones diofánticas lineales . . . . . . . . . . . . . . . . . . . . . . . 66
3.4. Congruencias Lineales . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.5. Teoremas de Fermat, Wilson y Euler . . . . . . . . . . . . . . . . . . . 77

4. Funciones Aritméticas 84
4.1. Funciones Multiplicativas . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.2. Funciones tau τ, sigma σ y phi φ . . . . . . . . . . . . . . . . . . . . . 86
4.3. Función parte entera . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4. Función de Möbius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

5. Residuos Cuadráticos 105

5.1. Congruencias cuadráticas con módulo primo . . . . . . . . . . . . . . . 105
5.2. El Sı́mbolo de Legendre . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.3. Ley de reciprocidad cuadrática . . . . . . . . . . . . . . . . . . . . . . . 114

1
5.4. El sı́mbolo de Jacobi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
5.5. Congruencias de grado superior . . . . . . . . . . . . . . . . . . . . . . 123
5.6. Potencias módulo n y raı́ces primitivas . . . . . . . . . . . . . . . . . . 127
Capı́tulo 1

Números Enteros

1.1. Propiedades fundamentales

En este curso asumiremos que existe el conjunto de los números enteros Z, el cual
podemos expresar como: Z = −N ∪ N = {. . . , −3, −2, −1, 0, 1, 2, 3, . . . } , donde N
denota el conjunto de los números naturales, esto es N = {0, 1, 2, 3, 4, 5, . . . } , y −N =
{−n : n ∈ N, n 6= 0} = {−1, −2, −3, −4, −5, . . . } . Además, a este conjunto se le ha
dotado de dos operaciones binarias internas denominadas suma y producto1 (denotadas,
para dos números enteros a y b, por a + b y a · b respectivamente) que satisfacen las
siguientes propiedades:

P1. Clausuras: si a y b son números enteros, entonces a + b y a · b también lo son.

P2. Leyes conmutativas: para todo par de enteros a y b se verifica que

a+b= b+a y a · b = b · a.

P3. Leyes asociativas: dados a, b, c ∈ Z se cumplen las siguientes igualdades:

a + (b + c) = (a + b) + c y a · (b · c) = (a · b) · c.

P4. Ley distributiva: si a, b, c ∈ Z, entonces a · (b + c) = a · b + a · c.

P5. Existencia de elementos neutros: Existen dos elementos en Z, denotados por

0 y 1 tales que a + 0 = a y a · 1 = a, para todo a ∈ Z.
1
El estudiante interesado en estudiar la construcción axiomática del conjunto de los números enteros
y la definición de las operaciones suma y producto en este conjunto, puede consultar el capı́tulo 1 del
texto [1].

3
P6. Inverso aditivo: para todo a ∈ Z, existe una única solución en Z para la ecuación
a + x = 0, tal solución se denomina el inverso aditivo de a y se denota −a.

P7. Ley cancelativa: si a, b, c ∈ Z son tales que a · c = b · c y c 6= 0, entonces a = b.

Notación 1.1. En adelante,

diremos que 0 es el elemento neutro (o módulo) de la suma y que 1 es el elemento

neutro (o módulo) del producto.

por simplicidad escribiremos ab en lugar de a · b y b − a en lugar de b + (−a).

Asumiendo las anteriores propiedades como axiomas, se pueden demostrar otras pro-
piedades de los números enteros, por ejemplo:

Proposición 1.2.

(a) a · 0 = 0, para todo a ∈ Z.

(b) Dados a, b ∈ Z, se tiene que ab 6= 0 si y solo si a 6= 0 y b 6= 0.

(c) (−1)a = −a, para todo a ∈ Z.

(d) Si a, b ∈ Z, entonces −(ab) = a(−b) = (−a)b, (−a)(−b) = ab, y −(a + b) =

(−a) + (−b).

Demostración.

(a) Sea a ∈ Z. Dado que 0 es el elemento neutro de la suma (P5.) entonces 0 + 0 = 0,

luego
a · 0 = a(0 + 0) = a · 0 + a · 0,

donde la última igualdad se sigue de la ley distributiva (P4.) Ahora, por P1, a·0 ∈ Z
y por P6 existe su inverso aditivo, ası́ que sumando el inverso aditivo de a · 0 en
ambos lados de la igualdad y asociando (P3.) convenientemente obtenemos:

a · 0 −(a · 0) = a · 0 + [a · 0 −(a · 0)] ,

de donde se sigue que 0 = a · 0 + 0 y por ser 0 el neutro de la suma se concluye

que 0 = a · 0.
(b) Demostraremos la implicación (⇐=) por contradicción. Supongamos que ab = 0.
Sumando a en ambos lados de la igualdad tenemos:

a + ab = a + 0.
a · 1 + ab = a. (P 5.)
a · (1 + b) = a · 1. (P 4.) y (P 5.)
(1 + b)a = 1 · a. (P 2.)
1 + b = 1. (P 7.) ya que si a = 0 se genera una contradicción.
(−1 + 1) + b = −1 + 1. (P 6.) y (P 3.)
0 + b = 0. (P 6.)
b = 0. (P 5.)

Lo cual es contradictorio. Ası́ que ab 6= 0.

La implicación (=⇒) se sigue inmediamente del item (a) al considerar la contra-
rrecı́proca. (Ejercicio)

(c) Sea a ∈ Z. Note que a + (−1)a = a1 + (−1)a = a(1 + (−1)) = a · 0 = 0, luego (−1)a
es solución de la ecuación a + x = 0, y dado que esta solución es única (según P6.)
entonces (−1)a es el inverso aditivo de a, esto es (−1)a = −a.

(d) Ejercicio.

1.2. Relación de orden en los enteros Z.

“He oı́do decir que los griegos pensaban que Pitágoras habı́a dicho que todo habı́a sido
engendrado por el Número. Pero esta afirmación nos perturba: ¿cómo nos podemos
imaginar cosas que no existen y que pueden engendrar? Él dijo no que todas las co-
sas nacı́an del número, sino que todo estaba formado de acuerdo con el Número, ya
que en el número reside el orden esencial, y las mismas cosas pueden ser nombradas
primeras, segundas, y ası́ sucesivamente, sólo cuando participan de este orden”

Teano - Sobre la piedad.

La relación definida por:

a ≤ b si y solo si b − a ∈ N,

establece un orden total en el conjunto de los números enteros, esto significa que ≤
satisface las siguientes propiedades:
Reflexividad: para todo a ∈ Z, se tiene que a ≤ a.

Transitividad: si a, b, c, ∈ Z son tales que a ≤ b y b ≤ c, entonces a ≤ c.

Antisimetrı́a: si a, b ∈ Z son tales que a ≤ b y b ≤ a, entonces a = b

Totalidad o Completitud: para todo par de enteros a y b se tiene que a ≤ b o b ≤ a.

La propiedad de totalidad se puede entender como que todo par de números enteros
son comparables bajo la relación ≤ .

Notación 1.3. En adelante,

a ≤ b también se denotará por b ≥ a;

si a ≤ b y a 6= b, escribiremos a < b;

si 0 < a diremos que a es un entero positivo, denotaremos por Z+ = {1, 2, 3, 4, . . . }

al conjunto de los enteros positivos;

si a es un número entero tal que 0 < −a, entonces diremos que a es un entero
negativo, denotaremos por Z− = −N = {−1, −2, −3, −4, . . . } al conjunto de los
enteros negativos;

también escribiremos a > 0 cuando a es un entero positivo y a < 0 si a es un

entero negativo.

Observación 1.4. Note que

0 no es positivo ni negativo, Z− ∩ Z+ = ∅ y además Z = Z− ∪ {0} ∪ Z+ .

a ≤ b ⇐⇒ existe c ∈ N tal que a + c = b.

a < b ⇐⇒ b − a ∈ Z+ .

a > b ⇐⇒ b − a ∈ Z− .

Teorema 1.5 (Ley de Tricotomı́a). Dados a, b ∈ Z, se da una y solo una de las

siguientes afirmaciones:

(i) a < b,

(ii) a > b,

(iii) a = b
Demostración. Sean a, b ∈ Z. Entonces a − b ∈ Z, pero

Z = Z− ∪ {0} ∪ Z+ , (1.1)

luego a − b ∈ Z− o a − b ∈ {0} o a − b ∈ Z+ , esto es a < b o a = b o a > b. y se da una

y solo una de las anteriores afirmaciones puesto que la unión (1.1) es disjunta.

La relación de orden en Z también tiene las siguientes propiedades:

Proposición 1.6.

(a) Si a, b ∈ Z+ , entonces a + b ∈ Z+ y ab ∈ Z+ .

(b) Si a, b ∈ Z son tales que a ≤ b, entonces a + c ≤ b + c, para todo c ∈ Z.

(c) Si a, b, c, d ∈ Z son tales que a ≤ b y c ≤ d, entonces a + c ≤ b + d.

(d) Si a, b ∈ Z son tales que a ≤ b, entonces ac ≤ bc, para todo c ∈ Z+ .

(e) Si a, b ∈ Z son tales que a ≤ b, entonces ac ≥ bc, para todo c ∈ Z− .

Demostración. Ejercicio.

Ejercicios 1.1 y 1.2

1. Completar la demostración de la Proposición 1.2.

2. Escribir los detalles de las afirmaciones de la Observación 1.4.

3. Demostrar la Proposición 1.6.

4. A partir de las propiedades P1. a P7., demostrar las siguientes afirmaciones,

siendo a, b y c números enteros:

(a) (a + b)c = ac + bc.

(b) (a + b)2 = a2 + 2ab + b2 .
(c) a2 ≥ 0.
(d) a3 < 0, si a < 0.
(e) si a > b y b > c, entonces a > c.
1.3. Principio del Buen Orden
Definición 1.7. Sea X un conjunto y ≤ una relación de orden en X. Diremos que
a ∈ X es el mı́nimo de X si a ≤ x, para todo x ∈ X.

Observación 1.8. El mı́nimo de un conjunto X, cuando existe, es único y se le denota

por mı́n(X).

Ejemplo 1.9. Con la relación de orden usual ≤,

mı́n({−1, 0, 1, 2}) = −1.

mı́n([0, ∞)) = 0.

mı́n(N) = 0.

Ejemplo 1.10. Algunos conjuntos no tienen mı́nimo, por ejemplo, con la relación de
orden usual ≤,
 
1 +
mı́n :n∈Z no existe
n
mı́n((0, ∞)) no existe.

mı́n(Z) no existe.

Axioma 1.11 (Principio del Buen Orden (PBO)). Todo subconjunto, no vacı́o,
de los números enteros positivos, tiene mı́nimo.
Esto es, si X ⊆ Z+ y X 6= ∅, entonces existe a ∈ X, tal que a ≤ x, para todo x ∈ X.

Ejemplo 1.12. Demostrar que no existen enteros entre 0 y 1.

Solución: Haremos la prueba por contradicción. Sea X = {k ∈ Z : 0 < k < 1} y su-
pongamos que existe un entero entre 0 y 1, esto es X 6= ∅. De modo que X es un
subconjunto de Z+ no vacı́o, y por el PBO, tiene mı́nimo. Sea a = mı́n(X). Entonces
0 < a < 1 y multiplicando por a, se tiene que 0 < a2 < a < 1, luego a2 ∈ X y a2 < a
lo que contradice que a es el mı́nimo de X. Por lo tanto X = ∅, esto es, no existen
números enteros entre 0 y 1.

Ejemplo 1.13 (Propiedad Arquimediana). Pruebe que dados a, b ∈ Z+ , existe

n ∈ Z+ tal que na ≥ b.
Solución: Supongamos que la afirmación es falsa; esto es, existen enteros positivos a y
b tales que na < b, para todo entero positivo n. Entonces el conjunto

S = {b − na : n es un entero positivo} ⊆ Z+ ,
no es vacı́o. Ası́, por el PBO, S tiene un elemento mı́nimo. Sea x0 = mı́n(S), entonces
x0 = b − ma, para algún m ∈ Z+ . Evidentemente b − (m + 1)a también está en S y

b − (m + 1)a = (b − ma) − a < b − ma = x0 ,

lo que contradice que x0 es el mı́nimo de S. Ası́, existe un entero positivo n tal que
na ≥ b.

1.4. Formas equivalentes del Principio de Inducción

Matemática
En esta sección se probará el Principio de Inducción Matemática (PMI) asumiendo el
Principio del Buen Orden y se presentarán algunas formas equivalentes del PMI.

Teorema 1.14 (Principio de Inducción Matemática “Débil”).

Sea S ⊆ Z+ que satisface las siguientes propiedades:

(i) 1 ∈ S.

(ii) Siempre que k ∈ S, entonces k + 1 ∈ S.

Entonces S = Z+ .

Demostración. La prueba se hará por contradicción. Supongamos que S 6= Z+ , enton-

ces X = Z+ \ S es un subconjunto no vacı́o de Z+ y por el PBO, tiene mı́nimo. Sea
a = mı́n(X). Luego a ∈ Z+ y a 6∈ S, y como 1 ∈ S, entonces a 6= 1, de modo que
a ≥ 2, ası́, 1 ≤ a − 1 y a − 1 ∈ Z+ . Pero a − 1 < a entonces a − 1 ∈ S, de no ser ası́ se
contradice que a = mı́n(X). Ahora, por (ii), se tiene que a ∈ S ¡no podemos escapar
del oscuro abismo la contradicción! a menos que aceptemos que S = Z+ .

Con el propósito de utilizar el Principio de Inducción Matemática como método de

demostración, conviene escribirlo de la siguiente forma:

Criterio 1.15 (Método de Inducción Matemática). Sea P (n) una afirmación

sobre un entero positivo n tal que:

(i) P (1) es verdadera.

(ii) Si P (k) es verdadera, entonces P (k + 1) es verdadera.

Entonces P (n) es verdadera para todo entero positivo n.

 Si paramos todas las fichas de un dominó, una seguida de la otra,
formando una fila, basta asegurarnos de dos cosas para hacer que
todas las fichas caigan:

(i) Que la primera ficha caiga.

(ii) Que si una ficha cae, empuje a la siguiente.

Los enteros positivos son como un dominó infinito y ordenado, donde cada ficha tie-
ne escrito un número. En estos términos, una proposición sobre los enteros positivos
es un arreglo en el que se han parado todas la fichas, una tras otra; mientras que una
prueba por inducción consiste en examinar si en este arreglo las fichas están a la dis-
tancia justa y en el ángulo adecuado, para que cada vez que caiga una, esta empuje a
la siguiente; de modo que al hacer caer la primera ficha, todas caen.

Observación 1.16. La prueba de la condición (i) se denomina la base de la inducción,

mientras que la prueba de (ii) se llama el paso de inducción, las suposiciones hechas
en el paso de inducción se conocen como las hipótesis de inducción.
n(n + 1)
Ejemplo 1.17. Demostrar que la suma de los primeros n enteros positivos es .
2
Solución: Haremos la prueba por inducción.
n(n + 1)
Sea P (n) la proposición “la suma de los primeros n enteros positivos es ”
2
Se ha ordenado el dominó...

1(1 + 1)
(i) Base de la inducción: verficamos que P (1) es cierta. En efecto, 1 = .
2

Se cae la primera ficha.

(ii) Paso de inducción: probaremos que siempre que P (k) sea verdadera, P (k + 1)
es verdadera.

Hipótesis de inducción (HI): Supongamos que P (k) es verdadera, esto es

k(k + 1)
1+2+3+···+k = ,
2
Si cae una,

(k + 1)(k + 2)
y veamos que 1 + 2 + 3 + · · · + k + (k + 1) = .
2
 En efecto,

HIk(k + 1)
1 + 2 + 3 + · · · + k + (k + 1) = + (k + 1),
2
k(k + 1) + 2(k + 1)
= ,
2
(k + 1)(k + 2)
= .
2

cae la siguiente.

Por lo tanto P (k + 1) es verdadera, y por el PIM concluimos que P (n) es ver-

dadera para todo n ∈ Z+ .
Entonces todas caen.

A veces no queremos tirar todo el dominó, sino que caigan todas, a

partir de cierta ficha.

En algunos casos tenemos que una determinada propiedad se cumple para todo entero
positivo n ≥ a, en estos casos el esquema de la demostración por inducción se modifica,
de manera que en vez de probar la base de la inducción para n = 1, se hace para n = a.
Esto es, el método de inducción se puede usar comenzando en un entero positivo distinto
de 1, por lo que conviene escribirlo de la siguiente manera:

Teorema 1.18. Sea a un entero positivo fijo y U = {k ∈ Z : k ≥ a} . Si S ⊆ Z+

satisface las siguientes propiedades:

(i) a ∈ S.

(ii) Siempre que k ∈ S, con k ≥ a, entonces k + 1 ∈ S.

Entonces U ⊆ S.
Ejemplo 1.19. Pruebe que para todo entero n ≥ 3, se tiene que n! > 3n−2 .

Solución: Haremos la prueba por inducción.

(i) Base de la inducción. Verificamos que la proposición se cumple para n = 3. De

hecho,
3! = 3 × 2 × 1 = 6 > 33−2 = 3.

(ii) Paso de inducción. Veamos que si la proposición es cierta para n = k ≥ 3,

también se cumple para n = k + 1.

Hipótesis de inducción (HI): Supongamos que k! > 3k−2, entonces:

HI
(k + 1)! = (k + 1)k! > (k + 1)3k−2 > 3 · 3k−2 = 3k−1.

Por lo tanto la desigualdad se cumple para n = k + 1, y por el Teorema 1.18,

concluimos que la desigualdad es cierta para todo entero n ≥ 3.

Teorema 1.20 (Principio de Inducción Matemática “Fuerte”).

Sean a un entero positivo fijo y U = {k ∈ Z+ : k ≥ a} . Si S ⊆ Z+ satisface las siguien-
tes propiedades:

(i) a ∈ S.

(ii) Siempre que {a, a + 1, . . . , k} ⊆ S, con k ≥ a, entonces k + 1 ∈ S.

Entonces U ⊆ S. En particular, si S ⊆ U, entonces S = U.

Demostración. Haremos la prueba por contradicción. Supongamos que U 6⊆ S, entonces

el conjunto
T = (U \ S) ⊆ Z+ ,

no es vacı́o y por el PBO tiene elemento mı́nimo. Sea x0 = mı́n(T ). Note que x0 6∈ S,
y por (i) a ∈ S, luego x0 > a, y como x0 = mı́n(T ), entonces

a, a + 1, . . . , x0 − 1 ∈ S.

Ası́, por (ii) se tiene que x0 ∈ S, lo cual genera una contradicción. Por lo tanto T es
vacı́o, esto es U ⊆ S. En particular, si S ⊆ U, se tiene que U = S.
Definición 1.21 (La sucesión de Fibonacci). Sea {Fn } la sucesión definida por:
F1 = 1,
F2 = 1,
Fn = Fn−1 + Fn−2 , para n ≥ 3.

De modo que los primeros términos de esta sucesión son:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, . . .

A esta sucesión se le llama sucesión de Fibonacci y a sus términos números de Fibonacci.

Ejemplo 1.22. Probar que Fn < 2n , para todo entero positivo n.

Solución: Haremos la prueba usando el PIM-Fuerte.

(i) Base de la inducción. Se verifica la validez de la desigualdad para F1 y F2 :

F1 = 1 < 2,
F2 = 1 < 4 = 22 .

(ii) Paso de inducción. Sea k un entero positivo tal que k ≥ 2. Suponemos que la
desigualdad se cumple para todo m ∈ Z+ tal 1 ≤ m ≤ k, esto es:

Hipótesis de inducción (HI): Fm < 2m , con 1 ≤ m ≤ k.

Debemos probar que también se cumple para k + 1. En efecto,

Fk+1 = Fk + Fk−1 , Por la definición de la sucesión de Fibonacci.

k k−1
<2 +2 , Por la Hipótesis de Inducción.
= 2 · 2k−1 + 2k−1 ,
= 3 · 2k−1 ,
< 22 · 2k−1,
= 2k+1.

Ası́, por el PIM-Fuerte, concluimos Fn < 2n , para todo entero positivo n.

Observación 1.23.

Cuando usamos Inducción Fuerte para demostrar una propiedad, en la hipótesis

de inducción, suponemos la validez de dicha propiedad para todo m, con 1 ≤
 m ≤ k, aunque es frecuente que, en el desarrollo del paso inductivo, sea necesario
utilizar la validez de la propiedad solo para algunos de los casos posibles. Note
que en el Ejemplo 1.22. solo usamos 2 instancias de la hipótesis de inducción:
para m = k y para m = k − 1.

Por otra parte, al probar la base de la inducción en el Ejemplo 1.22. no solo se

hizo para F1 , sino que además fue necesario hacerlo también para F2 . Lo anterior
obedece a la definición de la sucesión de Fibonacci, ya que esta se genera a partir
de F1 y F2 , y por lo tanto, la base de la inducción debe ser probada para ambos.
Ejercicios 1.3 y 1.4

1. Sea n un entero. Muestre que no existen enteros entre n y n + 1,

2. Sean n, m ∈ Z, tales que n < m. Muestre n + 1 ≤ m.

3. Muestre que todo subconjunto, no vacı́o, de los números naturales, tiene

mı́nimo.
√
4. Usando el Principio del Buen Orden, muestre que 2 es irracional.

5. Pruebe el Teorema 1.18.

6. Sea {Fn } la sucesión de Fibonacci. Pruebe que, para todo entero positivo n,
se verfica
(F1 )2 + (F2 )2 + · · · + (Fn )2 = Fn · Fn+1

7. Pruebe que (3n)! > 26n−4 , para todo entero positivo n.

8. Un automóvil solo puede recorrer distancias de 2 o 5 kilómetros cada vez que

este se enciende. ¿Cuál es la mayor cantidad de kilómetros que no pueden
recorrerse haciendo uso del automóvil?

9. Pruebe que cualquier entero mayor que 5 puede ser escrito como suma de un
múltiplo positivo de 7 y un múltiplo positivo de 2.

10. Demuestre la siguiente cadena de implicaciones

PBO nf ❚❚
❚❚❚❚❚
❚❚❚❚❚
 ❚❚❚
PIM-Débil 3 + PIM-Fuerte
Capı́tulo 2

Teorı́a de la divisibilidad de los

números enteros

Aquı́ desarrollaremos algunas ideas y resultados fundamentales de la aritmética de los

números enteros: el Algoritmo de la división, el concepto de divisibilidad, el máximo
común divisor, el mı́nimo común múltiplo, la definición de número primo y algunas
de sus propiedades, entre otros. También abordaremos el Teorema Fundamental de la
Aritmética y algunas de sus aplicaciones.

2.1. Algoritmo de la división

Teorema 2.1. Dados dos números enteros cualesquiera a y b, con b > 0, existen dos
únicos enteros q y r tales que

a = bq + r; 0 ≤ r < b.

Los enteros q y r se llaman, respectivamente, el cociente y el residuo en la división de

a por b.
Demostración. Existencia. Consideremos el conjunto

S = {a − xb : x ∈ Z y a − xb ≥ 0} ⊆ N.

Note S es no vacı́o, ya que como b ≥ 1, se cumple que |a|b ≥ |a| ≥ a y tomando

x = −|a| ∈ Z, se tiene que

0 ≤ a − (−|a|)b = a − xb ∈ S.

Ası́, por el PBO S tiene un elemento mı́nimo. Sea r = mı́n(S), entonces 0 ≤ r y

15
r = a − qb, para algún q ∈ Z. Falta probar que r < b. Supongamos lo contrario, esto
es r ≥ b. Entonces

t = a − (q + 1)b = a − qb − b = r − b ≥ 0,

y además t = r − b < r, esto contradice que r = mı́n(S). Luego r < b. Con lo anterior
hemos probado que existen q, r ∈ Z tales que

a = bq + r; 0 ≤ r < b.

Unicidad. Para demostrar la unicidad de q y r, supongamos que existen q ′ , r ′ ∈ Z

tales que
a = qb + r = q ′ b + r ′ , con 0 ≤ r, r ′ < b.

Entonces r − r ′ = b(q ′ − q), esto implica b|q ′ − q| = |r − r ′ | < b, de donde |q ′ − q| < 1 y

si q 6= q ′ , entonces 0 < |q ′ − q| < 1, lo cual es imposible, ası́ que q = q ′ y por lo tanto
r − r ′ = 0 lo que implica que r = r ′ .

Un versión más general del Algoritmo de la división es la siguiente:

Corolario 2.2. Dados a, b ∈ Z, con b 6= 0; existen q, r ∈ Z únicos tales que a = bq + r

con 0 ≤ r < |b|.

Observación 2.3. El Algoritmo de División discriminia a los números enteros según el

residuo que estos dejen al ser divididos por un entero no nulo n. Esto es, dado n ∈ Z+ ,
por el Algoritmo de la División, se tiene que todo número entero se puede escribir de
la forma nk + r, con 0 ≤ r < n, lo que genera una partición de Z con exactamente n
elementos que denotamos ası́:

r = nZ + r = {nk + r : k ∈ Z} , para cada 0 ≤ r < n.


A la partición de Z ası́ generada se le denota por Zn = 0, 1, . . . , n − 1, o simplemente
Zn = {0, 1, . . . , n − 1} .

Ejemplo 2.4. Los posibles residuos al dividir un entero entre n = 2, son: 0 y 1, de

modo que todo número entero puede ser escrito de la forma 2k o 2k + 1, con k ∈ Z. Al
conjunto los números enteros de la forma 2k también se les llama el conjuto de números
pares y se denota por
2Z = {2k : k ∈ Z} ,
mientras que a los números enteros de la forma 2k + 1 se le llama números impares y
al conjuto de todos estos números se le denota por

2Z + 1 = {2k + 1 : k ∈ Z} .

Note que, por el Algoritmo de la división, Z = 2Z ∪ (2Z + 1) y 2Z ∩ (2Z + 1) = ∅, por


lo que {2Z, 2Z + 1} = 0, 1 = Z2 es una partición de los números enteros.

Ejemplo 2.5. Un profesor obtuvo 4 por residuo al dividir un entero positivo entre
8, luego dividió el mismo número entre 12 y obtuvo 3 por residuo. Demuestre que el
profesor cometió un error.

Solución: Sea n el entero positivo que dividió el profesor. Dado que al dividir n entre 8
obtuvo 4 como residuo, entonces n = 8q+4 = 2(4q+2), para algún q ∈ Z; pero al dividir
n entre 12 el residuo que obtuvo fue 3, esto implica que n = 12k + 3 = 2(6k + 1) + 1
para algún k ∈ Z. Lo anterior muestra que n es un número par e impar a vez, lo cual
es contradictorio.

Ejemplo 2.6. Muestre que en 5 enteros tomados al azar siempre hay dos cuya dife-
rencia es múltiplo de 4.

Solución: Por el Algoritmo de la división los posibles residuos al dividir un número

entre 4 son: 0, 1, 2, 3 de modo que al tomar 5 enteros, por el Principio del Palomar, al
menos dos de ellos dejan el mismo residuo al dividir entre 4. Ahora, note que si dos
números dejan el mismo residuo al dividirse entre 4 entonces su diferencia es múltiplo
de 4. En efecto, m = 4k + r y n = 4k ′ + r entonces m − n = 4(k − k ′ ), con k − k ′ ∈ Z.

Ejemplo 2.7. Demuestre que el cuadrado de todo entero es de la forma 4k o de la

forma 4k + 1. Use este resultado para mostrar que en la sucesión

11, 111, 1111, 11111, . . .

ningún término tiene raı́z cuadrada exacta.

Solución: Probaremos la primera parte por casos: Sea n un número entero,

Caso 1. Si n es par, esto es, n = 2t, para algún t ∈ Z; entonces n2 = 4t2 = 4k, con
k = t2 ∈ Z.

Caso 2. Si n es impar, entonces n = 2t + 1, para algún t ∈ Z; luego

n2 = 4t2 + 4t + 1 = 4(t2 + t) + 1 = 4k + 1,
 con k = t2 + t ∈ Z.

Por lo tanto, el cuadrado de todo entero es de la forma 4k o de la forma 4k + 1. Para

la segunda parte, note que, para m ≥ 2,
!
11
| . {z . . . 1} 00 + 8 + 3 = 100 · 11
. . 111} = |11 {z . . . 1} + 8 + 3 = 4 25 · 11
| {z . . . 1} + 2
| {z + 3,
m unos m−2 unos m−2 unos m−2 unos

Luego cada término de la sucesión es de la forma 4k + 3, pero anteriormente probamos

que todo cuadrado es de la forma 4k o 4k+1, por lo tanto nigún término de esta sucesión
es el cuadrado de un entero, y por lo tanto ninguno tiene raı́z cuadrada exacta.

Definición 2.8. Se dice que un número entero a 6= 0 divide a otro número entero b,
y se escribe a|b, si existe c ∈ Z tal que b = ac. En caso contrario, diremos que a no
divide a b, lo cual denotaremos por a ∤ b.

Notación 2.9. En adelante,

cuando a divida a b, también diremos que

− “b es divisible por a”
− “a es un divisor de b”
− “a es un factor de b”
− “b es un múltiplo de a”.

si se usa la notación a|b, se debe asumir que a 6= 0.

Observación 2.10. Note que, si a es un divisor de b, entonces b también es divisible por

−a, es decir, los divisores de un entero “aparecen” en parejas. Ası́ que, para encontrar
todos los divisores de un entero dado, es suficiente con obtener los divisores positivos
y luego añandir a los correspondientes divisores negativos. Por esta razón, en adelante
los resultados se limitarán a divisores positivos.

A continuación enunciaremos algunas propiedades básicas, y tal vez muy conocidas, de

la relación “divide”. El lector debe realizar las demostraciones de estas propiedades,
ya que, aunque parezcan extremadamente simples, vale la pena hacerlas con rigor, al
menos una vez en la vida.

Proposición 2.11. Sean a, b, c números enteros.

(a) a|0, 1|a y a|a.

(b) a|1 si y solo a = ±1.

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

(d) a|b y b|a si y solo si a = ±b.

(e) Si a|b y b 6= 0, entonces |a| ≤ |b|.

(f ) Si a|b y c|d, entonces ac|bd.

(g) Si a|b y a|c, entonces a|(bx + cy), para todos x, y ∈ Z.

n
X
(h) Si a|bk para cada k ∈ {1, 2, . . . , n} , entonces a divide la suma bk xk , donde
k=1
xk ∈ Z, para todo k ∈ {1, 2, . . . , n} .

Demostración. Ejercicio.

Observación 2.12. La relación “divide” es una relación de orden en el conjunto de

los enteros positivos.

Ejemplo 2.13. Demuestre que 24 divide a Mn = n(n2 − 1)(3n + 2), para todo n ∈ N.

Solución: Haremos la prueba por Inducción. Note que 24|0 = M0 . Ahora, supongamos
que 24|Mk y veamos que 24|Mk+1 . En efecto, note que
 
Mk+1 − Mk = (k + 1) (k + 1)2 − 1 [3(k + 1) + 2] − k(k 2 − 1)(3k + 2),
= (k + 1)(k 2 + 2k)(3k + 5) − k(k + 1)(k − 1)(3k + 2),
= k(k + 1) [(k + 2)(3k + 5) − (k − 1)(3k + 2)] ,
= 12k(k + 1)2 .

Pero k y k + 1 son enteros consecutivos y por lo tanto uno de ellos es múltiplo de 2,

ası́ 24|(Mk+1 − Mk ) . Además, por Hipótesis de Inducción, 24|Mk , entonces por el item
(g) de la Proposición 2.11, se tiene que 24|[(Mk+1 − Mk ) + Mk ] esto es, 24|Mk+1. De
modo que por el PIM-Débil se tiene que la afirmación es cierta para todo n ∈ N.
 Ejercicios 2.1

1. Demuestre el Corolario 2.2.

2. Complete la demostración de la Proposición 2.11.

3. Justifique la Observación 2.12.

4. Un entero positivo al ser dividido entre 4 deja resto 1 y al ser dividido entre
5 deja resto 3. ¿Qué resto deja al ser dividido entre 20?

5. Muestre que el cuadrado de todo número impar es de la forma 8k + 1, para

algún k ∈ Z.
n(n2 + 2)
6. Use el Algoritmo de la División para demostrar que es un entero,
3
para todo entero n.

7. Sea n un entero mayor o igual a 2. Muestre que en cualquier conjunto con

n + 1 números enteros, hay dos cuya diferencia es múltiplo de n.

8. De contraejemplos para las siguientes afirmaciones:

(a) Si a|bc entonces a|b o a|c.

(b) Si a|bc y a ∤ c, entonces a|b.
(c) Si a|b, entonces b|a.

9. Muestre que si d|a, d|b y a = bq + r entonces d|r.

10. ¿Cuántos enteros positivos menores o iguales que 1000 son divisibles por 3?

11. ¿Cuántos enteros positivos menores o iguales que 1000 son divisibles por 2 y
por 3 pero no por 5?
2.2. Máximo común divisor
Proposición 2.14. Para cada número entero n definimos el conjunto Dn de todos los
enteros positivos que dividen a n, esto es Dn = {d ∈ Z+ : d|n} . Entonces

(a) 1, |n| ∈ Dn , para cada entero n 6= 0.

(b) Dn es finito, para cada entero n 6= 0.

(c) Dn = D−n , para cada n ∈ Z.

(d) Dn ∩ Dm es no vacı́o y finito para cada par de enteros m y n, no ambos nulos.

Observación 2.15. Note que D0 = Z+ .

Definición 2.16. Dados dos enteros m y n, con al menos uno de los dos diferente de
cero, se define el máximo común divisor entre m y n, como el mayor entero que divide
simultáneamente a m y a n. A tal entero lo denotaremos por mcd(m, n), esto es:

mcd(m, n) = máx (Dm ∩ Dn ) .

Observación 2.17. En virtud de la Proposición 2.14, se tiene que mcd(m, n), siempre
existe y es único, para cada par de enteros m y n con al menos uno de los dos diferente
de cero. Además, mcd(0, 0) no existe.

Observación 2.18. Que d = mcd(m, n) significa que:

(i) d|n y d|m,

(ii) Si c|n y c|m, entonces c ≤ d.

Ejemplo 2.19. mcd(12, 9) = 3, pues

D12 = {1, 2, 3, 4, 6, 12} ,

D9 = {1, 3, 9} ,
máx(D12 ∩ D9 ) = máx({1, 3}) = 3.

La siguiente proposición lista algunas propiedades básicas del máximo común divisor:

Proposición 2.20.

(a) mcd(n, 0) = |n|, para cada entero n 6= 0.

(b) mcd(n, 1) = 1, para cada n ∈ Z.

(c) mcd(m, n) = mcd(−m, n) = mcd(m, −n) = mcd(−m, −n), para cada par de ente-
ros m y n no ambos nulos.

(d) Si m|n, entonces mcd(m, n) = |m|.

Lema 2.21 (El Lema de Bezout). Dados dos enteros a y b, con al menos uno de los
dos diferente de cero. Entonces existen enteros x, y tales que mcd(a, b) = ax + by.

Demostración. Sea S = {am + bn : m, n ∈ Z} . Note que el conjunto A = S ∩ Z+ no es

vacı́o, pues a2 + b2 = aa + bb ∈ A y además A ⊆ Z+ . Ası́, por el PBO, A tiene mı́nimo.
Sea d = mı́n(A), entonces d = ax + by, para algunos x, y ∈ Z.
Veamos que d = mcd(a, b). En efecto, d divide a cualquier elemento de S, pues si
u = am + bn ∈ S, por el Algoritmo de la División, existen q, r ∈ Z, tales que

u = qd + r, con 0 ≤ r < d.
r = u − qd,
= (am + bn) − q(ax + by),
= a(m − qx) + b(n − qy).

Luego r ∈ S y r < d, entonces r 6∈ A, de modo que r = 0 y por lo tanto u = qd, esto

es d|u.
En particular, d divide a a = a(1) + b(0) y d divide a b = a(0) + b(1), luego d ∈ Da ∩ Db .
Además, si c ∈ Da ∩ Db , entonces c|a y c|b, y por el item (g) de la Proposición 2.11,
c|(ax + by), esto es c|d y por (e) de la Proposición 2.11, c ≤ d. De modo que

d = máx(Da ∩ Db ) = mcd(a, b).

Ejemplo 2.22. Vimos que mcd(12, 9) = 3, en este caso, tomando x = 1 y y = −1
tenemos que
3 = 12(1) + 9(−1).

Más adelante exhibiremos un algoritmo para encontrar los enteros x y y del Lema 2.21.
El siguiente teorema establece algunas caracterizaciones para el máximo común divisor
de entre dos números enteros m y n (no ambos nulos).

Teorema 2.23. Dados dos enteros m y n, con al menos uno de los dos diferente de
cero. Entonces las siguientes afirmaciones son equivalentes:

(a) d = mcd(m, n).

(b) d es el menor entero positivo que se puede expresar como una combinación lineal
de m y n.

(c) d satisface las siguientes condiciones:

(i) d > 0
(ii) d|n y d|m,
(iii) si c|n y c|m, entonces c|d.

Demostración. Ejercicio para el lector.

Definición 2.24. Diremos que dos enteros a y b son primos relativos (o coprimos) si
mcd(a, b) = 1.

Ejemplo 2.25. Los números 12 y 35 son primos relativos, pues mcd(12, 35) = 1. Pero
los números 12 y 15 no son primos relativos, pues mcd(12, 15) = 3.

Teorema 2.26. Sean a y b enteros, con al menos uno de los dos diferente cero. En-
tonces a y b son primos relativos si y sólo si existen enteros x y y tales que 1 = ax + by.

Demostración.

(=⇒) Por definición, si a y b son primos relativos, entonces mcd(a, b) = 1. Ası́, por el
Lema de Bezout, existen x, y ∈ Z tales que 1 = ax + by.

(⇐=) Supongamos que existen enteros x y y tales que 1 = ax+by, y sea d = mcd(a, b).
Entonces d|a y d|b, luego d|(ax + by), esto es d|1, además, d > 0 por lo tanto
mcd(a, b) = d = 1, de modo que a y b son primos relativos.
Más propiedades...

Proposición 2.27. Sean a, b, c enteros.

(a) (Lema de Euclides). Si a = bq + r, con q, r ∈ Z, entonces mcd(a, b) = mcd(b, r).

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

 
a b
(c) Si d = mcd(a, b), entonces mcd , = 1.
d d
(d) Si c 6= 0, entonces mcd(ca, cb) = |c|mcd(a, b).

(e) Si mcd(a, b) = mcd(a, c) = 1, entonces mcd(a, bc) = 1.

(f ) Si mcd(a, bi ) = 1, para cada entero bi , con 1 ≤ i ≤ k, entonces

mcd(a, b1 b2 · · · bk ) = 1.

Demostración.

(a) Sea a = bq + r. Veamos que Da ∩ Db = Db ∩ Dr .

En efecto, si x ∈ Da ∩ Db , entonces x|a y x|b, luego x|(at + bs), para todos t, s ∈ Z.
En particular, si t = 1 y s = −q, tenemos que x|(a − bq), pero r = a − bq, de ahı́
que x|r, esto es x ∈ Dr . Ası́ x ∈ Db ∩ Dr y por lo tanto Da ∩ Db ⊆ Db ∩ Dr .
Ahora, si x ∈ Db ∩ Dr , entonces x|b y x|r, x|(bt + rs), para todos t, s ∈ Z. En
particular, si t = q y s = 1, tenemos que x divide a bq + r = a, esto es x ∈ Da . Ası́,
x ∈ Da ∩ Db , luego Db ∩ Dr ⊆ Da ∩ Db .
Por lo anterior, Da ∩ Db = Db ∩ Dr , de ahı́ que

mcd(a, b) = máx(Da ∩ Db ) = máx(Db ∩ Dr ) = mcd(b, r).

Ejemplo 2.28. Dos enteros consecutivos son primos relativos.

Solución: Sean a y b = a + 1 dos enteros consecutivos, por el Lema de Euclides

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

Ejemplo 2.29. Muestre que si a y b son primos relativos, entonces

mcd(3a − b, 4a + b) ∈ {1, 7} .

Solución: Sea d = mcd(3a − b, 4a + b), entonces d|(3a − b) y d|(4a + b), en particular

d | [(3a − b) + (4a + b)] = 7a,

d | [−4(3a − b) + 3(4a + b)] = 7b.

De donde d divide al mcd(7a, 7b) = 7mcd(a, b) = 7. Por lo tanto d = 1 o d = 7.

El siguiente algoritmo establece una forma “eficiente” para hallar el máximo común
divisor de un par de enteros dados. Este algoritmo consiste en aplicar repetidas veces
el Algoritmo de la División y el Lema de Euclides (Proposición 2.27, item (a))

Algoritmo de Euclides
Dados dos enteros a y b, con 0 < b < a,

Paso 1. Aplicamos el Algoritmo de la División para escribir

a = bq1 + r1 , con 0 ≤ r1 < b.

Paso 2. Si r1 = 0, entonces b|a luego mcd(a, b) = b ¡y terminamos! Pero si r1 6= 0, por

el Lema de Euclides, tenemos que

mcd(a, b) = mcd(b, r1 ),

y repetimos el Paso 1 para los enteros b y r1 .

Paso 3. Aplicamos nuevamente el Algoritmo de la División para los enteros b y r1 , ası́,

b = r1 q2 + r2 , con 0 ≤ r2 < r1 .

Paso 4. Si r2 = 0, entonces r1 |b luego mcd(a, b) = mcd(b, r1 ) = r1 ¡y terminamos!

 Pero si r2 6= 0, por el Lema de Euclides, tenemos que

mcd(a, b) = mcd(b, r1 ) = mcd(r1 , r2 ),

y repetimos el Paso 1 para los enteros r1 y r2 .

Note que al aplicar a lo sumo b veces el Algortimo de la división llegaremos a un residuo

cero; y en este punto habremos encontrado el mcd(a, b). Ilustraremos lo anterior con
un ejemplo:

Ejemplo 2.30. Hallar mcd(756, 231).

Solución: Aplicado repetidas veces el Algortimo de la División, según el Algortimo de

Euclides tenemos:

756 = 231(3) + 63.

231 = 63(3) + 42.
63 = 42(1) + 21.
42 = 21(2) + 0.

Ası́, por el Lema de Euclides:

mcd(756, 231) = mcd(231, 63) = mcd(63, 42) = mcd(42, 21) = 21.

Observación 2.31. Note que, el Algortimo de Euclides también permite expresar el

mcd(a, b) como combinación lineal de los enteros a y b, con coeficientes enteros, esto
es, permite determinar enteros x y y tales que

mcd(a, b) = ax + by.

Ejemplo 2.32. Escribir el mcd(756, 231) como combinación lineal de 756 y 231.

Solución: Despejando los residuos obtenidos en el Ejemplo 2.30 desde el penúltimo,

obtenemos:

21 = 63 − 42.
42 = 231 − 63(3)
63 = 756 − 231(3),
Ası́ que reemplazado sucesivamente los residuos tenemos:

21 = 63 − [231 − 63(3)] = 63(4) − 231,

= [756 − 231(3)] (4) − 231 = 756(4) − 231(13).

Luego, 21 = 756(4) + 231(−13).

Ejemplo 2.33. Sea {Fn } la sucesión de Fibonacci. Muestre que para n > 1 el Algo-
ritmo de Euclides ejecuta exactamente n divisiones para mostrar que

mcd(Fn+1 , Fn+2 ) = 1.

Ejercicios 2.2

1. Justifique rigorosamente cada literal de las Proposiciones 2.14 y 2.20.

2. Demuestre el Teorema 2.23.

3. Complete la demostración de la Proposición 2.27.

4. Si c es cualquier divisor común de m y n, entonces c divide a mcd(m, n).

5. Si a y b son enteros, con al menos uno de los dos diferente de cero, entonces el
conjunto {ax + by : x, y ∈ Z} coincide con el conjunto de todos los múltiplos
de mcd(a, b).

6. Sea {Fn } la sucesión de Fibonacci. Muestre que Fn y Fn+1 son primos relativos
para cada n ∈ N.

7. Hallar el mcd(2019, 1001) y escribirlo como combinación lineal de ellos.

2.3. Mı́nimo Común Múltiplo.
Para cada entero n, definimos el conjunto Mn de todos los múltiplos positivos de n,
esto es:

Mn = nk ∈ Z+ : k ∈ Z .

Observación 2.34. Sean a, b enteros no nulos, entonces

(a) M0 = ∅.

(b) Ma = M−a .

(c) Ma ∩ Mb no es vacı́o, pues |ab| ∈ Ma ∩ Mb .

(d) Por el PBO, Ma ∩ Mb tiene mı́nimo.

Definición 2.35. Dados a, b enteros no nulos, se define el mı́nimo común múltiplo de

a y b, como el menor entero positivo que es múltiplo de a y de b simultáneamente. A
este entero lo denotaremos por mcm(a, b), esto es:

mcm(a, b) = mı́n(Ma ∩ Mb ).

Observación 2.36. De los literales (c) y (d) de la Observación 2.34 se sigue que el
mcm(a, b) siempre existe y es único para cada par de enteros no nulos a y b.

Observación 2.37. Que m = mcm(a, b) significa que:

(i) a|m y b|m.

(ii) Si a|c y b|c, con c > 0, entonces c ≥ m.

Ejemplo 2.38. mcm(3, 5) = 15, pues:

M3 = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30, . . . } ;

M5 = {5, 10, 15, 20, 25, 30, 35, . . . } ;
M3 ∩ M5 = {15, 30, 45, . . . } ;
mcm(3, 5) = mı́n (M3 ∩ M5 ) = 15.

En la siguiente proposición se listan algunas propiedades del mı́nimo común múltiplo:

Proposición 2.39. Sean a y b enteros no nulos.

(a) mcm(a, 1) = |a|.

(b) mcm(a, b) ≤ |ab|.

(c) mcm(a, b) = mcm(−a, b) = mcm(a, −b) = mcm(−a, −b).

(d) Si a = bk, con k ∈ Z, entonces mcm(a, b) = |a|.

(e) Si k 6= 0, entonces mcm(ka, kb) = |k|mcm(a, b).

 
a b mcm(a, b)
(f ) Sea d un entero positivo tal que d|a y d|b, entonces mcm , = .
d d d
Teorema 2.40. Sean a y b enteros no nulos. Entonces m = mcm(a, b), si y solo si,

(i) m > 0.

(ii) a|m y b|m.

(iii) Si a|c y b|c, con c > 0, entonces m|c.

Demostración.

(=⇒) Sea m = mcm(a, b), entonces m = mı́n(Ma ∩ Mb ), veamos que se verifican las
tres condiciones:

(i) Claramente m > 0.

(ii) a|m pues m ∈ Ma y b|m pues m ∈ Mb .
(iii) Sea c > 0, tal que a|c y b|c, entonces por el Algoritmo de la División, existen
q, r ∈ Z, tales que c = mq + r, con 0 ≤ r < m. Ahora, como a|m y a|c,
entonces a divide a c − mq = r. Análogamente se tiene que b|r. De modo
que si r > 0, entonces r ∈ Ma ∩ Mb y r < m = mı́n(Ma ∩ Mb ), lo cual es
contradictorio. Ası́ que r = 0 y por lo tanto c = mq esto es m|c.

(⇐=) Sea m un entero que satisface las condiciones (i), (ii) y (iii). Veamos que m =
mcm(a, b). En efecto, por (i) y (ii) tenemos que m ∈ Ma ∩ Mb . Además, si
x ∈ Ma ∩ Mb , entonces a|x y b|x, y por (iii) se tiene que m|x, luego m ≤ x, esto
es m = mı́n(Ma ∩ Mb ) = mcm(a, b).

El siguiente teorema establece una relación entre el mı́nimo común múltiplo y el máximo
común divisor.

Teorema 2.41. Sean a y b enteros no nulos, entonces

mcm(a, b)mcd(a, b) = |ab|. (2.1)

Demostración. Por el item (c) de la Proposición 2.39 y el item (c) de la Proposición
2.27, basta probar que la igualdad (2.1) se cumple para a y b enteros positivos. Sea

ab
m= ,
mcd(a, b)

con a y b enteros positivos, veamos que m = mcm(a, b). En efecto,

(i) m > 0, pues ab > 0 y mcd(a, b) > 0.

(ii) Sea d = mcd(a, b) entonces

 
ab  a  b
m= = b=a ,
d d d

a b
y , ∈ Z, luego a|m y b|m.
d d
(iii) Finalmente, si a|c y b|c, con c > 0, entonces c = at = bs, con t, s ∈ Z, luego
a b a b
t = s, esto es | s. Pero d = mcd(a, b), ası́ que, por el item (c) de la
d d d d  
a b
Proposición 2.27, 1 = mcd , , y por el item (b) de la misma proposición,
d d
a a
| s, luego s = r, para algún r ∈ Z. De modo que,
d d
 a  ab
c = bs = b r = r = mr,
d d
esto es, m|c. De lo anterior, por el Teorema 2.40, concluimos que m = mcm(a, b),
como querı́amos probar.

Corolario 2.42. Sean a, b enteros no nulos, entonces mcm(a, b) = |ab|, si y solo si, a
y b son primos relativos, esto es mcd(a, b) = 1.

Demostración. Ejercicio para el Lector.

Ejemplo 2.43. Vimos que mcd(756, 231) = 21, por lo tanto

(756)(231)
mcm(756, 231) = = 8316.
21
Ejemplo 2.44. Determinar todos los enteros a y b para los cuales mcm(a, b) = 2020
y mcd(a, b) = 101.
Solución: Como mcd(a, b) = 101, entonces a = 101A y b = 101B, con mcd(A, B) = 1.
Además, por el Teorema 2.41,

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

(101)(2020) = 1012|A||B|,
2020
= |A||B|.
101
20 = |A||B|

De modo que los posibles valores para A y B, y los correspondientes valores de a y b,

salvo por el orden, son:

A B a b
±4 5 ±404 505
±4 −5 ±404 −505
±1 20 ±101 2020
±1 −20 ±101 −2020
 Ejercicios 2.3

1. Justifique la Proposición 2.39.

2. Pruebe el Corolario 2.42.

3. Dado que mcm(a, b) = 3780 y mcd(a, b) = 63, hallar el menor valor posible
para 2a + b.

4. (ORM-UIS) El periodo de traslación de un planeta es el tiempo que este

demora en dar una vuelta completa alrededor del Sol. Si los periodos de
traslación de Júpiter, Saturno y Urano son 12, 30 y 84 años respectivamente,
¿cuántas vueltas debe dar Saturno hasta la próxima vez que los tres planetas
vuelvan a estar alineados como muestra la figura?

Sol
Júpiter Saturno Urano
2.4. Teorema Fundamental de la Aritmética
Definición 2.45 (Número primo). Sea p un entero positivo, diremos que p es pri-
mo si tiene exactamente dos divisores positivos, esto es, si Dp tiene exactamente dos
elementos. Si p > 1 no es primo, diremos que es compuesto.

Observación 2.46. El 1 no es compuesto ni es primo pues D1 = {1} tiene un solo

elemento. Por otra parte, si p es primo sus únicos divisores son 1 y el mismo p.

Ejemplo 2.47. Los primeros números primos son:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, . . .

Ejemplo 2.48. El único primo par es el 2.

Teorema 2.49. Si p es un número primo y p|ab, entonces p|a o p|b.

Demostración. Si p|a, se tiene el resultado. Ahora, si p ∤ a, entonces mcd(a, p) = 1 y

por el item (b) de la Proposición 2.27 se tiene que p|b.

Corolario 2.50. Si p es un número primo y p|a1 a2 · · · an , entonces p|ak , para algún

k ∈ {1, 2, . . . , n} .

Corolario 2.51. Si p, q1 , q2 , . . . , qn son números primos y p|q1 q2 · · · qn , entonces p = qk ,

para algún k ∈ {1, 2, . . . , n} .

Lema 2.52. Si n es un entero mayor que 1, entonces existe un primo p tal que p|n.

Demostración. Usaremos el PIM-Fuerte para probar el Lema. Claramente la afirma-

ción es cierta para el caso n = 2. Ahora, supongamos que se cumple para n ≤ k y
probemos que existe un primo que divide a k + 1. En efecto, si k + 1 es primo, ter-
minamos la prueba; en caso contrario k + 1 se podrá escribir de la forma k + 1 = ab,
con 1 < a ≤ b < k + 1. Pero a y b son menores que k + 1 y mayores que 1, de modo
que, por la Hipótesis de Inducción, existe un primo p tal que p|a, esto es a = pt, con
t ∈ Z. De modo que k + 1 = p (tb) y en consecuencia p|k + 1. Ası́, por el PIM-Fuerte,
concluimos que la afirmación es cierta para todo n > 1.
Teorema 2.53 (Teorema Fundamental de la Aritmética TFA). Todo número entero
n > 1, es primo o se puede expresar como un producto de primos y esta representación
es única, sin tener en cuenta el orden en el que aparecen los factores.

Demostración. Tarea.

Corolario 2.54. Cualquier entero n > 1, se puede escribir de forma única como

n = pk11 pk22 · · · pkr r , (2.2)

donde para cada i ∈ {1, 2, . . . , r} , ki es un entero positivo y cada pi es un número

primo, tal que p1 < p2 < · · · < pr .

A la representación del entero n > 1, dada en la expresión (2.2) se le llama factorización

prima de n o descomposición canónica de n.

Ejemplo 2.55. Encuentre la descomposición canónica de 3780.

Solución: Dividimos sistemáticamente por los primeros números primos ası́:

3780 2
1890 2
945 3
315 3
105 3
35 5
7 7
1

De donde, 3780 = 22 · 33 · 5 · 7.

Ejemplo 2.56. El producto de tres enteros mayores que 1 y distintos entre sı́ es 100.
¿Cuáles son los tres enteros?

Solución: Dado que 100 = 22 · 52 , tenemos que la única posibilidad para estos tres
números es: 2, 10, 5.

Ejemplo 2.57. ¿Cuál es el menor entero positivo que es divisible por todos los números
dı́gitos mayores que 0?

Solución: Tal número es

2 × 3 × 2 × 5 × 7 × 2 × 3 = 23 × 32 × 5 × 7 = 2520.
Ejemplo 2.58. Sea n un número natural tal que su factorización prima es

n = pn1 1 × pn2 2 × · · · × pnk k ,

esto es, los pi son números primos distintos y los ni son números enteros positivos.
Pruebe que la cantidad de divisores positivos de n está dada por

(n1 + 1)(n2 + 1) · · · (nk + 1).

Solución: Note que los divisores positivos de n deben ser de la forma

d = pa11 × pa22 × · · · × pakk ,

donde 0 ≤ ai ≤ ni , para cada i ∈ {1, 2, . . . , k} . Esto es, el exponente del primo pi en

la factorización del divisor d puede escogerse de ni + 1 formas. Ası́, por el principio
multiplicativo tenemos que el número de divisores positivos de n es:

(n1 + 1)(n2 + 1) · · · (nk + 1).

Ejemplo 2.59. ¿Cuántos divisores positivos tiene 10!?

Solución: Dado que

10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 28 × 34 × 52 × 7,

por el ejercicio anterior, tenemos que el número de divisores positivos de 10! es:

(8 + 1)(4 + 1)(2 + 1)(1 + 1) = 270.

Teorema 2.60. Sean a y b enteros positivos tales que:

a = pa11 pa22 · · · par r ,

b = pb11 pb22 · · · pbrr ,

donde ai ≥ 0 y bi ≥ 0 son enteros y los pi son primos diferentes, para cada i ∈

{1, 2, . . . , r} . Entonces

mcd(a, b) = pm1 m2 mr
1 p2 · · · pr ,

mcm(a, b) = pM 1 M2 Mr
1 p2 · · · pr ,

donde mi = mı́n {ai , bi } y Mi = máx {ai , bi } , para cada i ∈ {1, 2, . . . , r} .

Demostración. Se deja como ejercicio para el lector.

Ejemplo 2.61. Hallar mcd(360, 3780) y mcm(360, 3780).

Solución: Dado que

360 = 23 · 32 · 5 · 70 ,
3780 = 22 · 33 · 5 · 7.

Se tiene que

mcd(360, 3780) = 22 · 32 · 5 · 70 = 180,

mcm(360, 3780) = 23 · 33 · 5 · 7 = 7560.

Ejercicios 2.4

1. Pruebe los Corolarios 2.50 y 2.51.

2. Demuestre el Lema 2.52 usando el PBO.

3. Demuestre el Teorema 2.60.

(
p, si p|n
4. Pruebe que si p es primo y n ∈ Z, entonces mcd(n, p) =
1, si p ∤ n.
(
|n|, si p|n
Además, si n 6= 0, entonces mcm(n, p) =
p|n|, si p ∤ n.

5. Determine el número de divisores positivos de cada uno de los siguientes

números:

25 831.600 20202019
432 101000 20!

6. Si p y q son números primos distintos, ¿cuántos números de la forma pq × q p ,

tienen exactamente 48 divisores positivos? ¿Cuáles son?
2.5. Números Primos
¿Cómo decidir si n es primo?
El siguiente teorema establece que, para determinar si un número n es primo, basta
√
con probar que ninguno de los números primos menores que n es factor de n. Note
√
que, aunque n es “pequeño” respecto a n, este método no resulta eficiente si n es
muy “grande”.
Teorema 2.62. Sea n un número entero mayor que 1.
√ √
(a) Si n = ab, con a, b > 1, entonces a ≤ n o b ≤ n.
√
(b) Si n no tiene divisores primos menores o iguales que n, entonces n es primo.

Ejemplo 2.63. Pruebe que el número 281 es primo.

√
Solución: Puesto que 281 ≈ 16,7, por el Teorema anterior, basta con probar ninguno
√
los primos 2, 3, 5, 7, 11, 13 ≤ 281 divide a 281. Se deja como ejercicio al lector hacer
esta comprobación.
La Criba de Eratóstenes
La Criba de Eratóstenes, llamada ası́ en el honor al matemático, astrónomo y geógrafo
griego, Eratóstenes de Cirene (276-194 a.c); es un algoritmo que permite hallar todos
los números primos menores o iguales que un entero n > 1 dado. Este algoritmo
consiste en escribir la lista de todos los enteros desde 2 hasta n y comenzar a tachar
√
sistemáticamente todos los múltiplos de los primos menores o iguales que n en la
√
lista. Es decir, para cada primo p ≤ n se eliminan los enteros 2p, 3p, 4p, 5p, . . .
Los enteros no tachados al terminar este procedimiento son los números primos menores
o iguales a n.

Ejemplo 2.64. Determinar todos los números primos menores o iguales que 100.
√
Solución: Los primos menores o iguales que 100 = 10, son: 2, 3, 5 y 7, ası́ que,
luego de tachar en la siguiente tabla los múltiplos de estos primos, salvo ellos mismos,
obtendremos la lista de los números primos menores o iguales que 100.

2 3 4✁ 5 6✁ 7 8✁ 9✁ ✚
10
✚
11 ✚
12
✚ 13 ✚
14
✚ ✚
15
✚ ✚
16
✚ 17 ✚
18
✚ 19 ✚
20
✚
✚
21
✚ ✚
22
✚ 23 ✚
24
✚ ✚
25
✚ ✚
26
✚ ✚
27
✚ ✚
28
✚ 29 ✚
30
✚
31 ✚
32
✚ ✚
33
✚ ✚
34
✚ ✚
35
✚ ✚
36
✚ 37 ✚
38
✚ ✚
39
✚ ✚
40
✚
41 ✚
42
✚ 43 ✚
44
✚ ✚
45
✚ ✚
46
✚ 47 ✚
48
✚ ✚
49
✚ ✚
50
✚
✚
51
✚ ✚
52
✚ 53 ✚
54
✚ ✚
55
✚ ✚
56
✚ ✚
57
✚ ✚
58
✚ 59 ✚
60
✚
61 ✚
62
✚ ✚
63
✚ ✚
64
✚ ✚
65
✚ ✚
66
✚ 67 ✚
68
✚ ✚
69
✚ ✚
70
✚
71 ✚
72
✚ 73 ✚
74
✚ ✚
75
✚ ✚
76
✚ ✚
77
✚ ✚
78
✚ 79 ✚
80
✚
✚
81
✚ ✚
82
✚ 83 ✚
84
✚ ✚
85
✚ ✚
86
✚ ✚
87
✚ ✚
88
✚ 89 ✚
90
✚
✚
91 ✚
92 ✚
93 ✚
94 ✚
95 ✚
96 97 ✚
98 ✚
99 ✟✟
100
✚ ✚ ✚ ✚ ✚ ✚ ✚ ✚

¿Cuántos primos hay?

Teorema 2.65. (Euclides) Existen infinitos números primos.

Euclides formuló la primera demostración de este Teorema en la proposición 20 del

libro IX de su obra Elementos. Una adaptación común de esta demostración original
es la siguiente:

Demostración. Haremos la prueba por contradicción. Supongamos que el conjunto de

los números primos es finito. Sean p1 , p2 , . . . , pn todos los números primos, y definamos

N = p1 p2 · · · pn + 1.
Claramente N > 1, (pues uno de esos primos debe ser el 2) entonces, por el Lema 2.52,
existe un número primo p tal que p|N. Además, p|p1 p2 · · · pn , pues p debe ser alguno
de estos primos. Ası́ que
p|N − p1 p2 · · · pn = 1,

luego p = ±1, lo cual es absurdo. Por lo tanto deben existir infinitos números primos.

Observación 2.66. Una consecuencia de la prueba dada por Euclides del Teorema
2.65. es que, si pn es el n−ésimo número primo en su orden natural, entonces:

pn+1 ≤ p1 p2 · · · pn + 1 < pnn + 1.

Una mejor cota superior para el n−ésimo primo se establece en el siguiente teorema:
n−1
Teorema 2.67. Si pn es el n−ésimo número primo entonces pn ≤ 22 .

Solución: Usaremos el PIM-Fuerte. La afirmación es cierta para n = 1, pues p1 =

1−1 k−1
2 ≤ 22 = 2. Ahora, como hipótesis de inducción, supongamos que pk ≤ 22 , para
todo 1 ≤ k ≤ n y veamos que también se cumple para n + 1. En efecto, de la prueba de
Euclides del Teorema 2.65 observamos que

pn+1 ≤ p1 p2 p3 · · · pn + 1,
0 1 2 n−1
≤ 22 22 22 · · · 22 + 1,
2n −1 2n −1
≤2 +2 ,
2n −1 2n
≤2·2 =2 ;

donde la segunda desigualdad se sigue de la hipótesis de inducción y la tercera por la

n
identidad 20 + 21 + 22 + 2n−1 = 2n − 1 y el hecho que 1 ≤ 22 −1 . De lo anterior, por el
n−1
PIM-Fuerte, concluimos que pn ≤ 22 para todo entero positivo n.

Corolario 2.68. Dado un entero n > 1, existen al menos n + 1 números primos

n
menores que 22

Ejemplo 2.69. Para cada entero positivo n, existen n enteros cosecutivos compuestos.

Solución: Dado n entero positivo, considere la lista:

(n + 1)! + 2, (n + 1)! + 3, (n + 1)! + 4, . . . , (n + 1)! + (n + 1).

Observe que j| [(n + 1)! + j] , para cada 2 ≤ j ≤ n + 1, de ahı́ que la lista anterior
constituye un ejemplo de n enteros consecutivos compuestos.

El ejemplo anterior sugiere que los primos están espaciados irregularmente. Sin em-
bargo, si se denota por π(x) el número de primos menores o iguales que x, uno de
los resultados más impresionantes de la teorı́a avanzada de números, conocido como el
Teorema del Número Primo; proporciona una aproximación asintótica para π(x). Este
teorema establece lo siguiente:

Teorema 2.70 (Teorema del Número Primo). Sea π(x), la función contador de núme-
ros primos, esto es π(x) denota la cantidad de primos que no exceden a x. Entonces

π(x)
lı́m = 1.
x→∞ x/ ln(x)
Un problema que por siglos ha ocupado a algunos matemáticos es la existencia de
una fórmula “simple”, que genere todos los números primos o al menos una fórmula
“simple” que siempre de primos. Se creı́a que el polinomio cuadrático

f (n) = n2 + n + 41,

generaba números primos para cada entero no negativo n, y aunque esta afirmación es
cierta para 0 ≤ n ≤ 40, claramente para n = 41 la conjetura falla. Ahora, ¿existe un
polinomio no constante, con coeficientes enteros que devuelva solo números primos? La
respuesta a esta pregunta es negativa.

Teorema 2.71. No existe un polinomio no constante f (x) con coeficientes enteros, tal
que f (n) sea primo para todo entero n.

Demostración. Haremos la prueba por contradicción. Supongamos existe un polinomio

f (x) = am xm + · · · + a1 x + a0 ,

con m ≥ 1, ai ∈ Z para cada 0 ≤ i ≤ m, y ak 6= 0, para algún 1 ≤ k ≤ m; tal que f (n)

es primo para todo n ∈ Z. Note que si f (x0 ) = p, con p primo, para algún x0 ∈ Z,
entonces

f (x0 + tp) = am (x0 + tp)m + · · · + a1 (x0 + tp) + a0 ,

= am (xm m−1
0 + x0 p + · · · + x0 pm−1 + pm ) + · · · + a1 (x0 + tp) + a0 ,
= am xm
0 + · · · + a1 x0 + a0 + (múltiplo de p),

= f (x0 ) + (múltiplo de p)
= p + (múltiplo de p),

luego p|f (x0 + tp), para cada t ∈ Z. Pero p es primo y f (n) es primo para todo n ∈ Z,
entonces f (x0 + tp) = p, para cada t ∈ Z, de ahı́ que el polinomio g(x) = p − f (x)
tiene infinitas raı́ces, pero esto contradice el Teorema Fundamental del Álgebra. Por lo
tanto, f (n) no es primo para algún n ∈ Z.
Un teorema de P.G.L Dirichlet sobre primos en progresiones aritméticas, establece lo
siguiente:

Teorema 2.72 (Dirichlet). Si a y b son enteros positivos primos relativos, entonces la

progresión aritmética

a, a + b, a + 2b, a + 3b, . . . , a + nb, . . .

contiene un número infinito de primos.

Ejemplo 2.73. Muestre que existen infinitos primos que terminan en 999.

Solución: Note que mcd(999, 1000) = 1. Ası́, por el Teorema 2.72 tenemos que la pro-
gresión aritmetica definida por an = 1000n + 999 para cada n ≥ 1, contiene infinitos
números primos y todos ellos terminan en 999.

Aunque la demostración del Teorema 2.72 está fuera de los alcances del desarrollo
teórico de este curso, sı́ podemos demostrar algunos casos particulares como el siguiente.

Proposición 2.74. Existen infinitos primos de la forma 4k + 3.

Demostración. Haremos la prueba por contradicción. Suponga que existen finitos pri-
mos de la forma 4k + 3, a saber: p1 , p2 , . . . , pn , y consideremos el número

N = 4(p1 p2 · · · pn ) − 1 = 4(p1 p2 · · · pn − 1) + 3.

Sea N = r1 r2 · · · rs la descomposición en factores primos de N. Como N es impar,

entonces ri 6= 2, para cada 1 ≤ i ≤ s, ası́ que ri es de la forma 4k + 1 o 4k + 3. Pero
el producto de dos o más números de la forma 4k + 1 es de esta misma forma y N es
de la forma 4k + 3, entonces rj es de la forma 4k + 3, para algún 1 ≤ j ≤ s. Lo que
implica que rj es alguno de los primos pi y en consecuencia rj |(4(p1 p2 · · · pn ) − N) = 1
lo cual es absurdo. Por lo tanto deben existir infinitos primos de la forma 4k + 3.

Números primos de Mersenne

Proposición 2.75. Si n es un número natural y 2n − 1 es primo, entonces n es primo.

Demostración. Si 2n − 1 es primo entonces n ≥ 2 (ya que 21 − 1 = 1 no es primo).

Supongamos por absurdo que n es compuesto, entonces n = rs con 1 < r, s < n. Ası́,

2n − 1 = (2r )s − 1 = (2r − 1)(2r(s−1) + 2r(s−2) + · · · + 2r + 1).

De donde se tiene que 2n − 1 es compuesto, lo cual es absurdo. Por lo tanto n es
primo.

Los números primos de la forma 2n −1 se llaman números primos de Mersenne. A la fe-

cha se han encontrado 51 primos de Mersenne, el mayor de los cuales es 282589933 −1, con
24862048 dı́gitos. Los últimos 17 primos de Mersenne han sido encontrados por GIMPS
(Great Internet Mersenne Prime Search), fundada en 1996. Los voluntarios descargan
un programa gratuito para buscar estos primos, con un premio en efectivo ofrecido a
cualquiera que tenga la suerte de encontrar un nuevo primo. Si desea saber más sobre
esta búsqueda, visite la página principal de GIMPS, http://www.mersenne.org
¿Existen infinitos primos de Mersenne?

Números primos de Fermat

Proposición 2.76. Si n es un número natural y 2n + 1 es primo entonces n es una
potencia de 2.

Demostración. Si n es divisible por algún primo impar p entonces n = pr y ası́

2n + 1 = (2r )p + 1 = (2r + 1)(2r(p−1) − 2r(p−2) + · · · − 2r + 1),

de donde 2n + 1 serı́a compuesto, lo cual contradice la hipótesis. Por lo tanto, si 2n + 1

es primo, n tiene como único factor primo al 2, es decir que n es una potencia de 2.
n
Los números primos de la forma Fn = 22 + 1, con n ∈ N, se llaman números primos
de Fermat. A la fecha, solo se conocen cinco primos de Fermat, que son 3(n = 0),
5(n = 1), 17(n = 2), 257(n = 3) y 65537(n = 4). ¿Existen otros números primos de
Fermat?
 k
Ejemplo 2.77. Sea Fk = 22 + 1 el k−ésimo número primo de Fermat. Pruebe que
para cada entero positivo n se tiene que

F0 F1 F2 · · · Fn−1 = Fn − 2.
 k
Ejemplo 2.78. Sea Fk = 22 + 1 el k−ésimo número primo de Fermat. Pruebe que si
m y n son enteros positivos distintos, entonces Fm y Fn son primos relativos
Los números primos de Fermat también tienen un rol importante en la geometrı́a. El
siguiente teorema que caracteriza los polı́gonos regulares que pueden construirse con
regla y compás, demostrado por Gauss y Wantzel.

Teorema 2.79. Un polı́gono regular de n lados puede construirse con solo regla y
compás si y solo si n = 2α p1 p2 · · · pk , donde α es un entero no negativo y los pi son
números primos de Fermat distintos entre sı́, para cada i ∈ {1, 2, . . . , k} .

Ejercicios 2.5
√
1. ¿Puede un número compuesto n tener factores primos mayores que n?

2. Pruebe que el número 2017 es primo y encuentre el siguiente número primo.

3. Probar que todo primo diferente de 2 o 3 es de la forma 6k + 1 o 6k − 1.

4. Probar que todo entero de la forma 3k + 2 tiene un factor primo de la misma

forma.

5. Probar que todo entero de la forma 4k + 3 tiene un factor primo de la misma

forma.

6. Pruebe que existen infinitos primos de la forma 6k + 5.

7. Pruebe que si los n términos de la progresión aritmética

p, p + d, p + 2d, . . . , p + (n − 1)d,

son todos primos, entonces la diferencia común d es divisible por todo primo
q < n.

8. Demuestre que si f (x) es un polinomio no constante con coeficientes enteros,

entonces f (n) es un número compuesto para infinitos valores del entero n.
√
9. Muestre que si p es primo, el número n p no es racional.

10. Encuentre un divisor primo de la forma 4k + 3 para los números

N = 4(3 · 7 · 11) − 1 y M = 4(3 · 7 · 11 · 15) − 1.

11. Pruebe que si p y p2 + 8 son primos, entonces p3 + 4 también es primo.

Capı́tulo 3

Congruencias

3.1. Definición y algunas propiedades

En este capı́tulo n denotará un entero positivo.

Definición 3.1. Sea n un entero positivo fijo. Dos enteros a y b se dice que son
congruentes módulo n, denotado por

a ≡ b (mód n) ,

si n divide a a − b; es decir si existe un entero k tal que a − b = kn. En caso contrario

diremos que a y b son incongruentes módulo n, lo cual denotaremos por a 6≡ b (mód n) .

Ejemplo 3.2.

(a) 5 ≡ 7 (mód 2) , pues 5 − 7 = 2(−1).

(b) 2020 ≡ 1993 (mód 3) , pues 2020−1993 = 27 = 3(9). También 2020 ≡ 1993 (mód 9) .

(c) 5 6≡ −3 (mód 3) , ya que 5 − (−3) = 8 y 3 ∤ 8.

Proposición 3.3. Sean a, b, c, n ∈ Z, con n > 0. Entonces:

(a) a ≡ b (mód 1) .

(b) Si n|a, entonces a ≡ 0 (mód n) .

(c) Si c|n y a ≡ b (mód n), entonces a ≡ b (mód c) .

(d) Si a = qn + r, con q, r ∈ Z, entonces a ≡ r (mód n) .

Demostración.

48
(a) Claramente 1|(a − b).

(b) Si n|a, entonces n|(a − 0), esto es a ≡ 0 (mód n) .

(c) Dado que a ≡ b (mód n), esto es n|(a − b), se tiene que a − b = nk, para algún
k ∈ Z. Además c|n, luego existe t ∈ Z tal que n = ct. Ası́, a − b = ctk, de ahı́ que
a ≡ b (mód c) .

(d) Si a = qn+r, con q, r ∈ Z, entonces a−r = nq, de ahı́ que n|(a−r) y por definición
a ≡ r (mód n) .

Teorema 3.4. Dos enteros a y b son congruentes módulo n, si y solo si, dejan el
mismo residuo al dividirse entre n.

Demostración.

(=⇒) Suponga que a y b son congruentes módulo n. Entonces a − b = nk, para algún
k ∈ Z. Además, por el Algoritmo de la División, existen q, r ∈ Z, con 0 ≤ r < n,
tales que b = nq + r, donde r es el residuo que deja b al dividirse entre n. Ası́,

a = b + nk = nq + nk + r = n(q + k) + r,

de modo que a y b dejan el mismo residuo r al dividirse entre n.

(⇐=) Suponga que a y b dejan el mismo residuo r, al dividirse entre n. Por el Algoritmo
de la División, existen q, q ′, r ∈ Z tales que

a = nq + r,
b = nq ′ + r.

Ası́, a − b = n(q − q ′ ), luego n|(a − b) y por definición a ≡ b (mód n) .

El teorema anterior establece que dado un entero a, este es congruente módulo n, con
exactamente uno de los números del conjunto {0, 1, 2, . . . , n − 1} . A los conjuntos con
esta propiedad se les llama sistema completo de residuos módulo n.

Definición 3.5. Un sistema completo de residuos módulo n, es una colección de exac-

tamente n enteros {r1 , r2 , . . . , rn } tales que todo entero es congruente módulo n a uno
y solamente uno de los rk .
Ejemplo 3.6. El conjunto {−3, 0, 6, 23, 89} es un sistema completo de residuos módulo
5.

Proposición 3.7. Sean a, b, c números enteros. Entonces se tienen las siguientes pro-
piedades:

(a) (Reflexividad) a ≡ a (mód n) .

(b) (Simetrı́a) Si a ≡ b (mód n) , entonces b ≡ a (mód n) .

(c) (Transitividad) Si a ≡ b (mód n) y b ≡ c (mód n) , entonces a ≡ c (mód n) .

(d) Si a ≡ b (mód n) y c ≡ d (mód n) , entonces

a + c ≡ b + d (mód n) ,
ac ≡ bd (mód n) .

(e) Si a ≡ b (mód n) y k es un entero positivo, entonces:

ka ≡ kb (mód n) ,
ak ≡ bk (mód n) .

(f ) Si ac ≡ bc (mód n), entonces a ≡ b (mód n/d), donde d = mcd(c, n).

(g) Si ac ≡ bc (mód n) y mcd(c, n) = 1, entonces a ≡ b (mód n) .

(h) Si ac ≡ bc (mód nc), entonces a ≡ b (mód n) .

(i) Si a ≡ b (mód n) y a ≡ b (mód m) , entonces a ≡ b (mód mcm(n, m)) .

(j) Sean n1 , n2 , . . . , nk enteros positivos tales que a ≡ b (mód ni ) , para cada i ∈

{1, 2, . . . , k} . Entonces

a ≡ b (mód mcm(n1 , n2 , . . . , nk )) .

(k) Si los enteros positivos n1 , n2 , . . . , nk son primos relativos dos a dos y a ≡ b (mód ni )
para cada i ∈ {1, 2, . . . , k} , entonces

k
!
Y
a ≡ b mód ni .
i=1
Demostración. Las pruebas de los literales (a), (b), (c), (e), (g), (h), (j) y (k) se dejan
como ejercicio para el lector y como inspiración para tal fin, veremos las pruebas de
los demás:

(d) Si a ≡ b (mód n) y c ≡ d (mód n) , existen k, t ∈ Z tales que

a − b = nk,
c − d = nt.

De ahı́ que a − b + c − d = (a + c) − (b + d) = n(k + t), luego

a + c ≡ b + d (mód n) .

Ahora, observe que

ac − bd = (a − b)c + b(c − d) = nkc + bnt = n(kc + bt),

por lo tanto
ac ≡ bd (mód n) .

(f ) Sea d = mcd(c, n). Entonces c = dt y n = ds, con mcd(t, s) = 1. Además, si

ac ≡ bc (mód n), entonces ac − bc = c(a − b) = nk, para algún k ∈ Z. De modo
que:

c(a − b) = nk,
dt(a − b) = dsk,
t(a − b) = sk,

Luego s|t(a − b), pero mcd(t, s) = 1, entonces s|(a − b), esto es a ≡ b (mód s),
n
donde s = .
d
(i) Dado que a ≡ b (mód n) y a ≡ b (mód m) , entonces n|(a − b) y m|(a − b), y
por el item (iii) del Teorema 2.40, M|(a − b), con M = mcm(n, m). De ahı́ que
a ≡ b (mód M) .

Las propiedades (a), (b) y (c) establecen que la relación de congruencia módulo n
definida en Z, es una relación de equivalencia.
Ejemplo 3.8. No siempre se pueden cancelar factores en las congruencias, esto es, no
es cierto que si ac ≡ bc (mód n), entonces a ≡ b (mód n) . Por ejemplo,

(5)(3) ≡ (7)(3) (mód 6) , pero 5 6≡ 7 (mód 6) .

Ejemplo 3.9. Hallar el residuo que deja 72020 cuando se divide entre 8.

Solución: Dado que 7 ≡ −1 (mód 8), por el item (e) de la Proposición 3.7, se tiene que

72020 ≡ (−1)2020 (mód 8) ,

y (−1)2020 = 1, de ahı́ que 72020 deja residuo 1 al dividirse entre 8.

Ejemplo 3.10. Sean a y b enteros y p un número primo. Probar que

(a + b)p ≡ ap + bp (mód p) .

Solución: Por el Teorema del Binomio, tenemos que

     
p pp p−1 p p−2 2 p
(a + b) = a + a b+ a b +···+ abp−1 + bp .
1 2 p−1
     
p p p p p−1 p p−2 2 p
(a + b) − (a + b ) = a b+ a b +···+ abp−2 ,
1 2 p−1
(a + b)p − (ap + bp ) = pk;
 
 p
donde la última igualdad se sigue del hecho que p  , para cada 1 ≤ i ≤ p − 1,
i
(ejercicio para el lector) de ahı́ que

(a + b)p ≡ ap + bp (mód p) .
Ejemplo 3.11. Calcular el residuo de dividir 15196 por 13.

Solución: Note que

15196 ≡ 2196 (mód 13) , porque 15 ≡ 2 (mód 13) ,

49
≡ 24 (mód 13) , ya que 196 = 22 · 72 ,
≡ 349 (mód 13) , porque 24 = 16 ≡ 3 (mód 13) ,

7
≡ (33 )2 · 3 (mód 13) , propiedades de la potenciación,

7
≡ (1)2 · 3 (mód 13) , pues 33 = 27 ≡ 1 (mód 13) ,

2
≡ 33 · 3 (mód 13) , propiedades de la potenciación,
≡ 3 (mód 13) , pues 33 = 27 ≡ 1 (mód 13) .

Por lo tanto, el residuo que se obtiene al dividir 15196 entre 13 es 3.

Ejemplo 3.12. Resolver la ecuación 4x ≡ 8 (mód 12) para x ∈ {0, 1, 2, . . . , 11} .

Solución: Por la propiedad (h) de la Proposición 3.7, tenemos que x ≡ 2 (mód 3), esto
es x, deja residuo 2 al dividirse entre 3 y los x ∈ {0, 1, 2, . . . , 11} con esta propiedad
son: x = 2, 5, 8, 11.

Ejemplo 3.13. Probar que para todo entero positivo n, se tiene que 132n −1 es múltiplo
de 7.

Solución: Note que 13 ≡ −1 (mód 7) , luego 132 ≡ 1 (mód 7) , por lo tanto

132n ≡ 1 (mód 7) ,

para cada entero positivo n, esto es 7|(132n −1), o equivalentemente 132n −1 es múltiplo
de 7.
Ejemplo 3.14. Determine todos los enteros que al ser divididos por 2, 3, 4, 5 y 6 dejan
como residuo 1, 2, 3, 4 y 5, respectivamente.
Solución: Sea x un número que satisface tales condiciones, entonces

x ≡ 1 (mód 2) ⇐⇒ x ≡ −1 (mód 2) ,
x ≡ 2 (mód 3) ⇐⇒ x ≡ −1 (mód 3) ,
x ≡ 3 (mód 4) ⇐⇒ x ≡ −1 (mód 4) ,
x ≡ 4 (mód 5) ⇐⇒ x ≡ −1 (mód 5) ,
x ≡ 5 (mód 6) ⇐⇒ x ≡ −1 (mód 6) .

Ası́, por la propiedad (j) de la Proposición 3.7, tenemos que:

x ≡ −1 (mód mcm(2, 3, 4, 5, 6)) ,

x ≡ −1 (mód 60) ,
x + 1 = 60k, para algún entero k.

Por lo tanto, x = 60k − 1, esto es, los números que tienen la propiedad del enunciado
son los múltiplos de 60 menos 1.
 Ejercicios 3.1

1. Complete la prueba de la Proposición 3.7.

2. Deje en evidencia que n enteros consecutivos forman un sistema completo de

residuos módulo n.

3. Demuestre que cualquier conjunto de n enteros forma un sistema completo de

residuos módulo n si y sólo si ninguna pareja de estos enteros son congruentes
módulo n.

4. Pruebe que si a ≡ b (mód n) , entonces mcd(a, n) = mcd(b, n).

5. Encuentre el residuo que se obtiene al dividir 62020 entre 37.

7
6. Determinar el dı́gito de las unidades de 3100 + 77 .

7. Halle todas las soluciones de 5x ≡ 3 (mód 7) .

8. Muestre que si a es un entero entonces a4 ≡ 0 (mód 16) o a4 ≡ 1 (mód 16) .

9. Demuestre que no existen enteros x, y, z tales que

x4 + y 4 + z 4 = 2020.

10. Pruebe que 7 divide a 32n+1 + 2n+2, para todo entero positivo n.
3.2. Criterios de Divisibilidad
Dado un entero b > 1, cualquier entero positivo N se puede escribir de forma única,
como suma de múltiplos no negativos de potencias de b, ası́:

N = am bm + am−1 bm−1 + · · · + a1 b + a0 ,

donde 0 ≤ ai ≤ b − 1, para cada i ∈ {0, 1, 2, . . . , m} . (¿Por qué?)

Ası́, el número N lo podemos representar por:

N = (am · · · a1 a0 )b , (3.1)

lo que llamaremos representación de N en base b, y a los números 0 ≤ ai ≤ b − 1, los

llamaremos la cifras de N en la representación en base b.

Ejemplo 3.15 (Sistema Binario). La presentación en base b = 2, de un número se

denomina representación binaria, note que en este caso las cifras son ceros o unos, esto
es ai ∈ {0, 1} .

Ejemplo 3.16 (Sistema decimal). La presentación en base b = 10, de un número se

denomina representación decimal.
Teorema 3.17 (Criterios de divisibilidad del 2, 5 y 10). Sea N = (ak · · · a1 a0 )10 . En-
tonces N es divisible por

(a) 2 si y solo si a0 ∈ {0, 2, 4, 6, 8} .

(b) 5 si y solo si a0 ∈ {0, 5} .

(c) 10 si y solo si a0 = 0.

Demostración. Por el algoritmo de la división, N = 10q + a0 , donde q ∈ Z y

a0 ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ,

es la cifra de las unidades de N. De modo que

2|N ⇐⇒ 2|a0 ⇐⇒ a0 ∈ {0, 2, 4, 6, 8}
5|N ⇐⇒ 5|a0 ⇐⇒ a0 ∈ {0, 5}
10|N ⇐⇒ 2|a0 y 5|a0 ⇐⇒ a0 = 0.

En general, si m ≥ 1, entonces
N = q10m + b,

donde q ∈ Z y b corresponde al número formado por las m últimas cifras de la repre-

sentación decimal de N note que 0 ≤ b < 10m . De manera que, si d|10m , entonces

d|N ⇐⇒ d|b.

De este hecho se pueden deducir criterios de divisibilidad a partir del estudio de las
últimas cifras de un número, por ejemplo:
Teorema 3.18. Un número N es divisible por:

(a) 4 si y solo si el número formado por las dos últimas cifras de su desarrollo decimal
es divisible por 4.

(b) 25 si y solo si el número formado por sus dos últimas cifras de su desarrollo decimal
es divisible por 25.

(c) 8 si y solo si el número formado por sus tres últimas cifras es divisible por 8.

Demostración. Ejercicio para el lector.

 m
X
Teorema 3.19. Sea P = ck xk un polinomio con coeficientes enteros, esto es ck ∈ Z.
k=0
Si a ≡ b (mód n), entonces P (a) ≡ P (b) (mód n) .

Demostración. Se sigue de las propiedades de la Proposición 3.7.

Teorema 3.20 (Criterios de divisibilidad del 3, 9 y 11). Un número N es divisible por:

(a) 3 si y solo si la suma de sus cifras de su representación decimal es múltiplo de 3.

(b) 9 si y solo si la suma de sus cifras de su representación decimal es múltiplo de 9.

(c) 11 si y solo si la suma alternada de sus cifras de su representación decimal es

múltiplo de 11.

Demostración. Sea N = am 10m + am−1 10m−1 + · · · + a1 10 + a0 , el desarrollo decimal

Xm
de N y P (x) = ak xk . Entonces
k=0

P (10) = N,
P (1) = a0 + a1 + · · · + am−1 + am
P (−1) = a0 − a1 + · · · + (−1)m−1 am−1 + (−1)m am

Además

10 ≡ 1 (mód 3) ,
10 ≡ 1 (mód 9) ,
10 ≡ −1 (mód 11)

Ası́, por el Teorema 3.19 tenemos que

N ≡ a0 + a1 + · · · + am−1 + am (mód 3) ,
N ≡ a0 + a1 + · · · + am−1 + am (mód 9) ,
N ≡ a0 − a1 + · · · + (−1)m−1 am−1 + (−1)m am (mód 11) .

De donde se obtienen los criterios que se querı́an probar.

Ejemplo 3.21. Determinar el residuo del número 67320 al dividirse por 2, 3, 4, 5, 6, 8, 9, 10, 11.
En general tomando la representación de un número N en base 10t , con t ≥ 1 tenemos
Xm
que N = ak 10tk , donde los ak son los bloques de t cifras de la representación decimal
k=0
m
X
de N. Ası́, tomando el polinomio P (x) = ak xk tenemos que
k=0

P 10t = N,
P (1) = a0 + a1 + · · · + am−1 + am ,
P (−1) = a0 − a1 + · · · + (−1)m−1 am−1 + (−1)m am .

De modo que si 10t ≡ 1 (mód n) o 10t ≡ −1 (mód n) entonces

N ≡ a0 + a1 + · · · + am−1 + am (mód n) , o
N ≡ a0 − a1 + · · · + (−1)m−1 am−1 + (−1)m am (mód n) ,

respectivamente. Lo anterior permite establecer criterios de divisibilidad para los divi-

sores de 10t − 1 o 10t + 1.

Ejemplo 3.22 (Criterio de divisibilidad del 37). Dado que 103 − 1 = 33 · 37, tomando
t = 3 en nuestro análisis anterior, podemos establecer que un número N es divisible
por 37 si y solo si la suma de sus cifras (en la representación decimal) en bloques de 3
es divisible por 37. Aplicando este criterio al número 159840 tenemos que

37|159840 ⇐⇒ 37| (159 + 840) ⇐⇒ 37|999,

y esto último se puede verificar fácilmente.

Ejemplo 3.23 (Criterios de divisibilidad del 7 y del 13). Dado que 103 + 1 = 7 · 11 · 13,
tomando t = 3 en nuestro análisis anterior, podemos establecer que un número N es
divisible por 7 (respectivamente por 13) si y solo si la suma alternada de sus cifras (en
la representación decimal) en bloques de 3 es divisible por 7 (respectivamente por 13)
Aplicando este criterio al número 83538 tenemos:

7|83538 ⇐⇒ 7| (−083 + 538) ⇐⇒ 7|455,

13|83538 ⇐⇒ 13| (−083 + 538) ⇐⇒ 13|455.

Observación 3.24 (Criterios de divisibilidad del 6 y del 18). Si d1 y d2 son primos

relativos, entonces un número N es divisible por d1 d2 si y solo si N es divisible por d1
y d2 . Ası́, por ejemplo, 6|N si y solo si 2|N y 3|N y también 18|N si y solo si 2|N y
9|N. De este modo, bastarı́a tener criterios de divisibilidad para primos o potencias de
primos.

Ejemplo 3.25. Determine el residuo que deja el número |11 . {z

. . 111} cuando se divide
1000 unos
por: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, y 37.

Ejercicios 3.2

1. Demuestre el Teorema 3.18.

2. Enuncie y demuestre criterios de divisibilidad para los números 50, 40, 2n ,

5n , y 2n × 5m , con m, n ∈ Z.

3. Establezca, razonadamente, criterios de divisibilidad para los números 99,

101, 41, 271, 73, 137, 999, 17, 19, 23.
3.3. Ecuaciones diofánticas lineales
Una ecuación diofántica es una ecuación en una o más variables que se resuelve en
los números enteros. En esta sección estudiaremos la ecuación diofántica lineal de dos
variables
ax + by = c,

donde a, b, c son enteros fijos y ab 6= 0. Una solución de esta ecuación es un par ordenado
(x0 , y0 ) de números enteros tal que ax0 + by0 = c.

Ejemplo 3.26. Determinar, si existe, una solución para la ecuación diofántica

2x + 6y = 13.

Solución: Reescribiendo la ecuación en la forma

2(x + 3y) = 13,

se observa que la parte izquierda es un número par, pero la parte derecha es un número
impar, lo cual es imposible. De mmanera que esta ecuación no tiene solución.

Ejemplo 3.27. Determinar, si existe, una solución para la ecuación diofántica

2x + 3y = 2.

Solución: esta ecuación corresponde a una recta en la plano cartesiano, y sus soluciones
enteras corresponden a los puntos (x, y) con coordenadas enteras que están sobre la
recta. Veamos:

b 4

3
b 2

0 b

−7 −6 −5 −4 −3 −2 −1 0 1 2 3 4 5 6
−1

−2 b

−3

−4 b

−5
De donde (1, 0), (−2, 2), (−5, 4), (4, −2) . . . son soluciones de esta ecuación.

Teorema 3.28. Sea d = mcd(a, b). La ecuación lineal diofántica

ax + by = c, (3.2)

tiene solución si y sólo si d|c. Además, si (x0 , y0 ) es una solución de esta ecuación,
entonces todas las soluciones están dadas por:

b a
x = x0 + t, y = y0 − t, (3.3)
d d
para cada t ∈ Z.

Demostración. Sea d = mcd(a, b).

(=⇒) Si existen x, y ∈ Z tales que ax + by = c, entonces d|c, pues d|a y d|b.

(⇐=) Por el Algoritmo de Euclides, existen s, t ∈ Z, tales que as + bt = d, y si d|c,

entonces c = dk, para algún k ∈ Z, de modo que

c = dk = a(ks) + b(kt),

luego x = ks y y = kt es una solución de la ecuación lineal diofántica

ax + by = c.

Ahora, claramente (3.3) es solución de la ecuación (3.2), para cada t ∈ Z. Veamos que
toda solución de (3.2) es de la forma (3.3). En efecto, sea (x0 , y0 ) una solución dada de
la ecuación ax + by = c. Si (x′ , y ′) es otra solución de esta ecuación, entonces

ax0 + by0 = ax′ + by ′ = c,

b(y0 − y ′ ) = a(x′ − x0 ).

Por otra parte, como d = mcd(a, b), existen r, u ∈ Z, tales que a = dr y b = du, con
mcd(r, u) = 1. De modo que

du(y0 − y ′ ) = dr(x′ − x0 ),
u(y0 − y ′ ) = r(x′ − x0 ).
Luego, r|u(y0 − y ′), pero mcd(r, u) = 1, entonces r|(y0 − y ′), de ahı́ que

y0 − y ′ = rt,
x′ − x0 = ut,

para algún t ∈ Z. Por lo tanto,

b a
x′ = x0 + t, y ′ = y0 − t.
d d

Ejemplo 3.29. Determine, si existen, todas las soluciones de las siguientes ecuaciones
diofánticas:

(a) 66x + 117y = 85 (c) 15x + 17y = 21

(b) 7x + 5y = 0 (d) 21x + 105y = 3

Solución:

(a) Dado que mcd(66, 117) = 3 y 3 ∤ 85, por el Teorema anterior, la ecuación 66x +
117y = 85 no tiene solución en los enteros.

(b) Una solución particular para la ecuación diofántica lineal homogénea 7x + 5y = 0

es (0, 0). Además mcd(7, 5) = 1, ası́ que, la solución general está dada por:

x = 5t,
y = −7t.

para cada t ∈ Z.

(c) Dado que mcd(15, 17) = 1, la ecuación tiene solución. Por el Algoritmo de Euclides
(o graficamente) encontramos que

15(8) + 17(−7) = 1,

Luego,

15(8 × 21) + 17(−7 × 21) = 1 × 21,

15(168) + 17(−147) = 21.
 Ası́ que una solución particular para la ecuación orginal es (168, −147) y la solución
general está dada por:

x = 168 + 17t,
y = −147 − 15t.

(d) Dado que mcd(21, 105) = 21 pero 21 ∤ 3, entonces la ecuación 21x + 105y = 3 no
tiene solución en los enteros.

Ejemplo 3.30. Un hombre compró 12 frutas entre manzanas y naranjas, por 99 pesos.
Si una manzana cuesta 3 pesos más que una naranja, y el hombre compró el más
manzanas que naranjas, ¿cuántas frutas de cada una compró?

Solución: Sean x y y el número de manzanas y narajas, respectivamente, que compró

el hombre, y p el precio de una naranja. Entonces el precio de una manzana es p + 3
y del enunciado tenemos:

x + y = 12,
x(p + 3) + yp = 99,
p(x + y) + 3x = 99,
12p + 3x = 99,
4p + x = 33.

Una solución particular de la última ecuación es p = 0, x = 33, luego la solución

general es:

p = t,
x = 33 − 4t.

Pero, como el número de manzanas es mayor que el número de narajas entonces x ≥ 7,

y además x ≤ 12, de ahı́ que:

7 ≤ 33 − 4t ≤ 12,
5,25 ≤ t ≤ 6,5.

Por lo anterior, t = 6, de ahı́ que el hombre compró x = 9 manzanas y y = 3 naranjas.

 Ejercicios 3.3

1. Pruebe que si a y b son primos relativos, la ecuación diofántica ax + by = c

tiene infinitas soluciones para todo c ∈ Z. ¿Cuáles son sus soluciones?

2. Determine, si existen, todas las soluciones de las siguientes ecuaciones

diofánticas:

(a) 60x + 18y = 97 (e) 30x + 16y = 2

(b) 15x + 39y = 42 (f ) 30x + 16y = 2020
(c) 105x + 45y = 11 (g) 21x + 14y = 147
(d) 30x + 16y = 0 (h) 101x + 97y = 100

3. Demuestre que la ecuación diofántica ax + by + cz = d tiene solución si y solo

si mcd(a, b, c) divide a d.

4. Encuentre todas las soluciones enteras de la ecuación 15x + 12y + 30z = 24.

5. Resolver los siguientes sistema de ecuaciones diofánticas lineales en tres va-

riables
( (
x + 2y + 3z = 23 2x + 3y + 5z = 100
a) b)
x + 6y + 9z = 35 30x + 6y + 21z = 120

6. En una bolsa hay monedas de 50, 100 y 200 pesos. Se sabe que hay en total
24 monedas y que su valor es 2000 pesos. ¿Qué combinaciones de monedas
son posibles?

7. Resolver el siguiente acertijo, propuesto en el siglo IX por el astrónomo indio

Mahavira: un grupo de 23 viajeros llega a un campamento y encuentra 63
montones de sacos, todos con el mismo número de sacos, y un montón adicio-
nal con 7 sacos. Si sabemos que los viajeros no podrán cargar con más de 50
sacos y pudieron repartı́rselos por igual y sin abrirlos, ¿cuántos sacos habı́a
en cada uno de los montones?

8. En cierta fábrica tienen tres empleados que se encargan de armar cajas.

Matı́as arma 107 cajas por dı́a, Lucas arma 301 cajas por dı́a y Pablo ar-
ma 213 cajas por dı́a. En los primeros 30 dı́as hábiles del año armaron en
total 16000 cajas. ¿Cuántos dı́as faltó cada uno al trabajo, en ese lapso?
3.4. Congruencias Lineales
Definición 3.31. Una ecuación de la forma ax ≡ b (mód n) se denomina una congruen-
cia lineal. Una solución de esta congruencia es un entero x0 tal que ax0 ≡ b (mód n)
Observación 3.32. Por definición

ax ≡ b (mód n) ⇐⇒ ax − b = ny, para algún entero y

⇐⇒ ax − ny = b.

Luego el problema de encontrar una solución para la congruencia lineal ax ≡ b (mód n)

equivale a encontrar las soluciones de la ecuación diofántica lineal ax − ny = b.
Teorema 3.33. Sea d = mcd(a, n). La congruencia lineal ax ≡ b (mód n) tiene so-
lución si y sólo si d|b. Además, si d|b, entonces la congruencia tiene exactamente d
soluciones mutuamente incongruentes (diferentes) módulo n, a saber:

n 2n (d − 1)n
x0 , x0 + , x0 + , . . . , x0 + ,
d d d
donde x0 es una solución particular.
Corolario 3.34. Si mcd(a, n) = 1, la congruencia lineal ax ≡ b (mód n) tiene solución
única módulo n.
Definición 3.35. Un entero b es llamado inverso multiplicativo de un entero a módulo
n, si ab ≡ 1 (mód n) .
Observación 3.36. Dado un entero a, del Corolario 3.34 tenemos que a tiene un
inverso multiplicativo módulo n si y sólo si a es primo relativo con n. Además, cuando
existe, el inverso multiplicativo es único.
Ejemplo 3.37. Determine el inverso múltiplicativo 3 módulo 7.
Solución: Se trata de encontrar una solución de la congruencia 3x ≡ 1 (mód 7) . Dado
que mcd(3, 7) = 1, sabemos que esta solución existe y es única. Por inspección se ve
que tal solución es x ≡ 5 (mód 7) , ya que 3 · 5 ≡ 1 (mód 7) .
Ejemplo 3.38. Resolver la congruencia 18x ≡ 30 (mód 42) .
Solución: dado que mcd(18, 42) = 6 y 6|30 entonces la congruencia tiene exactamente
6 soluciones diferentes módulo 42. Usando propiedades de las congruencias tenemos

18x ≡ 30 (mód 42) ,

3x ≡ 5 (mód 7) ,
multiplicando la última congruencia por 5 (el inverso de 3 módulo 7, tenemos:

15x ≡ 25 (mód 7) ,
x ≡ 4 (mód 7) .

Por lo tanto, las 6 diferentes soluciones de la congruencia original están dadas por:

42 2 × 42 3 × 42 4 × 42 5 × 42
4, 4 + , 4+ , 4+ , 4+ , 4+ ,
6 6 6 6 6
es decir: 4, 11, 18, 25, 32, 39.

Ejemplo 3.39. Un profesor compró lápices y borradores por $24.900. Si cada borrador
costó $290, cada lápiz, $330, y compró más lápices que borradores, ¿cuántos lápices y
cuántos borradores compró el profesor?

Solución: Sea x el número de lápices y y el número de borradores, entonces

330x + 290y = 24900.

Dado que mcd(330, 290) = 10, la ecuación tiene solución. En efecto, por propiedades
de las congruencias tenemos:

29y ≡ 2490 (mód 33) ,

−4y ≡ 15 (mód 33) ,
−32y ≡ 120 (mód 33) ,
y ≡ 21 (mód 33) ,

De modo que la solución general de la ecuación diofántica inicial está dada por

y = 21 + 33t,
x = 57 − 29t.

Dado que x, y ≥ 0, entonces t = 0 o t = 1, de ahı́ que (x, y) = (57, 21) o (x, y) =

(28, 54), pero el profesor compró más lápices que borradores, ası́ que el número de
lápices comprados fue 57 y de borradores, 21.
Teorema 3.40 (Teorema Chino de los Restos). Sean a1 , a2 , . . . , ak enteros arbitrarios
y n1 , n2 , · · · , nk enteros positivos, primos relativos entre sı́, esto es mcd(ni , nj ) = 1, si
i 6= j. Entonces el sistema de congruencias lineales


 x ≡ a1 (mód n1 ) ,


 x ≡ a2 (mód n2 ) ,
.. (3.4)


 .

 x ≡ a (mód n ) ,
k k

tiene solución única, módulo n1 n2 . . . nk ,

N
Demostración. Sea N = n1 n2 . . . nk . Definimos qi = , para cada i ∈ {1, 2, . . . , k} .
ni
Dado que mcd(qi , ni ) = 1, existe ri , el inverso de qi módulo ni , esto es

qi ri ≡ 1 (mód ni ) , para cada i ∈ {1, 2, . . . , k} . (3.5)

Sea
k
X
x= ai qi ri = a1 q1 r1 + a2 q2 r2 + · · · + ak qk rk ,
i=1

entonces x es solución del sistema de congruencias (3.4). De hecho, note que ni |qj ,
siempre que i 6= j, luego

x ≡ ai qi ri (mód ni ) , para cada i ∈ {1, 2, . . . , k} .

Ası́, por (3.5),

x ≡ ai (mód ni ) , para cada i ∈ {1, 2, . . . , k} .

Finalmente, vemos que esta solución es única módulo n1 n2 . . . nk . En efecto, si y es otra

solución del sistema de congruencias (3.4), entonces

y ≡ ai (mód ni ) , para cada i ∈ {1, 2, . . . , k} ,

de modo que ni |(x − y), luego mcm(n1 , n2 , . . . , nk )|(x − y), esto es

x ≡ y (mód n1 n2 . . . nk ) .

La demostración del Teorema Chino de los Restos que acabamos de estudiar es cons-
tructiva, esto quiere decir que nos brinda un método para determinar la solución única
del sistema de congruencias (3.4). Veamos:
Ejemplo 3.41. Determinar el menor entero positivo que deja residuo 2 cuando se
divide entre 5, 4 cuando se divide entre 7 y 5 cuando se divide entre 11.

Solución: Se trata de resolver el sistema de congruencias


 x ≡ 2 (mód 5)

x ≡ 4 (mód 7)


x ≡ 5 (mód 11)

Usando la notación de la demostración del Teorema 3.40,

N = 5 × 7 × 11 = 385,
q1 = 7 × 11 = 77,
q2 = 5 × 11 = 55,
q3 = 5 × 7 = 35.

Ahora, hallamos los inversos de qi módulo ni , esto lo podemos hacer por inspección o
usando el Algortimo de Euclides, como sigue:

5(31) + 77(−2) = 1 =⇒ 5(31) = 1 − 77(−2),

=⇒ 5|(1 − 77(−2)),
=⇒ 77(−2) ≡ 1 (mód 5) .
=⇒ r1 = −2.
7(8) + 55(−1) = 1 =⇒ 55(−1) ≡ 1 (mód 7) ,
=⇒ r2 = −1.
11(16) + 35(−5) = 1 =⇒ 35(−5) ≡ 1 (mód 11) ,
=⇒ r3 = −5.

De modo que la solución, módulo 5 × 7 × 11 del sistema de congruencias, está dada por

x = (2)(77)(−2) + (4)(55)(−1) + (5)(35)(−5) = −1403 ≡ 137 (mód 385) .

Por lo tanto el número buscado es 137.

El siguiente es un problema clásico, se encuentra en trabajos del matemático indio
Bhaskara (siglo VI), también aparece en trabajos del matemático egipcio Al-Hasan
(siglo XI) y en la obra Liberacci de Fibonacci.

Ejemplo 3.42. Una mujer fue al mercado y un caballo quebró los huevos que tenı́a
en su canasto. El dueño del caballo ofreció pagarle por el daño causado. Le preguntó
cuántos huevos habı́a quebrado su caballo. La mujer dijo que no sabı́a, pero recordó que
cuando los ordenó de dos en dos, quedaba uno. Igual cosa sucedió cuando los ordenó
en grupos de 3, de 4, de 5, y de 6. Pero cuando los ordenó en grupos de 7, no quedó
ninguno. ¿Cuál es la mı́nima cantidad de huevos que habı́a en el canasto?

Solución: Se trata de resolver el sistema de congruencias:



 x ≡ 1 (mód 2) ,




 x ≡ 1 (mód 3) ,

 x ≡ 1 (mód 4) ,


 x ≡ 1 (mód 5) ,

 x ≡ 1 (mód

 6) ,


x ≡ 0 (mód 7) .

Por la Propiedad (j) del la Proposición 3.7, este sistema se puede reducir al siguiente:

 x ≡ 1 (mód 12) ,

x ≡ 1 (mód 5) ,


x ≡ 0 (mód 7) .

Y ahora estamos en condiciones de aplicar el Teorema Chino de los Restos, se deja

como ejercicio para el lector terminar esta solución.
 Ejercicios 3.4

1. Determine el menor entero positivo de cuatro cifras, múltiplo de 13, cuya cifra
de las unidades es 4, y al ser dividido por 7 deja residuo 2.

2. Resolver el sistema de congruencias



 2x ≡ 7 (mód 3)


 x ≡ 2 (mód 4)


5x ≡ 4 (mód 6)




 x ≡ 0 (mód 5)

 3x ≡ 5 (mód 7)

3. Resolver la congruencia lineal 17x ≡ 9 (mód 276) .

4. Un juego especial de naipes se compone de n cartas. Si se distribuye equitati-

vamente entre 7 jugadores queda una carta. Si se distribuye entre 11 jugadores
quedan 10 cartas. ¿Cuáles son los posibles valores de n? ¿Cuál es la mı́nima
cantidad de cartas que tiene el juego de naipes?

5. Una banda de 17 piratas se apodera de un botı́n compuesto por monedas de

oro de igual valor. Deciden repartirse el botı́n en partes iguales y dar el resto
al cocinero chino. Ası́, el cocinero recibirı́a tres monedas. Pero los piratas
se pelean entre ellos y seis de ellos mueren en la riña. El cocinero recibirı́a
entonces 4 monedas. Posteriormente ocurre un naufragio y solo 6 piratas, el
cocinero y el tesoro se salvan. La nueva repartición dejarı́a 5 monedas de oro
al cocinero. ¿Cuál es la fortuna mı́nima que esperarı́a el cocinero si decide
liquidar al resto de los piratas?

6. Pruebe la siguiente generalización del Teorema Chino de los restos:

El sistema de congruencias
(
x ≡ a (mód m)
x ≡ b (mód n)

tiene solución si y solo si mcd(m, n)|(a − b). En caso de tener solución, esta
es única módulo mcm(m, n).
3.5. Teoremas de Fermat, Wilson y Euler
Teorema 3.43 (Pequeño Teorema de Fermat). Sea a un entero y p un primo tal que
p ∤ a, entonces
ap−1 ≡ 1 (mód p) .

Demostración. Note que cada uno de los números del conjunto

{a, 2a, 3a, . . . , (p − 1)a} ,

son incongruentes dos a dos módulo p y primos relativos con p. En efecto, si ra ≡

sa (mód p) , con 1 ≤ r < s ≤ p − 1, entonces r ≡ s (mód p) , lo cual es imposible.
Ası́, el conjunto anterior debe ser congruente módulo p al conjunto {1, 2, . . . , p − 1}
en algún orden, de modo que,

a(2a)(3a) · · · ((p − 1)a) ≡ (1)(2)(3) · · · (p − 1) (mód p) .

ap−1 (p − 1)! ≡ (p − 1)! (mód p) .

Pero mcd(p, (p − 1)!) = 1, luego

ap−1 ≡ 1 (mód p) .

Corolario 3.44. Si p es un primo, entonces ap ≡ a (mód p) , para cualquier entero a.

Demostración. Si p|a entonces ap ≡ a ≡ 0 (mód p) . Si p ∤ a, por el Pequeño Teorema

de Fermat, ap−1 ≡ 1 (mód p) , de ahı́ que ap ≡ a (mód p) .

Ejemplo 3.45. Encuentre el residuo que se obtiene al dividir 13 · 1245 entre 47.

Solución: Por el Pequeño Teorema de Fermat, se tiene que

1246 ≡ 1 (mód 47) .

Luego,

12 · 1245 ≡ 1 (mód 47) ,

(4 · 12)1245 ≡ 4 (mód 47) ,
1245 ≡ 4 (mód 47) ,
13 · 1245 ≡ 52 ≡ 5 (mód 47) .

Por lo tanto, el residuo que se obtiene al dividir 13 · 1245 entre 47 es 5.

Ejemplo 3.46. Pruebe que 17 divide al número 11104 + 1

Solución: Por el Pequeño Teorema de Fermat, se tiene que

1116 ≡ 1 (mód 17) ,

luego

6
1116 = 1196 ≡ 1 (mód 17) ,

Además,

11 ≡ −6 (mód 17) ,
112 ≡ 36 ≡ 2 (mód 17) ,
118 ≡ 24 = 16 ≡ −1 (mód 17) ,

Por lo tanto,
11104 ≡ −1 (mód 17) ,

de ahı́ que 17 divide a 11104 + 1.

Lema 3.47. Sea p un número primo y a un entero. Entonces a2 ≡ 1 (mód p) , si y

solo si a ≡ 1 (mód p) o a ≡ p − 1 (mód p) .

Demostración. Se deja como ejercicio para el lector.

Teorema 3.48 (Teorema de Wilson). Si p es un número primo, entonces

(p − 1)! ≡ −1 (mód p)

Demostración. El resultado se verifica directamente para p = 2 y p = 3. Suponga que

p > 3. Sea a un entero tal que 2 ≤ a ≤ p − 2, y a el inverso multiplicativo de a módulo
p. Entonces 2 ≤ a ≤ p − 2, y a 6= a (¿Por qué?). Ası́, podemos agrupar los enteros
2, 3, . . . , p − 2 en parejas (a, a), tales que aa ≡ 1 (mód p), de ahı́ que

(2)(3) · · · (p − 2) ≡ 1 (mód p) ,

Finalmente, multiplicando por p − 1 se tiene que

(p − 1)! ≡ −1 (mód p) .

El recı́proco del Teorema de Wilson también es cierto,

Teorema 3.49. Si p es un entero tal que (p − 1)! ≡ −1 (mód p) , entonces p es primo.

Demostración. Haremos la prueba por contradicción. Supongamos que p no es primo,

entonces p debe tener un divisor d tal que 1 < d < p − 1, luego d|(p − 1)!. Por hipótesis,
(p − 1)! ≡ −1 (mód p) , esto es p|((p − 1)! + 1), luego d|1, pero esto es absurdo. Ası́ que
p debe ser un número primo.

Los teoremas anteriores establecen el siguiente test de primalidad:

Teorema 3.50 (Test de primalidad). Un entero p > 1 es primo si y solo si

(p − 1)! ≡ −1 (mód p) .
Proposición 3.51. Si p es primo, la congruencia x2 ≡ −1 (mód p) tiene solución si
y solo si p = 2 o bien p ≡ 1 (mód 4) .

Demostración.

(=⇒) Sea a una solución de la congruencia x2 ≡ −1 (mód p) . Entonces p ∤ a. Para ver

que p = 2 o bien p ≡ 1 (mód 4) , basta probar que p 6≡ 3 (mód 4) . En efecto, si
p ≡ 3 (mód 4) , entonces p−1
2
es impar, y como a2 ≡ −1 (mód p) , se tiene que

p−1 p−1
ap−1 = a2 2
≡ (−1) 2 (mód p) ≡ −1 (mód p) ,

lo cual es absurdo, pues por el Pequeño Teorema de Fermat, se tiene que ap−1 ≡
1 (mód p) .

(⇐=) Si p = 2 todo impar es solución de la congruencia x2 ≡ −1 (mód 2) . Ahora, si

p ≡ 1 (mód 4) , entonces p−1
2
es par. Claramente,

1 ≡ −(p − 1) (mód p) ,
2 ≡ −(p − 2) (mód p) ,
..
.
p−1 p+1
≡− (mód p) .
2 2
Note que el número de congruencias listadas es par, ası́ que al multiplicarlas todas
se obtiene  
p−1 p+1
! ≡ (p − 1)(p − 2) · · · (mód p) ,
2 2


multiplicando la última congruencia por p−12
! se tiene
  2
p−1
! ≡ (p − 1)! (mód p) ,
2

y por el Teorema de Wilson,

  2
p−1
! ≡ −1 (mód p) ,
2
p−1


de ahı́ que x = 2
! es una solución de la congruencia.
Definición 3.52. Sea n un entero positivo. Se define φ(n) como el número de enteros
positivos menores o iguales a n que son primos relativos con n, esto es:
 
φ(n) =  k ∈ Z+ : k ≤ n ∧ mcd(k, n) = 1  .

1
A la función φ : N −→ N se le denomina función phi de Euler.

Ejemplo 3.53.

φ(1) = 1.

φ(6) = 2, ya que de los números 1, 2, 3, 4, 5 y 6 solamente 1 y 5 son primos

relativos con 6.

Si p es primo, φ(p) = p − 1.

El siguiente Teorema establece una generalización del Pequeño Teorema de Fermat.

Teorema 3.54 (Teorema de Euler). Si mcd(a, n) = 1, entonces

aφ(n) ≡ 1 (mód n) .

Demostración. Sean c1 , c2 , . . . , cφ(n) los elementos del conjunto {1, 2, . . . , n} que son
primos relativos con n. Por el algoritmo de la división, existen qi , ri ∈ Z tales que

aci = qi n + ri ,

con 0 ≤ ri < n, para cada i ∈ {1, 2, . . . , φ(n)} . Note que los residuos ri son todos
diferentes, ya que si ri = rj entonces aci ≡ acj (mód n) , luego ci ≡ cj (mód n) , pues
mcd(a, n) = 1, pero esto es absurdo. Además,

mcd(ri , n) = mcd(aci , n) = 1.

De lo que se concluye que

 
c1 , c2 , . . . , cφ(n) = r1 , r2 , . . . , rφ(n) .

Pero ri ≡ aci (mód n) , por lo tanto

c1 c2 · · · cφ(n) ≡ r1 r2 · · · rφ(n) ≡ aφ(n) c1 c2 · · · cφ(n) (mód n) ,

1
Algunas propiedades de esta función se estudian en el capı́tulo de funciones artiméticas.
Por lo tanto,
aφ(n) ≡ 1 (mód n) .

Observación 3.55. Observe que si p es primo, entonces φ(p) = p − 1, de modo que si

mcd(a, p) = 1 se obtiene ap−1 ≡ 1 (mód p), esto es, el Pequeño Teorema de Fermat, es
un caso particular del teorema de Euler.

Teorema 3.56. Si mcd(a, n) = 1, entonces la única solución módulo n, de la con-

gruencia
ax ≡ b (mód n) ,

es
x ≡ aφ(n)−1 b (mód n) .

Demostración. Del Teorema de Euler, se tiene que

aφ(n) ≡ 1 (mód n) ,

luego
aφ(n) b ≡ b (mód n) ,

de modo que
ax ≡ aφ(n) b (mód n) .

Finalmente, como mcd(a, n) = 1, se concluye que

x ≡ aφ(n)−1 b (mód n) .
 Ejercicios 3.5

1. Pruebe el Pequeño Teorema de Fermat, usando el método de inducción ma-

temática.

2. Si p y q son primos distintos tales que ap ≡ a (mód q) , y aq ≡ a (mód p) ,

entonces apq ≡ a (mód pq) .

3. Pruebe que a21 ≡ a (mód 15) , para todo a ∈ Z.

4. Muestre que si mcd(a, 35) = 1, entonces a12 ≡ 1 (mód 35) .

5. Muestre que si a y b son enteros tales que mcd(a, b) = 1, entonces

φ(ab) = φ(a)φ(b).

6. Pruebe que si p es un primo impar y p ∤ a, entonces

p−1
a 2 ≡ ±1 (mód p) .

7. Determine el residuo que deja 15! cuando se divide entre 17.

Capı́tulo 4

Funciones Aritméticas

4.1. Funciones Multiplicativas

Una función aritmética es una función cuyo dominio de definición es el conjunto de los
enteros positivos.

Definición 4.1 (Función multiplicativa). Una función aritmética f se dice que es

multiplicativa, si
f (mn) = f (m)f (n),

para cualesquiera enteros positivos m y n, con mcd(m, n) = 1.

Ejemplo 4.2. Las funciones aritméticas f (n) = 1 y h(n) = n son multiplicativas.

Observación 4.3. Note que si f es una función multiplicativa y n = pα1 1 pα2 2 · · · pαk k ,
donde los pi son primos diferentes y los αi enteros positivos, entonces

k
Y
f (n) = f (pα1 1 ) f (pα2 2 ) · · · f (pαk k ) = f (pαi i ) .
i=1

84
Proposición 4.4. Si f es una función multiplicativa, entonces la función g definida
para cada n ∈ Z+ por X
g(n) = f (d),
d|n

también es multiplicativa.

Demostración. Sean m, n enteros positivos tales que mcd(m, n) = 1. Note que si d es

un divisor de mn, entonces d = kt, donde k|m, t|n y mcd(k, t) = 1. De modo que,
X X
g(mn) = f (d) = f (kt),
d|mn k|m
t|n

pero como f es multiplicativa, entonces

  
X X X
g(mn) = f (k)f (t) =  f (k)  f (t) = g(m)g(n).
k|m k|m t|n
t|n
4.2. Funciones tau τ, sigma σ y phi φ
Definición 4.5. Dado un entero positivo n se define

la función τ (n) como el número de divisores positivos n.

la función σ(n) como la suma de todos los divisores positivos de n.

la función φ(n) como el número de enteros positivos menores o iguales que n que
son primos relativos con n.

Ejemplo 4.6.

τ (1) = σ(1) = φ(1) = 1.

τ (6) = 4, pues D6 = {1, 2, 3, 6} .

σ(6) = 1 + 2 + 3 + 6 = 12.

φ(6) = 2, ya que de los números 1, 2, 3, 4, 5 y 6 solamente 1 y 5 son primos

relativos con 6.

Un número p es primo si y solo si se da una de (y por lo tanto todas) las siguientes

igualdades:

τ (p) = 2,
σ(p) = p + 1,
φ(p) = p − 1.
Lema 4.7. Si p es primo y n es un entero positivo, entonces

τ (pn ) = n + 1,
n pn+1 − 1
σ (p ) = ,
p−1
 
n n n−1 n 1
φ (p ) = p − p =p 1− .
p

Demostración. Note que los divisores de pn son: 1, p, p2, p3 , . . . , pn , luego

 
τ (pn ) =  1, p, p2 , p3 , . . . , pn  = n + 1.

Además,
pn+1 − 1
σ (pn ) = 1 + p + p2 + p3 + · · · + pn = .
p−1
Por otra parte, note que desde 1 hasta pn hay exactamente pn enteros, pero de estos,
pn
los que no son primos relativos con pn son los múltiplos de p y de estos hay = pn−1
p
(entre 1 y pn ) por lo tanto,
φ (pn ) = pn − pn−1 .
Observación 4.8. Para cada entero positivo n se tiene que
X X
τ (n) = 1, σ(n) = d,
d|n d|n

Proposición 4.9. Las funciones τ, σ y φ son multiplicativas y si n = pα1 1 pα2 2 · · · pαk k es

la factorización prima de n > 1, entonces

k
Y
τ (n) = (α1 + 1)(α2 + 1) · · · (αk + 1) = (αi + 1),
i=1
     k  αi +1 
pα1 1 +1 − 1 pα2 2 +1 − 1 pαk k +1 − 1 Y p −1
i
σ(n) = ··· = ,
p1 − 1 p2 − 1 pk − 1 pi − 1
i=1
k  



Y 1
φ(n) = pα1 1 − pα1 1 −1 pα2 2 − pα2 2 −1 · · · pαk k αk −1
− pk =n 1− ,
i=1
pi

Demostración. Que las funciones τ y σ son multiplicativas se sigue de la Proposición

4.4 y la Observación 4.8. Veamos que la función φ es multiplicativa. En efecto, sean m
y n enteros primos relativos, consideremos el siguiente arreglo:

1 m + 1 2m + 1 3m + 1 · · · (n − 2)m + 1 (n − 1)m + 1
2 m + 2 2m + 2 3m + 2 · · · (n − 2)m + 2 (n − 1)m + 2
3 m + 3 2m + 3 3m + 3 · · · (n − 2)m + 3 (n − 1)m + 3
.. .. .. .. .. .. ..
. . . . . . .
m 2m 3m 4m ··· (n − 1)m nm
Consideremos la r−ésima fila, con 1 ≤ r ≤ m :
r m+r 2m + r 3m + r · · · (n − 2)m + r (n − 1)m + r
Note que si mcd(m, r) = d entonces mcd(km+r, m) = mcd(m, r) = d, con 0 ≤ k ≤ n−1
esto es, si d = 1, entonces todos los elementos de la fila son primos relativos con m
y si d 6= 1 entonces ninguno es primo relativo con m. De ahı́ que en el arreglo hay
exactamente φ(m) filas tal que todos sus elementos son primos relativos con m y en
las demás filas no hay enteros primos relativos con m.

Ahora veamos que en cada una de las φ(m) filas hay exactamente φ(n) enteros primos
relativos con n. Sea
r m+r 2m + r 3m + r · · · (n − 2)m + r (n − 1)m + r
una de las φ(m) filas, veamos que todos sus elementos son incongruentes dos a dos
módulo n de hecho, si km + r ≡ lm + r (mód n) , entonces km ≡ lm (mód n) y como
mcd(m, n) = 1 entonces k ≡ l (mód n) y por tanto n es divisor de k − l, lo cual es
imposible pues k − l < n. de lo anterior tenemos que la fila es congruente módulo n al
conjunto {1, 2, 3, . . . , n − 1, n} en algún orden, de ahı́ que cada una de las φ(m) filas
contiene φ(n) números primos relativos con n.
Por todo lo anterior, y teniendo en cuenta que mcd(a, mn) = 1 si y solo si mcd(a, m) = 1
y mcd(a, n) = 1, concluimos que φ(mn) = φ(m)φ(n).

Ejemplo 4.10. Calcular τ (n), σ(n) y φ(n) para n = 8, 12, 360, 2021
Definición 4.11 (Número perfecto). Decimos que un entero positivo n es perfecto, si
la suma de sus divisores positivos menores que n coincide con n, es decir si σ(n)−n = n
o equivalentemente
σ(n) = 2n.

Ejemplo 4.12. El primer número perfecto es el 6 pues 6 = 1 + 2 + 3, el segundo es

28 = 1 + 2 + 4 + 7 + 14, los siguientes son: 496, 8126, . . .

Teorema 4.13. Un número par n es perfecto, si y solo si

n = 2m−1 (2m − 1) ,

donde 2m − 1 es primo.

Demostración. contenidos...

Recuerde que los números primos de la forma 2m − 1 se llaman número primos de

Mersenne, a la fecha se han encontrado 51 de estos primos, por lo que a la fecha se
conocen 51 números perfectos pares.
Algunas preguntas, aun sin solución, sobre los números perfectos son las siguientes:

¿Existen infinitos números perfectos?

¿Existen números perfectos impares?

4.3. Función parte entera
Definición 4.14 (Función parte entera). Dado un número real x, la parte entera de
x, denotada con [x], es el mayor entero menor o igual que x; es decir, [x] es el único
entero tal que
[x] ≤ x ≤ [x] + 1.

Aunque la función parte entera [.] : R −→ Z no es una función aritmética, veremos que
tiene relaciones interesantes con algunas de ellas.

Ejemplo 4.15. Note que

[3,6] = [3,1] = [3,9] = [π] = [3] = 3

[−0,6] = [−0,8] = −1.

Proposición 4.16 (Propiedades de la función parte entera). Sean x, y números reales

y n un entero. Se verifican las siguientes propiedades:

(a) x − 1 < [x] ≤ x.

(b) si n ≤ x, entonces n ≤ [x].

(c) si n > x, entonces n ≥ [x] + 1.

(d) si x ≤ y, entonces [x] ≤ [y].

(e) 0 ≤ x − [x] < 1.

(f ) si x = n + y con 0 ≤ y < 1, entonces [x] = n.

(g) [x + n] = [x] + n,

(h) [x] + [y] ≤ [x + y] ≤ [x] + [y] + 1

(
0 si x ∈ Z
(i) [x] + [−x] =
1 si x 6∈ Z
hai
(j) si a = bq + r con 0 ≤ r < b entonces = q.
b
hxi  
+ [x]
(k) si n ∈ Z , entonces = .
n n
¿Cuántas veces aparece un primo p como factor de n!?

Teorema 4.17. Si n es un entero positivo y p un primo, entonces el exponente mayor

e tal que pe |n! es
∞  
X n
e=
i=1
pi

Demostración. Ejercicio para el lector

Observación 4.18 (Fórmula de Legendre). Para cada entero n ≥ 2 se tiene que

∞
Y P∞
n! = p k=1 [n/pk ]
p:primo

Ejemplo 4.19. Encontrar el número de ceros en los que termina la representación

decimal de 2021!.
Ejemplo 4.20. Sean a1 , a2 , . . . , ar enteros positivos tales que a1 + a2 + · · · + ar = n,
n!

entonces es un entero. En particular nk es un entero.
a1 !a2 ! · · · ar !
Ejemplo 4.21. Si r es un entero positivo, el producto de r enteros consecutivos es
divisible por r!
Teorema 4.22. Sean f y g una funciones aritméticas tales que
X
g(n) = f (d).
d|n

Entonces, para cualquier entero positivo N, se verifica que

N N  
X X N
g(n) = f (k)
n=1
k
k=1

Corolario 4.23. Para cada entero N > 1, se tiene que

N N   N N  
X X N X X N
τ (n) = , σ(n) = k .
n=1 k=1
k n=1 k=1
k

100
X
Ejemplo 4.24. Calcular τ (1) + τ (2) + τ (3) + · · · + τ (10) y σ(n)
n=1
4.4. Función de Möbius
Definición 4.25. Para un entero positivo n, se define µ(n) por:

 1
 si n = 1.
µ(n) = 0 si p2 |n, para algún primo p.


(−1)r si n = p1 p2 · · · pr , donde los pi son primos distintos.

Los enteros positivos n para los cuales µ(n) 6= 0 se demoninan, enteros libres de cua-
drados.

Ejemplo 4.26.

µ(2) = −1.


Si p es primo µ(p) = −1 y µ pk = 0 si k ≥ 2.

µ(6) = 1, pues 6 = 2 · 3.

µ(8) = 0, pues 22 |8.

µ(30) = −1, pues 30 = 2 · 3 · 5.

Teorema 4.27. La función µ : Z+ −→ {−1, 0, 1} es multiplicativa.
Teorema 4.28. Para cada entero positivo n se tiene que
(
X 1 si n = 1.
µ(d) =
d|n
0 si n > 1,
Teorema 4.29 (Fómula de inversión de Möbius). Sean g y f dos funciones multipli-
cativas tales que X
g(n) = f (d),
d|n

entonces
X X
f (n) = µ(d)g(n/d) = µ(n/d)g(d).
d|n d|n
Corolario 4.30. Para cada entero n > 1, se tiene que
X X
1= µ(n/d)τ (d), n= µ(n/d)σ(d).
d|n d|n
Ejemplo 4.31. Encuentre el menor entero positivo n tal que τ (n) = 21.
Ejemplo 4.32. Encuentre una fórmula para el producto de los divisores positivos de
un número, en términos de la función τ.
Ejemplo 4.33. Para cada entero positivo n, encuentre una fórmula para la suma de
todos los enteros positivos menores o iguales que n que son primos relativos con n.
 Ejercicios Cap 4.

1. (ORM-UIS) Se ubican k bombillos en lı́nea recta, con su respectivo interrup-

tor numerado con la posición que ocupa de izquierda a derecha. En un grupo
de k personas se le asigna a cada una de ellas un número entre 1 y k, de tal
forma que no hay dos personas con el mismo número. Ahora, se van esco-
giendo las personas de forma aleatoria y se les pide que pasen por la mesa
oprimiendo los interruptores etiquetados con los números que sean múltiplos
del número que les fue asignado. Si todos los bombillos estaban apagados
inicialmente, ¿cuáles bombillos quedaron encendidos luego de hacer pasar a
todas las personas una vez?
X
2. Sea n un entero positivo, pruebe que φ(d) = n.
d|n
X
3. Sean m y n enteros positivos. Pruebe que τ (m2 ) = τ 2 (n).
m|n

4. Demuestre que si existe un número perfecto impar, este no puede ser de la

forma pα q β , con p y q primos.

5. ¿Cuántos puntos de coordenadas enteras están en el primer cuadrante, sin

incluir los ejes, y, bajo o sobre la hipérbola xy = n.
Capı́tulo 5

Residuos Cuadráticos

5.1. Congruencias cuadráticas con módulo primo

En esta sección estudiaremos la solución de congruencias cuadráticas con módulo p
primo, es decir, congruencias de la forma

ax2 + bx + c ≡ 0 (mód p) , con mcd(a, p) = 1. (5.1)

Si p = 2, las soluciones de esta congruencia pueden encontrarse por simple inspección,

por lo que en adelante consideraremos que p es un primo impar.
Ahora, dado que mcd(4a, p) = 1, la ecuación (5.1) puede escribirse como

4a2 x2 + 4abx + 4ac ≡ 0 (mód p) , (5.2)

o equivalentemente,

(2ax + b)2 ≡ b2 − 4ac (mód p) , (5.3)

De ahı́ que, tomando X = 2ax + b y d = b2 − 4ac, se obtiene:

X 2 ≡ d (mód p) . (5.4)

Observación 5.1. Note que:

1. Si (5.4) no tiene solución, entonces (5.1) tampoco tiene solución.

2. Si u es solución de (5.4), esto es

u2 ≡ d (mód p) ,

105
 entonces el entero x0 que es solución de

2ax + b ≡ u (mód p)

es solución de la congruencia (5.1)

3. Recı́procamente, si x0 es solución de (5.1), entonces

2ax0 + b ≡ u (mód p) ,

donde u es solución de la congruencia (5.4).

4. Por lo anterior, existe una correspondencia biyectiva entre las soluciones de (5.1)
y (5.4) por lo que nuestro estudio se limitará a congruencias de la forma (5.4).

Teorema 5.2 (Teorema de Lagrange). Si p es un número primo y P (x) = a0 + a1 x +

· · · + an xn es un polinomio de grado n ≥ 1 con coeficientes enteros y an 6≡ 0 (mód p) ,
entonces la congruencia polinómica P (x) ≡ 0 (mód p) tiene a lo más n soluciones
incongruentes módulo p.

Por el Teorema de Langrange, la congruencia

x2 ≡ a (mód p) . (5.5)

tiene a lo más dos soluciones módulo p y además, si x0 es una solución, entonces la

otra solución es p − x0 ya que

(p − x0 )2 ≡ x20 (mód p) .
Ejemplo 5.3. Resolver la congruencia

5x2 − 6x + 2 ≡ 0 (mód 13) .

Definición 5.4 (Residuo Cuadrático). Sea p un primo impar y a un entero tal que
mcd(a, p) = 1. Si la congruencia x2 ≡ a (mód p) tiene solución, decimos que a es un
residuo cuadrático módulo p.

Ejemplo 5.5. Encontrar los residuos cuádraticos módulo 7.

Observación 5.6. Si mcd(a, p) = 1, entonces a2 es residuo cuadrático módulo p.
5.2. El Sı́mbolo de Legendre
Definición 5.7 (Sı́mbolo de Legendre).
  Dado un entero a y un primo impar p, el
a
sı́mbolo de Legendre, denotado por o (a|p) , está dado por:
p

0 si p|a
  


a
= 1 si a es residuo cuadrático módulo p
p 


−1 si a es no residuo cuadrático módulo p

Ejemplo 5.8. Para el primo p = 7 tenemos:

     
1 2 4
1= = = ,
7 7 7
     
3 5 6
−1 = = = .
7 7 7
 
7k
0= , con k ∈ Z.
7

Proposición 5.9. Sean a y b enteros primos relativos con un primo impar p. Entonces
 2
a
(a) = 1.
p
 
1
(b) = 1.
p
   
a b
(c) si a ≡ b (mód p) , entonces = .
p p
p−1
(d) Hay exactamente residuos cuadráticos incongruentes módulo p.
2
Demostración.
Teorema 5.10 (Criterio de Euler). Si p es un número primo impar y a es primo
relativo con p, entonces  
p−1 a
a 2 ≡ (mód p) .
p
Proposición 5.11 (El sı́mbolo de Legendre es multiplicativo). Sean a y b enteros
primos relativos con un primo impar p. Entonces
    
ab a b
= .
p p p

Demostración.
Corolario 5.12. Sea p un número primo impar y a un entero primo relativo con p. Si
a = pα1 1 pα2 2 · · · pαr r es la descomposición canónica de a, entonces
  Y r  αi
a pi
= .
p i=1
p

Demostración.
5.3. Ley de reciprocidad cuadrática
Teorema 5.13 (Lema de Gauss). Sea p un primo impar y a un entero primo relativo
con p. Sea  
p−1
S = a, 2a, 3a, . . . , a ,
2
y S ′ el conjunto formado por todos los restos positivos obtenidos al hacer la división
entera por p de los elementos de S. Si k es el número de elementos de S ′ que son
mayores que 2p , entonces  
a
= (−1)k .
p
 
30
Ejemplo 5.14. Hallar .
23
Teorema 5.15. Sea p un primo impar, a un entero primo relativo con p y
     
a 2a (p − 1)a
M= + +···+ ,
p p 2p
 
a
(a) si a es impar, entonces = (−1)M .
p
 
2 p2 −1
(b) = (−1) 8 .
p
 
17
Ejemplo 5.16. Hallar
19
  
2
Ejemplo 5.17. Hallar
19
Teorema 5.18 (Ley de reciprocidad cuadrática). Sean p y q primos impares distintos,
entonces   
p q p−1 q−1
= (−1) 2 2 ,
q p
o equivalentemente,    
p q p−1 q−1
= (−1) 2 2 .
q p
Ejemplo 5.19. Determinar si tiene solución la congruencia

x2 ≡ 60 (mód 239) .
  
3
Ejemplo 5.20. Sea p un número primo impar, determinar
p
5.4. El sı́mbolo de Jacobi
Una generalización del Sı́mbolo de Legendre.

Definición 5.21. Sea P un entero positivo impar, cuya factorización prima es

k
Y
P = pαi i .
i=1

Para cada entero a primo relativo con P , se define el Sı́mbolo de Jacobi denotado por
(a | P ) , como sigue:
k  αi
Y a
(a | P ) = ,
i=1
p i
 
a
donde es el sı́mbolo de Legendre. Además, se define (a | 1) = 1 y (a | P ) = 0 si
pi
mcd(a, P ) 6= 1.

Ejemplo 5.22. Calcular (12 | 55) y (84 | 385)

Observación 5.23. Note que el Sı́mbolo de Jacobi coincide con el Sı́mbolo de Legendre
cuando P es primo. Además, (a | P ) ∈ {−1, 0, 1} , sin embargo no es cierto que si
(a | P ) = 1, entonces a es residuo cuadrático módulo P, de hecho (5 | 9) = 1, pero la
congruencia x2 ≡ 5 (mód 9) no tiene solución.

Proposición 5.24 (Propiedades del Sı́mbolo de Jacobi). Sean P un entero positivo

impar, a y b enteros primos relativos con P. Se tiene que:

(a) Si a ≡ b (mód P ) , entonces (a | P ) = (b | P ) .

(b) (a2 | P ) = 1.

(c) (1 | P ) = 1.

(d) (a | P ) (b | P ) = (ab | P ) .
k
Y
(e) Si a = pαi i es la factorización prima de a, entonces
i=1

k
Y
(a | P ) = (pi | P )αi
i=1

P −1
(f ) (−1 | P ) = (−1) 2 .
P 2 −1
(g) (2 | P ) = (−1) 8 .
Teorema 5.25 (LRC para el Sı́mbolo de Jacobi). Sea P y Q enteros positivos impares
primos relativos, entonces
(P | Q) (Q | P ) = (−1)r ,
(P − 1)(Q − 1)
donde r = .
4
 
420
Ejemplo 5.26. Hallar
631
  
−216
Ejemplo 5.27. Hallar
839
5.5. Congruencias de grado superior
Teorema 5.28. Sea f un polinomio con coeficientes enteros, m1 , m2 , . . . , mr enteros
r
Y
primos relativos entre sı́ y m = mi . Entonces cada solución de la congruencia
i=1
f (x) ≡ 0 (mód m) es solución del sistema

f (x) ≡ 0 (mód m1 ) ,
f (x) ≡ 0 (mód m2 ) ,
..
.
f (x) ≡ 0 (mód mr ) ;

y recı́procamente. Además, si N es el número de soluciones de la congruencia f (x) ≡

0 (mód m) y Ni es el número de soluciones del congruencia f (x) ≡ 0 (mód mi ) para
cada i ∈ {1, 2, . . . , r} entonces N = N1 N2 · · · Nr .

Ejemplo 5.29. Determinar si la congruencia x2 ≡ 327 (mód 2821) tiene solución.

Ejemplo 5.30. Determinar las soluciones de la congruencia 3x2 +4x+5 ≡ 0 (mód 60) .
Ejemplo 5.31. Determinar las soluciones de la congruencia x3 + 2x − 3 ≡ 0 (mód 45) .
Ejemplo 5.32. Determinar las soluciones de la congruencia 7x4 +19x+25 ≡ 0 (mód 27) .

Problema 5.33. ¿Cómo resolver congruencias de la forma f (x) ≡ 0 (mód pα )?

Página 146 Teorı́a de Números para principiantes

5.6. Potencias módulo n y raı́ces primitivas
En esta sección estudiaremos la congruencia xm ≡ a (mód p), donde m es un entero
positivo, p es primo y a es primo relativo con p.

Definición 5.34. Sea p un primo impar, m un entero positivo y a un entero, primo

relativo con p. Si la congruencia xm ≡ a (mód p) tiene solución, decimos que a es una
potencia m−ésima módulo p.

Ejemplo 5.35. Las potencias cuartas módulo p = 7 son: 1, 2, 4.

a a4
1 1
2 2
3 4
4 4
5 2
6 1
De lo anterior, tenemos que la congruencia x4 ≡ 2 (mód 7) tiene solución, a saber
x ≡ 2, 5 (mód 7), pero la congruencia x4 ≡ 3 (mód 7) no tiene solución.

Definición 5.36. Sea n un entero positivo y a un entero primo relativo con n. El orden
de a módulo n, denotado por Ordn a se define por:

Ordn a = mı́n k ∈ Z+ : ak ≡ 1 (mód n) .

Observación 5.37. Por el teorema de Euler, aφ(n) ≡ 1 (mód n) . Ası́ por el PBO, el
Ordn a está bien definido y además, Ordn a ≤ φ(n).

Observación 5.38. En adelante, al escribir Ordn a se entiende que a y n son primos

relativos.

Observación 5.39. Si a ≡ b (mód n) entonces Ordn a = Ordn b.

Ejemplo 5.40. Para n = 10, tenemos que φ(10) = 4, luego basta calcular (módulo 10)
hasta las potencias cuartas de los números primos relativos con 10 menores o iguales
que 10.
a a2 a3 a4 Ord10 a,
1 1
3 9 7 1 4
7 9 3 1 4
9 1 2
Ejemplo 5.41. ¿Cuál es la menor potencia (positiva) de 17 cuya cifra de las unidades
es 1?
Se trata de hallar el menor k ∈ Z+ tal que 17k = 1 ≡ 1 (mód 10, ) esto es

Ord10 17 = Ord10 7 = 4.

Luego 174 es la menor potencia de 17 cuya cifra de las unidades es 1.

Teorema 5.42. Si at ≡ 1 (mód n) , entonces (Ordn a)|t.

Demostración. Sea Ordn a = k, por el Algoritmo de la División (aplicado a los enteros

k y t) existen q y r enteros tales que

t = kq + r, y 0 ≤ r < k.

Luego,

q
at = ak · ar ≡ ar ≡ 1 (mód n) .

De ahı́ que, r = 0, pues de no se ası́ se contradice la minimalidad de k = Ordn a. Por

lo tanto t = kq, esto es Ordn a divide a t.

Corolario 5.43. (Ordn a)|φ(n).

Demostración. Por el Teorema de Euler se tiene que aφ(n) ≡ 1 (mód n) . Luego, (Ordn a)|φ(n)
por el teorema anterior.

Corolario 5.44. Si Ordn a = k, entonces ai ≡ aj (mód n) si y solo si i ≡ j (mód k) .

Demostración.

(=⇒) Si i ≡ j (mód k) , entonces i = j + qk, luego

q
ai ≡ aj+qk = aj ak ≡ aj (mód n) .

(⇐=) Supongamos que ai ≡ aj (mód n) . Sin pérdida de generalidad podemos suponer

que i ≥ j y dado que mcd(a, n) = 1, multiplicando j veces por a−1 la congruencia
ai ≡ aj (mód n) , tenemos que

ai−j ≡ 1 (mód n) .

Ası́, por el Teorema 5.42 se tiene que k|(i − j), es decir i ≡ j (mód k) .
Teorema 5.45. Si Ordn a = k y m es un entero positivo, entonces

k
Ordn am = .
mcd(m, k)

Demostración. Sea d = mcd(m, k) y h = Ordn am . Dado que ak ≡ 1 (mód n) , entonces

k
md
(am ) d = ak ≡ 1 (mód n) ,

k
De donde se sigue que h  , por el Teorema 5.42.
d
m h k  m
Además, dado que (a ) ≡ 1 (mód n) , entonces k|mh, de ahı́ que  h , pero
  d d
k m k 
mcd , = 1, luego h .
d d d
k
Por lo anterior h = , como se querı́a mostrar.
d
Ejemplo 5.46. Dado que Ord10 3 = 4, se tiene que

4
Ord10 9 = Ord10 32 = = 2,
mcd(10, 4)
4
Ord10 7 = Ord10 33 = = 4.
mcd(3, 4)

Teorema 5.47. Sea p un número primo. Si existe un entero a tal que Ordp a = h,
entonces existen exactamente φ(h) enteros incongruentes módulo p, que tienen orden
h módulo p.

Demostración. ...

Ejemplo 5.48. Sabiendo que Ord17 9 = 8, determinar ¿cuántos números incongruentes

módulo 17 tienen orden 8? ¿cuáles son?

Definición 5.49. Si Ordn a = φ(n) decimos que a es una raı́z primitiva módulo n

Ejemplo 5.50. Las raı́ces primitivas módulo 10, son 3 y 7.

Ejemplo 5.51. No hay raı́ces primitivas módulo 12, pues Ord12 5, 7, 11 = 2 6= φ(12) =
4.

Teorema 5.52. Si p es primo, hay exactamente φ(p − 1) raı́ces primitivas módulo p.

Ejemplo 5.53. Hay φ(13 − 1) = 4 raı́ces primitivas módulo 13.

Ejemplo 5.54. 2 es raı́z primitiva módulo 13.

Lema 5.55. Sea p un primo impar, a un entero primo relativo con p y b una raı́z
primitiva módulo p. Entonces la congruencia xm ≡ a (mód p) tiene solución si y solo
si a ≡ bkd (mód p) , donde d = mcd(m, p − 1) y k es un entero positivo.

Ejemplo 5.56. Determinar si la congruencia x8 ≡ 3 (mód 13) tiene solución.

Teorema 5.57 (Criterio Generalizado de Euler). Sea p un primo impar, a un entero
primo relativo con p, m ∈ Z+ y d = mcd(m, p − 1). Entonces
p−1
xm ≡ a (mód p) tiene solución ⇐⇒ a d ≡ 1 (mód p) .

Además, si xm ≡ a (mód p) tiene solución, entonces tiene exactamente d soluciones

incongruentes módulo p.

Ejemplo 5.58. ¿Cuántas soluciones incongruentes módulo 13, tiene x8 ≡ 3 (mód 13)?
¿Cuáles son estas soluciones?
Ejemplo 5.59. ¿Cuántas soluciones incongruentes módulo 13, tiene x18 ≡ 15 (mód 17)?
¿Cuáles son estas soluciones?
Teorema 5.60. Sea p un primo impar, m ∈ Z+ , d = mcd(m, p − 1) y b una raı́z
primitiva módulo p. Entonces las potencias m−ésimas incongruentes módulo p son:
p−1
bd , b2d , b3d , . . . , b d d .

Ejemplo 5.61. Determinar las raı́ces octavas módulo 13.

 Ejercicios CAP 5.

1. Haga la lista de todos los residuos cuadráticos módulo p para p = 3, 5, 13, 19.
 
7
2. Halle .
19
3. Pruebe la Proposición 5.9.

4. Sea a un entero primo relativo con un primo impar p. Entonces

 
−1 p−1
= (−1) 2 .
p

5. Pruebe la Proposición 5.24.

Bibliografı́a

[1] Jimenez L., Gordillo J. & Rubiano G. Teorı́a de números para principiantes,
Universidad Nacional de Colombia, Pro-Offset Editorial Ltda., Bogotá, 2004.

135