Algebra I

Vista previa del material en texto

Universidad Nacional de San Cristobal de Huamanga
Facultad de Ingeniería de Minas, Geología y Civil
E.F.P. de Ciencias Físico Matemáticas
Álgebra I
Sigla: MA-144
Autor: Enrique Aviles Mendoza
Marzo 2021
Capítulo 1
Aritmética en Z
1.1. El Algoritmo de la División
Proposición 1.1 (El Principio del Buen Orden). Cada subconjunto no vacío
del conjunto de los enteros no negativos contiene un menor elemento.
Teorema 1.2. No existe entero entre 0 y 1.
Demostración. La prueba es indirecta. Supongamos que hay un entero c tal
que 0 ă c ă 1, entonces el conjunto C :“ tc P Z : 0 ă c ă 1u ­“ H. Por el
principio del buen orden, habrá un entero m mínimo en este conjunto; luego
0 ă m ă 1. Multiplicando esta desigualdad por el número positivo m resultará
0 ă m2 ă m. Entoncesm2 es otro entero del conjunto C, menor que el supuesto
elemento mínimo de C. Esta contradicción demuestra el teorema.
Teorema 1.3. Si a, b P Z y a ą b entonces a ě b` 1.
Demostración. Si fuese a ă b ` 1 tendríamos que b ă a ă b ` 1 de donde
resultaría 0 ă a´ b ă 1 con a´ b P Z pùñðùq
Teorema 1.4 (El algoritmo de la división). Sean a, b enteros con b ą 0.
Entonces existen enteros únicos q y r tal que
a “ bq ` r y 0 ď r ă b.
Demostración. (Existencia) Sea T :“ ta ´ bx{x P Zu y S “ T X Z`0 , donde
Z`0 “ tx P Z{x ě 0u. El conjunto S ­“ H ya que si a ě 0 entonces a P T , pues
podemos escribir a “ a´ bx para x “ 0 P Z, mientras que si a ă 0, a´ ba P T
ya que
b ą 0 ùñ b ě 1 ùñ bp´aq ě ´a ùñ a´ ba ě 0.
1
CAPÍTULO 1. ARITMÉTICA EN Z 2
Por el principio del buen orden S tiene un menor elemento, digamos r, entonces
1. r P S, y
2. r ď s para todo s P S (minimalidad de r).
Ya que r P S “ T X Z`0 se deduce que r “ a´ bq para cierto q P Z y r ě 0, o
en forma equivalente a “ bq ` r y r ě 0. Se afirma que r ă b. Supóngase que
r ě b, entonces tenemos
0 ď r ´ b “ a´ bq ´ b “ a´ bpq ` 1q
con q ` 1 P Z. Esto muestra que r ´ b P S; además, r ´ b ă b ya que b ą 0,
pero esto contradice la minimalidad de r, o sea 2. Por lo tanto, r ă b. En
consecuencia, existen q, r P Z tales que
a “ bq ` r y 0 ď r ă b.
(Unicidad) Supóngase que también existen enteros q1 y r1 tales que a “
bq1 ` r1 y 0 ď r1 ă b. Demostraremos que q “ q1 y r “ r1. En efecto, r ě r1
o r1 ě r (caso contraio tendríamos que r ă r pùñðùq). Supongamos que
r ě r1, entonces restando la ecuación a “ bq1 ` r1 de la ecuación a “ bq ` r
obtenemos
0 “ bpq ´ q1q ` r ´ r1 ðñ r ´ r1 “ bpq1 ´ qq. (1.1)
Por otra parte,
r ă b ùñ r1 ` r ă r1 ` b
0 ď r1 ùñ r ď r ` r1
de donde por transitividad tenemos r ă r1 ` b, esto es,
0 ď r ´ r1 ă b. (1.2)
Por consiguiente, de (1.1) y (1.2) se sigue que r ´ r1 “ 0, es decir, r “ r1.
Al reemplazar este resultado en (1.1) obtenemos bpq1´ qq “ 0 y de aquí q1 “ q
ya que b ­“ 0.
Corolario 1.5. Sean a y c enteros con c ­“ 0. Entonces existen enteros únicos
q y r tal que
a “ cq ` r y 0 ď r ă |c|
CAPÍTULO 1. ARITMÉTICA EN Z 3
1.2. Problemas Resueltos
Problema 1.6. Si divide 59 entre 7 en una calculadora, la respuesta se mues-
tra como 8.428571429. Al usar el algoritmo de división, vemos que cuando 59
se divide por 7, el cociente es 8 y el resto es 3. ¿Cómo puedes usar la calcu-
ladora para obtener este cociente entero y el resto?. De manera más general,
desarrolle un algoritmo para usar con su calculadora que producirá el cociente
y el resto para un dividendo y divisor positivo determinados. Asegúrese de que
su algoritmo funcione tanto para dividendos positivos como negativos.
Solución. Supongamos que el entero a “ 4327 se divide por b “ 281. Al ingresar
a{b en una calculadora produce 15.39857 ¨ ¨ ¨ . Se toma q “ v15.39857w “ 15 y
el resto es:
r “ a´ bq “ 4327´ 281 ¨ 15 “ 112.
Estos cálculos se muestran en la pantalla de la calculadora en la siguiente
figura.
Supongamos que a “ ´7432 se divide por b “ 453. Ingresando a{b a una calcu-
ladora produce ´16.40618 ¨ ¨ ¨ . En este caso el cociente es q “ v´16.40618w “
´17. Ahora, como siempre,
r “ a´ bq “ ´7432´ 453 ¨ p´17q “ 269.
Los cálculos anteriores se resumen en la pantalla de la calculadora:
CAPÍTULO 1. ARITMÉTICA EN Z 4
Obsérvese que estamos tomando q “ va{bw y r “ a ´ bq y de ello resulta que
a “ bq ` r y la desigualdad
q ď a{b ă q ` 1 ðñ bq ď a ă bpq ` 1q ðñ 0 ď a´ bq ă bðñ 0 ď r ă b
Problema 1.7. Sea a cualquier entero y sean b y c enteros positivos. Supon-
gamos que cuando a se divide por b, el cociente es q y el resto es r, de modo
que
a “ bq ` r y 0 ď r ă b.
Supongamos también que cuando q se divide por c, el cociente es k. Probar
que si a se divide por bc, entonces el cociente es igualmente k.
Solución. Cuando q se divide por c, el cociente es k, de manera que q “ ck. Así,
a “ bq`r “ bpckq`r “ pbcqk`r. Además, c ą 0 implica c ě 1, por el teorema
1.3, de donde bc ě b, de tal forma que 0 ď r ă b ď bc, esto es, 0 ď r ă bc. Por
lo tanto, a “ pbcqk ` r es la única representación con 0 ď r ă bc, por lo que el
cociente es en efecto k.
Problema 1.8. Probar que el cuadrado de cualquier entero a es de la forma
3k o de la forma 3k ` 1 para algún entero k.
Solución. Por el algoritmo de la división (en el que el divisor es b “ 3) a debe
ser de la forma 3q, 3q ` 1 o 3q ` 2, para cierto entero q. En el primer caso
tenemos
a2 “ p3qq2 ““ 9q2 “ 3p3qq “ 3k,
donde k :“ 3q. En el segundo caso se tiene
a2 “ p3q ` 1q2 “ 9q2 ` 6q ` 1 “ 3p3q2 ` 2q
looomooon
“:k
q ` 1 “ 3k ` 1
y en el último tenemos
a2 “ p3q ` 2q2 “ 9q2 ` 12q ` 4 “ 3p3q2 ` 4q ` 1
loooooomoooooon
“:k
q ` 1 “ 3k ` 1.
Problema 1.9. Sea n un entero positivo: Probar que a y c dejan el mismo
residuo cuando son divididos por n si y solo si a´ c “ nk para cierto entero k.
CAPÍTULO 1. ARITMÉTICA EN Z 5
Solución. pùñq Supongamos que los enteros a y c dejan el mismo resto al
dividirlos por n, entonces
a “ nq ` r, c “ nq1 ` r y 0 ď r ă n
Restando de la primera igualdad la segunda obtenemos a ´ c “ npq ´ q1q. Si
ponemos k :“ q ´ q1 tenemos a´ c “ nk con k P Z.
pðùq Supongamos que a ´ c “ nk para cierto k P Z. Al dividir a por n
(por el algoritmo de la división) se obtiene a “ qn` r con 0 ď r ă n. Entonces
c` nk “ nq ` r ðñ c “ npq ´ kq ` r
Si hacemos q1 :“ q ´ k tenemos c “ nq1 ` r y 0 ď r ă n. Esto indica que el
resto de dividir c por n es también r. Por lo tanto, a y c dejan el mismo resto
cuando son divididos por n.
1.3. Divisibilidad
Definición 1.10. Sean a, b enteros con b ­“ 0,
b|aðñ Dc P Z{a “ bc
El lado izquierdo se lee “b divide a a”, “b es un divisor de de a” o “b es un factor
de a”. Por otra parte, a ffl b significa que b no divide a.
Ejemplo 1.11. 1. 3|24.
2. ´6|54.
3. Si b P Zzt0u, entonces b|0.
4. Para cada a P Z, 1|a.
5. b|a si y solo si b| ´ a, esto es, a y ´a tienen los mismos divisores.
Ejemplo 1.12. Probar que si a ­“ 0 y b|a, entonces |b| ď |a|.
Solución. Como b|a tenemos a “ bc para cierto c P Z. Ya que a ­“ 0 implicamos
que c ­“ 0. Entonces |c| ą 0, luego por el teorema 1.3, |c| ě 1. Al multiplicar
esta desigualdad por |b| ą 0 resulta
|a| “ |bc| “ |b||c| ě |b|.
CAPÍTULO 1. ARITMÉTICA EN Z 6
Por el ejemplo anterior los divisores de un entero a P Zzt0u están entre ´|a|
y |a|; por ejemplo, los divisores de a “ 12 están entre ´12 y 12 y estos son:
˘1,˘2,˘3,˘4,˘6,˘12.
Si a “ 30 sus divisores están entre ´30 y 30 y son:
˘1,˘2,˘3,˘5,˘6,˘10,˘15,˘30.
Ejemplo 1.13. Un cconjunto S de enteros tiene al entero b como cota superior
si x ď b para todo x P S; el mismo b puede pertenecer o no pertenecer a S.
Demostrar que cualquier S no vacío que tiene una cota superior, tiene un
elemento máximo.
Solución. El conjunto de enteros no negativos T :“ tb´x : x P Su no es vacío,
pues S ­“ H, entonces por el principio del buen orden, T contiene un menor
elemento, es decir, hay un a P S tal que b´ a ď b´x para todo x P S. De esto
se deduce que x ď a para todo x P S y por lo tanto, a es el elemento máximo
del conjunto S.
Definición 1.14. Sean a y b enteros, no ambos cero. El máximo común divisor
de a y b es el mayor entero d que divide a y b, esto es, d es el máximo común
divisor de a y b si
piq d|a y d|b; (d esdivisor común de a y b)
piiq Si c|a y c|b, entonces c ď d. (d es el mayor entre los divisores comunes de
a y b)
El máximo común divisor de a y b usualmente se denota por pa, bq.
Observación 1.15. 1. Obsérvese que como 1 es un divisor común de a y b,
del ítem piiq de la definición anterior se desprende que 1 ď d.
2. Si a y b no son ambos 0, entonces su máximo común divisor existe y es
único. Los ejemplos 1.12 y 1.13 justifican esta afirmación.
Ejemplo 1.16. Hallemos el máximo común divisor de 12 y 30, esto es, p12, 30q.
divisores de 12 : ˘1,˘2,˘3,˘4,˘6,˘12
divisores de 30 : ˘1,˘2,˘3,˘5,˘6,˘10,˘15,˘30
divisores comunes : ˘1,˘2,˘3,˘6
elegimos el mayor de los divisores comunes: p12, 30q “ 6.
CAPÍTULO 1. ARITMÉTICA EN Z 7
Teorema 1.17. Sean a y b enteros, no ambos cero, y sea d su máximo común
divisor. Entonces existen enteros u y v tal que d “ au` bv.
Demostración. Sea S el conjunto de las combinaciones lineales enteras de a y
b, esto es,
S “ tam` bn : m,n P Zu
y sea T :“ SXZ`. El conjunto T ­“ H ya que a2`b2 P T . En efecto, a2`b2 P S
porque para m “ a y n “ b tenemos
am` bn “ aa` bb “ a2 ` b2.
Asimismo, a2 ` b2 P Z` ya que por hipótesis a ­“ 0 o b ­“ 0. Por ejemplo si
a ­“ 0 , entonces b2 ě 0 ùñ a2 ` b2 ě a2 ą 0.
Por el principio del buen orden T tiene un menor elemento, digamos d,
entonces este elemento mínimo cumple:
paq d P T , y
pbq d ď t para todo t P T (minimalidad de d).
Del ítem paq se deduce que d ą 0 y que d “ au ` bv, para ciertos enteros u y
v. Afirmamos que d “ pa, bq. En efecto, verificaremos las dos condiciones en la
definición de máximo común divisor.
piq Demostramos que d|a y d|b. Por el algoritmo de la división, hay enteros q
y r tales que
a “ dq ` r y 0 ď r ă d. (1.3)
Se afirma que r “ 0. Supongamos que r ą 0, entonces r P Z`; además,
r “ a´ dq “ a´ pau` bvqq “ a´ auq ´ bvq “ ap1´ uq
loomoon
PZ
q ` bp ´vq
loomoon
PZ
q
así, r es combinación lineal entera de a y b por lo que r P S. Por consiguiente,
r P S X Z` “ T y r ă d pùñðùq. Contradice la minimalidad de d, es decir,
pbq. En consecuencia, r “ 0. Al sustituir esto en la igualdad de (1.3) se obtiene
a “ dq con q P Z, lo que significa que d|a.
De un modo similar se prueba que d|b.
piiq Sea c P Z tal que c|a y c|b entonces a “ rc y b “ sc donde r, s P Z, de
manera que podemos escribir
d “ au` bv “ rcu` scv “ cpru` sv
loomoon
PZ
q
esto indica que c|d. Entonces por el Ejemplo 1.12 tenemos |c| ď |d| y como
d ą 0 resulta c ď |c| ď |d| “ d.
CAPÍTULO 1. ARITMÉTICA EN Z 8
Corolario 1.18. Sean a y b enteros, no ambos cero, y sea d un entero positivo.
Entonces d es el máximo común divisor de a y b si y solo si d satisface estas
condiciones
paq d|a y d|b;
pbq Si c|a y c1b, entonces c|d.
Demostración. pùñq Suponemos que d es el máximo común divisor de los
enteros a y b. Demostraremos que d satisface las condicones paq y pbq. En
efecto, como d es el máximo común divisor de a y b se cumple:
piq d|a y d|b;
piiq Si c|a y c|b, entonces c ď d.
de esta manera paq resulta de piq y resta demostrar pbq. Sea c P Z tal que c|a y
c|b, entonces existen enteros r y s tales que a “ rc y b “ sc . Por otra parte, por
el teorema 1.17, d es una combinación lineal entera de a y b, es decir, existen
enteros m y n tales que d “ am` bn. Al sustituir las ecuaciones anteriores en
esta última se obtiene
d “ am` bn “ rcm` scn “ cprm` snq.
Si hacemos t :“ rm` sn P Z, tenemos d “ ct, lo que quiere decir que c|d. Esto
prueba la parte pbq.
pðùq Suponemos que d ą 0 satisface las condiciones paq y pbq. Demostra-
remos que d es el máximo común divisor de los enteros a y b, es decir, que d
cumple las condiciones piq y piiq de la definición 1.14. Ciertamente, piq se sigue
de paq. Vamos a verificar piiq, con este fin supongamos que c P Z es tal que c|a
y c|b, entonces por pbq se tiene que c|d, y por el ejemplo 1.12 obtenemos
c ď |c| ď |d| “ d.
Se concluye por tanto que d “ pa, bq.
Definición 1.19. Sean a y b enteros, no ambos cero. Si pa, bq “ 1, diremos
que a y b son primos relativos.
Ejemplo 1.20. los enteros 10 y 21 son primos relativos, ya que p10, 21q “ 1.
En efecto,
divisores de 10 : ˘1,˘2,˘5,˘10
CAPÍTULO 1. ARITMÉTICA EN Z 9
divisores de 21 : ˘1,˘3,˘7,˘21
divisores comunes : ˘1.
El mayor de los divisores comunes es 1 “ p10, 21q.
Teorema 1.21. Si a|bc y pa, bq “ 1, entonces a|c.
Demostración. Ya que, pa, bq “ 1 por el teorema 1.17 podemos expresar el
entero 1 como una combinación lineal entera de a y b, esto es, existen enteros
m y n tal que 1 “ am ` bn. Al multiplicar esta ecuación por el entero c se
obtiene
c “ cam` cbn. (1.4)
Como por hipótesis a|bc, existe un entero r tal que bc “ ra. Si sustituimos esta
igualdad en (1.4) resulta
c “ cam` ran “ apcm` rnq.
Si escribimos t :“ cm`rn P Z, tenemos que c “ at, lo que significa que a|c.
Teorema 1.22 (El algoritmo euclidiano ). Sean a y b enteros positivos con
a ě b. Si b|a entonces pa, bq “ b. Si a ffl b entonces aplicamos el algoritmo de
la división repetidamente, hasta obtener un residuo igual a cero y esto ocurre
después de un número finito de pasos
a “ bq0 ` r0
b “ r0q1 ` r1
r0 “ r1q2 ` r2
r1 “ r2q3 ` r3
r2 “ r3q4 ` r4
¨ ¨ ¨
rt´2 “ rt´1qt ` rt
rt´1 “ rtqt`1 ` 0.
0 ď r0 ă b
0 ď r1 ă r0
0 ď r2 ă r1
0 ď r3 ă r2
0 ď r4 ă r3
¨ ¨ ¨
0 ă rt ă rt´1
Entonces rt, el último residuo diferente de cero es el máximo común divisor de
a y b.
Ejemplo 1.23. Hallar el máximo común divisor de los enteros a “ 314 y
b “ 159 y expresar como una combinación lineal entera de a y b.
CAPÍTULO 1. ARITMÉTICA EN Z 10
Solución. En primer lugar, obsérvese que b ffl a. Al aplicar repetidamente el
algoritmo de la división tenemos
314 “ 159 ¨ 1` 155 0 ď 155 ă 159 (1.5)
159 “ 155 ¨ 1` 4 0 ď 4 ă 155 (1.6)
155 “ 4 ¨ 38` 3 0 ď 3 ă 4 (1.7)
4 “ 3 ¨ 1` 1 0 ď 1 ă 3 (1.8)
3 “ 1 ¨ 3` 0
El máximo común divisor es 1, porque es el último residuo diferenre de cero.
Por lo tanto, p314, 159q “ 1. Ahora expresamos este máximo común divisor
como una combinación lineal entera de 314 y 159. Para ello vamos a usar
sustitución hacia atrás en la ecuaciones anteriores.
De la ecuación (1.8) despejamos el entero 1:
1 “ 4´ 3 ¨ 1
“ 4´ p155´ 4 ¨ 38q1, por la ecuación (1.7)
“ 4´ 155` 4 ¨ 38
“ 4p1` 38q ´ 155
“ 4 ¨ 39´ 155
“ p159´ 155 ¨ 1q39´ 155, por (1.6)
“ 159 ¨ 39´ 155 ¨ 39´ 155
“ 159 ¨ 39` 155p´40q, por (1.5)
“ 159 ¨ 39` p314´ 159qp´40q
“ 159 ¨ 39` 314p´40q ` 159 ¨ 40
“ 314p´40q ` 159 ¨ 79.
Por lo tanto, p314, 159q “ 1 “ 314p´40q ` 159 ¨ 79.
Lema 1.24. Si a, b, q, r P Z y a “ bq ` r, entonces pa, bq “ pb, rq.
Demostración. Sean d “ pa, bq y e “ pb, rq. Como d|a y d|b, d divide a cualquier
combinación lineal entera de a y b, en particular, d divide a r “ a` bp´qq. Así,
d es un divisor común de b y r, y ya que e es el mayor de los divisores comunes
de b y r tenemos
d ď e. (1.9)
De forma similar, e|b y e|r, por consiguiente, e divide la combinación lineal
entera a “ bq ` r. De esta manera, d es un divisor común de los enteros a y b
CAPÍTULO 1. ARITMÉTICA EN Z 11
y dado que d es el mayor de estos tenemos
e ď d. (1.10)
De (1.9) y (1.10) se concluye que d “ e.
1.4. Primos
Todo entero distinto de cero n excepto ˘1 tiene al menos cuatro diviso-
res distintos, a saber, 1,´1, n,´n. Los enteros que tienen solo estos cuatro
divisores juegan un papel crucial.
Definición 1.25. Se dice que un entero p es primo si p ­“ 0,˘1 y los únicos
divisores de p son ˘1 y ˘p.
Ejemplo 1.26. 1. Los enteros 2, 3,´5, 7,´11, 13 y ´17 son primos, pero 15
no lo es, porque 15 tiene divisores distintos de ˘1 y ˘15, tales como 3 y 5.
2. Debido a que un entero p tiene los mismos divisores que ´p, vemos que p
es primo si y solo si ´p es primo.
3. Si p y q son primos y p|q, entonces p “ ˘q. En efecto, si p y q son primos y
p|q, entonces p debe ser uno de los enteros 1,´1, q,´q. Pero dado que p es
primo, p ­“ ˘1. Luego p “ ˘q.
Teorema 1.27. Sea p un número entero con p ­“ 0,˘1. Entonces p es primo
si y solo si p tiene esta propiedad:
si p|bc, entonces p|b o p|c. (1.11)
Demostración. pùñq Supongamos que p es primoy que p|bc. Consideremos
el máximo común divisor de p y b. Ahora pp, bq debe ser un divisor positivo
del primo p. Por lo que las únicas posibilidades son pp, bq “ 1 y pp, bq “ ˘p
(cualquiera que sea positivo). Si pp, bq “ ˘p, entonces p|b. Si pp, bq “ 1, entonces
p|c por el teorema 1.21. En cualquier caso, p|b o p|c.
pðùq Si d|p, digamos p “ dt, para cierto entero t, entonces, por la propiedad
(1.11), p|d o p|t. Si p|d entonces al aplicar el problema 1.29 obtenemos d “ ˘p.
Similarmente, si p|t entonces, ya que sabemos que t|p, obtenemos t “ ˘p, y
por lo tanto d “ ˘1.
Corolario 1.28. Si p es primo y p|a1a2 ¨ ¨ ¨ an, entonces p divide al menos uno
de los ai.
Demostración. Usar el teorema 1.27 repetidamente.
CAPÍTULO 1. ARITMÉTICA EN Z 12
1.5. Problemas Resueltos
Problema 1.29. Probar que que si a|b y b|a entonces a “ ˘b.
Solución. Vamos a usar el siguiente resultado: si r, s P Z y rs “ 1, entonces
r “ s “ 1 o r “ s “ ´1.
Las relaciones a|b y b|a significan que b “ ra y a “ sb, para ciertos enteros
r y s. Después de sustituir la segunda ecuación en la primera se obtiene
b “ ra “ rsb.
Podemos cancelar b ­“ 0 de esta igualdad y obtener rs “ 1, y por el resultado
anterior r “ s “ 1 o r “ s “ ´1, de donde a “ b o a “ ´b.
Problema 1.30. Probar que pn, n` 1q “ 1 para cada entero n.
Solución. Usamos el corolario 1.18, es decir, vamos a demostrar que
p1q 1|n y 1|pn` 1q,
p2q Si c|n y c|pn` 1q entonces c|1.
Lo primero es obvio, así que supongamos que c|n y c|pn` 1q, entonces n “ cr
y n` 1 “ cs, donde r, s P Z. Al sustituir la primera ecuación en la segunda, se
obtiene
cr ` 1 “ csðñ 1 “ cps´ rq.
Como s´ r P Z, esto significa que c|1.
Problema 1.31. Hallar el menor entero positivo en el conjunto dado
paq t6u` 15v{u, v P Zu.
pbq t12r ` 17s{r, s P Zu.
Solución. En la demostración del teorema 1.17 vimos que tal menor entero
positivo es p6, 15q. Por el algoritmo de Euclides tenemos
15 “ 6 ¨ 2` 3, 0 ď 3 ă 6
6 “ 3 ¨ 2` 0,
luego p6, 15q “ 3. Observe que por el lema 1.24 tenemos
p15, 6q “ p6, 3q “ p3, 0q “ 3.
CAPÍTULO 1. ARITMÉTICA EN Z 13
Problema 1.32. Si pa, bq “ d, probar que pa{d, b{dq “ 1.
Solución. Como d es un divisor común de los enteros a y b, podemos escribir
a “ dr y b “ ds, (1.12)
para ciertos enteros r y s. Así pues, a{d “ r y b{d “ s y debemos probar
que pr, sq “ 1. En efecto, por el teorema 1.17, existen enteros u y v tales que
au`bv “ d. Al sustituir (1.12) en esta ecuación resulta dru`dsv “ d. Podemos
cancelar d ą 0 de esta ecuación y obtener ru` sv “ 1.
Vamos ahora a demostrar que pr, sq “ 1 por medio del corolario 1.18. Es
claro que 1 es un divisor común de r y s. Supongamos que c es divisor común
de r y s, entonces c divide cualquier combinación lineal entera de r y s; en
particular, c divide ru` sv “ 1, esto es, c|1.
Problema 1.33. Si c ą 0, probar que pca, cbq “ cpa, bq.
Solución. Pongamos d “ pa, bq y k “ pca, cbq. Demostraremos que cd|k y que
k|cd y por el problema 1.29 se concluirá que k “ cd, ya que estas cantidades son
positivas. La verificación de que cd|k es inmediata, así que, comprobemos la
otra. Como d “ pa, bq, por el teorema 1.17, existen enteros x, y con ax`by “ d.
Al multiplicar por c esta ecuación se obtiene
cax` cby “ cd. (1.13)
Ahora bien, k|ca y k|cb, luego k divide cualquier combinación lineal entera de
los enteros ca y cb, en particular, k divide la combinación (1.13) y por lo tanto,
k|cd.
Problema 1.34.paq Si a, b, u, v P Z son tales que au ` bv “ 1, probar que
pa, bq “ 1.
pbq Demostrar con un ejemplo que si au` bv “ d ą 1, entonces pa, bq puede no
ser d.
Solución.paq Supongamos que d “ pa, bq. Entonces d|a y d|b, de manera que d
divide cualquier combinación lineal entera de a y b, en particular, d divide
la combinación lineal au ` bv “ 1, esto es, d|1. Como obviamente 1|d, por
el problema 1.29 resulta d “ 1 ya que d es positivo.
pbq Hay muchos ejemplos. Por ejemplo, si a “ 2, b “ 3, u “ 3, v “ 2, entonces
pa, bq “ p2, 3q “ 1, mientras que d “ au` bv “ 2 ¨ 3` 3 ¨ 2 “ 12.
Problema 1.35. Si n P Z, cuáles son los posibles valores de
CAPÍTULO 1. ARITMÉTICA EN Z 14
paq pn, n` 2q.
pbq pn, n` 6q.
Solución. Sea d “ pn, n` 2q. Como 1 es un divisor común de n y n` 2, y d es
el mayor de los divisores comunes tenemos 1 ď d. Por otra parte, como d|n y
d|pn ` 2q, existen enteros r y s tales que n “ rd y n ` 2 “ sd. Al sustituir la
primera ecuación en la segunda obtenemos
rd` 2 “ sdðñ 2 “ dps´ rq
Ya que s´r P Z, esto significa que d|2. De aquí se obtiene que d ď |d| ď |2| “ 2.
Por lo tanto, d “ 1 o d “ 2.
Problema 1.36. Demostrar que un entero positivo es divisible por 3 si y solo
si la suma de sus dígitos es divisible por 3.
Solución. Supongamos que el número entero consta de dígitos anan´1 ¨ ¨ ¨ a1a0.
Entonces el número es igual a
n
ÿ
k“0
ak10
k “
n
ÿ
k“0
akp10
k ´ 1q `
n
ÿ
k“0
ak. (1.14)
Por ejemplo, si el número entero es 1246 “ a3a2a2a0 tenemos
1 ¨ 103 ` 2 ¨ 102 ` 4 ¨ 101 ` 6 ¨ 100 “
“ 1p103 ´ 1q ` 2p102 ´ 1q ` 4p101 ´ 1q ` 6p100 ´ 1q ` 1` 2` 4` 6.
Ahora, el primer término del lado derecho de la ecuación en (1.14), consta de
términos con factores de la forma 10k ´ 1, todos los cuales son de la forma
999 ¨ ¨ ¨ 99, que son divisibles por 3, de modo que el primer término siempre es
divisible por 3. Así
řn
k“0 ak10
k es divisible por 3 si y solo si el segundo término
del lado derecho de (1.14), esto es,
řn
k“0 ak es divisible por 3. Pero este es la
suma de los dígitos.
Problema 1.37. Si a1, a2, ..., an son enteros, no todos cero, entonces su má-
ximo común divisor es el mayor entero d tal que d|ai para cada i, es decir,
d “ máxtk P Z : k|ai para todo i “ 1, 2, ..., nu,
en forma equivalente
p1q d|ai para cada i “ 1, 2, ..., n.
CAPÍTULO 1. ARITMÉTICA EN Z 15
p2q Si c|ai para cada i “ 1, 2, ..., n, entonces c ď d.
Probar que existen enteros ui tal que d “ a1u1 ` a2u2 ` ¨ ¨ ¨ ` anun
Solución. Sea S “ ta1x1` a2x2` ¨ ¨ ¨ ` anxn{x1, x2, ..., xn P Zu y T “ SXZ`.
El conjunto T no es vacío. En efecto, si ai ­“ 0, entonces a2i ą 0 y pertenece a
T , ya que para xj “ 0 para j ­“ i y xi “ ai tenemos
a10` a20` ¨ ¨ ¨ ` ai´10` aiai ` ai`10` ¨ ¨ ¨ ` an0 “ a
2
i
Por el principio del buen orden este conjunto T contiene un menor elemento,
que llamamos t. Supongamos que t “ a1u1 ` a2u2 ` ¨ ¨ ¨ ` anun para ciertos
enteros ui. Se afirma que t “ d. El primer paso es demostrar que t|a1. Por el
algoritmo de la división existen enteros q y r tal que a1 “ tq` r con 0 ď r ă t.
Entonces
r “ a1 ´ tq “ a1 ´ pa1u1 ` a2u2 ` ¨ ¨ ¨ ` anunqq
“ a1p1´ u1qq ` a2p´u2qq ` ¨ ¨ ¨ ` anp´unqq
es un elemento del conjunto S. Si r ą 0 tendríamos que r P T y r ă t pùñðùq
contradice la minimalidad de t. Ya que r ě 0 la única posibilidad es r “ 0. por
lo tanto, t|a1. De un modo similar se prueba que t divide a a2, ..., an, y t es un
divisor común de a1, a2, ..., an. Entonces t ď d por p2q.
Por otra parte, d divide a cada ai, así d divide cada combinación lineal
entera de a1, a2, ..., an. En particular, d|t. Ya que t ą 0 por el ejemplo 1.12
tenemos d “ |d| ď |t| “ t y por lo tanto d “ t.
Problema 1.38. El mínimo común múltiplo de los enteros distintos de cero
a1, a2, ..., ak es el menor entero positivo m tal que ai|m para i “ 1, 2, .., k y se
denota por ra1, a2, ..., aks.
paq Hallar cada uno de los siguientes: r6, 10s, r4, 5, 6, 10s, r20, 42s, y r2, 3, 14, 36, 42s.
pbq Si t es un entero tal que ai|t para i “ 1, 2, ..., k, probar que ra1, a2, ..., aks|t.
Solución.paq Tenemos: r6, 10s “ 30
r4, 5, 6, 10s “ 60
r20, 42s “ 420, y
r2, 3, 14, 36, 42s “ 252.
pbq Denotemos m :“ ra1, a2, ..., aks. Por el algoritmo de la división, hay enteros
q y r tal que t “ mq ` r y 0 ď r ă m. Para cada i, ai|t por hipótesis
y ai|m ya que m es un múltiplo común de los ai. Así, ai divide cualquier
CAPÍTULO 1. ARITMÉTICA EN Z 16
combinación lineal entera de t y m, en particular, ai divide la combinación
t´mq “ r. De esta manera, ai|r, para cada i y r es un múltiplo común de
los ai. Por la minimalidad de m tenemos r “ 0 (si fuese r ą 0, se tendría
que 0 ă r ă m y ai|r paracada i “ 1, 2, ..., k pùñðùq), de manera que m|t.
Por lo tanto, cualquier múltiplo común de los ai es un múltiplo del mínimo
común múltiplo.
Problema 1.39. Sean a y b enteros, no ambos cero, y t un entero positivo.
Probar que t es el mínimo común múltiplo de a y b si y solo si t satisface estas
condiciones:
piq a|t y b|t;
piiq Si a|c y b|c, entonces t|c (cualquier múltiplo común de a y b es un múltiplo
de t).
Solución. piq En primer lugar, supongamos que t “ ra, bs. Entonces por la
definición de mínimo común múltiplo, t es un múltiplo de a y b, de modo que
a|t y b|t y se cumple piq. Por otra parte, si a|c y b|c, entonces c es un múltiplo
común de a y b, así que por el ítem pbq del problema 1.38, c es un múltiplo de
t, esto es, t|c y por lo tanto, también se cumple piiq.
Recíprocamente, supongamos que t satisface las condiciones piq y piiq. Por piq,
t es un múltiplo común de a y b. Sea c cualquier otro múltiplo común de a y
b, de manera que a|c y b|c. Entonces por piiq tenemos que t|c, de donde por
el ejemplo 1.12 tenemos t ď c. Se deduce de ello que t es el mínimo común
múltiplo de a y b.
Problema 1.40. Si a ą 0 y b ą 0, probar que ra, bspa, bq “ ab.
Solución. Sea d “ pa, bq, de manera que a “ da1 y b “ db1 para ciertos enteros
a1 y b1. Pongamos m :“ da1b1, y notemos que m ą 0, así como
md “ da1db1 “ ab. (1.15)
Verificaremos que m cumple las condiciones piq y piiq del problema 1.39 y
concluiremos que m “ ra, bs. En efecto,
piq m es un múltiplo común de a y b, esto es, a|m y b|m ya que
m “ da1b1 “ ab1 y m “ da1b1 “ ba1.
CAPÍTULO 1. ARITMÉTICA EN Z 17
piiq Supongamos ahora que k es un múltiplo común de a y b. Entonces k “
au “ bv para ciertos enteros u y v, de modo que k “ da1u “ db1v, que
después de cancelar d ą 0 queda como a1u “ b1v por lo que a1|b1v.
Ya que pa1, b1q “ 1, según el problema 1.32, tenemos que a1|v, digamos
v “ a1w con w P Z. Entonces
k “ bv “ db1v “ db1a1w “ mw,
esto significa que m|k.
El resultado es ahora consecuencia de (1.15).
CAPÍTULO 1. ARITMÉTICA EN Z 18
1.6. Congruencia y Clases de Congruencia
El concepto de “congruencia” puede considerarse como una generalización
de la relación de igualdad. Dos enteros a y b son iguales si su diferencia es 0 o,
de manera equivalente, si su diferencia es un múltiplo de 0. Si n es un entero
positivo, decimos que dos enteros son congruentes módulo n si su diferencia es
un múltiplo de n. Decir que a ´ b “ nk para algún entero k significa que n
divide a a´ b. De modo que tenemos esta definición formal:
Definición 1.41. Sean a, b, n enteros con n ą 0. Entonces
a ” bpmod nq ðñ n|pa´ bq
se lee “a es congruente a b módulo n”.
Ejemplo 1.42.paq 17 ” 5pmod 6q porque 6 divide a 17´ 5 “ 12.
pbq 4 ” 25pmod 7q ya que 7 divide a 4´ 25 “ ´21.
pcq 6 ” ´4pmod 5q porque 5 divide a 6´ p´4q “ 10.
pdq 6 ı ´1pmod 5q dado que 5 no divide a 6´ p´1q “ 7.
Teorema 1.43. Sea n un entero positivo. Para todo a, b, c P Z se cumple
1. Reflexiva: a ” apmod nq;
2. Simétrica: Si a ” bpmod nq, entonces b ” apmod nq;
3. Transitiva: Si a ” bpmod nq y b ” cpmod nq, entonces a ” cpmod nq.
Demostración. 1. Como a´ a “ 0 y n|0 se tiene que a ” apmod nq.
2. La relación a ” bpmod nq significa que n|pa´bq y esto a su vez que a´b “ nk
para cierto k P Z. Entonces
b´ a “ ´pa´ bq “ ´nk “ np´kq,
es decir, b´ a “ np´kq con ´k P Z por lo que n|pb´ aq.
3. Si a ” bpmod nq y b ” cpmod nq, entonces por la definición de congruencia,
hay enteros r y s tales que a´b “ nr y b´c “ ns. Sumando estas igualdades
obtenemos
a´ c “ a´ b` b´ c “ nr ` ns “ npr ` sq,
esto es, a´ c “ npr ` sq con r ` s P Z. Así, n|pa´ cq y a ” cpmod nq.
CAPÍTULO 1. ARITMÉTICA EN Z 19
Varias manipulaciones aritméticas y algebraicas esenciales dependen de este
hecho clave:
Si a “ b y c “ d, entonces a` c “ b` d y ac “ bd.
Ahora mostramos que lo mismo es cierto para la congruencia.
Teorema 1.44. Si a ” bpmod nq y c ” dpmod nq, entonces
1. a` c ” b` dpmod nq;
2. ac ” bdpmod nq.
Demostración. La hipótesis a ” bpmod nq y c ” dpmod nq significan que
a´ b “ nr y c´ d “ ns, para ciertos r, s P Z.
1. Sumando estas igualdades obtenemos
a´ b` c´ d “ nr ` nt
a` c´ pb` dq “ npr ` tq
Como r ` t P Z esto significa que n divide a a ` c ´ pb ` dq y por lo tanto
a` c ” b` dpmod nq.
2. Tenemos
ac´ bd “ ac´ ad` ad´ bd
“ apc´ dq ` pa´ bqd
“ ans` nrd
“ npas` rdq.
Ya que as ` rd P Z se deduce que n divide a ac ´ bd y por lo tanto ac ”
bdpmod nq.
Definición 1.45. Sean a, n enteros con n ą 0. La clase de congruencia de a
módulo n, que denotamos por ras, es por definición:
ras :“ tx P Z{x ” apmod nqu.
Dado que
x ” apmod nq ðñ x´ a “ nk, para algún k P Z
ðñ x “ a` nk, para algún k P Z,
CAPÍTULO 1. ARITMÉTICA EN Z 20
tenemos
ras “ tx P Z{x “ a` nk, para algún k P Zu
“ ta` kn{k P Zu
“ ta, a˘ n, a˘ 2n, a˘ 3n, ...u
Ejemplo 1.46. La clase de congruencia de a “ 2 módulo n “ 3 es:
r2s “ t2` 3k{k P Zu “ t2, 2˘ 3, 2˘ 6, ...u
“ t...,´4,´1, 2, 5, 8, ...u
Observe que en congruencia módulo 3 las clases de congruencia
r2s “ r´1s “ t...,´7,´4,´1, 2, 5, 8, ...u;
además, 2 ” ´1pmod 3q, esto da pie al siguiente teorema
Teorema 1.47. a ” cpmod nq si y solo si ras “ rcs.
Demostración. pùñq Supongamos que a ” cpmod nq. Demostraremos que
ras “ rcs por doble inclusión. En primer lugar se demuestra que ras Ď rcs.
Sea x P ras. Por definición de clase de congruencia tenemos x ” apmod nq.
Como a ” cpmod nq, por la propiedad transitiva se tiene x ” cpmod nq. Por
definición de clase de congruencia nuevamente , x P rcs.
De un modo similar se demuestra la otra inclusión.
pðùq Supongamos que ras “ rcs. Demostraremos que a ” cpmod nq. En
efecto, por la propiedad reflexiva tenemos a ” apmod nq, entonces por defi-
nición de clase de congruencia se tiene a P ras, y como ras “ rcs resulta que
a P rcs. Por definición de clase de congruencia, a ” cpmod nq.
Corolario 1.48. Dos clases de congruencia módulo n son disjuntas o idénticas.
Demostración. Sean ras y rcs dos clases de congruencia módulo n. Si rasXrcs “
H no hay nada que probar. Supongamos que ras X rcs ­“ H, entonces podemos
elegir b P ras X rcs, de manera que b P ras y b P rcs. Por definición de clase de
congruencia se tiene b ” apmod nq y b ” cpmod nq. Por simetría y transitividad
resulta a ” cpmod nq y de aquí ras “ rcs por el teorema anterior.
Corolario 1.49. Hay exactamente n clases de congruencia módulo n distintas,
a saber, r0s, r1s, ..., rn´ 1s.
Demostración. En primer término demostramos que ninguno de los enteros
0, 1, 2, ..., n ´ 1 son congruentes módulo n. Para ver esto, supongamos que
0 ď s ă n, 0 ď t ă n y que s ­“ t. Para fijar ideas digamos que s ă t. Entonces
CAPÍTULO 1. ARITMÉTICA EN Z 21
t ´ s ą 0. Además, de 0 ď s se obtiene n ď n ` s, y como t ă n resulta que
t ă n ď n` s y por transitividad t ă n` s o también t´ s ă n. Por lo tanto,
0 ă t´ s ă n.
De esto por el ejemplo 1.12 se deduce que n ffl t ´ s (caso contrario, esto es,
n|pt ´ sq, se tendría por el ejemplo mencionado que n “ |n| ď |t ´ s| “ t ´ s
pùñðùq), de donde t ı spmod nq. Ya que ninguno de los enteros 0, 1, 2, ..., n´1
son congruentes, las clases r0s, r1s, ..., rn´1s son todas distintas por el teorema
1.47.
En segundo lugar se demuestra que cada clase de congruencia es una de
estas n clases. Sea a P Z. Por el algoritmo de la división, existen enteros q y r
tales que a “ nr ` r con 0 ď r ă n. Se sigue que a ´ r “ nq, de manera que
a ” rpmod nq. Por el teorema 1.47, ras “ rrs, donde r P t0, 1, 2, ..., n´ 1u.
Definición 1.50. El conjunto de todas las clases de congruencia módulo n se
denota por Zn, es decir,
Zn “ tras : a P Zu
.
1.7. Problemas resueltos
Problema 1.51. Si p ě 5 y p es primo, probar que rps “ r1s o rps “ r5s en
Z6.
Solución. Si p ” 0, 2 o 4pmod 6q entonces p es divisible por 2. Por ejemplo,
supongamos que p ” 4pmod 6q, entonces 6|pp´ 4q, lo que significa que
p´ 4 “ 6k ðñ p “ 2p2` 3kq
para cierto k P Z. Ya que 2 ` 3k P Z resulta que 2|p. Similarmente, si p ”
3pmod 6q, entonces p es disible por 3. Ya que p es primo, estos casos no pueden
ocurrir,de manera que p ” 1 o 5pmod 6q. Por el teorema 1.47 esto implica que
rps “ r1s o r5s en Z6.
Problema 1.52.paq Probar o refutar:
si ab ” 0pmod nq, entonces a ” 0pmod nq o b ” 0pmod nq. (1.16)
pbq Hacer el inciso paq cuando n es primo.
CAPÍTULO 1. ARITMÉTICA EN Z 22
Solución.paq La afirmación es falsa. Tomemos por ejemplo a “ 3, b “ 4 y
n “ 6. Se cumple 3 ¨ 4 “ 12 ” 0pmod 6q, pero no es cierto 3 ” 0pmod 6q ni
4 ” 0pmod 6q.
pbq La afirmación (1.16) equivale a:
si n|ab, entonces n|a o n|b.
Esta afirmación es cierta cuando n es primo según el teorema 1.27.
Problema 1.53. Si pa, nq “ 1, probar que hay un entero b tal que ab ”
1pmod nq.
Solución. Como pa, nq “ 1, por el teorema 1.17, existen enteros u y v tal que
au` nv “ 1, de donde obtenemos au´ 1 “ np´vq con ´v P Z, de manera que
au ” 1pmod nq y podemos elegir b “ u.
Problema 1.54. Si ras “ r1s en Zn, probar que pa, nq “ 1. Demostrar con un
ejemplo que el recíproco puede ser falso.
Solución. Ya que ras “ r1s en Zn, por el teorema 1.47 a ” 1pmod nq, de donde
a ´ 1 “ nq, para cierto entero q, en forma equivalente, a ` nq “ 1. Por el
problema 1.34 resulta entonces que pa, nq “ 1. El recíproco es falso y para
demostrarlo tomemos, por ejemplo, a “ 5, n “ 6. Tenemos p5, 6q “ 1, sin
embargo r5s ­“ r1s.
Problema 1.55. Probar que 10n ” p´1qnpmod 11q para cada entero positivo.
Solución. Notemos en primer término que 10 ” ´1pmod 11q. Supongamos
ahora que 10n ” p´1qnpmod 11q, entonces por el teorema 1.44 tenemos
10n`1 “ 10 ¨ 10n ” p´1qp´1qn “ p´1qn`1pmod 11q.
Problema 1.56.paq Demostrar que 10n ” 1pmod 9q para cada entero positivo.
pbq Probar que cada entero positivo es congruente a la suma de sus dígitos
módulo 9.
Solución.paq Similar al del problema anterior.
CAPÍTULO 1. ARITMÉTICA EN Z 23
pbq Supongamos que en base 10 los dígitos del entero positivo a son cn, cn´1,
..., c1, c0, entonces
a “
n
ÿ
k“0
ck10
k “ cn10
k ` cn´110
n´1 ` ¨ ¨ ¨ ` c110` c010
0
Ya que 10k ” 1pmod 9q, por el teorema 1.44, tenemos ck10k ” ckpmod 9q,
y por el mismo teorema resulta
n
ÿ
k“0
ck10
k ”
n
ÿ
k“0
ckpmod 9q,
es decir, a ”
řn
k“0 ckpmod 9q.
Problema 1.57. Usar congruencias (no una calculadora) para demostrar que
p125698qp23797q ­“ 2891235306. (1.17)
Solución. Por el inciso pbq del problema 1.56 tenemos
125698 ” 31 ” 4pmod 9q
23797 ” 28 ” 1pmod 9q, y
2891235306 ” 39 ” 12 ” 3pmod 9q.
Ahora, obsérvese, por el teorema 1.44 tenemos
p125698qp23797q ” 4 ¨ 1pmod 9q.
Si fuera (1.17) una igualdad se tendría, por la propiedad simétrica y transitiva,
que 4 ¨ 1 ” 3pmod 9q; sin embargo, 4 ¨ 1 ı 3pmod 9q como puede comprobarse
con facilidad.
Problema 1.58. Probar o refutar: si ras “ rbs en Zn, entonces pa, nq “ pb, nq
Solución. Si ras “ rbs, entonces a ” bpmod nq por el teorema 1.47, de manera
que a “ nk ` b para cierto entero k. Entonces pa, nq “ pb, nq por el lema
1.24.
Problema 1.59.paq Probar o refutar: si a2 ” b2pmod nq, entonces a ” bpmod nq
o a ” ´bpmod nq.
pbq Hacer el ítem paq cuando n es primo.
CAPÍTULO 1. ARITMÉTICA EN Z 24
Solución.paq La afirmación es falsa, por ejemplo para a “ 0, b “ 2 y n “ 4
tenemos 0 ” 4pmod 4q, pero 0 ı 2pmod 4q y 0 ı ´2pmod 4q.
pbq Si a2 ” b2pmod nq, entonces n divide a a2´ b2 “ pa´ bqpa` bq. Ya que n es
primo, por el teorema 1.27, n|pa´ bq o n|pa` bq. Por lo tanto, a ” bpmod nq
o a ” ´bpmod nq.
1.8. Aritmética Modular
El conjunto finito Zn está estrechamente relacionado con el conjunto in-
finito Z. Por lo que es natural preguntarse si es posible definir la suma y la
multiplicación en Zn y hacer algún tipo de aritmética razonable allí. Usaremos
un signo más ordinario para la suma en Zn y un punto pequeño o yuxtaposición
para la multiplicación.
Definición 1.60. La adición y la multiplicació n en Zn son definidas por:
1. ras ` rcs “ ra` cs;
2. rasrcs “ racs.
Ejemplo 1.61. En Z3 “ tr0s, r1s, r2su tenemos
r0s “ t0` 3k{k P Zu “ t0,˘3,˘6, ...u “ t...,´6,´3, 0, 3, 6, ...u
r1s “ t1` 3k{k P Zu “ t1, 1˘ 3, 1˘ 6, ...u “ t...,´5,´2, 1, 4, 7, ...u
r2s “ t2` 3k{k P Zu “ t2, 2˘ 3, 2˘ 6, ...u “ t...,´4,´1, 2, 5, 8, ...u.
Hallemos la suma r1s ` r2s. Tenemos
r1s ` r2s “ r1` 2s “ r3s. (1.18)
Cada elemento de Z3 tiene muchas representaciones,
r1s “ r4s “ r7s “ r´2s “ r´5s, etc.
r2s “ r5s “ r8s “ r´1s “ r´4s, etc.
Volvemos a efectuar la operación usando ahora las representaciones en rojo,
esto es, r4s en lugar de r1s y r5s en lugar de r2s. Tenemos
r4s ` r5s “ r4` 5s “ r9s. (1.19)
Los resultados obtenidos en (1.18) y (1.19) son el mismo ya que r3s “ r9s
debido a que 3 ” 9pmod 3q.
CAPÍTULO 1. ARITMÉTICA EN Z 25
Teorema 1.62. Si ras “ rbs y rcs “ rds en Zn, entonces
ras ` rcs “ rbs ` rds y rasrcs “ rbsrds.
Demostración. De las hipótesis ras “ rbs y rcs “ rds, por el teorema 1.47,
obtenemos a ” bpmod nq y c ” dpmod nq. Por el teorema 1.44 a ` c ” b `
dpmod nq y ac ” bdpmod nq, y por el teorema 1.47 nuevamente ra`cs “ rb`ds
y racs “ rbds.
Ejemplo 1.63. En este ejemplo vamos a hallar las tablas de sumar y multi-
plicar para Z4.
` r0s r1s r2s r3s
r0s r0s r1s r2s r3s
r1s r1s r2s r3s r0s
r2s r2s r3s r0s r1s
r3s r3s r0s r1s r2s
ras ` r0s “ ra` 0s “ ras
r0s ` ras “ r0` as “ ras
r1s ` r1s “ r1` 1s “ r2s
r1s ` r2s “ r1` 2s “ r3s
r1s ` r3s “ r1` 3s “ r4s “ r0s.
Hallemos ahora la tabla de multiplicar
r0s r1s r2s r3s
r0s r0s r0s r0s r0s
r1s r0s r1s r2s r3s
r2s r0s r2s r0s r2s
r3s r0s r3s r2s r1s
rasr0s “ ra ¨ 0s “ r0s
r0sras “ r0 ¨ as “ r0s
r2sr2s “ r2 ¨ 2s “ r4s “ r0s
r2sr3s “ r2 ¨ 3s “ r6s “ r2s
r3sr3s “ r3 ¨ 3s “ r9s “ r1s.
Teorema 1.64. Para clases cualesquiera en ras, rbs, rcs en Zn se cumple:
1. Si ras P Zn y rbs P Zn, entonces ras ` rbs P Zn.
2. pras ` rbsq ` rcs “ ras ` prbs ` rcsq.
3. ras ` rbs “ rbs ` ras.
4. ras ` r0s “ ras “ r0s ` ras; la identidad aditiva es r0s.
5. Existe r´as P Zn tal que ras` r´as “ r0s “ r´as` ras; el negativo o inverso
aditivo de ras, denotado por ´ras, es r´as, es decir, ´ras “ r´as.
6. Si ras P Zn y rbs P Zn, entonces rasrbs P Zn.
7. prasrbsqrcs “ rasprbsrcsq.
8. rasprbs ` rcsq “ rasrbs ` rasrcs y pras ` rbsqrcs “ rasrcs ` rbsrcs.
9. rasr1s “ ras “ r1sras; la identidad multiplicativa es 1.
CAPÍTULO 1. ARITMÉTICA EN Z 26
Demostración. 2. pras ` rbsq ` rcs “ ra` bs ` rcs, adición en Zn
“ rpa` bq ` cs, adición en Zn
“ ra` pb` cqs, la adición en Z es asociativa
“ ras ` rb` cs, adición en Zn
“ ras ` prbs ` rcsq, adición en Zn.
Por lo tanto, pras ` rbsq ` rcs “ ras ` prbs ` rcsq.
5. Obsérvese que r´as “ rn ´ as ya que n divide a ´a ´ pn ´ aq “ ´n. Así,
rn´ as es otra representación del negativo de ras. Notemos también que
ras ` rn´ as “ ra` n´ as “ rns “ r0s.
9. rasrbs “ rabs,multiplicación enZn
“ rbas, la multiplicación en Z es conmutativa
“ rbsras,multiplicación en Zn.
Por lo tanto, rasrbs “ rbsras.
De manera similar se prueban las otras propiedades.
Adoptaremos una nueva notación que se usa ampliamente en matemáticas,
aunque tiene el defecto de que el mismo símbolo representa dos entidades
totalmente diferentes. A pesar de este hecho, no es probable que la nueva
notación cause confusión. Siempre que el contexto aclare que estamos tratando
con Zn, abreviaremos la notación de clase ras y escribiremos simplemente a.
En Z6, por ejemplo, podríamos decir 6 “ 0, lo que ciertamente es cierto para
las clases en Z6 aunque no tiene sentido si 6 y 0 son enteros ordinarios.
Ejemplo 1.65. En este ejemplo hallaremos la tabla de sumar para Z5 y los
negativos de los elementos de Z5.
Demostración.
` 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 0 0
2 2 3 0 1 1
3 3 0 1 2 2
4 4 0 1 2 3
El negativo de 0 es 0 : ´0 “ 0
El negativo de 1 es 5´ 1 “ 4 : ´1 “ 4
El negativo de 2 es 5´ 2 “ 3 : ´2 “ 3
El negativo de 3 es 5´ 3 “ 2 : ´3 “ 2
El negativo de 4 es 5´ 4 “ 1 : ´4 “ 1.
Ejemplo 1.66. Un elemento a ­“ 0 em Zn es un divisor de cero si existe un
elemento b ­“ 0 en Zn tal que ab “ 0. Hallar los divisores de cero en Z6.
CAPÍTULO 1. ARITMÉTICA EN Z 27
Demostración. En primer lugar se construye la tabla de multiplicar para Z6
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 42 0 4 2
5 0 5 4 3 2 1
Los divisores de cero son 2, 3 y 4. Por
ejemplo, 2 es un divisor de cero porque
2 ­“ 0 y hay 3 P Z6 con 3 ­“ 0 y tal que
2 ¨ 3 “ 0.
1.9. Problemas Resueltos
Problema 1.67.paq Resolver la ecuación x2 ` x “ 0 en Z5.
pbq Resolver la ecuación x2 ` x “ 0 en Z6.
pcq Si p es primo, probar que las únicas soluciones de x2 ` x “ 0 en Zp son 0 y
p´ 1.
Solución. paq Para x “ 0 : 02 ` 0 “ 0
x “ 1 : 12 ` 1 “ 3 ­“ 0
x “ 2 : 22 ` 2 “ 1 ­“ 0
x “ 3 : 32 ` 3 “ 2 ­“ 0
x “ 4 : 42 ` 4 “ 0.
Por lo tanto, las soluciones son 0 y 4.
pbq Las soluciones son x “ 0, 2, 3, 5.
pcq Tenemos rxs2 ` rxs “ r0s. Como
rxs2 ` rxs “ rxsrxs ` rxs “ rx2s ` rxs “ rx2 ` xs
la ecuación queda como rx2 ` xs “ r0s, de donde por el teorema 1.47
x2 ` x ” 0pmod pq, es decir, p divide a x2 ` x “ xpx` 1q. Entonces por
el teorema 1.27, p|x o p|px` 1q. Como x “ 0, 1, 2, ..., p´ 1 tenemos x “ 0
o x “ p´ 1.
Problema 1.68.paq En Z5 calcule pa` bq5.
CAPÍTULO 1. ARITMÉTICA EN Z 28
pbq En Z3 calcule pa` bq3.
pcq En Z2 calcule pa` bq2.
pdq Con base en los resultados de las partes paq ´ pcq, ¿a qué crees que es igual
pa` bq7 en Z7?.
Solución.paq Vamos a usar el triángulo de Pascal. Tenemos
pras ` rbsq5 “ ras5 ` 5ras4rbs ` 10ras3rbs2 ` 10ras2rbs3 ` 5rasrbs4 ` rbs5.
Debido a que
5ras4rbs “ r5a4bs “ r0s, porque 5a4b ” 0pmod 5q.
10ras3rbs2 “ r10a3b2s “ r0s
10ras2rbs3 “ r10a2b3s “ r0s
5rasrbs4 “ r10ab4s “ r0s
La ecuación se reduce a pras ` rbsq5 “ ras5 ` rbs5.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
CAPÍTULO 1. ARITMÉTICA EN Z 29
1.10. La estructura de Zp cuando p es primo
Una de las propiedades de Z es : si a, b P Z, a ­“ 0 y b ­“ 0, entonces
ab ­“ 0 (la ausencia de divisores de cero). Sin embargo, esta propiedad no es
compartida, por ejemplo, por Z6, ya que 2, 3 P Z6, 2 ­“ 0 y 3 ­“ 0, pero 2 ¨3 “ 0.
Por otra parte, en Z5 hay ausencia de divisores de cero, es decir se cumple la
propiedad: si a, b P Z5, a ­“ 0 y b ­“ 0, entonces ab ­“ 0. Para comprobarlo
basta observar la tabla de multiplicar para Z5
0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
Por ejemplo,
1 ­“ 0 y 2 ­“ 0 ùñ 1 ¨ 2 “ 2 ­“ 0
2 ­“ 0 y 3 ­“ 0 ùñ 2 ¨ 3 “ 1 ­“ 0
etc.
Pero Z5 tiene una propiedad mucho más fuerte que Z. Los únicos elementos de
Z que tienen inverso multiplicativo son ˘1. Ahora bien, la tabla de multiplicar
para Z5 demuestra que cada elemento a ­“ 0 en Z5 tiene inverso multiplicativo
o recíproco, es decir, hay un elemento en Z5, el cual se denota por a´1, tal que
aa´1 “ 1 “ a´1a.
1´1 “ 1 ya que 1 ¨ 1 “ 1.
2´1 “ 3 porque 2 ¨ 3 “ 1 “ 3 ¨ 2.
3´1 “ 2 pues 3 ¨ 2 “ 1 “ 2 ¨ 3.
4´1 “ 4 debido a que 4 ¨ 4 “ 1.
Más generalmente, si n es primo, Zn tiene propiedades especiales.
Teorema 1.69. Si p ą 0 es un entero, entonces las siguientes condiciones son
equivalentes:
p1q p es primo;
p2q Para cualquier a ­“ 0 en Zp, la ecuación ax “ 1 tiene solución en Zp.
p3q Si ab “ 0 en Zp, entonces a “ 0 o b “ 0.
Demostración. p1q ùñ p2q. (Usamos corchetes) Demostraremos que si ras ­“ r0s
en Zp, entonces la ecuación rasX “ r1s tiene solución en Zp. Supongamos que
ras ­“ r0s en Zp, entonces a ı 0pmod pq según el teorema 1.47. Por la definición
de congruencia módulo p se tiene que p ffl a. Sea d “ pa, pq, esto es, d es máximo
común divisor de a y p, entonces d|p. Como p es primo, sus únicos divisores
CAPÍTULO 1. ARITMÉTICA EN Z 30
son ˘1, ˘p, luego d P t˘1,˘pu. Ya que d ą 0, se tiene que d ­“ ´1,´p, de
manera que d P t1, pu. Dado que d es un divisor de a y p ffl a, se tiene que d ­“ p.
Por lo tanto, d “ 1. Expresemos ahora este máximo común divisor como una
combinación lineal entera de a y p, esto es, au`pv “ 1, para ciertos enteros u y
v. Entonces au´ 1 “ pp´vq, donde ´v P Z, lo que significa que au ” 1pmod pq
y por el teorema 1.47 rasrus “ raus “ r1s. Así, X “ rus es una solución de la
ecuación rasX “ r1s.
p2q ùñ p3q. (Evitamos corchetes) Supongamos que ab “ 0 en Zp. Tenemos
dos casos a “ 0 o a ­“ 0. Si a “ 0 no hay nada que probar. Si a ­“ 0, entonces
por p2q, la ecuación ax “ 1 tiene solución en Zp, es decir, hay un u P Zp tal
que au “ 1. Entonces
0 “ u0 “ upabq “ puaqb “ 1b “ b.
p3q ùñ p1q.(Usamos corchetes) Supongamos que a|p, entonces p “ ab para
cierto b P Z. Queremos demostrar que a “ ˘1 o a “ ˘p. En efecto, p “ ab
implica que ab ” 0pmod pq. Por el teorema 1.47 tenemos rasrbs “ rabs “ r0s
en Zp. Entonces por p3q, ras “ r0s o rbs “ r0s. Supongamos que ras “ r0s,
entonces a ” 0pmod pq, por definición de congruencia, p|a lo que significa que
a “ pw para cierto w P Z. Así, p “ ab “ pwb, cancelando p ą 1 obtenemos
wb “ 1, de donde se deduce que w “ b “ 1 o w “ b “ ´1. Al sustituir w “ ˘1
en la ecuación a “ pw se obtiene a “ ˘p. Mediante un argumento similar se
demuestra que de rbs “ r0s se infiere que a “ ˘1. Por lo tanto, p es primo.
Según el teorema anterior, cada ecuación en Zn de la forma ax “ 1 con
a ­“ 0 tiene solución cunado n es primo. Cuando n no es primo algunas de
estas ecuaciones pueden tener soluciones, por ejemplo, en Z6, x “ 5 es solución
de la ecuación 5x “ 1.
Corolario 1.70. Sean a y n enteros con n ą 1. Entonces pa, nq “ 1 en Z si y
solo si la ecuación ax “ 1 en Zn tiene una solución.
Demostración. pùñq Supongamos que pa, nq “ 1 en Z. Demostraremos que la
ecuación ax “ 1, con a ­“ 0, tiene solución en Zn. En efecto, como pa, nq “ 1,
podemos escribir el entero 1 como una combinación lineal entera de a y n, es
decir, existen enteros u y v tales que au ` nv “ 1. De aquí se obtiene que
au ´ 1 “ np´vq con ´v P Z, de donde au ” 1pmod nq. Esto significa que
au “ 1 en Zn, y x “ u es solución de la ecuación.
pðùq Existe u P Zn tal que au “ 1 en Zn, entonces au ” 1pmod nq en Z
por lo que au´ 1 “ nv para cierto v P Z, o lo que es lo mismo au`np´vq “ 1.
Por el problema 1.34, pa, nq “ 1.
Ejemplo 1.71. Resolver la ecuación 58x “ 1 en Z127.
CAPÍTULO 1. ARITMÉTICA EN Z 31
Demostración. Como 127 es primo, por el teorema anterior, la ecuación 58x “
1 tiene solución en Z127. A continuación hallaremos tal solución. Por el algo-
ritmo euclidiano
127 “ 58 ¨ 2` 11 0 ď 11 ă 58
58 “ 11 ¨ 5` 3 0 ď 3 ă 11
11 “ 3 ¨ 3` 2 0 ď 2 ă 3
3 “ 2 ¨ 1` 1 0 ď 1 ă 2
2 “ 1 ¨ 2` 0
Por lo tanto, p127, 58q “ 1. Ahora expresamos este máximo común divisor
como combinación lineal entera de 127 y 58 para ello usamos sustitución hacia
atrás en las ecuaciones anteriores:
1 “ 3´ 2 ¨ 1
“ 3´ p11´ 3 ¨ 3q1 “ 3´ 11` 3 ¨ 3 “ 3 ¨ 4´ 11
“ p58´ 11 ¨ 5q4´ 11 “ 58 ¨ 4´ 11 ¨ 20´ 11 “ 58 ¨ 4` 11 ¨ p´21q
“ 58 ¨ 4` p127´ 58 ¨ 2qp´21q
“ 58 ¨ 4` 127p´21q ` 58 ¨ 42
“ 58 ¨ 46` 127p´21q,
de donde resulta 58¨46´1 “ 127¨21, esto quiere decir que 58¨46 ” 1pmod 127q.
De esta manera 58¨46 “ 1 en Z127 y x “ 46 es solución de la ecuación dada.
1.11. Problemas Resueltos
Problema 1.72. Un elemento a en Zn se llama una unidad si hay un elemento
b en Zn tal que ab “ 1. En este caso, decimos que b es el inverso de a y escribimos
a´1 “ b.
paq Si a es una unidad en Zn, probar que a no es un divisor de cero.
pbq Si a es un divisor de cero en Zn, probar que a no es una unidad.
Solución. Supongamos que a es una unidad. Sea b P Zn tal que ab “ 0. Ya que
a es una unidad, existe a´1 P Zn tal que aa´1 “ 1 “ a´1a. Entonces
b “ 1b “ pa´1aqb “ a´1pabq “ a´10 “ 0.
Se ha demostrado que la ecuación ab “ 0 se cumple únicamente para b “ 0.
Por lo tanto, a no es un divisor de cero.
CAPÍTULO 1. ARITMÉTICA EN Z 32
pbq Es el contrapositivo de la parte paq.
Problema 1.73. Probar que cada elemento distinto de cero de Zn es un divisor
de cero o una unidad, pero no ambos.
Solución. Ningún elemento puede ser una unidad y un divisor de cero, por el
problema 1.72. Sea x ­“ 0 en Zn. Si x es un divisor de cero no hay nada que
probar. Supóngase que x no es un divisor de cero y consideremos el conjunto de
productos tx¨1, x¨2, ..., x¨pn´1qu, entonces 0 no pertenece a este conjunto y sus
elementos son distintos dos a dos. En efecto, si x ¨a “ x ¨b, entonces tendríamos
x ¨ pa ´ bq “ 0, de manera que x sería un divisor de cero loque contradice
nuestra suposición. Entonces tx ¨ 1, x ¨ 2, ..., x ¨ pn´ 1qu “ t1, 2, ..., n´ 1u, luego
1 P tx ¨ 1, x ¨ 2, ..., x ¨ pn´ 1qu, de manera que hay un elemento a P Zn tal que
x ¨ a “ 1. Por lo tanto, x es una unidad.
Por ejemplo, la tabla de multiplicar de Z6 es
0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1
Los elementos 2, 3 y 4 son divisores de
cero, pero 5 no lo es, entonces
t5 ¨ 1, 5 ¨ 2, 5 ¨ 3, 5 ¨ 4, 5 ¨ 5u “ t5, 4, 3, 2, 1u
y 5 ¨ 5 “ 1.
Problema 1.74. Sean a, b, n enteros con n ą 1. Sea d “ pa, nq y supongamos
que d|b. Probar que la ecuación rasx “ rbs tiene solución en Zn como sigue
paq Explicar por qué hay enteros u, v, a1, b1 n1 tal que au ` nv “ d, a “ da1,
b “ db1, n “ dn1.
pbq Demostrar que cada uno de
rub1s, rub1 ` n1s, rub1 ` 2n1s, rub1 ` 3n1s, ..., rub1 ` pd´ 1qn1s
es una solución de rasx “ rbs.
Solución.paq Ya que d divide a, b y n, hay enteros a1, b1, n1, con a “ da1,
b “ db1 y n “ dn1. Por otra parte, como d “ pa, nq, por el teorema 1.17,
existen enteros u, v tal que au` nv “ d.
pbq Vamos a probar que para cada entero t, la clase x “ rub1 ` tn1s es solución
de la ecuación rasx “ rbs. En efecto, de la ecuación au` nv “ d obtenemos
CAPÍTULO 1. ARITMÉTICA EN Z 33
au ´ d “ np´vq, de manera que au ” dpmod nq y como obviamente b1 ”
b1pmod nq, por el teorema 1.44 resulta
aub1 ” db1 “ bpmod nq. (1.20)
Por otra parte, an1t “ a1dn1t “ a1nt ” 0pmod nq, esto es,
an1t ” 0pmod nq. (1.21)
Así, de (1.20) y (1.21), por el teorema 1.44 nuevamente, implicamos que
apub1 ` tn1q ” bpmod nq, que por el teorema 1.47 podemos expresar como
rasrub1 ` tn1s “ rbs.
Problema 1.75. Sean a, b, n enteros con n ą 1. Sea d “ pa, nq y suponer que
d|b. Probar que la ecuación rasx “ rbs tiene d soluciones distintas en Zn como
sigue:
paq Demostrar que las soluciones enumeradas en el problema 1.74 son todas
distintas.
pbq Si x “ rrs es cualquier solución de rasx “ rbs, demostrar que rrs “
rub1 ` kn1s para algún entero k con 0 ď k ă d.
Demostración.paq Supongamos que rub1`sn1s “ rub1`tn1s en Zn, para ciertos
0 ď s ă t ă d. Si sumamos d a la desigualdad 0 ď s obtenemos d ď d ` s.
Dado que t ă d, por transitividad se tiene t ă d` s. Por lo tanto,
0 ă t´ s ă d. (1.22)
Por otro lado, de la igualdad anterior, por el teorema 1.47 y la definición de
congruencia módulo n, se deduce que n divide a tn1 ´ sn1 “ pt´ sqn1. Ya
que n “ dn1, resulta que d|pt´ sq, de donde, por el ejemplo 1.12, se obtiene
d ď t´ spùñðùq.
pbq Si x “ rrs es una solución, entonces rars “ rasrrs “ rbs. Asimismo, si se toma
t “ 0 en la solución general hallada en el inciso pbq del problema 1.74 se
obtiene que x “ rub1s es también solución de la ecuación por lo que raub1s “
rasrub1s “ rbs. Así pues rars “ raub1s, de donde por el teorema 1.47 y la
definición de la relación congruencia módulo n obtenemos apr ´ ub1q “ nw
para cierto entero w. Puesto que a “ da1 y n “ dn1, la ecuación anterior
puede escribirse como da1pr ´ ub1q “ dn1w. Al cancelar d ą 0 obtenemos
a1pr ´ ub1q “ n1w de ahí que n1|a1pr ´ ub1q. Dado que según el problema
CAPÍTULO 1. ARITMÉTICA EN Z 34
1.32, pa1, n1q “ 1, el teorema 1.21 implica que n1|pr´ ub1q, de esta manera
r “ ub1 ` tn1 para cierto entero t.
Por otra parte, si dividimos t por d obtenemos enteros q y k tal que t “ dq`k
y 0 ď k ă d. Entonces
x “ rrs “ rub1 ` tn1s “ rub1 ` pdq ` kqn1s “ rub1 ` kn1s ` rdn1qs
“ rub1 ` kn1s ` rnqs “ rub1 ` kn1s ` r0s “ rub1 ` kn1s.
Problema 1.76. Usar el problema 1.74 para resolver las siguientes ecuaciones.
paq 15x “ 9 en Z18.
pbq 25x “ 10 en Z65.
Solución.paq Identificando, a “ 15, b “ 9 y n “ 18. Por el algoritmo euclidiano
tenemos
18 “ 15 ¨ 1` 3 0 ď 3 ă 15
15 “ 3 ¨ 5` 0
Por lo tanto, d “ p15, 18q “ 3. Además,
b1 “ b{d “ 9{3 “ 3
n1 “ n{d “ 18{3 “ 6
3 “ d “ au` nv “ 15p´1q ` 18 ¨ 1,
de manera que u “ ´1. Las soluciones de la ecuación son ub1 ` kn1 “
p´1q3` k6, con 0 ď k ă d “ 3:
k “ 0 : p´1q3` k6 “ ´3 “ 15 en Z18
k “ 1 : p´1q3` k6 “ 3
k “ 2 : p´1q3` k6 “ 9.
Obsérvese que
3 “ 18 ¨ 0` 3
´3 “ 18 ¨ 0´ 3
´3 “ 18 ¨ 0´ 18` 18´ 3
´3 “ 18p´1q ` 15
de donde ´3 ” 15pmod 18q y ´3 “ 15 en Z18.
pbq Es similar al del ítem paq.
Capítulo 2
Relaciones
Desde la infancia, todos nos damos cuenta, implícitamente, de la necesidad
de “clasificar ” y “ordenar” las cosas, de varias maneras. Un niño, cuando juega
con una colección de objetos (bloques, fichas, etc), los agrupará frecuentemen-
te, por su color, o construirá con ellos alguna especie de pirámide, ordenándolos
de acuerdo con su tamaño. Como la clasificación y la ordenación son sucesos de
la vida diaria, los matemáticos se preguntaron si tales procesos tienen caracte-
rísticas intrínsecas que puedan abstraerse y conducir a la creación de modelos
matemáticos de los procesos. La respuesta a esa pregunta requiere, ante todo,
que la ordenación y la clasificación se describan en lenguaje matemático. Esto
nos lleva a un estudio de las “relaciones de equivalencia”, que ofrecen un mo-
delo para el proceso de clasificar, y el de las “relaciones de orden” que ofrecen
un modelo de la ordenación.
2.1. Relaciones
Definición 2.1. Sean A y B dos conjuntos. Una relación de A en B es un
subconjunto del producto cartesiano AˆB.
Observación 2.2 (Notación y Terminología). Sea R una relación de A en B.
1. Si px, yq P R se escribe xRy y se dice que x está relacionado con y.
2. Si px, yq R R se escribe x�Ry y se dice que x no está relacionado con y.
3. Si A “ B diremos que “R es una relación en A” en lugar de “R es una
relación de A en A”.
35
CAPÍTULO 2. RELACIONES 36
B
A
R
AˆB
Ejemplo 2.3. Si A “ t1, 2, 3, 4u y B “ ta, b, cu entonces R1 “ H, R2 “
tp1, aqu, R3 “ tp1, aq, p2, bq, p3, cqu y R4 “ A ˆ B son algunas relaciones de A
en B, esto pues Ri Ď AˆB para cada i “ 1, 2, 3, 4.
En realidad, el número de relaciones de A en B es:
|P pAˆBq| “ 2|AˆB| “ 2|A||B| “ 24ˆ3 “ 212.
Observación 2.4. A menudo se utiliza la siguiente sintaxis para especificar
una relación R de A en B:
xRy si y sólo si P px, yq.
Aquí P px, yq es una función proposicional de dos variables. El dominio de
variación de la variable x es el conjunto A, mientras que el de la variable y es
el conjunto B.
Ejemplo 2.5. Sean los conjuntos A “ t1, 2, 3, 4u y B “ t1, 4, 6, 8, 9u. Se define
la siguiente relación R de A en B
xRy si y sólo si x2 “ y.
La expresión de R como un subconjunto del producto cartesiano AˆB es
R “ tpx, yq P AˆB : x2 “ yu “ tp1, 1q, p2, 4q, p3, 9qu
Ejemplo 2.6. Sea A “ tx P Z : 1 ď x ď 4u. Se define la siguiente relación R
en A
aRb si y solo si a2 ´ b2 “ 3pa´ bq
Halle R en forma de lista o tabular.
CAPÍTULO 2. RELACIONES 37
Solución. En notación conjuntista tenemos
R “ tpa, bq P AˆA : a2 ´ b2 “ 3pa´ bqu
“ tpa, bq P AˆA : a “ b o a` b “ 3u
“ tp1, 1q, p1, 2q, p2, 1q, p2, 2q, p3, 3q, p4, 4qu.
La segunda igualdad se debe a las equivalencias
a2 ´ b2 “ 3pa´ bq ô a2 ´ b2 ´ 3pa´ bq “ 0
ô pa` bqpa´ bq ´ 3pa´ bq “ 0
ô pa´ bqpa` b´ 3q “ 0
ô a´ b “ 0 o a` b´ 3 “ 0
ô a “ b o a` b “ 3.
Ejemplo 2.7. Sean A “ R. Encuentre la relación R en A especificada por la
región sombreada de la siguiente figura.
3
2
0
Solución
piq La relación es:
xRy si y sólo si 0 ď x ď 3 y 0 ď y ď 2.
piiq Para x “ 3 P A tenemos x�Rx ya que 0 ď 3 ď 3 es verdadero, pero
0 ď 3 ď 2 es falso.
piiiq Para x “ 3, y “ 0 tenemos 3R0 pues 0 ď 3 ď 3 y 0 ď 0 ď 2 son
verdaderos, sin embargo, 0�R3 ya que 0 ď 0 ď 3 es verdadero, pero
0 ď 3 ď 2 es falso.
CAPÍTULO 2. RELACIONES 38
pivq Supongamos que xRy y yRz, entonces 0 ď x ď 3 y 0 ď y ď 2, así como,
0 ď y ď 3 y 0 ď z ď 2, de manera que 0 ď x ď 3 y 0 ď z ď 2 por lo que
xRz.
Ejemplo 2.8. En el conjunto de los números racionales Q se define la siguiente
relación:
aRb si y sólo si existen m,n P Z,m ‰ 0, n ‰ 0 tales que am “ bn.
Probar que
p1q a P Q implica aRa.
p2q aRb implica bRa.
p3q aRb y bRc implica aRc.
Solución. Daremos solución al item p3q, los otros son triviales. Supongamos
que aRb y bRc, esto significa que am “ bn y br “ cs para ciertos m,n, r,s P Z,
m ‰ 0, n ‰ 0, r ‰ 0, s ‰ 0. Entonces por las leyes de los exponentes
amr “ pamqr “ pbnqr “ bnr “ pbrqn “ pcsqn “ csn,
y como mr, sn P Z, mr ­“ 0 y sn ­“ 0 resulta que aRc.
2.2. Propiedades de las Relaciones
Definición 2.9. Sea A un conjunto y R una relación en A.
piq Se dice que la relación R es reflexiva si, aRa para todo a P A.
piiq Se dice que R es una relación simétrica si aRb implica bRa.
piiiq Se dice que la relación R es transitiva si aRb y bRc implica aRc.
Observación 2.10.paq Se deduce de esta definición que una relación R no es
reflexiva si hay al menos un elemento a P A tal que a�Ra.
pbq Una relación R no es simétrica si hay elementos a P A, b P A tales que aRb,
pero b�Ra.
pcq La relación R no es transitiva si hay elementos a, b y c de A tales que aRb,
bRc pero a�Rc.
Ejemplo 2.11. Determinar si las siguientes relaciones tienen algunas de las
propiedades de la definición anterior.
CAPÍTULO 2. RELACIONES 39
1. A “ Z; aRbðñ a ď b.
2. A “ R; aRbðñ |a´ b| ď 4.
3. A “ R; aRbðñ a2 ` b2 “ 1.
Solución. 1. La relación R es reflexiva pues a ď a para todo a P Z.
a ď aðñ a ă a
loomoon
F
o a “ a
loomoon
V
loooooooomoooooooon
V
.
La relación R no es simétrica porque hay elementos 1 P Z, 2 P Z tales que
1 ď 2, pero 2 ę 1.
La relación R es transitiva pues a ď b y b ď c implica a ď c.
2. La relación R es reflexiva, pues |a ´ a| “ 0 ď 4 para todo a P R, es decir,
aRa para toda a P R.
La relación R es simétrica ya que para a, b en R tenemos
aRb ùñ |a´ b| ď 4
ùñ |b´ a| ď 4
ùñ bRa.
La relación R no es transitiva pues hay números reales, a saber, ´4, 0 y 4
tales que ´4R0 y 0R4, pero ´4�R4.
´4R0
‚
0R4 ‚
´4�R4
‚
a´ b “ 4
a´ b “ ´4
R
3. La relación R no es reflexiva porque existe 1 P R tal que 1�R1.
La relación R es simétrica:
aRb ùñ a2 ` b2 “ 1
CAPÍTULO 2. RELACIONES 40
ùñ b2 ` a2 “ 1
ùñ bRa.
La relación R no es transitiva ya que la implicación
»
—
—
—
—
–
1R0
loomoon
V
y 0R1
loomoon
V
loooooooomoooooooon
V
ùñ 1R1
loomoon
F
fi
ffi
ffi
ffi
ffi
fl
pF q
es falsa.
1R0
‚
0R1
‚
1�R1‚
a2 ` b2 “ 1
R
Ejemplo 2.12. Si A es un conjunto finito y con pocos elementos y R es una
relación enA, se puede representar aR gráficamente mediante el llamado “grafo
dirigido”, su contrucción es como sigue: dibújese un pequeño círculo para cada
elemento de A y etiquétese el círculo con el elemento correspondiente de A.
Estos círculos son llamados vértices. Dibújese una flecha, llamada arista, del
vértice a al vértice b si, y sólo si, aRb. Por consiguiente, si R es una relación en
A, las aristas en el grafo dirigido de R corresponden exactamente a los pares
en R y los vértices a los elementos del conjunto A.
Sea A “ t1, 2, 3, 4u. Investigue las propiedades de la relación
R “ tp1, 1q, p2, 2q, p1, 2q, p2, 1q, p2, 3q, p3, 2q, p4, 4qu.
CAPÍTULO 2. RELACIONES 41
Demostración. El grafo dirigido de la relación R es:
4
1 2
3
Al observar el grafo dirigido de la relación vemos que ésta no es reflexiva pues
existe 3 P A tal que p3, 3q R R. Notamos también que es simétrica pero no es
transitiva ya que los elementos 1, 2, 3 P A son tales que p1, 2q P R, p2, 3q P R,
pero p1, 3q R R.
Ejemplo 2.13. En los siguientes casos determine si la relación R definida
sobre el conjunto A es reflexiva, simétrica o transitiva.
1. A “ R; aRb si y sólo si Dk P Z{a “ kb.
2. A “ Q; aRb si y sólo si a´ b ě 1.
Solución. 1. Si a P R entonces aRa, esto pues para k “ 1 P Z tenemos que
a “ ka. Esto prueba que la relación es reflexiva.
La relación no es simétrica. Para establecer esto debemos hallar una ex-
cepción a la condición de la definición 2.9 piiq, es decir, debemos hallar
elementos a, b en R tales que la implicación aRb ñ bRa sea falsa. Basta
tomar a “ 3 y b “ 1{2, pues
»
–3 R 1{2
looomooon
V
ñ 1{2 R 3
looomooon
F
fi
fl pF q.
La relación es transitiva. Demostramos que si aRb y bRc entonces aRc.
En efecto, aRb y bRc significan que existen enteros k,m tales que a “ kb
y b “ mc. Reemplazando la segunda ecuación en la primera obtenemos
a “ pkmqc con km P Z, luego aRc.
2. Ejercicio.
CAPÍTULO 2. RELACIONES 42
2.3. Relaciones de Equivalencia
En esta sección estudiaremos las relaciones de equivalencia, las cuales agru-
pan elementos que tienen características semejantes o comparten alguna pro-
piedad. Estas relaciones aparecen en todo el campo de las matemáticas y en
otros campos, aunque formalmente no se les identifique como tales.
Definición 2.14. Una relación en un conjunto A la cual es reflexiva, simétrica
y transitiva es llamada una relación de equivalencia.
Es frecuente designar a una relación de equivalencia con el símbolo “ „ ”.
Si a „ b se dice que “a es equivalente a b”.
Ejemplo 2.15. En el conjunto de los números reales R se define la siguiente
relación
a „ b si y sólo si a´ b P Z.
Probar que es una relación de equivalencia.
Solución. 1. La relación es reflexiva pues a ´ a “ 0 P Z para todo a P R, es
decir, a „ a para toda a P R.
2. La relación es simétrica pues si a y b son números reales, entonces
a „ b ùñ a´ b P Z
ùñ p´1qpa´ bq P Z
ùñ b´ a P Z
ùñ b „ a.
3. La relación es transitiva porque si a, b y c son números reales tenemos
a „ b y b „ c ùñ a´ b P Z y b´ c P Z
ùñ pa´ bq ` pb´ cq P Z
ùñ a´ c P Z
ùñ a „ c.
CAPÍTULO 2. RELACIONES 43
Por lo tanto, la relación “ „ ” es una relación de equivalencia.
n
“
0n
“
´
1
n
“
1
n
“
´
2
n
“
2
´3 ´2 ´1 1 2 3
´3
´2
´1
1
2
3
Ejemplo 2.16. En el conjunto de los números enteros Z la relación
a ” bpmod nq si y solo si n|pa´ bq,
donde n P Z`, es una relación de equivalencia.
Solución. En el teorema 1.43 del capítulo 1 fue demostrado que esta es una
relación de equivalencia.
Ejemplo 2.17. La relación “„” cuyo grafo dirigido se muestra es una relación
CAPÍTULO 2. RELACIONES 44
de equivalencia.
2
1 3 4
5 6
Asociado a una relación de equivalencia están dos conceptos muy impor-
tantes el de clase de equivalencia y el de conjunto cociente que a continuación
definimos
Definición 2.18. Sea „ una relación de equivalencia definida en un conjunto
A.
1. Si a es cualquier elemento de A, entonces el conjunto, denotado por ras (o
Ca), que consiste de todos los x P A tal que x „ a, simbólicamente,
ras “ tx P A : x „ au,
se llama la clase de equivalencia de a respecto a la relación “„”. Además, a
un elemento cualquiera x P ras se le llama un representante de clase.
2. El conjunto de todas las clases de equivalencia con respecto a “ „ ”, deno-
tado por A{ „, se llama el conjunto cociente (o factor) de A con respecto a
“ „ ”. Simbólicamente,
A{ „“ tras : a P Au.
Ejemplo 2.19. Halle las clases de equivalencia y el conjunto factor para la
relación de equivalencia del ejemplo 2.17.
Solución. Recuerde que dado x P A, x P ras ô x „ a. Teniendo en cuenta esto
debemos hallar ras para cada a P A “ t1, 2, 3, 4, 5, 6u.
CAPÍTULO 2. RELACIONES 45
1 „ 1 ùñ 1 P r1s
2 „ 1 ùñ 2 P r1s
3  1 ùñ 3 R r1s
4  1 ùñ 4 R r1s
5  1 ùñ 5 R r1s
6  1 ùñ 6 R r1s.
Por lo tanto, r1s “ t1, 2u. En forma análoga hallamos que
r2s “ r1s “ t1, 2u,
r3s “ r4s “ r5s “ t3, 4, 5u,
r6s “ t6u.
El conjunto factor es:
S{ „ “ tr1s, r3s, r6su
“ tt1, 2u, t3, 4, 5u, t6uu.
Ejemplo 2.20. Sean A, B conjuntos y f : A Ñ B una función. Sobre el
dominio A de la función se define la siguiente relación
a „ b si, y sólo si, fpaq “ fpbq.
piq Probar que “ „ ” es una relación de equivalencia en el conjunto A.
piiq Hallar r0s para fpxq “ sinpxq y fpxq “ cospxq.
Solución. piq Es reflexiva pues fpaq “ fpaq para cualquier a P A. Es simétrica
pues fpaq “ fpbq implica que fpbq “ fpaq; y es transitiva porque si
fpaq “ fpbq y fpbq “ fpcq, entonces fpaq “ fpcq.
piiq Por definición de clase de equivalencia
r0s “ tx P R : x „ 0u
“ tx P R : sinpxq “ sinp0qu
“ tx P R : sinpxq “ 0u
“ tkπ : k P Zu
r0s “ tx P R : x „ 0u
“ tx P R : cospxq “ cosp0qu
“ tx P R : cospxq “ 1u
“ tkπ : k P Zu
CAPÍTULO 2. RELACIONES 46
´2π ´ 32π
´π ´π2
π
2
π 3
2π
2π
´1
1
fpxq “ sinx fpxq “ cosx
Teorema 2.21. Sea “ „ ” una relación de equivalencia en un conjunto A y
a, belementos de A.
p1q a „ b si y sólo si ras “ rbs.
p2q Dos clases de equivalencia son disjuntas o idénticas, esto es, para cuales-
quiera a, b P A se cumple
ras X rbs “ H o ras “ rbs.
Prueba
p1q pùñq Suponemos que a „ b y demostramos que ras “ rbs por doble inclu-
sión. Sea x P ras. Según la definición de clase de equivalencia esto significa
que x „ a. Como a „ b, por la propiedad transitiva de la relación obtenemos
x „ b, de donde x P rbs. En consecuencia, ras Ď rbs.
De otra parte, sea x P rbs de manera que x „ b. De la hipótesis a „ b por la
propiedad simétrica de la relación se deduce que b „ a. Entonces apelando
ahora a la propiedad transitiva de la relación se obtiene x „ a. De acuerdo a
la definición de clase ello significa que x P ras. Esto establece que rbs Ď ras.
pðùq Suponemos que ras “ rbs y probamos que a „ b. En efecto, como
a „ a, según la propiedad reflexiva, se tiene que a P ras y dado que por
hipótesis ras “ rbs tenemos a P rbs, por lo que a „ b, según la definición de
clase de equivalencia.
CAPÍTULO 2. RELACIONES 47
p2q Si rasX rbs “ H no hay nada que demostrar. Supongamos que rasX rbs ­“ H
y sea c P ras X rbs. Entonces, de acuerdo a la definición de clase tenemos
c „ a y c „ b, de donde por simetría y transitividad obtenemos a „ b. De
esta manera por la parte p1q se concluye que ras “ rbs.
Ejemplo 2.22. Para la relación de equivalencia del ejemplo 2.15 halle las
clases de equivalencia r0s, r1{2s y ras para a P R y el conjunto cociente.
Solución. Tenemos
ras “ tx P R : x „ au
“ tx P R : x´ a P Zu
“ tx P R : x “ a` k para algún k P Zu
“ ta` k : k P Zu
“ ta, a˘ 1, a˘ 2, a˘ 3, ...u
“ t. . . , a´ 2, a´ 1, a, a` 1, a` 2, . . .u.
Si tomamos a “ 0 tenemos
r0s “ t0,˘1,˘2,˘3, ...u “ Z.
Note que también tenemos rks “ r0s para todo k P Z. Si se toma a “ 1{2 se
obtiene
„
1
2

“
"
1
2
,
1
2
˘ 1,
1
2
˘ 2,
1
2
˘ 3, ...
*
“
"
. . . ,
´5
2
,
´3
2
,
´1
2
,
1
2
,
3
2
,
5
2
,
7
2
. . .
*
.
‚ ‚ ‚ ‚ ‚
´2 ´1 0 1 2 3´3
2
´1
2
1
2
3
2
5
2
Para responder la segunda parte necesitamos del siguiente resultado: Para
cada número real a, existe un único entero k tal que k ď a ă k ` 1.
Se afirma que
R{ „“ tras : a P Ru “ trxs : 0 ď x ă 1u. (2.1)
En efecto, si a P R, entonces por el resultado antes mencionado, hay un entero
k tal que k ď a ă k ` 1, pero
k ď a ă k ` 1 ðñ 0 ď a´ k
loomoon
“x
ă 1
CAPÍTULO 2. RELACIONES 48
de manera que si ponemos x :“ a´ k tenemos
a´ x “ k P Zðñ a „ xðñ ras “ rxs,
con 0 ď x ă 1. Esto prueba la segunda igualdad en (2.1).
Además, rxs ­“ rys si 0 ď x, y ă 1 y x ­“ y. En efecto, supongamos que
rxs “ rys y que x ă y, entonces x „ y ðñ x´ y P Z. Por otra parte,
0 ď x ùñ 1 ď x` 1
y como y ă 1, obtenemos y ă x` 1. De esta manera, 0 ă y ´ x ă 1 pùñðùq,
pues no existe enteros entre 0 y 1.
Finalmente, obsérvese que
piq rxs ­“ H, para cada 0 ď x ă 1.
piiq rxs X rys “ H, para todo 0 ď x, y ă 1 y x ­“ y.
piiiq
Ť
xPr0,1qrxs “ R.
Ejemplo 2.23. Considérese en el conjunto de los números reales R la relación
x „ y si y sólo si rrxss “ rryss
piq Compruebe que “ „ ” es una relación de equivalencia.
piiq Describa las clases de equivalencia y el conjunto cociente.
Solución. piq Es un caso particular del ejemplo 2.20, basta tomar la función
máximo entero f : RÑ R definida por fpxq “ rrxss.
piiq Sea k P Z. Por la definición de clase de equivalencia tenemos
rks “ tx P R{x „ ku
“ tx P R{ rrxss “ rrkssu
“ tx P R{ rrxss “ ku
“ tx P R{k ď x ă k ` 1u
“ rk, k ` 1q
Por lo tanto, rks “ rk, k ` 1q.
CAPÍTULO 2. RELACIONES 49
Por otro lado, dado a P R, existe un único k P Z tal que k ď a ă k ` 1,
entonces rrass “ k “ rrkss por lo que, a „ k y así ras “ rks. Por lo tanto,
el conjunto factor es
R{ „“ trk, k ` 1q{k P Zu.
´2 ´1 0 1 2 3
r0s r1s r2sr´1sr´2s
Ejemplo 2.24. En el conjunto C de los números complejos se define la relación:
z „ w si y sólo si |z| “ |w|.
1. Probar que “ „ ” es una relación de equivalencia.
2. Mostrar graficamente las clases de equivalencia de
?
2
2 `
?
2
2 i, 2i y z “ a`bi.
Solución. 1. Este ejemplo es un caso particular del ejemplo 2.20, basta consi-
derar A “ C, B “ R y la función f : C Ñ R, fpzq “ |z| “
a
x2 ` y2 para
z “ x` yi P C (módulo de un número complejo)
2. Sea z0 P C y rz0s “ tz P C : z „ z0u su clase de equivalencia. Como
z “ x` yi „ z0 ðñ |x` yi| “ |z0|
ðñ
a
x2 ` y2 “ |z0|
ðñ x2 ` y2 “ |z0|
2.
tenemos rz0s “ tz P C : x2 ` y2 “ |z0|2u.
Por ejemplo, si tomamos z0 “
?
2
2 `
?
2
2 i tenemos |z0|
2 “ 1, de manera que
z “ x` yi P rz0s ô x
2 ` y2 “ 1.
Si ahora se toma z0 “ 2i se obtiene |z0|2 “ 4, entonces
z “ x` yi P rz0s ô x
2 ` y2 “ 4.
CAPÍTULO 2. RELACIONES 50
x
y
1
2
|z|
x
y
CAPÍTULO 2. RELACIONES 51
Ejemplo 2.25. Sea A “ R2 ´ tp0, 0qu.
px, yq „ pr, sq si y sólo si xs “ yr
1. Compruebe que “ „ ” es una relación de equivalencia.
2. Describa las clases rp1, 0qs, rp0, 1qs, rp1, 1qs y rp1,´1qs.
Solución. Demostramos que la relación es de equivalencia.
Reflexividad. Si px, yq P A entonces px, yq „ px, yq.
En efecto, debido a la propiedad conmutativa de la multiplicación de números
se tiene xy “ yx, pero esto significa que px, yq „ px, yq.
Simetría. Si px, yq „ pr, sq entonces pr, sq „ px, yq.
En efecto, px, yq „ pr, sq significa que xs “ yr. Por la propiedad simétrica de
la relación de igualdad y la conmutatividad de la multiplicación en R podemos
escribir ry “ sx, pero entonces pr, sq „ px, yq.
Transitividad. Si px, yq „ pr, sq y pr, sq „ pp, qq entonces px, yq „ pp, qq.
De las relaciones px, yq „ pr, sq y pr, sq „ pp, qq obtenemos las igualdades
xs “ yr y rq “ sp. (2.2)
Por otro lado, como pr, sq P A “ R2 ´ tp0, 0qu se tiene que pr, sq ‰ p0, 0q, luego
r ‰ 0 ó s ‰ 0. Supongamos que r ‰ 0. Multiplicando la segunda igualdad en
(2.2) por x obtenemos xprqq “ xpspq, que por la conmutatividad y la asociati-
vidad de la multiplicación de números puede ser escrita como pxqqr “ pxsqp.
Reemplazando ahora la primera igualdad en (2.2) en el lado derecho de esta úl-
tima igualdad se obtiene pxqqr “ pyrqp. Nuevamente la propiedad conmutativa
y asociativa de la multiplicación de números nos permite escribir pxqqr “ pypqr.
Podemos cancelar r ‰ 0 en la ecuación anterior y obtener xq “ yp, de donde
px, yq „ pp, qq.
Finalmente, de acuerdo con la definición de clase de equivalencia tenemos
rp0, 1qs “ tpx, yq P A{px, yq „ p0, 1qu
“ tpx, yq P A{x “ 0qu
rp1, 0qs “ tpx, yq P A{px, yq „ p1, 0qu
“ tpx, yq P A{y “ 0u
rp1, 1qs “ tpx, yq P A{px, yq „ p1, 1qu
“ tpx, yq P A{x “ yqu
rp1,´1qs “ tpx, yq P A{px, yq „ p1,´1qu
“ tpx, yq P A{ ´ x “ yqu
CAPÍTULO 2. RELACIONES 52
x
y
rp1, 1qsrp1,´1qs
rp0, 1qs
rp1, 0qs
x
y
CAPÍTULO 2. RELACIONES 53
Definición 2.26. Se dice que una familia pAiqiPI de subconjuntos de un con-
junto A es una partición de A si se cumplen las siguientes condiciones:
piq Ai ‰ H para cada i P I;
piiq Aj XAi “ H o Ai “ Aj para cualesquiera i, j P I;
piiiq
Ť
iPI Ai :“ tx P A{ Di P I : x P Aiu “ A
Teorema 2.27. Sea “ „” una relación de equivalencia en un conjunto A. La
familia prasqaPA es una partición del conjunto A.
Prueba. Demostraremos que
1. ras ‰ H para cada a P A;
2. ras X rbs “ H o ras “ rbs para cualesquiera a, b P A;
3.
Ť
aPAras “ A.
En efecto,
1. ras ­“ H pues contiene al elemento a.
2. Se sigue del Teorema 2.21.
3. Es obvio.
Teorema 2.28. Toda partición de un conjunto determina una relación de
equivalencia definida en él.
Demostración. Sea A un conjunto no vacío y pAiqiPI una partición del conjunto
A. Considérese en el conjunto A la relación:
a „ b si y sólo si Di P I{a P Ai y b P Ai.
Demostraremos que “ „” es una relación de equivalencia. Las propiedades
reflexiva y simétrica son de fácil verificación. Veamos la propiedad transitiva.
Supongamos que a „ b y b „ c, entonces existen i, j P I tales que a, b P Ai y
b, c P Aj . Como b P Ai X Aj , tenemos que Ai X Aj ‰ H. Dado que pAiqiPI es
una partición debe ser que Ai “ Aj . Por consiguiente, hay un índice i P I tal
que a, c P Ai, luego a „ c.
CAPÍTULO 2. RELACIONES 54
Ejemplo2.29. Sean A “ ta, b, c, d, eu y C “ tta, b, cu, td, euu Ď P pAq una
partición del conjunto A. Como se sabe la relación
x „ y ðñ DC P C {x, y P C
es una relación de equivalencia. Hallar los pares ordenados que forman tal
relación.
Solución. Los pares ordenados que conforman la relación son:
ta, b, cu ˆ ta, b, cu Y td, eu ˆ td, eu.
El grafo dirigido de esta relación es:
d
e a b
c
2.4. Problemas Resueltos
Problema 2.30. En el conjunto de los números reales R definimos la siguiente
relación:
aRbðñ ab ě 0.
piq Investigar las propiedades de R.
piiq Graficar.
Solución. La relación R es reflexiva pues a2 ě 0 para todo a P R, esto es, aRa
para todo a P R. Asimismno, la relación es simétrica debido a la conmutativi-
dad de la multiplicación usual:
aRb ùñ ab ě 0 ùñ ba ě 0 ùñ bRa.
CAPÍTULO 2. RELACIONES 55
La relación no es transitiva ya que, por ejemplo, ´2R0 y 0R2 pero ´2�R2.
´2 ´1 1 2
´2
´1
1
2
‚
´2R0
‚
´2�R2
‚
0R2
R
Problema 2.31.
En el conjunto de los números reales R defínase la relación
x „ y ðñ x2 “ y2.
piq Demostrar que es una relación de equivalencia.
piiq Hallar las clases de equivalencia y el conjunto cociente.
piiiq Graficar la relación.
Solución. piq Es un caso particular del ejemplo 2.20, en este caso la función es
f : RÑ R, fpxq “ x2.
piiq Observemos en primer lugar que
x2 “ y2 ðñ x2 ´ y2 “ 0
ðñ px´ yqpx` yq “ 0
ðñ x “ y o x “ ´y.
(2.3)
En consecuencia,
ras “ tx P R : x „ au
CAPÍTULO 2. RELACIONES 56
“ tx P R : x2 “ a2u
“ tx P R : x “ ˘au
“ t´a, au.
Por lo tanto, el conjunto cociente es
R{ „“ tras : a P Ru “ tt´a, au : a P Ru.
piiiq En vista de (2.3) podemos escribir
tpx, yq P R2{x2 “ y2u “ tpx, yq P R2{x “ yu Y tpx, yq P R2{x “ ´yu
y dado que la relación es un subconjunto de R2 podemos representarla
gráficamente en el plano
a
a
´a
´a
R
Problema 2.32.
Sea A “ Z` ˆ Z` y la relación definida en A como sigue
pa, bq „ pc, dq si, y sólo si, ad “ bc
1. Demostrar que „ es una relación de equivalencia.
2. Hallar rp1, 1qs y rp2, 1qs.
Solución. La relación es reflexiva porque ab “ ba para todo pa, bq P A. La
relación es simétrica pues si pa, bq y pc, dq son pares de enteros positivos tenemos
pa, bq „ pc, dq ùñ ad “ bc
CAPÍTULO 2. RELACIONES 57
ùñ bc “ ad
ùñ cb “ da
ùñ pc, dq „ pa, bq.
Para comprobar la propiedad transitiva consideremos pa, bq, pc, dq y pe, fq en
A tales que pa, bq „ pc, dq y pc, dq „ pe, fq, entonces ad “ bc y cf “ de. Al
multliplicar la segunda ecuación por el entero a y sustituir la primera ecuación
en el resultado obtenemos
caf “ acf “ ade “ bce “ cbe,
podemos cancelar c ­“ 0 y obtener af “ be, lo significa que pa, bq „ pe, fq. Por
lo tanto, „ es una relación de equivalencia.
Para la segunda parte tenemos,
rp1, 1qs “ tpx, yq P A{px, yq „ p1, 1qu
“ tpx, yq P A{x “ yu
“ tp1, 1q, p2, 2q, p3, 3q, p4, 4q, . . .u.
Asimismo,
rp2, 1qs “ tpx, yq P A{px, yq „ p2, 1qu
“ tpx, yq P A{x “ 2yu
“ tp2, 1q, p4, 2q, p6, 3q, p8, 4q, . . .u.
1 2 3 4 5 6 7 8
1
2
3
4
‚
‚
‚
‚
‚
‚
‚
‚
rp1, 1qs rp2, 1qs
Problema 2.33.
CAPÍTULO 2. RELACIONES 58
En el conjunto de los números reales distintos de cero R˚ “ Rzt0u se define la
relación:
a „ b si y sólo si ab ą 0.
paq Probar que “ „ ” es una relación de equivalencia en R˚.
pbq Describir las clases de equivalencia y el conjunto cociente.
Solución.paq Reflexiva. a „ a para toda a P R˚.
En efecto, si a P R˚, entonces a ‰ 0 de manera que a2 “ aa ą 0, esto quiere
decir que a „ a.
Simétrica. Si a „ b entonces b „ a.
En efecto, si a „ b entonces ab ą 0. Puesto que la multiplicación usual es
conmutativa esta desigualdad la podemos escribir como ba ą 0, de donde
b „ a.
Transitiva: Si a „ b y b „ c entonces a „ c.
En efecto, si a „ b y b „ c entonces ab ą 0 y bc ą 0. Multiplicando estas
desigualdades se obtiene pabqpbcq “ b2ac ą 0 “ 0b2. Como b2 ą 0 deducimos
que ac ą 0 y por lo tanto a „ c.
pbq Si x P R˚, entonces x ­“ 0. Por la ley de tricotomía x ą 0 o x ă 0. En el
primer caso x1 “ x ą 0, de manera que x „ 1 y por lo tanto rxs “ r1s. En
el segundo caso, xp´1q “ ´x ą 0, por lo que x „ ´1, así que rxs “ r´1s.
Así, basta hallar las siguientes clases de equivalencia
r1s “ tx P R˚ : x „ 1u
“ tx P R˚ : x “ x1 ą 0u
“ p0,`8q
r´1s “ tx P R˚ : x „ ´1u
“ tx P R˚ : ´x “ xp´1q ą 0u
“ tx P R˚ : x ă 0u
“ p´8, 0q.
Por lo tanto, el conjunto cociente es
R˚{ „“ tr1s, r´1su “ tp0,`8q, p´8, 0qu.
Capítulo 3
Operaciones Binarias
3.1. Definición y Ejemplos
Definición 3.1. Una operación binaria “˚” en un conjunto no vacío A es una
regla que asigna a cada par ordenado pa, bq de elementos de A, exactamente un
elemento a ˚ b en A. Más precisamente, una operación binaria en un conjunto
A es una función
˚ : AˆA ÝÑ A
pa, bq ÞÝÑ a ˚ b
Observación 3.2. Hay tres aspectos de esta definición que deben destacarse
1. a ˚ b está definido para cada par ordenado pa, bq de elementos de A.
2. a ˚ b debe estar definido de forma única.
3. Si a y b están en A, entonces a ˚ b debe estar en A.
Ejemplo 3.3. 1. a ˚ b “ a{b, a, b P R. Esta regla no es una operación binaria
pues 3˚0 “ 3{0 no está definida; así, no se cumple el ítem 1 de la observación
anterior.
2. a ˚ b “ c si c2 “ ab, a, b P R. Esta manera de combinar los elementos
de R tampoco es una operación binaria ya que 2 ˚ 8 “ 4 o ´ 4 porque
42 “ p´4q2 “ 2 ¨ 8. Por lo tanto, no se cumple el inciso 2 de la observación
3.2.
3. a ˚ b “ a{b, a, b P Z. No es una operación binaria porque 3 ˚ 4 “ 3{4 R Z; así,
no se cumple el ítem 3 de la observación 3.2.
59
CAPÍTULO 3. OPERACIONES BINARIAS 60
4. a ˚ b “ a{b, a, b P R` “ tx P R : x ą 0u. Esta regla si es una operacuión
binaria en R` porque
* a ˚ b está definida para todo a, b P R`,
* a ˚ b es único para todo a, b P R`, y
* a ˚ b P R` para todo a, b P R`.
Ejemplo 3.4. Si a es un número entero y n es un número entero positivo,
definimos a mod n como el resto cuando a se divide por n, por ejemplo,
p1q 7 mod 3 “ 1
p2q ´10 mod 4 “ 2
p3q 35 mod 7 “ 0.
paq Probar las siguientes propiedades:
piq a mod n “ pa` knqmod n para cualquier entero k.
piiq pa mod n` bqmod n “ pa` bq mod n
piiiq pa` bqmod n “ pa mod n` b mod nqmod n.
pivq pa´ bqmod n “ pa mod n´ b mod nqmod n.
pvq pa ¨ bqmod n “ pa mod n ¨ b mod nqmod n.
pviq pakqmod n “ pa mod nqkmod n.
pviiq a ” bpmod nq ðñ a mod n “ b mod n.
pbq Determine si la siguiente regla es una operación binaria en Z
‘ : Zˆ Z ÝÑ Z
pa, bq ÞÝÑ a‘ b :“ pa` bqmod n
Solución.paq piiq Por el algoritmo de la división hay enteros q y r tales que
a “ nq ` r y 0 ď r ă n,
entonces
a mod n “ r “ a´ nq ùñ a mod n` b “ a` b´ nq,
por lo que
pa mod n` bqmod n “ pa` b´ nqqmod n “ pa` bqmod n
CAPÍTULO 3. OPERACIONES BINARIAS 61
piiiq Por el algoritmo de la división, teorema 1.4, hay enteros q, r y q1, r1
tales que:
a “ nq ` r, 0 ď r ă n
b “ nq1 ` r1, 0 ď r1 ă n
(3.1)
al sumar las igualdades resulta a` b “ npq ` q1q ` r ` r1. Entonces por piq
tenemos
pa` bqmod n “ pnpq ` q1q ` r ` r1qmod n “ pr ` r1qmod n (3.2)
Por otra parte, de (3.1) tenemos
pa mod n` b mod nqmod n “ pr ` r1qmod n (3.3)
al comparar (3.2) y (3.3) obtenemos el resultado requerido, esto es,
pa` bqmod n “ pa mod n` b mod nqmod n.
pvq Por el algoritmo de la división, teorema 1.4, hay enteros q, r y q1, r1 tales
que:
a “ nq ` r, 0 ď r ă n
b “ nq1 ` r1, 0 ď r1 ă n
(3.4)
al multiplicar las igualdades resulta
a ¨ b “ pnq ` rqpnq1 ` r1q “ npnqq1 ` qr1 ` rq1q ` rr1.
Entonces por piq tenemos
pa ¨ bqmod n “ pnpnqq1 ` qr1 ` rq1q ` rr1qmod n “ pr ¨ r1qmod n (3.5)
De otro lado, de (3.4) tenemos
pa mod n ¨ b mod nqmod n “ pr ¨ r1qmod n (3.6)
al comparar (3.5) y (3.6) obtenemos el resultado requerido, el cual es
pa ¨ bqmod n “ pa mod n ¨ b mod nqmod n.
pviiq Es consecuencia del problema 1.9.
pbq Si es.
CAPÍTULO 3. OPERACIONES BINARIAS 62
Definición 3.5. Se dice que una operación binaria “˚” definida en un conjunto
A es conmutativa, si a ˚ b “ b ˚ a para todo a, b P A.
Se deduce de la definición precedente que una operación “˚” en un conjunto
A no es conmutativa si hay por lo menos un par