Álgebra Abstrata - Versão 1.0 - Josimar da Silva Rocha

Prévia do material em texto

UNIVERSIDADE ESTADUAL DE GOIA´S
UNIDADE UNIVERSITA´RIA DE FORMOSA
DEPARTAMENTO DE MATEMA´TICA
A´LGEBRA ABSTRATA
(Versa˜o 1.0)
Josimar da Silva Rocha
FORMOSA
GOIA´S - BRASIL
2010
Suma´rio
1 Relac¸o˜es e Aplicac¸o˜es 1
1.1 Produto Cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Relac¸o˜es entre Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.1 Representac¸a˜o Gra´fica de uma relac¸a˜o de A em B . . . . . . 3
1.3 Aplicac¸o˜es ou Func¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.1 Tipos de aplicac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Relac¸o˜es de um conjunto A em si pro´prio (ou relac¸o˜es sobre A) . . . 5
1.5 Relac¸a˜o de Equivaleˆncia . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 Relac¸o˜es de Ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6.1 Composic¸a˜o de Relac¸o˜es . . . . . . . . . . . . . . . . . . . . . 12
2 Operac¸o˜es ou Lei de Composic¸a˜o Interna 14
2.0.2 Ta´bua de operac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . 19
2.0.3 A ta´bua de uma operac¸a˜o ∗ sobre um conjunto A (enumera´vel,
ou finito) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.0.4 Propriedades da operac¸a˜o a partir da ta´bua de operac¸o˜es . . . 20
3 Nu´meros Inteiros 35
3.1 Congrueˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.1.1 Propriedades das Congrueˆncias . . . . . . . . . . . . . . . . . 49
4 Grupos 53
4.1 Estruturas Alge´bricas . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Conjunto Gerador de um Grupo . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Exemplos de Grupos . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.2 Grupo de permutac¸o˜es . . . . . . . . . . . . . . . . . . . . . . 62
2
4.2.3 Grupo Diedral 2n : D2n . . . . . . . . . . . . . . . . . . . . . 64
4.2.4 Subgrupos Normais . . . . . . . . . . . . . . . . . . . . . . . . 65
4.2.5 Homomorfismo de Grupos . . . . . . . . . . . . . . . . . . . . 66
5 Ane´is e domı´nios de integridade 75
5.1 Ane´is de Integridade - Corpos . . . . . . . . . . . . . . . . . . . . . . 78
5.1.1 Ideais em Ane´is Comutativos . . . . . . . . . . . . . . . . . . 83
5.1.2 Caracter´ıstica de um anel . . . . . . . . . . . . . . . . . . . . 88
5.2 Ane´is de polinoˆmios sobre corpos . . . . . . . . . . . . . . . . . . . . 94
3
Cap´ıtulo 1
Relac¸o˜es e Aplicac¸o˜es
1.1 Produto Cartesiano
Definic¸a˜o 1. Sejam A e B conjuntos. Definimos o produto cartesiano de A em
B por
A×B := {(a, b) | a ∈ A e b ∈ B}.
Exemplo 1. Se A = {a, b} e B = {1, 2, 3}, enta˜o
A×B = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
Exemplo 2. Se A = [0, 1] e B = [−1, 1], enta˜o
A×B = [0, 1]× [−1, 1]
e´ o retaˆngulo representado por
Observac¸a˜o 1. Em geral, se A1, · · · , Ak sa˜o conjuntos, podemos definir o produto
cartesiano destes conjuntos como:
A1 × A2 × · · · × Ak := {(a1, a2, · · · , ak) | a1 ∈ A1, · · · , ak ∈ Ak}
1.2 Relac¸o˜es entre Conjuntos
Definic¸a˜o 2. Uma relac¸a˜o de um conjunto A em um conjunto B e´ um sub-
conjunto do produto cartesiano A×B.
1
Exemplo 3. Seja A = {−1, 1} e B = {a, b, c}, enta˜o
A×B = {(−1, 1), (−1, b), (−1, c), (1, a), (1, b), (1, c)}.
Assim,
R1 = {(−1, a)}
R2 = {(1, a), (−1, a)}
sa˜o relac¸o˜es de A em B.
Existem 26 relac¸o˜es de A em B, onde 6 e´ a quantidade de elementos do conjunto
A×B.
Definic¸a˜o 3. Seja R uma relac¸a˜o de A em B. O domı´nio da relac¸a˜o R e´ o
conjunto
DomR := {a ∈ A | ∃b ∈ B com (a, b) ∈ R}
Exemplo 4. Se A = {a, b} e B = {0, 1}, enta˜o
A×B = {(a, 0), (a, 1), (b, 0), (b, 1)}.
Assim,
(i) se R1 = {(a, 0), (a, 1)}, enta˜o DomR1 = {a};
(ii) se R2 = {(a, 0), (b, 1), (a, 1)}, enta˜o DomR2 = {a, b};
(iii) se R3 = ∅, enta˜o DomR3 = ∅.
Observac¸a˜o 2. Se R e´ uma relac¸a˜o de A em B e (a, b) ∈ R, enta˜o dizemos que
a ∈ R esta´ relacionado com b ∈ B.
Definic¸a˜o 4. Seja R uma relac¸a˜o de A em B, enta˜o a imagem de R e´ definida
como sendo o conjunto
ImR = {b ∈ B | ∃a ∈ A tal que (a, b) ∈ R}.
Exemplo 5. Se A = [−1, 1] e B = [0, 2] e R = {(a, b) ∈ A × B | b2 = a}, enta˜o
DomR = [0, 1] e ImR = [0, 1].
Exemplo 6. Se A = {1, 2, 3}, B = {3, 4} e R = {(0, 3), (1, 3)}, enta˜o DomR = {0, 1}
e ImR = {3}.
2
1.2.1 Representac¸a˜o Gra´fica de uma relac¸a˜o de A em B
Representemos, primeiramente, o conjunto A por marcac¸o˜es em uma reta horizontal
e o conjunto B por marcac¸o˜es em uma reta que corta a reta anterior perpendicu-
larmente. Os elementos de uma relac¸a˜o R de A em B sa˜o representados por pontos
neste sistema de coordenadas. Assim, se A = {0, 1, 2} e B = {−1, c}, enta˜o a relac¸a˜o
R = {(0, c), (2,−1), (0,−1)} pode ser representada graficamente por
Definic¸a˜o 5. Seja R uma relac¸a˜o de A em B. A relac¸a˜o inversa de R e´ a relac¸a˜o
de B em A definida por:
R−1 := {(b, a) ∈ B × A | (a, b) ∈ R}.
Exemplo 7. Se A = {−1, 0, 1}, B = {2, 4, 6, 8} e R = {(0, 2), (1, 4), (0, 6)}, enta˜o
R−1 = {(2, 0), (4, 1), (6, 0)}.
Observac¸a˜o 3. Se A e B sa˜o conjuntos finitos, enta˜o uma relac¸a˜o de A em B pode
tambe´m ser representada por diagramas de Venn.
Assim, se A = {a1, · · · , ak} e B = {b1, · · · , bt}, enta˜o uma seta que parte de um
elemento ai ∈ A e chega em bj ∈ B dira´ que (ai, bj) ∈ R.
Exemplo 8. Se A = {1, 2, 3} e B = {a, b, c, d}, enta˜o R = {(2, a), (2, b), (3, b)} e´
representado pelo seguinte diagrama de Venn:
1.3 Aplicac¸o˜es ou Func¸o˜es
Definic¸a˜o 6. Sejam A e B conjuntos e R uma relac¸a˜o de A em B. Dizemos que R
e´ uma aplicac¸a˜o de A em B (ou func¸a˜o de A em B ) quando cada elemento
de A esta´ relacionado com um u´nico elemento de B. Neste caso, se a ∈ A, enta˜o
representaremos por R(a) o elemento u´nico de B tal que (a,R(a)) ∈ R, ou seja,
R(a) = b se (a, b) ∈ R.
Exemplo 9. Se A = [0, 1]e B = R+, enta˜o f definida por f(x) = ex,∀x ∈ A, e´ uma
aplicac¸a˜o de A em B. Neste caso, Domf = A, Imf = [1, e] e f−1 = {(b, a) ∈ B×A |
(a, b) ∈ f} = {(ea, a) | a ∈ A} = {(b, ln b) | b ∈ Imf}, ou seja, f−1 pode ser definida
por f−1(b) = ln b, onde b ∈ Imf.
3
Observac¸a˜o 4. Se f e´ uma aplicac¸a˜o de A em B, enta˜o a relac¸a˜o inversa f−1 nem
sempre sera´ uma aplicac¸a˜o. Por exemplo, se A = {1, 2, 3} e B = {a, b}, enta˜o
f = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
e´ uma aplicac¸a˜o de A em B, mas
f−1 = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
e´ uma relac¸a˜o de B em A, mas na˜o e´ uma aplicac¸a˜o de B em A.
1.3.1 Tipos de aplicac¸o˜es
Definic¸a˜o 7. Uma aplicac¸a˜o f de A em B e´ dita ser sobrejetora se Imf = B.
Definic¸a˜o 8. Uma aplicac¸a˜o f de A em B e´ injetora se
(∀x, y ∈ A) (f(x) = f(y)⇒ x = y) ,
ou seja,
(∀x, y ∈ A) (x 6= y ⇒ f(x) 6= f(y)) ,
ou seja, dois elementos de A na˜o esta˜o relacionados com o mesmo elemento de B.
Exemplo 10. Sejam A = R+∗ e B = R, enta˜o f definida por f(x) = ln x e´ uma
aplicac¸a˜o sobrejetora e injetora de A em B. De fato, se b ∈ B, enta˜o x = eb ∈ A
satisfaz lnx = ln eb = b. Logo f e´ sobrejetora.
Para provar que f e´ injetora, se x1, x2 ∈ A, satisfazem f(x1) = f(x2), enta˜o existe
t ∈ B tal que
t = lnx1 = lnx2 ⇒ et = x1 = x2.
Logo f e´ injetora.
Definic¸a˜o 9. Uma aplicac¸a˜o f de A em B e´ bijetora quando f e´ injetora e f e´
sobrejetora.
Exemplo 11. A aplicac¸a˜o do exemplo anterior e´ uma aplicac¸a˜o bijetora.
4
a
��
��
c
��
b XX
Figura 1.1: Figura do Exemplo 12
1.4 Relac¸o˜es de um conjunto A em si pro´prio (ou
relac¸o˜es sobre A)
Definic¸a˜o 10. Uma relac¸a˜o R sobre um conjunto A e´ dita ser reflexiva se
(∀a ∈ A) ((a, a) ∈ R)
ou
(∀a ∈ A) (aRa) .
Exemplo 12. Se A = {a, b, c}, enta˜o R = {(a, a), (b, b), (c, c), (a, b)} e´ uma relac¸a˜o
reflexiva.
Observac¸a˜o 5. Se R e´ uma relac¸a˜o sobreum conjunto A e (a, b) ∈ R, enta˜o este
elemento (a, b) e´ representado graficamente por uma seta partindo do ponto a ao ponto
b, assim:
Se a = b, enta˜o (a, b) = (a, a), enta˜o este elemento R e´ representado graficamente
pelo ciclo:
Definic¸a˜o 11. Uma relac¸a˜o R sobre A e´ sime´trica se
(∀x, y ∈ A) ((x, y) ∈ R⇒ (y, x) ∈ R) ,
ou seja,
(∀x, y ∈ A) (xRy ⇒ yRx)
Exemplo 13. Se A = {1, 2, 3, 4}, enta˜o R = {(1, 1), (1, 2), (2, 1), (3, 3), (3, 1), (1, 3)}
e´ uma relac¸a˜o sime´trica. Graficamente,
Definic¸a˜o 12. Uma relac¸a˜o sobre A e´ transitiva se
(∀x, y, z ∈ A) (((x, y) ∈ R e (y, z) ∈ R)⇒ ((x, y) ∈ R)) ,
ou seja,
(∀x, y, z ∈ A) (xRy e yRz ⇒ xRz)
5
1
��
��
// 2
��
oo
3
OO
4
Figura 1.2: Figura do Exemplo 13
12
��
4
99tttttttttttttttttttttt��
6
eeJJJJJJJJJJJJJJJJJJJJJJ��
2
JJ��������������������������
__>>>>>>>>>>>>>>>>
77nnnnnnnnnnnnnnnnnnnnnnnnnnnnnn
FF 3
TT((((((((((((((((((((((((((
??����������������
FF
Figura 1.3: R(A)
Exemplo 14. Seja A = Z e R = {(a, b) ∈ Z×Z | b e´ mu´ltiplo de a}, enta˜o R e´ uma
relac¸a˜o transitiva. De fato, se (a, b) ∈ R e (b, c) ∈ R, enta˜o existem r, k ∈ Z tais que
b = ra e c = kb. Logo c = kb = k(ra) = (kr)a, com kr ∈ Z, i.e., c e´ mu´ltiplo de a.
Portanto, (a, c) ∈ R. Consequentemente, R e´ transitiva.
Exemplo 15. Seja A = {2, 4, 3, 6, 12} e R = {(a, b) ∈ A × A | b e´ mu´ltiplo de a},
enta˜o R e´ uma relac¸a˜o transitiva. Observe que R = {(2, 4), (2, 6), (3, 6), (2, 12), (4, 12), (3, 12), (6, 12), (2, 2), (4, 4), (6, 6), (12, 12), (3, 3)}.
Definic¸a˜o 13. Uma relac¸a˜o sobre um conjunto A e´ dita ser anti-sime´trica se
(∀x, y ∈ A) ((x, y) ∈ R e (y, x) ∈ R⇒ x = y) ,
i.e.,
(∀x, y ∈ A) (xRy e yRx⇒ x = y)
Exemplo 16. Se A = {a, b, c} e R = {(a, a), (a, b), (b, c), (b, b)} e´ uma relac¸a˜o anti-
sime´trica.
Observac¸a˜o 6. Graficamente:
• Uma relac¸a˜o R sobre A e´ reflexiva se existem ciclos em cada elemento de A;
• Uma relac¸a˜o R sobre A e´ sime´trica se na˜o existem setas simples ligando ele-
mentos de A;
6
• Uma relac¸a˜o R sobre A e´ transitiva se para todo caminho ligando dois pontos a
e b de A, existe uma seta ligando a e b;
• Uma relac¸a˜o R sobre A e´ anti-sime´trica se na˜o existem setas duplas ligando
elementos de A.
1.5 Relac¸a˜o de Equivaleˆncia
Definic¸a˜o 14. Uma relac¸a˜o R sobre um conjunto A e´ dita ser uma relac¸a˜o de
equivaleˆncia se R e´ uma relac¸a˜o reflexiva, sime´trica e transitiva.
Definic¸a˜o 15. Seja R uma relac¸a˜o de equivaleˆncia sobre um conjunto A. Para cada
elemento a ∈ A podemos definir um conjunto
a := {x ∈ A | xRa}
chamado de classe de equivaleˆncia do elemento a. O conjunto das classes de
equivaleˆncia de A sera´ representado por A/R.
Proposic¸a˜o 1. Seja R uma relac¸a˜o de equivaleˆncia sobre A, enta˜o
(i) Se b ∈ a, enta˜o a ∈ b.
(ii) Se a ∩ b 6= ∅, enta˜o a = b.
(iii) A =
⋃
a∈A a.
Demonstrac¸a˜o.
(i) Se b ∈ a, enta˜o bRa. Como R e´ uma relac¸a˜o sime´trica e bRc, enta˜o aRb. Como
aRb enta˜o a ∈ b.
(ii) Se a∩ b 6= ∅ enta˜o existe x ∈ a∩ b. Assim x ∈ a e x ∈ b. Seja y ∈ a, enta˜o yRa
e como x ∈ ae x ∈ b, temos que yRa, xRa e xRb. Como R e´ sime´trica, temos
que yRa, aRx e xRb. Como R e´ transitiva, temos que yRa, aRb ⇒ yRb. Logo
y ∈ b. Portanto a ⊂ b.
Outra forma:
7
(∃x ∈ a ∩ b) (∀y ∈ a) (yRa, xRa, xRb)
Re´ sime´trica ⇒ (∃x ∈ a ∩ b) (∀y ∈ a) (yRa, aRx, xRb)
R e´ transitiva ⇒ (∀y ∈ a) (yRa, aRb)
R e´ transitiva ⇒ (∀y ∈ a) (y ∈ b)
⇒ (a ⊂ b)
Da mesma forma, podemos mostrar que b ⊂ a. Logo a = b.
(iii) (∀a ∈ A) (a ∈ a) ⇒ (∀b ∈ A) (b ∈ ⋃a∈A a) . Logo A = ⋃a∈A a. Assim, A ⊂⋃
b∈A b e como b ⊂ A,
⋃
b∈B b ⊂ A para todo b ∈ A, segue que b ∈ A. Logo
A =
⋃
b∈A b =
⋃
a∈A a.
Definic¸a˜o 16. Seja A um conjunto e (Bλ)λ∈I uma colec¸a˜o de subconjuntos na˜o vazios
de A para algum conjunto de ı´ndices I. Dizemos que (Bλ)λ∈I e´ uma partic¸a˜o de A
se:
(i) Bλ1 ∩Bλ2 6= ∅ se λ1 6= λ2;
(ii)
⋃
λ∈I
Bλ = A.
Exerc´ıcio 1. Seja (Bλ)λ∈I uma partic¸a˜o de um conjunto A. Definindo uma relac¸a˜o
sobre A como
(∀a, b ∈ A) (aRb⇔ (∃λ ∈ I) ({a, b} ⊂ Bλ))
1.6 Relac¸o˜es de Ordem
Definic¸a˜o 17. Seja A um conjunto. Dizemos que uma relac¸a˜o R sobre A e´ uma
relac¸a˜o de ordem parcial sobre A se
(i) R e´ reflexiva:
(∀x ∈ A) (xRx)
(ii) R e´ transitiva:
(∀x, y, z ∈ A) (xRy e yRz ⇒ xRz)
8
(iii) R e´ anti-sime´trica:
(∀x, y ∈ A) (xRy e yRx⇒ x = y)
Definic¸a˜o 18. Dizemos que um conjunto A e´ parcialmente ordenado se existe
uma relac¸a˜o de ordem parcial R sobre A.
Observac¸a˜o 7. Se a relac¸a˜o de ordem R for conhecida, utilizaremos o s´ımbolo ≤ no
lugar de R.
Definic¸a˜o 19. Seja R uma relac¸a˜o de ordem parcial sobre A. Dizemos que dois
elementos a, b ∈ A sa˜o compara´veis segundo a relac¸a˜o R se
aRb ou bRa.
Definic¸a˜o 20. Seja R uma relac¸a˜o de ordem parcial sobre A tal que quaisquer dois
elementos de A sa˜o compara´veis enta˜o dizemos que R e´ uma relac¸a˜o de ordem
total sobre A.
Se for poss´ıvel estabelecer uma relac¸a˜o de ordem total sobre A, enta˜o dizemos que
A e´ um conjunto totalmente ordenado.
Exemplo 17. Sejam A = {2, 4, 6, 8, 10, 12} e R = {(a, b) ∈ A×A | b e´ mu´ltiplo de a},
enta˜o R e´ uma relac¸a˜o de ordem parcial sobre A.
De fato,
(i) Se a ∈ A, enta˜o a = 1 · a, i.e., a e´ mu´ltiplo de a. Logo aRa. Portanto R e´
reflexiva.
(ii) Sejam a, b, c ∈ A tais que (a, b), (b, c) ∈ R. Assim b e´ mu´ltiplo de a e c e´ mu´ltiplo
de b. Logo existem r, s ∈ Z tais que b = ra e c = sb. Portanto c = rb = s(ra) =
(sr)a, onde sr ∈ Z, ou seja, c e´ mu´ltiplo de a. Consequentemente, (a, c) ∈ R.
Logo (∀a, b, c ∈ A) (((a, b), (b, c) ∈ R)⇒ ((a, c) ∈ R)) .
9
Portanto, R e´ transitiva. Simbolicamente, se a, b, c ∈ A,
((a, b) ∈ R e (b, c) ∈ R)
⇒ (b e´ mu´ltiplo de a e c e´ mu´ltiplo de b)
⇒ (∃r, s ∈ Z) (b = ra e c = sb)
⇒ (∃r, s ∈ Z) (c = sb = s(ra) = (sr)a)
t=sr⇒ (∃t ∈ Z) (c = ta)
⇒ (c e´ mu´ltiplo de a)
⇒ ((a, c) ∈ R)
Logo R e´ transitiva.
(iii) Sejam a, b ∈ A tais que aRb e bRa, enta˜o existem r, s ∈ Z tais que b = ra e
a = rb.
Assim, b = ra = r(sb) ⇒ b(1 − rs) = 0 ⇒ 1 − rs = 0 ⇒ rs = 1 ⇒ r = s =
±1 a,b>0⇒ r = s = 1. Logo b = a. Portanto, R e´ anti-sime´trica.
Logo, por (i), (ii) e (iii), R e´ uma relac¸a˜o de ordem parcial sobre A.
Graficamente,
O grafo simplificado desta relac¸a˜o de ordem parcial e´
Definic¸a˜o 21. Seja E um conjunto parcialmente ordenado e A ⊂ E.
• Dizemos que m e´ cota superior de A (ou limite superior de A ) se
(∀a ∈ A) (a ≤ m)
• Dizemos que L ∈ E e´ cota inferior de A (ou limite superior de A ) se
(∀a ∈ A) (L ≤ a)
• Dizemos que m ∈ A e´ o ma´ximo de A se
(∀a ∈ A) (a ≤ m) ,
ou seja, se m e´ uma cota superior que pertence a A.
• Dizemos que L ∈ A e´ o mı´nimo de A se
(∀a ∈ A) (L ≤ a) ,
ou seja, L e´ cota inferior de A e L ∈ A.
10
{a, b, c}
{a, b}
::ttttttttt
{a, c}
OO
{b, c}
ddJJJJJJJJJ
{a}
OO ::tttttttttt
{b}
ddJJJJJJJJJJ
::tttttttttt
{c}
ddJJJJJJJJJJ
OO
∅
OOeeKKKKKKKKKKK
99sssssssssss
• Seja B o conjunto das cotas superiores de A e m ∈ E satisfazendo (∀b ∈ B) (m ≤ b)
enta˜o m e´ chamado de supremo de A, ou seja, o supremo de A e´ a menor
das cotas superiores de A.
• Seja C o conjunto das cotas inferiores de A e L ∈ E satisfazendo (∀c ∈ C) (c ≤ L) ,
enta˜o L e´ chamado de ı´nfimo do conjunto A, ou seja, o ı´nfimo do conjunto
A e´ a maior das cotas inferiores de A.
• Seja m ∈ A. Dizemos que m e´ um elemento maximal de A se
(∀a ∈ A) (m ≤ a⇒ a = m)
• Seja L ∈ A. Dizemos que L e´ um elemento minimal de A se
(∀a ∈ A) (a ≤ L⇒ a = L)
Exemplo 18. Sejam D = {a, b, c}, E = P(D) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}, A =
{{a}, {b, c}} e R a relac¸a˜o de ordem sobre E definida por R = {(x, y) ∈ E ×E | x ⊆
y}.
O gra´fico simplificadoda relac¸a˜o de ordem R(A) e´
(a) Cotas superiores de A : {a, b, c}.
(b) Cotas inferiores de A : ∅.
(c) Ma´ximo de A : @.
(d) Mı´nimo de A : @
(e) Supremo de A : {a, b, c}.
(f) I´nfimo de A : ∅.
11
(g) Elementos maximais de A : {a}, {b, c}.
(h) Elementos minimais de A : {a}, {b, c}.
Para B = {{b}, {a}, {a, b}}, temos que
(a) Cotas superiores de B : {a, b}, {a, b, c}.
(b) Cotas inferiores de B : ∅.
(c) Ma´ximo de B : {a, b}.
(d) Mı´nimo de B : @
(e) Supremo de B : {a, b}.
(f) I´nfimo de B : ∅.
(g) Elementos maximais de B : {a, b}.
(h) Elementos minimais de B : {a}, {b}.
Exerc´ıcio 2. Prove que todo conjunto finito e´ totalmente ordenado.
1.6.1 Composic¸a˜o de Relac¸o˜es
Definic¸a˜o 22. Sejam R1 uma relac¸a˜o de A em B e R2 uma relac¸a˜o de C em D tais
que ImR1 ⊆ DomR2, enta˜o R3 uma relac¸a˜o de A em D tal que
(∀a ∈ A) (∀b ∈ B) (∀c ∈ C) (∀d ∈ D) ((a, b) ∈ R1 e (b, c) ∈ R2 ⇒ (a, c) ∈ R3)
e´ chamada relac¸a˜o composta de R1 por R2 e sera´ simbolizada por R2 ◦ R1, i.e.,
R3 = R2 ◦R1. Neste caso, ImR3 ⊆ ImR2,DomR3 = DomR1.
Se R1 e R2 sa˜o aplicac¸o˜es, enta˜o R3 = R2 ◦R1 e´ chamada aplicac¸a˜o composta de
R1 por R2.
Observac¸a˜o 8. A aplicac¸a˜o f sobre um conjunto A tal que f(a) = a para todo a ∈ A
e´ chamada de aplicac¸a˜o ideˆntica de A e sera´ simbolizada por iA.
Observac¸a˜o 9. E´ poss´ıvel termos relac¸o˜es R1 e R2 que na˜o sa˜o func¸o˜es, mas R1 ◦R2
sendo uma func¸a˜o ?
12
Exerc´ıcio 3. Se f e´ uma aplicac¸a˜o e A em B e g e´ uma aplicac¸a˜o de C em D com
Domg = Imf, enta˜o g ◦ f e´ uma aplicac¸a˜o composta de f por g.
Exerc´ıcio 4. Sejam f uma aplicac¸a˜o injetora de A em B e g uma aplicac¸a˜o injetora
de B em C, enta˜o g ◦ f e´ uma aplicac¸a˜o injetora de A em C.
13
Cap´ıtulo 2
Operac¸o˜es ou Lei de Composic¸a˜o
Interna
Definic¸a˜o 23. Uma operac¸a˜o bina´ria sobre um conjunto A e´ uma aplicac¸a˜o de
A× A em A.
Exemplo 19. Seja A = Z e f : A × A → A definida por f(a, b) = ab2, enta˜o f e´
uma operac¸a˜o sobre A.
Exemplo 20. A multiplicac¸a˜o e adic¸a˜o de nu´meros reais sa˜o operac¸o˜es sobre os
nu´meros reais.
Exemplo 21. Se A = R∗+, enta˜o f(a, b) = ab e´ uma operac¸a˜o sobre A.
Observac¸a˜o 10. Utilizaremos muitas vezes s´ımbolos gra´ficos para representarmos
operac¸o˜es. Assim, por exemplo, utilizaremos uma operac¸a˜o ∗ sobre um conjunto A
para representar uma aplicac¸a˜o f : A× A→ A de forma que:
(∀a, b ∈ A) (a ∗ b = f(a, b)) ,
ou seja, a ∗ b e´ a imagem de (a, b) ∈ A× A por uma aplicac¸a˜o f : A× A→ A.
Definic¸a˜o 24. Uma operac¸a˜o ∗ sobre A e´ associativa se
(∀a, b, c ∈ A) ((a ∗ b) ∗ c = a ∗ (b ∗ c))
Definic¸a˜o 25. Uma operac¸a˜o ∗ sobre A e´ comutativa (ou abeliana ) se
(∀a, b ∈ A) (a ∗ b = b ∗ a)
14
Definic¸a˜o 26. Um elemento e ∈ A e´ dito ser um elemento neutro de A a` es-
querda em relac¸a˜o a uma operac¸a˜o ∗ sobre A se
(∀a ∈ A) (e ∗ a = a)
Exemplo 22. Se A =

 1 0
0 0
 ,
 1 1
0 0
 , com a operac¸a˜o usual de multi-
plicac¸a˜o ·, enta˜o  1 0
0 0
 ·
 1 1
0 0
 =
 1 1
0 0

 1 1
0 0
 ·
 1 0
0 0
 =
 1 0
0 0

 1 0
0 0
 ·
 1 0
0 0
 =
 1 0
0 0

 1 1
0 0
 ·
 1 1
0 0
 =
 1 1
0 0

Logo,
 1 0
0 0
 e
 1 1
0 0
 sa˜o elementos neutros a` esquerda de A.
Exemplo 23. Se A =

 1 0
0 0
 ,
 1 1
0 0
 ,
 0 0
0 0
 com a operac¸a˜o usual de
multiplicac¸a˜o ·, enta˜o
 1 0
0 0
 e´ o u´nico elemento neutro a` esquerda para a operac¸a˜o
·.
Definic¸a˜o 27. Um elemento e ∈ A e´ dito ser um element neutro a` direita em
relac¸a˜o a uma operac¸a˜o ∗ sobre A se
(∀a ∈ A) (a ∗ e = a) .
Exemplo 24. Se A =

 0 0
0 1
 ,
 0 1
0 1
 , , enta˜o
 0 0
0 1
 e
 0 1
0 1
 sa˜o
elementos neutros a` direita de A com relac¸a˜o a operac¸a˜o de usual de multiplicac¸a˜o de
matrizes.
Exemplo 25. Se A =

 0 1
0 0
 ,
 0 1
0 1
 ,
 0 0
0 0
 , enta˜o
 0 1
0 1
 e´ o u´nico
elemento neutro a` direita de A com respeito a operac¸a˜o usual de multiplicac¸a˜o de
matrizes.
15
Definic¸a˜o 28. Dizemos que e ∈ A e´ o elemento neutro de A com relac¸a˜o a uma
operac¸a˜o ∗ se
(∀a ∈ A) (a ∗ e = e ∗ a = a) ,
ou seja, se e for um elemento neutro a` esquerda e a` direita.
Exemplo 26. Se A =

 1 0
0 0
 ,
 0 1
0 0
 ,
 0 0
0 0
 ,
 1 0
0 1
 , enta˜o
 1 0
0 1

e´ o elemento neutro de A com relac¸a˜o a` operac¸a˜o de multiplicac¸a˜o de matrizes.
Proposic¸a˜o 2. Seja A um conjunto munido de uma operac¸a˜o ∗ tal que e1 ∈ A e´ um
elemento neutro a` esquerda e e2 ∈ A e´ um elemento neutro a` direita. Enta˜o e1 = e2.
Demonstrac¸a˜o. Como e1 e´ elemento neutro a` esquerda e e2 e´ elemento neutro a` direita,
enta˜o e1 ∗ e2 = e2 e e1 ∗ e2 = e1. Logo e1 = e1 ∗ e2 = e2.
Corola´rio 1. Seja A um conjunto munido de uma operac¸a˜o ∗, enta˜o se existir um
elemento neutro e ∈ A para a operac¸a˜o ∗ enta˜o este elemento neutro e´ unico.
Definic¸a˜o 29. Seja ∗ uma operac¸a˜o sobre um conjunto A com elemento neutro e ∈
A. Dizemos que x′ e´ um elemento sime´trico a` esquerda de x (ou inverso a`
esquerda ) se x′ ∗ x = e. Neste caso dizemos que x e´ invers´ıvel (ou simetriza´vel
) a` esquerda.
Definic¸a˜o 30. Seja ∗ uma operac¸a˜o sobre um conjunto A com elemento neutro e ∈ A.
Dizemos que x′ ∈ A e´ um elemento sime´trico a` direita de x (ou inverso a`
direita) se x ∗ x′ = e. Neste caso dizermos que x e´ invers´ıvel (ou simetriza´vel) a`
direita.
Definic¸a˜o 31. Sejam ∗ uma operac¸a˜o sobre um conjunto A e e ∈ A o elemento
neutro de A com relac¸a˜o a operac¸a˜o ∗. Dizemos que a ∈ A e´ invers´ıvel se existir
a′ ∈ A tal que
a′ ∗ a = e = a ∗ a′,
ou seja, se existir a′ ∈ A que e´ o inverso a` direita e a esquerda de a.
Proposic¸a˜o 3. Seja ∗ uma operac¸a˜o associativa com elemento neutro e sobre um
conjunto A. Se a1 e´ um elemento sime´trico a` esquerda de a e a2 e´ um elemento
sime´trico a` direita de a, enta˜o a1 = a2.
16
Corola´rio 2. Seja ∗ uma operac¸a˜o associativa com elemento neutro e sobre um con-
junto A. Se a e´ invers´ıvel a` direita e a e´ invers´ıvel a` esquerda, enta˜o a e´ invers´ıvel e
o seu inverso e´ u´nico.
Proposic¸a˜o 4. Seja ∗ uma operac¸a˜o associativa com elemento neutro e sobre um
conjunto A. Se a tem inverso a′ e b tem inverso b′, enta˜o a ∗ b tem inverso b′ ∗ a′.
Demonstrac¸a˜o. Como
(a ∗ b) ∗ (b′ ∗ a′) = a ∗ (b ∗ (b′ ∗ a′)) = a ∗ ((b ∗ b′) ∗ a′) = a ∗ (e ∗ a′) e∗a′=a′= a ∗ a′ = e
e
(b′ ∗ a′) ∗ (a ∗ b) = b′ ∗ (a′ ∗ (a ∗ b)) = b′ ∗ ((a′ ∗ a) ∗ b) = b′ ∗ (e ∗ b) = b′ ∗ b = e,
enta˜o b′ ∗ a′ e´ o inverso de a ∗ b.
Definic¸a˜o 32. Seja ∗ uma operac¸a˜o sobre um conjunto A. Dizemos que a ∈ A e´ um
elemento regular a` esquerda de A para a operac¸a˜o ∗ se
(∀x, y ∈ A) (a ∗ x = a ∗ y ⇒ x = y) .
Definic¸a˜o 33. Seja ∗ uma operac¸a˜o sobre um conjunto A. Dizemos que b ∈ A e´ um
elemento regular a` direita de A para a operac¸a˜o ∗ se
(∀x, y ∈ A) (x ∗ b = y ∗ b⇒ x = y) .
Definic¸a˜o 34. Seja ∗ uma operac¸a˜o sobre um conjunto A. Dizemos que c ∈ A e´ um
elemento regular de A para a operac¸a˜o ∗ se c e´ um elemento regular a` direita e e´
elemento regular a` esquerda com relac¸a˜o a` operac¸a˜o ∗.
Notac¸a˜o 1. Seja ∗ uma operac¸a˜o sobre um conjunto A, enta˜o
• U∗(A) denotara´ o conjunto dos elementos simetriza´veis de A com relac¸a˜o a
operac¸a˜o ∗ e
• R∗(A) denotara´ o conjunto dos elementos regulares de A com relac¸a˜o a operac¸a˜o
∗.
Definic¸a˜o 35. Sejam ∗ e ? duas operac¸o˜es sobre um conjunto A tais que
(∀a, b, c ∈ A) ((a ∗ b) ? c = (a ? c) ∗ (b ? c)) ,
enta˜o dizemos que a operac¸a˜o ? e´ distributiva a` direita com relac¸a˜oa` operac¸a˜o ∗.
17
Definic¸a˜o 36. Sejam ∗ e ? duas operac¸o˜es sobre um conjunto A tais que
(∀a, b, c ∈ A) (a ? (b ∗ c) = (a ? b) ∗ (a ? c)) ,
enta˜o dizemos que a operac¸a˜o ? e´ distributiva a` esquerda com relac¸a˜o a` operac¸a˜o
∗.
Definic¸a˜o 37. Sejam ∗ e ? duas operac¸o˜es sobre um conjunto A. Dizemos que ∗ e´
distributiva em relac¸a˜o a operac¸a˜o ∗ se
(∀x, y, z ∈ A) ((x ∗ y) ? z = (x ? y) ∗ (y ? z) e z ? (x ∗ y) = (z ? x) ∗ (z ? y)) ,
Exemplo 27. Seja A = R∗ e seja ∗ uma operac¸a˜o definida por a ∗ b = a
b
,∀a, b ∈ A.
(a) ∗ na˜o e´ associativa, pois
1 ∗ (2 ∗ 2) = 1 ∗
(
2
2
)
= 1 ∗ 1 = 1
e
(1 ∗ 2) ∗ 2 =
(
1
2
)
∗ 2 =
1
2
2
=
1
4
.
(b) ∗ na˜o e´ comutativa, pois
1 ∗ 2 = 1
2
6= 2 = 2 ∗ 1.
(c) A na˜o tem elemento neutro para a operac¸a˜o ∗, pois para existir elemento neutro
e, devemos ter a
e
= e
a
= a,∀e ∈ A. Para a = 2, temos que 2
e
= e
2
e e
2
= 2, o que
implica em e = ±2 e e = 4, o que e´ imposs´ıvel.
(d) U∗(A) = ∅, pois A na˜o possui elemento neutro para a operac¸a˜o ∗.
(e) A possui elemento regular a` esquerda, pois se a ∈ A e´ tal que a ∗x = a ∗ y, para
x, y ∈ A, enta˜o a
x
= a
y
⇒ 1
x
= 1
y
⇒ x = y.
(f) A possui elemento regular a` direita, pois se b ∈ A satisfaz x ∗ b = y ∗ b, para
x, y ∈ A, enta˜o x
b
= y
b
⇒ x = y.
(g) R∗(A) = A, pois todos os elementos de A sa˜o elementos regulares a` esquerda e
a` direita.
18
Exemplo 28. Seja A = R∗ munido da operac¸a˜o ∗ do exemplo anterior e com a
operac¸a˜o de adic¸a˜o de nu´meros reais, +. Enta˜o ∗ e´ distributiva a` direita mas na˜o e´
distributiva a` esquerda com relac¸a˜o a` operac¸a˜o +.
De fato,
(∀a, b, c ∈ A)
(
(a+ b) ∗ c = a+ b
c
=
a
c
+
b
c
= (a ∗ c) + (b ∗ c)
)
.
Mas,
1 ∗ (2 + 1) = 1
2 + 1
=
1
3
.
e
(1 ∗ 2) + (1 ∗ 1) = 1
2
+ 1 =
3
2
.
Exemplo 29. Se A =

 1 0
0 0
 ,
 0 0
1 0
 ,
 0 0
0 0
 para a operac¸a˜o de multi-
plicac¸a˜o de matrizes, enta˜o R∗(A) = ∅.
2.0.2 Ta´bua de operac¸o˜es
2.0.3 A ta´bua de uma operac¸a˜o ∗ sobre um conjunto A (enu-
mera´vel, ou finito)
Seja A um conjunto munido de uma operac¸a˜o ∗ e seja (ai)i∈I uma lista dos elementos
de A, onde I = {1, 2, · · · , n} se A e´ finito e possui n elementos ou I = {1, 2, · · · } se
A e´ infinito, com ai 6= aj, se i 6= j e ∪i∈I{ai} = A.
Uma ta´bua para a operac¸a˜o ∗ sobre A com relac¸a˜o a lista (ai)i∈I e´ uma tabela ou
matriz B cujas entradas Bij e´ o elemento ai ∗ aj, ou seja, Bij = ai ∗ aj.
Exemplo 30. Sejam A = {1, i,−1,−i} e ∗ a operac¸a˜o usual de multiplicac¸a˜o em C,
enta˜o uma ta´bua da operac¸a˜o ∗ em A e´ :
∗ 1 i −1 −i
1 1 i −1 −i
i i −1 −i 1
−1 −1 −i 1 i
−i −i 1 i −1
19
2.0.4 Propriedades da operac¸a˜o a partir da ta´bua de operac¸o˜es
Observac¸a˜o 11. Se A um conjunto munido de uma operac¸a˜o ∗, enta˜o as propriedades
da operac¸a˜o ∗ podem ser identificadas a partir das caracter´ısticas da ta´bua da operac¸a˜o
∗.
(a) Se ∗ e´ uma operac¸a˜o comutativa, enta˜o a ta´bua da operac¸a˜o ∗ e´ uma matriz
sime´trica.
(b) Se a ∈ R∗(A), enta˜o na linha e na coluna rotulada por ”a”temos como entradas
todos os elementos de A.
(c) Se existe um elemento neutro e ∈ A com respeito a operac¸a˜o ∗, enta˜o na linha
correspondente a e temos todos os elementos de A na mesma ordem em que as
colunas sa˜o rotuladas e na coluna correspondente a e temos todos os elementos
de A na mesma ordem em que as linhas sa˜o rotuladas.
Exerc´ıcio 5. Seja A um conjunto munido de uma operac¸a˜o ∗ e b ∈ A um elemento
simetriza´vel de A com respeito a operac¸a˜o ∗, enta˜o que caracter´ıstica possui a ta´bua
da operac¸a˜o ∗ sobre A ?
Primeira Lista de Exerc´ıcios
1) Seja A = {0, 2, 4, 6, 8} e B = {1, 3, 5, 9}. Enumerar os elementos das seguintes
relac¸o˜es R1 = {(x, y) ∈ A × B | y = x + 1} e R2 = {(x, y) ∈ A × B | x ≤ y}.
Dizer qual e´ o domı´nio, a imagem e a inversa de cada.
2) A e´ um conjunto com 5 elementos e R = {(0, 1); (1, 2); (2, 3); (3, 4)} e´ uma
relac¸a˜o sobre A. Pede-se obter:
I) os elementos de A;
II) domı´nio e imagem de R;
III) os elementos, domı´nio e imagem de R−1;
IV) os gra´ficos de R e de R−1.
3) Seja R = {(x, y) | x ∈ R, y ∈ R, 4x2 + 9y2 = 36}. Achar:
20
(1) o domı´nio de R;
(2) a imagem de R;
(3) R−1.
4) Seja R a relac¸a˜o nos nu´meros N∗ = {1, 2, 3, · · · } definida pela sentenc¸a aberta
”2x+ y = 10”, isto e´, seja R = {(x, y) | x ∈ N∗, y ∈ N∗, 2x+ y = 10}.
Achar:
(1) o domı´nio de R, (2) a imagem de R, (3) R−1.
5) Sejam A e B dois conjuntos com m e n elementos, respectivamente. Calcular o
nu´mero de elementos de A×B e o nu´mero de relac¸o˜es de A em B.
6) Seja R a relac¸a˜o em A = {1, 2, 3, 4, 5} tal que:
xRy ⇔ {x− ye´ mu´ltiplo de 2}.
Enumerar os elementos de R. Que propriedades R apresenta ?
7) Representar graficamente as seguintes relac¸o˜es em A = {a, b, c, d} :
(a) R1 = {(a, a), (a, b), (b, c), (c, b), (c, c), (d, d)};
(b) R2 = {(a, a), (b, b), (c, c), (d, d), (b, c), (c, b), (a, d), (d, a)}.
Que propriedades R1 e R2 apresentam ?
8) Um casal tem 5 filhos: A´lvaro, Bruno, Cla´udio, Dario e Elizabete. Enumerar
os elementos da relac¸a˜o R definida no conjunto E = {a, b, c, d, e} por xRy ⇔ x
e´ irma˜o de y. Que propriedade R apresenta ?
Obs.: x e´ irma˜o de y quando x e´ homem, x 6= y e x e y teˆm os mesmos pais.
9) Seja A o conjunto das retas definidas pelos ve´rtices de um paralelogramo abcd.
Enumerar os elementos da relac¸a˜o R em A assim definida: xRy ⇔ x ‖ y. Quais
sa˜o as propriedades apresentadas por R ?
Obs. : x e´ paralela a y quando x = y ou x ∩ y = ∅ com x e y coplanares.
10) Determinar todas as relac¸o˜es bina´rias sobre o conjunto A = {a, b}.
Quais sa˜o reflexivas ? E sime´tricas ? E transitivas ? E anti-sime´tricas ?
21
11) Seja A = {1, 2, 3}. Considerem-se as seguintes relac¸o˜es sobre A :
R1 = {(1, 2); (1, 1); (2, 2); (2, 1); (3, 3)}
R2 = {(1, 1); (2, 2); (3, 3); (1, 2); (2, 3)}
R3 = {(1, 1); (2, 2); (1, 2); (2, 3); (3, 1)}
R4 = A× A
R5 = ∅
Quais sa˜o reflexivas ? sime´tricas ? transitivas ? anti-sime´tricas ?
12) Construir sobre o conjunto E = {a, b, c, d} relac¸o˜es R1, R2, R3 e R4 tais que R1
so´ tem a propriedade reflexiva, R2 so´ a sime´trica, R3 so´ a transitiva e R4 so´ a
anti-sime´trica.
13) Pode uma relac¸a˜o sobre um conjunto E 6= ∅ ser sime´trica e anti-sime´trica ?
Pode uma relac¸a˜o sobre E na˜o ser sime´trica e nem anti-sime´trica ? Justifique.
14) Seja R uma relac¸a˜o em R (conjunto dos nu´meros reais) e seja Gr seu gra´fico
cartesiano. Qual e´ a particularidade apresentada por Gr quando:
a) R e´ reflexiva ? b) R e´ sime´trica ?
15) Esboc¸ar os gra´ficos cartesianos das seguintes relac¸o˜es em R :
R1 = {(x, y) ∈ R2 | x2 + y2 = 1}
R2 = {(x, y) ∈ R2 | x+ y ≤ 2}
R3 = {(x, y) ∈ R2 | y2 = x}
R4 = {(x, y) ∈ R2 | x2 + y2 ≤ 4}
R5 = {(x, y) ∈ R2 | x2 + x = y2 + y}
R6 = {(x, y) ∈ R2 | x2 + y2 < 16}
R7 = {(x, y) ∈ R2 | x2 − 4y2 ≥ 9}
R8 = {(x, y) ∈ R2 | x2 + y2 ≥ 16}
R9 = {(x, y) ∈ R2 | x2 − 4y2 < 9}
R10 = {(x, y) ∈ R2 | y = x2}
R11 = {(x, y) ∈ R2 | y ≤ x2}
22
R12 = {(x, y) ∈ R2 | y < 3− x}
R13 = {(x, y) ∈ R2 | y ≥ sen x}
R14 = {(x, y) ∈ R2 | y ≥ x3}
R15 = {(x, y) ∈ R2 | y > x3}
Quais sa˜o reflexivas ?
Quais sa˜o sime´tricas ?
16) Seja A um conjunto finito com n elementos.
Quantas sa˜o as relac¸o˜es bina´rias em A ?
Quantas sa˜o as relac¸o˜es reflexivas me A ?
Quantas sa˜o as relac¸o˜es sime´tricas em A ?
17) Provar que se uma relac¸a˜o R e´ transitiva, enta˜o R−1 tambe´m o e´.
18) Sejam R e S relac¸o˜es no mesmo conjunto A. Provar que:
(a) R−1 ∩ S−1 = (R ∩ S)−1.
(b) R−1 ∪ S−1 = (R ∪ S)−1
(c) Se R e S s ao transitivas, ent ao R ∩ S e´ transitiva.
(d) Se R e S sa˜o sime´tricas, enta˜oR ∪ S e R ∩ S sa˜o sime´tricas.
(e) Para todo R, R ∪R−1 e´ sime´trica.
19) Seja R uma relac¸a˜o de E em F e S uma relac¸a˜o de G em H tal que DomS ⊂
ImR. Chama-se relac¸a˜o composta de R e S a seguinte relac¸a˜o (indicada S ◦R)
de E em H :
S ◦R = {(x, z) ∈ E ×H | ∃y ∈ F : (x, y) ∈ R e (y, z) ∈ S}.
Mostre que
(a) (S ◦R)−1 = R−1 ◦ S−1
(b) Se R e´ reflexiva, enta˜o R ◦R−1 e R−1 ◦R tambe´m o sa˜o (R ⊂ E × E) .
(c) Se R e´ uma relac¸a˜o sobre E, enta˜o R ◦R−1 e R−1 ◦R sa˜o sime´tricas.
23
(d) Se R e S sa˜o relac¸o˜es sime´tricas sobre um conjunto E, enta˜o
S ◦R e´ sime´trica ⇔ S ◦R = R ◦ S.
20) Sejam A = {a, b, c}, B = {1, 2, 3, 4, 5}, R = {(a, 1), (a, 2), (b, 3), (c, 4)} e
S = {(1, b), (2, b), (3, c), (4, a), (5, a), (5, b)}.
Calcule a relac¸a˜o composta S ◦ R. R e´ uma aplicac¸a˜o de A em B ? S e´ uma
aplicac¸a˜o de B em A ? S ◦ R e´ uma aplicac¸a˜o de A em A ? Justifique sua
resposta.
21) Quais das relac¸o˜es abaixo sa˜o relac¸o˜es de equivaleˆncia sobre E = {a, b, c} ?
R1 = {(a, a), (a, b), (b, a), (b, b), (c, c)}
R2 = {(a, a), (a, b), (b, a), (b, b), (b, c)}
R3 = {(a, a), (b, b), (b, c), (c, b), (a, c), (c, a)}
R4 = E × E
R5 = ∅
22) Quais das seguintes sentenc¸as abertas definem uma relac¸a˜o de equivaleˆncia em
N ( conjunto dos nu´meros naturais) ?
a) xRy ⇔ ∃k ∈ Z | x− y = 3k b) x | y
c) x ≤ y d) mdc(x, y) = 1
e) x+ y = 10.
23) Seja A o conjunto dos triaˆngulos do espac¸o euclidiano. Seja R uma relac¸a˜o em
A definida por
xRy ⇔ x e´ semelhante a y.
Mostrar que R e´ de equivaleˆncia.
24) Seja A o conjunto das retas de um plano α e seja P um ponto fixo de α. Quais
das relac¸o˜es abaixo definidas sa˜o relac¸o˜es de equivaleˆncia em A ?
(a) xRy ⇔ x ‖ y
(b) xRy ⇔ x ⊥ y
24
(c) xRy ⇔ P ∈ x ∩ y
25) Mostrar que a relac¸a˜o R sobre N × N tal que (a, b)R(c, d) ⇔ a + b = c + d e´
uma relac¸a˜o de equivaleˆncia.
26) Mostrar que a relac¸a˜o S sobre Z × Z∗ tal que (a, b)S(c, d) ⇔ ad = bc e´ uma
relac¸a˜o de equivaleˆncia.
27) Seja E um conjunto na˜o vazio. Dados X, Y ∈ P(E) (conjunto das partes de E)
mostre que as relac¸o˜es R e S sa˜o de equivaleˆncia em P(E) :
(a) X R Y ⇔ X ∩ A = Y ∩ A
(b) X S Y ⇔ X ∪ A = Y ∪ A
onde A e´ um subconjunto fixo de E.
28) Seja A = {x ∈ Z | 0 ≤ x ≤ 10} e R uma relac¸a˜o sobre A definida por
xRy ⇔ ∃k ∈ Z | x− y = 4k. Determinar o conjunto quociente A/R.
29) Seja A = {x ∈ Z | |x| ≤ 5} e R a relac¸a˜o sobre A definida por xRy ⇔ x2+2x =
y2 + 2y. Determinar o conjunto-quociente A/R.
30) Sejam E = {−3,−2,−1, 0, 1, 2, 3} e R = {(x, y) ∈ E × E | x + |x| = y + |y|}.
Mostre que R e´ uma relac¸a˜o de equivaleˆncia e descrever E/R.
31) Seja R a relac¸a˜o sobre Q definida da forma seguinte xRy ⇔ x− y ∈ Z. Provar
que R e´ uma relac¸a˜o de equivaleˆncia e descrever a classe 1.
32) Seja R = {(x, y) ∈ R2 | x−y ∈ Q}. Provar que R e´ uma relac¸a˜o de equivaleˆncia
e descrever as classes representadas por 1/2 e
√
2.
33) Mostrar que a relac¸a˜o S sobre C (conjunto dos nu´meros complexos) definida
pela lei:
(x+ yi)S(z + ti)⇔ x2 + y2 = z2 + t2
com x, y, z, t ∈ R e´ uma relac¸a˜o de equivaleˆncia. Descrever a classe 1 + i.
34) Mostre que e´ uma relac¸a˜o de equivaleˆncia em C : R = {(a+ bi, c+ di) | b = d}.
Descrever o conjunto quociente C/R.
25
35) Sejam P = (x1, y1) e Q = (x2, y2) pontos gene´ricos de um plano cartesiano pi.
Mostre que as relac¸o˜es a seguir sa˜o relac¸o˜es de equivaleˆncia sobre pi e interprete
geometricamente as classes de equivaleˆncia e o conjunto-quociente, em cada
caso.
(a) P S Q⇔ x1y1 = x2y2
(b) P S Q⇔ y2 − y1 = x2 − x1
(c) P T Q⇔ x21 + y21 = x22 + y22
(d) P V Q⇔ k1x21 + k2y21 = k1x22 + k2y22, com k2 > k1 > 0.
36) Qual e´ a relac¸a˜o de equivaleˆncia associada a cada uma das seguintes partic¸o˜es
?
I) A/R = {{a, b}, {c, d, e}}
II) A/R = {{a, b, c}, {d}, {e}}
III) A/R = {{0,±2,±4, · · · }, {±1,±3,±5, · · · }}
37) Quais sa˜o as relac¸o˜es de equivaleˆncia sobre E = {a, b}.
38) Enumerar todas as relac¸o˜es de equivaleˆncia sobre A = {a, b, c}.
39) Quantas sa˜o as relac¸o˜es de equivaleˆncia que podem ser estabelecidas sobre E =
{a, b, c, d} ?
40) Seja R uma relac¸a˜o reflexiva sobre um conjunto E. Mostre que R e´ uma relac¸a˜o
de equivaleˆncia se, e somente se, R ◦R−1 = R.
41) Seja R uma relac¸a˜o reflexiva sobre um conjunto E com as seguintes proprieda-
des:
1) Dom(R) = E;
2) (∀a, b, c ∈ E)(aRc e bRc⇒ aRb).
Mostre que R e´ uma relac¸a˜o de equivaleˆncia.
42) Fazer um diagrama simplificado das seguintes relac¸o˜es de ordem no conjunto
A = {1, 2, 3, 4, 6, 12}.
a) ordem habitual b) ordem por divisibilidade
26
43) Dizer se cada um dos seguintes subconjuntos de N e´ ou na˜o totalmente ordenado
para a relac¸a˜o de divisibilidade:
a) {24, 2, 6} b) {3, 15, 5} c) {15, 5, 30} d) N
44) Fazer um diagrama simplificado da relac¸a˜o de ordem por inclusa˜o em E =
P({a, b}) e em E ′ = P({a, b, c}).
45) Seja C o conjunto dos nu´meros complexos e sejam x = a+ bi e y = c+ di dois
elementos de C. Mostrar que R e´ uma relac¸a˜o de ordem parcial em C :
xRy ⇔ a ≤ c e b ≤ d
46) Fazer um diagrama simplificado da relac¸a˜o de ordem por inclusa˜o em:
E = {{a}, {b}, {a, b, c}, {a, b, d}, {a, b, c, d}, {a, b, c, d, e}}
Quais sa˜o os limites superiores, limites inferiores, ı´nfimo, supremo, ma´ximo e
mı´nimo do subconjunto A = {{a, b, c}, {a, b, d}, {a, b, c, d}} de E ?
47) Seja A = {x ∈ Q | 0 ≤ x2 ≤ 2} um subconjunto de Q, onde esta´ definida a
relac¸a˜o de ordem habitual. Determinar os limites superiores, limites inferiores,
ı´nfimo, supremo, ma´ximo e mı´nimo de A.
48) Seja E = {a, b, c, d, e, f, g, h, i, j} e seja R o menor subconjunto de E ×E que e´
uma relac¸a˜o de ordem e contem o subconjunto
{(f, h), (h, i), (g, i), (g, j), (d, f), (e, f), (e, g), (a, d), (b, d), (b, e), (c, e)}.
Pede-se:
(a) Desenhe o diagrama simplificado de R.
(b) Determinar os limites superiores, os limites inferiores, o ı´nfimo, o supremo,
o ma´ximo e o mı´nimo de A = {d, e}.
(c) Dar os pares que constituem R−1.
49) Em N× N define-se (a, b) ≤ (c, d)⇔ a | c e b ≤ d.
(a) Mostrar que essa relac¸a˜o (≤) e´ uma relac¸a˜o de ordem parcial em N× N.
27
(b) Sendo A = {(2, 1); (1, 2)}, ache os limites superiores, limites inferiores,
ı´nfimo, supremo, ma´ximo e mı´nimo de A.
50) Provar que se R e´ uma relac¸a˜o de ordem sobre E, enta˜o R−1 tambe´m e´.
51) Mostre que e´ uma relac¸a˜o de ordem total no conjunto C :
R = {(a+ bi, c+ di) ∈ C2 | a < c ou (a = c e b ≤ d)}
52) Sendo E = {a, b, c, d} e F = {1, 2, 3}, decida quais das relac¸o˜es abaixo sa˜o
aplicac¸o˜es de E em F.
R1 = {(a, 1), (b, 2), (c, 3)}
R2 = {(a, 1), (b, 1), (c, 2), (d, 3)}
R3 = {(a, 1), (a, 2), (b, 1) < (c, 2), (d, 3)}
R4 = {(a, 2), (b, 2), (c, 2), (d, 2)}
53) Determinar todas as aplicac¸o˜es de E = {0, 1, 2} em F = {3, 4}.
54) Achar uma func¸a˜o f : A → B, com A e B subconjuntos de R, para cada caso
abaixo:
(a) A = R, B ( R e f injetora e na˜o sobrejetora.
(b) B = A ( R, B = R e f injetora e na˜o sobrejetora.
(c) B = R, B ( R e f sobrejetora e na˜o injetora.
(d) A ( R, B = R e f sobrejetora e na˜o injetora.
55) Uma aplicac¸a˜o sobre E tal que (a, a) ∈ E para todo a ∈ E e´ chamada de
aplicac¸a˜o ideˆntica de E e e´ muitas vezes denotada por iE.
Se f : E → F e g : F → E sa˜o tais que g◦f = iE, quais das seguintes concluso˜es
sa˜o va´lidas ?
a) g = f−1; d) g e´ injetora;
b) f e´ sobrejetora; e) g e´ sobrejetora.
c) f e´ injetora;
56) Sejam as aplicac¸o˜es f : E → F e g : F → E. Provar que:
28
(a) se g ◦ f e´ injetora, enta˜o f e´ injetora;
(b) se f ◦ g e´ sobrejetora, enta˜o f e´ sobrejetora.
57) Sejam f : E → F, g : E → F, : F → G. Supondo h injetora e h ◦ g = h ◦ f,
provar que g = f.
58) Sejam f : E → F e g : F → G. Supondo g bijetora, provar que f e´ injetorase,
e somente se, g ◦ f tambe´m e´ injetora.
59) Em cada caso abaixo, considere a operac¸a˜o ∗ sobre E e verifique se e´ asso-
ciativa, se e´ comutativa, se existe elemento neutro e determine os elementos
simetriza´veis.
(a) E = R e x ∗ y = x+y
2
(b) E = R e x ∗ y = x
(c) E = R+ e x ∗ y =
√
x2 + y2
(d) E = R e x ∗ y = 3
√
x3 + y3
(e) E = R∗ e x ∗ y = x
y
(f) E = R+ e x ∗ y = x+y1+xy
(g) E = Z e x ∗ y = x+ y + x · y
(h) E = Z e x ∗ y = xy + 2x
(i) E = Q e x ∗ y = x+ xy
(j) E = Z e x ∗ y = x+ xy
(k) E = R e x ∗ y = x2 + y2 + 2xy
(l) E = R e x ∗ y = x+ y − 2x2y2
(m) E = N e x ∗ y = min(x, y)
(n) E = R e x ∗ y = max(x, y)
(o) E = Z e x ∗ y = mdc(x, y)
(p) E = N e x ∗ y = mdc(x, y)
(q) E = Z e x ∗ y = mmc(x, y)
(r) E = N e x ∗ y = mmc(x, y)
29
60) Determine R∗(E) para cada operac¸a˜o definida no exerc´ıcio anterior.
61) Em cada caso abaixo, esta´ definida uma operac¸a˜o sobre Z × Z. Verifique se e´
associativa, se e´ comutativa, se existe elemento neutro e determine os elementos
simetriza´veis.
(a) (a, b) ∗ (c, d) = (ac, 0)
(b) (a, b)4(c, d) = (a+ c, b+ d)
(c) (a, b) ⊥ (c, d) = (ac, ad+ bc)
(d) (a, b) ◦ (c, d) = (a+ c, bd)
(e) (a, b) ? (c, d) = (ac− bd, ad+ bc)
62) Determinar os elementos regulares de Z × Z para cada operac¸a˜o definida no
exerc´ıcio anterior.
63) Sejndo ∗ a operac¸a˜o sobre Z3 dada pela lei (a, b, c) ∗ (d, e, f) = (ad, be, cf).
Provar que ∗ e´ associativa e tem neutro. Determinar U∗(Z3).
64) Em que condic¸o˜es, sobre m e n ∈ Z a operac¸a˜o dada por x∗y = mx+ny, sobre
Z,
a) e´ associativa ? b) e´ comutativa c) admite elemento neutro.
65) Consideremos a operac¸a˜o ∗ em R definida por x ∗ y = ax+ by + cxy, onde a, b
e c sa˜o nu´meros reais dados. Determine as condic¸o˜es para a, b e c de modo que
∗ seja associativa e tenha elemento neutro.
66) Determine todos os elementos neutros a` esquerda no conjuntoE =

 a b
0 0
 | a, b ∈ R

para a operac¸a˜o de multiplicac¸a˜o.
67) Mostrar que nenhum elemento de R e´ regular para a operac¸a˜o4 assim definida:
x4y = x2 + y2 + xy.
68) Verifique se a lei dada por (a, b)4(c, d) = (ac, ad+ bc) e´ distributiva em relac¸a˜o
a` lei (a, b) + (c, d) = (a+ c, b+ d), tudo em Z× Z.
69) Ache m ∈ R de modo que a lei definida por x4y = x + my (sobre R) seja
distributiva em relac¸a˜o a x ∗ y = x+ y + xy (sobre R ).
30
70) Dizer quais dos subconjuntos de Z sa˜o fechados para a operac¸a˜o de adic¸a˜o.
a) Z− c) I = {x ∈ Z | x e´ ı´mpar }
b) P = {x ∈ Z | x e´ par } d) mZ = {x ∈ Z | m divide x} (m fixo).
71) Dizer quais dos seguintes subconjuntos de Z sa˜o fechados para a operac¸o˜a de
multiplicac¸a˜o.
a) Z− b) P c) I d) mZ
72) Mostrar que A = {z ∈ C | z = cos θ + i · sen θ} e´ subconjunto de C fechado
para a multiplicac¸a˜o.
73) Mostrar que A =

 cos a sen a
−sen a cos a
 | a ∈ R
 e´ subconjunto de M2(R) fe-
chado para a multiplicac¸a˜o.
74) Em cada caso abaixo, esta´ definida uma operac¸a˜o ∗ sobre E. Pede-se: fazer
a ta´bua da operac¸a˜o, verificar se e´ comutativa e se existe neutro, determinar
U∗(E) e R∗(E).
(a) E = {1, 2, 3, 4} e x ∗ y = mdc(x, y)
(b) E = {1, 3, 9, 27} e x ∗ y = mmc(x, y)
(c) E = P({a, b}) e x ∗ y = x ∪ y
(d) E = P({a, b}) e x ∗ y = x ∩ y
(e) E = P({a, b}) e x ∗ y = (x ∪ y)− (x ∩ y).
(f) E = {√3/2, 3√5/2, 4√7/2} e x ∗ y = min{x, y}
(g) E = {3√2, pi, 7/2} e x ∗ y = max{x, y}
(h) E = {1, i,−1,−i} e x ∗ y = x · y
(i) E = {0, 1, 2, 3}e x ∗ y = resto da divisa˜o em Z de x+ y por 4
(j) E = {0, 1, 2, 3, 4} e x ∗ y = resto da divisa˜o em Z de x · y por 5
75) Construir a ta´bua da operac¸a˜o de composic¸a˜o de func¸o˜es em E = {f1, f2, f3}
onde:
f1 = {(a, a), (b, b), (c, c)}
f2 = {(a, b), (b, c), (c, a)}
f3 = {(a, c), (b, a), (c, b)}
31
76) Seja EE o conjunto das aplicac¸o˜es de E em E. A composic¸a˜o de aplicac¸o˜es e´
uma operac¸a˜o sobre EE. Construir a ta´bua desta operac¸a˜o para E = {0, 1}
e determinar os elementos simetriza´veis, os elementos regulares e o elemento
neutro de EE.
77) Seja S(E) o conjunto das permutac¸o˜es de E (aplicac¸o˜es bijetoras de E em E
). A composic¸a˜o de permutac¸o˜es ’e uma operac¸a˜o em S(E). Construir a ta´bua
desta operac¸ ao em E = {1, 2, 3}. Verifique se esta operac¸a˜o e´ associativa,
comutativa, que elementos sa˜o simetriza´veis e quais sa˜o regulares.
78) Construir a ta´bua de uma operac¸ ao ∗ sobre o conjunto E = {a, b, c, d} de
modo que
(a) seja comutativa;
(b) a seja elemento neutro;
(c) U∗(E) = E;
(d) R∗(E) = E
(e) b ∗ c = a
79) Construir a ta´bua de uma operac¸a˜o ∗ sobre o conjunto E = {e, a, b, c} de modo
que:
(a) seja comutativa;
(b) e seja elemento neutro;
(c) x ∗ a = a,∀a
(d) R∗(E) = E − {a}
80) Dar um exemplo de operac¸a˜o sobre E em que todo elemento de E e´ regular,
existe neutro e so´ ele e´ simetriza´vel.
81) Dar um exemplo de operac¸ ao sobre E em que existe neutro e todos os elementos
de E, com excec¸a˜o do neutro teˆm dois sime´tricos.
82) Dar um exemplo de operac¸a˜o em que o composto de dois elementos simetriza´veis
na˜o e´ simetriza´vel.
32
83) Dar um exemplo de uma operac¸a˜o na˜o associativa nem comutativa mas que tem
neutro.
84) Seja E = P({a, b, c}). Qual e´ a condic¸a˜o sobre X e Y , com X ∈ E e Y ∈ E,
pra que {X, Y } seja fechado em relac¸a˜o a operac¸a˜o de intersecc¸a˜o sobre E ?
85) Seja ∗ a operac¸ ao sobre E = {1, 2, 3, 4, 6, 12} definida por x ∗ y = mmc(x, y).
Determinar os subconjuntos de E que teˆm treˆs elementos e sa˜o fechados em
relac¸a˜o a ∗.
86) Determinar todas as operac¸o˜es sobre o conjunto E = {a, b}.
87) Mostrar que o nu´mero de operac¸ o˜es sobre um conjunto finito com n elementos
e´ nn
2
.
88) Seja E um conjunto sobre o qual esta´ definida uma operac¸a˜o ∗ que e´ associativa.
Provar que:
(a) a ∈ E e´ regular a` esquerda se, e somente se, f : A→ A tal que f(x) = a∗x
e´ injetora;
(b) R∗(E) e´ fechado em relac¸a˜o a operac¸ a˜o ∗;
(c) se E e´ finito e R∗(E) 6= ∅, enta˜o existe elemento neutro para a operac¸a˜o
∗.
89) Seja E um conjunto munido de uma operac¸a˜o ∗ que admite elemento neutro e.
Mostrar que esta operac¸a˜o e´ associativa e comutativa se, e somente se, a∗(b∗c) =
(a ∗ c) ∗ b, quaisquer que sejam a, b, c ∈ E.
90) Uma lei de composic¸a˜o interna {x, y} 7→ x ∗ y num conjunto E 6= ∅ e´ chamada
totalmente na˜o associativa se
(∀a, b, c)(a, b, c ∈ E ⇒ (a ∗ b) ∗ c 6= a ∗ (b ∗ c))
(a) Mostre que tal lei na˜o e´ comutativa.
(b) Mostre que (a, b) 7→ ab e´ totalmente na˜o associativa em E = {3, 4, · · · }.
91) Seja ∗ uma operac¸a˜o sobre E que e´ associativa e tem neutro. Sendo A um
subconjunto na˜o vazio de E, indiquemos por C(A) o conjunto dos elementos
x ∈ E tais que a ∗ x = x ∗ a para todo a ∈ A. Provar que
33
(a) C(A) e´ fechado em relac¸a˜o a operac¸a˜o ∗;
(b) se B ⊂ A, enta˜o C(B) ⊃ C(A);
(c) C(C(C(A))) = C(A).
34
Cap´ıtulo 3
Nu´meros Inteiros
Princ´ıpio da Boa Ordem: Todo subconjunto na˜o vazio do conjunto dos nu´meros
inteiros constitu´ıdo de elementos na˜o negativos possui um mı´nimo.
Proposic¸a˜o 5 (Algor´ıtmo de Euclides). Sejam a, b ∈ Z, b 6= 0, enta˜o existe um u´nico
par (q, r) ∈ Z× Z tal que
a = bq + r, 0 ≤ r < |b|.
Demonstrac¸a˜o. (Existeˆncia) Seja A = {a− bq ∈ Z | a− bq ≤ 0, q ∈ Z}, enta˜o A 6= ∅,
pois a− b · 0 = a > 0, ou seja, a ∈ A.
Portanto, pelo Princ´ıpio da Boa Ordem, como A 6= ∅ e A e´ constitu´ıdo de
nu´meros inteiros na˜o negativos, enta˜o existe r0 = minA. Assim, existe q0 ∈ Z tal que
r0 = a− bq0.
Afirmac¸a˜o: 0 ≤ r0 < |b|.
De fato, se r0 ≥ |b|, enta˜o existiria m ≥ 0 tal que r0 = |b|+m e, como 0 ≤ m < r0
e r0 = |b|+m = a− bq0, ter´ıamos que
m = a− bq − |b| =
 a− b(q + 1), se b > 0a− b(q − 1), se b < 0
ou seja, 0 ≤ m < r0 e m ∈ A, o que e´ um absurdo, pois r0 = minA.
Logo 0 ≤ r0 < b.Portanto, tomando q = q0 e r = r0, temos que (q, r) satisfaz a = bq+r e 0 ≤ r < b.
(Unicidade) Sejam (q1, r1), (q2, r2) ∈ Z× Z tais que
a = bq1 + r, 0 ≤ r1 < b
35
e
a = bq2 + r2, 0 ≤ r2 < b.
Assim,
bq1 + r1 = bq2 + r2
⇒ b(q1 − q2) = r2 − r1
⇒ |b||q1 − q2| = |r2 − r1| < |b|
⇒ |q1 − q2| < 1
⇒ |q1 − q2| = 0
⇒ q1 = q2
⇒
 q1 = q2r2 − r1 = b(q1 − q2) = 0
⇒
 q1 = q2r1 = r2
⇒ (q1, r1) = (q2, r2)
Exemplo 31. Para encontrarmos (q, r) ∈ Z × Z satisfazendo a = bq + r, com 0 ≤
r < b, onde a = 45 e b = 56, basta escolhermos q = 0 e r = a = 45. Desta forma,
obtemos que a = 45 = 56 · 0 + 45 = bq + r, com 0 ≤ r = 45 < 56 = b.
Definic¸a˜o 38. Dizemos que um nu´mero inteiro a e´ um divisor de um nu´mero
inteiro b se existe z ∈ Z tal que b = za. Neste caso, dizemos que b e´ divis´ıvel por a
ou que b e´ mu´ltiplo de a.
Notac¸a˜o 2. a | b significara´ que a e´ um divisor de b ou b e´ mu´ltiplo de a.
Proposic¸a˜o 6 (Propriedades). Seja A = Z∗+, enta˜o a relac¸a˜o
R = {(a, b) ∈ A× A | a | b}
e´ uma relac¸a˜o de ordem parcial sobre Z∗+, ou seja,
(i) (∀a ∈ A) (a | a) (Reflexiva)
(ii) (∀a, b, c ∈ Z) (a | b e b | c⇒ a | c) (Transitiva)
(iii) (∀a, b ∈ A) (a | b e b | a⇒ a = b) (Anti-sime´trica)
Demonstrac¸a˜o.
(i) Como a = 1 · a,∀a ∈ A, enta˜o a | a,∀a ∈ A.
36
(ii) Se a | b e b | c, enta˜o existem z1, z2 ∈ Z tais que b = z1a e c = z2b, o que implica
em c = z2(z1a) = (z2z1)a. Logo a | c.
(iii) Para a, b ∈ R∗+, temos que
(a | b e b | a)
⇒ (∃z1, z2 ∈ Z) (b = z1a e a = z2b)
⇒ (∃z1, z2 ∈ Z) (b = z1a e a = z2(z1a))
⇒ (∃z1, z2 ∈ Z) (b = z1a e a = (z2z1)a)
⇒ (∃z1, z2 ∈ Z) (b = z1a e 1 = z2z1)
a,b∈Z∗+⇒ (∃z1, z2 ∈ Z) (b = z1a e z1 = z2 = 1)
⇒ (a = b)
Observac¸a˜o 12. As propriedades (i) e (ii) valem tambe´m para A = Z.
Definic¸a˜o 39. Sejam a, b ∈ Z. Dizemos que um nu´mero inteiro positivo d e´ o
ma´ximo divisor comum de a e b se
(i) d | a e d | b;
(ii) Se d′ ∈ Z satisfaz d′ | a e d′ | b, enta˜o d′ | d.
Notac¸a˜o 3. Utilizaremos o s´ımbolo mdc(a, b) ou (a, b) para representarmos o ma´ximo
divisor comum de a e b (ou entre a e b).
Exemplo 32. Vamos calcular agora o ma´ximo divisor comum entre 45 e 12. Para
fazermos isto, observe primeiramente que
• o conjunto dos divisores positivos de 45 e´ d(45) = {1, 3, 5, 9, 15, 45};
• o conjunto dos divisores positivos de 12 e´ d(12) = {1, 2, 3, 4, 6, 12};
• o conjunto dos divisores positivos de 12 e de 45 sa˜o d(45) ∩ d(12) = {1, 3}.
Portanto, o ma´ximo divisor comum entre 45 e 12 sera´ o ma´ximo do conjunto d(45)∩
d(12), que e´ 3, ou seja, mdc(45, 12) = max d(45) ∩ d(12) = 3.
Proposic¸a˜o 7. Se a, b ∈ Z d um divisor de a e de b. Enta˜o d | (αa+ βb),∀α, β ∈ Z.
37
Demonstrac¸a˜o. Se d | a e d | b, enta˜o existem z1, z2 ∈ Z tais que a = z1d e b = z2d.
Assim,
αa+ βb = α(z1d) + β(z2d) = (αz1 + βz2)d,
com αz1 + βz2 ∈ Z. Logo d | (αa+ βb).
Proposic¸a˜o 8. Sejam a, b ∈ Z e A = {αa + βb | αa + βb > 0, α, β ∈ Z}, enta˜o
mdc(a, b) = minA.
Demonstrac¸a˜o. Pelo Princ´ıpio da Boa Ordem, existe m0 = minA.
Se d′ ∈ Z e´ tal que d′ | a e d′ | b, enta˜o, pela proposic¸a˜o anterior, d′ | (αa +
βb),∀α, β ∈ Z. Como m0 ∈ A, existem α0, β0 ∈ Z tais que m0 = α0a + β0b. Logo
d′ | (α0a+ β0b), o que implica em d′ | m0.
Provaremos agora que m0 | a e m0 | b. De fato, pelo Algor´ıtmo de Euclides,
existem q, r ∈ Z tais que
(a = m0q + r, 0 ≤ r < m0)
⇒ (a = (α0a+ β0q + r, 0 ≤ r1 < m0)
⇒ (a = (α0q)a+ (β0q)b+ r, 0 ≤ r1 < m0)
⇒ ((1− α0q)a+ (β0q)b, 0 ≤ r < m0)
Logo r = 0, pois 0 ≤ r < m0 e m0 e´ o menor nu´mero inteiro positivo escrito na forma
αa+ βb, com α, β ∈ Z.
Assim, a = m0q + r = m0q ⇒ m0 | a.
Da mesma forma podemos concluir que m0 | b.
Assim, m0 > 0 e
(i) m0 | a e m0 | b;
(ii) Se d′ ∈ Z e´ tal que d′ | a e d′ | b, enta˜o d′ | m0.
Logo m0 = mdc(a, b).
Corola´rio 3. mdc(n, n+ 1) = 1,∀n ∈ Z.
Demonstrac¸a˜o. Como 1 = n + 1 − n = 1 · (n + 1) + (−1) · n e 1 e´ o menor nu´mero
inteiro positivo, enta˜o, pela Proposic¸a˜o anterior, mdc(n, n+ 1) = 1.
Corola´rio 4. Para todo inteiro n,
mdc
(
2n+ 1,
n(n+ 1)
2
)
= 1.
38
Demonstrac¸a˜o. Basta observar que se α = 2n+ 1 e β = −8, enta˜o
α(2n+ 1) + β
n(n+ 1)
2
= (2n+ 1)(2n+ 1) + (−8)n(n+ 1)
2
= 1.
Definic¸a˜o 40. Um nu´mero inteiro p 6= ±1 e´ primo se os u´nicos divisores de p sa˜o
±1 e ±p.
Proposic¸a˜o 9. Seja p um nu´mero primo e sejam a, b ∈ Z, tais que p | (ab), enta˜o
p | a ou p | b.
Demonstrac¸a˜o. Se p | a, enta˜o ja´ temos o que quer´ıamos.
Se p - a, enta˜o mdc(a, p) = 1, pois os u´nicos divisores de p sa˜o ±p e ±1.
Como mdc(p, a) = 1, enta˜o existem α, β ∈ Z tais que
αp+ βa = 1⇒ b · 1 = b(αp+ βa)⇒ b = (αb)p+ β(ab)
Como p | (ab) e mdc(p, a) = 1, enta˜o existem z, α, β ∈ Z tais que
ab = zp (3.1)
e
αp+ βa = 1 (3.2)
Portanto,
1 = αp+ βa
⇒ b · 1 = b(αp+ βa)
⇒ b = (bα)p+ β(ab)
(3.1)⇒ b = (bα)p+ β(zp)
⇒ b = (bα + βz)p
⇒ p | b
Logo p | a ou p | b.
Exerc´ıcio 6. Se c | (ab) e mdc(c, a) = 1, enta˜o c | b.
Definic¸a˜o 41. Um nu´mero inteiro m 6∈ {±1, 0} e´ um nu´mero composto se m
na˜o e´ primo, ou seja, se m 6= 0 e m possui mais de 4 divisores.
39
Proposic¸a˜o 10. Seja m um nu´mero inteiro positivo maior ou igual a 2, enta˜o o
menor elemento do conjunto (o mı´nimo) S = {x ∈ Z | x > 1 e x | m} e´ um
nu´mero primo.
Demonstrac¸a˜o. Como m ∈ S e S e´ constitu´ıdo por nu´meros inteiros positivos, enta˜o,
pelo Princ´ıpio da Boa Ordem, existe p = minS. Para provar que p e´ primo, supo-
nhamos que p seja composto. Se p for composto, enta˜o existem inteiros z1, z2 > 1 tais
que p = z1z2. Assim, como p | a e z2 | p, enta˜o z2 | a. Portanto, z2 ∈ S e z2 < p, o
que contradiz a minimalidade de p.
Logo p e´ primo.
Proposic¸a˜o 11 (Primeiro Princ´ıpio de Induc¸a˜o). Seja P (n) uma afirmac¸a˜o que de-
pende de n ∈ N = {0, 1, 2, · · · } que pode ser julgada como verdadeira ou falsa para
cada n.
Se
(i) P (n0) e´ verdadeira para algum n0 ∈ N e
(ii) (∀n ∈ N) (P (n) verdadeira ⇒ P (n+ 1) verdadeira) ,
enta˜o P (n) e´ verdadeira para todo n ∈ N tal que n ≥ n0.
Demonstrac¸a˜o. Seja S = {n ∈ N | n > n0 e P (n) e´ falsa, }. Suponhamos que P (n)
seja falsa para algum m > n0. Assim, S 6= ∅ e pelo Princ´ıpio da Boa Ordem, existe
m0 = minS. Logo, m0− 1 6∈ S e P (m0− 1) e´ verdadeira. Se P (m0− 1) e´ verdadeira,
por (ii), P (m0) e´ verdadeira, o que e´ um absurdo.
Portanto, na˜o existe P (m) falsa para nenhum m ∈ N tal que m ≥ n0. Logo P (n)
e´ verdadeira para todo n ∈ N tal que n ≥ n0.
Proposic¸a˜o 12 (Segundo Princ´ıpio de Induc¸a˜o). Seja P (n) uma afirmac¸a˜o que pode
ser julgada verdadeira ou falsa para cada n ∈ N satisfazendo as seguintes condic¸o˜es:
(i) P (n0) e´ verdadeira para algum n0 ∈ N e
(ii) Se P (k) e´ verdadeira para todo k ∈ N tal que n0 ≤ k < n, enta˜o P (n) verdadeira.
Logo P (n) e´ verdadeira para todo n ∈ N tal que n ≥ n0.
Demonstrac¸a˜o. Exerc´ıcio.
40
Exemplo 33. Mostraremos que
1 + 2 + 3 + · · ·+ n = n(n+ 1)
2
,∀n ∈ N∗.
Seja P (n) a seguinte afirmac¸a˜o:
P (n) : 1 + 2 + · · ·+ n = n(n+ 1)
2
.
Como 1 =
1(1 + 1)
2
, enta˜o P (1) e´ verdadeira.
Se P (n) e´ verdadeira, enta˜o
1 + 2 + · · ·+ n(n+ 1)
2
. (3.3)
Assim, somando n+ 1 em ambos os lados da equac¸a˜o (3.3), obtemos
1 + 2 + · · ·+ n+ (n+ 1)
= n(n+1)
2
+ (n+ 1)
= (n+ 1)
[
n
2
+ 1
]
= (n+ 1)n+2
2
= (n+1)((n+1)+1)
2
.
Portanto P (n+ 1) e´ verdadeira.
Logo, por induc¸a˜o,
1 + 2 + · · ·+ n = n(n+ 1)
2
,∀n ∈ N∗.
Proposic¸a˜o 13. Seja p primo tal que p | (a1a2 · · · an), enta˜o p | a1 ou p | a2 ou · · ·
ou p | an.
Demonstrac¸a˜o. Por induc¸a˜o sobre n.
Se n = 1, enta˜o p | a1 ⇒ p | a1.
Se n = 2, enta˜o p | (a1a2) e, pelo resultado da aula passada, p | a1 ou p | a2.
Se p | (a1 · · · an), enta˜o p | ((a1a2 · · · an−1)an), o que implica em p | (a1 · · · an−1)
ou p | an. Por induc¸a˜o,p | a1 ou p | a2 ou · · · ou p | an−1 ou p | an.
Demonstrac¸a˜o. Seja p primo e
P (n) : (∀a1, · · · , an ∈ N) (p | (a1a2 · · · an)⇒ ( p | a1 ou p | a2 ou · · · ou p | an ))
Assim,
• P (1) e´ verdadeira, pois p | a1 ⇒ p | a1.
41
• P (2) e´ verdadeira, pois p | (a1a2)⇒ (p | a1 ou p | a2) .
• Supondo que P (m) seja verdadeira para todo m ∈ N tal que 1 ≤ m < n, temos
que
p | (a1 · · · an)
⇒ p | ((a1 · · · an−1)an)
P (2) e´ verdadeira⇒ (p | (a1 · · · an−1) ou p | an)
P (n− 1) e´ verdadeira⇒ ( p | a1 ou p | a2 ou · · · ou p | an−1 ou p | an )
Logo, por induc¸a˜o, se p | (a1 · · · an), enta˜o p | a1 ou p | a2 ou · · · ou p | an.
Definic¸a˜o 42. Sejam a1, · · · , an ∈ Z. Dizemos que d e´ o ma´ximo divisor comum
de a1, · · · , an, d = mdc(a1, a2, · · · , an), se
(i) d | a1, · · · , d | an;
(ii) Se d′ ∈ Z satisfaz d′ | a1, · · · , d′ | an, enta˜o d′ | d.
Exerc´ıcio 7. Mostre que mdc(a1, · · · , an) = mdc(a1,mdc(a2, · · · , an)).
Exerc´ıcio 8. Se c = ab com mdc(a, b) = 1, a | n e b | n, enta˜o c | n.
Teorema 1 (Teorema Fundamental da Aritme´tica). Seja n ∈ Z, n > 1, enta˜o
existem k ∈ N e p1, · · · , pk nu´meros primos positivos tais que n = p1 · · · pk. Ale´m
disso, se q1, · · · , qm sa˜o nu´meros primos positivos tais que n = q1q2 · · · qm, enta˜o
k = m e cada pi e´ algum qj, ou seja, todo nu´mero inteiro maior do que 1 pode ser
escrito de forma u´nica como produto de nu´meros primos positivos a menos da ordem
em que estes nu´meros primos aparecem no produto.
Demonstrac¸a˜o. Por induc¸a˜o sobre n. Para n = 2 temos que 2 e´ primo e a afirmac¸a˜o
e´ verdadeira.
Caso contra´rio, existem p1 primo tal que p1 | n, pois n > 1, pelo resultado anterior.
Portanto existe a1 ∈ Z tal que n = p1a1. Se a1 = 1, enta˜o n = p1 e a afirmac¸a˜o e´
verdadeira.
Se 1 < a1 < n, enta˜o, por induc¸a˜o, existem p2, · · · , pk primos positivos tais que
a1 = p2 · · · pk.
Logo n = p1a = p1p2 · · · pk.
42
Sejam p1, · · · , pk, q1, · · · , qm primos positivos tais que n = p1 · · · pk = q1 · · · qm.
Assim, p1 e´ um primo com p1 | n, ou seja,
p1 | (q1 · · · qm)⇒ ( p1 | q1 ou p1 | q2 ou · · · ou p1 | qm. )
A menos de ordenac¸a˜o, podemos supor que p1 | q1 e, como p1 e q1 sa˜o nu´meros
primos positivos, segue que p1 = q1.
Logo n = p1p2 · · · pk = p1q2 · · · qm ⇒ p2 · · · pk = q2 · · · qm. Fazendo n′ = p2 · · · pk =
q2 · · · qm. Por induc¸a˜o, como n > n′, enta˜o k − 1 = m − 1 e todo pi e´ igual a algum
qj para i, j ∈ {2, · · · , k}, ou seja, k = m e todo pi e´ igual a algum qj para todo
i, j ∈ {1, 2, · · · , k}.
Corola´rio 5. Seja n ∈ N, n > 1, enta˜o existem p1, · · · , pk primos positivos e
α1, · · · , αk ∈ N∗ com p1 < p2 < · · · < pk tais que n pode ser escrito de forma
u´nica:
n = pα11 p
α2
2 · · · pαkk .
Corola´rio 6. Se n ∈ Z∗, n 6= 1, enta˜o existem p1, · · · , pk primos positivos e α1, · · · , αk
inteiros positivos tais que n pode ser escrito de forma u´nica:
n = upα11 p
α2
2 · · · pαkk para u = ±1.
Proposic¸a˜o 14. Sejam n > 1 e d > 1 um divisor de n. Se p1 < · · · < pk sa˜o nu´meros
primos positivos e α1, · · · , αk ∈ N∗ sa˜o tais que n = pα11 · · · pαkk enta˜o d = pβ11 · · · pβkk ,
para alguns β1, · · · , βk ∈ N com 0 ≤ β1 ≤ α1, · · · , 0 ≤ βk ≤ αk.
Demonstrac¸a˜o. Seja pβ a maior poteˆncia de um primo p que divide d. Assim, como
d e´ divisor de n = pα11 · · · pαkk , enta˜o existira´ pi tal que pi = p e pβ e´ um divisor de
n. Logo n = pα11 · · · pαkk = pα11 · · · pαii · · · pαkk = pβm. Pelo Teorema Fundamental da
Aritme´tica, existem γ1, · · · , γk tais que m = pγ11 · · · pγkk . Assim, como p = pi, temos
que n = pα11 · · · pαii · · · pαkk = pγ11 · · · pγi−1i−1 pγi+βi pγi+1i+1 · · · pγkk ⇒ α1 = γ1, · · · , αi−1 =
γi−1, αi = γi + β, · · · , βi+1 = γi+1, · · · , αk = γk ⇒ β ≤ αi.
Logo d = pβ11 · · · pβkk , onde 0 ≤ β1 ≤ α1, · · · , 0 ≤ βk ≤ αk.
Corola´rio 7. Seja n = pα11 · · · pαkk , onde p1, · · · , pk sa˜o primos positivos com p1 <
p2 < · · · < pk e α1, · · · , αk ∈ N∗, enta˜o o nu´mero de divisores de n e´
d(n) = (α1 + 1)(α2 + 1) · · · (αk + 1).
43
Demonstrac¸a˜o. Pela proposic¸a˜o anterior, se d e´ um divisor de n, enta˜o d e´ escrito na
forma d = pβ11 · · · pβkk , onde 0 ≤ β1 ≤ α1, · · · , 0 ≤ βk ≤ αk.
Assim, temos
• α1 + 1 possibilidades de escolha para β1;
• α2 + 1 possibilidades de escolha para β2;
· · ·
• αk + 1 possibilidades de escolha para βk.
Portanto, temos (α1 + 1) · · · (αk + 1) possibilidades de escolha para os divisores de
n.
Proposic¸a˜o 15. Sejam a = pα11 · · · pαkk e b = pβ11 · · · pβkk , onde p1, · · · , pk sa˜o primos
positivos e α1, · · · , αk, β1, · · · , βk ∈ N. Enta˜o,
mdc(a, b) = p
min{α1,β1}
1 · · · pmin{αk,βk}k .
Demonstrac¸a˜o. Como min{αi, βi} ≤ αi e min{αi, βi} ≤ βi, para todo i ∈ {1, · · · , k},
enta˜o
d = p
min{α1,β1}
1 · · · pmin{αk,βk}k
e´ um divisor de a e de b, ou seja, d | a e d | b.
Pela proposic¸a˜o anterior, se d′ | a e d′ | b, enta˜o existem γ1, · · · , γk ∈ N tais que
d′ = pγ11 · · · pγkk
com
• γ1 ≤ α1, · · · , γk ≤ αk, pois d′ | a e
• γ1 ≤ β1, · · · , γk ≤ βk, pois d′ | b.
Logo γ1 ≤ min{α1, β1}, · · · , γk ≤ min{αk, βk}, ou seja, d′ | d.
Portanto, d = p
min{α1,β1}
1 · · · pmin{αk,βk}k = mdc(a, b).
Proposic¸a˜o 16. Sejam a, b ∈ Z com b 6= 0 tais que a = bq + r para (q, r) ∈ Z × Z
com 0 ≤ r < |b|, enta˜o mdc(a, b) = mdc(b, r).
44
Demonstrac¸a˜o. Sejam d1 = mdc(a, b) e d2 = mdc(b, r). Como d1 | a e d1 | b, enta˜o
d1 | (a − bq). Logo d1 | b e d1 | r ⇒ d1 | d2, pela definic¸a˜o de d2 = mdc(b, r). Como
d2 | b e d2 | r, enta˜o d2 | (bq+r) e d2 | b, ou seja, d2 | a e d2 | b. Portanto, pela definic¸a˜o
de d1 = mdc(a, b), temos que d2 | d1. Logo, como d1 | d2 e d2 | d1 e d1, d2 > 0, enta˜o
d1 = d2, ou seja mdc(a, b) = mdc(b, r).
Proposic¸a˜o 17 (Algoritmo para ca´lculo do mdc). Sejam a, b ∈ Z e considere a
sequeˆncia (rn)n∈N definida recursivamente, atrave´s do Algoritmo de Euclides, por
r0 = b
a = bq + r1, 0 ≤ r1 < b
b = r1q2 + r2, 0 ≤ r2 < r1
r1 = r2q3 + r3, 0 ≤ r3 < r2
...
rn = rn+1qn+2 + rn+2, 0 ≤ rn+2 < rn+1
Enta˜o, existe um menor inteiro positivo n0 tal que rn0 = 0 e rn0−1 = mdc(a, b).
Demonstrac¸a˜o. Pela Proposic¸a˜o anterior,
(a, b) = (b, r1) = (r1, r2) = · · · = (rn, rn+1).
Afirmac¸a˜o: Existe n ∈ N tal que rn+1 = 0.
De fato, se rn+1 6= 0,∀n ∈ N, enta˜o temos uma quantidade infinita de elementos
na sequeˆncia
b > r1 > r2 > · · · rn > rn+1 · · · > 0,
o que contradiz o Princ´ıpio da Boa Ordem.
Logo, existe um menor n ∈ N tal que rn+1 = 0.
Assim,
(a, b) = (b, r1) = (r1, r2) = · · · = (rn, rn+1) = (rn, 0) = rn.
Portanto, rn = (a, b).
Exemplo 34. Para calcular o mdc(36, 45), observe que
45 = 36 · 1 + 9
45
36 = 9 · 4 + 0.
Logo mdc(36, 45) = 9.
Exemplo 35. Para calcular o mdc(354, 12), observe que
354 = 12 · 29 + 6
12 = 6 · 2 + 0.
Logo mdc(354, 12) = 6.
Observac¸a˜o 13. Uma maneira de formar a sequeˆncia a partir do Algoritmo de Eu-
clides e´ formar uma tabela do tipo
q1 q2 q3 · · · qn+1
a b r1 r2 · · · rn
r1 r2 r3 · · · rn+1
Desta forma, se n e´ o menor inteiro na˜o negativo tal que rn+1 = 0, enta˜o rn =
mdc(a, b).
Exemplo 36. Para calcular o mdc(354, 12), observe que
29 2
354 12 6
6 0
Logo 6 = mdc(354, 12).
Exemplo 37. Encontrar α, β ∈ Z tais que d = mdc(354, 12) = α · 354 + β · 12.
Voltando os passos no algoritmo para a determinac¸a˜o do ma´ximo divisor comum,
obtemos 6 = 1 · 354 + (−29) · 12.
Logo α = 1 e β = −29 satisfazem 6 = mdc(354, 12) = α · 354 + β · 12.
Exemplo 38. Encontrar α, β ∈ Z tais que d = mdc(345, 354) = α · 345 + β · 354.
Como
354 = 345 · 1 + 9,
345 = 9 · 38 + 3,
9 = 3 · 3 + 0,
46
enta˜o
3 = 345 · 1− 38(354− 1 · 345) = 39 · 345− 38 · 354.
Assim, α = 39 e β = −38 satisfazem 3 = mdc(345, 354) = α · 345 + β · 354.
Proposic¸a˜o 18. Sejam a, b ∈ Z, enta˜o a equac¸a˜o
ax+ by = c (3.4)
temsoluc¸a˜o inteira (nos inteiros) se, e so´ se, mdc(a, b) | c. Ale´m disso, se (x0, y0)
e´ uma soluc¸a˜o de (3.4), enta˜o, para qualquer t ∈ Z, (x1, y1) =
(
x0 +
tb
(a,b)
, y0 − ta(a,b)
)
tambe´m e´ soluc¸a˜o de (3.4).
Demonstrac¸a˜o. Se d = (a, b), enta˜o existem α, β ∈ Z tais que d = α · a+ β · b. Assim,
se d | c, existira´ k ∈ Z tal que c = kd. Logo c = kd = (kα)a + (kβ)b, ou seja,
(x0, y0) = (kα, kβ) e´ soluc¸a˜o de (3.4).
Reciprocamente, se existe (x0, y0) tal que ax0+by0 = c, enta˜o, como d = mdc(a, b)
satisfaz d | a e d | b, obtemos que d | (ax0 + by0), ou seja, d | c.
Para provar a segunda parte da proposic¸a˜o, se (x0, y0) e´ soluc¸a˜o de ax + by = c,
enta˜o
a
(
x0 +
tb
(a, b)
)
+ b
(
y0 − ta
(a, b)
)
= ax0 +
tab
(a, b)
+ by0 − tab
(a, b)
= ax0 + by0 = c,
para todo t ∈ Z, ou seja, (x1, y1) =
(
x0 +
tb
(a.b)
, y0 − ta(a,b)
)
,∀t ∈ Z tambe´m e´ soluc¸a˜o
de ax+ by = c.
Proposic¸a˜o 19. Seja (x0, y0) uma soluc¸a˜o em Z× Z da equac¸a˜o ax + by = c, onde
a, b, c ∈ Z. Assim, se (x1, y1) tambe´m for soluc¸a˜o em Z× Z, existira´ t ∈ Z tal que
x1 = x0 +
tb
(a, b)
e y1 = y0 − ta
(a, b)
Demonstrac¸a˜o. Se (x0, y0) e (x1, y1) sa˜o soluc¸o˜es de ax+ by = c, enta˜o ax0 + by0 = cax1 + by1 = c
Assim, subtraindo as equac¸o˜es acima, obtemos
a(x0 − x1) + b(y0 − y1) = 0
47
⇒ a(x0 − x1) = −b(y0 − y1) = z,
para algum z ∈ Z.
Assim, temos que a
(a,b)
| z e b | z e como
(
a
(a,b)
, b
)
= 1, temos que ab
(a,b)
| z. Portanto,
existe t ∈ Z tal que z = −t ab
(a,b)
.
Logo z = −t ab
(a,b)
= a(x0 − x1) = −b(y0 − y1), o que implica em x1 = x0 + t b(a,b) e
y1 = y0 − t a(a,b) .
Observac¸a˜o 14. Dois nu´meros inteiros a, b tais que mdc(a, b) = 1 sa˜o chamados de
coprimos ou primos entre si.
3.1 Congrueˆncias
Definic¸a˜o 43. Sejam a, b e n inteiros. Dizemos que a e´ congruente a b mo´dulo n
se n | (a− b), ou seja, se a− b e´ um mu´ltiplo de n.
Notac¸a˜o 4. Se a, b e n sa˜o inteiros enta˜o utilizaremos a ≡ b mod n significando que
a e´ congruente a b mo´dulo n.
Exemplo 39. 1) (∀a ∈ Z) (a ≡ a mod 0)
2) (∀a, b ∈ Z) (a ≡ b mod 1)
3) (∀a, b ∈ Z) (∀n ∈ N) (a ≡ b mod n⇒ a ≡ b mod (−n))
Observac¸a˜o 15. Nos casos 1) e 2) do exemplo anterior temos as chamadas con-
grueˆncias triviais. O caso 3) mostra que trabalhar com congrueˆncias mo´dulo n e´
o mesmo que trabalhar com congrueˆncias mo´dulo |n|. Portanto, a partir de agora
trabalharemos somente com congrueˆncias mo´dulo n onde n ∈ Z e n ≥ 2.
Exemplo 40.
1) 5 ≡ 7 mod 2, pois 5− 7 = −2 e 2 | (−2).
2) 13 ≡ 8 mod 5, pois 13− 8 = 5 e 5 | 5.
3) 256 ≡ 1 mod 3, pois 256− 1 = 255 e 3 | 255.
Proposic¸a˜o 20. Sejam a, n ∈ Z com n ≥ 2, enta˜o existe r ∈ Z com 0 ≤ r < n
satisfazendo a ≡ r mod n.
48
Demonstrac¸a˜o. Pelo Algor´ıtmo de Euclides, existem q, r ∈ Z tais que
a = qn+ r, 0 ≤ r < n.
Portanto a− r = qn⇒ n | (a− r).
Logo a ≡ r mod n com 0 ≤ r < n.
Observac¸a˜o 16. • Sejam a, b ∈ Z com b 6= 0, enta˜o, pelo Algoritmo de Euclides,
existem q, r ∈ Z tais que
a = qb+ r, 0 ≤ r < |b|.
Neste caso, dizemos que q e´ o quociente da divisa˜o de a por b e que r e´ o
resto (ou o res´ıduo ) da divisa˜o de a por b.
• Pela Proposic¸a˜o anterior, se a, n ∈ Z com n ≥ 2, enta˜o r ∈ Z tal que 0 ≤ r < n
e a ≡ r mod n e´ o resto da divisa˜o de a por n.
3.1.1 Propriedades das Congrueˆncias
Seja n um nu´mero inteiro maior ou igual a 2. Enta˜o,
(i) (∀a ∈ Z) (a ≡ a mod n) .
(ii) (∀a, b ∈ Z) (a ≡ b mod n⇒ b ≡ a mod n) .
(iii) (∀a, b, c ∈ Z) ((a ≡ b mod n e b ≡ c mod n)⇒ a ≡ c mod n)
(iv) (∀a, b, c, d ∈∈ Z) ((a ≡ b mod n e c ≡ d mod n)⇒ a+ c ≡ b+ d mod n) .
(v) (∀a, b, c ∈ Z) ((a ≡ b mod n e c ≡ d mod n)⇒ ac ≡ bd mod n) .
(vi) (∀a, b ∈ Z) (∀m ∈ N) (a ≡ b mod n⇒ am ≡ bm mod n) .
(vii) (∀a, b, c ∈ Z) ((ca ≡ cb mod n e (c, n) = 1)⇒ a ≡ b mod n)
Proposic¸a˜o 21. Se (c, n) = 1, enta˜o a congrueˆncia cx ≡ b mod n tem uma soluc¸a˜o
inteira x. Quaisquer duas soluc¸o˜es x1 e x2 sa˜o congruentes mo´dulo n.
49
Demonstrac¸a˜o. Se (c, n) = 1, enta˜o existem α, β ∈ Z tais que
αc+ βn = 1
⇒ b(αc+ βn) = b
⇒ (bα)c+ (bβ)n = b
⇒ (bα)c ≡ b mod n
Logo x = bα e´ uma soluc¸a˜o da congrueˆncia cx ≡ b mod n.
Se x1 e x2 sa˜o soluc¸o˜es de cx ≡ b mod n, enta˜o cx1 ≡ b mod ncx2 ≡ b mod n
Logo, subtraindo as equac¸o˜es acima, obtemos cx1 ≡ cx2 mod n e, como (c, n) = 1,
segue que x1 ≡ x2 mod n.
Proposic¸a˜o 22. Seja a ∈ Z e p primo, enta˜o ap ≡ a mod p.
Demonstrac¸a˜o. Fixemos p primo.
Se a = 0, enta˜o, obviamente, ap ≡ a mod p.
Se a > 0 satisfaz ap ≡ a mod p, enta˜o (−a)p ≡ (−a) mod p. Portanto basta
mostrarmos que np ≡ n mod p para todo n ∈ N∗. Seja P (n) a afirmac¸a˜o: np ≡ n
mod p. P (1) e´ verdadeira, pois 1 = 1p ≡ 1 mod p.
Suponhamos que P (n) seja verdadeira. Assim, np ≡ n mod p.
Portanto (n+ 1)p ≡ np + 1 ≡ (n+ 1) mod p, ou seja, P (n+ 1) e´ verdadeira.
Logo, por induc¸a˜o, P (n) e´ verdadeira para todo n ∈ N∗, ou seja, np ≡ n mod p
para todo n ∈ N.
Observac¸a˜o 17. Seja n ≥ 2. Definindo a relac¸a˜o R sobre Z por
R = {(a, b) ∈ Z× Z | a ≡ b mod n},
enta˜o R e´ uma relac¸a˜o de equivaleˆncia.
A classe de equivaleˆncia de a ∈ Z e´ o conjunto
a = {x ∈ Z | x ≡ a mod n}.
O conjunto das classes de equivaleˆncia de R e´ o conjunto quociente
Z/R = {0, 1, · · · , n− 1},
50
que pode tambe´m ser simbolizada por Z/nZ ou por Zn.
E´ poss´ıvel definirmos operac¸o˜es de adic¸a˜o e multiplicac¸a˜o em Zn da seguinte
forma:
a · b := a · b
a+ b := a+ b
Segunda Lista de Exerc´ıcios
1) Prove por induc¸a˜o:
(a) 1 + 2 + 3 + · · ·+ n = n(n+ 1)
2
,∀n ∈ N, n ≥ 1.
(b) 12 + 22 + 32 + · · ·+ n2 = n(n+1)(2n+1)
6
,∀n ∈ N, n ≥ 1.
(c) 0 < a⇒ 0 < an,∀n ∈ N.
(d) am · an = am+n,∀m,n ∈ N.
(e) (am)n = amn,∀m,n ∈ N.
(f) a < 0⇒ 0 < a2n e a2n+1 < 0,∀n ∈ N.
(g) 22n−1 · 3n+2 + 1 e´ divis´ıvel por 11,∀n ∈ N, n ≥ 1.
(h) 32n+1 + 2n+1 e´ divis´ıvel por 7,∀n ∈ N.
(i) 22n + 15n− 1 e´ divis´ıvle por 9,∀n ∈ N, n ≥ 1.
(j) 34n+2 + 2 · 43n+1 e´ mu´ltiplo de 17,∀n ∈ N.
2) Sejam a, b, c ∈ N∗ nu´meros sem divisores comuns tais que a2 + b2 = c2.
(a) Mostre que ou a ou b e´ par;
(b) Mostre que ou a ou b e´ mu´ltiplo de 3.
3) Mostre que o quadrado de um nu´mero ı´mpar e´ da forma 8q + 1, q ∈ Z.
4) Seja a ∈ Z um nu´mero na˜o divis´ıvel por 5. Mostre que a4 = 5q + 1, q ∈ Z.
5) Sejam a, b ∈ Z de modo que mdc(a, b) = 1. Se a | c e b | c, mostre que ab | c.
6) Use o resultado do exerc´ıcio anterior para provar que 6 | n(2n+7)(7n+1),∀n ∈
Z.
51
7) Mostre que, para todo inteiro n, o ma´ximo divisor comum entre 2n+1 e
n(n+ 1)
2
e´ 1.
8) Prove que mdc(a, b) = mdc(a+ bc, a+ b(c− 1)),∀a, b, c ∈ Z.
9) Mostre que a3 − a e´ mu´ltiplo de 3,∀a ∈ Z.
10) Mostre que a3 − b3 e´ mu´ltiplo de 3, se, e somente se, a− b e´ mu´ltiplo de 3.
11) Mostre que 6 | n(n+ 1)(2n+ 1),∀n ∈ Z.
12) Mostre que 30 | n(n2 − 49)(n2 + 49), ∀n ∈ Z.
13) Ache o resto da divisa˜o de a = 531 · 312 · 2 por 7.
14) Ache o algorismo das unidades dos nu´meros 9(9
9) e 7(7
7).
15) Ache os dois u´ltimos algarismos de 7(7
1000).
16) Enuncie e justifique crite´rios de divisibilidade por 9, 5, 11 e 6.
17) Mostre que o conjunto dos nu´meros primos e´ infinito.
18) Sejam a, b, c ∈ Z nu´meros tais que a | bc e mdc(a, b) = 1. Prove que a | c.
19) Mostre que se p e´ primo, enta˜o p |
(
p
i
)
onde 0 < i < p.
20) Sejam a, b ∈ Z. Se existem x, y ∈ Z tais que ax+by = 1, mostre que mdc(a, b) =
1.
52
Cap´ıtulo 4
Grupos
4.1 Estruturas Alge´bricas
Notac¸a˜o 5. Utilizaremos (G, ∗) significando um conjunto na˜o vazio G e´ munido de
uma operac¸a˜o ∗.
Definic¸a˜o 44. Um conjunto na˜o vazio munido de uma operac¸a˜o ∗ e´ chamado de
grupo´ide.
Definic¸a˜o 45. Um conjunto na˜o vazio munido de uma operac¸a˜o ∗ associativa e´ cha-
mado de semigrupo .
Definic¸a˜o46. Um conjunto na˜o vazio munido de uma operac¸a˜o ∗ associativa e com
elemento neutro e´ chamado de mono´ide.
Definic¸a˜o 47. Dizemos que um conjunto na˜o vazio G munido de uma operac¸a˜o ∗ e´
um grupo com respeito a esta operac¸a˜o ∗ se:
(i) ∗ e´ associativa:
(∀x, y, z ∈ G) ((x ∗ y) ∗ z = x ∗ (y ∗ z))
(ii) G possui um elemento neutro com relac¸a˜o a esta operac¸a˜o ∗:
(∃e ∈ G) (∀a ∈ G) (a ∗ e = e ∗ a = a)
(iii) Todos os elementos de G sa˜o invers´ıveis (simetriza´veis):
(∀g ∈ G) (∃g′ ∈ G) (g ∗ g′ = g′ ∗ g = e)
53
Exemplo 41.
(i) Os conjuntos Q∗ e R∗ sa˜o grupos em relac¸a˜o a operac¸a˜o usual de mu´ltiplicac¸a˜o.
(ii) O conjunto U(Mn(R)) = {x ∈ Mn(R) | det(x) 6= 0}, das matrizes n × n
com determinante diferente de 0 e´ um grupo com respeito a operac¸a˜o usual de
multiplicac¸a˜o de matrizes.
(iii) Se p e´ primo, enta˜o Z∗p o conjunto das classes de equivaleˆncia mo´dulo p dife-
rentes de 0 e´ um grupo em relac¸a˜o a operac¸a˜o de multiplicac¸a˜o definida por
(∀x, y ∈ Z) (x · y = x · y)
(iv) O subconjunto {−1, 1, i,−i} do conjunto dos nu´meros complexos e´ um grupo em
relac¸a˜o a operac¸a˜o usual de multiplicac¸a˜o de nu´meros complexos.
Definic¸a˜o 48. Seja A um conjunto munido de uma operac¸a˜o ∗ e H ⊂ A. Dizemos
que H e´ um subconjunto de A fechado para a operac¸a˜o ∗ se
(∀x, y ∈ H) (x ∗ y ∈ H)
Exemplo 42. Seja A = Z4, enta˜o os seguintes subconjuntos de A sa˜o fechados para
a operac¸a˜o de multiplicac¸a˜o:
H1 = {0}
H2 = {1}
H3 = {0, 1}
H4 = {0, 2}
H5 = {1, 3}
H6 = {0, 1, 2}
H7 = {0, 1, 3}
H8 = {0, 1, 2, 3}
Definic¸a˜o 49. Sejam (G, ∗) um grupo e H um subconjunto na˜o vazio de G. Dizemos
que H e´ um subgrupo de G com relac¸a˜o a operac¸a˜o ∗ se (H, ∗) tambe´m e´ um grupo.
54
Exemplo 43. (i) (Q∗, ·) e´ um subgrupo de (R∗, ·); (Z,+) e´ um subgrupo de (Q,+); (R,+)
e´ um subgrupo de (C,+).
(ii) O conjunto das matrizes diagonais invers´ıveis e´ um subgrupo do conjunto das
matrizes invers´ıveis com respeito a operac¸a˜o de multiplicac¸a˜o de matrizes.
Proposic¸a˜o 23. Seja (G, ∗) um grupo. Um subconjunto H de G e´ um subgrupo de
G com respeito a esta operac¸a˜o ∗ se, e somente se,
(i) H 6= ∅.
(ii) (∀x, y ∈ H) (x ∗ y−1 ∈ H) ,
Demonstrac¸a˜o. Por (i), existe x ∈ H. Da´ı, por (i), x ∗ x−1 = e ∈ H. Logo H tem
elemento neutro e. Como e, x ∈ H, enta˜o, por (ii), x−1 = e ∗ x−1 ∈ H. Logo todo
elemento de H tem seu inverso tambe´m em H. Como H e´ um subconjunto de G enta˜o
a associatividade de H com relac¸a˜o a operac¸a˜o ∗ e´ herdada pela associatividade de
G com relac¸a˜o a esta operac¸a˜o ∗. Para finalizar, basta mostrarmos que H e´ um
subconjunto de G fechado para a operac¸a˜o ∗. De fato, se x, y ∈ H, enta˜o x, y−1 ∈ H.
Da´ı, por (ii), temos que x ∗ (y−1)−1 = x ∗ y ∈ H.
Notac¸a˜o 6. A menos que a operac¸a˜o seja colocada explicitamente, utilizaremos a
notac¸a˜o multiplicativa dos nu´meros reais quando dizemos que um conjunto G e´ um
grupo ou que H e´ um subgrupo de G. Usaremos tambe´m o s´ımbolo H ≤ G significando
que H e´ um subgrupo de G.
Proposic¸a˜o 24. Sejam H1 e H2 subgrupos de um grupo G, enta˜o H1 ∩ H2 e´ um
subgrupo de G.
Demonstrac¸a˜o. Como H1 e H2 sa˜o subgrupos de G, enta˜o e ∈ H1 e e ∈ H2, ou seja,
e ∈ H1 ∩ H2. Ale´m disso, se x, y ∈ H1 ∩ H2, enta˜o x, y ∈ H1 e x, y ∈ H2. Como
x, y ∈ H1e x, y ∈ H2 e H1 e H2 sa˜o subgrupos de G, enta˜o xy−1 ∈ H1 e xy−1 ∈ H2, o
que implica em xy−1 ∈ H1 ∩H2. Logo H1 ∩H2 ≤ G.
Exemplo 44. Sejam G um grupo e Z(G) = {x ∈ G | gx = xg,∀g ∈ G}, enta˜o
Z(G) ≤ G. Z(G) e´ chamado de centro do grupo G.
55
Demonstrac¸a˜o. Z(G) 6= ∅, pois e ∈ Z(G), ja´ que eg = ge = g,∀g ∈ G. Ale´m disso,
se x, y ∈ Z(G), temos que
(∀g ∈ G) (xg = gx)
⇒ (∀g ∈ G) (xg = (gx)e)
⇒ (∀g ∈ G) (xg = (gx)(y−1y))
⇒ (∀g ∈ G) (xg = ((gx)y−1)y)
⇒ (∀g ∈ G) (xg = y((gx)y−1))
⇒ (∀g ∈ G) (xg = y(g(xy−1))
⇒ (∀g ∈ G) (y−1(xg) = y−1(y(g(xy−1))))
⇒ (∀g ∈ G) ((y−1x)g = (y−1y)(g(xy−1)))
⇒ (∀g ∈ G) ((xy−1)g = (y−1y)(g(xy−1)))
⇒ (∀g ∈ G) ((xy−1)g = e(g(xy−1)))
⇒ (∀g ∈ G) ((xy−1)g = g(xy−1))
Logo xy−1 ∈ Z(G).
Portanto, pela Proposic¸a˜o 23, Z(G) ≤ G.
Definic¸a˜o 50. Seja H um subgrupo de um grupo G e seja a ∈ G. O conjunto Ha =
{ha | h ∈ H} e´ chamado de classe lateral a` direita de G mo´dulo H e o conjunto
aH = {ah | h ∈ H} e´ chamado de classe lateral a` esquerda de G mo´dulo H.
Notac¸a˜o 7. O conjunto das classes laterais a` direita de G mo´dulo H e´ simbolizado
por G/H.
Proposic¸a˜o 25. Se H um subgrupo de um grupo G e a, b ∈ G, enta˜o Ha = Hb se,
e somente se, ab−1 ∈ H.
Demonstrac¸a˜o. Se Ha = Hb, enta˜o para todo h1 ∈ H existe h2 ∈ H tal que
h1a = h2b
⇒ h−11 (h1a) = h−11 (h2b)
⇒ (h−11 h1)a = (h−11 h2)b
⇒ ea = (h−11 h2)b
⇒ a = (h−11 h2)b
⇒ ab−1 = ((h−11 h2)b)b−1
⇒ ab−1 = (h−11 h2)(bb−1)
⇒ ab−1 = (h−11 h2)e
⇒ ab−1 = h−11 h2
56
Portanto, como h1, h2 ∈ H e H ≤ G, temos que h−11 h2 ∈ H, o que implica em
ab−1 = h−11 h2 ∈ H.
Reciprocamente, se ab−1 ∈ H, enta˜o existe h ∈ H tal que ab−1 = h, o que implica
em ha = b e a = h−1b.
Para todo h1 ∈ H, se h2 = h1h−1, enta˜o h2 ∈ H e
h1a = (h1(h
−1h))a = ((h1h−1)h)a) = (h1h−1)(ha) = (h1h−1)b = h2b,
o que implica em Ha ⊆ Hb.
Para todo h1 ∈ H, se h2 = h1h, enta˜o h2 ∈ H e
h1b = h1(ha) = (h1h)a = h2a,
o que implica em Hb ⊆ Ha.
Logo Ha = Hb.
Proposic¸a˜o 26. Sejam H ≤ G e R = {(a, b) ∈ G× G | ab−1 ∈ H}, enta˜o R e´ uma
relac¸a˜o de equivaleˆncia sobre G. Ale´m disso, temos que a = Ha, ou seja, o conjunto
das classes laterais de a` direita de G mo´dulo H coincide com o conjunto das classes
de equivaleˆncia de G/R, ou seja, G/R = G/H. Em particular,
G =
·⋃
a∈T
Ha,
onde T e´ o conjunto dos representantes das diferentes classes de equivaleˆncia de R
sobre G.
Demonstrac¸a˜o. R e´ uma relac¸a˜o de equivaleˆncia sobre G, pois:
(i) R e´ reflexiva:
(∀a ∈ G)(aa−1 = e ∈ H)
⇒ (∀a ∈ G) ((a, a) ∈ R)
(ii) R e´ sime´trica:
(∀a, b ∈ G)
(a, b) ∈ R
⇒ ab−1 ∈ H
⇒ ba−1 = (ab−1)−1 ∈ H
⇒ (b, a) ∈ R
57
(iii) R e´ transitiva:
(∀a, b, c ∈ H)
((a, b) ∈ R e (b, c) ∈ R)
⇒ (ab−1 ∈ H e bc−1 ∈ H)
⇒ (ac−1 = ab−1bc−1 ∈ H)
⇒ ((a, c) ∈ R)
Como R e´ uma relac¸a˜o de equivaleˆncia, enta˜o, pela Proposic¸a˜o anterior, temos
que
b ∈ a⇔ ab−1 ∈ H ⇔ b ∈ Ha = Hb.
Logo, para todo a ∈ G, temos que a = Ha, ou seja, o conjunto das classes de
equivaleˆncia de G mo´dulo R coincide com o conjunto das classes laterais a` direita
de G mo´dulo H. Portanto, G =
·⋃
a∈T
Ha, onde T e´ o conjunto dos representantes das
diferentes classes de equivaleˆncia de A mo´dulo R.
Definic¸a˜o 51. O nu´mero de elementos de um grupo G e´ chamado de ordem do grupo
G e e´ simbolizado por ooo(G). No caso em que G tem m elementos enta˜o ooo(G) = m
e no caso em que o grupo G e´ infinito ooo(G) = ∞. Se H ≤ G enta˜o o ı´ndice de G
mo´dulo H e´ o nu´mero de elementos de G/H e e´ simbolizado por iG(H).
Proposic¸a˜o 27 (Teorema de Lagrange). Se H ≤ G, enta˜o ooo(G) = iG(H) ·ooo(H). Em
particular, a ordem de todo subgrupo de um grupo G e´ divisor da ordem do grupo G.
Demonstrac¸a˜o. Pela Proposic¸a˜o 26,
G =
⋃
a∈T
Ha,
onde T o conjunto dos diferentes representantes das classes laterais a` direita de G
mo´dulo H.
Assim,
|G| =
∣∣∣∣∣⋃
a∈T
Ha
∣∣∣∣∣ = ∑
a∈T
|Ha|
Agora, como para todo a ∈ G, a aplicac¸a˜o ϕa : H → Ha definida por h 7→ ha e´
bijetora, enta˜o |Ha| = |H| = ooo(H) para todo a ∈ T.
Logo, ooo(G) =
∑
a∈T |Ha| =
∑
a∈T ooo(H) =
∑|T |
k=1 ooo(H) = |T |ooo(H) = iG(H)ooo(H).
58
Definic¸a˜o 52. Seja G um grupo. Dizemos que g ∈ G tem ordem n se n e´ o
menor inteiro positivo tal que gn = e. No caso em que na˜o existe tal n inteiro positivo
satisfazendo esta condic¸a˜o, dizemos que g tem ordem infinita. Utilizamos ooo(g)
significando a ordem de um elemento g ∈ G. Assim, ooo(g) = n se g tem ordem n e
ooo(g) =∞ se g tem ordem infinita.
Proposic¸a˜o