Alguns Topicos de Matematica Discreta - Ana Paula Tomas

Prévia do material em texto

Alguns To´picos de Matema´tica Discreta
Ana Paula Toma´s
Departamento de Cieˆncia de Computadores
Faculdade de Cieˆncias do Porto
2005
Conteu´do
1 Conjuntos 1
1.1 Operac¸o˜es com Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Representac¸a˜o de Nu´meros em Computador 7
2.1 Sistema de Representac¸a˜o Posicional . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1 Relac¸a˜o entre bina´rio, octal e hexadecimal . . . . . . . . . . . . . . . . 11
2.1.2 Adic¸a˜o e multiplicac¸a˜o na base b . . . . . . . . . . . . . . . . . . . . . 12
2.1.3 Representac¸a˜o de nu´meros com um nu´mero fixo de d´ıgitos . . . . . . . 15
2.1.4 Representac¸a˜o de nu´meros negativos . . . . . . . . . . . . . . . . . . . 16
2.2 Adic¸a˜o e Subtracc¸a˜o em n Bits . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1 Adic¸a˜o e subtracc¸a˜o bina´ria de inteiros na˜o negativos . . . . . . . . . 19
2.2.2 Adic¸a˜o de inteiros em complemento para 2 . . . . . . . . . . . . . . . 20
2.2.3 Subtracc¸a˜o de inteiros em complemento para 2 . . . . . . . . . . . . . 20
2.3 Representac¸a˜o em Vı´rgula Fixa . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Representac¸a˜o em Vı´rgula Flutuante . . . . . . . . . . . . . . . . . . . . . . . 21
3 Algumas Noc¸o˜es de Divisibilidade 23
3.1 Bases de Numerac¸a˜o e Crite´rios de Divisibilidade . . . . . . . . . . . . . . . . 23
3.2 Noc¸a˜o de Divisor e de Mu´ltiplo . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Factorizac¸a˜o em Primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3.1 Determinac¸a˜o de primos: crivo de Erasto´tenes . . . . . . . . . . . . . 27
3.3.2 Ca´lculo de divisores por ana´lise da factorizac¸a˜o em primos . . . . . . . 28
3.4 Ma´ximo Divisor Comum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.1 Ca´lculo do ma´ximo divisor comum pelo algoritmo de Euclides . . . . . 29
3.5 Mı´nimo Mu´ltiplo Comum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.6 Congrueˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
i
4 Induc¸a˜o Matema´tica 33
4.1 Princ´ıpio de Induc¸a˜o Matema´tica . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.1.1 Erros frequentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Induc¸a˜o Forte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.2.1 Outras formulac¸o˜es do princ´ıpio de induc¸a˜o . . . . . . . . . . . . . . . 42
5 Relac¸o˜es Bina´rias 43
5.1 Relac¸o˜es Bina´rias de A em B . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1.1 Operac¸o˜es com relac¸o˜es bina´rias . . . . . . . . . . . . . . . . . . . . . 43
5.1.2 Matriz duma relac¸a˜o bina´ria . . . . . . . . . . . . . . . . . . . . . . . 45
5.1.3 Func¸o˜es de A em B . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.2 Relac¸o˜es Bina´rias Definidas num Conjunto . . . . . . . . . . . . . . . . . . . . 47
5.2.1 Propriedades das relac¸o˜es bina´rias definidas em A . . . . . . . . . . . 48
5.2.2 Grafo da relac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3 Relac¸o˜es de Compatibilidade e de Equivaleˆncia . . . . . . . . . . . . . . . . . 50
5.3.1 Classes de equivaleˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3.2 Partic¸o˜es e relac¸o˜es de equivaleˆncia . . . . . . . . . . . . . . . . . . . . 53
5.3.3 Classes de Compatibilidade . . . . . . . . . . . . . . . . . . . . . . . . 55
5.4 Relac¸o˜es de Ordem Parcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.4.1 Diagrama de Hasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
5.4.2 Ma´ximos, mı´nimos, supremo, ı´nfimo, majorantes e minorantes . . . . 59
5.5 Fechos duma Relac¸a˜o para uma Propriedade . . . . . . . . . . . . . . . . . . . 60
5.5.1 Fecho transitivo e percursos em grafos . . . . . . . . . . . . . . . . . . 62
5.5.2 Fecho transitivo duma relac¸a˜o definida num conjunto finito . . . . . . 68
6 Grafos e Multigrafos 71
6.1 Grafos Dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
6.1.1 Multigrafos dirigidos. . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.1.2 Grafos, Percursos e relac¸o˜es bina´rias . . . . . . . . . . . . . . . . . . . 74
6.2 Grafos Na˜o Dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6.2.1 Grafos Conexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2.2 Condic¸a˜o necessa´ria para um grafo ser conexo . . . . . . . . . . . . . . 78
6.3 A´rvores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.3.1 A´rvores com ra´ız . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.4 Percursos Eulerianos e Hamiltonianos . . . . . . . . . . . . . . . . . . . . . . 82
6.5 Grafos Planares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.6 Isomorfismo de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
ii
6.7 Colorac¸a˜o de Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
6.8 Grafos com Valores Associados aos Ramos . . . . . . . . . . . . . . . . . . . . 86
6.8.1 Determinac¸a˜o da distaˆncia mı´nima . . . . . . . . . . . . . . . . . . . . 87
6.9 Grafos com S´ımbolos Associados aos Ramos . . . . . . . . . . . . . . . . . . . 93
iii
iv
Prefa´cio
Estes apontamentos teˆm por base material elaborado em anos anteriores para disciplinas da
licenciatura em Cieˆncia de Computadores [5, 6, 7], o qual foi agora revisto e nalguns to´picos
completado para servir de apoio a` disciplina de Matema´tica para Cieˆncia de Computadores,
no ano lectivo de 2005/06. Na˜o visam substituir a leitura da bibliografia recomendada pelos
docentes e na˜o cobrem actualmente todos os to´picos abordados na disciplina.
v
vi
Cap´ıtulo 1
Conjuntos
Neste cap´ıtulo vamos essencialmente recordar ou introduzir alguma da notac¸a˜o que e´ usada
para conjuntos. Tomamos a noc¸a˜o de conjunto como primitiva, convencionando que um
conjunto e´ constitu´ıdo por elementos – objectos materiais ou entes abstractos que teˆm
alguma propriedade em comum (no caso extremo, a de pertencerem todos a esse conjunto).
Os conjuntos podem ser vazios (i.e. sem elementos). Em geral, usamos letras maiu´sculas
para designar conjuntos e minu´sculas para referir os seus elementos. Para indicar que a e´ um
elemento do conjunto A escrevemos a ∈ A. Os conjuntos podem ser especificados em extensa˜o
– exibindo todos os elementos que os constituem – ou indicando a propriedade que caracteriza
os seus elementos – definic¸a˜o em compreensa˜o. Por exemplo, {1, 2, 3, 4} e {n | n ∈ Z+∧n ≤ 4}.
Notac¸a˜o. Sejam A e B conjuntos.
a ∈ A a pertence a A, a e´ elemento de A
a /∈ A a na˜o pertence a A
A = B igualdade de conjuntos (qualquer que seja x,
x ∈ A se e so´ se x ∈ B)
A ⊆ B A contido em B, A subconjunto de B
(qualquer que seja x, se x ∈ A enta˜o x ∈ B)
A ⊇ B A conte´m B, B ⊆ A
A ⊂ B A contido propriamente em B,
A subconjunto pro´prio de B
A ⊆ B ∧A 6= B
A ⊃ B A conte´m propriamente B
A 6= B A 6⊆ B ou B 6⊆ A
∅ ou {} conjunto vazio
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
1.1. OPERAC¸O˜ES COM CONJUNTOS 2
O conjunto dos subconjuntos de A, representa-se por P(A) ou 2A. Qualquer con-
junto A pertence ao seu conjunto de subconjuntos, isto e´ A ∈ P(A). Por exemplo,
P({1, 2, 3}) = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
O conjunto P({1, 2, 3}) tem 23 elementos. Tambe´m se pode verificar que P(P({1, 2, 3}))
tem 22
3
elementos. Se A tem n elementos, P(A) tem 2n elementos.
Nestes apontamentos, N representa o conjunto dos inteiros na˜o negativos (incluindo
assim tambe´m 0).
N inteirosna˜o negativos (em vez de N0)
Z inteiros
Q racionais
R reais
R+0 reais na˜o negativos
R+ reais positivos
R− reais negativos
Um conjunto A na˜o vazio e´ finito se e so´ se existir uma bijecca˜o de A em {x ∈ N | x < n}
para algum n ∈ N. Nesse caso, n e´ o cardinal (nu´mero de elementos) de A. Usamos |A| (ou,
alternativamente, #A) para designar o cardinal de A. O cardinal do conjunto vazio e´ zero.
A propo´sito de questo˜es de notac¸a˜o, e´ de salientar que
{n | n ∈ N}
{n}, com n ∈ N
denotam conjuntos diferentes: o primeiro e´ N e o segundo e´ constitu´ıdo por um u´nico inteiro
(que esta´ a ser representado pela letra n).
1.1 Operac¸o˜es com Conjuntos
A intersecc¸a˜o de A com B representa-se por A ∩ B, e e´ o conjunto dos elementos que
pertencem a ambos os conjuntos.
A ∩B = {x | x ∈ A e x ∈ B}
A unia˜o de A com B que se representa por A ∪ B, e´ o conjunto dos elementos que
pertencem a pelo menos um dos conjuntos.
A ∪B = {x | x ∈ A ou x ∈ B}
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
1.1. OPERAC¸O˜ES COM CONJUNTOS 3
O complementar de B em A representa-se por A \B, e e´ o conjunto dos elementos de
A que na˜o pertencem a B.
A \ B = {x | x ∈ A e x /∈ B}
Quando esta´ implic´ıto um dado universo U , chama-se complementar de A, e representa-
se por A, ao complementar de A em U , ou seja a U \ A.
Exemplo 1 Vamos provar que A \ (B ∪C) = (A \B)∩ (A \C). Para tal vamos mostrar que
x ∈ A \ (B ∪ C)⇔ x ∈ (A \ B) ∩ (A \ C), qualquer que seja x.
x ∈ A \ (B ∪C) ⇔ x ∈ A ∧ x /∈ B ∪ C (por def. de diferenc¸a)
⇔ x ∈ A ∧ (x /∈ B ∧ x /∈ C) (por def. unia˜o)
⇔ x ∈ A \B ∧ x ∈ A \ C (por def. de diferenc¸a)
⇔ x ∈ (A \ B) ∩ (A \ C) (por def. intersecc¸a˜o)
Exemplo 2 Quaisquer que sejam os conjuntos A,B ⊆ U , tem-se A ∪B = A ∩B. De facto,
se x ∈ A ∪B enta˜o, por definic¸a˜o de complementar, x /∈ A ∪B. Logo, x /∈ A e x /∈ B. Mas,
x /∈ A sse x ∈ A. E, x /∈ B sse x ∈ B. Enta˜o, x ∈ A e x ∈ B. Donde, x ∈ A∩B. Mostra´mos
assim que A ∪B ⊆ A ∩B. Reciprocamente,
x ∈ A ∩B =⇒ (x ∈ A ∧ x ∈ B) (por def. ∩)
=⇒ (x /∈ A ∧ x /∈ B) (por def. complementar)
=⇒ x /∈ (A ∪B) (por def. ∪)
=⇒ x ∈ A ∪B (por def. complementar)
ou seja, A ∪B ⊇ A ∩B.
Exerc´ıcio 1.1.1 Suponha que os conjuntos indicados sa˜o subconjuntos do universo U . Sendo
A, B e C subconjuntos de U quaisquer, mostre cada uma das propriedades:
(a) A \ B = A ∩B = B \ A (j) ∅ = U (r) U = ∅
(b) A \ B = ∅ sse A ⊆ B (k) A \ A = ∅ (s) A \ ∅ = A
(c) A \ B = A sse A ∩B = ∅ (l) A = A (t) A ∪ U = U
(d) (A \ B) ∪ (B \ A) = (A ∪B) \ (B ∩A) (m) A ∪A = U (u) A ∩A = ∅
(e) (A ∩B) ∩ C = A ∩ (B ∩ C) (n) A ∩ U = A (v) A ∩A = A
(f) (A ∪B) ∪C = A ∪ (B ∪ C) (o) A ∪ ∅ = A
(g) (A ∪B) ∩ C = (A ∩ C) ∪ (B ∩ C)
(h) (A ∩B) ∪ C = (A ∪ C) ∩ (B ∪ C) (p) A ∪B = A ∩B
(i) A \ (B ∪ C) = (A \ B) ∩ (A \ C) (q) A ⊆ B sse B ⊆ A
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
1.1. OPERAC¸O˜ES COM CONJUNTOS 4
Exemplo 3 A t´ıtulo de exemplo, vamos analisar a veracidade ou falsidade das afirmac¸o˜es
seguintes e justifica´-la.
1. Qualquer que seja x ∈ Z, existe y ∈ Z tal que x ≤ y e x 6= y.
∀x ∈ Z ∃y ∈ Z (x ≤ y ∧ x 6= y)
A afirmac¸a˜o e´ verdadeira porque, sendo o conjunto dos inteiros infinito, se x e´ inteiro,
x + 1 tambe´m e´ um inteiro e x + 1 e´ superior a x. Ou seja, dado um x qualquer, se
considerarmos que y e´ x + 1, satisfazemos a condic¸a˜o (x ≤ y ∧ x 6= y). Note que y
dependera´ de x.
2. Existe y ∈ Z tal que para todo x ∈ Z se tem x ≤ y.
∃y ∈ Z ∀x ∈ Z x ≤ y
A afirmac¸a˜o e´ falsa porque em particular se x fosse y+1 enta˜o teriamos que ter y+1 ≤ y,
que na˜o e´ satisfaz´ıvel (ja´ que e´ equivalente a 1 ≤ 0).
3. Existe um inteiro na˜o negativo que na˜o excede qualquer outro inteiro na˜o
negativo.
∃x ∈ Z+0 ∀y ∈ Z+0 x ≤ y
A afirmac¸a˜o e´ verdadeira. O inteiro 0 e´ menor ou igual que cada um dos inteiros na˜o
negativos. Aqui, Z+0 denota o conjunto dos inteiros na˜o negativos, o qual identifica´mos
tambe´m por N.
4. Existe x ∈ Z tal que x e´ maior do que qualquer outro inteiro y.
∃x ∈ Z ∀y ∈ Z x > y
A afirmac¸a˜o e´ falsa (ana´loga a` 2).
5. Para todo A ⊆ Z, tem-se P(A) = {∅}.
A afirmac¸a˜o e´ falsa, porque {1} e´ um subconjunto de Z e P({1}) = {∅, {1}} 6= {∅}.
6. Para todo A ⊆ Z, se A = ∅ enta˜o P(A) = {∅}.
A afirmac¸a˜o e´ verdadeira. So´ existe um subconjunto de Z que e´ vazio, e P(∅) = {∅}.
Note que {∅} e´ um conjunto que tem um elemento. Esse elemento e´ ∅, ou seja, e´ o
conjunto vazio.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
1.1. OPERAC¸O˜ES COM CONJUNTOS 5
7. Tem-se P(A) = ∅, para algum A ⊆ Z.
∃A (A ⊆ Z ∧ P(A) = ∅)
A afirmac¸a˜o e´ falsa, porque qualquer que seja o subconjunto A de Z, o conjunto vazio e´
um elemento de P(A).
8. Quaisquer que sejam x, y ∈ Z, tem-se x ≤ y ou y ≤ x.
∀x ∈ Z ∀y ∈ Z (x ≤ y ∨ y ≤ x)
Dizer que x ≤ y equivale a dizer que existe um inteiro na˜o negativo z tal que y = x + z.
E´ verdade que (x ≤ y ∨ y ≤ x), quaisquer que sejam os inteiros x e y.
Como x− y e´ inteiro, quaisquer que sejam x e y, se x− y e´ na˜o negativo, enta˜o y ≤ x
pois x = y + (x − y). Se x − y e´ negativo, enta˜o y − x e´ um inteiro positivo, e como
y = x + (y − x), tem-se x ≤ y.
9. Qualquer que seja A ⊆ Z, se A 6= {−1, 2, 3} enta˜o 4 ∈ A.
∀A ( (A ⊆ Z ∧ A 6= {−1, 2, 3}) ⇒ 4 ∈ A) )
Falso. Existe um subconjunto de Z que e´ diferente de {−1, 2, 3} e que na˜o tem o 4. Por
exemplo, o conjunto vazio.
10. Quaisquer que sejam A,B ⊆ Z, se 5 ∈ A \B enta˜o 5 ∈ A.
∀A ∀B( (A ⊆ Z ∧ B ⊆ Z ∧ 5 ∈ A \B)⇒ 5 ∈ A )
A afirmac¸a˜o e´ verdadeira. Quaisquer que sejam os subconjuntos A e B de Z, tem-se
5 ∈ A \ B se e so´ se 5 ∈ A e 5 /∈ B. Logo, se 5 ∈ A \ B enta˜o 5 ∈ A.
11. Para todo o x ∈ Z, e quaisquer que sejam A,B ⊆ Z, se x ∈ A \ B enta˜o x ∈ A.
A afirmac¸a˜o e´ verdadeira. A justificac¸a˜o e´ semelhante a` dada para a afirmac¸a˜o anterior
(claro que e´ necessa´rio falar em x e na˜o em 5!).
12. Existe x ∈ Z tal que x ∈ A \ B, quaisquer que sejam A,B ⊆ Z.
Esta afirmac¸a˜o pode ser traduzida pela expressa˜o lo´gica
∃x (x ∈ Z ∧ ( ∀A∀B ( (B ⊆ Z ∧A ⊆ Z)⇒ x ∈ A \ B) ))
a qual escrevemos por vezes como
∃x ∈ Z ∀A ⊆ Z∀B ⊆ Z (x ∈ A \ B)
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
1.1. OPERAC¸O˜ES COM CONJUNTOS 6
que e´ falsa. Quaisquer que sejam os conjuntos A e B se A = B enta˜o A\B = ∅. Assim,
se tomarmos, por exemplo, A = B = {1}, os conjuntos A e B sa˜o subconjuntos de Z e
na˜o existe qualquer inteiro x tal que x ∈ A \B.
13. 2 + 2 = 4 ou
√
2 ∈ Z.
A afirmac¸a˜o e´ verdadeira porque embora
√
2 /∈ Z, e´ verdade que 2 + 2 = 4.
14. Se 2 + 2 6= 4 enta˜o √2 ∈ Z.
A afirmac¸a˜o e´ equivalente a “2 + 2 = 4 ou
√
2 ∈ Z”.
15. Se
√
2 ∈ Z enta˜o 2 + 2 6= 4.
A afirmac¸a˜o e´ equivalente a “
√
2 /∈ Z ou 2 + 2 6= 4”, e como √2 /∈ Z, a afirmac¸a˜o e´
verdadeira.
16.
√
2 6∈ Z ou 2 + 2 6= 4.
A afirmac¸a˜o e´ verdadeira porque
√
2 6∈ Z.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
Cap´ıtulo 2
Representac¸a˜o de Nu´meros em
Computador
Do mesmo modo que “5692 segundos”, “94 minutos e 52 segundos”, “1 hora, 34 minutos e 52
segundos” sa˜o designac¸o˜es ou representac¸o˜es diferentes da mesma entidade, tambe´m 5692(10),
13074(8) e 1011000111100(2) o sa˜o. De facto,
1 34 52(60) ≡ 1h34′52′′ ≡ 1× 602 + 34× 601 + 52× 600
5 6 9 2(10) ≡ 5× 103 + 6× 102 + 9× 101 + 2× 100
1 3 0 7 4(8) ≡ 1× 84 + 3× 83 + 0× 82 + 7× 81 + 4× 80
1 0 1 1 0 0 0 1 1 1 1 0 0(2) ≡ 1× 212 + 0× 211 + 1× 210 + 1× 29 + 0× 28 + 0× 27 +
0× 26 + 1× 25 + 1× 24 + 1× 23 + 1× 22 + 0× 21 + 0× 20
dizendo-se que 60, 10, 8 e 2 sa˜o as bases de numerac¸a˜o, respectivas. Habitualmente, escreve-se
5692 em vez de 5692(10), porque a base mais usual para representac¸a˜o de inteiros e´ a base 10,
designada por decimal. As bases 8 e 2 sa˜o designadas por octal e bina´ria. Se considerarmos
as poteˆnciasde 2,
212 211 210 29 28 27 26 25 24 23 22 21 20
4096 2048 1024 512 256 128 64 32 16 8 4 2 1
podemos observar que 5692 = 4096+1596 = 4096+(1024+572) = 4096+1024+(512+60) =
. . . = 4096 + 1024 + 512 + 32 + 16 + 8 + 4 = 1011000111100(2).
Analogamente, se considerarmos as poteˆncias de 3,
38 37 36 35 34 33 32 31 30
6561 2187 729 243 81 27 9 3 1
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 8
podemos verificar que 5692 = 21210211(3). De facto, 5692 = 2 × 2187 + 1318 = 2 × 2187 +
(1× 729 + 589) = 2× 2187 + 1× 729 + (2× 243 + 103) = . . . = 2× 2187 + 1× 729 + 2× 243 +
1× 81 + 2× 9 + 1× 3 + 1 = 21210211(3).
2.1 Sistema de Representac¸a˜o Posicional
Num sistema de numerac¸a˜o de base b usam-se b s´ımbolos diferentes para b d´ıgitos (de 0 a
b− 1). Os nu´meros sa˜o representados por uma sequeˆncia de d´ıgitos.
Os d´ıgitos na base 10 sa˜o 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9. Os d´ıgitos na base 2 sa˜o 0 e 1, e
normalmente sa˜o designados por bits. Por exemplo,
1011102 = 1× 25 + 0× 24 + 1× 23 + 1× 22 + 1× 21 + 0× 20
Se a = rmb
m + rm−1b
m−1 + . . . + r2b
2 + r1b
1 + r0b
0 com rm 6= 0 e 0 ≤ ri ≤ b − 1 para
0 ≤ i ≤ m enta˜o
a ≡ rm . . . r2r1r0 (b)
e´ a representac¸a˜o de a na base b. Os coeficientes r0, r1, r2, . . . rm chamam-se d´ıgitos de repre-
sentac¸a˜o de a na base b, sendo r0 o d´ıgito menos significativo e rm o d´ıgito mais significativo.
A representac¸a˜o e´ u´nica, o que e´ consequeˆncia da unicidade do quociente e resto da divisa˜o
inteira.
Proposic¸a˜o 1 (divisa˜o euclideana de inteiros) Quaisquer que sejam a ∈ Z e b ∈ Z+ existe
um e um so´ q ∈ Z e um e um so´ r ∈ Z tal que b = aq + r e 0 ≤ r < b.
A q chama-se quociente e a r resto da divisa˜o inteira de a por b, sendo importante a
condic¸a˜o 0 ≤ r < b para garantir a unicidade.
Corola´rio 1.1 Quaisquer que sejam a ∈ Z+ e b ∈ Z+ \ {1}, existem inteiros u´nicos r0, r1,
r2, . . . rm tais que a = rmb
m + rm−1b
m−1 + . . . + r2b
2 + r1b
1 + r0b
0, rm 6= 0 e 0 ≤ ri ≤ b− 1
para 0 ≤ i ≤ m.
Prova: Sejam a e b inteiros com a > 0 e b > 1. Tem-se ou a < b ou a ≥ b.
Se a < b enta˜o a = 0b + a. Portanto, 0 < r0 = a.
Se a ≥ b enta˜o, por definic¸a˜o de divisa˜o inteira, existem q0 e r0 u´nicos tais que a = bq0+r0,
com 0 ≤ r0 < b. Se q0 < b, toma-se r1 = q0 e obtem-se a = r1b + r0. Se q0 ≥ b, enta˜o o
processo repete-se agora para q0. Ou seja, q0 = bq1 + r1, com 0 ≤ r1 < b. Logo,
a = bq0 + r0 = b(bq1 + r1) + r0 = b
2q1 + br1 + r0
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 9
Se q1 < b, toma-se r2 = q0 e obtem-se a = b
2r2+br1+r0. Se q1 ≥ b, enta˜o o processo repete-se
agora para q1, e sucessivamente. O processo termina porque a > q0 > q1 > . . . e qualquer qi
e´ um inteiro na˜o negativo. ut
Esta prova indica um algoritmo para determinac¸a˜o da representac¸a˜o dum inteiro a numa
base b.
Exemplo 4 Tem-se 125(10) = 5
3 = 1000(5) = 2
6 + 25 + 24 + 23 + 22 + 20 = 1111101(2) =
175(8) = 7D(16). De facto,
125 5
0 25 5
r0 0 5 5
r1 0 1
r2
r3
125 2
1 62 2
r0 0 31 2
r1 1 15 2
r2 1 7 2
r3 1 3 2
r4 1 1
r5
r6
125 8
5 15 8
r0 7 1
r1
r2
125 16
13 7
r0
r1
No entanto, quando se conhecem poteˆncias da base, pode ser mais fa´cil determinar a
representac¸a˜o por outro me´todo. Por exemplo, para a base 2,
46(10) = 32(10) + 8(10) + 4(10) + 2(10) = 101110(2)
enquanto se se aplicar o algoritmo dado pela prova anterior teria
46 2
0 23 2
r0 1 11 2
r1 1 5 2
r2 1 2 2
r3 0 1
r4
r5
46(10) = 23× 2 + 0 = (11× 2 + 1)× 2 + 0 = ((5× 2 + 1)× 2 + 1)× 2 + 0
= (((2× 2 + 1)× 2 + 1)× 2 + 1)× 2 + 0
= ((((2 × 1 + 0)× 2 + 1)× 2 + 1)× 2 + 1)× 2 + 0
= 1× 25 + 0× 24 + 1× 23 + 1× 22 + 1× 21 + 0× 20 = 101110(2)
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 10
Pode interessar tambe´m saber qual a representac¸a˜o decimal dum inteiro dado
numa base b. Para a obter, bastara´ aplicar a definic¸a˜o e efectuar os ca´lculos na base 10.
101110(2) = 1× 25 + 0× 24 + 1× 23 + 1× 22 + 1× 21 + 0× 20 = 32 + 8 + 4 + 2 = 46(10)
101110(3) = 1× 35 + 0× 34 + 1× 33 + 1× 32 + 1× 31 + 0× 30 = 162 + 27 + 9 + 3 = 201(10)
Para ale´m da base 2, sa˜o bastante usadas em Computac¸a˜o as bases 8 (octal) e 16 (hexa-
decimal). Os d´ıgitos em octal sa˜o 0, 1, 2, 3, 4, 5, 6 e 7. Embora os restos da divisa˜o por 16
sejam 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,. . . , 15, por convenc¸a˜o, os d´ıgitos em hexadecimal
a partir de 10 sa˜o representados pelas letras maiu´sculas de A a F. Deste modo na˜o havera´
qualquer ambiguidade de representac¸a˜o (por exemplo, fica claro que o hexadecimal 15 designa
o decimal 1×16+5 e F o decimal 15). Os nu´meros representados na base octal sa˜o por vezes
indexados por (o), por exemplo 235(o), e os representados na base hexadecimal por (h), por
exemplo F15A(h).
Designac¸a˜o Base Dı´gitos
Bina´rio 2 0 a 1
Octal 8 (=23) 0 a 7
Hexadecimal 16 (=24) 0 a 9, A, B, C, D, E, F
Decimal 10 0 a 9
Exemplo 5 A sequeˆncia 78412 na˜o pode representar nenhum inteiro na base 4 porque 7, 8 e 4
na˜o sa˜o d´ıgitos base 4. A sequeˆncia 001231 na˜o e´ representac¸a˜o numa base de numerac¸a˜o,
no sentido acima definido, porque teria zeros na˜o significativos. A sequeˆncia 123100 pode
representar um inteiro em qualquer base b superior a 4.
Exerc´ıcio 2.1.1 Converter para bina´rio: 153(10), 153(6), 153(8), 153(16).
Exerc´ıcio 2.1.2 Converter para hexadecimal: 153(10), 151323(10) , 153(8), 1010101111(2) .
Exerc´ıcio 2.1.3 Converter para octal: 1123(4), 151323(10) , 153(8), 1010101111(2) .
Exerc´ıcio 2.1.4 Converter para a base 251 e 666 os seguintes nu´meros em decimal:
1383, 1498, 1500, 1580, 1640
Exerc´ıcio 2.1.5 Represente x, xn e xn − 1 na base x, para x > 1 e n ∈ N.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 11
2.1.1 Relac¸a˜o entre bina´rio, octal e hexadecimal
Seja por exemplo, 101011110(2) um bina´rio que se pretende converter para octal. Como foi
visto, o inteiro que esse bina´rio representa e´
1× 28 + 0× 27 + 1× 26 + 0× 25 + 1× 24 + 1× 23 + 1× 22 + 1× 2 + 0
ou seja 350. A representac¸a˜o octal correspondente pode ser obtida agrupando os d´ıgitos
bina´rios 3 a 3: uma vez que 8 = 23 e 82 = 26, tem-se
26(1×22 +0×2+1×2)+23(0×22 +1×2+1)+(1×22+1×2+0) = 82×5+8×3+6 = 536(2)
Em geral se ak . . . a5a4a3a2a1a0(2), sendo k ≥ 0, representa o inteiro
ak2
k + . . . + a52
5 + a42
4 + a32
3 + a22
2 + a12
1 + a02
0
enta˜o a representac¸a˜o em octal do mesmo inteiro pode ser obtida da forma descrita:
ak2
k + . . . + 23(a52
2 + a42
1 + a32
0) + (a22
2 + a12
1 + a02
0) =
ak2
k + . . . + 8(a52
2 + a42
1 + a32
0) + (a22
2 + a12
1 + a02
0)
Notar que na expressa˜o resultante, qualquer poteˆncia de 8 tem por coeficiente
ai+22
2 + ai+12 + ai
para algum i, o qual e´ sempre na˜o negativo e inferior a 8, podendo assim ser d´ıgito da
representac¸a˜o octal. A cada d´ıgito octal correspondem 3 d´ıgitos em bina´rio. Do mesmo
modo, a cada d´ıgito hexadecimal correspondem 4 d´ıgitos em bina´rio. Assim, para converter
um bina´rio a hexadecimal, agrupam-se os seus d´ıgitos em grupos de 4 (da direita para a
esquerda) correspondendo a cada um desses grupos um d´ıgito hexadecimal. Por exemplo,
101011110(2) ⇒ 1 | 0101 | 1110⇒ 1 | 5 | E ⇒ 15E(h)
Para converter um bina´rio a octal procede-se de modo ideˆntico mas formando grupos de 3.
Por exemplo,
101011110(2) ⇒ 101 | 011 | 110⇒ 5 | 3 | 6⇒ 536(o)
Inversamente, se se pretender converter de hexadecimal a bina´rio basta associar a cada um
dos d´ıgitos hexadecimal o grupo de 4 d´ıgitos bina´rios correspondente. Por exemplo,
3AC3A(h) ⇒ 0011 | 1010 | 1100| 0011 | 1010⇒
11 | 1010 | 1100 | 0011 | 1010⇒ 111010110000111010(2)
Notar a eliminac¸a˜o dos zeros na˜o significativos. O que se acaba de ilustrar e´ um caso particular
da proposic¸a˜o seguinte.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 12
Proposic¸a˜o 2 Se z e´ um inteiro positivo, a cada d´ıgito (com poss´ıvel excepc¸a˜o do mais signi-
ficativo) da representac¸a˜o de z na base bn corresponde um grupo de n d´ıgitos na representac¸a˜o
de z na base b, qualquer que seja n inteiro positivo. Mais concretamente, se
akak−1 . . . atnatn−1 . . . a2na2n−1 . . . anan−1 . . . a1a0
com k ≥ 0 e´ a representac¸a˜o na base b de um inteiro positivo z enta˜o, a representac¸a˜o do
mesmo inteiro na base bn e´
wtwt−1 . . . w1w0
sendo t+1 o nu´mero de blocos de n d´ıgitos da representac¸a˜o de z na base b (podendo o u´ltimo
ser completado por zeros na˜o significativos), e wi (i ≤ t) o d´ıgito da base bn que representa o
inteiro a2in−1 . . . ain+1ain(b) (representac¸a˜o base b a menos de zeros na˜o significativos).
Exemplo 6 Por exemplo, para converter 100313210(4) para a base 16, agrupam-se os d´ıgitos
2 a 2, da direita para a esquerda, pois 16 = 42.
100313210(4) = 01 | 00 | 31 | 32 | 10 = 10DE4(16)
Exerc´ıcio 2.1.6 Repita os exerc´ıcios 2.1.1 a 2.1.3.
Exerc´ıcio 2.1.7 Mostre a proposic¸a˜o anterior. Comece por mostrar que wtwt−1 . . . w1w0
conforme descrito pode ser representac¸a˜o base bn de z; use em seguida o facto da representac¸a˜o
numa base ser u´nica para concluir que wtwt−1 . . . w1w0 e´ a representac¸a˜o de z. Mostre depois
que se wtwt−1 . . . w1w0 representa z na base b
n, a representac¸a˜o de z na base b e´
akak−1 . . . atnatn−1 . . . a2na2n−1 . . . anan−1 . . . a1a0
2.1.2 Adic¸a˜o e multiplicac¸a˜o na base b
Recorde como se adicionam dois inteiros representados na base 10, calculando por exemplo
987654 + 73561.
987654
+ 73561
. . . 5
(vai 0)
987654
+ 73561
. . . 15
(vai 1)
987654
+ 73561
. . . 215
(vai 1)
987654
+ 73561
. . . 1215
(vai 1)
987654
+ 73561
. . . 61215
(vai 1)
987654
+ 73561
. . . 061215
(vai 1)
987654
+ 73561
1061215
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 13
Algoritmo para Adic¸a˜o (base 10). Se x e y sa˜o inteiros positivos representados na
base 10 por xkxk−1 . . . x1x0 e ymym−1 . . . y1y0 respectivamente enta˜o a representac¸a˜o na
base 10 de x + y, digamos spsp−1 . . . s1s0, pode ser obtida da forma seguinte.
xkxk−1 . . . x1x0
+ ymym−1ym−2 . . . y1y0
. . . s0
Caso x0 + y0 < 10, toma-se s0 = x0 + y0 e repete-se o processo para os d´ıgitos seguintes.
Sena˜o, s0 e´ tal que x0 + y0 = 1s0, adicionando-se 1 a x1 + y1 repetindo-se o processo (global)
para os d´ıgitos seguintes. Quando k < m (respectivamente m < k) pode-se considerar xi = 0,
i ≥ k (respectivamente yi = 0, i ≥ m). Notar que p = max(k,m) ou p = max(k,m) + 1
sendo neste u´ltimo caso sp = 1.
Adic¸a˜o (base 3). 2102(3) + 21(3) = (2× 33 + 1× 32 + 0× 31 + 2× 30) + (2× 31 + 1× 30) =
2× 33 +1× 32 +(0+2)× 31 +(2 + 1)× 30 = 2× 33 +1× 32 +(0+2)× 31 +(1× 3 + 0)× 30 =
2 × 33 + 1 × 32 + (0 + 2 + 1) × 31 + 0 × 30 = 2 × 33 + (1 + 1) × 32 + 0 × 31 + 0 × 30 =
2× 33 + 2× 32 + 0× 31 + 0× 30.
2102(3)
+ 21(3)
. . . 0(3)
(vai 1)
2102(3)
+ 21(3)
. . . 00(3)
(vai 1)
2102(3)
+ 21(3)
. . . 200(3)
(vai 0)
2102(3)
+ 21(3)
2200(3)
Exerc´ıcio 2.1.8 Justifique que se x e y sa˜o inteiros positivos representados na base b por
xkxk−1 . . . x1x0 e ymym−1 . . . y1y0 respectivamente enta˜o spsp−1 . . . s1s0, a representac¸a˜o na
base b de x+y, pode ser obtida por um processo ana´logo ao descrito acima, ou seja, seguindo
o algoritmo habitual. Comece por notar que quando soma xi com yi o resultado e´ sempre
menor ou igual que 2b − 2, e portanto tanto xi + yi como xi + yi + 1 se representa como
0si ou 1si (pelo que ou “vai 0” ou “vai 1”), qualquer que seja i. Depois, use a definic¸a˜o de
representac¸a˜o na base b, a` semelhanc¸a do que se fez acima para b = 3.
Os algoritmos usuais para adic¸a˜o e multiplicac¸a˜o base 10 sa˜o va´lidos quando se usam
representac¸o˜es em qualquer outra base b, embora sejam obviamente diferentes as tabuadas
dessas operac¸o˜es se escrevermos os resultados na base b. O mesmo se pode dizer para a
subtracc¸a˜o (quando o aditivo e´ maior do que subtractivo) e para a divisa˜o inteira.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 14
Tabuadas de adic¸a˜o e multiplicac¸a˜o para bina´rio:
+2 0 1
0 0 1
1 1 10
×2 0 1
0 0 0
1 0 1
Tabuadas de adic¸a˜o e multiplicac¸a˜o para base 3:
+3 0 1 2
0 0 1 2
1 1 2 10
2 2 10 11
×3 0 1 2
0 0 0 0
1 0 1 2
2 0 2 11
Tabuadas de adic¸a˜o e multiplicac¸a˜o para octal:
+8 0 1 2 3 4 5 6 7
0 0 1 2 3 4 5 6 7
1 1 2 3 4 5 6 7 10
2 2 3 4 5 6 7 10 11
3 3 4 5 6 7 10 11 12
4 4 5 6 7 10 11 12 13
5 5 6 7 10 11 12 13 14
6 6 7 10 11 12 13 14 15
7 7 10 11 12 13 14 15 16
×8 0 1 2 3 4 5 6 7
0 0 0 0 0 0 0 0 0
1 0 1 2 3 4 5 6 7
2 0 2 4 6 10 12 14 16
3 0 3 6 11 14 17 22 25
4 0 4 10 14 20 24 30 34
5 0 5 12 17 . . . . . . . . . . . . . . .
6 0 6 . . . . . . . . . . . . . . . . . . . . . . . .
7 0 7 . . . . . . . . . . . . . . . . . . . 61
Exerc´ıcio 2.1.9 Complete a tabuada de multiplicac¸a˜o base 8 e determine as tabelas para a
base hexadecimal.
Assim, por exemplo, 1021(3) × 211(3) = 1000201(3) , ou seja, 34(10) × 22(10) = 748(10),
porque:
1 0 2 1(3)
× 2 1 1(3)
1 0 2 1
1 0 2 1
+ 2 1 1 2
1 0 0 0 2 0 1(3)
3 4(10)
× 2 2(10)
6 8
+ 6 8
7 4 8(10)
A` esquerda, todos os valores interme´dios esta˜o representados na base 3 e a` direita na base 10
(visando recordar o algoritmo da multiplicac¸a˜o e estabelecer a comparac¸a˜o).
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 15
Exerc´ıcio 2.1.10 Calcule:
(i) 1110010(2) + 111001111(2) em bina´rio.
(ii) 1F5(h) + 111001111(2) em hexadecimal.
(iii) 1330(4) + 123(4) em octal.
(iv) 1F5(h) + ABCD(h) + 1FB(h) em hexadecimal.
(v) ABCD(h) − 1FB(h) em hexadecimal.
(vi) 73542(o) × 27(10) em octal.
(vii) 73542(o)/27(10) em octal.
(viii) 111000010(2)/111(2) em bina´rio.
2.1.3 Representac¸a˜o de nu´meros com um nu´mero fixo de d´ıgitos
Num computador cada inteiro e´ representado por um nu´mero fixo de bits. Em 8 bits, 13 seria
representado por 00001101. Isto e´, introduzem-se 0’s a` esquerda sempre que o nu´mero de bits
da representac¸a˜o do inteiro seja menor que o nu´mero de bits que se fixou.
Se n representar o nu´mero de bits que se fixou para a representac¸a˜o, os bits sa˜o numerados
da esquerda para a direita por bitn−1, bitn−2, . . . , bit1 e bit0. O bitn−1 diz-se o bit mais
significativo e bit0 e´ o menos significativo.
Quando se fixa o nu´mero de bits da representac¸a˜o, limita-se tambe´m os valores que podem
ser representados. Se, por exemplo, o nu´mero de bits for 8 enta˜o o maior inteiro positivo que
se pode representar e´:
1 1 1 1 1 1 1 1
bit 7 bit 6 bit 5 bit 4 bit 3 bit 2 bit 1 bit 0
cujo valor e´
27 × 1 + 26 × 1 + 25 × 1 + 24 × 1 + 23 × 1 + 22 × 1 + 21 × 1 + 20 × 1 = 255 = 28 − 1
Em geral, com n bits podemos representar nu´meros inteiros positivos de 0 a 2n − 1.
Proposic¸a˜o 3 O maior inteiro positivo que se consegue representar na base b com n d´ıgitos
e´ bn − 1.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 16
Prova: Suponhamos que A e´ representado com n d´ıgitos na base b por an−1an−2 . . . a1a0
com ai ∈ {0, . . . , b− 1}. Enta˜o,
A = an−1b
n−1 + an−2b
n−2 . . . a1b
1 + a0b
0 =
n−1∑i=0
aib
i
Ora,
n−1∑
i=0
aib
i ≤
n−1∑
i=0
(b− 1)bi
= (b− 1)
n−1∑
i=0
bi
= (b− 1)b
0 − b× bn−1
1− b (soma de termos de progressa˜o geome´trica)
= (b− 1)1− b
n
1− b
= bn − 1
ut
Observac¸a˜o:
∑n−1
i=0 ui e´ uma notac¸a˜o abreviada para u0 + u1 + · · · + un−1, podendo-se ler
“somato´rio para i desde 0 ate´ n− 1 de ui”.
Exerc´ıcio 2.1.11 Qual e´ o nu´mero mı´nimo de bits necessa´rio para representar 1125? Qual
o valor ma´ximo que pode ser representado com esse nu´mero de bits?
Normalmente o nu´mero de bits usados sa˜o 8, 16, 32 ou 64. Com 8 bits podemos representar
inteiros entre 0 e 255, com 16 bits entre 0 e 65535, com 32 bits entre 0 a 4294967295, etc.
2.1.4 Representac¸a˜o de nu´meros negativos
Para representar nu´meros inteiros positivos e negativos numa base b e com um nu´mero fixo
de d´ıgitos e´ necessa´rio codificar o sinal e encontrar um processo eficiente de determinar se
um nu´mero e´ positivo ou negativo. Normalmente e´ reservado um d´ıgito para indicar o sinal.
Por exemplo, em n d´ıgitos, sendo A = an−1an−2 . . . a1a0(b), se an−1 = 0 enta˜o A e´ positivo,
se an−1 = b− 1 o nu´mero e´ negativo.
Vamos considerar treˆs formas introduzidas para representar nu´meros inteiros positivos e
negativos e que obedecem a` condic¸a˜o de sinal apresentada. Vamos supor que a base e´ 2 e que
o nu´mero de d´ıgitos e´ n, embora os resultados possam ser generalizados para qualquer base b.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 17
Representac¸a˜o com bit de sinal. Reserva-se o bit mais a` esquerda para o sinal e os
restantes para o mo´dulo do nu´mero.
n bits︷ ︸︸ ︷
n−1 n−2 . . . . . . . . 0
sinal mo´dulo
O bit de sinal e´ 0 para os positivos e e´ 1 para os negativos. Assim, um nu´mero positivo
e´ da forma A = 0an−2 . . . a1a0 e um negativo e´ da forma A = 1an−2 . . . a1a0. Com n bits
podemos representar nu´meros positivos de 0 a 2n−1 − 1 e negativos −(2n−1 − 1) a 0.
As representac¸o˜es de dois nu´meros com o mesmo mo´dulo diferem apenas no bit de sinal.
Se n = 3 temos o quadro seguinte:
Valor 0 1 2 3 −0 −1 −2 −3
Representac¸a˜o com bit de sinal 000 001 010 011 100 101 110 111
Podemos observar que zero tem duas representac¸o˜es: +0 e −0. Para efectuar adic¸o˜es
de nu´meros com sinais diferentes e´ necessa´rio primeiro determinar qual e´ o maior e qual o
sinal do resultado. O mesmo problema surge para a subtracc¸a˜o, a qual pode ser tratada como
a adic¸a˜o associando o sinal negativo ao subtraendo, x− y = x + (−y).
Representac¸a˜o em Complemento para 1. A utilizac¸a˜o desta representac¸a˜o para inteiros
apresenta o mesmo problema da anterior, isto e´, zero tera´ duas representac¸o˜es +0 e −0. Para
uma representac¸a˜o em n bits, chama-se complemento para 1 de A ao valor (2n − 1) − A.
O bit mais signficativo da´ indicac¸a˜o sobre o sinal do nu´mero (se for 1, o nu´mero e´ negativo).
O nu´mero negativo −x sera´ representado por (2n − 1) − x. Por exemplo, para n = 3, temos
o quadro seguinte:
Valor +0 +1 +2 +3 −3 −2 −1 −0
Complemento para 1 000 001 010 011 100 101 110 111
Estas representac¸o˜es podem ser obtidas por troca de 1’s por 0’s e 0’s por 1’s na repre-
sentac¸a˜o de x em n bits, o que resulta de 2n− 1 ser representado por n 1’s. Por exemplo, -14
e´ representado em complemento para 1 em 8 bits por:
1 1 1 1 1 1 1 1
− 0 0 0 0 1 1 1 0
1 1 1 1 0 0 0 1
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.1. SISTEMA DE REPRESENTAC¸A˜O POSICIONAL 18
Representac¸a˜o em Complemento para 2. Neste caso, zero tera´ uma so´ representac¸a˜o:
Exactamente metade dos nu´meros representados sa˜o na˜o negativos e a outra metade nu´meros
negativos.
De 0 a 2n−1−1 encontram-se os nu´meros na˜o negativos e de 2n−1 a 2n−1 nu´meros
negativos.
Para os positivos a representac¸a˜o coincide com a representac¸a˜o anterior. Os nu´meros nega-
tivos sa˜o complementos para a base. Por definic¸a˜o, o complemento para 2 de A numa
representac¸a˜o de n bits e´ o inteiro 2n −A.
Exemplo 7 Para n = 3 enta˜o -1 e´ representado por 111 pois 23 − 1 = 7. Se n = 8, o
inteiro -1 e´ representado por 11111111 em complemento para 2. Nnuma representac¸a˜o em 8
bits usando complemento para 2 o inteiro −3 e´ o bina´rio correspondente a 28 − 3, ou seja
253 = 11111101.
Em resumo, temos o quadro seguinte para n = 3:
Valor 0 +1 +2 +3 −4 −3 −2 −1
Complemento para 2 000 001 010 011 100 101 110 111
Usando a definic¸a˜o de complemento para 2, pode-se concluir que 2n−1 representa −2n−1
pois 2n − 2n−1 = 2n−1. Por outro lado, 2n − 1 representa −1.
Proposic¸a˜o 4 No sistema de representac¸a˜o com n bits e complemento para 2 os valores
poss´ıveis dos inteiros representa´veis variam de −2n−1 a 2n−1 − 1. De 0 a 2n−1 − 1 tem-se
nu´meros na˜o negativos e de 2n−1 a 2n − 1 nu´meros negativos.
Para ale´m de so´ haver um zero, neste caso todos os negativos teˆm 1 como bit mais
significativo, o qual funciona assim como bit de sinal. As adic¸o˜es podem ser efectuadas
sem analisar o sinal dos operandos e nas subtracc¸o˜es basta calcular o complemento para 2 do
subtraendo e adicionar o valor resultante ao subtractivo, como se vera´ adiante.
Para determinar representac¸a˜o em complemento para 2 dum nu´mero e´ u´til observar
a sua relac¸a˜o com a representac¸a˜o em complemento para 1.
Como 2n −A = (2n − 1−A) + 1 e 2n − 1−A e´ a representac¸a˜o em complemento para 1,
podemos obter a representac¸a˜o em complemento para 2 complementando todos os d´ıgitos
de A (isto e´ trocando os uns com os zeros e os zeros com os uns) e adicionando depois uma
unidade.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.2. ADIC¸A˜O E SUBTRACC¸A˜O EM N BITS 19
Exemplo 8 Para determinar a representac¸a˜o de -17 em complemento para 2 em 8 bits,
toma-se 00010001, troca-se 0’s por 1’s, obtendo 11101110, e soma-se 1, resultando 11101111.
Inversamente, se se pretender determinar o valor (em decimal) do inteiro que e´ dado em
complemento para 2 por A = an−1an−2 . . . a1a0, basta considerar que a parcela an−12
n−1 e´
negativa. Por exemplo,
110(2) = 1× (−22) + 1× 21 + 0× 20 = −4 + 2 + 0 = −2(10)
Exerc´ıcio 2.1.12 Represente em complemento para 2 e com 8 bits os nu´meros inteiros se-
guintes:
(i) 25, -25, 41, 56, 19, -31, -87;
(ii) a soma dos anteriores e verifique se o resultado de somar as representac¸o˜es esta´ correcto.
Exerc´ıcio 2.1.13 Suponha que a representac¸a˜o em complemento para dois com 4 d´ıgitos de
um inteiro e´ 1101. Como e´ a representac¸a˜o com:
(i) 6 d´ıgitos
(ii) 8 d´ıgitos
(iii) n d´ıgitos, com n ≥ 4.
Exerc´ıcio 2.1.14 Suponha agora que, em 4 d´ıgitos, a representac¸a˜o em complemento para
dois e´ 0101. Como responderia a`s al´ıneas anteriores? Em geral, dado um inteiro x represen-
tado em n d´ıgitos como procederia para obter a sua representac¸a˜o com mais d´ıgitos?
2.2 Adic¸a˜o e Subtracc¸a˜o em n Bits
2.2.1 Adic¸a˜o e subtracc¸a˜o bina´ria de inteiros na˜o negativos
• Adic¸a˜o: Segue o algoritmo habitual de adic¸a˜o bina´ria; se se tiver uma representac¸a˜o de
m bits e a soma for superior a 2m − 1 (o maior inteiro positivo com m bits) diz-se que
ha´ transporte (carry); Por exemplo: a soma em 8-bits dos inteiros positivos 10010000
e 11111101 e´ 10001101, o que esta´ errado (tem transporte 1).
• Subtracc¸a˜o: Segue algoritmo habitual de subtracc¸a˜o bina´ria; se o valor da diferenc¸a for
inferior a zero, diz-se que ha´ transporte (borrow); Por exemplo: a diferenc¸a em 8-bits
10010000 − 11111101 = 10010011 o que esta´ errado (tem transporte 1).
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.2. ADIC¸A˜O E SUBTRACC¸A˜O EM N BITS 20
2.2.2 Adic¸a˜o de inteiros em complemento para 2
Se os inteiros sa˜o na˜o negativos, a soma e´ calculada pelo algoritmo habitual. Sea repre-
sentac¸a˜o tiver m bits e a soma for superior a 2m−1 − 1 (o maior inteiro positivo com m bits
num sistema de complemento para 2) diz-se que ha´ overflow, sendo indicac¸a˜o de que o valor
obtido esta´ errado.
Por exemplo: a soma em 8-bits e complemento para 2 de 01111111 com 00000001 e´
10000000 ou seja, a soma de +127 com +1 e´ −128(!). Neste caso, ha´ overflow.
Se os inteiros sa˜o ambos negativos (em complemento para 2) a soma e´ calculada pelo
algoritmo habitual ”desprezando-se”o transporte. Se se usa uma representac¸a˜o em m bits,
o ”desprezar”o transporte corresponde a subtrair ao resultado obtido 2m. Basta notar que
quando se efectua (−x) + (−y) se pretende obter o complemento para 2 de x + y, isto e´
2m− (x + y). A relac¸a˜o desse nu´mero com os complementos para 2 de x e y e´ 2m− (x + y) =
(2m − x) + (2m − y) − 2m. Ou seja, para obter a representac¸a˜o em complemento para 2 de
(−x) + (−y) adicionam-se as representac¸o˜es de (−x) e (−y) e subtrai-se 2m.
Se a representac¸a˜o tiver m bits e a soma for inferior a −2m−1 (o menor inteiro negativo
com m bits num sistema de complemento para 2) diz-se que ha´ underflow, sendo indicac¸a˜o
de que o valor obtido esta´ errado.
Por exemplo: a soma em 8-bits e complemento para 2 de 10000000 com 11111111 seria
01111111 ou seja, −128 + (−1) = +127 (!). Neste caso, ha´ underflow.
Analogamente, a soma dum inteiro positivo com um inteiro negativo e´ o bina´rio correspon-
dente a` adic¸a˜o das representac¸o˜es dos operandos, ”desprezando-se”o transporte se o houver.
Na˜o havera´ overflow nem underflow.
2.2.3 Subtracc¸a˜o de inteiros em complemento para 2
A subtracc¸a˜o bina´ria de inteiros representados em complemento para 2 pode-se reduzir a`
adic¸a˜o de inteiros.
Exemplos
(-x)-(-y) = (-x)+y 10010000-11111101=10010000+00000011=10010011
(-x)-y=(-x)+(-y) 10010000-00000011=10010000+11111101=10001101
y-(-x)=y+x 00000011-10010000=00000011+ 01110000=01110011
y-x=y+(-x) 00000011-00010000=00000011+11110000=11110011
Exerc´ıcio 2.2.1 Quais das seguintes somas esta˜o correctas (se truncadas a 8 bits) caso as
representac¸o˜es indicadas sejam representac¸o˜es em complemento para 2 e caso sejam repre-
sentac¸o˜es so´ para inteiros na˜o negativos?
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.3. REPRESENTAC¸A˜O EM VI´RGULA FIXA 21
negativos negativo e positivo positivos
10010000
+ 11111101
1 10001101
00010000
+ 11111111
1 00001111
00010000
+ 00111101
0 01001101
positivos negativos
01111010
+ 01110001
0 11101011 < 0
10000110
+ 10001111
1 00010101 > 0
overflow underflow
2.3 Representac¸a˜o em Vı´rgula Fixa
A representac¸a˜o posicional de inteiros pode ser generalizada para representar nu´meros racio-
nais considerando-se poteˆncias negativas da base. Por exemplo, na base 10:
344.45 = 3× 102 + 4× 101 + 4× 100 + 4× 10−1 + 5× 10−2
Podemos ainda escrever:
344.45 = 34445. × 10−2 = (3× 104 + 4× 103 + 4× 102 + 4× 101 + 5× 100)× 10−2
Se se fixar a posic¸a˜o da v´ırgula (neste caso o factor e´ 10−2), o nu´mero pode ser tratado
como um inteiro. Assim as operac¸o˜es com nu´meros racionais podem ser feitas internamente
como operac¸o˜es com inteiros, desde que os factores de ajuste sejam guardados para que o
resultado final seja correctamente calculado.
Note-se em particular que as representac¸o˜es de inteiros em computadores estudadas anteri-
ormente sa˜o representac¸o˜es em v´ırgula fixa, com a v´ırgula a` direita do bit menos significativo.
No caso geral, os ajustes da posic¸a˜o da v´ırgula e o seu armazenamento ficara˜o a cargo do
programador.
Contudo, actualmente, a representac¸a˜o em computadores dos nu´meros racionais e´ feita,
geralmente, em v´ırgula flutuante.
2.4 Representac¸a˜o em Vı´rgula Flutuante
A representac¸a˜o dum nu´mero racional em v´ırgula flutuante, contrariamente a` representac¸a˜o
em v´ırgula fixa, e´ feita atrave´s de um par de inteiros que representam respectivamente a
mantissa m e o expoente e de forma que para uma determinada base b, o seu valor e´:
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
2.4. REPRESENTAC¸A˜O EM VI´RGULA FLUTUANTE 22
F = m× be
Por exemplo, 673 × 1014.
A designac¸a˜o v´ırgula flutuante resulta do facto de que a posic¸a˜o da v´ırgula depender do
expoente e portanto na˜o ser fixada previamente.
A notac¸a˜o mais usada para v´ırgula flutuante e´ a do IEEE (Institute of Electrical and
Electronics Engineers). A base e´ a bina´ria. Em precisa˜o simples cada nu´mero e´ representado
com 32 bits:
S E (8 bits) M (23 bits)
O sinal da mantissa e´ representado pelo bit S, que por questo˜es de eficieˆncia e´ separado
da representac¸a˜o do mo´dulo da mantissa o qual e´ constitu´ıdo pelos 23 bits mais a` direita. O
valor do mo´dulo da mantissa e´ normalmente dado por 1.M(2), isto e´, 1 mais o valor de M
considerado como nu´mero racional bina´rio, com a v´ırgula a` esquerda do bit mais significativo.
Os oito bits restantes sa˜o interpretados como um inteiro positivo E e representam o expoente
cujo valor e´ E − 127. O valor representado e´
F = (−1)S(2E−127)(1.M)(2)
excepto se E for 0000000 enta˜o F = (−1)S(2−127)(.M(2)) e se M tambe´m e´ zero enta˜o F = 0.
A sequeˆncia 1 10000111 10100000000000000000000 representaria um nu´mero negativo,
dado que S = 1. Como 10000111(2) = 135(10), o expoente e´ 135 − 127 = 8; e o mo´dulo da
mantissa e´
1 + 0.101(2) = 1 + 1× 2−1 + 1× 2−3 = 1 + (5/8) = 1 + 0.625 = 1.625
O valor representado e´ −28 × 1.625 = −416.
Existem outras representac¸o˜es em v´ırgula flutuante IEEE, como a precisa˜o dupla em que
sa˜o usados 64 bits e a qua´drupla em que sa˜o usados 128 bits.
Exerc´ıcio 2.4.1 Determine qual o maior nu´mero que e´ representa´vel em precisa˜o simples,
segunda a norma do IEEE.
Exerc´ıcio 2.4.2 Indique o valor das seguintes representac¸o˜es em precisa˜o simples segunda a
norma do IEEE:
(i) 0 01110101 01010100000000000000000000
(ii) 1 00101010 11100000000000000000000000
Exerc´ıcio 2.4.3 Exprima o mais exactamente poss´ıvel os seguintes nu´meros em precisa˜o
simples IEEE: 2.5, .0005, 2−40 e 256
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
Cap´ıtulo 3
Algumas Noc¸o˜es de Divisibilidade
Por definic¸a˜o, um inteiro a e´ divis´ıvel por um inteiro b se e so´ se a = bq para algum inteiro q.
Nesse caso, escreve-se b | a, lendo-se b divide a. Tambe´m se diz que b e´ divisor de a e
que a e´ mu´ltiplo de b. O inteiro q e´ o quociente da divisa˜o inteira de a por b. Atendendo
a` definic¸a˜o de divisor, se a = bq enta˜o tanto b como q sa˜o divisores de a. Por exemplo, os
divisores positivos de 30 sa˜o 1, 2, 3, 5, 6, 10, 15 e 30, encontrando-se emparelhados.
1 302 15
3 10
5 6
Na procura de divisores de a, para a positivo, na˜o e´ necessa´rio ultrapassar
√
a, pois qualquer
divisor que seja superior a
√
a tera´ que emparelhar com algum divisor que e´ inferior a
√
a.
3.1 Bases de Numerac¸a˜o e Crite´rios de Divisibilidade
E´ conhecido que, um inteiro positivo representado na base 10 e´ divis´ıvel por 100 se e so´ se a
sua representac¸a˜o terminar por 00 (pois os restos da divisa˜o por 10 e 102 sa˜o 0). E´ divis´ıvel
por 1000 sse tal representac¸a˜o terminar em 000. De modo ana´logo se pode concluir que um
inteiro (positivo) representado na base 2 e´ divis´ıvel por 4 (isto e´, por 22) se a sua representac¸a˜o
em bina´rio terminar por 00 e e´ divis´ıvel por 8 (isto e´, por 23) sse terminar em 000.
Proposic¸a˜o 5 Um inteiro (positivo) x representado numa certa base b e´ divis´ıvel por bk,
sendo k inteiro positivo fixo, se e so´ a representac¸a˜o de x na base b terminar por k zeros.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
3.1. BASES DE NUMERAC¸A˜O E CRITE´RIOS DE DIVISIBILIDADE 24
Ideia da prova: Para que xseja divis´ıvel por bk enta˜o tera´ que ser divis´ıvel tambe´m por
b1, b2, . . . , bk−1, o que quer dizer que se efectuar k diviso˜es sucessivas por b tera´ k restos 0.
Ou seja, x = b(x/b) + 0. Depois, k > 1, tambe´m (x/b) = b((x/b)/b) + 0, . . . ut
Analisando a definic¸a˜o de representac¸a˜o base 10, podemos justificar o seguinte crite´rio de
divisibilidade por 9.
Proposic¸a˜o 6 Um inteiro e´ divis´ıvel por 9 sse a soma dos d´ıgitos da sua representac¸a˜o na
base 10 for divis´ıvel por 9.
Prova: Seja x um inteiro (positivo) qualquer e suponhamos que a sua representac¸a˜o
base 10 e´ anan−1 . . . a1a0. Isto quer dizer que,
x = an × 10n + an−1 × 10n−1 + · · ·+ a1 × 10 + a0
Como
10 = 9 + 1 um mu´ltiplo de 9 mais uma unidade
100 = 99 + 1 um mu´ltiplo de 9 mais uma unidade
1000 = 999 + 1 um mu´ltiplo de 9 mais uma unidade
...
10n = 99 . . . 9︸ ︷︷ ︸
9 repetido n vezes
+1 um mu´ltiplo de 9 mais uma unidade
enta˜o x = (9˙ + 1)× an + (9˙ + 1)× an−1 + · · ·+ (9˙ + 1)× a1 + a0, ou seja
x = 9˙ + (an + an−1 + · · ·+ a1 + a0)
em que 9˙ e´ abreviatura de “um mu´ltiplo de 9” (nesta igualdade, cada ocorreˆncia de 9˙ designa
um mu´ltiplo diferente). Na “simplificac¸a˜o” da igualdade, usa´mos tambe´m o facto da soma
de mu´ltiplos de 9 ser um mu´ltiplo de 9 e do produto dum nu´mero qualquer por um mu´ltiplo
de 9 ser um mu´ltiplo de 9. Observando que x = 9˙ + (an + an−1 + · · · + a1 + a0), concluimos
que x e´ mu´ltiplo de 9˙ se e so´ se an + an−1 + · · ·+ a1 + a0 for mu´ltiplo de 9˙. ut
O exerc´ıcio seguinte pode ser resolvido por aplicac¸a˜o dum racioc´ınio ana´logo, agora obser-
vando que 10 = 1˙1−1, 100 = 1˙1+1, 1000 = 1˙1−1, 1000 = 1000×10 = (1˙1−1)(1˙1−1) = 1˙1+1,
10000 = (1˙1 + 1)× 10 = 1˙1− 1, . . .
Exerc´ıcio 3.1.1 Mostre que um inteiro e´ divis´ıvel por 11 sse a soma dos d´ıgitos de ordem
par da sua representac¸a˜o na base 10 for igual a` soma dos d´ıgitos de ordem ı´mpar.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
3.2. NOC¸A˜O DE DIVISOR E DE MU´LTIPLO 25
Exerc´ıcio 3.1.2 Mostre que um inteiro
(i) e´ divis´ıvel por 5 sse a sua representac¸a˜o decimal terminar em 0 ou 5;
(ii) e´ divis´ıvel por 3 sse a soma dos d´ıgitos da sua representac¸a˜o decimal for divis´ıvel por 3.
(iii) e´ divis´ıvel por 2 sse o d´ıgito menos significativo da sua representac¸a˜o decimal for par.
3.2 Noc¸a˜o de Divisor e de Mu´ltiplo
O conjunto1 dos divisores dum inteiro a e´ constitu´ıdo por todos os inteiros positivos tais que
se b | a e os seus sime´tricos.
{divisores de a} = {b : b ∈ Z e b divide a}
Frequentemente, o termo divisor e´ usado para referir divisor positivo.
O conjunto dos mu´ltiplos de b e´ constitu´ıdo pelos inteiros da forma bz para z inteiro, ou
seja
{mu´ltiplos de b} = {bz : z ∈ Z}.
Para mostrar formalmente o resultado seguinte basta usar a definic¸a˜o de mu´ltiplo e de
divisor que acaba´mos de apresentar. Este resultado foi utilizado na secc¸a˜o anterior, devendo
ser bem conhecido.
Proposic¸a˜o 7 A soma, a diferenc¸a e o produto de dois mu´ltiplos de b e´ um mu´ltiplo de b.
O produto dum mu´ltiplo de b por qualquer inteiro e´ um mu´ltiplo de b.
Prova: Sejam m1 e m2 mu´ltiplos de b. Enta˜o existem inteiros z1 e z2 tais que m1 = bz1
e m2 = bz2. Logo, m1 + m2 = bz1 + bz2 = b(z1 + z2) e como a soma de inteiros e´ um inteiro,
conclui-se que z1+z2 ∈ Z, pelo que m1+m2 e´ da forma bz, para algum z ∈ Z (concretamente,
para z = z1 + z2). Portanto, a soma de mu´ltiplos de b e´ mu´ltiplo de b.
Para mostrar que a diferenc¸a de dois mu´ltiplos de b (isto e´, m1 − m2) e´ mu´ltiplo de b
procede-se analogamente.
Para mostrar que m1m2 e´ mu´ltiplo de b, isto e´, que o produto de dois mu´ltiplos de b e´
mu´ltiplo de b, observe-se que m1m2 = (bz1)(bz2) = b(bz1z2) e como bz1z2 ∈ Z, conclui-se que
m1m2 e´ produto de b por um inteiro, ou seja, e´ mu´ltiplo de b.
Do mesmo modo, para concluir que o produto dum mu´ltiplo de b (por exemplo, m1) por
um qualquer inteiro x e´ mu´ltiplo de b, basta notar que m1x = (bz1)x = b(z1x) e z1x ∈ Z. ut
1E´ usual representar “o conjunto dos x’s tais que x satisfaz condic¸a˜o. . . ” por {x | x satisfaz condic¸a˜o . . . }.
Neste cap´ıtulo, usaremos a notac¸a˜o alternativa {x : x satisfaz condic¸a˜o . . . }, para evitar usar | com duplo
significado, reservando | para “divide”.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
3.3. FACTORIZAC¸A˜O EM PRIMOS 26
Exerc´ıcio 3.2.1 Mostrar que quaisquer que sejam x, y e z inteiros, se x dividir y e dividir
y + z enta˜o tambe´m divide z.
3.3 Factorizac¸a˜o em Primos
Um nu´mero p e´ primo se e so´ se tem exactamente quatro divisores (inteiros), nomeadamente,
p, −p, 1 e −1. Assim, um nu´mero e´ primo se e so´ se tem exactamente dois divisores positivos.
Proposic¸a˜o 8 Qualquer inteiro maior do que 1 e´ ou primo ou produto de primos.
Prova: Pela definic¸a˜o de primo, tem-se 2 e´ primo.
Seja x ∈ N tal que x > 2. Suponhamos que ja´ mostra´mos que todo y ∈ N tal que 2 ≤ y < x
e´ ou primo ou produto de primos. Vamos mostrar que enta˜o tambe´m podemos concluir que
x e´ primo ou produto de primos. De facto, se x na˜o for primo, existem x1, x2 ∈ N \ {0, 1}
tais que x = x1x2. Como 2 ≤ x1 < x e 2 ≤ x2 < x, sabemos ja´ que x1 e´ primo ou produto de
primos e x2 e´ primo ou produto de primos.
Analisando os quatro casos (a) x1 e x2 primos, (b) x1 e x2 produtos de primos, (c) x1
primo e x2 produto de primos, e (d) x1 produto de primos e x2 primo, concluimos que se
x = x1x2 enta˜o x pode escrever-se como produto de primos. Logo, se x na˜o e´ primo enta˜o x
e´ um produto de primos, ou seja, x e´ primo ou produto de primos. ut
A te´cnica utilizada na prova anterior designa-se por induc¸a˜o matema´tica. Como
hipo´tese de induc¸a˜o supusemos que ja´ se tinha mostrado que todo y ∈ N tal que 2 ≤ y < x ou
e´ primo ou e´ produto de primos. Como x esta´ fixo (e e´ finito), essa prova pode ser realmente
reconstru´ıda. Por exemplo, se x fosse 24, estariamos a assumir que ja´ tinhamos verificado que
2, 3, 5, 7, 11, 13, 17, 19 e 23 sa˜o primos e que 4 = 2× 2, 6 = 2× 3, 8 = 2× 2× 2, 9 = 3× 3,
10 = 2 × 5, 12 = 2 × 2 × 3, 14 = 2 × 7, 15 = 3 × 5, 16 = 2 × 2 × 2 × 2, 18 = 2 × 3 × 3,
20 = 2 × 2 × 5, 21 = 3 × 7 e 22 = 2 × 11. Como 24 na˜o e´ primo porque, por exemplo,
24 = 4× 6, enta˜o podemos concluir que e´ produto de primos, por substituic¸a˜o de 4 e 6 (que
correspondem a x1 e x2) pelas suas factorizac¸o˜es em primos: 24 = (2× 2)× (2× 3).
Usualmente, escreve-se 24 = 23 × 3, sendo esta a factorizac¸a˜o de 24 primos. Em geral,
para qualquer nu´mero natural n na˜o inferior a 2, existem primos p1, . . . pk u´nicos e tal que n
se pode factorizar de forma u´nica como pα11 × · · · × pαkk sendo αi 6= 0 e pi < pj se i < j, para
todo i ≤ k e todo j ≤ k. Por exemplo, 37268 = 22 × 71 × 113 e 500 = 22 × 53.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
3.3. FACTORIZAC¸A˜O EM PRIMOS 27
Corola´rio 8.1 Seja x um inteiro tal que x ≥ 2 e x na˜o e´ primo. A factorizac¸a˜o de x em
primos e´ u´nica, a menos de reordenac¸a˜o dos factores.
Ideia da prova: Ana´loga a` anterior, supondo como hipo´tese ja´ se provou que todo
y ∈ N tal que 2 ≤ y < x ou e´ primo ou se escreve de forma u´nica como produto de primos (a
menos de reordenac¸a˜o de factores). ut
Corola´rio 8.2 Qualquer inteiro maior do que 1 que na˜o e´ primo e´ divis´ıvel por algum primo.
Prova: Seja x um inteiro qualquer maior do que 1. Se x na˜o e´ primo enta˜o x e´ produto
de primos. Consequentemente, algum primo e´ seu divisor. ut
Proposic¸a˜o 9 O conjunto dos inteiros na˜o negativos que sa˜o primos e´ infinito.
Prova: Suponhamos que so´ existiam n primos, sendo n um certo inteiro fixo. Ou seja,
suponhamos que o conjunto dos primos era finito e que tinha exactamente n elementos, os
quais vamos denotar por p1, p2, . . . , pn. Enta˜o, o inteiropositivo
1 +
n∏
i=1
pi
na˜o seria primo, ja´ que e´ maior do que qualquer um dos primos p1, p2, . . . , pn.
Mas se 1 + p1p2 . . . pn na˜o e´ primo, enta˜o algum dos primos o divide (ou seja, e´ mu´ltiplo
de algum dos primos). Suponhamos que pk divide 1 + p1p2 · · · pn, sendo k um inteiro fixo,
1 ≤ k ≤ n. Como pk divide
∏n
i=1 pi isto e´, pk divide o produto 1+p1p2 · · · pn, pode-se concluir
que se pk dividir 1 + p1p2 · · · pn enta˜o pk divide 1. Mas nenhum primo divide 1. O absurdo
resultou de se ter suposto que o conjunto dos primos era finito. Logo, o conjunto dos primos
e´ infinito. ut
3.3.1 Determinac¸a˜o de primos: crivo de Erasto´tenes
Descreve-se a seguir um algoritmo para determinac¸a˜o de todos os primos na˜o superiores a
um nu´mero n dado. Tal algoritmo e´ conhecido como me´todo do crivo. Parte-se duma tabela
contendo todos os nu´meros na˜o superiores n. O algoritmo resume-se a seleccionar o menor
inteiro na tabela (ainda na˜o seleccionado) e apagar todos os seus mu´ltiplos ate´ todos os valores
estarem ou seleccionados ou apagados.
2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
3.4. MA´XIMO DIVISOR COMUM 28
2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
41 43 45 47 49
2 3 5 7
11 13 17 19
23 25 29
31 35 37
41 43 47 49
2 3 5 7
11 13 17 19
23 29
31 37
41 43 47 49
2 3 5 7
11 13 17 19
23 29
31 37
41 43 47
O processo continua . . . Os valores que ficarem na tabela sa˜o os primos, neste caso, na˜o
superiores a 50 (o valor de n neste exemplo).
3.3.2 Ca´lculo de divisores por ana´lise da factorizac¸a˜o em primos
A partir da factorizac¸a˜o dum nu´mero em primos e´ poss´ıvel determinar todos os seus divisores.
Por exemplo, os divisores de 30, que e´ dado por
30 = 21 × 31 × 51
sa˜o:
20 × 30 × 50 = 1 21 × 30 × 50 = 2 20 × 31 × 50 = 3
20 × 30 × 51 = 5 21 × 31 × 50 = 6 21 × 30 × 51 = 10
20 × 31 × 51 = 15 21 × 31 × 51 = 30
Em geral, se pα11 · · · pαkk for a decomposic¸a˜o de x em primos enta˜o o conjunto dos divisores
positivos de x e´
{pβ11 · · · pβkk : 0 ≤ βi ≤ αi para i = 1, . . . , k}
concluindo-se que o nu´mero de divisores de pα11 · · · pαkk e´
∏k
i=1(αi + 1).
3.4 Ma´ximo Divisor Comum
Sabemos que 1 e´ divisor de qualquer inteiro e que o maior divisor de qualquer inteiro positivo x
e´ o pro´prio x. Dados inteiros positivos a e b, podemos falar do seu ma´ximo divisor comum,
o qual representamos por mdc(a, b). O ma´ximo divisor comum e´ o maior dos divisores comuns:
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
3.4. MA´XIMO DIVISOR COMUM 29
d e´ mdc(a, b) sse d | a, d | b e d′ | d qualquer que seja d′ tal que d′ | a e d′ | b. Por definic¸a˜o de
mdc(a, b), cada divisor comum de a e b e´ divisor de mdc(a, b).
Por exemplo, por ana´lise da decomposic¸a˜o de 30 e 500 em primos, 30 = 2 × 3 × 5 e
500 = 22 × 53, podemos concluir que mdc(30, 500) = 10.
Dois inteiros a e b chamam-se primos entre si se e so´ se mdc(a, b) = 1.
Proposic¸a˜o 10 Os inteiros a/mdc(a, b) e b/mdc(a, b) sa˜o primos entre si.
Prova: Queremos mostrar que mdc( a
mdc(a,b) ,
b
mdc(a,b) ) = 1. Para isso vamos provar que
se mdc( a
mdc(a,b) ,
b
mdc(a,b) ) = d enta˜o mdc(a, b)d tambe´m divide a e b. Podemos depois concluir
que necessariamente d = 1 pois se d fosse maior do que 1 enta˜o mdc(a, b)d > mdc(a, b),
mdc(a, b)d seria um divisor comum a a e b, maior do que o ma´ximo divisor comum, o que,
por definic¸a˜o de mdc(a, b) e´ imposs´ıvel. Para completar os detalhes da prova, resta mostrar
que mdc(a, b)d e´ divisor de a e de b se d | a
mdc(a,b) e d | bmdc(a,b) . De facto, basta notar que:
a = mdc(a, b)
a
mdc(a, b)
= mdc(a, b)d
a
mdc(a, b)d
e
b = mdc(a, b)
b
mdc(a, b)
= mdc(a, b)d
b
mdc(a, b)d
.
ut
Tem-se mdc(320×57×1127×312, 24×36×525) = 36×57, porque o ma´ximo divisor comum
e´ dado por
2min(0,4) × 3min(20,6) × 5min(7,25) × 11min(27,0) × 31min(2,0)
ou seja, por 203657110310. Este me´todo pode ser sempre aplicado se forem conhecidas as
factorizac¸o˜es dos nu´meros a e b. Quando na˜o se conhecem, o algoritmo de Euclides
permite calcular mdc(a, b) eficientemente.
3.4.1 Ca´lculo do ma´ximo divisor comum pelo algoritmo de Euclides
A correcc¸a˜o do algoritmo de Euclides para ca´lculo do mdc(a, b) decorre do seguinte resultado.
Lema 1 Sejam a e b inteiros positivos tais que a < b e seja r o resto da divisa˜o de a por b.
Enta˜o, mdc(a, b) = mdc(b, r).
Prova: Represente-se por d o ma´ximo divisor comum de a e b. Por definic¸a˜o de divisa˜o
inteira, r e´ o resto da divisa˜o de a por b sse 0 ≤ r < b e a = bq + r para algum q ∈ Z. Por
outro lado, por definic¸a˜o de ma´ximo divisor comum, d|a e d|b. Portanto, d|(a− bq). Ou seja,
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
3.4. MA´XIMO DIVISOR COMUM 30
d|r. Logo, d e´ um divisor comum de b e r. Seja d′ um outro divisor comum de b e de r.
Resta-nos mostrar que d′ tera´ que dividir d para poder concluir que d e´ mdc(b, r). Para isso,
basta notar que se d′|b e d′|r enta˜o d′|(bq + r) e portanto d′|a. Logo, d′ e´ um divisor comum
a a e b, e portanto d′|mdc(a, b), isto e´, d′|d. ut
Algoritmo de Euclides para determinac¸a˜o de mdc(a, b). Sendo a e b inteiros positivos,
podemos definir mdc(a, b) recursivamente por
mdc(a, 0) = a se a > 0
mdc(a, b) = mdc(b, a%b) se a > b > 0
mdc(a, b) = mdc(b, a) se a < b
em que a%b denota o resto da divisa˜o de a por b.
Por exemplo, mdc(30, 500) = mdc(500, 30) = mdc(30, 500%30) = mdc(30, 20) = mdc(20, 10) =
mdc(10, 0) = 10.
500 30
20 16
30 20
10 1
20 10
0 2
Observe-se que mdc(500, 30) = 17× 30− 1× 500 ja´ que
10 = 30 − 1× 20 = 30− (500 − 16× 30) = 17 × 30 − 1× 500
ou seja, mdc(500, 30) pode-se escrever na forma 500x + 30y para x, y ∈ Z apropriados.
Lema 2 Quaisquer que sejam a, b ∈ Z+, existem inteiros x e y tais que ax + by = mdc(a, b),
ou seja, mdc(a, b) e´ combinac¸a˜o linear inteira de a e b.
Para escrever mdc(100, 17) (isto e´, 1) como combinac¸a˜o de 100 e 17, observe-se que:
100 17
15 5
17 15
2 1
15 2
1 7
2 1
0 2
Efectuando ana´lise para tra´s, substituindo sucessivamente os restos de forma a conseguir
fazer aparecer 100 e 17 (a e b iniciais) obtem-se a combinac¸a˜o procurada: 1 = 15 − 7 × 2 =
15− 7(17 − 1× 15) = 8× 15− 7× 17 = 8(100 − 5× 17)− 7× 17 = 8× 100− 47× 17.
Proposic¸a˜o 11 Sendo a, b e c constantes inteiras, a equac¸a˜o ax + by = c com x, y ∈ Z, tem
soluc¸a˜o se e so´ se mdc(a, b) | c.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
3.5. MI´NIMO MU´LTIPLO COMUM 31
Prova: Como mdc(a, b) divide a e divide b, tambe´m divide ax + by quaisquer que sejam
x, y ∈ Z. Portanto, para que ax + by = c tenha soluc¸a˜o e´ necessa´rio que mdc(a, b) divida c.
Por outro lado, usando o facto de mdc(a, b) se poder escrever como combinac¸a˜o inteira
de a e de b, temos mdc(a, b) = ama + bmb para ma e mb inteiros adequados. Se mdc(a, b) | c,
enta˜o c = mdc(a, b) c
mdc(a,b) e
c
mdc(a,b) ∈ Z. Multiplicando mdc(a, b) = ama + bmb por cmdc(a,b)
obtem-se mdc(a, b) c
mdc(a,b) = a(ma
c
mdc(a,b) ) + b(mb
c
mdc(a,b) ). Assim, vemos que se tomarmos
x = ma
c
mdc(a,b) e y = mb
c
mdc(a,b) temos uma soluc¸a˜o inteira de ax + by = c. ut
Pode-se provar que (x, y) ∈ Z2 e´ soluc¸a˜o de ax + by = c sse x = ma cmdc(a,b) + k bmdc(a,b) e
y = mb
c
mdc(a,b) − k bmdc(a,b) , com k ∈ Z qualquer.
3.5 Mı´nimo Mu´ltiplo Comum
Dados inteiros positivos a e b sabemos que ab e´ um mu´ltiplo de a e de b, fazendo sentido
determinar o menor inteiro positivo que e´ mu´ltiplocomum a a e b, ou seja o mı´nimo mu´ltiplo
comum, mmc(a, b). Por definic¸a˜o m e´ mmc(a, b) sse a |m, b |m e m |m′ para todo m′ tal
que a |m′ e b |m′. Assim, mmc(a, b) e´ um divisor de todos os mu´ltiplos comuns de a e b.
Exemplo 9 mmc(320571127312, 2436525) = 2max(0,4)3max(20,6)5max(7,25)11max(27,0)31max(2,0) =
243205251127312.
Como
a
mdc(a, b)
e
b
mdc(a, b)
sa˜o primos entre si, podemos mostrar a Proposic¸a˜o 12.
Proposic¸a˜o 12 Quaisquer que sejam a, b ∈ Z+, mmc(a, b) = ab
mdc(a, b)
.
Prova:
ab =
(
mdc(a, b)
a
mdc(a, b)
)(
mdc(a, b)
b
mdc(a, b)
)
=
(
mdc(a, b)
a
mdc(a, b)
b
mdc(a, b)
)
︸ ︷︷ ︸
mmc(a,b)
mdc(a, b)
Para ver que mdc(a, b) a
mdc(a,b)
b
mdc(a,b) e´ mmc(a, b), notemos que e´ mu´ltiplo de a e de b. Por
outro lado, para verificar que divide qualquer outro mu´ltiplo m′ de a e de b, escrevamos
m′ = k1a e m
′ = k2b para inteiros k1 e k2 apropriados. Enta˜o, m
′ = k1mdc(a, b)
a
mdc(a,b) e m
′ =
k2mdc(a, b)
b
mdc(a,b) , pelo que k1
a
mdc(a,b) = k2
b
mdc(a,b) . Como
b
mdc(a,b) e
a
mdc(a,b) sa˜o primos entre
si, b
mdc(a,b) tem que dividir k1. Assim, k1 =
b
mdc(a,b)k
′
1 para algum k
′
1 e consequentemente, m
′ =
b
mdc(a,b)k
′
1mdc(a, b)
a
mdc(a,b) e portanto m
′ e´ mu´ltiplo de mdc(a, b) b
mdc(a,b)
a
mdc(a,b) . Conclui-se
que mdc(a, b) b
mdc(a,b)
a
mdc(a,b) e´ mmc(a, b). ut
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
3.6. CONGRUEˆNCIAS 32
3.6 Congrueˆncias
Dados b ∈ Z+ e x, y ∈ Z dizemos que x e y sa˜o congruentes mo´dulo b se e so´ se x− y for
mu´ltiplo de b, escrevendo x ≡ y (mod b). Tal e´ equivalente a dizer que x e y da˜o o mesmo
resto quando divididos por b. De facto, se x = qxb + rx e y = qyb + ry com 0 ≤ rx < b e
0 ≤ ry < b, enta˜o x − y = (qx − qy)b + (rx − ry) e portanto x − y e´ mu´ltiplo de b se e so´ se
rx − ry o for. Mas, como 0 ≤ rx < b e 0 ≤ ry < b, podemos concluir que −b < rx − ry < b, e
consequentemente rx − ry e´ mu´ltiplo de b se e so´ se for zero. Portanto, x ≡ y (mod b) sse os
restos da divisa˜o de x e y por b sa˜o iguais. (Escrevemos qx, qy e rx, ry em vez de q1, q2 e r1, r2
para indicar que esses quocientes e restos dependem de x e y respectivamente.)
As relac¸o˜es de congrueˆncias teˆm algumas propriedades interessantes (e importantes). Por
exemplo, a “congrueˆncia mo´dulo 2” decompo˜e os inteiros em dois conjuntos:
{x : x ∈ Z, x ≡ 0 (mod 2)} = {2k : k ∈ Z} = {pares}
{x : x ∈ Z, x ≡ 1 (mod 2)} = {1 + 2k : k ∈ Z} = {´ımpares}
A relac¸a˜o de “congrueˆncia mo´dulo b” (para b ∈ Z+) decompo˜e os inteiros em b conjuntos
{x : x ∈ Z, x ≡ 0 (mod b)} e {x : x ∈ Z, x ≡ 1 (mod b)}, . . . , {x : x ∈ Z, x ≡ b− 1 (mod b)},
sendo cada um identificado por um dos b restos poss´ıveis.
Outra das propriedades interessantes da relac¸a˜o de congrueˆncia e´ ser preservada pelas
operac¸o˜es de soma, subtracc¸a˜o e produto, ou seja, se x1 ≡ y1 (mod b) e x2 ≡ y2 (mod b) enta˜o
x1 ± x2 ≡ y1 ± y2 (mod b) e x1 × x2 ≡ y1 × y2 (mod b).
O exemplo seguinte ilustra uma das aplicac¸o˜es de congrueˆncias.
Exemplo 10 Suponha que se quer resolver 5x + 3y = 1 para x, y ∈ Z. Como 5x + 3y = 1⇔
5x − 1 = 3(−y) podemos comec¸ar por resolver 5x ≡ 1 (mod 3). Tem-se 5x ≡ 1 (mod 3) ⇔
2x ≡ 1 (mod 3). Por outro lado, 2x ≡ 1 (mod 3)⇔ (−1)x ≡ 1 (mod 3), ou seja x ≡ (−1) (mod 3),
isto e´ x ≡ 2 (mod 3). Assim, 5x ≡ 1 (mod 3) se e so´ se x = 2 + 3k para algum k ∈ Z.
Voltando a` equac¸a˜o inicial, temos 5x + 3y = 1 ⇔ 5(2 + 3k) + 3y = 1 ⇔ y = −3 − 5k
concluindo-se que as soluc¸o˜es de 5x + 3y = 1 sa˜o os pontos (x, y) da forma x = 2 + 3k e
y = −3− 5k, com k ∈ Z.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
Cap´ıtulo 4
Induc¸a˜o Matema´tica
O me´todo de demonstrac¸a˜o por induc¸a˜o matema´tica (ou induc¸a˜o finita) sera´ bastante usado
durante o curso pelo que e´ conveniente introduzi-lo (ou recorda´-lo).
4.1 Princ´ıpio de Induc¸a˜o Matema´tica
Imagine uma escada com uma infinidade de degraus. Na˜o e´ uma escada com um nu´mero
enorme de degraus! Esta escada, tem sempre um degrau acima de qualquer outro que consi-
dere. Suponha que e´ verdade (4.1).
“Se conseguir chegar ate´ um degrau, enta˜o tambe´m consigo chegar ao seguinte.” (4.1)
Se nada mais for dito, na˜o pode concluir que “consegue chegar ao 16o¯ degrau”.
Suponha agora na˜o so´ (4.1) mas tambe´m (4.2).
“Consigo chegar ao 13o¯ degrau” (4.2)
O que pode concluir? Como consegue chegar ao 13o¯ e e´ verdade (4.1), enta˜o consegue chegar
ao 14o¯. Como consegue chegar ao 14
o
¯ e e´ verdade (4.1), enta˜o consegue chegar ao 15
o
¯. Como
consegue chegar ao 15o¯ e e´ verdade (4.1), enta˜o consegue chegar ao 16
o
¯. De (4.1) e (4.2),
conclui-se (4.3).
“Consegue chegar ao n-e´simo degrau, qualquer que seja n ≥ 13.” (4.3)
Como na˜o e´ dito sobre de que forma chegou ao 13o¯ degrau, nada pode concluir sobre a
possibilidade de chegar ao degrau n, para n < 13.
Mas, suponha agora que (4.4) e´ verdade.
“Consigo chegar ao 1o¯ degrau”. (4.4)
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
4.1. PRINCI´PIO DE INDUC¸A˜O MATEMA´TICA 34
Do mesmo modo que anteriormente, se supuser (4.1) e (4.4) enta˜o pode concluir (4.5).
“Consegue chegar ao n-e´simo degrau, qualquer que seja n ≥ 1.” (4.5)
Proposic¸a˜o 13 (Princ´ıpio de Induc¸a˜o Matema´tica) Escrevamos P(n) como abreviatura
de “o inteiro na˜o negativo n satisfaz a propriedade/condic¸a˜o P ”. Tem-se ∀n ∈ N P (n), se
forem satisfeitas as duas condic¸o˜es (i) e (ii) seguintes.
(i) P (0) e´ verdade;
(ii) ∀k ∈ N ( P (k)⇒ P (k + 1) ), isto e´ para todo k ∈ N, se P (k) enta˜o P (k + 1);
P (0) diz-se (caso de) base de induc¸a˜o. Em P (k)⇒ P (k+1), chamamos a P (k) a hipo´tese
de induc¸a˜o e a P (k + 1) a tese.
Exemplo 11 Seja An a a´rea dum quadrado de lado 2
n, com n ≥ 1 (inteiro). Vamos mostrar
que o resto da divisa˜o de An por 3 e´ 1, qualquer que seja n ≥ 1.
(i) (Caso de base) Como A1 e´ 4 e sabemos que o resto da divisa˜o de 4 por 3 e´ 1, e´ verdade
que a condic¸a˜o se verifica para n = 1.
(ii) (Hereditariedade) Mostremos que qualquer que seja k ≥ 1, se Ak for da forma 3p+1 para
algum inteiro na˜o negativo p, enta˜o Ak+1 = 3q + 1 para algum inteiro na˜o negativo q.
Ora, se Ak = 3p+1, enta˜o Ak+1 = (2
k+1)2 = 4(2k)2 = 4Ak = 4(3p+1) = 3(4p+1)+1.
Ou seja, Ak+1 = 3q + 1 para algum inteiro na˜o negativo, ja´ que se p ∈ Z e p ≥ 0 enta˜o
4p + 1 ∈ Z e 4p + 1 ≥ 0.
Usando (ii) e (i) podemos concluir que qualquer que seja n ≥ 1, a a´rea do quadrado de
lado 2n excede numa unidade um mu´ltiplo de 3.
Observe que, se nos fosse pedido, podiamos apresentar a deduc¸a˜o de que A6 excede numa
unidade um mu´ltiplo de 3:
Por (i), sabemos que o resto da divisa˜o de A1 por 3 e´ 1;
De (i) e (ii), concluimos que o resto da divisa˜o de A2 por 3 e´ 1;
Como o resto da divisa˜o de A2 por 3 e´ 1, concluimos, por (ii), que o resto da divisa˜o de A3 por 3 e´ 1;
Como o resto da divisa˜o de A3 por 3 e´ 1, concluimos, por (ii), que o resto da divisa˜o de A4 por 3 e´ 1;
Como o resto da divisa˜o de A4 por 3 e´ 1, concluimos, por (ii), que o resto da divisa˜o de A5 por 3 e´ 1;
Como o resto da divisa˜o de A5 por 3 e´ 1, concluimos, por (ii), que o resto da divisa˜o de A6 por 3 e´ 1.
Do mesmo modo que conseguimos mostrar que A6 da´ resto 1 quando dividido por 3,
podiamos, dado um n ≥ 1, apresentar a deduc¸a˜o de que An da´ resto 1 quando dividido por 3,
se tal nos fosse pedido.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
4.1. PRINCI´PIO DE INDUC¸A˜O MATEMA´TICA 35
Proposic¸a˜o 14 (Versa˜o geral do Princ´ıpio de Induc¸a˜o) Seja n0 ∈ Z, e suponha que
P (n) denota “o inteiro n satisfaz a propriedade P . Se forem satisfeitas as duas condic¸o˜es (i)
e (ii) seguintes, enta˜o, para todo o inteiro n ≥ n0 tem-se P (n).
(i) P (n0)e´ verdade;
(ii) ∀k ≥ n0 ( P (k)⇒ P (k + 1) ), isto e´, para todo inteiro k tal que k ≥ n0, se P (k)
enta˜o P (k + 1);
Exemplo 12 Vamos mostrar que qualquer que seja n ≥ 1 e quaisquer que sejam a, b ∈ R+,
se tem (a + b)n < 2n(an + bn).
Podemos concluir isso se mostrarmos que as duas condic¸o˜es de aplicabilidade do princ´ıpio
de induc¸a˜o matema´tica se verificam neste caso.
(i) Para n=1, (a + b)1 = a + b < 2(a + b) = 21(a1 + b1), porque a, b ∈ R+.
(ii) Suponhamos agora que para um dado k ≥ 1 se tem (a+b)k < 2k(ak +bk), para a, b ∈ R+
quaisquer, e vamos mostrar que enta˜o (a + b)k+1 < 2k+1(ak+1 + bk+1).
Como (a + b)k+1 = (a + b)k(a + b), e por hipo´tese
(a + b)k < 2k(ak + bk),
concluimos que
(a + b)k+1 < 2k(ak + bk)(a + b) = 2k(ak+1 + bk+1 + akb + bka).
Como
2k(ak+1 + bk+1 + akb + bka) = 2k(ak+1 + bk+1) + 2k(akb + bka),
para concluir que (a + b)k+1 < 2k+1(ak+1 + bk+1) vamos mostrar que
akb + bka ≤ ak+1 + bk+1
quaisquer que sejam a, b reais positivos. Tem-se
akb + bka− ak+1 − bk+1 = −(ak − bk)(a− b) ≤ 0,
ja´ que quaisquer que sejam x, y ∈ R+, se x ≤ y enta˜o xp ≤ yp, para todo p ≥ 1 (relembre
que as func¸o˜es fp(x) = x
p, sa˜o estritamente crescentes em R+).
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
4.1. PRINCI´PIO DE INDUC¸A˜O MATEMA´TICA 36
Exerc´ıcio 4.1.1 Aplique o princ´ıpio de induc¸a˜o matema´tica para resolver os problemas se-
guintes.
a) Mostrar que |sen(nx)| ≤ n|sen(x)|, para todo x ∈ R e todo n ∈ N.
b) Mostrar que 4n + 15n− 1 e´ mu´ltiplo de 9, para todo n ≥ 1.
Exemplo 13 Considere o seguinte algoritmo (imagine que Y e´ uma caixa1).
1. Coloque em Y o valor 0.
2. Escolha um inteiro (vamos referi-lo por X).
3. Se X = 0 enta˜o fac¸a 7.
4. Se X > 0 enta˜o volte a 2.
5. Substitua o valor em Y pela soma do valor que la´ estava com dois.
6. Volte a 2.
7. Indique o valor que guarda em Y, e pa´re.
O valor em Y quando se executa 7. e´ o dobro do nu´mero de inteiros negativos nos valores
escolhidos. Para o provar, vamos mostrar que tal propriedade caracteriza o valor de Y em
cada iterac¸a˜o do ciclo (ou seja, e´ um invariante do ciclo). Usamos induc¸a˜o sobre o nu´mero
de iterac¸o˜es efectuadas.
O valor que esta´ guardado em Y quando esta´ a executar 2. pela 2a¯ vez e´ 0 se o primeiro
valor escolhido em 2. for positivo, e e´ 2 se tal valor for negativo.
Quando esta´ a executar 2. pela 3a¯ vez, o valor em Y e´ 4 se ambos os valores escolhidos
anteriormente forem negativos, e´ 2 se um for negativo e o outro positivo, e e´ 0 se ambos forem
positivos.
Suponhamos que para um dado k ≥ 1, quando se se esta´ a executar 2. pela ka¯ vez, o valor
em Y e´ o dobro do nu´mero de inteiros negativos nos k − 1 valores escolhidos anteriormente.
Enta˜o, por ana´lise do algoritmo, concluimos que se se estiver a executar 2. pela (k + 1)a¯
vez, o valor em Y e´ igual ao valor anterior se tivermos dado mais um nu´mero positivo, ou foi
incrementado de duas unidades, se tivermos dado mais um nu´mero negativo. Portanto, se
quando se estiver a executar 2. pela ka¯ vez, o valor em Y e´ o dobro do nu´mero de inteiros
negativos nos k−1 valores escolhidos anteriormente, enta˜o quando se estiver a executar 2. pela
(k + 1)a¯ vez, valor em Y e´ o dobro do nu´mero de inteiros negativos nos k valores escolhidos
anteriormente.
Consequentemente, por induc¸a˜o matema´tica, podemos concluir que o valor em Y quando
se executa 7. e´ o dobro do nu´mero de inteiros negativos nos valores escolhidos.
1Na terminologia de linguagens de programac¸a˜o, X e Y sa˜o varia´veis de programac¸a˜o.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
4.1. PRINCI´PIO DE INDUC¸A˜O MATEMA´TICA 37
4.1.1 Erros frequentes
E´ necessa´rio mostrar as duas condic¸o˜es de aplicabilidade do princ´ıpio de induc¸a˜o, sem o que
as provas na˜o ficam completas e, no pior dos casos, os resultados mal “demonstrados” sa˜o
mesmo falsos.
O exemplo seguinte serve para ilustrar o facto de certas propriedades, na˜o observa´veis,
poderem ser heredita´rias. Heredita´rias, no sentido de se um dado inteiro as satisfizer, tambe´m
o inteiro seguinte as satisfaz.
Exemplo 14 Considere a seguinte demonstrac¸a˜o (claramente, errada!) de que “entre dois
inteiros consecutivos existe uma infinidade de inteiros”.
Prova: Para todo x ∈ R (em particular para x inteiro) se k ≤ x ≤ k + 1 enta˜o
k + 1 ≤ x + 1 ≤ k + 2, qualquer que seja k ∈ N. Assim, se entre k e k + 1 existir
uma infinidade de inteiros, enta˜o entre k+1 e k+2 tambe´m existe uma infinidade
de inteiros. De facto, a cada inteiro x no intervalo [k, k +1] podemos associar um
inteiro x′ no intervalo [k + 1, k + 2], a saber, por exemplo x′ e´ x + 1.
Logo, por induc¸a˜o matema´tica sobre k, concluimos que entre dois inteiros conse-
cutivos existe uma infinidade de inteiros. ut
Como entre dois inteiros consecutivos na˜o ha´ qualquer outro inteiro, a prova tem que estar
errada. O erro esta´ na conclusa˜o “precipitada”. Na˜o se mostrou que existia um intervalo
[k, k+1] que tinha uma infinidade de inteiros. Apenas se mostrou a condic¸a˜o (ii) do princ´ıpio
de induc¸a˜o. A condic¸a˜o (i) na˜o foi provada, nem se pode provar!
Exemplo 15 A demonstrac¸a˜o seguinte esta´ obviamente errada dado que permite concluir
que “todos os cavalos sa˜o brancos” (e, todos sabemos que ha´ cavalos doutras cores).
Vamos mostrar que qualquer que seja o nu´mero de cavalos que estejam numa
cerca, se existir algum cavalo branco entre eles enta˜o todos os cavalos nessa cerca
sa˜o brancos.
Prova: Para isso vamos mostrar que as duas condic¸o˜es (i) e (ii) do princ´ıpio de
induc¸a˜o se verificam nessa situac¸a˜o.
(i) Como deve estar pelo menos um cavalo branco na cerca, podemos afirmar
que se so´ existir um cavalo na cerca e´ branco.
c©A. P. Toma´s – Dep. de Cieˆncia de Computadores – FCUP
4.1. PRINCI´PIO DE INDUC¸A˜O MATEMA´TICA 38
(ii) Fixemos um k ∈ N, e suponhamos que se existirem k cavalos numa cerca
qualquer, estando pelo menos um cavalo branco entre eles, enta˜o todos os
demais sa˜o brancos. Consideramos agora uma cerca onde esta˜o k + 1 cavalos
sendo branco pelo menos um deles. Retiremos um cavalo da cerca deixando
ficar o branco. Dado que esta˜o k cavalos na cerca, estando um branco entre
eles, segue pela hipo´tese de induc¸a˜o, que os k cavalos na cerca sa˜o brancos.
Resta mostrar que o cavalo que retira´mos primeiramente tambe´m era branco.
Retiremos um dos cavalos que esta´ na cerca (e´ indiferente qual se retira
porque de facto todos sa˜o brancos), e voltemos a colocar o que retira´mos
primeiramente. Mais uma vez, pela hipo´tese, podemos concluir que todos os
cavalos que esta˜o agora na cerca sa˜o brancos.
Assim, pelo princ´ıpio de induc¸a˜o matema´tica segue a validade da proposic¸a˜o que
queriamos mostrar. ut
Sabemos que “se existir algum cavalo branco numa cerca”, tambe´m la´ podem estar cavalos
doutras cores. Logo, a afirmac¸a˜o que “mostra´mos” por induc¸a˜o e´ falsa. Mas, como o sistema
dedutivo que estamos a seguir e´ consistente, na˜o podemos deduzir proposic¸o˜es falsas, pelo
que ha´ que encontrar um erro (v´ıcio) na prova dada.
Sabemos que se estiverem dois cavalos numa cerca e um deles for branco, enta˜o isso na˜o
implica que o outro tambe´m seja branco. Por outras palavras, e´ falso P (1)⇒ P (2).
Para localizarmos o erro, vamos enta˜o seguir em detalhe a prova de (ii) para k = 1.
Fixemos k = 1. Suponhamos (podemos sempre supor o que quisermos) que e´
sempre branco o cavalo que estiver so´zinho numa cerca em que ha´ pelo menos
um cavalo branco. Consideramos agora uma cerca onde esta˜o dois cavalos sendo
branco pelo menos um deles. Retiremos um cavalo da cerca deixando ficar o
branco. Dado que esta´ um so´ cavalo na cerca, estando um branco na cerca, segue
pela hipo´tese de induc¸a˜o, que o cavalo na