Notas sobre Elementos de Matemática Finita

Prévia do material em texto

Notas sobre Elementos de Matema´tica Finita
Pedro Martins Rodrigues
April 19, 2013
2
Contents
1 Apresentac¸a˜o 5
2 Conjuntos, func¸o˜es e relac¸o˜es: noc¸o˜es ba´sicas 7
2.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Func¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Relac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Nu´meros Naturais: Axiomas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4.1 Nu´meros Inteiros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.4.2 Conjuntos finitos e infinitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.5 Princ´ıpio de Induc¸a˜o Finita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.6 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Elementos de Aritme´tica dos Inteiros 29
3.1 Lema da Divisa˜o e o Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1 Ma´ximo Divisor Comum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Nu´meros primos e o Teorema Fundamental da Aritme´tica . . . . . . . . . . . . . . . . . . . . 36
3.2.1 Nu´meros perfeitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Congrueˆncias e aritme´tica modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 A equac¸a˜o linear numa varia´vel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4 O Teorema Chineˆs dos Restos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.5 Os Teoremas de Fermat e Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5.1 Nota sobre o ca´lculo eficiente de poteˆncias . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.5.2 Testes de primalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.5.3 Raizes mo´dulo m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.5.4 Aplicac¸a˜o a` Criptografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.6 Equac¸o˜es modulares com mo´dulo primo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.6.1 Ordem de um inteiro mo´dulo p e ra´ızes primitivas . . . . . . . . . . . . . . . . . . . . 65
3.6.2 Raizes mo´dulo p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.7 O Lema de Hensel e a resoluc¸a˜o de equac¸o˜es mo´dulo pj . . . . . . . . . . . . . . . . . . . . . 69
3.8 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4 Elementos de Combinato´ria Enumerativa 95
4.1 Subconjuntos de [n] e nu´meros binomiais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.1.1 Escolhas com e sem ordem, com e sem repetic¸a˜o . . . . . . . . . . . . . . . . . . . . . 100
4.2 Princ´ıpio do Pombal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.3 Distribuic¸o˜es, partic¸o˜es e func¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
4.3.1 Partic¸o˜es de um conjunto e Nu´meros de Stirling de segunda espe´cie . . . . . . . . . . . 106
3
4 CONTENTS
4.3.2 Partic¸o˜es de um nu´mero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.3.3 Distribuic¸o˜es e func¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.4 O Princ´ıpio de Inclusa˜o-Exclusa˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.5 Permutac¸o˜es e simetrias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
4.5.1 Decomposic¸a˜o c´ıclica de permutac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
4.5.2 Transposic¸o˜es e paridade de uma permutac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . 119
4.5.3 Grupos de simetrias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.6 Contagem com simetria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
4.6.1 O Teorema de Polya . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.7 Func¸o˜es Geradoras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
4.8 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
5 Elementos da Teoria de Grafos 161
5.1 Introduc¸a˜o e definic¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
5.1.1 Sequeˆncia de graus de um grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
5.1.2 Passeios e caminhos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
5.1.3 Isomorfismos e Automorfismos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
5.2 A´rvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
5.2.1 Busca em largura e em profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
5.2.2 Grafos com pesos e a´rvores geradoras minimais . . . . . . . . . . . . . . . . . . . . . . 174
5.2.3 Fo´rmula de Cayley e Co´digo de Pru¨fer . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
5.3 Grafos planares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
5.3.1 So´lidos regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.3.2 Grafo dual e condic¸o˜es de planaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
5.3.3 Teorema de Kuratowski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.4 Colorac¸o˜es de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.4.1 Algoritmo ganancioso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.4.2 Colorac¸a˜o de grafos planares. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
5.4.3 Polino´mio de colorac¸a˜o. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
5.4.4 O Teorema de Tura´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.4.5 A teoria de Ramsey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
5.5 Emparelhamentos em grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
5.5.1 Emparelhamentos em grafos bipartidos . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
5.5.2 Emparelhamentos com prioridades ou o “problema dos casamentos” . . . . . . . . . . 197
5.6 Grafos dirigidos e Fluxos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
5.6.1 Fluxos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
5.7 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
I´ndice
Chapter 1
Apresentac¸a˜o
Estas Notas foram elaboradas ao longo dos anos lectivos de 2008/2009 a 20012/2013 como textos de apoio
para a Unidade Curricular de Elementos de Matema´tica Finita da Licenciatura em Matema´tica Aplicada e
Computac¸a˜o do Instituto Superior Te´cnico (Universidade Te´cnica de Lisboa).
A informac¸a˜o sobre a UC conte´m mais de uma dezena de refereˆncias bibliogra´ficas que os alunos sa˜o enco-
rajados a consultar, sendo dadas nas aulas explicac¸o˜es adicionais sobre elas. Esta´ portanto fora de questa˜o
qualquer pretensa˜o, na escrita destas notas, de substituir essas refereˆncias. O seu objectivo,mais modesto,
e´ o de servirem como guia de estudo e, espera-se, como est´ımulo para o seu aprofundamento.
Esta Unidade Curricular constitui uma introduc¸a˜o a` Aritme´tica dos inteiros, e nomeadamente a` Aritme´tica
Modular, a` Combinato´ria Enumerativa e a` Teoria dos Grafos. A natureza introduto´ria do curso, bem
como os constrangimentos de tempo, impedem qualquer abordagem aprofundada e sistema´tica destes temas,
privilegiando-se antes a apresentac¸a˜o de diversos aspectos de cada um deles, de exemplos e aplicac¸o˜es signi-
ficativos e, sobretudo, da enorme variedade e riqueza de problemas associados.
5
6 CHAPTER 1. APRESENTAC¸A˜O
Chapter 2
Conjuntos, func¸o˜es e relac¸o˜es: noc¸o˜es
ba´sicas
2.1 Conjuntos
Usamos o termo conjunto como um termo primitivo, ou seja, na˜o definido a partir de outros termos.
Intuitivamente um conjunto e´ uma qualquer colecc¸a˜o de objectos (os elementos ou membros do conjunto).
Esta descric¸a˜o levanta va´rios problemas, relativos a` noc¸a˜o de objecto, ao significado do termo colecc¸a˜o e
em particular ao uso do pronome qualquer, que so´ podem ser resolvidos satisfatoriamente por uma fundac¸a˜o
axioma´tica da Teoria dos Conjuntos, fora do aˆmbito desta cadeira.
Mas, devido a` natureza simples dos conjuntos com que teremos ocasia˜o de lidar, esses problemas na˜o nos
surgira˜o no caminho.
Vamo-nos portanto ater a uma descric¸a˜o de algumas das noc¸o˜es e propriedades mais elementares da chamada
Teoria intuitiva dos Conjuntos, bem como da notac¸a˜o correspondente.
Note-se que essa descric¸a˜o depende do uso de s´ımbolos lo´gicos e suas propriedades, que na˜o sera˜o recordados
aqui.
1. Um conjunto e´ completamente determinado pelos seus elementos. Usamos a notac¸a˜o x ∈ X para dizer
que x e´ um elemento do conjunto X e x /∈ X para dizer que x na˜o e´ um elemento do conjunto X.
2. Um conjunto pode ser definido por extensa˜o, quer dizer, enumerando todos os seus elementos, ou
atrave´s de uma propriedade que determina que elementos tem o conjunto. Por exemplo, o conjunto
dos nu´meros naturais pares menores que 8 pode ser descrito como
{2, 4, 6}
ou como
{x ∈ N : x < 8 ∧ ∃z ∈ N : x = 2z}
onde N designa o conjunto de todos os naturais.
7
8 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
3. Existe o conjunto vazio, designado por ∅ e caracterizado por na˜o ter elementos.
4. Dados conjuntos X e Y existem o conjunto unia˜o X ∪ Y , o conjunto intersecc¸a˜o X ∩ Y e o conjunto
diferenc¸a X \ Y definidos repectivamente por
X ∪ Y = {x : x ∈ X ∨ x ∈ Y }
X ∩ Y = {x : x ∈ X ∧ x ∈ Y }
X \ Y = {x : x ∈ X ∧ x /∈ Y }
5. X ⊂ Y denota o facto de todo o elemento de X ser tambe´m elemento de Y :
X ⊂ Y ⇔ (x ∈ X ⇒ x ∈ Y )
Se Y ⊂ X mas Y 6= X, usa-se a notac¸a˜o Y ( X.
6. Um elemento x ∈ X pode por sua vez ser tambe´m um conjunto. Em particular, dado um qualquer
conjunto X, existe o conjunto das partes de X:
P(X) = {Y : Y ⊂ X}
7. Dados conjuntos X e Y , existe o conjunto produto
X × Y = {(x, y)|x ∈ X ∧ y ∈ Y }
ou seja, o conjunto cujos membros sa˜o os pares ordenados em que o primeiro elemento pertence a X e
o segundo a Y .
Observac¸a˜o 2.1.1 A definic¸a˜o do produto de dois conjuntos X × Y pode ser feita a partir das noc¸o˜es
anteriores: podemos por exemplo definir
X × Y = {{{a}, {a, b}} : a ∈ X ∧ b ∈ Y }
Ou seja, cada elemento deste conjunto e´ um conjunto que tem como membros o conjunto que tem como u´nico
elemento um a ∈ X e o conjunto que tem como elementos o mesmo a ∈ X e um b ∈ Y .
Para vermos que temos uma definic¸a˜o correcta, basta comprovar que
{{a}, {a, b}} = {{c}, {c, d}} =⇒ a = c ∧ b = d
2.2. FUNC¸O˜ES 9
2.2 Func¸o˜es
Intuitivamente, uma func¸a˜o e´ uma correspondeˆncia entre os elementos de um conjunto X (o domı´nio ou
conjunto de partida) e elementos de um conjunto Y (o contradomı´nio ou conjunto de chegada)
Definic¸a˜o 2.2.1 uma func¸a˜o f : X → Y diz-se
1. injectiva se
x1 6= x2 ⇒ f(x1) 6= f(x2) ∀x1, x2 ∈ X
2. sobrejectiva se
∀y ∈ Y ∃x ∈ X : f(x) = y
.
3. bijectiva se for injectiva e sobrejectiva.
Definic¸a˜o 2.2.2 Se f : X → Y , W ⊂ X e Z ⊂ Y definem-se as
• imagem de W por f :
f(W ) = {f(x) : x ∈W}
• imagem inversa de Z por f :
f−1(Z) = {x ∈ X : f(x) ∈ Z}
Exemplo 2.2.3 :
f : N→ N, f(n) = n2 + n+ 1
e´ uma func¸a˜o injectiva mas na˜o sobrejectiva.
De facto,
f(n) = f(m)⇔ n2 + n = m2 +m⇔ n2 −m2 = m− n
⇔ (n−m)(n+m) = m− n⇔ n+m = −1 ∨ n = m
Ora a primeira igualdade e´ imposs´ıvel porque n,m sa˜o naturais.
Por outro lado, n2 + n+ 1 e´ sempre ı´mpar, pelo que f na˜o e´ sobrejectiva.
Exemplo 2.2.4 : d : N → N definida por d(n) ser o nu´mero de divisores naturais de n, e´ uma func¸a˜o
sobrejectiva mas na˜o injectiva.
10 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
2.3 Relac¸o˜es
Um subconjunto R ⊂ X × Y designa-se uma relac¸a˜o entre X e Y . Encontraremos diversos tipos especiais
de relac¸a˜o particularmente importantes, como as relac¸o˜es de ordem ou de equivaleˆncia, definidas mais a`
frente.
E´ usual escolher um s´ımbolo (por exemplo on) para representar a relac¸a˜o e usa-se enta˜o a notac¸a˜o x on y para
significar que x ∈ X e y ∈ Y esta˜o na relac¸a˜o, ou seja (x, y) ∈ R. Quando Y = X dizemos abreviadamente
que temos uma relac¸a˜o em X (e na˜o entre X e X).
Uma func¸a˜o f : X → Y na˜o e´ mais do que uma relac¸a˜o (chamemos-lhe f) entre X e Y , com a propriedade
de ser un´ıvoca:
∀x ∈ X,∃1 ∈ Y : (x, y) ∈ f,
onde o s´ımbolo ∃1 significa “existe um e um so´”.
Naturalmente, usamos a notac¸a˜o habitual f(x) = y em vez de (x, y) ∈ f .
Observac¸a˜o 2.3.1 Aproveitamos esta clarificac¸a˜o do conceito de func¸a˜o para esclarecer um detalhe lo´gico:
Quantas func¸o˜es f : ∅ → ∅ existem?
A definic¸a˜o, dada no para´grafo anterior, de func¸a˜o como uma relac¸a˜o un´ıvoca permite compreender porque
e´ que a resposta e´ 1:
Existe uma u´nica relac¸a˜o definida no conjunto vazio ja´ que ∅ e´ o u´nico subconjunto de ∅ × ∅. E esta
relac¸a˜o satisfaz (trivialmente) aquela condic¸a˜o: se na˜o, existiria algum x ∈ ∅ para o qual a condic¸a˜o na˜o era
satisfeita...
O mesmo racioc´ınio mostra que, para qualquer conjunto A, existe uma u´nica func¸a˜o f : ∅ → A.
Por outro lado, se A 6= ∅, na˜o existe nenhuma func¸a˜o f : A→ ∅.
Definic¸a˜o 2.3.2 Uma relac¸a˜o R num conjunto X e´
• reflexiva se xRx ∀x ∈ X
• sime´trica se xRy ⇒ yRx
• anti-sime´trica se xRy ∧ yRx⇒ x = y
• transitiva se xRy ∧ yRz ⇒ xRz
Definic¸a˜o 2.3.3 • Uma relac¸a˜o reflexiva, transitiva e anti-sime´trica chama-se uma relac¸a˜o de ordem
(parcial);
• Uma relac¸a˜o reflexiva, transitiva e sime´trica chama-se uma relac¸a˜o de equivaleˆncia;
Exemplo 2.3.4 : A relac¸a˜o de inclusa˜o ⊂ definida em P(X ), para qualquer conjunto X, e´ uma relac¸a˜o de
ordem parcial.
2.4. NU´MEROS NATURAIS: AXIOMAS 11
Exemplo 2.3.5 : Dado um conjunto de conjuntos C, podemos definir uma relac¸a˜o ∼ por
X ∼ Y ⇔ ∃f : X → Y bijectiva
Como se verifica facilmente, ∼ e´ uma relac¸a˜o de equivaleˆncia.
De uma relac¸a˜o de equivaleˆncia R num conjunto X resulta uma decomposic¸a˜o de X numa unia˜o de
subconjuntos, disjuntos dois a dois, que se chamam as classes de equivaleˆncia da relac¸a˜o; cada uma
dessas classes de equivaleˆncia e´ um subconjunto (na˜o vazio) de X cujos elementos esta˜o em relac¸a˜o entre
si. As propriedades reflexiva, sime´trica e transitiva de R garantem que esta definic¸a˜o e´ coerente e que esses
subconjuntos sa˜o de facto disjuntos dois a dois.
2.4 Nu´meros Naturais: Axiomas
Designamos por N = {1, 2, 3, . . . , n, . . .} o conjunto dos nu´meros naturais. N satisfaz os seguintes axiomas.
Dados a, b, c ∈ N:
1. Esta´ definida uma operac¸a˜o de soma a+ b ∈ N.
2. Esta´ definida uma operac¸a˜o de produto a× b = a.b = ab ∈ N.
3. a+ b = b+ a.
4. (a+ b) + c = a+ (b+ c) .
5. ab = ba.
6. (ab) c = a (bc) .
7. ∃1 ∈ N : n1 = n, ∀n ∈ N.
8. ac =bc =⇒ a = b.
9. a (b+ c) = ab+ ac.
Definic¸a˜o 2.4.1 a < b ⇐⇒ ∃n ∈ N : a+ n = b.
Usamos a notac¸a˜o a ≤ b com o significado a < b ∨ a = b.
A relac¸a˜o ≤ e´ evidentemente uma relac¸a˜o de ordem mas satisfaz ale´m disso uma outra condic¸a˜o, que e´
mais um dos axiomas de N:
12 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
10. Se a, b ∈ N enta˜o verifica-se uma e uma so´ das condic¸o˜es
a < b, b < a, a = b.
Ale´m disso,
a ≤ b ∧ b ≤ a =⇒ a = b
Uma relac¸a˜o de ordem com esta propriedade chama-se uma relac¸a˜o de ordem total.
Temos finalmente um outro axioma:
11. (Boa Ordenac¸a˜o): Se X ⊆ N, X 6= ∅, enta˜o X tem um primeiro elemento, isto e´
∃x0 ∈ X : x0 ≤ x,∀x ∈ X.
Note-se que, por exemplo, o conjunto dos racionais positivos satisfaz os axiomas 1−10 mas na˜o o axioma
11.
Os axiomas 1−11 caracterizam completamente o conjunto dos naturais, isto e´, qualquer conjunto munido
de duas operac¸o˜es satisfazendo as propriedades contidas naqueles axiomas, e´ de facto uma “co´pia” de N com
as operac¸o˜es de soma e produto.
2.4.1 Nu´meros Inteiros
Ainda que os nu´meros naturais sejam suficientes quando se trata de contar os elementos de um conjunto, a
necessidade de comparar nu´meros entre si e de realizar e compreender com clareza as operac¸o˜es aritme´ticas,
conduz naturalmente a` introduc¸a˜o do conjunto dos nu´meros inteiros
Z = {· · · ,−n, · · · ,−1, 0, 1, · · · , n, · · · }
Z satisfaz os axiomas 1-10, desde que no axioma 8. se imponha c 6= 0 e fica completamente caracterizado
se estabelecermos ale´m disso que
• 0 + a = a, ∀a ∈ Z
• ∀a ∈ Z,∃1(−a) ∈ Z : a+ (−a) = 0
• ∀a ∈ Z, a ∈ N ∨ −a ∈ N
Evidentemente, Z na˜o satisfaz o axioma 11 (Princ´ıpio da Boa Ordenac¸a˜o). Mas para qualquer a ∈ Z, o
conjunto {n ∈ Z : n ≥ a} ja´ tem essa propriedade.
Os axiomas dos inteiros teˆm como consequeˆncia todas as propriedades bem conhecidas de que destacamos
as seguintes
1. 0 · a = 0, ∀a ∈ Z
2. ab = 0 =⇒ a = 0 ∨ b = 0
2.4. NU´MEROS NATURAIS: AXIOMAS 13
3. (−a)(−b) = ab
O estudo mais aprofundado da aritme´tica dos inteiros sera´ iniciado mais adiante.
Notac¸a˜o 2.4.2 N0 = {0} ∪ N e´ o conjunto dos inteiros na˜o negativos e
[m] = {x ∈ N0 : x < m} = {0, · · · ,m− 1}
Com esta notac¸a˜o [0] = ∅.
Observac¸a˜o 2.4.3 Em vez de o definirmos de forma axioma´tica, o conjunto Z pode ser constru´ıdo a partir
do conjunto dos naturais da seguinte forma:
Considere-se o conjunto N×N dos pares ordenados de nu´meros naturais, onde definimos a relac¸a˜o R seguinte:
(a, b)R(c, d)⇔ a+ d = b+ c.
Chamemos conjunto dos inteiros ao conjunto das classes de equivaleˆncia de R. Portanto, de acordo com
esta definic¸a˜o, um inteiro pode ser representado por um par (a, b) ∈ N×N, mas tambe´m por qualquer outro
par (c, d) tal que (a, b)R(c, d).
Esta definic¸a˜o, aparentemente artificial, ganha sentido quando pensamos, como se referiu acima, nos inteiros
como o resultado de comparar naturais: o par (a, b) corresponde ao inteiro (no sentido habitual) b−a. Note-
se que esta operac¸a˜o de subtracc¸a˜o, na˜o esta´ bem definida para quaisquer a, b ∈ N, mas apenas quando a < b.
Assim, a relac¸a˜o de equivaleˆncia R limita-se a exprimir, na linguagem dos naturais, que b− a = d− c e que
portanto ambos os pares (a, b) e (c, d) definem a mesma diferenc¸a de naturais.
Um par (a, b) representa um natural se a < b; o inteiro 0 e´ representado por qualquer par da forma (a, a); o
sime´trico do inteiro representado por (a, b) e´ representado por (b, a).
Resta verificar como se devem definir as operac¸o˜es de soma e produto e a relac¸a˜o de ordem, o que se torna
claro se seguimos a interpretac¸a˜o feita de identificar (a, b) com b− a:
(a, b) + (c, d) = (a+ c, b+ d)
ja´ que
(b− a) + (d− c) = (b+ d)− (a+ c).
Do mesmo modo, como
(b− a)(d− c) = bd+ ac− bc− ad = (bd+ ac)− (ad+ bc),
definimos o produto
(a, b) · (c, d) = (ad+ bc, bd+ ac)
onde as somas e produtos em cada entrada do par ordenado sa˜o as ja´ definidas para os naturais.
E, seguindo a mesma ideia,
(a, b) < (c, d)⇔ b+ c < a+ d.
O passo final, mas fundamental, desta construc¸a˜o reside em verificar que a definic¸a˜o das operac¸o˜es e da
relac¸a˜o de ordem na˜o dependem dos representantes escolhidos: temos de facto que recordar que nesta con-
struc¸a˜o um inteiro na˜o e´ um par de naturais mas sim uma classe de equivaleˆncia desses pares. E´ necessa´rio
portanto garantir que se
(a, b)R(a′, b′), (c, d)R(c′, d′)
14 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
se obte´m o mesmo inteiro na soma (a, b) + (c, d) que na soma (a′, b′) + (c′, d′), e o mesmo para o produto
ou para a relac¸a˜o de ordem. Fazemos essa verificac¸a˜o para a soma, deixando as outras como um exerc´ıcio.
Dizer que estas duas somas representam o mesmo inteiro e´ o mesmo que dizer que
((a, b) + (c, d))R((a′, b′) + (c′, d′));
mas, de acordo com a definic¸a˜o de soma a que chega´mos anteriormente, isso equivale a
(a+ c, b+ d)R(a′ + c′, b′ + d′)
ou seja
a+ c+ b′ + d′ = b+ d+ a′ + c′;
ora, como por hipo´tese
(a, b)R(a′, b′), (c, d)R(c′, d′),
temos
a+ b′ = b+ a′ c+ d′ = d+ c′
e a igualdade anterior resulta consequeˆncia das propriedades da soma de naturais.
Um racioc´ınio semelhante permite construir o conjunto dos racionais e as suas propriedades, a partir de
Z. Encontraremos mais adiante uma outra situac¸a˜o em que definimos operac¸o˜es entre classes de equivaleˆncia
a partir de operac¸o˜es nos inteiros.
2.4.2 Conjuntos finitos e infinitos
Os nu´meros naturais sa˜o o resultado da abstracc¸a˜o, desenvolvida pela humanidade ao longo de se´culos,
do acto de contar. Mais precisamente, o acto de contar, como quando conto os livros que tenho numa
prateleira, 1, 2, 3, ...,, comec¸ando, por exemplo, da esquerda para a direita, corresponde a estabelecer uma
certa bijecc¸a˜o entre dois conjuntos: o conjunto dos livros na prateleira e um certo conjunto de nu´meros. Os
nu´meros vieram assim substituir outros conjuntos (os dedos das ma˜os, os no´s numa corda...) como conjunto
padra˜o de contagem.
Definic¸a˜o 2.4.4 Um conjunto X diz-se finito se existe m ∈ N0 e uma bijecc¸a˜o
f : [m]→ X
Diz-se enta˜o que X tem m elementos ou que a cardinalidade de X e´ m, usando-se a notac¸a˜o |X| = m. Um
conjunto X diz-se infinito se na˜o for finito.
Pode-se formular estas definic¸o˜es de outros modos; o teorema seguinte ilustra esse facto.
Teorema 2.4.5 Dado um conjunto X, as seguintes afirmac¸o˜es sa˜o equivalentes:
i) X e´ infinito;
2.4. NU´MEROS NATURAIS: AXIOMAS 15
ii) Existe uma func¸a˜o f : N→ X injectiva;
iii) Existe uma func¸a˜o g : X → X injectiva e na˜o sobrejectiva.
Demonstrac¸a˜o 2.4.6 Note-se que o conjunto N satisfaz a condic¸a˜o iii): basta tomar
g : N→ N, f(n) = 2n.
Se um conjunto X satisfaz a condic¸a˜o ii), ou seja, existe f : N→ X injectiva, podemos definir g : X → X
do seguinte modo
g(x) =
 x se x /∈ f(N)
f(2n) se x = f(n)
que se verifica facilmente ser injectiva mas na˜o sobrejectiva.
Portanto ii) =⇒ iii).
Por outro lado se X satisfaz a condic¸a˜o iii) na˜o pode ser finito; vamos provar isso por absurdo, supondo
que existe algum conjunto finito que satisfaz iii); como um conjunto finito esta´ em bjecc¸a˜o com {1, · · · ,m}
para algum m, isso equivale a supoˆr que existe algum natural n e uma func¸a˜o f : {1, · · · , n} → {1, · · · , n}
injectiva mas na˜o sobrejectiva; ora, se isso fosse verdade, existiria, pelo Princ´ıpio da Boa Ordenac¸a˜o, um
primeiro natural, chamemos-lhe c, com essa propriedade. Vamos chegar a um absurdo mostrando que, pelo
contra´rio, c− 1 tambe´m teria que satisfazer iii). Note-se que se existisse, ter-se-ia de certeza c > 1.
Seja enta˜o
f : {1, · · · , c} → {1, · · · , c}
uma func¸a˜o injectiva mas na˜o sobrejectiva; ha´ treˆs casos poss´ıveis:
Se c na˜o pertence a` imagem de f , chamemos f ′ a` restric¸a˜o de f a {1, · · · , c − 1}; f ′ tem imagemcontida em {1, · · · , c− 1}, e´ injectiva e, como supomos que f e´ injectiva, f(c) /∈ f ′({1, · · · , c− 1}). Ou
seja,
f ′ : {1, · · · , c− 1} → {1, · · · , c− 1}
e´ injectiva e na˜o sobrejectiva.
Se f(c) = c, a mesma restric¸a˜o f ′ do caso anterior da´-nos uma func¸a˜o de {1, · · · , c− 1} nele pro´prio,
injectiva e na˜o sobrejectiva.
Finalmente, suponhamos que existem 1 ≤ a, b < c tais que f(a) = c e f(c) = b; nesse caso podemos
modificar a func¸a˜o trocando estas duas imagens, ou seja, definimos
g : {1, · · · , c} → {1, · · · , c}, g(x) =

x se x /∈ {a, c}
b se x = a
c se x = c
e ca´ımos no caso anterior.
Para completar a demonstrac¸a˜o do teorema, tem que se provar que i) =⇒ ii), o que se faz definindo
recursivamente os valores de uma func¸a˜o f : N → X: se X e´ infinito enta˜o certamente na˜o e´ vazio e
podemos escolher um elemento f(1); como X 6= {f(1)} (caso contra´rio seria finito), podemos escolher
f(2) ∈ X \ {f(1)}; e em geral, para qualquer m ∈ N, depois de escolhidos f(1), · · · , f(m), podemos escolher
16 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
f(m + 1) ∈ X \ {f(1), · · · , f(m)}. A func¸a˜o f assim definida e´ sem du´vida injectiva. Que este argumento
garante de facto que temos uma func¸a˜o definida em N decorre do Princ´ıpio da Boa Ordenac¸a˜o ( se f na˜o
ficasse definida para todo o n ∈ N, haveria um primeiro natural para o qual na˜o estava definida e chegar´ıamos
a uma contradic¸a˜o).
Estes argumentos devem ser revistos depois de estudado mais a` frente o Princ´ıpio de Induc¸a˜o Finita.
A generalizac¸a˜o da definic¸a˜o de conjunto finito leva ao conceito geral de cardinalidade: dizemos que dois
conjuntos X e Y teˆm a mesma cardinalidade se existe uma bijecc¸a˜o f : X → Y e que X tem cardinalidade
menor ou igual a` de Y se existe f : X → Y injectiva. Note-se que, para que seja poss´ıvel comparar de modo
coerente as cardinalidades de diferentes conjuntos, e´ necessa´rio demonstrar que se existem
f : X → Y, g : Y → X
ambas injectivas, enta˜o X e Y teˆm a mesma cardinalidade; este resultado, que na˜o se demonstra nestas
notas, e´ o Teorema de Cantor-Bernstein.
2.5 Princ´ıpio de Induc¸a˜o Finita
Uma consequeˆncia importante do princ´ıpio da boa ordenac¸a˜o e´ o seguinte
Teorema 2.5.1 Se X ⊂ N0 satisfaz as condic¸o˜es
(i) : k0 ∈ X,
(ii) : k ≥ k0, k ∈ X =⇒ k + 1 ∈ X,
enta˜o
X ⊃ N0 \ [k0] .
Demonstrac¸a˜o 2.5.2 De facto, se o conjunto Y = {x ∈ N0|x ≥ k0 ∧ x /∈ X} na˜o for vazio, tem que ter,
pelo Princ´ıpio da Boa Ordenac¸a˜o, um primeiro elemento, chamemos-lhe a. Como k0 ∈ X, tem-se k0 < a e
portanto k0 ≤ a− 1; por outro lado a− 1 ∈ X uma vez que a e´ o primeiro elemento do conjunto Y definido
atra´s.
Mas a condic¸a˜o ii) do teorema implica enta˜o que a ∈ X, uma contradic¸a˜o. Esta contradic¸a˜o decorre de
supormos que Y 6= ∅.
O teorema anterior e´ de facto logicamente equivalente ao Princ´ıpio da Boa Ordenac¸a˜o, e e´ um bom
exerc´ıcio demonstrar este u´ltimo, assumindo a validade do teorema anterior.
Este teorema e´ frequentemente usado da seguinte forma:
2.5. PRINCI´PIO DE INDUC¸A˜O FINITA 17
2.5.3 Princ´ıpio de Induc¸a˜o Finita: Se P (n) e´ uma dada afirmac¸a˜o referente aos nu´meros naturais n ∈ N0
tal que :
i: P (k0) e´ verdadeira;
ii: se k ≥ k0 e P (k) e´ verdadeira enta˜o P (k + 1) e´ verdadeira;
enta˜o P (n) e´ verdadeira para qualquer n ≥ k0.
Exemplo 2.5.4 Ilustramos a aplicac¸a˜o do Princ´ıpio de Induc¸a˜o Finita atrave´s de um exemplo simples:
provar por induc¸a˜o que a igualdade
n∑
k=1
k =
n(n+ 1)
2
se verifica para todo o n ≥ 1.
Comec¸amos por verificar que a igualdade se verifica para n = 1, o que e´ imediato.
Em seguida mostramos que, se a igualdade se verificar para um certo natural n enta˜o tambe´m se verifica
para n+ 1: de facto, se
n∑
k=1
k =
n(n+ 1)
2
enta˜o
n+1∑
k=1
k =
(
n∑
k=1
k
)
+ (n+ 1) =
=
n(n+ 1)
2
+ n+ 1) =
n(n+ 1) + 2(n+ 1)
2
=
(n+ 1)(n+ 2)
2
ou seja a igualdade e´ igualmente va´lida para n+1 como quer´ıamos mostrar. O passo essencial na deduc¸a˜o
feita esta´ na segunda igualdade, onde usamos a hipo´tese de que a igualdade se verifica para n para substituir
o somato´rio
∑n
k=1 k por
n(n+1)
2 .
Exemplo 2.5.5 Dado r 6= 1, provar por induc¸a˜o a fo´rmula para a soma dos termos de uma progressa˜o
geome´trica com primeiro termo 1 e raza˜o r:
1 + r + r2 + · · ·+ rn =
n∑
k=0
rk =
1− rn+1
1− r ∀n ≥ 0
Mais uma vez, a igualdade e´ obviamente verdadeira para n = 0; de modo semelhante ao do exemplo anterior,
se a fo´rmula e´ verdadeira para um natural n enta˜o, para n+ 1 temos
n+1∑
k=0
rk =
n∑
k=0
rk + rn+1 =
1− rn+1
1− r + r
n+1 =
1− rn+1 + (1− r)rn+1
1− r =
1− rn+2
1− r
ou seja, a fo´rmula verifica-se tambe´m para n+ 1.
18 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
Ainda como um terceiro exemplo (que tem a particularidade de ter sido a primeira exposic¸a˜o escrita,
pelo matema´tico franceˆs Pascal, da aplicac¸a˜o do Princ´ıpio de Induc¸a˜o Finita), provamos a chamada:
Proposic¸a˜o 2.5.6 Fo´rmula do Bino´mio
∀a, b ∈ R, ∀n ∈ N0(a+ b)n =
n∑
k=0
(
n
k
)
akbn−k
onde (
n
k
)
=
n!
k!(n− k)!
e n! = 1× 2× 3× · · · × n ou mais precisamente n! = Πnj=1j (por convenc¸a˜o 0! = 1).
Demonstrac¸a˜o 2.5.7 Para simplificar a nossa deduc¸a˜o, conve´m alargar a definic¸a˜o dos nu´meros binomiais(
n
k
)
a todos os valores inteiros de k:
(
n
k
)
=

n!
k!(n− k)! se 0 ≤ k ≤ n
0 se k < 0 ∨ n < k
Esta generalizac¸a˜o permite reescrever a fo´rmula como
(a+ b)n =
∑
k
(
n
k
)
akbn−k
onde o s´ımbolo
∑
k significa que o ı´ndice k toma todos os valores inteiros: esta soma de “um nu´mero infinito”
de termos e´ definida como a soma dos termos na˜o nulos.
Mais uma vez os casos n = 0 ou n = 1 sa˜o de verificac¸a˜o imediata; a demonstrac¸a˜o de que a validade da
fo´rmula para um certo n implica a sua validade para n+ 1 e´ um pouco mais complicada que a dos exemplos
anteriores e faz-se do seguinte modo: supondo enta˜o que
(a+ b)n =
∑
k
(
n
k
)
akbn−k
temos
(a+ b)n+1 = (a+ b)(a+ b)n = (a+ b)
∑
k
(
n
k
)
akbn−k =
∑
k
(
n
k
)
ak+1bn−k +
∑
k
(
n
k
)
akbn+1−k =
fazendo j = k + 1 no primeiro somato´rio,
=
∑
j
(
n
j − 1
)
ajbn+1−j +
∑
k
(
n
k
)
akbn+1−k =
2.5. PRINCI´PIO DE INDUC¸A˜O FINITA 19
designando de novo por k o ı´ndice do primeiro somato´rio,
=
∑
k
(
n
k − 1
)
akbn+1−k +
∑
k
(
n
k
)
akbn+1−k =
∑
k
((
n
k − 1
)
+
(
n
k
))
akbn+1−k =
∑
k
(
n+ 1
k
)
akbn+1−k
onde a u´ltima igualdade e´ justificada por(
n
k − 1
)
+
(
n
k
)
=
n!
(k − 1)!(n− (k − 1))! +
n!
k!(n− k)! =
n!k
k!(n+ 1− k)! +
n!(n+ 1− k)
k!(n+ 1− k)! =
(n+ 1)!
k!(n+ 1− k)!
que e´ a conhecida propriedade do triaˆngulo de Pascal (fica so´ por comprovar a igualdade nos casos k < 1 e
k > n, o que e´ simples).
Observac¸a˜o 2.5.8 os exemplos anteriores, ale´m de servirem de ilustrac¸a˜o da aplicac¸a˜o do Princ´ıpio de
Induc¸a˜o Finita, sa˜o importantes pelos resultados em si, que sa˜o igualdades, principalmente as duas u´ltimas,
que devem ser conhecidas.
Antes de dar outro exemplo conve´m desde ja´ fazer algumas observac¸o˜es:
• E´ muito natural perguntar “de onde vem” a fo´rmula que e´ enunciada para provar. Ou seja, aparente-
mente, para provar uma certa proposic¸a˜o atrave´s do Princ´ıpio de Induc¸a˜o Finita, e´ preciso saber ja´ o
que se vai provar.
Em muitos casos o resultado a provar e´ sugerido por ca´lculos em casos particulares ou por um racioc´ınio
menos rigoroso. O Princ´ıpio de Induc¸a˜o Finita serve enta˜o para comprovar a conjectura formulada.
Mas e´ verdade que muitos dos resultadosque provamos por aplicac¸a˜o do Princ´ıpio de Induc¸a˜o Finita
podem ser provados com outras abordagens. Um exemplo disso e´ a deduc¸a˜o da igualdade do primeiro
exemplo apresentada num exerc´ıcio.
• O Princ´ıpio de Induc¸a˜o Finita e´ por vezes mal entendido como um mero artif´ıcio formal; a necessidade
de provar
P (k) e´ verdadeira =⇒ P (k + 1) e´ verdadeira
para finalmente concluir que P (k) e´ verdadeira (para todo o k ≥ k0, claro) pode criar a ideia errada
de que estamos a admitir antecipadamente o resultado que queremos provar.
Na verdade, o que se prova naquele passo e´ a implicac¸a˜o. Como se sabe, o facto de uma implicac¸a˜o
a =⇒ b entre duas proposic¸o˜es ser verdadeira significa apenas que se a for verdadeira enta˜o b e´
verdadeira: formalmente o valor lo´gico de a =⇒ b e´ o mesmo de (¬a)∨ b, onde ¬ significa negac¸a˜o, e
esta proposic¸a˜o so´ e´ falsa se a for verdadeira e b falsa.
E´ por isso que a prova da implicac¸a˜o tem que ser acompanhada pela verificac¸a˜o de que P (k0) e´
verdadeira. Uma boa maneira de compreender isso e´ atrave´s do seguinte exemplo: suponhamos que,
devido a uma gralha, o primeiro exemplo acima e´ enunciado assim: provar por induc¸a˜o que
n∑
k=1
k =
n2 + n+ 1
2
∀n ≥ 1;
20 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
se assumirmos que a igualdade e´ verdadeira para um certo n enta˜o temos, para n+ 1.
n+1∑
k=1
k =
n∑
k=1
k + (n+ 1) =
=
n2 + n+ 1
2
+ (n+ 1) =
n2 + n+ 1 + 2(n+ 1)
2
=
=
n2 + 3n+ 3
2
=
(n2 + 2n+ 1) + n+ 2
2
=
(n+ 1)2 + (n+ 1) + 1
2
;
prova´mos portanto que se a igualdade se verifica para n tambe´m se verifica para n + 1, ou seja,
verifica´mos a segunda condic¸a˜o para a aplicac¸a˜o do Princ´ıpio de Induc¸a˜o Finita. No entanto, aquela
igualdade e´ obviamente falsa.
Uma outra forma equivalente e por vezes de aplicac¸a˜o mais directa do Princ´ıpio de Induc¸a˜o Finita e´ a
seguinte:
2.5.9 Princ´ıpio de Induc¸a˜o Finita (”FORTE”):
Se P (n) e´ uma dada afirmac¸a˜o referente aos nu´meros naturais n ∈ N0 tal que :
i : P (k0) e´ verdadeira;
ii : k ≥ k0 e P (k0) , P (k0 + 1) , . . . , P (k) verdadeiras, implica que P (k + 1) e´ verdadeira;
enta˜o P (n) e´ verdadeira para qualquer n ≥ k0.
O argumento da demonstrc¸a˜o da equivaleˆncia dos dois resultados e´ resumidamente este: O Princ´ıpio de
Induc¸a˜o Finita (”FORTE”) implica o Princ´ıpio de Induc¸a˜o Finita, uma vez que se P (k) =⇒ P (k+1) enta˜o
tambe´m
P (k0) ∧ P (k0 + 1) ∧ · · · ∧ P (k) =⇒ P (k + 1);
portanto, se as condic¸o˜es do Princ´ıpio de Induc¸a˜o Finita esta˜o satisfeitas tambe´m as do Princ´ıpio de Induc¸a˜o
Finita (”FORTE”) o esta˜o.
Mas reciprocamente o Princ´ıpio de Induc¸a˜o Finita implica o Princ´ıpio de Induc¸a˜o Finita (“FORTE”): aplicar
este u´ltimo a P (k) e´ o mesmo que aplicar o Princ´ıpio de Induc¸a˜o Finita a Q(k)⇔ P (k0) ∧ · · · ∧ P (k).
Exemplo 2.5.10 Como aplicac¸a˜o desta forma do princ´ıpio considere-se o seguinte exemplo: seja xn a
sucessa˜o definida pela seguinte recorreˆncia
x0 = 0, x1 = 1; xn+1 = 2xn − xn−1 ∀n > 1
Calculando x2 = 2 , x3 = 3, somos naturalmente levados a conjecturar que se tem xn = n para todo o
n ≥ 0. Como o termo de ordem n + 1 e´ definido a` custa dos dois termos anteriores, e´ mais fa´cil fazer a
demonstrac¸a˜o atrave´s do Princ´ıpio de Induc¸a˜o Finita (”FORTE”): o caso n = 0 e´ estabelecido pela pro´pria
definic¸a˜o da sucessa˜o; supondo agora que xk = k para todo o k ≤ n, conclu´ımos facilmente que temos
xn+1 = 2xn − xn−1 = 2n− (n− 1) = n+ 1
2.6. EXERCI´CIOS 21
2.6 Exerc´ıcios
1. Verificar que os conjuntos
∅, {∅}, {{∅}}, {∅, {∅}}
sa˜o todos diferentes.
Resoluc¸a˜o: ∅ 6= {∅} uma vez que o segundo conjunto tem um elemento, o conjunto vazio ∅, enquanto
que o primeiro e´ o conjunto vazio e portanto na˜o tem elementos. O mesmo racioc´ınio mostra que cada um
dos outros conjuntos e´ diferente do conjunto vazio.
Deduz-se tambe´m que {∅} 6= {{∅}}, pois cada um dos conjuntos tem um so´ elemento e esses elementos sa˜o
diferentes. E do mesmo modo cada um destes conjuntos e´ diferente de {∅, {∅}}, ja´ que este u´ltimo conte´m
um elemento que na˜o esta´ em cada um deles.
2. Mostrar que para quaisquer conjuntos X, Y e Z
X ∩ (Y ∪ Z) = (X ∩ Y ) ∪ (X ∩ Z); X ∪ (Y ∩ Z) = (X ∪ Y ) ∩ (X ∪ Z).
Resoluc¸a˜o: Seja x ∈ X ∩ (Y ∪Z) e suponhamos que x /∈ (X ∩ Y ); como x ∈ X isso significa que x /∈ Y .
Mas x ∈ Y ∪Z logo tem que pertencer a (pelo menos) um dos conjuntos e portanto x ∈ Z, donde se conclui
que
x ∈ X ∩ Z ⊂ (X ∩ Y ∪ (X ∩ Z)
e
X ∩ (Y ∪ Z) ⊂ (X ∩ Y ) ∪ (X ∩ Z).
Por outro lado, se x ∈ X ∩ Y enta˜o x ∈ X e x ∈ Y ∪ Z, logo x ∈ X ∩ (Y ∪ Z). Se x ∈ X ∩ Z o racioc´ınio e´
ideˆntico e fica assim provada a outra inclusa˜o.
A segunda igualdade demonstra-se de modo semelhante.
3. Defina-se a diferenc¸a sime´trica de dois conjuntos como
AuB = A \B ∪B \A
Mostrar que
• (AuB)u C = Au (B u C)
• A ∩ (B u C) = (A ∩B)u (A ∩ C)
Resoluc¸a˜o: Podemos tomar A, B e C como subconjuntos de um conjunto U (basta, por exemplo, definir
U = A ∪B ∪ C). Define-se enta˜o Ac = U \A. Com essa notac¸a˜o
AuB = (A ∩Bc) ∪ (Ac ∩B);
Temos enta˜o, usando as chamadas leis de Morgan
(A ∩B)c = Ac ∪Bc, (A ∪B)c = Ac ∩Bc,
22 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
bem como o exerc´ıcio anterior,
(AuB)u C = [((A ∩Bc) ∪ (Ac ∩B)) ∩ Cc] ∪ [((A ∩Bc) ∪ (Ac ∩B))c ∩ C] =
= [(A ∩Bc ∩ Cc) ∪ (Ac ∩B ∩ Cc)] ∪ [(A ∩Bc)c ∩ (Ac ∩B)c ∩ C] =
= [(A ∩Bc ∩ Cc) ∪ (Ac ∩B ∩ Cc)] ∪ [(Ac ∪B) ∩ (A ∪Bc) ∩ C] =
= [(A ∩Bc ∩ Cc) ∪ (Ac ∩B ∩ Cc)] ∪ [(((Ac ∪B) ∩A) ∪ ((Ac ∪B) ∩Bc)) ∩ C] =
= [(A ∩Bc ∩ Cc) ∪ (Ac ∩B ∩ Cc)] ∪ [(B ∩A) ∪ (Ac ∩Bc)) ∩ C] =
= (A ∩Bc ∩ Cc) ∪ (Ac ∩B ∩ Cc) ∪ (A ∩B ∩ C) ∪ (Ac ∩Bc ∩ C)
Uma vez que a diferenc¸a sime´trica e´ obviamente comutativa, a expressa˜o no segundo lado da equac¸a˜o obte´m-
se da do lado esquerdo trocando A com C; mas essa troca na˜o altera a u´ltima expressa˜o a que chega´mos,
pelo que se conclui a igualdade do enunciado.
De modo semelhante,
A ∩ (B u C) = A ∩ ((B ∩ Cc) ∪ (Bc ∩ C)) = (A ∩B ∩ Cc) ∪ (A ∩Bc ∩ C),
enquanto que
(A ∩B)u (A ∩ C) = ((A ∩B) ∩ (A ∩ C)c) ∪ ((A ∩B)c ∩ (A ∩ C)) =
= ((A ∩B) ∩ (Ac ∪ Cc)) ∪ ((Ac ∪Bc) ∩ (A ∩ C)) =
= (A ∩B ∩ Cc) ∪ (Bc ∩A ∩ C)
4. Quantas func¸o˜es f : ∅ → ∅ existem?
Resoluc¸a˜o: Para se compreender porque e´ que a resposta e´ 1, temos que recordar que uma func¸a˜o
f : X → Y e´ uma relac¸a˜o entre X e Y (ou seja, um subconjunto R ⊂ X × Y ) satisfazendo a condic¸a˜o
∀x ∈ X,∀y, y′ ∈ Y, (x, y) ∈ R ∧ (x, y′) ∈ R =⇒ y = y′.
Existe uma u´nica relac¸a˜o definida no conjunto vazio ja´ que ∅ e´ o u´nico subconjunto de ∅ × ∅. E esta relac¸a˜o
satisfaz (trivialmente) aquela condic¸a˜o: se na˜o, existiria algum x ∈ ∅ para o qual a condic¸a˜o na˜o era satisfeita.
O mesmo racioc´ınio mostra que, para qualquer conjunto A, existe uma u´nica func¸a˜o f : ∅ → A.
Por outro lado, se A 6= ∅, na˜o existe nenhuma func¸a˜o f : A→ ∅.
5. Dado um conjunto X mostrar que
a) existe uma bijecc¸a˜o entre o conjunto P(X) dos subconjuntos de X e o conjunto {f : X → {0, 1}} das
func¸o˜es com domı´nio X e contradomı´nio {0, 1}.
b) na˜o existe uma func¸a˜o f : X → P(X) sobrejectiva.
Sugesta˜o: considerar o conjunto {x ∈ X|x /∈ f(X)} ∈ P(X).
Resoluc¸a˜o: a) Considere-se a func¸a˜o
ϕ : P(X)→ {f : X → {0, 1}}
2.6. EXERCI´CIOS 23
definida do seguinte modo: dado um subconjunto Y ⊂ X, ϕ(Y ) e´ a func¸a˜o fY : X → {0, 1} definida por
f(x) =
{
1 se x ∈ Y
0 se x /∈ Y .
ϕ e´ injectiva porque se Y e Z sa˜o dois subconjuntos de X diferentes, existe x ∈ Y \ Z ∪ Z \ Y ; suponhamos
que x ∈ Y \ Z (o outro caso e´ ideˆntico); enta˜o
fY (x) = 1 6= 0 = fZ(x)
e portanto ϕ(Y ) 6= ϕ(Z).
ϕ e´ tambe´m sobrejectiva pois, se f : X → {0, 1} e Y = f−1(1) = {x ∈ X : f(x) = 1}, temos obviamente
f = fY ou seja f = ϕ(Y ).
Note-se que se |X| = n, o conjunto {f : X → {0, 1}} pode ser identificado como conjunto das sequeˆncias de
comprimento n formadas por 0 e 1; e uma consequeˆncia imediata do resultado anterior e´ que nesse caso
|P(X)| = 2n.
b) se f : X → P(X) e´ sobrejectiva, o subconjunto {x ∈ X|x /∈ f(X)} tem que ser a imagem por f de
algum a ∈ X, ou seja f(a) = {x ∈ X|x /∈ f(X)}; podemos enta˜o perguntar se a ∈ {x ∈ X|x /∈ f(X)}. Se a
resposta for afirmativa enta˜o a ∈ f(a) mas isso e´ uma contradic¸a˜o com a pro´pria definic¸a˜o deste conjunto;
mas se a /∈ {x ∈ X|x /∈ f(X)} enta˜o isso significaria que a ∈ f(a) = {x ∈ X|x /∈ f(X)}, que e´ de novo uma
contradic¸a˜o!
Conclu´ımos que f na˜o pode ser sobrejectiva.
A conclusa˜o da al´ınea b) traduz-se intuitivamente na ideia de que para qualquer conjunto X, P(X) tem
“mais elementos” do que X. No caso de X ser finito, essa ideia e´ confirmada pela al´ınea anterior, ja´ que
n < 2n.
Esta ideia generaliza-se atrave´s do conceito, referido nas aulas, de cardinalidade.
6. Dada uma func¸a˜o f : X → Y e A,B ⊂ X, quais as relac¸o˜es entre f(A ∪B) e f(A) ∪ f(B)?
E entre f(A ∩B) e f(A) ∩ f(B)?
Resoluc¸a˜o: No primeiro caso tem-se igualdade:
y ∈ f(A ∪B)⇔ ∃x ∈ A ∪B : y = f(x)⇔ ∃x ∈ A : y = f(x) ∨ ∃x ∈ B : y = f(x)⇔
⇔ y ∈ f(A) ∨ y ∈ f(B)⇔ y ∈ f(A) ∪ f(B)
Ja´ no segundo caso temos apenas uma inclusa˜o:
y ∈ f(A ∩B) =⇒ y ∈ f(A) ∩ f(B)
mas a outra inclusa˜o na˜o se verifica em geral, mesmo que A ∩B 6= ∅: considere-se o exemplo
f : {a, b, c} → {0, 1}, f(a) = f(c) = 0, f(b) = 1
e os conjuntos
A = {a, b}, B = {b, c}.
24 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
7. Mostrar que, se {Ai : i ∈ N} e {Bi : i ∈ N} sa˜o famı´lias de conjuntos satisfazendo
Ai ⊃ Ai+1, Bi ⊃ Bi+1,∀i ∈ N
enta˜o ⋂
i∈N
(Ai ∪Bi) =
⋂
i∈N
Ai ∪
⋂
i∈N
Bi
Sem aquela condic¸a˜o esta igualdade verifica-se ou na˜o?
Resoluc¸a˜o: Vamos mais uma vez mostrar que se verificam as duas incluso˜es. A inclusa˜o ⊃ e´ o´bvia
e na˜o depende da condic¸a˜o no enunciado: se x ∈ ⋂i∈NAi enta˜o, para todo o i, x ∈ Ai ∪ Bi e portanto
x ∈ ⋂i∈N(Ai ∪Bi); se x ∈ ⋂i∈NBi o racioc´ınio e´ o mesmo.
Reciprocamente, seja x ∈ ⋂i∈N(Ai ∪ Bi); se x ∈ ⋂i∈NAi na˜o ha´ nada a demonstrar, portanto suponhamos
que x /∈ ⋂i∈NAi; isso significa que existe pelo menos um ı´ndice i tal que x /∈ Ai, e portanto, como Ai ⊃
Ai+1 ⊃ Ai+2 ⊃ · · · , temos que x /∈ Aj , para todo o j ≥ i; mas, tendo em conta a hipo´tese feita sobre x, isso
implica que x ∈ Bj para todo o j ≥ i e, como B1 ⊃ B2 ⊃ · · · ⊃ Bi, temos x ∈
⋂
i∈NBi.
Se a condic¸a˜o das incluso˜es na˜o se verificar, o resultado na˜o e´ va´lido em geral: basta pensar no exemplo
em que Ai = {0} para i ı´mpar e Ai = {1} para i par, enquanto que Bi = {1} para i ı´mpar e Bi = {0} para
i par. Tem-se nesse caso ⋂
i∈N
(Ai ∪Bi) = {0, 1},
⋂
i∈N
Ai ∪
⋂
i∈N
Bi = ∅.
8. Consegue provar por induc¸a˜o em n que
∀n ∈ N : 1
2
3
4
· · · 2n− 1
2n
=
n∏
k=1
2k − 1
2k
<
1√
3n
?
E se foˆr
∀n ∈ N : 1
2
3
4
· · · 2n− 1
2n
=
n∏
k=1
2k − 1
2k
<
1√
3n+ 1
?
Resoluc¸a˜o:Na primeira desigualdade, o caso n = 1 e´ de verificac¸a˜o imediata porque
1∏
k=1
2k − 1
2k
=
1
2
<
1√
3
;
para completarmos a demonstrac¸a˜o por induc¸a˜o, tomamos como hipo´tese que a desigualdade do enunciado
se verifica para um certo n e procuramos deduzir, a partir dessa hipo´tese, que ela tambe´m se verifica para
n+ 1. Ora
n+1∏
k=1
2k − 1
2k
=
(
n∏
k=1
2k − 1
2k
)
2(n+ 1)− 1
2(n+ 1)
;
por hipo´tese de induc¸a˜o, o produto do lado direito e´ majorado por 1√
3n
e portanto
n+1∏
k=1
2k − 1
2k
<
1√
3n
2(n+ 1)− 1
2(n+ 1)
=
1√
3n
2n+ 1
2(n+ 1)
;
2.6. EXERCI´CIOS 25
se provarmos que o lado direito desta desigualdade e´ majorado por 1√
3(n+1)
, completamos a demonstrac¸a˜o.
Mas e´ a´ı que surgem problemas:
1√
3n
2n+ 1
2(n+ 1)
≤ 1√
3(n+ 1)
⇔ (2n+ 1)
√
3(n+ 1) ≤ 2(n+ 1)
√
3n⇔ (2n+ 1)2(3n+ 3) ≤ 4(n+ 1)23n⇔
⇔ (4n2 + 4n+ 1)(n+ 1) ≤ 4(n2 + 2n+ 1)n⇔ 4n3 + 8n2 + 5n+ 1 ≤ 4n3 + 8n2 + 4n
e esta u´ltima desigualdade e´ obviamente falsa.
Ja´ se tentamos a mesma abordagem para a outra desigualdade, notamos que o caso n = 1 na˜o se verifica
(tem-se igualdade e na˜o desigualdade estrita); mas para n = 2 ja´ se tem a desigualdade:
1
2
3
4
=
3
8
<
1√
3× 2 + 1 =
1√
7
.
Se repetirmos o racioc´ınio feito anteriormente para provar o resultado por induc¸a˜o, somos conduzidos a
demonstrar a desigualdade
1√
3n+ 1
2n+ 1
2(n+ 1)
≤ 1√
3(n+ 1) + 1
que se verifica, seguindo ca´lculos ideˆnticos aos feitos acima, ser verdadeira. Portanto a segunda desigualdade
do enunciado verifica-se para todo o n ≥ 2.
O ponto interessante e´ que se conclui enta˜o que a primeira desigualdade tambe´m se verifica, uma vez que
obviamente
1√
3n+ 1
<
1√
3n
;
quer isto dizer que, embora na˜o consegu´ıssemos provar por induc¸a˜o uma desigualdade, ja´ o conseguimos
fazer para uma outra desigualdade mais “forte”, que implica a primeira.
Isto acontece porque, no passo de induc¸a˜o, podemos usar tambe´m a desigualdade mais “forte”.
9. Mostrar que, dados n quadrados, e´ poss´ıvel recorta´-los em pol´ıgonos de modo a formar com estes um
novo quadrado.
Sugesta˜o: O u´nico caso dif´ıcil e´ n = 2;
Resoluc¸a˜o: Se soubermos resolver o caso n = 2, podemos raciocinar por induc¸a˜o: suponhamos que
sabemos resolver o problema com n quadrados; dados n+ 1 quadrados, podemos formar um novo quadrado
com n deles e depois formar um quadrado a partir deste e do quadrado restante.
Suponhamos enta˜o que temos dois quadrados, um com lado a e o outro com lado b e seja a < b (o caso em
que a = b resolve-se por uma versa˜o simplificada deste procedimento). A ideia guia e´ que o quadrado final
tera´ que ter obrigatoriamente lado
√
a2 + b2.
Comec¸amos por cortar no quadrado de lado b um rectaˆngulo a× b e cortamo-lo ao longo de uma diagonal.
O rectaˆngulo restante (de medidas (b− a)× b) e´ cortado num quadrado (b− a)× (b− a) e num rectaˆngulo
(b−a)×a. Juntando este u´ltimo rectaˆngulo ao quadrado de lado a obtemos um novo rectaˆngulo com medidas
a× b que pode ser de novo cortado ao longo de uma diagonal.
Temos enta˜o pol´ıgonos que formam quatro triaˆngulos rectaˆngulos com um cateto de comprimento a e o outro
de comprimento b, e um quadrado (b − a) × (b − a). Os quatro triaˆngulos podem ser dispostos de modo a
que as suas hipotenusas sejam os lados de um quadrado, tendo no meio o espac¸o para o quadrado.
26 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
10. Demonstrar, por induc¸a˜o em n, que
∀n ∈ N (bi > 0 ∀i ≤ n ∧
n∏
i=1
bi = 1)⇒
n∑
i=1
bi ≥ n
Nota:
∏n
i=1 bi designa o produto dos bi, com 1 ≤ i ≤ n.
Sugesta˜o: Se bi = 1∀i, o resultado e´ evidente; caso contra´rio, notar que: i) se b1, b2, b3, · · · , bn+1 sa˜o n + 1
reais positivos tais que
∏n+1
i=1 bi, enta˜o b1b2, b3, · · · , bn+1 sa˜o n reais positivos cujo produto e´ 1; podemos
supoˆr que, por exemplo, b1 < 1 < b2; Mostrar que se 0 < a < 1 < b, enta˜o ab < a+ b− 1.
Resoluc¸a˜o: Se n = 1 na˜o ha´ nada a provar. Vamos enta˜o assumir como hipo´tese de induc¸a˜o que dados
quaisquer n reais positivos cujo produto e´ igual a 1, a sua soma e´ maior ou igual a n. Dados reais positivos
b1, b2, b3, · · · , bn+1
tais que
n+1∏
i=1
bi,
podemos supoˆr que na˜o todos iguais a 1 (caso contra´rio, o resultado e´ evidente) e portanto que se tem
b1 < 1 < b2. Enta˜o
0 < (b2 − 1)(1− b1) = b2 + b1 − 1− b1b2
ou seja, b1b2 < b2 + b1 − 1.
Ora,
b1b2, b3, · · · , bn+1
sa˜o n reais positivos cujo produto e´ 1 e portanto, pela hipo´tese de induc¸a˜o
b1b2 + b3 + · · ·+ bn+1 ≥ n;
usando a desigualdade anterior, obtemos
(b1 + b2 − 1) + b3 + · · ·+ bn+1 ≥ n⇔
n+1∑
i=1
bi ≥ n+ 1
como quer´ıamos mostrar.
11. Usar o resultado do problema anterior para demonstrar o seguinte: dados n nu´merosreais positivos
ai, 1 ≤ i ≤ n, verificam-se as desigualdades
n
1
a1
+ 1a2 + · · ·+ 1an
≤ n√a1a2 · · · an ≤ a1 + a2 + · · ·+ an
n
ou seja, usando a notac¸a˜o para somato´rios e produtos,
n∑n
i=1
1
ai
≤ n
√√√√ n∏
i=1
ai ≤
∑n
i=0 ai
n
2.6. EXERCI´CIOS 27
As fo´rmulas acima representam, respectivamente, as me´dias harmo´nica, geome´trica e aritme´tica dos nu´meros
ai, 1 ≤ i ≤ n, e estas desigualdades sa˜o u´teis em muitas ocasio˜es.
Resoluc¸a˜o: Aplicamos o exerc´ıcio anterior aos reais definidos por
bi =
ai
n
√∏n
i=1 ai
;
e´ evidente que
∏n
i=1 bi = 1 e portanto
∑n
i=1 bi ≥ n, ou seja, pondo em evideˆncia
1
n
√∏n
i=1 ai
,
n∑
i=1
ai ≥ n n
√√√√ n∏
i=1
ai
que e´ a desigualdade entre as me´dia aritme´tica e geome´trica. A outra desigualdade prova-se de modo
semelhante, substituindo os ai pelos seus inversos.
Nota: Estas desigualdades podem ser demonstradas sem o uso do resultado contido no exerc´ıcio anterior,
nomeadamente aplicando de outras maneiras o Princ´ıpio de Induc¸a˜o Finita.
28 CHAPTER 2. CONJUNTOS, FUNC¸O˜ES E RELAC¸O˜ES: NOC¸O˜ES BA´SICAS
Chapter 3
Elementos de Aritme´tica dos Inteiros
3.1 Lema da Divisa˜o e o Algoritmo de Euclides
Recorde-se que |a|, o mo´dulo ou valor absoluto de a, designa
|a| =
 a se a ∈ N−a se a /∈ N
Dados a, b, c ∈ Z denotamos por
a | b :
a divide b ou a e´ um divisor de b, a relac¸a˜o definida por
a | b ⇐⇒ ∃q ∈ Z : b = aq
Da definic¸a˜o decorrem imediatamente as seguintes propriedades:
1. a | b e b | c =⇒ a | c
2. a | b e a | c =⇒ a | (b+ c)
3. a | b =⇒ a | bs,∀s ∈ Z
4. a = bq + r, d | a, d | b =⇒ d | r
5. a | b⇔ |a| | |b|
29
30 CHAPTER 3. ELEMENTOS DE ARITME´TICA DOS INTEIROS
Lema 3.1.1 da Divisa˜o (inteira):
Dados b ∈ N e a ∈ Z, existem q, r ∈ Z u´nicos, tais que
a = bq + r e 0 ≤ r < b.
De facto, o resto r pode ser definido como o menor elemento do conjunto
{a− xb|x ∈ Z} ∩ N
e q e´ o maior inteiro menor ou igual a
a
b
;
Notac¸a˜o 3.1.2 (Knuth): q =
⌊a
b
⌋
Teorema 3.1.3 (Representac¸a˜o dos inteiros em bases):
Seja b um inteiro ≥ 2. Enta˜o qualquer inteiro positivo a pode ser representado na base b, isto e´, a pode
ser escrito de forma u´nica como
a = rnb
n + rn−1bn−1 + · · ·+ r2b2 + r1b+ r0
com 0 ≤ ri < b; i = 1, 2, . . . , n.
Notac¸a˜o 3.1.4 Escreve-se enta˜o a = (rnrn−1 . . . r2r1r0)b .
3.1.1 Ma´ximo Divisor Comum
Definic¸a˜o 3.1.5 Dados a, b ∈ Z, na˜o ambos nulos, diz-se que d e´ o ma´ximo divisor comum de a e b,
d = mdc (a, b) , se
(i) d > 0 ; (ii) d | a e d | b ; (iii) c | a e c | b =⇒ c | d.
Observac¸a˜o 3.1.6 • ∀a ∈ N : mdc (a, 0) = a;
• ∀a ∈ N : mdc (a, 1) = 1.
3.1. LEMA DA DIVISA˜O E O ALGORITMO DE EUCLIDES 31
Teorema 3.1.7 Dados a, b ∈ Z, na˜o ambos nulos, existe sempre o ma´ximo divisor comum de a e b.
Este facto pode ser estabelecido teoricamente e resolvido na pra´tica pelo
Algoritmo de Euclides para calcular mdc (a, b) ; a, b ∈ N, a ≥ b :
1 Enquanto b > 0,, calcular a = qb+ r com 0 ≤ r < b, substituir a por b e b por r;
2 Quando b = 0, a = mdc (a, b) .
Uma descric¸a˜o mais detalhada, incluindo a justificac¸a˜o de que este procedimento pa´ra num nu´mero finito
de passos, e´: Seja r−1 = a e r0 = b; definimos por recorreˆncia
rn−1 = qn+1rn + rn+1
com 0 ≤ rk+1 < rk para k ≥ 1.
rk e´ uma sucessa˜o estritamente decrescente de inteiros na˜o negativos e portanto existe m tal que rm+1 = 0;
isso implica que rm | rm−1 e, por um racioc´ınio anaa´logo ao do princ´ıpio de Induc¸a˜o Finita, deduzimos que
rm | rn para todo o n ≥ −1: se rm | rk para todo o k ≥ n, enta˜o como
rn−1 = qn+1rn + rn+1
tem que se ter rm | rn−1.
Portanto rm e´ um divisor comum de a e b; mas, por outro lado, se c | a e c | b, deduzimos da mesma forma
que c | rn para todo o n e portanto c | rm.
Conclu´ımos que rm = mdc(a, b).
Exemplo 3.1.8 seja a = r−1 = 5324 e b = r0 = 1023; obtemos sucessivamente
r−1 = 5324 = 5× 1023 + 209 = q1r0 + r1
r0 = 1023 = 4× 209 + 187 = q2r1 + r2
r1 = 209 = 1× 187 + 22 = q3r2 + r3
r2 = 187 = 8× 22 + 11 = q4r3 + r4
r3 = 22 = 2× 11 + 0 = q5r4 + r5
Observac¸a˜o 3.1.9 O algoritmo de Euclides pode ser visto como um caso especial da expansa˜o de um nu´mero
em fracc¸a˜o cont´ınua:
a
b
= q1 +
r1
b
= q1 +
r1
q2r1 + r2
=
q1 +
1
q2 +
r2
r1
= · · · = q1 + 1
q2 +
1
q3 +
1
. . . +
1
qm +
1
qm+1
32 CHAPTER 3. ELEMENTOS DE ARITME´TICA DOS INTEIROS
Corola´rio 3.1.10 Se d = mdc (a, b) , existem x, y ∈ Z :
xa+ yb = d.
Demonstrac¸a˜o 3.1.11 Os coeficientes x, y podem ser obtidos por um procedimento ana´logo ao da demon-
strac¸a˜o anterior; se d = rm, isso significa que
d = rm−2 − qmrm−1;
mas como rm−3 = qm−1rm−2 + rm−1
d = rm−2 − qm (rm−3 − qm−1rm−2) = −qmrm−3 + (1 + qmqm−1) rm−2
e assim por diante: se ja´ temos
d = srn + trn+1
e
rn−1 = qn+1rn + rn+1
enta˜o
d = srn + t (rn−1 − qn+1rn) = trn−1 + (s− tqn+1) rn
e continuando deste modo acabamos com uma equac¸a˜o
d = xa+ yb.
Observac¸a˜o 3.1.12 Como se verifica facilmente, o mdc (a, b) e´ o menor inteiro positivo que se pode escrever
como combinac¸a˜o inteira de a e b.
O ca´lculo dos coeficientes x e y do corola´rio anterior pode ser feito, com vantagem, procedendo de outro
modo: como, para todo o n > 0, se tem rn = rn−2 − qnrn−1, se ja´ tivermos
rn−2 = xn−2a+ yn−2b, e do mesmo modo rn−1 = xn−1a+ yn−1b
enta˜o obtemos igualmente uma combinac¸a˜o
rn = xna+ ynb = (xn−2 − qnxn−1)a+ (yn−2 − qnyn−1)b.
Podemos portanto ir calculando os coeficientes xk e yk ao mesmo tempo que calculamos os sucessivos rk e
qk e chegar ao fim da aplicac¸a˜o do algoritmo, obtendo como resultado final o mdc(a, b) e os coeficientes x e
y da equac¸a˜o.
A tabela seguinte descreve a aplicac¸a˜o do algoritmo de Euclides a a = 2163 e b = 910, com o ca´lculo
simultaˆneo dos xi e yi que satisfazem
ri = axi + byi :
3.1. LEMA DA DIVISA˜O E O ALGORITMO DE EUCLIDES 33
ri qi xi yi
2163 1 0
910 0 1
2163 = 2× 910 + 343 343 2 1 −2
910 = 2× 343 + 224 224 2 −2 5
343 = 1× 224 + 119 119 1 3 −7
224 = 1× 119 + 105 105 1 −5 12
119 = 1× 105 + 14 14 1 8 −19
105 = 7× 14 + 7 7 7 −61 145
14 = 2× 7 + 0
Estes ca´lculos podem tambe´m ser representados atrave´s do produto de matrizes: a equac¸a˜o acima pode
escrever-se como (
0 1
1 −qn
)(
xn−2 yn−2
xn−1 yn−1
)
=
(
xn−1 yn−1
xn yn
)
;
com a condic¸a˜o inicial
r−1 = 1× a+ 0× b = x−1a+ y−1b
e
r0 = 0× a+ 1× b = x0a+ y0b
temos que os coeficientes x e y pretendidos sa˜o os elementos da segunda linha da matriz(
0 1
1 −qm
)(
0 1
1 −qm−1
)
· · ·
(
0 1
1 −q2
)(
0 1
1 −q1
)
Definic¸a˜o 3.1.13 Dizemos que a e b sa˜o primos entre si se mdc(a, b) = 1.
Deduz-se portanto do resultado anterior que a e b sa˜o primos entre si se e so´ se existem inteiros x e y
tais que
xa+ yb = 1
Teorema 3.1.14 Se a, b, c ∈ Z,
mdc (a, c) = 1 e c | ab =⇒ c | b.
Demonstrac¸a˜o 3.1.15 De facto, como existem inteiros x, y tais que ax+ cy = 1, temos
abx+ cby = b
e como c divide as duas parcelas da esquerda tem tambe´m que dividir b.
34 CHAPTER 3. ELEMENTOS DE ARITME´TICA DOS INTEIROS
Proposic¸a˜o 3.1.16 Se mdc(a, b) = 1
a|c e b|c =⇒ (ab)|c
Demonstrac¸a˜o 3.1.17 Sabemos que existem inteiros u, v tais que au+bv = 1; por outro lado, c = ax = by.
Enta˜o,
byu = cu = aux = (1− bv)x
e portanto
x = b(yu+ vx) e c = ab(yu+ vx)
Mais geralmente,
Proposic¸a˜o 3.1.18 Se a1, a2, · · · , ak sa˜o primos dois a dois, ou seja
mdc(ai, aj) = 1 ∀ i 6= j
enta˜o
ai|c ∀ 1 ≤ i ≤ k =⇒ (
k∏
i=1
ai)|c
Demonstrac¸a˜o 3.1.19 Usamos induc¸a˜o: o caso k = 2 e´ o da proposic¸a˜o anterior; suponhamos enta˜o que a
implicac¸a˜o e´ verdadeira para k−1; enta˜o dados inteiros a1, a2, · · · , ak nas condic¸o˜es do enunciado, temos que
os k − 1 inteiros a1, a2, · · · , ak−1 tambe´msatisfazem essas condic¸o˜es e portanto, pela hipo´tese de induc¸a˜o,
(a1a2 · · · ak−1)|c; mas os dois inteiros a1a2 · · · ak−1 e ak sa˜o primos entre si e ambos dividem c; estamos
portanto nas condic¸o˜es do caso k = 2 e podemos concluir, pela proposic¸a˜o anterior, que
(a1 · · · ak)|c
Corola´rio 3.1.20 Se d = mdc (a, b) , a equac¸a˜o
ax+ by = c
tem soluc¸o˜es x, y ∈ Z se e so´ se d | c. Mais, se (x0, y0) e´ uma soluc¸a˜o desta equac¸a˜o, o conjunto de todas as
soluc¸o˜es e´ constitu´ıdo pelos pares de inteiros (x, y) da forma
x = x0 + k
b
d
; y = y0 − ka
d
; k ∈ Z.
3.1. LEMA DA DIVISA˜O E O ALGORITMO DE EUCLIDES 35
Demonstrac¸a˜o 3.1.21 A primeira parte do resultado e´ o´bvia: se d = as + bt e c = dm, enta˜o c =
a(ms) + b(mt); por outro lado, se c = ax+ by, enta˜o d | c.
Dada uma soluc¸a˜o c = ax0 + by0, e´ evidente que, para qualquer k ∈ Z, se tem tambe´m
c = a(x0 + k
b
d
) + b(y0 − ka
d
)
Suponhamos que c = az + bw; enta˜o
ax0 + by0 = az + bw ⇔ a(x0 − z) = b(w − y0)⇔ a
d
(x0 − z) = b
d
(w − y0)
Mas, como se verifica imediatamente a partir da definic¸a˜o de ma´ximo divisor comum, se mdc(a, b) = d
enta˜o mdc(
a
d
,
b
d
) = 1; logo, se
a
d
divide o produto
b
d
(w− y0), pelo Teorema anterior tem que dividir w− y0,
ou seja, existe um inteiro k tal que
w = y0 + k
a
d
.
Substituindo na equac¸a˜o anterior,
a
d
(x0 − z) = b
d
(w − y0) = b
d
k
a
d
e portanto
z = x0 − k b
d
como quer´ıamos provar.
Corola´rio 3.1.22 Se a, b1 , b2, · · · , bn sa˜o inteiros tais que
mdc(a, bi) = 1 ∀i
enta˜o mdc(a, b) = 1, onde b =
∏n
i=1 bi.
Demonstrac¸a˜o 3.1.23 Existem inteiros xi e yi (com 1 ≤ i ≤ n) tais que
axi + biyi = 1 ∀i
Multiplicando estas igualdades termo a termo obtemos
aX + bY = 1
onde Y = y1y2 · · · yn.
O conceito de ma´ximo divisor comum generaliza-se a mais de dois inteiros e prova-se (ver exerc´ıcios) que
mdc(a1, a2, · · · , an) = mdc(mdc(a1, a2, · · · , an−1), an)
e a partir desta igualdade conclui-se que se d = mdc(a1, a2, · · · , an), enta˜o existem inteiros xi tais que
d =
n∑
i=1
xiai
e que um inteiro c tem uma representac¸a˜o desta forma se e so´ se d | c.
36 CHAPTER 3. ELEMENTOS DE ARITME´TICA DOS INTEIROS
3.2 Nu´meros primos e o Teorema Fundamental da Aritme´tica
Definic¸a˜o 3.2.1 Um inteiro p > 1 diz-se primo se os seus u´nicos divisores positivos sa˜o 1 e o pro´prio p.
Deduz-se facilmente que qualquer inteiro n > 1 e´ divis´ıvel por algum primo. Ale´m disso, o u´ltimo
corola´rio da secc¸a˜o anterior tem como consequeˆncia a seguinte
Proposic¸a˜o 3.2.2 Dados a1, a2, . . . , an ∈ Z e p primo,
p | a1a2 . . . an =⇒ ∃i : p | ai.
Teorema 3.2.3 (Euclides) : O conjunto dos nu´meros primos e´ infinito.
Seja de facto p1, p2, · · · , pm um qualquer conjunto finito de primos (por exemplo, os primeiros m primos);
o nu´mero
N = p1p2 · · · pm + 1
ou e´ primo ou tem que ter um factor primo p; se p ∈ {p1, p2, · · · , pm} enta˜o p dividiria o produto p1p2 · · · pm
e enta˜o teria que dividir 1, o que e´ imposs´ıvel. Em qualquer caso verificamos que N tem um factor primo
diferente de qualquer um dos pi.
Teorema 3.2.4 Teorema Fundamental da Aritme´tica
Para cada inteiro n > 1, existem primos p1, p2, . . . , pr, tais que
n = p1p2 . . . pr
e essa factorizac¸a˜o e´ u´nica a menos de permutac¸a˜o dos factores.
Demonstrac¸a˜o 3.2.5 A demonstrac¸a˜o deste Teorema pode ser feita por uma aplicac¸a˜o do Princ´ıpio de
Induc¸a˜o Finita (Forte) e das propriedades deduzidas anteriormente:
n = 1 e´ o produto do conjunto vazio de primos (tal como a soma de um conjunto vazio de nu´meros e´ igual
a zero...) e n = 2 e´ primo; dado n > 2, suponhamos, como hipo´tese de induc¸a˜o, que todo o natural menor
que n tem uma factorizac¸a˜o u´nica em factores primos.
Se n e´ primo tem evidentemente uma factorizac¸a˜o u´nica; caso contra´rio, podemos factorizar n = n1n2 com
1 < n1, n2 < n; por hipo´tese de induc¸a˜o, n1 e n2 teˆm ambos factorizac¸a˜o u´nica
n1 = p1p2 · · · pm, n2 = p′1p′2 · · · p′l
3.2. NU´MEROS PRIMOS E O TEOREMA FUNDAMENTAL DA ARITME´TICA 37
e portanto n tem claramente uma factorizac¸a˜o em factores primos
n = p1p2 · · · pmp′1p′2 · · · p′l
Para vermos que essa factorizac¸a˜o e´ u´nica notamos que se
n = p1p2 · · · ps = q1q2 · · · qt
sa˜o duas factorizac¸o˜es em factores primos, enta˜o p1, por ser primo, divide forc¸osamente um dos factores
qi, que podemos supor, renumerando os factores, ser q1; mas como este e´ primo, os seus u´nicos divisores
(positivos) sa˜o 1 e q1 e portanto p1 = q1.
Cancelando esse factor obtemos
n
p1
= p2 · · · ps = q2 · · · qt
e como
n
p1
e´ menor que n, tem factorizac¸a˜o u´nica em factores primos, ou seja s = t e os qi coincidem com
os pi, a menos de uma permutac¸a˜o dos factores. Mas enta˜o o mesmo acontece com as factorizac¸o˜es de n.
Se designarmos por Pk a sucessa˜o crescente de todos os nu´meros primos, P1 = 2, P2 = 3, · · · , podemos
escrever a factorizac¸a˜o de n como
n =
∏
k≥1
P ikk
onde os expoentes ik satisfazem a condic¸a˜o de serem 0 excepto para um nu´mero finito de casos, com a
convenc¸a˜o de que o produto de um nu´mero infinito de 1 e´ 1 (a` semelhanc¸a do que se passa com a soma de
um nu´mero infinito de termos iguais a zero). Qualquer sucessa˜o ik que satisfac¸a as condic¸o˜es
ik ≥ 0∀k ≥ 1, ∃m : ik = 0∀k > m
corresponde a uma factorizac¸a˜o de um natural positivo e temos portanto uma bijecc¸a˜o entre o conjunto dos
naturais positivos e o conjunto das sucesso˜es que satisfazem aquelas condic¸o˜es, e o produto de dois naturais
corresponde, por essa bijecc¸a˜o, a` soma das sucesso˜es respectivas: se
n =
∏
k≥1
P ikk , m =
∏
k≥1
P jkk
enta˜o
nm =
∏
k≥1
P ik+jkk
A relac¸a˜o de divisibilidade n | m traduz-se em ik ≤ jk, ∀k e, do mesmo modo,
mdc(n,m) =
∏
k≥1
P
min{ik,jk}
k , mmc(n,m) =
∏
k≥1
P
max{ik,jk}
k
onde mmc(n,m) designa o menor mu´ltiplo comum dos dois naturais n e m.
Observac¸a˜o 3.2.6 O Teorema Fundamental da Aritme´tica pode parecer evidente, de tal modo as pro-
priedades dos nu´meros inteiros esta˜o enraizadas na nossa mente. O seu alcance, e a sua dependencia da
validade do Lema da Divisa˜o, sa˜o melhor compreendidos se estudarmos a aritme´tica de outros conjuntos.
Um bom exemplo e´ o dos nu´meros da forma
a+ b
√
10 a, b ∈ Z.
38 CHAPTER 3. ELEMENTOS DE ARITME´TICA DOS INTEIROS
3.2.1 Nu´meros perfeitos
O que se segue e´ um exemplo de aplicac¸a˜o das noc¸o˜es de divisibilidade e de factorizac¸a˜o em factores primos
a um problema cla´ssico da aritme´tica dos inteiros:
Um nu´mero natural n diz-se um nu´mero perfeito se igualar a soma dos seus divisores pro´prios
n =
∑
d|n∧1≤d<n
d
Por exemplo 6 e´ perfeito uma vez que 1 + 2 + 3 = 6, enquanto que 12 na˜o e´ perfeito ja´ que
1 + 2 + 3 + 4 + 6 = 16 6= 12
Uma formulac¸a˜o equivalente e´ que n e´ perfeito se
2n =
∑
d|n∧1≤d
d
A letra grega sigma e´ usada para designar esta func¸a˜o: σ(n) =
∑
d|n∧1≤d d.
Euclides demonstrou o seguinte
Teorema 3.2.7 Se N = 2n−1 (2n − 1) e 2n − 1 e´ primo, enta˜o N e´ perfeito.
Demonstrac¸a˜o 3.2.8 Como consequeˆncia do Teorema Fundamental da Aritme´tica, os divisores positivos
de N sa˜o
1, 2, · · · 2n−1, (2n − 1) , 2 (2n − 1) , · · · , 2n−1 (2n − 1)
A soma destes divisores da´
n−1∑
k=0
2k + (2n − 1)
n−1∑
k=0
2k = 2n
n−1∑
k=0
2k =
por aplicac¸a˜o da fo´rmula da soma dos termos de uma progressa˜o geome´trica
= 2n (2n − 1) = 2N
Conve´m notar que para que 2n− 1 seja primo e´ condic¸a˜o necessa´ria que o pro´prio n seja primo; de facto,
se n = kj com 1 < k, j enta˜o temos a factorizac¸a˜o
2n − 1 = (2k − 1) (2k(j−1) + 2k(j−2) + · · ·+ 2k + 1) = (2k − 1) j−1∑
i=0
2ki
Essa condic¸a˜o no entanto na˜o e´ suficiente; o primeiro exemplo e´ n = 11:
211 − 1 = 2047 = 23× 89Cerca de vinte se´culos depois de Euclides, Euler demonstrou a seguinte rec´ıproca parcial:
3.2. NU´MEROS PRIMOS E O TEOREMA FUNDAMENTAL DA ARITME´TICA 39
Teorema 3.2.9 Se N e´ um nu´mero perfeito par enta˜o existe um primo n tal que N = 2n−1 (2n − 1) e 2n−1
e´ primo.
Demonstrac¸a˜o 3.2.10 Suponhamos que N e´ perfeito e que temos N = 2n−1F em que F e´ ı´mpar. Os
divisores positivos de N sa˜o os nu´meros da forma 2kd em que 0 ≤ k ≤ n− 1 e d | F . Se
S =
∑
d|F
d
for a soma dos divisores positivos de F , podemos calcular a soma dos divisores positivos de N como
n−1∑
k=0
2kS = (2n − 1)S
Como N e´ perfeito temos
2N = 2nF = (2n − 1)S
e portanto
S =
2nF
2n − 1 = F +
F
2n − 1
Conclui-se que
F
2n − 1 e´ um inteiro e portanto um divisor de F ; por outro lado
F
2n − 1 = S − F
e´ a soma de todos os divisores positivos de F menores que F ; mas isso implica que
F
2n − 1 e´ o u´nico divisor
positivo de F menor que F e portanto tem que ser
F
2n − 1 = 1.
Portanto
N = 2n−1 (2n − 1)
Como F = 2n − 1 na˜o tem mais divisores e´ porque e´ primo.
Continua em aberto, entre muitos outros relacionados com este, o problema de saber se existem nu´meros
perfeitos ı´mpares.
Observac¸a˜o 3.2.11 Os nu´meros da forma 2n− 1 com n primo designam-se por nu´meros de Mersenne, em
homenagem ao matema´tico e teo´logo franceˆs Marin Mersenne (1588-1648), e os primos dessa forma sa˜o
os primos de Mersenne. A investigac¸a˜o sobre estes nu´meros continua activa e em Setembro de 2008 foi
descoberto o maior primo de Mersenne conhecido ate´ agora:
243112609 − 1
um nu´mero primo cuja representac¸a˜o decimal tem 12978189 algarismos...
40 CHAPTER 3. ELEMENTOS DE ARITME´TICA DOS INTEIROS
3.3 Congrueˆncias e aritme´tica modular
Consideremos primeiro o seguinte exemplo: o que podemos dizer sobre a imagem da func¸a˜o
f : Z→ Z, f(x) = x2 + x+ 1?
Uma poss´ıvel abordagem a este problema comec¸a pela observac¸a˜o de que f so´ toma valores ı´mpares; para o
verificar basta evidentemente considerar os dois casos x par e x ı´mpar.
Desenvolvendo esta ideia, pod´ıamos perguntar quais os pos´ıveis restos da divisa˜o de f(x) por 3; mais uma
vez, esta pergunta e´ fa´cil de responder se notarmos que para qualquer inteiro x
f(x+ 3k) = (x+ 3k)2 + x+ 3k + 1 = x2 + x+ 1 + 6kx+ 9k2 + 3k
ou seja, se somarmos a um certo x um mu´ltiplo de 3, o valor de f muda mas tambe´m por um mu´ltiplo de
3 e portanto o resto da divisa˜o do valor de f por 3 na˜o muda; de facto este resto so´ depende do resto da
divisa˜o de x por 3.
Como qualquer inteiro e´ igual a 0, 1 ou 2 mais um mu´ltiplo de 3, para responder a` pergunta basta calcular
f(0) = 1, f(1) = 3 e f(2) = 7 e os respectivos restos na divisa˜o por 3 que sa˜o 1, 0 e 1 novamente. Conclu´ımos
que 2 nunca e´ resto na divisa˜o de f(x) por 3 e portanto f na˜o toma nenhum dos valores
· · · ,−4,−1, 2, 5, 8, 11, · · ·
Naturalmente, o mesmo racioc´ınio se podia aplicar a outro inteiro em vez de 3 e do mesmo modo a outra
func¸a˜o
f : Z→ Z
Vamos agora clarificar com uma notac¸a˜o adequada esta ideia de trabalhar apenas com os restos da divisa˜o
por um certo inteiro.
Definic¸a˜o 3.3.1 Seja m ∈ N. Dois inteiros a e b dizem-se congruentes mo´dulo m
a ≡ b mod m
se m divide a− b.
Como se verifica facilmente, a congrueˆncia e´ uma relac¸a˜o de equivaleˆncia em Z, para qualquer escolha do
mo´dulo m. A classe de congrueˆncia de a e´
· · · , a− 3m, a− 2m,m, a, a+m, a+ 2m, a+ 3m, · · ·
e cada classe de congrueˆncia tem um e um so´ representante no conjunto
{0, 1, · · · ,m− 1}
Um conjunto com esta propriedade chama-se um sistema completo de res´ıduos mod m:
3.3. CONGRUEˆNCIAS E ARITME´TICA MODULAR 41
Definic¸a˜o 3.3.2 : Um sistema completo de res´ıduos mo´dulo m e´ um conjunto
{n0, n1, · · · , nm−1} ⊂ Z
tal que se i 6= j enta˜o ni e nj na˜o sa˜o congruentes mod m.
Podemos tambe´m descrever um sistema completo de res´ıduos mo´dulo m como um conjunto
{n0, n1, · · · , nm−1} ⊂ Z
tal que ni ≡ i mod m.
Existem evidentemente infinitos sistemas completos de res´ıduos para um mo´dulo dado.
O conjunto das classes de congrueˆncia mo´dulo m e´ representado por Z/mZ ou mais simplesmente por
Z/m. Uma congrueˆncia entre nu´meros mo´dulo m corresponde portanto a uma igualdade entre classes, ou
seja entre elementos de Z/m.
A propriedade fundamental da relac¸a˜o de congrueˆncia esta´ contida na proposic¸a˜o seguinte, cuja demonstrac¸a˜o
se deixa como exerc´ıcio.
Proposic¸a˜o 3.3.3 : Se a ≡ b mod m e c ≡ d mod m enta˜o
a+ c ≡ b+ d mod m ac ≡ bd mod m
ou seja, a classe de congrueˆncia da soma ou do produto de dois inteiros depende apenas das classes
de congrueˆncia destes (e na˜o dos representantes particulares dentro de cada classe); esta˜o portanto bem
definidas em Z/m as operac¸o˜es de soma e produto.
Exemplo 3.3.4 : as tabuadas de soma e multiplicac¸a˜o de Z/4 sa˜o
+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
× 0 1 2 3
0 0 0 0 0
1 0 1 2 3
2 0 2 0 2
3 0 3 2 1
e de Z/5
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
× 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
42 CHAPTER 3. ELEMENTOS DE ARITME´TICA DOS INTEIROS
Observac¸a˜o 3.3.5 : Para se ser mais preciso, dev´ıamos distinguir a classe de congrueˆncia dos seus repre-
sentantes; pode-se por exemplo usar a notac¸a˜o a para designar a classe de congrueˆncia de a.
Mas quando na˜o ha´ perigo de confusa˜o usamos um nu´mero para representar a sua classe de congrueˆncia;
e´ no entanto crucial que esteja sempre claro quando e´ que isso acontece; por exemplo, e´ verdade que
714 ≡ 214 mod 5
e portanto podemos usar qualquer dos dois nu´meros para representar a respectiva classe. No entanto
o expoente 14 na˜o representa uma classe de congrueˆncia mo´dulo 5; ele indica que estamos a multiplicar a
classe de 2 por si mesma 14 vezes e embora 14 ≡ 4 mod 5, na˜o e´ verdade que 214 seja congruente com
24 mo´dulo 5.
Uma equac¸a˜o sobre classes de congrueˆncia mo´dulo m chama-se tambe´m uma equac¸a˜o modular. Uma
soluc¸a˜o de uma tal equac¸a˜o pode ser vista como um elemento de Z/m ou como um conjunto de nu´meros
inteiros.
Como ja´ vimos no exemplo inicial, uma das aplicac¸o˜es principais do conceito de congrueˆncia consiste
precisamente em, dado um problema definido no conjunto dos inteiros, passar a um problema no conjunto
das classes de congrueˆncia mod m, e deduzir da soluc¸a˜o deste problema informac¸o˜es sobre o problema
original. Um outro exemplo muito simples:
Exemplo 3.3.6 : Sera´ que 2349674927 e´ um quadrado perfeito em Z?
Pela proposic¸a˜o anterior, se existir x ∈ Z tal que x2 = 2349674927 enta˜o tambe´m sera´, para qualquer
escolha de m,
x2 ≡ 2349674927 mod m
Notamos no entanto que, de acordo com as tabelas acima, os quadrados perfeitos esta˜o nas classes de con-
grueˆncia 0 e 1 mo´dulo 4, enquanto que 2349674927 = 2349674900 + 27 ≡ 3 mod 4, pelo que este nu´mero
na˜o e´ de certeza um quadrado perfeito.
Ja´ para, por exemplo, 2495788725, a passagem a`s classes de congrueˆncia mo´dulo 4 na˜o permitia re-
sponder a` mesma pergunta, pois este nu´mero e´ congruente com 1 mo´dulo 4; mas pod´ıamos observar que
2495788725 ≡ 3 mod 7 e que os quadrados perfeitos esta˜o nas classes de congrueˆncia 0, 1, 2, 4 (mo´dulo 7),
pelo que 2495788725 tambe´m na˜o e´ um quadrado perfeito.
Dados mo´dulos m e n, na˜o e´ poss´ıvel, em geral, estabelecer uma relac¸a˜o entre as respectivas classes de
congrueˆncia. Mas no caso de n | m ha´ uma relac¸a˜o simples e importante entre Z/m e Z/n: seja m = nd; em
primeiro lugar e´ o´bvio que
x ≡ y mod m =⇒ x ≡ y mod n;
por outro lado, se x ≡ y mod n e´ porque existe k ∈ Z tal que y = x + kn; e verificamos que a classe de
congrueˆncia mod m de y so´ depende da classe de congrueˆncia de k mo´dulo d.
Conclui-se que a classe de congrueˆncia mod n de x e´a unia˜o das d classes de congrueˆncia mod m com
representantes
x, x+ n, · · ·x+ (d− 1)n
3.3. CONGRUEˆNCIAS E ARITME´TICA MODULAR 43
3.3.1 A equac¸a˜o linear numa varia´vel
Consideramos a equac¸a˜o
ax ≡ b mod m
De acordo com as definic¸o˜es dadas, um inteiro x sera´ uma soluc¸a˜o se existir y ∈ Z tal que ax− b = my. Seja
d = mdc(a,m); resulta directamente da u´ltima equac¸a˜o que para que exista soluc¸a˜o e´ necessa´rio que d|b pois
b = ax−my.
Por outro lado, sabemos que existem inteiros x0 e y0 tais que
ax0 +my0 = d
x0 e y0 podem ser determinados por aplicac¸a˜o do algoritmo de Euclides com que se calcula d.
Mas enta˜o, se d|b, temos que
ax0
b
d
+my0
b
d
= b
e vemos que a equac¸a˜o modular tem a soluc¸a˜o x = x0
b
d
(ou, mais precisamente, a classe de congrueˆncia
deste nu´mero).
Que outras soluc¸o˜es (na˜o congruentes com esta, claro) existem? suponhamos que z e w satisfazem
igualmente az −mw = b; enta˜o
az −mw = ax−my ⇔ a(z − x) = m(w − y)⇔ a
d
(z − x) = m
d
(w − y)
mas, como
a
d
e
m
d
sa˜o primos entre si, isso implica que
m
d
|(z − x)
ou seja
z = x+ k
m
d
Duas soluc¸o˜es desta forma sera˜o congruentes mo´dulo m se d|k. Temos portanto d soluc¸o˜es distintas, corre-
spondendo aos valores 0 ≤ k < d. Resumindo,
Proposic¸a˜o 3.3.7 : Para m ∈ N, a inteiro e d = mdc(a,m), a equac¸a˜o
ax ≡ b mod m
tem d soluc¸o˜es distintas se d|b e na˜o tem soluc¸o˜es caso contra´rio.
Se x0 e y0 sa˜o inteiros satisfazendo ax0 +my0 = d, as soluc¸o˜es do primeiro caso sa˜o
x0
b
d
+ k
m
d
, 0 ≤ k < d
44 CHAPTER 3. ELEMENTOS DE ARITME´TICA DOS INTEIROS
Exemplo 3.3.8 : Determinar as soluc¸o˜es de
210x ≡ 10 mod 745
Usando o algoritmo de Euclides
745 = 3× 210 + 115
210 = 1× 115 + 95
115 = 1× 95 + 20
95 = 4× 20 + 15
20 = 1× 15 + 5
deduzimos que
mdc(210, 745) = 5 = 11× 745− 39× 210
Aplicando a proposic¸a˜o anterior, conclu´ımos que as soluc¸o˜es da equac¸a˜o modular sa˜o dadas pela expressa˜o
2× (−39) + k 745
5
, 0 ≤ k < 5
ou seja
−78, 71, 220, 369, 518
E´ importante notar a seguinte interpretac¸a˜o deste resultado no caso d = 1; mdc(a,m) = 1 significa que
a classe de a e´ invert´ıvel para a multiplicac¸a˜o em Z/m: se au + mv = 1, enta˜o a classe de u e´ a inversa da
classe de a; a soluc¸a˜o da congrueˆncia
ax ≡ b mod m
e´, como numa equac¸a˜o “habitual”, x = a−1b (em que a−1 designa a classe inversa da de a).
Por outro lado, no caso geral, se d = mdc(a,m) divide b podemos observar que
ax ≡ b mod m⇔ m|(ax− b)⇔ m
d
|
(
a
d
x− b
d
)
⇔ a
d
x ≡ b
d
mod
m
d
Assim, podemos comec¸ar por encontrar a soluc¸a˜o (u´nica) t desta u´ltima congrueˆncia e notar que as soluc¸o˜es
da congrueˆncia inicial sa˜o as classes mod m dadas por t + k
m
d
com 0 ≤ k < d, que sa˜o as classes de
congrueˆncia mo´dulo m que esta˜o contidas na classe de t mod
m
d
.
Exemplo 3.3.9 : 15x ≡ 21 mod 72 tem 3 soluc¸o˜es uma vez que mdc(15, 72) = 3 e 3|21;
15x ≡ 21 mod 72⇔ 5x ≡ 7 mod 24
Como 55˙− 1 · 24 = 1 (ou seja o inverso de 5 mo´dulo 24 e´ o pro´prio 5) deduzimos que a soluc¸a˜o desta u´ltima
congrueˆncia e´ x ≡ 5 · 7 ≡ 11 mod 24.
Finalmente, x ≡ 11 mod 24⇔ x ≡ 11 ∨ x ≡ 35 ∨ x ≡ 59 mod 72.
3.4. O TEOREMA CHINEˆS DOS RESTOS 45
Observac¸a˜o 3.3.10 E´ importante notar que multiplicar ambos os lados de uma congrueˆncia por um inteiro
so´ resulta numa congrueˆncia equivalente (ou seja, com as mesmas soluc¸o˜es) se esse inteiro for primo com
o mo´dulo. Caso contra´rio, temos apenas uma implicac¸a˜o.
Por exemplo se multiplicarmos por 3 ambos os lados da congrueˆncia
7x ≡ 2 mod 18,
obtemos
21x ≡ 6 mod 18⇔ 3x ≡ 6 mod 18;
esta u´ltima equac¸a˜o tem a soluc¸a˜o evidente x ≡ 2 mod 18, que na˜o e´ soluc¸a˜o da equac¸a˜o original. Podemos
apenas dizer que a soluc¸a˜o da equac¸a˜o original (que existe e e´ u´nica) esta´ entre as soluc¸o˜es da u´ltima, que
sa˜o as classes de congrueˆncia de 2, 8 e 14 mo´dulo 18. E de facto
7× 6 ≡ 2 mod 18.
3.4 O Teorema Chineˆs dos Restos
Comec¸amos com um exemplo simples que esta´ na origem do resultado que vamos apresentar:
Exemplo 3.4.1 Um camponeˆs tem um certo nu´mero de ovos; quandos os divide por 3, sobra-lhe 1; quando
os divide por 4, sobram 2 ovos; e quando os divide por 5, sobram 3. Quantos ovos tem o camponeˆs?
O que queremos aqui e´ a soluc¸a˜o simultaˆnea de um sistema de equac¸o˜es modulares x ≡ 1 mod 3x ≡ 2 mod 4
x ≡ 3 mod 5
Comec¸ando pela primeira equac¸a˜o, temos que qualquer soluc¸a˜o x do sistema tem que satisfazer
x = 1 + 3y
para algum y ∈ Z; substituindo na segunda equac¸a˜o ficamos com
3y + 1 ≡ 2 mod 4⇔ 3y ≡ 1 mod 4⇔ y ≡ 3 mod 4
e portanto y = 3 + 4z e x = 1 + 3(3 + 4z) = 10 + 12z, onde, mais uma vez, z representa uma nova inco´gnita
inteira; substituindo de novo na terceira equac¸a˜o
12z + 10 ≡ 3 mod 5⇔ 2z ≡ 3 mod 5⇔ z ≡ 4 mod 5
Conclu´ımos que z = 4 + 5w e portanto a soluc¸a˜o do nosso sistema e´
x = 10 + 12(4 + 5w) = 58 + 60w.
A resposta a` pergunta e´ portanto que o camponeˆs poderia ter 58 ovos ou 118 ou 178, etc.
Que a soluc¸a˜o do sistema so´ fica determinada mo´dulo 60 e´ evidente, uma vez que se x for soluc¸a˜o, qualquer
inteiro da forma x + 60w tambe´m seria soluc¸a˜o. Por outro lado, se x e y forem duas soluc¸o˜es do sistema,
enta˜o x−y sera´ divis´ıvel por 3, por 4 e por 5, e como estes sa˜o primos dois a dois, x−y tem que ser divis´ıvel
46 CHAPTER 3. ELEMENTOS DE ARITME´TICA DOS INTEIROS
pelo seu produto 60.
Podemos tambe´m observar que o facto de 3, 4 e 5 serem primos entre si dois a dois nos garantiu que ao
substituir o valor de x na segunda e depois na terceira equac¸a˜o, ficar´ıamos sempre com uma equac¸a˜o com
soluc¸o˜es, uma vez que o coeficiente de y e depois de z e´ primo com o mo´dulo da equac¸a˜o respectiva.
Vamos agora enunciar um resultado fundamental para a simplificac¸a˜o da resoluc¸a˜o de equac¸o˜es modulares:
Teorema 3.4.2 (Teorema Chineˆs dos Restos) : Sejam m1,m2, · · · ,mk inteiros positivos primos dois
a dois (ou seja, se 1 ≤ i < j ≤ k enta˜o mdc(mi,mj) = 1) e M =
∏k
i=1mi. Enta˜o, dados a1, a2, · · · , ak
quaisquer, o sistema de congrueˆncias 
x ≡ a1 mod m1
x ≡ a2 mod m2
...
x ≡ ak mod mk
tem soluc¸a˜o que e´ u´nica mo´dulo M .
Demonstrac¸a˜o 3.4.3 Comecemos por notar que a observac¸a˜o feita a propo´sito do exemplo, vale em geral:
dada uma soluc¸a˜o do sistema ela e´ u´nica mo´dulo M , uma vez que se x e y sa˜o soluc¸o˜es, temos mi | (x− y)
para todo o i e como os mi sa˜o primos dois a dois isso implica M | (x− y).
O me´todo iterativo de soluc¸a˜o usado no exemplo pode ser usado para fazer uma demonstrac¸a˜o por induc¸a˜o:
dado um sistema com duas equac¸o˜es {
x ≡ a1 mod m1
x ≡ a2 mod m2
a soluc¸a˜o pode ser determinada como ja´ vimos substituindo na segunda equac¸a˜o x por a1 +m1y; a equac¸a˜o
m1y ≡ a2 − a1 mod m2
tem soluc¸a˜o u´nica mo´dulo m2 uma vez que mdc(m1,m2) = 1.
Suponhamos agora, como hipo´tese de induc¸a˜o, que o resultado do teorema e´ va´lido para um certo k e seja
x ≡ a1 mod m1
x ≡ a2 mod m2
...
x ≡ ak mod mk
x ≡ ak+1 mod mk+1
Chamemos n ao produto m1 × · · · ×mk. Por hipo´tese de induc¸a˜o, o sistema constitu´ıdo pelas primeiras k
equac¸o˜es tem soluc¸a˜o u´nica c mod n; podemos enta˜o resolver o sistema de duas equac¸o˜es{
x ≡ c mod n
x ≡ ak+1 mod mk+1
a sua soluc¸a˜o, u´nica mo´dulo n×mk+1 = M , e´ a desejada soluc¸a˜o do sistema de k + 1 equac¸o˜es.
3.4. O TEOREMA CHINEˆS DOS RESTOS 47
O Teorema Chineˆs dos Restos permite reduzir a resoluc¸a˜o de uma congrueˆncia a` de um sistema de
congrueˆncias mais simples:
Exemplo 3.4.4 : Considere-se a equac¸a˜o
327x ≡ 171 mod 520;
Calculando mdc(327, 520) = 1 podemos deduzir que existe uma u´nica soluc¸a˜o e aplicar o me´todo explicado
mais atra´s. No entanto, notando que 520 = 5 · 8 · 13, passamos