Divisibilidade em Teoria dos Números

Prévia do material em texto

Mestrado Profissional
em Matemática em Rede Nacional
Iniciação à Matemática
Autores:
Krerley Oliveira Adán J. Corcho
Unidade II:
Capítulos III e IV
3
Divisibilidade
Os números governam o mundo. Platão
A teoria dos números é o ramo da Matemática que estuda os mis-
térios dos números e teve sua origem na antiga Grécia. Os belíssimos
problemas ligados a esta área constituem, até hoje, uma das princi-
pais fontes inspiradoras dos amantes da Matemática. Além disso, essa
área possui várias aplicações úteis a humanidade, como por exemplo,
o processo de criptogra�a usado em transações pela Internet.
Alguns problemas em teoria dos números demoram séculos para
serem resolvidos, como por exemplo o último teorema de Fermat, que
a�rma que não existe nenhum conjunto de inteiros positivos x, y, z e n
com n maior que 2 que satisfaça xn + yn = zn. Esse problema foi ob-
jeto de fervorosas pesquisas durante mais de 300 anos e foi �nalmente
demonstrado em 1995 pelo matemático Andrew Wiles.
Ainda hoje persistem muitas questões naturais e simples sem res-
posta. Por exemplo, ninguém sabe mostrar (apesar de todo mundo
89
90 3 Divisibilidade
acreditar que é verdade!) que todo natural par é soma de dois pri-
mos. Essa é a famosa conjectura de Goldbach. Essa simplicidade de se
anunciar problemas e a extrema di�culdade em resolvê-los faz desta
área um grande atrativo para os matemáticos do mundo todo.
Este capítulo será dedicado ao estudo de algumas propriedades
básicas relativas aos números inteiros.
3.1 Conceitos Fundamentais e Divisão Eu-
clidiana
Denotamos por Z o conjunto dos números inteiros formado pelo con-
junto dos números naturais N = {1, 2, 3, . . .} munido do zero e dos
números negativos. Ou seja, Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}.
Começamos observando que a soma, diferença e produto de núme-
ros inteiros também serão números inteiros. Entretanto, o quociente
de dois inteiros pode ser um inteiro ou não.
Uma das propriedades fundamentais dos números naturais que uti-
lizaremos ao longo do texto é o conhecido princípio da boa ordenação,
que a�rma o seguinte:
Princípio da Boa Ordenação: todo subconjunto não vazio A ⊆ N
possui um elemento menor que todos os outros elementos deste, ou
seja, existe a ∈ A tal que a ≤ n para todo n ∈ A.
Por exemplo, se A é o conjunto dos números pares, o menor ele-
mento de A é o número 2. Por outro lado, observamos que o conjunto
dos números inteiros não goza da boa ordenação.
Apesar do princípio da boa ordenação parecer inocente e natural,
muitos resultados importantes a respeito dos números naturais decor-
3.1 Conceitos Fundamentais e Divisão Euclidiana 91
rem do mesmo, como veremos ao longo de todo este capítulo.
De�nição 3.1. Sejam a e b inteiros. Dizemos que a divide b se existe
um inteiro q tal que b = aq. Também usaremos as frases a é divisor
de b ou b é múltiplo de a para signi�car esta situação.
Usaremos a notação a | b para representar todas as frases equi-
valentes ditas anteriormente. Se a não for divisor de b, então escre-
veremos a - b.
Exemplo 3.2. 7 | 21 pois 21 = 7 · 3. Por outro lado 3 - 8 pois
considerando o conjunto M = {3m, m ∈ N} = {3, 6, 9, 12, . . .} dos
múltiplos positivos de 3 vemos que 8 não pertence ao mesmo.
A seguinte proposição é um bom exercício para entender os con-
ceitos enunciados acima.
Proposição 3.3. Sejam a, b e c números inteiros. Então,
(a) se a | b e b | c então a | c;
(b) se a | b e a | c então a | (b+ c) e a | (b− c);
(c) se a e b são positivos e a | b então 0 < a ≤ b;
(d) se a | b e b | a então a = b ou a = −b.
Demonstração. Se a | b e b | c então existem inteiros q1 e q2 tais que
b = aq1 (3.1)
e
c = bq2. (3.2)
92 3 Divisibilidade
Substituindo (3.1) em (3.2) temos que
c = aq1q2 = aq, onde q = q1q2 ∈ Z, (3.3)
provando isto a a�rmação feita em (a).
Agora provaremos (b). Com efeito, se a | b e a | c valem as
igualdades
b = aq1, q1 ∈ Z (3.4)
e
c = aq2, q2 ∈ Z. (3.5)
Operando com os ambos lados das igualdades (3.4) e (3.5) temos que
b+ c = a(q1 + q2︸ ︷︷ ︸
r∈Z
) e b− c = a(q1 − q2︸ ︷︷ ︸
s∈Z
),
obtendo assim o resultado desejado.
Continuamos agora com a prova de (c). De fato, se a | b, sendo
ambos positivos, então b = aq com
q ≥ 1. (3.6)
Logo, multiplicando por a ambos lados de (3.6) temos (como a é posi-
tivo) que
b = aq ≥ a > 0,
como esperávamos.
Finalmente, provaremos (d). Com este propósito observamos que
se a | b e b | a então |a| divide |b| e |b| divide |a|. Portanto, pelo item
(c) temos que |a| ≤ |b| e |b| ≤ |a|, ou seja, |a| ≤ |b| ≤ |a|. Logo,
|a| = |b| e consequentemente a = b ou a = −b.
3.1 Conceitos Fundamentais e Divisão Euclidiana 93
Exemplo 3.4. Prove que o número N = 545362−7 não é divisível por
5.
Solução. Vamos mostrar isso utilizando o método do absurdo. Se
este número fosse divisível por 5, então 545362 − 7 = 5q. Logo, 7 =
545362 − 5q, ou seja, 7 seria divisível por 5, o que é um absurdo.
O próximo passo de nossa discussão é ver o que acontece quando
um número não é divisível por outro. Por exemplo, analisemos se 31 é
divisível por 7 e para isto listaremos a diferença entre 31 e os múltiplos
positivos de 7, isto é:
r1 = 31− 7 · 1 = 24,
r2 = 31− 7 · 2 = 17,
r3 = 31− 7 · 3 = 10,
r4 = 31− 7 · 4 = 3,
r5 = 31− 7 · 5 = −4,
r6 = 31− 7 · 6 = −11,
...
Claramente 31 não é divisível por 7, pois caso contrário teríamos
que alguma das diferenças acima seria igual a zero, o que é impossível
pois as diferenças rq = 31 − 7q com 1 ≤ q ≤ 4 são todas positivas
e com q ≥ 5 são todas negativas. Entretanto, notamos que entre as
diferenças positivas a única que é menor que 7 corresponde ao caso
q = 4. O resultado seguinte nos diz o que acontece no caso geral da
divisão de um inteiro b por um inteiro positivo a.
94 3 Divisibilidade
Teorema 3.5 (Divisão Euclidiana). Dados dois inteiros a e b, sendo
a positivo, existem únicos inteiros q e r tais que
b = aq + r, 0 ≤ r < a.
Se a - b, então r satisfaz a desigualdade estrita 0 < r < a.
Demonstração. Por simplicidade, suporemos que b é positivo. Se b <
a, basta tomar q = 0 e r = b. Se b = a, então tomamos q = 1 e r = 0.
Assim, assumiremos também que b > a > 0. Consideremos o conjunto
R = {b− aq ∈ Z; b− aq ≥ 0} ⊆ N ∪ {0} (3.7)
Notemos que o conjunto R é não vazio, pois b − a ∈ R, já que
b − a > 0. Deste modo, pelo princípio da boa ordenação temos que
R admite um menor elemento, que denotaremos por r. Claramente
r = b − aq ≥ 0, para algum q ≥ 0. Além disso, r < a pois caso
contrário
r = b− aq ≥ a⇒ b− a(q + 1) ≥ 0. (3.8)
Por outro lado,
a > 0⇒ b− a(q + 1) < b− aq. (3.9)
Das desigualdades (3.8) e (3.9) segue que
0 ≤ b− a(q + 1) < b− aq,
contradizendo o fato de que r = b−aq é o menor elemento não negativo
de R.
Agora provaremos que de fato r e q, escolhidos desta forma, são
únicos. Com efeito, suponhamos que existem outros inteiros r1 e q1
tais que
b = aq1 + r1, 0 ≤ r1 < a.
3.1 Conceitos Fundamentais e Divisão Euclidiana 95
Então resulta que aq + r = aq1 + r1. Logo,
(r − r1) = (q1 − q)a; (3.10)
sendo assim, r−r1 é múltiplo de a. Mas, em virtude de−a < r−r1 < a,
o único valor que r − r1 pode tomar, sendo este múltiplo de a, é
r − r1 = 0. Portanto, r = r1, de onde se deduz diretamente de (3.10)
que q = q1.
Os números q e r no enunciado do teorema acima são chamados,
respectivamente, de quociente e resto da divisão de b por a.
Um resultado imediato da divisão euclidiana é o seguinte.
Corolário 3.6. Dados dois números naturais a e b com 1 < a ≤ b,
existe um número natural n tal que
na ≤ b < (n+ 1)a.
Demonstração. Pela divisão euclidiana, existem únicos q, r ∈ N com
0 ≤ r < a tais que b = aq + r. Assim
aq ≤ b = aq + r < aq + a = a(q + 1).
Basta agora tomar q = n para obtermos o resultado.
Os exemplos a seguir apresentam a utilidade do Teorema 3.5.
Exemplo 3.7. Se a é um natural com a ≥ 3, então a2 deixa resto 1
na divisão por a− 1. Consequentemente, a− 1 divide a2 − 1.
Solução. Usando a identidade a2 − 1 = (a − 1)(a + 1) temos que
a2 = (a− 1)(a+ 1) + 1 com 1 < a−1, de onde segue o resultado.
96 3 Divisibilidade
O próximo exemplo, como veremos, motiva a procura de cami-
nhos e�cientes para encontrar o resto que deixa um número quando é
dividido por outro.
Exemplo 3.8. Um turista brasileiro chega a Cuba e troca parte de
seu dinheiro na casa de câmbio, recebendo 175 notas de 50 pesos e
213 notas de 20 pesos. Ele decide trocar este dinheiro pela maior
quantidade possível das famosas moedas de 3 pesos cubanos, porque
elas têm gravada a imagem do guerrilheiro Che Guevara. Quanto
sobrou do dinheiro depois de fazer a troca pelas moedas?
Solução. Para resolver este problema basta achar o resto que deixa o
número n = 175 · 50 + 213 · 20 quando é dividido por 3. Entretanto,
queremos destacar que não é preciso fazer os produtos e a soma envol-
vidos no número n. Em lugar de fazer isto substituímos cada número
que aparece em n pelo resto que este deixa na divisão por 3, formando
assim um novo número n1, ou seja,
n1 = 1 · 2 + 0 · 2 = 2.
Agora procuramos o resto que n1 deixa na divisão por 3, que obvi-
amente é 2. A surpresa é que este resto é o mesmo que deixa n na
divisão por 3. Logo, sobraram 2 pesos depois de fazer a troca.
A solução do exemplo anterior é uma aplicação particular do se-
guinte lema que é de muita utilidade na resolução de problemas.
Lema 3.9 (Lema dos Restos). A soma e o produto de quaisquer dois
números naturais deixa o mesmo resto que a soma e o produto dos
seus restos, na divisão por um inteiro positivo a.
3.1 Conceitos Fundamentais e Divisão Euclidiana 97
Demonstração. Sejam n1, n2 ∈ Z. Fazendo a divisão com resto de
ambos os números por a temos que
n1 = aq1 + r1 e n2 = aq2 + r2,
com 0 ≤ r1, r2 < a. Então,
n1n2 = (aq1 + r1)(aq2 + r2)
= a2q1q2 + aq1r2 + aq2r1 + r1r2
= a(aq1q2 + q1r2 + q2r1) + r1r2
= aq + r1r2,
(3.11)
onde q = aq1q2+q1r2+q2r1. Agora dividimos r1r2 por a para obtermos
r1r2 = ap+ r, p ∈ Z, 0 ≤ r < a. (3.12)
Das igualdades (3.11) e (3.12) segue que
n1n2 = aq + ap+ r = a(p+ q) + r, 0 ≤ r < a. (3.13)
Portanto, de (3.12) e (3.13) concluímos que os restos que deixam n1n2
e r1r2 na divisão por a são iguais, �cando provado o resultado para o
produto. A prova para a soma é análoga.
Observação 3.10. A vantagem do lema é que em certos problemas
que envolvem números muito grandes podemos substituir estes por nú-
meros muito menores e mais confortáveis para trabalhar.
Vejamos como aplicar o lema dos restos nos seguintes exemplos a
seguir.
Exemplo 3.11. Prove que o produto de dois números naturais con-
secutivos é sempre divisível por 2.
98 3 Divisibilidade
Solução. Se n ∈ N temos que provar que an = n(n+1) é divisível por
2. Quando fazemos a divisão de n por 2 temos duas possibilidades
para o resto: r = 0 ou r = 1. Analisemos os dois casos por separado.
• [r = 0] Neste caso o resto que deixa an na divisão por 2 é o
mesmo que o resto que deixa 0(0+1)=0, logo an é divisível por
2.
• [r = 1] Neste caso podemos substituir an por 1(1+1)=2 e o
resto que este último deixa quando é dividido por 2 é 0, logo an
também é divisível por 2.
Mostraremos agora como utilizar o exemplo anterior pra resolver
um dos problemas da 1a Olimpíada Brasileira de Matemática.
Exemplo 3.12. Prove que se n é ímpar, então n2 − 1 é múltiplo de
8.
Solução. Como n é ímpar, podemos escrever n = 2m+ 1, para algum
k ∈ Z. Logo
n2 − 1 = (2m+ 1)2 − 1 = 4m2 + 4m+ 1− 1 = 4m2 + 4m.
Assim,
n2 − 1 = 4m(m+ 1).
Observe que de acordo com o exemplo 3.11, m(m + 1) é múltiplo de
2. Portanto, m(m+ 1) = 2q para algum q ∈ Z, de aonde
n2 − 1 = 4m(m+ 1) = 4 · 2q = 8q,
como queríamos demonstrar.
3.2 Bases Numéricas 99
Exemplo 3.13. Prove que em qualquer triângulo retângulo com lados
inteiros, pelo menos um deles é múltiplo de 3.
Solução. Comecemos analisando quais são os restos possíveis para a
divisão por 3 de um número que é quadrado. De acordo com o lema
dos restos temos a seguinte tabela para os restos de n e n2, na divisão
por 3:
n n2
0 0
1 1
2 1
Resumindo, se um número não é múltiplo de 3 então o resto da divisão
de seu quadrado por 3 deve ser igual a 1.
Agora denotemos por a e b os catetos e por c a hipotenusa. Supo-
nhamos que nenhum deles é divisível por 3. Então a2 e b2 deixam resto
1 na divisão por 3. Logo, a2 + b2 deixa resto 12 + 12 = 2 na divisão
por 3; mas isto é uma contradição pois, pelo Teorema de Pitágoras,
a2 + b2 = c2 e c2 deixa resto 1 quando é dividido por 3.
3.2 Bases Numéricas
Começamos esta seção com uma brincadeira interessante.
João, ao sair da aula de matemática do professor Peitágoras, en-
controu Pedro e lhe propôs a seguinte brincadeira:
� Pense numa peça de dominó, Pedro. Vou adivinhar que peça é
essa usando uma fórmula mágica.
� Ok, João. Pode começar, já pensei.
100 3 Divisibilidade
x y
Figura 3.1: Peça de Dominó
- Escolha um dos números na peça e multiplique por 5. Depois
disso some três a esse resultado. Multiplique agora o número que você
obteve por dois. Some isto com o outro número da peça. Qual foi o
resultado?
� Foi 40.
� Então a peça que você escolheu foi a 3 com 4!
� Como você acertou? Me ensina!
Claro que de mágico João não tinha nada e decidiu contar seu
segredo a Pedro.
O jogo funciona assim: cada parte da peça de dominó pode ser
considerada como um dos dígitos de um número de 2 algarismos, o qual
denotamos por n = xy = 10x+ y (veja a Figura 3.1). Acompanhando
os passos de João, temos que:
(5x+ 3)2 + y = 40⇔ 10x+ y = 34, (3.14)
que claramente, tem por soluções: x = 3 e y = 4, usando a represen-
tação de 34 na base decimal.
No sistema de numeração decimal, também conhecido como sis-
tema numérico na base 10, todo número pode ser representado como
uma sequência de 10 símbolos, constituídos pelo 0 (zero) e os alga-
rismos 1, 2, 3, . . . , 9. Por exemplo, 345 escreve-se na base decimal da
3.2 Bases Numéricas 101
seguinte forma
345 = 300 + 40 + 5 = 3 · 102 + 4 · 10 + 5,
assim como 2768 se escreve da forma
2768 = 2000 + 700 + 60 + 8 = 2 · 103 + 7 · 102 + 6 · 10 + 8.
De modo geral, se denotamos por a = anan−1 . . . a1a0 o número inteiro
positivo formado pelos algarismos an, an−1, . . . , a1 e a0, nessa ordem,
então a se escreve na base decimal da forma
a = an10
n + an−110
n−1 + . . .+ a110 + a0 (3.15)
Antes de provar alguns dos critérios de divisibilidade mais po-
pulares do sistema de numeração decimal, provamos uma identidade
muito útil.
Lema 3.14. Sejam a, b, n ∈ N. Temos que
an − bn = (a− b)(an−1 + an−2b+ · · ·+ abn−2 + bn−1).
Consequentemente, se 0 < b < a, então a− b divide an − bn.
Demonstração. Primeiro provaremos que a propriedade vale para b =
1. Com efeito, considerando a soma geométrica
s = 1 + a+ a2 + · · ·+ an−1
e multiplicando s por a temos que
as = (a+ a2 + · · ·+ an−1) + an = s− 1 + an.
102 3 Divisibilidade
Assim, (a− 1)s = as− s = an − 1, de onde se segue que
an − 1 = (a− 1)(an−1 + an−2 + · · ·+ a+ 1). (3.16)
Daí temos a validade para b = 1.
Para b ∈ N qualquer, observe que an− bn = bn
[
(a
b
)n − 1
]
. Usando
esta expressão e (3.16) tem-se
an − bn = bn(a
b
− 1)
[
(a
b
)n−1 + (a
b
)n−2 + · · ·+ (a
b
) + 1
]
= (a− b)bn−1
[
(a
b
)n−1 + (a
b
)n−2 + · · ·+ (a
b
) + 1
]
= (a− b)(an−1 + an−2b+ · · ·+ abn−2 + bn−1),
(3.17)
obtendo-se a igualdade clamada.
Proposição 3.15 (Critérios de Divisibilidade). Seja a = an . . . a1a0
um inteiro positivo, então
(a) a é divisível por 10 se, e somente se, a0 for igual a 0;
(b) a é divisível por 3 ou por 9 se, e somente se, a soma dos seus
dígitos é divisível por 3 ou por 9, respectivamente;
(c) a é divisível por 5 se, e somente se, a0 for igual a 0 ou 5.
Demonstração. Utilizando a representação decimal (3.15) temos que
a = 10(an10
n−1 + an−110
n−2 + · · ·+ a1) + a0.
Então, pela Proposição 3.3-(b) tem-se que 10 | a se, e somente se,
10 | a0, prondose-se assim o critério (a).
Para provar (b) observemos que
a = an10
n + an−110
n−1 + · · ·+ 10a1 + a0
= an(10
n − 1) + an−1(10n−1 − 1) + · · ·+ (10− 1)a1
+ an + an−1 + · · ·+ a1 + a0.
(3.18)3.2 Bases Numéricas 103
Pelo Lema 3.14 temos que 10j − 1 = 9qj para todo 1 ≤ j ≤ n, daí
segue-se
a = 9(anqn + an−1qn−1 + · · ·+ a1) + an + an−1 + · · ·+ a1 + a0.
Então, aplicando novamente o item (b) da Proposição 3.3 temos que
9 | a se, e somente se, 9 | (an + an−1 + · · ·+ a1 + a0).
A prova para o caso da divisibilidade por 3 segue de maneira idêntica,
logo �ca provado o item (b).
A prova do item (c) segue de maneira muito semelhante e deixamos
a mesma a cargo do leitor.
Exemplo 3.16. Prove sem fazer muitas contas que o número
N = 13424136 + 1234567890
é divisível por 3.
Solução. Note que não precisamos fazer a soma dos números ante-
riores. Para mostrar isso, basta aplicar o item (b) da Proposição 3.3 e
o item (b) da Proposição 3.15, observando que cada um dos números
acima é divisível por 3, pois a soma de seus dígitos é um múltiplo de
3.
Finalizamos esta seção com uma aplicação da divisão euclidiana
que nos mostra que, analogamente à representação decimal, qualquer
número admite uma representação única em qualquer outra base nu-
mérica.
104 3 Divisibilidade
Teorema 3.17 (Bases Numéricas). Dados a, b ∈ N, com b > 1, exis-
tem únicos números naturais r0, r1, . . . , rn tais que 0 ≤ ri ≤ b− 1,
0 ≤ i ≤ n, e satisfazendo
a = rnb
n + rn−1b
n−1 + · · ·+ r1b+ r0.
A representação acima é dita representação de a na base b e usaremos
a notação
a = (rncn−1 . . . r1r0)b,
para fazer referência a esta.
Demonstração. Apliquemos sucessivamente a divisão euclidiana como
segue:
a = bq0 + r0, r0 < b,
q0 = bq1 + r1, r1 < b,
q1 = bq2 + r2, r2 < b,
...
...
...
...
qj−1 = bqj + rj, rj < b,
e assim por diante. Como a > q0 > q1 > q2 > · · · > qj−1, para algum
j = n deveremos ter que qn−1 < b. Logo, qj = 0 para todo j ≥ n,
assim como rj = 0 para todo j ≥ n + 1. Das igualdades acima, para
3.2 Bases Numéricas 105
1 ≤ j ≤ n, tem-se
a = bq0 + r0,
bq0 = b
2q1 + br1,
b2q1 = b
3q2 + b
2r2,
...
...
...
bn−1qn−2 = b
nqn + b
n−1rn−1
bnqn−1 = b
n+10 + bnrn.
(3.19)
Efetuando a soma de todas as igualdades em (3.19) obtemos
a = rnb
n + rn−1b
n−1 + · · ·+ r1b+ r0.
A unicidade dos números ri vem da unicidade dos restos na divisão
euclidiana.
Observação 3.18. O sistema de numeração na base 2 é também co-
nhecido como sistema binário e é o sistema habitualmente utilizado no
funcionamento dos computadores.
Exemplo 3.19. Se deseja pesar qualquer número inteiro de gramas de
ouro, entre 1g e 100g, numa balança de dois pratos, onde os pesos só
podem ser usados no prato esquerdo da balança. Mostre que a escolha
adequada de 7 pesos diferentes é su�ciente para realizar esta tarefa.
Demonstração. Usando o sistema de numeração em base 2 temos que
qualquer número a tal que 1 ≤ a ≤ 100 pode ser expressado de forma
única como
a = r62
6 + r52
5 + r42
4 + r32
3 + r22
2 + r12 + r01,
106 3 Divisibilidade
com ri ∈ {0, 1}, 0 ≤ i ≤ 1. Observe que 2n ≥ 128, com n ≥ 7, logo
estas potências não são consideradas. notemos também que o fato de
cada ri ser 0 ou 1 nos diz que não precisamos repetir nenhum dos
pesos na realização de qualquer pesada. Logo, os pesos
1, 22, 23, 24, 25, 26
são su�cientes para realizar as pesadas de gramas de ouro entre 1g e
100g.
3.3 Máximo Divisor Comum eMínimoMúl-
tiplo Comum
Nesta seção estudaremos dois conceitos fundamentais, que aparecem
naturalmente em vários problemas de divisibilidade, assim como a
relação existente entre eles.
3.3.1 Máximo Divisor Comum
O primeiro destes conceitos está relacionado com os inteiros positivos
que dividem simultaneamente a dois inteiros pre�xados e é denomi-
nado máximo divisor comum.
Daqui por diante só consideraremos os divisores positivos dos nú-
meros.
De�nição 3.20 (Máximo Divisor Comum). Sejam a e b inteiros dife-
rentes de zero. O máximo divisor comum, resumidamente mdc, entre
a e b é o número d que satisfaz as seguintes condições:
(a) d é um divisor comum de a e b, isto é, d | a e d | b;
3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 107
(b) d é o maior inteiro positivo com a propriedade (a).
Neste caso, denotamos o mdc entre a e b por d = mdc(a, b) ou por
d = (a, b). Se (a, b) = 1, então dizemos que a e b são primos entre si.
Exemplo 3.21. Observando que 12 = 6 · 2, 18 = 6 · 3 temos que
mdc.(12, 18) = 6. Por outro lado, mdc.(4, 15) = 1, logo os números 4
e 15 são primos entre si.
Vejamos agora algumas das propriedades mais importantes dos
divisores comuns de dois inteiros.
Proposição 3.22. Sejam a e b dois inteiros. Então valem as seguintes
a�rmações.
(a) Se a é múltiplo de b, então (a, b) = b.
(b) Se a = bq+ c, c 6= 0, então o conjunto dos divisores comuns dos
números a e b coincide com o conjunto dos divisores comuns dos
números b e c. Particularmente, (a, b) = (b, c).
Demonstração. Começamos com a prova de (a). Com efeito, todo
divisor comum dos números a e b é um divisor de b. Reciprocamente,
usando que a é múltiplo de b, todo divisor de b é também um divisor
de a, ou seja, um divisor comum dos números a e b. Portanto, o
conjunto dos divisores comuns dos números a e b é igual ao conjunto
dos divisores de b. Como o maior divisor de b é ele mesmo, resulta que
(a, b) = b.
Vejamos (b). Usando o item (b) da Proposição 3.3 temos que
todo divisor comum de a e b também divide c e, consequentemente, é
um divisor de b e c. Pela mesma razão todo divisor comum de b e c
também divide a e, consequentemente, é um divisor de a e b. Portanto
108 3 Divisibilidade
os divisores comuns de a e b são os mesmos que os divisores comuns
de b e c. Particularmente, também coincidem os maiores divisores
comuns, ou seja, (a, b) = (b, c).
O teorema a seguir é uma das ferramentas básicas na resolução
de problemas que envolvem o mdc entre dois números. O resultado
foi provado pela primeira vez por Claude-Gaspard Bachet de Méziriac
(1581-1638) e mais tarde generalizado para polinômios por Étienne
Bézout (1730-1783). Frequentemente, na literatura se enuncia este
resultado como teorema (ou identidade) de Bézout, esquecendo-se o
nome de Bachet.
Teorema 3.23 (Teorema de Bachet-Bézout). Se d é o mdc de a e b,
então existem números inteiros x0 e y0 tais que d = (a, b) = ax0+ by0.
Demonstração. Considere a combinação linear ax + by, onde x e y
percorrem todos os inteiros. Este conjunto de inteiros, denotado por
Ca,b = {ax+ by; x, y ∈ Z},
inclui valores positivos e negativos. Além disso, escolhendo x = y = 0,
vemos que Ca,b também contém o zero.
Pelo princípio da boa ordenação, podemos escolher x0 e y0 tais que
λ = ax0+by0 seja o menor número inteiro positivo contido no conjunto
Ca,b.
Agora mostraremos que λ | a e λ | b. Provaremos que λ | a e o
outro segue analogamente. Usaremos para este propósito o método de
redução ao absurdo, ou seja, vamos supor que λ - a e obteremos uma
contradição.
3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 109
Usando a divisão euclidiana, de λ - a segue que existem inteiros q
e r tais que a = λq + r com 0 < r < λ. Portanto,
r = a− λq = a− q(ax0 + by0) = a(1− qx0) + b(−qy0)
e assim r está no conjunto Ca,b, o que contradiz a hipótese de λ ser o
menor elemento positivo contido em Ca,b.
Uma vez que λ divide a e b só resta provar que λ = d. Com efeito,
desde que d = (a, b), podemos escrever a = da1, b = db1 e
λ = ax0 + by0 = d(a1x0 + b1y0).
Assim d | λ. Logo pela parte (c) da Proposição 3.3, concluímos que
d ≤ λ. Agora d < λ é impossível pois d = mdc(a, b), e portanto
d = λ = ax0 + by0.
A seguinte proposição resume algumas consequências importantes
da demonstração dada ao teorema de Bézout.
Proposição 3.24. Sejam d, λ ∈ N e a, b, c ∈ Z. Então valem as
seguintes a�rmações:
(a) Se d | a e d | b, então d | (a, b).
(b) O mdc.(a, b) é o menor valor positivo de ax + by, onde x e y
percorrem todos os números inteiros.
(c) (λa, λb) = λ(a, b).
(d) Se d | a e d | b, então (a
d
, b
d
) = 1
d
(a, b). Consequentemente,(
a
(a, b)
,
b
(a, b)
)
= 1.
110 3 Divisibilidade
(e) Se (a, c) = (b, c) = 1, então (ab, c) = 1.
(f) Se c | ab e (b, c)= 1, então c | a.
Demonstração. A prova de (a) é consequência imediata da igualdade
(a, b) = ax0 + by0 anunciada no teorema de Bézout; assim como (b)
segue diretamente da demonstração dada a este teorema.
Para provar (c), primeiro observamos que
(λa)x+ (λb)y = λ(ax+ by) onde x, y ∈ Z.
Usando o item (a) e o fato de λ ser positivo, da igualdade acima segue
que
(λa, λb) = min
{
(λa)x+ (λb)y > 0; x, y ∈ Z
}
= λmin
{
ax+ by ; x, y ∈ Z
}
= λ(a, b).
A a�rmação feita em (d) segue diretamente de (c), observando que
(a, b) =
(
d
a
d
, d
b
d
)
= d
(
a
d
,
b
d
)
.
Continuamos com a prova de (e). De (a, c) = (b, c) = 1, temos que
existem inteiros xj e yj, j = 1, 2, tais que
ax1 + cy1 = 1,
bx2 + cy2 = 1.
Multiplicando lado a lado as igualdades obtemos
(x1x2︸︷︷︸
x
)ab+ (ax1y2 + y1bx2 + cy1y2︸ ︷︷ ︸
y
)c = 1.
3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 111
Então, usando o item (b) e a igualdade acima resulta que (ab, c) = 1.
Finalmente, provaremos (f). Das hipóteses temos que existem in-
teiros x0 e y0 tais que
bx0 + cy0 = 1.
Multiplicamos a igualdade acima por a em ambos lados para obtermos
abx0 + acy0 = a.
Por outro lado, ab = cq para algum inteiro q. Usando esta condição
na última igualdade temos que
cqx0 + acy0 = c(qx0 + ay0) = a,
logo c | a.
3.3.2 Algoritmo de Euclides
Apesar de conhecermos propriedades teóricas do mdc entre dois intei-
ros, encontrá-lo de fato pode ser uma tarefa complicada, sem auxílio
das ferramentas corretas. Lembrando o seu signi�cado, o leitor talvez
pudesse pensar que devemos calcular todos os divisores de a, todos
os divisores de b e descobrir qual é o maior elemento comum aos dois
conjuntos.
Para achar o mdc se faz uso de um importante método denominado
algoritmo de Euclides .
Teorema 3.25 (Algoritmo de Euclides). Dados dois inteiros positivos,
a e b, aplicamos sucessivamente a divisão euclidiana para obter a se-
112 3 Divisibilidade
guinte sequência de igualdades
b = aq1 + r1, 0 ≤ r1 < a,
a = r1q2 + r2, 0 ≤ r2 < r1,
r1 = r2q3 + r3, 0 ≤ r3 < r2,
· · · · · · · · · · · · · · ·
rn−2 = rn−1qn + rn, 0 ≤ rn < rn−1,
rn−1 = rnqn+1,
(3.20)
até algum rn dividir rn−1. Assim, o mdc.(a, b) = rn, ou seja, é o
último resto não-nulo no processo de divisão anterior.
Observação 3.26. Quando lidamos com números pequenos achar o
mdc é uma tarefa fácil pois podemos calcular o mdc valendo-nos das
fatorações dos números envolvidos. No entanto, quando estamos tra-
balhando com números grandes o algoritmo de Euclides, em geral, é
mais fácil que a fatoração, podendo ser esta última bem difícil.
Demonstração do algoritmo de Euclides. Começamos observando que
o processo de divisão (3.20) é �nito. Com efeito, a sequência de núme-
ros inteiros rk é estritamente decrescente e está contida no conjunto
{r ∈ Z, 0 ≤ r < a}, portanto não pode conter mais do que a intei-
ros positivos. Examinando as igualdades (3.20) de cima para baixo e
usando a Proposição 3.22 temos que
(a, b) = (a, r1) = (r1, r2) = · · · = (rn−1, rn) = rn.
3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 113
Observação 3.27. Notemos que o teorema de Bézout também pode
ser obtido como consequência do processo de divisão (3.20). Com
efeito, podemos escrever
rn = rn−2 − rn−1qn
rn−1 = rn−3 − rn−2qn−1
}
⇒ rn = rn−2 − (rn−3 − rn−2qn−1)qn.
Logo, conseguimos escrever rn em termos de rn−2 e rn−3. Utilizando a
expressão rn−2 = rn−4− rn−3qn−2 podemos escrever rn como combina-
ção de rn−3 e rn−4. Repetindo este processo várias vezes, concluímos
que existem x, y ∈ Z tais que
d = rn = xr1 + yr2.
Ora, como r1 = b − aq1 e r2 = a − r1q2 = a(1 + q1q2) − bq2, então,
substituindo estes valores na última igualdade obtemos o Teorema de
Bézout.
Exemplo 3.28. Achar o máximo divisor comum dos números 471 e
1.176.
Solução. Aplicando o algoritmo de Euclides obtemos a seguinte sequên-
cia de divisões com resto:
1176 = 471 · 2 + 234,
471 = 234 · 2 + 3,
234 = 78 · 3,
então o mdc(471, 1176) = 3.
Exemplo 3.29. Provar que a fração
2n+ 8
4n+ 15
é irredutível para todo
número natural n.
114 3 Divisibilidade
Solução. Usando o algoritmo de Euclides temos que
4n+ 15 = (2n+ 8) · 1 + 2n+ 7,
2n+ 8 = (2n+ 7) · 1 + 1,
2n+ 7 = (2n+ 7) · 1.
Então o mdc.(4n + 15, 2n + 8) = 1 e portanto 4n + 15 e 2n + 8 são
primos entre si para qualquer valor de n.
Exemplo 3.30. Achar o mdc.(111 . . . 111︸ ︷︷ ︸
100 vezes
, 11 . . . 11︸ ︷︷ ︸
60 vezes
)
Solução. Primeiro escrevemos os números na base decimal, isto é,
111 . . . 111︸ ︷︷ ︸
100 vezes
= 1099 + 1098 + · · ·+ 1,
11 . . . 11︸ ︷︷ ︸
60 vezes
= 1059 + 1058 + · · ·+ 1.
Aplicamos agora o algoritmo de Euclides para obter as seguintes igual-
dades
111 . . . 111︸ ︷︷ ︸
100 vezes
= (1059 + 1058 + · · ·+ 1)1040 + 1039 + 1038 + · · ·+ 1,
1059 + 1058 + · · ·+ 1 = (1039 + 1038 + · · ·+ 1)1020+
+ 1019 + 1018 + · · ·+ 1,
1039 + 1038 + · · ·+ 1 = (1019 + 1018 + · · ·+ 1)1020+
+ 1019 + 1018 + · · ·+ 1.
Disso resulta que
mdc.(111 . . . 111︸ ︷︷ ︸
100 vezes
, 11 . . . 11︸ ︷︷ ︸
60 vezes
) = 1019 + 1018 + · · ·+ 1 = 11 . . . 11︸ ︷︷ ︸
20 vezes
.
3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 115
3.3.3 Mínimo Múltiplo Comum
Agora passamos ao segundo conceito importante desta seção. O mesmo
está relacionado com os inteiros positivos que são simultaneamente
múltiplos de dois inteiros pre�xados e é denominado mínimo múltiplo
comum.
De�nição 3.31 (Mínimo Múltiplo Comum). Sejam a e b inteiros
diferentes de zero. O mínimo múltiplo comum, resumidamente mmc,
entre a e b é o inteiro positivo m que satisfaz as seguintes condições:
(a) m é um múltiplo comum de a e b, isto é, a | m e b | m;
(b) m é o menor inteiro positivo com a propriedade (a).
Neste caso, denotamos o mmc entre a e b por m = mmc(a, b) ou por
m = [a, b].
Resumimos a seguir algumas das propriedades fundamentais do
mmc de dois inteiros.
Proposição 3.32. Sejam a, b, c ∈ Z e λ ∈ Z. Então valem as se-
guintes a�rmações:
(a) se c é múltiplo comum de a e b, então [a, b] | c;
(b) [λa, λb] = λ[a, b];
(c) |ab| = [a, b] · (a, b).
Demonstração. Começamos com a prova de (a). A divisão com resto
de c por [a, b] nos dá
c = [a, b]q + r, 0 ≤ r < [a, b]. (3.21)
116 3 Divisibilidade
Da igualdade anterior, basta provar que r = 0 para obter o resultado
desejado. Suponhamos, pelo contrário, que 0 < r < [a, b]. Notemos
que tanto a como b dividem c e [a, b]. Logo, pelo item (b) da Pro-
posição 3.3 e a igualdade (3.21), temos que a e b também dividem r,
ou seja, r é múltiplo comum de a e b e não pode ser menor que [a, b],
contradizendo nossa suposição.
Prosseguimos com a prova de (b). Observemos que λ[a, b] é múlti-
plo comum de λa e λb, logo pelo item (i) vale que
[λa, λb] ≤ λ[a, b]. (3.22)
Por outro lado, [λa, λb] = q1λa = q2λb, para alguns inteiros q1 e q2;
logo, [λa,λb]
λ
é um múltiplo comum de a e b. Portanto,
[a, b] ≤ [λa, λb]
λ
⇔ λ[a, b] ≤ [λa, λb]. (3.23)
Das igualdades (3.22) e (3.23) segue que
λ[a, b] ≤ [λa, λb] ≤ λ[a, b],
de onde vem diretamente o resultado.
Para provar (c) podemos supor sem perda de generalidade que a e
b são positivos devido às igualdades
[a, b] = [a,−b] = [−a, b] = [−a,−b].
Dividiremos a prova em dois casos:
Caso 1: (a, b) = 1.
Sabemos que b | [a, b] e [a, b] = qa, para algum q ∈ N. Então b | qa
e além disso (a, b) = 1. Logo, pelo item (v) da Proposição 3.24 temos
que b | q. Portanto, b ≤ q e consequentemente
ab ≤ aq = [a, b]. (3.24)
3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 117
Entretanto, da de�nição de [a, b] vale que
[a, b] ≤ ab. (3.25)
Das desigualdades (3.24) e (3.25) segue que ab ≤ [a, b] ≤ ab. Assim,
ab = [a, b] = [a, b] · 1 = [a, b] · (a, b).
Caso 2: (a, b) > 1.
Da parte (c) da Proposição 3.24 sabemos que
(
a
(a,b)
, b
(a,b)
)
= 1.
Aplicando o caso anterior vale que
a
(a, b)
· b
(a, b)
=
[
a
(a, b)
,
b
(a, b)
]
·
(
a
(a, b)
,
b
(a, b)
)
.
Multiplicamos esta última igualdade por (a, b)2 e usamos o item (b)
provado anteriormente, assim como a parte (d) da Proposição 3.24
paraobter
ab = (a, b)
[
a
(a, b)
,
b
(a, b)
]
(a, b)
(
a
(a, b)
,
b
(a, b)
)
= [a, b] · (a, b).
Exemplo 3.33. Dois amigos passeiam de bicicleta, na mesma dire-
ção, em torno a uma pista circular. Para dar uma volta completa um
deles demora 15 minutos e o outro demora 18 minutos. Eles partem
juntos e combinam interromper o passeio quando os dois se encontra-
rem pela primeira vez no ponto de partida. Quantas voltas deu cada
um?
Solução. Denotemos por n1 e n2, respectivamente, o número de voltas
que dá cada um dos amigos. Notemos que o tempo total da corrida é
o menor valor positivo de T que satisfaz as igualdades
T = 15n1 = 18n2,
118 3 Divisibilidade
ou seja
T = [15, 18] =
15 · 18
3
= 90.
Portanto, n1 = 6 e n2 = 5.
Finalizamos esta seção com um exemplo que nos fornece uma bela
interpretação geométrica do mínimo múltiplo comum. O mesmo foi
proposto na Olimpíada Brasileira de Matemática.
Exemplo 3.34. Um retângulo de lados inteiros AB = m e CD = n,
é dividido em quadrados de lado 1. Em cada um dos vértices ele possui
um pequeno orifício. Um raio de luz entra no retângulo por um dos
vértices, na direção da bissetriz do ângulo reto, e é re�etido sucessi-
vamente nos lados do retângulo. Quantos quadrados são atravessados
pelo raio de luz?
A B
CD
Figura 3.2: Interpretação geométrica do mmc
Solução. Se �zermos alguns testes preliminares dando valores a m e
n, veremos que em cada caso a resposta coincidirá com o mmc(m,n).
Provemos que isto de fato vale para m e n quaisquer. Para realizar a
prova nos auxiliaremos da Figura 3.2.
3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 119
Primeiramente, notemos que cada vez que o raio de luz atravessa
um quadrado ele avança uma unidade tanto na direção horizontal como
na direção vertical. Usando este fato fazemos as observações a seguir.
• Se o raio entra pelo vértice A, terá que atravessar m quadrados
até chegar ao lado BC, imediatamente mais m para chegar ao
lado AD, depois mais m para chegar novamente ao lado BC, e
assim sucessivamente. Além disso, depois do raio percorrer pm
quadrados, com p ∈ N, estará batendo no lado BC ou no lado
AD.
• Analogamente o raio baterá no lado AB ou no lado DC se, e
somente se, atravessar qn quadrados, com q ∈ N.
• Somente nos vértices B, C e D do retângulo pode acontecer que
o raio incidente saia do retângulo, terminando assim o processo
de re�exão.
Usando as observações acima é fácil ver que o raio chegará a um
vértice quando chegar simultaneamente a dois lados perpendiculares
do retângulo. Portanto, deve ter atravessado um número x de quadra-
dos tal que x = pm = qn, ou seja, x deverá ser um múltiplo comum
de m e n. É claro que a primeira vez que o raio chega a um vértice o
número x é o menor múltiplo comum de m e n, isto é, x = [m,n].
Finalmente, observamos que nenhum dos quadrados é atravessado
duas vezes no percurso do raio de A até bater no primeiro vértice, pois
como vemos na �gura numa das direções os quadrados atravessados
serão todos cinzas e na outra direção, serão todos brancos.
120 3 Divisibilidade
3.3.4 Equações Diofantinas Lineares
Consideremos a equação
ax+ by = c, (3.26)
onde a, b, c ∈ Z, com a 6= 0 e b 6= 0.
A equação (3.26) é chamada de equação diofantina linear e uma
solução desta é qualquer par de inteiros (x, y) que satisfaçam (3.26).
É conhecido que todos os pontos do plano, com coordenadas (x, y),
que satisfazem a igualdade (3.26) representam, geometricamente, uma
reta. Logo, as soluções de uma equação diofantina linear são os pontos
de coordenadas inteiras do plano cartesiano, que estão dispostos sobre
a reta que esta representa. Por exemplo, os pontos (−1,−2) e (1, 1)
são soluções da equação diofantina 3x− 2y = 1, veja a Figura 3.3.
-3 -2 -1 0 1 2
-3
-2
-1
0
1
2
3
x
y
•
•
ℓ
Figura 3.3: A equação da reta ` é 3x− 2y = 1.
Naturalmente nos perguntamos: É sempre possível achar soluções
para uma equação diofantina linear? A resposta é não; o próximo
resultado nos diz quando isto é possível. Além disso, se uma equação
diofantina linear tem uma solução na verdade ela tem uma in�nidade
de soluções.
3.3 Máximo Divisor Comum e Mínimo Múltiplo Comum 121
Proposição 3.35. A equação diofantina linear
ax+ by = c, a, b, c ∈ Z, com a 6= 0 e b 6= 0, (3.27)
tem solução se, e somente se, d | c, onde d = (a, b). Além disso,
se (x0, y0) é uma solução, então o conjunto de soluções de (3.27) é
constituído por todos os pares de inteiros (x, y) da forma:
x = x0 + t
b
d
e y = y0 − tad , t ∈ Z. (3.28)
Demonstração. Primeiramente suponhamos que (x0, y0) é uma solução
de (3.27), logo ax0 + by0 = c. Usando que d = (a, b) sabemos que
existem inteiros q1 e q2, tais que dq1 = a e dq2 = b. Portanto, se
veri�ca a igualdade
dq1x0 + dq2y0 = d(q1x0 + q2y0) = c,
de onde segue obviamente que d | c.
Reciprocamente, suponhamos que d | c e portanto c = qd com q
inteiro. O teorema de Bézout nos garante a existência de dois inteiros,
x0 e y0, tais que ax0 + by0 = d. Multiplicando ambos os lados desta
última igualdade por q temos que
ax0q + by0q = c,
logo o par (x1, y1), com x1 = x0q e y1 = y0q, é solução da equação
diofantina.
Resta provar agora que temos in�nitas soluções da forma (3.28).
Com efeito, sendo (x, y) uma outra solução qualquer além de (x0, y0),
vale que ax0 + by0 = c = ax+ by, de onde ax0 + by0 = ax+ by. Desta
igualdade obtemos a(x− x0) = b(y0 − y) e dividimos esta última por
d para obtermos
a
d
(x− x0) =
b
d
(y0 − y).
122 3 Divisibilidade
Como (a
d
, b
d
) = 1, então temos que a
d
| (y0 − y) e bd | (x − x0). Logo,
existe inteiro t tal que
x = x0 + t
b
d
e y = y0 − tad .
Por outro lado, é fácil veri�car que para qualquer inteiro t as expressões
achadas acima para x e y resolvem a equação diofantina.
A seguir damos um exemplo de como proceder para resolver equa-
ções diofantinas.
Exemplo 3.36. Achar todas as soluções inteiras da equação
12x+ 33y = 27.
Solução. Observemos que (12, 33) = 3 e que 3 | 27, logo a equa-
ção tem in�nitas soluções. Como sabemos, basta achar uma delas
e teremos as restantes. Para achar esta solução particular podemos
trabalhar de duas maneiras, que descrevemos a seguir:
Alternativa 1: reduzimos a equação à forma equivalente
4x+ 11y = 9,
e por tentativa e erro vemos que x0 = 5 e y0 = −1 solucionam a
mesma. Então pela Proposição 3.35 temos que
x = 5 + 11t e y = 4t− 1, t ∈ Z,
esgotam todas as soluções que procuramos.
Alternativa 2: aplicamos o algoritmo de Euclides para achar o
mdc (12, 33), obtendo os seguintes resultados:
33 = 12 · 2 + 9,
12 = 9 · 1 + 3,
9 = 3 · 3 + 0.
3.4 Números Primos e Compostos 123
Da segunda e primeira igualdades temos, respectivamente, que
3 = 12− 9 · 1 e 9 = 33− 12 · 2.
Usando estas duas obtemos
3 = 12− (33− 12 · 2) · 1
= 12− 33 + 12 · 2
= 3 · 12− 1 · 33,
ou seja, achamos x0 = 3 e y0 = −1, garantidos pelo teorema de
Bézout, que validam 3 = 12x0+33y0. Multiplicamos por 9 esta última
igualdade para obter
27 = 12(9x0) + 33(9y0).
Portanto, x̃0 = 9x0 = 27 e ỹ0 = 9y0 = −9 resolvem, particularmente,
a equação diofantina. Analogamente, como na alternativa anterior,
podemos escrever a solução geral da forma:
x = 27 + 11s e y = 4s− 9, s ∈ Z.
3.4 Números Primos e Compostos
Ao longo da história da Matemática, os números primos foram pro-
tagonistas de célebres problemas que motivaram o desenvolvimento
de teorias e técnicas pelas mentes mais férteis, como Fermat, Euler e
Gauss. Até hoje muitos desses problemas, simples de enunciar, que
envolvem números primos são desa�os intelectuais para toda a huma-
nidade.
124 3 Divisibilidade
Esta seção será dedicada ao estudo de propriedades básicas dos
números primos. Todo número natural n maior do que 1 tem pelo
menos 2 divisores, claramente 1 e n. Isto motiva a seguinte de�nição.
De�nição 3.37 (Números Primos e Compostos). Um inteiro positivo
n ≥ 2 é dito primo se os únicos divisores que ele tem são 1 e ele
próprio; caso contrário, é dito composto.
Observação 3.38. De modo geral o número1 não é considerado nem
primo nem composto.
Exemplo 3.39. Os números 2, 3, 5, 7, e 11 são primos e os números
10, 15, 35 e 348 são compostos.
Exemplo 3.40. O número n = 220 − 254 é composto.
Solução. Escrevemos n de outra forma, com o objetivo de facilitar
nosso trabalho. Com efeito, observemos que
n = (210)2 − (252)2 = 10242 − 6252,
logo é composto por ser diferença de quadrados. Além disso,
n = 10242 − 6252,
= (1024− 625)(1024 + 625),
= 399 · 1649,
= 3 · 133 · 1649.
(3.29)
Portanto, podemos concluir que 3 | n.
Proposição 3.41. Seja n > 1 um número inteiro. Então
(a) o menor divisor de n diferente de 1 é um número primo;
3.4 Números Primos e Compostos 125
(b) se n é composto, o seu menor divisor diferente de 1 não é maior
que
√
n. Em outras palavras, se n não possui divisores diferentes
de 1, menores ou igual que
√
n, então n é primo.
Demonstração. Começamos provando (a). Seja p o menor divisor de
n, diferente de 1. Se p fosse composto teria algum divisor q tal que
1 < q < p; mas
q | p e p | n,
o que nos diz que q | n, e isto contradiz a hipótese levantada sobre p.
Para provar (b) denotamos por p o menor divisor de n, diferente
de 1. Portanto, n = pq com q ≥ p. Multiplicando ambos lados da
desigualdade por p obtemos
n = pq ≥ p2,
e consequentemente vale
√
n ≥ p.
Agora vamos enunciar um dos resultados mais clássicos da Mate-
mática, que garante a existência de in�nitos números primos. Até
onde se conhece, a demonstração a seguir foi a primeira demonstração
escrita utilizando o método de redução ao absurdo e é devida a Eu-
clides cerca de 300 a.C. Para outras seis provas, incluindo a moderna
prova de Fustenberg, recomendamos os livros [1] e [10].
Teorema 3.42 (Teorema de Euclides). A quantidade de números pri-
mos é in�nita.
Demonstração. Faremos a prova por redução ao absurdo. Suponha
que existe uma quantidade �nita de números primos e denotemos estes
por
p1, p2, p3, . . . , pk.
126 3 Divisibilidade
Consideremos o número
n = p1p2p3 · · · pk + 1
e chamemos de q o seu menor divisor primo. Obviamente q não coin-
cide com nenhum dos números pi, 1 ≤ i ≤ k, pois caso contrário,
como ele divide n, teria que dividir 1, o que é impossível. Logo, te-
mos uma contradição à hipótese de termos uma quantidade �nita de
primos.
Os números primos também podem ser caracterizados da seguinte
maneira:
Proposição 3.43. Um inteiro positivo p é primo se, e somente se,
satisfaz a seguinte propriedade:
p | ab =⇒ p | a ou p | b (3.30)
onde a, b ∈ Z.
Demonstração. Primeiramente, suponhamos que p é primo e que p - b,
logo (p, b) = 1. Então, pelo item (f) da Proposição 3.24 temos que
p | a.
Reciprocamente, suponhamos que, a propriedade 3.30 é válida e
além disso vamos supor, pelo absurdo, que p não é primo. Então,
p = d1d2, com 1 < d1 < p, 1 < d2 < p. (3.31)
De (3.30) segue que p | d1 ou p | d2; consequentemente
p ≤ d1, ou p ≤ d2, (3.32)
contradizendo isto o a�rmado em (3.31).
3.5 Procurando Primos 127
3.5 Procurando Primos
Os números primos além de belos e desa�adores do ponto de vista
matemático, são extremamente importantes para as atividades usuais
de nosso dia a dia. Por exemplo, nenhuma transação bancária ou pela
internet estaria segura sem o uso de números primos muito grandes.
Assim, surge naturalmente a pergunta de como podemos produzi-los
em grandes quantidades. Essa pergunta sempre intrigou os matemá-
ticos e continua sem solução até os dias atuais. Apesar deles serem
abundantes, em quantidade in�nita de acordo com o Teorema 3.42,
não existe nenhum método razoável de produção de números primos,
mesmo tendo em mãos a alta tecnologia de hoje em dia. Porém, ao
longo do tempo algumas fórmulas e algoritmos se mostraram úteis
para a descoberta de números primos.
3.5.1 O Crivo de Eratóstenes
O crivo de Eratóstenes é um algoritmo que nos permite achar todos
os números primos que são menores ou iguais que um natural N dado.
Segundo a tradição, este método foi criado pelo matemático grego
Eratóstenes (285-194 a.C.).
O método consiste nos seguintes passos: escrevemos os números de
forma ordenada a partir de 2, isto é,
2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, . . . , n (3.33)
• Observamos que o primeiro primo que aparece em (3.33) é 2 e
imediatamente apagamos da lista (3.33) todos os múltiplos de
2 maiores que ele, por serem compostos; resta assim a seguinte
128 3 Divisibilidade
lista
2, 3, 5, 7, 9, 11, 13, 15, 17 . . .
• O primeiro número não apagado que aparece na lista restante é
3, que também é primo. Imediatamente apagamos da lista todos
os múltiplos de 3 maiores que ele, por serem compostos; resta
agora a lista
2, 3, 5, 7, 11, 13, 17, . . .
• O primeiro número não apagado que aparece na lista que restou
do passo anterior é 5, que também é primo. Imediatamente
apagamos da lista todos os múltiplos de 5 maiores que ele, por
serem compostos.
• Repetimos este processo até que o primeiro número não apagado
da lista em questão seja maior que
√
n, pois graças à Proposição
3.41-(b) a partir desse momento todos os números restantes são
os primos menores ou iguais que n..
Por exemplo, se n = 40, temos que
√
40 = 6, 324555. Então,
aplicando o método:
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
Passo 1: ordenamos os números
2 3 5 7 9
11 13 15 17 19
21 23 25 27 29
31 33 35 37 39
3.5 Procurando Primos 129
Passo 2: tiramos os múltiplos de 2
2 3 5 7
11 13 17 19
23 25 29
31 35 37
Passo 3: tiramos os múltiplos de 3
2 3 5 7
11 13 17 19
23 29
31 37
Passo 4: tiramos os múltiplos de 5
Como 72 = 49 > 40, paramos agora.
Observação 3.44. Note que ao começar a apagar os múltiplos de um
número primo p podemos começar a apagar a partir de p2, pois se
supomos que existe um número composto m não apagado menor que
p2, temos que m = p1q1, sendo p1 seu menor divisor primo. Então,
pelo item (b) da Proposição 3.41, p1 <
√
m < p, logo m deveria ter
sido apagado pois é múltiplo de um primo menor que p.
3.5.2 Primos de Mersenne
Marin Mersenne (1588-1648) foi um monge francês que nasceu na ci-
dade de Maine e foi um dos grandes in�uenciadores da Matemática
130 3 Divisibilidade
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
Tabela 3.1: Os primeiros 100 números primos
francesa nos séculos XVI e XVII. Apaixonado pelos números, teve en-
tre seus correspondentes Descartes, Fermat, Pascal e Galileu. Entre
suas várias descobertas, ele estudou os números da forma:
Mn = 2
n − 1.
Observe que vale o seguinte fato a respeito desses números:
Proposição 3.45. Se Mn é primo, então n é primo.
Demonstração. Provar essa proposição equivale a mostrar que a sua
forma contrarrecíproca vale. Ou seja, que se n é composto, digamos
n = a.b, com a ≥ b > 1, então Mn também é composto. De fato,
usando o Lema 3.14, podemos decompô-lo do seguinte modo:
Ma.b = 2
ab − 1 =
(
2a(b−1) − 2a(b−2) + · · ·+ 2a + 1
)(
2b − 1
)
.
3.5 Procurando Primos 131
Porém, não é verdade a recíproca da a�rmação acima. Por exem-
plo, Hudalricus Regius mostrou em 1536 que M11 = 211 − 1 = 2.047
não é primo, já que 2.047 = 23 · 89.
Em 1643, Mersenne a�rmou que para
n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 e 257,
os valores de Mn são todos primos e para todos os outros valores de n
menores que 257, Mn é composto.
Hoje sabemos que Mersenne errou na sua a�rmação, esquecendo
três valores de n ondeMn é primo: 61, 89 e 107 e incluindoM67 eM257
como números primos. Para mais informações, sugerimos a página web
http://primes.utm.edu/mersenne/index.html.
Finalizamos esta seção, com um critério interessante, devido à ma-
temática francesa Sophie Germain(1776-1831), que nos permite saber
quando um número não é primo.
Proposição 3.46 (Identidade de Sophie Germain). Dados a, b ∈ R,
vale a igualdade
a4 + 4b4 = (a2 + 2b2 + 2ab)(a2 + 2b2 − 2ab).
Demonstração. A prova segue das seguintes igualdades:
a4 + 4b4 = a4 + 4a2b2 + 4b4 − 4a2b2
= (a2 + 2b2)2 − 4a2b2
= (a2 + 2b2 + 2ab)(a2 + 2b2 − 2ab).
Como aplicação desta identidade vejamos os seguintes exemplos.
132 3 Divisibilidade
Exemplo 3.47. qn = n
4 + 4n é composto, para todo n ∈ N.
Solução. O conjunto dos números naturais é particionado em duas
classes disjuntas:o conjunto dos números pares e o conjunto dos nú-
meros ímpares. Estudaremos cada classe por separado. Assim,
• se n é um número par, então n = 2m para algum inteiro positivo
m ≥ 1. Deste modo,
n4 + 4n = (2m)4 + 42m = 16m4 + 24m,
= 2
(
8m4 + 24m−1
)
.
Portanto, neste caso, n4 + 4n ≥ 2. Logo, se n > 1 é qualquer
número inteiro positivo par temos que n4+4n não é um número
primo;
• se n é um número ímpar, então n = 2m + 1 para algum inteiro
positivo m ≥ 1. Assim,
n4 + 4n = (2m+ 1)4 + 42m+1 = (2m+ 1)4 + 4 · 42m
= (2m+ 1)4 + 4 · 24m = (2m+ 1)4 + 4 · (2m)4.
Logo, tomando a = 2m + 1 e b = 2m, o resultado é uma con-
sequência direta da identidade de Sophie Germain.
Exemplo 3.48. 520 + 230 é um número composto.
Solução. Escrevemos
520 + 230 = 55·4 + 22 · 228 =
(
55
)4
+ 4 ·
(
27
)4
,
de onde podemos usar a Identidade de Sophie Germain com a = 55 e
b = 27 para comprovar que o número 520 + 230 é composto.
3.5 Procurando Primos 133
3.5.3 O Teorema Fundamental da Aritmética
Os números primos são as células dos números naturais, no sentido
de que qualquer número natural é produto de números primos. Por
exemplo,
560 = 56 · 10 = 7 · 8 · 5 · 2 = 7 · 2 · 2 · 2 · 5 · 2,
onde cada um dos fatores que aparecem no produto são números pri-
mos. Perguntamo-nos, o que acontece se começamos com uma outra
fatoração inicial de 560, por exemplo, 560 = 28 · 20. Vejamos:
560 = 28 · 20 = 14 · 2 · 10 · 2 = 7 · 2 · 2 · 5 · 2 · 2.
Surpreendentemente chegamos à mesma representação anterior, salvo
a ordem dos fatores.
222
2 75
Figura 3.4: O número 560 é composto de 4 células do tipo 2, uma célula
do tipo 7 e uma célula do tipo 5.
O fato observado acima vale para qualquer número natural maior
que 1. Especi�camente, temos o seguinte resultado conhecido como
teorema fundamental da aritmética.
134 3 Divisibilidade
Teorema 3.49 (Teorema Fundamental da Aritmética). Todo número
natural n maior que 1 pode ser escrito como um produto
n = pα11 p
α2
2 p
α3
3 · · · pαmm , (3.34)
onde m ≥ 1 é um número natural, αi ∈ N e pi é primo para todo
1 ≤ i ≤ m . Além disso, a fatoração em (3.34) é única se exigirmos
que p1 < p2 < · · · < pm.
Demonstração. Seja n um inteiro maior que 1. Denotando por p1 seu
menor divisor primo tem-se que
n = p1β1, 1 ≤ β1 < n.
Se β1 = 1, então N1 = p1 e a fatoração desejada é obtida. Caso
contrário, denotando por p2 o menor divisor primo de β1 tem-se que
n = p1p2β2, 1 ≤ β2 < β1.
Se β2 = 1, então n = p1p2 e novamente chegamos à fatoração desejada.
Caso contrário, denotando por p3 o menor divisor primo de β2 tem-se
que
n = p1p2p3β3, 1 ≤ β3 < β2.
Continuando este processo sucessivamente obtemos então uma sequên-
cia estritamente decrescente de números naturais αn, ou seja,
n > β1 > β2 > β2 > · · · > βn > βn+1 > · · · ≥ 1,
Então, pelo princípio da boa ordem, só pode existir uma quantidade
�nita de índices n tais que βn > 1 e consequentemente βn+1 = 1, de
onde segue que
n = p1p2 · · · pn.
3.5 Procurando Primos 135
Notemos que na representação acima os pi podem-se repetir, resul-
tando �nalmente a representação desejada em (3.34).
Provaremos agora a unicidade de tal fatoração. Com efeito, supo-
nha que existem duas fatorações:
pα11 p
α2
2 p
α3
3 · · · pαmm = n = qβ11 qβ22 qβ33 · · · qβss
Pela Proposição 3.43 temos que cada pi divide algum qj, logo pi =
qj, por serem primos. Portanto, cada pi aparece no lado direito da
igualdade acima, e, um argumento análogo nos dá que cada qj também
aparece no lado esquerdo da igualdade. Então, como os pis e os qjs
são diferentes dois a dois e organizados crescentemente, temos m = s
e a igualdade se reduz a
pα11 p
α2
2 p
α3
3 · · · pαmm = pβ11 pβ22 pβ33 · · · pβmm .
Suponhamos agora que α1 seja diferente de β1; sem perda de ge-
neralidade vamos supor que α1 < β1. Portanto,
pα22 · pα33 · · · pαmm = pβ1−α11 pβ22 pβ33 · · · pβmm ,
e como β1 − α1 > 0 então, pela Proposição 3.43 temos que p1 di-
vide algum pj, com j > 1, o que é impossível. Portanto, α1 = β1.
Similarmente provamos que αi = βi, com i = 1, . . . , n.
Observação 3.50. O teorema fundamental da aritmética foi enun-
ciado precisamente por Gauss (1777-1855). Seus antecessores, Fer-
mat, Euler, Lagrange e Legendre, utilizavam este teorema sem a preo-
cupação de tê-lo enunciado ou demonstrado com precisão. Uma prova
alternativa deste teorema será apresentada no Capítulo 6, usando o
método de indução.
136 3 Divisibilidade
Exemplo 3.51. Prove que um número n é par se, e somente se, o
número 2 aparece na fatoração de n em fatores primos.
Solução. Obviamente, se 2 aparece na fatoração em primos de N ,
então N é par. Ora, se n é par temos que n = 2q. Por outro lado q e
n se fatoram, respectivamente, como
q = qα11 q
α2
2 · · · qαmm e n = pβ11 pβ22 · · · pβss .
Logo,
2 · qα11 qα22 · · · qαmm = pβ11 pβ22 · · · pβss .
Pela unicidade da fatoração, para algum i, com 1 ≤ i ≤ s, o cor-
respondente pi deve ser igual a 2. Portanto, 2 aparece na fatoração de
n.
Exemplo 3.52. Seja A = {1, 2, 3, 4, 5, 6, 7}. É possível decompor
o conjunto A em dois subconjuntos disjuntos tais que o produto dos
elementos de um seja igual ao produto dos elementos do outro?
Solução. Mostraremos que é impossível fazer esta decomposição. Com
efeito, suponha que existem tais conjuntos, A1 = {p1, p2, . . . , pr} e
A2 = {q1, q2, . . . , qs}. Então
p1p2 · · · pr︸ ︷︷ ︸
α
= q1q2 · · · qs︸ ︷︷ ︸
β
e além disso, como os conjuntos A1 e A2 são disjuntos, temos que o
número 5 aparece no produto α ou no produto β, mas não em ambos
simultaneamente. Por outro lado, o Teorema 3.49 nos diz que a fatora-
ção em primos de α é igual à fatoração em primos de β, logo o número
5 deveria aparecer tanto no produto α como no produto β, contra-
dizendo isto o fato anterior. Portanto não existe uma decomposição
com as condições exigidas.
3.5 Procurando Primos 137
Exemplo 3.53. Encontre todos os números inteiros e positivos n com
a propriedade de que o conjunto
A = {n, n+ 1, n+ 2, n+ 3, n+ 4, n+ 5}
pode ser particionado em dois subconjuntos tais que o produto dos
elementos de um dos subconjuntos seja igual ao produto dos elementos
do outro.
Demonstração. Digamos que seja possível essa decomposição para al-
gum n e vamos denotar os conjuntos que obtemos com a decomposição
por A1 e A2. Observando a decomposição dos elementos dos subcon-
juntos em fatores primos, temos que todo fator primo de A1 também
deverá pertencer a A2. No conjunto dos seis números só podemos ter
um múltiplo de 7, por isso não podemos tomar n como múltiplo deste
primo. Analogamente para primos maiores que 7. Analisando o primo
5, concluímos que n e n+ 5 são múltiplos de 5, pois se não, cairíamos
na análise anterior. Assim, os números n+ 1, n+ 2, n+ 3 e n+ 4 são
da forma 2α3β. Como entre eles existem dois ímpares, logo teremos
duas potências de 3 cuja diferença é 2, um absurdo. Assim, não existe
n que satisfaz as condições do enunciado.
Finalizamos esta seção com um exemplo que mostra como podemos
combinar os fatos estudados para resolver problemas mais difíceis
Exemplo 3.54. Encontre todos os números que são formados por 4
algarismos da forma aabb e que sejam quadrados perfeitos.
138 3 Divisibilidade
Solução. Como o número aabb é um quadrado perfeito, signi�ca que:
n2 =aabb
n2 =103a+ 102a+ 10b+ b =
(
103 + 102
)
· a+ (10 + 1) · b
n2 =1100 · a+ 11 · b
n2 =11
(
100a+ b
)
= 11
(
99a+ a+ b
)
.
Como 11 é primo é fácil ver, usando aProposição 3.43, que 112 | N2.
Segue-se então que 11 | (99a+a+b). Portanto, 11 | (a+b). Como aabb
tem 4 algarismos, segue-se que a 6= 0; portanto a ∈ {1, 2, 3, . . . , 9} e
b ∈ {0, 1, 2, . . . , 9}. De onde a + b ≤ 18. Logo, necessariamente
devemos ter a + b = 11. Podemos observar que a 6= 1, pois se a = 1
então b = 10. Analogamente, b 6= 0, 1. Portanto,
a ∈ {2, 3, 4, . . . , 9} e b ∈ {2, 3, 4, . . . , 9}.
Como em todo número quadrado perfeito o algarismo das unidades
somente pode acabar em 0, 1, 4, 5, 6 e 9. Segue-se que
b ∈ {4, 5, 6, 9}.
Certamente b 6= 5, pois todo número que acaba em 5 quando é elevado
ao quadrado sempre acaba em 25. Assim,
b ∈ {4, 6, 9}.
• Se b = 4, então a = 7. Neste caso o número seria 7.744 que é
um quadrado perfeito;
• Se b = 6, então a = 5. Neste caso o número seria 5.566 que não
é um quadrado perfeito;
3.6 Exercícios 139
• Se b = 9, então a = 2. Neste caso o número seria 2.299 que não
é um quadrado perfeito.
Finalmente, a única solução possível é aabb = 7.744 = 882.
3.6 Exercícios
1. Encontre o resto que deixa
(a) 2001 · 2002 · 2003 · 2004 + 20052 quando é dividido por 7;
(b) 2100 quando é dividido por 3;
(c) (1237156 + 34)28 quando é dividido por 111.
2. Provar que o número n5 + 4n é divisível por 5 para qualquer
número natural n.
3. Prove que se n é ímpar
(a) n3 − n é divisível por 24;
(b) n2 − 1 é divisível por 8;
(c) n2 + (n+ 2)2 + (n+ 4)2 + 1 é divisível por 12.
4. O número 21093 − 2 é divisível por 10932 ?
5. Prove que (999994)1234567890 − 1 é divisível por 333331.
6. O número N = 42005 + 20054 é primo?
7. Demonstre que o número 1 000 . . . 00︸ ︷︷ ︸
2006 zeros
1 é composto.
140 3 Divisibilidade
8. Utilizando o fato de que o resto de um quadrado quando dividido
por 4 só pode ser 0 ou 1, dê uma outra solução para o problema
do Exemplo 3.54.
9. Dados três inteiros, x, y, z, tais que x2 + y2 = z2, mostre que x
e y não são ambos ímpares e que xy é múltiplo de 6.
10. Demonstre que o quadrado de um inteiro é da forma 8n ou 8n+1
ou 8n+ 4.
11. Três números primos p, q e r, maiores que 3, formam uma pro-
gressão aritmética, ou seja, q = p+ d e r = p+ 2d. Prove que d
é divisível por 6.
12. Demonstrar que existem in�nitos números primos da forma 4m+
3 e da forma 6m+ 5, onde m ∈ Z.
13. Encontrar o último dígito dos números
(a) 19892005;
(b) 777777 + 250;
(c) 1 + 22 + 32 + · · ·+ 20052.
14. Prove que a soma dos quadrados de cinco números consecutivos
não é um quadrado perfeito.
15. Prove que 1 00 · · · 00︸ ︷︷ ︸
100−zeros
5 00 · · · 00︸ ︷︷ ︸
100−zeros
1 não é um cubo perfeito.
16. Seja b um inteiro positivo. Enuncie e prove o critério de divisi-
bilidade por b no sistema de numeração de base b.
17. Prove que os números
3.6 Exercícios 141
(a) αn = 1 +
1
2
+
1
3
+ · · ·+ 1
n
, com n > 1,
(b) βn =
1
3
+
1
5
+ · · ·+ 1
2n+ 1
, com n > 0,
não são inteiros.
18. Considere o polinômio p(n) = amnm + am−1nm−1 + · · · + a0 de
grau m ≥ 1 com coe�cientes inteiros e n ∈ N. Prove que p(n) é
um número composto para in�nitos valores de n.
Sugestão: Use o fato de que existe a ∈ N tal que α = |p(a)| > 1
e mostre que α divide a p(αk + a), para todo k ∈ Z.
19. Dizemos que um conjunto An formado por n inteiros positivos
escritos no sistema binário (base 2) é regular se, para qualquer
s inteiro não negativo a quantidade de números de An que con-
templam 2s na representação binária é par. Dizemos que An é
irregular se, pelo menos para algum s, este número é ímpar. De-
monstre que um sistema irregular pode se converter em regular
excluindo-se apenas um único elemento do mesmo, e, um sistema
regular pode se converter em irregular excluindo-se qualquer um
dos seus elementos.
20. Seja n um inteiro positivo. Demonstrar que todos os coe�cientes
do desenvolvimento do binômio de Newton (a+ b)n são ímpares
se, e somente se, n é da forma 2s − 1.
21. Prove que se (x0, y0) é uma solução da equação diofantina linear
ax − by = 1, então a área do triângulo cujos vértices são (0, 0),
(b, a) e (x0, y0) é 1/2.
142 3 Divisibilidade
22. Qual é a menor distância possível entre dois pontos (x1, y1) e
(x2, y2), com coordenadas inteiras, situados sobre a reta de�nida
pela equação diofantina ax+ by = c?
4
O Princípio da Casa dos
Pombos
Uma vez um matemáti
o me falou que o verdadeiro prazer não estáem a
har a verdade, mas em pro
urar por ela. Leo Tolstoy
Um interessante instrumento elementar para tratar problemas mate-
máticos relacionados à existência de elementos de conjuntos validando
certas exigências é o chamado princípio de Dirichlet , também conhe-
cido como princípio da casa dos pombos (PCP). Este princípio foi
usado por Dirichlet (1805-1859) para resolver problemas na Teoria
dos Números, entretanto ele possui um grande número de aplicações
em diversos ramos da Matemática como Combinatória e Geometria.
A seguir enunciamos a versão mais simples do PCP.
Proposição 4.1 (PCP � Versão Simples). Se distribuímos N + 1
pombos em N casas, então alguma das casas contém dois ou mais
pombos.
143
144 4 O Princípio da Casa dos Pombos
· · · · · · · · ·P1 P2 PN
C1 C2 CN
PN+1
Figura 4.1: Em cada casa Cj , 1 ≤ j ≤ N , coloca-se um único pombo,
denotado por Pj . O pombo restante, denotado por PN+1, deve ir para
alguma das casas, juntando-se ao que já se encontrava contido nela
Demonstração. A prova deste princípio é muito fácil e decorre de fa-
zer uma simples contagem dos pombos contidos em todas as casas de-
pois de distribuídos. Com efeito, suponhamos pelo contrário que em
cada casa não existe mais do que um pombo, então contando todos
os pombos contidos nas N casas não teremos mais do que N pombos,
contradizendo isto a hipóteses de termos N + 1 pombos distribuídos
nas N casas (ver Figura 4.1).
Não é difícil detectar quando o princípio pode ser usado, mas a
principal di�culdade para aplicá-lo reside em identi�car, em cada pro-
blema, quem faz papel de pombos e quem faz papel de casas.
Nas seguintes seções discutiremos vários exemplos de diferentes
naturezas onde o princípio da casa dos pombos é aplicado com sucesso.
4.1 Primeiros Exemplos 145
4.1 Primeiros Exemplos
Exemplo 4.2. Numa �oresta crescem 1.000 jaqueiras. É conhecido
que uma jaqueira não contém mais do que 600 frutos. Prove que
existem 2 jaqueiras na �oresta que têm a mesma quantidade de frutos.
Solução. Temos 1.000 jaqueiras, representando os pombos, e 601 casas
identi�cadas pelos números 0, 1, 2, 3, . . . , 600. O número k associado
a cada casa signi�ca que nela serão colocadas jaqueiras que têm exa-
tamente k frutos. Como 1000 > 602 = 601 + 1, o PCP nos garante
que existem duas jaqueiras com a mesma quantidade de frutos.
Exemplo 4.3. Em uma reunião há n pessoas. Mostre que existem
duas pessoas que conhecem exatamente o mesmo número de pessoas.
Solução. Os pombos neste caso são as n pessoas. As casas são enume-
radas com os números 0, 1, 2, . . . , n−1, indicando estes que na mesma
serão colocadas pessoas que têm essa quantidade de conhecidos. No-
temos que uma das casas enumeradas com 0 ou n − 1 permanece
desocupada, pois a possibilidade de conhecer 0 e n − 1 pessoas não
acontece simultaneamente. Logo, nas n − 1 casas restantes haverá
uma ocupada por dois ou mais pombos, depois de serem distribuídos.
Portanto, existem no mínimo duas pessoas com o mesmo número de
conhecidos.
Exemplo 4.4. Dados 8 números inteiros mostre que existem dois
deles cuja diferença é divisível por 7.
Solução. Consideramos os 8 números como sendo os pombos e as casas
como sendo os 7 possíveis restos na divisão por 7. Como temos 8 =
7 + 1 números o PCP nos diz que existem dois números dentro dos
146 4 O Princípio da Casa dos Pombos
8 dados que têm o mesmo resto quando divididos por 7. Finalmente,
observamos que se dois números deixam o mesmo resto na divisão por
7 então a diferença entre eles é divisível por 7.
Uma forma alternativa e muito útil na qual pode-se apresentar o
princípio da casa dos pombos é a seguinte:
Proposição 4.5 (PCP � VersãoAlternativa). Se a soma de n nú-
meros naturais é igual S, então existe pelo menos um deles que não
é maior que S/n, assim como existe pelo menos um deles que não é
menor que S/n.
Exemplo 4.6. Numa família formada por 5 pessoas a soma das idades
é de 245 anos. Prove que podem ser selecionados 3 membros da família
cuja soma das idades não é menor que 147.
Solução. Temos um total de
(
5
3
)
= 5!
3!2!
= 10 trios diferentes formados
por membros da família. Além disso, cada pessoa aparece exatamente
em
(
4
2
)
= 4!
2!2!
= 6 trios. Então, denotando por Ej a soma das idades
dos membros de cada trio Tj, j = 1, 2 . . . 10, temos que
E1 + E2 + · · ·+ E10 = 6 · 245 = 1470;
consequentemente existe algum trio Tj∗ tal que Ej∗ ≥ 147010 = 147.
4.2 Uma Versão mais Geral
A seguinte versão mais geral do PCP é bastante útil na resolução de
alguns problemas.
Proposição 4.7 (PCP � Versão Geral). Se distribuímos Nk+1 pom-
bos em N casas, então alguma das casas contém pelo menos k + 1
pombos.
4.2 Uma Versão mais Geral 147
A prova deste enunciado mais geral é similar à anterior. Com efeito,
suponhamos pelo contrário que em cada casa não existe mais do que
k pombos, então contando todos os pombos contidos nas N casas não
teremos mais do que Nk pombos, contradizendo isto a hipóteses de
termos Nk + 1 pombos distribuídos nas N casas.
Notemos que se k = 1, esta versão mais geral coincide com a versão
mais simples.
Exemplo 4.8. Num colégio com 16 salas são distribuídas canetas nas
cores preta, azul e vermelha para realizar uma prova de concurso. Se
cada sala recebe canetas da mesma cor então prove que existem pelo
menos 6 salas que receberam canetas da mesma cor.
Solução. Fazendo a divisão com resto de 16 por 3 temos que 16 =
3 · 5 + 1. Consideramos as 16 salas como sendo os pombos e as três
cores, preto, azul e vermelho como sendo as casas. Logo, podemos
�colocar� cada sala em uma das três cores. Assim, o PCP com N = 3
e k = 5 nos dá que existe uma casa com pelo menos 6 pombos, ou seja,
existem no mínimo 6 salas que receberam canetas da mesma cor.
Exemplo 4.9. Uma equipe formada por seis alunos de Matemática é
selecionada para representar o Brasil numa olimpíada internacional.
Mostre que necessariamente existem três deles que se conhecem mu-
tuamente, ou três deles que não se conhecem mutuamente.
Solução. Resolveremos o problema com o auxílio da Figura 4.2. Cada
aluno Aj, com j = 1, 2, . . . , 6, é representado por um dos vértices de
um hexágono regular. Quando dois alunos se conhecem traçamos o
segmento de reta que liga os vértices correspondentes com uma linha
contínua; caso contrário traçamos este segmento com uma linha pon-
tilhada. Logo, usando este esquema, o problema equivale a provar
148 4 O Princípio da Casa dos Pombos
que sempre existe um triângulo de lados contínuos ou um triângulo de
lados pontilhados com vértices no conjunto A = {A1, A2, . . . , A6}.
Temos 5 segmentos (pombos) incidindo no vértice A1, cada um
deles contínuo ou pontilhado (estes dois tipos de linhas são conside-
radas como as casas). Como 5 = 2 · 2 + 1, pelo PCP temos que 3
dos 5 segmentos são contínuos ou pontilhados. Suponhamos que 3 são
contínuos (caso contrário o argumento é similar) e denotemos estes
por A1A3, A1A4 e A1A6 (ver Figura 4.2). Se algum dos segmentos
A3A4, A3A6 ou A4A6 for contínuo então este segmento junto aos que
se ligam com A1 formam um triângulo de lados contínuos. Por outro
lado, se nenhum deles for contínuo, então eles formam um triângulo
de lados pontilhados, completando isto a demonstração.
A1
A2A3
A4
A5 A6
Figura 4.2: O triângulo A1A2A5 indica que os alunos A1, A2 e A5 não se
conhecem mutuamente e o triângulo A1A4A6 indica que os alunos A1, A4
e A6 se conhecem mutuamente
4.3 Aplicações na Teoria dos Números 149
4.3 Aplicações na Teoria dos Números
Nesta seção apresentamos alguns exemplos de aplicações do PCP na
Teoria dos Números. A primeira delas é:
Exemplo 4.10. Se n e m são números naturais, então o conjunto
A = {m+ 1,m+ 2, . . . ,m+ n} possui algum divisor de n.
Solução. Temos n números diferentes no conjunto acima. Vamos utili-
zar o método de redução ao absurdo. Se não existisse nenhum múltiplo
de n, quando dividíssemos os números do conjunto A por n, os res-
tos pertenceriam ao conjunto B = {1, 2, . . . , n− 1}, que possui n− 1
elementos. Logo, devem existir dois números m + i e m + j, com
1 ≤ i < j ≤ n tais que o resto da divisão de m + i por n é o mesmo
que o resto da divisão de m + j por n. Logo, m + j − (m + i) é um
múltiplo de n, o que implica que n > j − i ≥ 1 é múltiplo de n menor
que n (absurdo!). Logo, deve existir algum múltiplo de n no conjunto
A.
Como consequência desse exemplo, podemos resolver o próximo
problema.
Exemplo 4.11. Demonstrar que todo inteiro tem um múltiplo cuja
representação decimal começa com o bloco de dígitos 1234567890.
Solução. Se m e n são inteiros positivos, pelo exemplo anterior um
dos número m + 1,m + 2, . . . ,m + n é múltiplo de n. Assim, dado n
um inteiro qualquer, escolhe-se m = 1234567890×10n+1. Deste modo,
todos os inteiros m+1,m+2, . . . ,m+ n começam com 1234567890 e
algum deles é múltiplo de n.
150 4 O Princípio da Casa dos Pombos
Exemplo 4.12. Dado um número inteiro positivo n, mostre que existe
um múltiplo de n que se escreve com os algarismos 0 e 1 apenas. (Por
exemplo, se n = 3, temos 111 ou 1.101 etc.)
Solução. Consideramos os n+ 1 números
1, 11, 111, 1111, . . . , 111 · · · 1︸ ︷︷ ︸
n+1−vezes
(4.1)
como sendo os pombos e n casas enumeradas com os números
0, 1, 2, 3, . . . , n− 1,
ou seja, com os possíveis restos na divisão por n. Similarmente ao
exemplo anterior existem dois números na lista (4.1) que deixam o
mesmo resto na divisão por n e, portanto, a diferença entre o maior e
o menor é múltiplo de n. Obviamente a diferença entre dois números
quaisquer da lista (4.1) resulta em um número formado apenas pelos
algarismos 0 e 1.
Exemplo 4.13. Prove que entre n + 1 elementos escolhidos no con-
junto {1,2,3, . . . , 2n} existem dois que são primos relativos.
Solução. A escolha das casas e dos pombos neste exemplo não é tão ób-
via. Os pombos representam os n + 1 números escolhidos do conjunto
{1, 2, . . . , 2n} e as casas são escolhidas como sendo os n conjuntos:
Cj = {2j − 1, 2j}, 1 ≤ j ≤ n.
Logo, pelo PCP, quando distribuímos os n + 1 números nos n conjun-
tos Cj, 1 ≤ j ≤ n, dois deles �carão juntos em algum conjunto Cj, ou
seja, estes números serão consecutivos e portanto primos entre si.
4.4 Aplicações Geométricas 151
Finalizaremos esta seção com uma outra prova do teorema de
Bachet-Bézout, (veja o Teorema 3.23).
Exemplo 4.14. Seja d = (a, b) o mdc entre os números naturais a e
b. Então, existem x e y números inteiros tais que
ax+ by = d.
Solução. Denotando por m = a/d e n = b/d, podemos supor que a e
b são primos entre si. Realmente, se podemos escrever
mx+ ny = 1
então, substituindo os valores de m e n na equação acima, temos que
ax+ by = d.
Se (a, b) = 1, considere a sequência A = {a, 2a, . . . , ba}. A�rmamos
que existe algum número no conjunto A que deixa resto 1 quando
dividido por b. De fato, se isso não ocorresse, teríamos b números em
A deixando no máximo b − 1 restos diferentes quando divididos por
b. Logo, pelo PCP, dois deles, digamos ia e ja com b > j > i ≥ 1,
devem deixar o mesmo resto quando divididos por b. assim, (j − i)a
é divisível por b. Como estamos supondo que (a, b) = 1, temos que b
deve dividir j − i > 0. Como b > j − i, temos um absurdo.
Assim, algum dos números em a deixa resto 1 quando divididos
por b. Digamos que esse número seja ax. Logo, ax − 1 é múltiplo de
b, onde ax− 1 = by, o que encerra nossa prova.
4.4 Aplicações Geométricas
Na geometria também encontramos belas aplicações do PCP. Vejamos
os problemas a seguir para constatar isto.
152 4 O Princípio da Casa dos Pombos
Exemplo 4.15. Mostre que se tomamos cinco pontos quaisquer sobre
um quadrado de lado 1, então pelo menos dois deles nãodistam mais
que
√
2/2.
Solução. Vamos dividir o quadrado em quatro quadradinhos de lado
1/2, como mostra a �gura. Logo, pelo PCP pelo menos dois deles de-
1
•
••
•
•
vem estar no mesmo quadradinho, uma vez que temos 4 quadradinhos
e 5 pontos. Logo, como a maior distância num quadrado é a diagonal,
o Teorema de Pitágoras nos garante que a distância desses dois pontos
é no máximo
√
2/2, como queríamos mostrar.
Exemplo 4.16. Na região delimitada por um triângulo equilátero de
lado 4 são marcados 10 pontos no interior deste. Prove que existe ao
menos um par destes pontos cuja distância entre eles não é maior que√
3.
Solução. Dividimos o triângulo equilátero de lado 4 em 16 triângulos
equiláteros menores de lado 1, conforme a Figura 4.3.
Agora pintamos os triângulos nas cores branco e cinza de maneira
que dois triângulos vizinhos, isto é, com um lado comum, são pintados
de cores diferentes. Se tivéssemos dois pontos no mesmo triângulo a
distância máxima possível entre eles seria 1 e o problema estaria resol-
vido. Se tivéssemos pontos em triângulos vizinhos, a maior distância
possível entre eles seria
√
3 e também isto resolveria o problema. Se
não tivéssemos nenhum dos casos anteriores, não seria difícil ver que
4.5 Miscelânea 153
A B
C
D
E
• • • •
•
•
•
••
•
Figura 4.3: O triângulo DBE é equilátero de lado 3
os 10 pontos deveriam estar situados sobre os 10 triângulos brancos,
contendo cada triângulo exatamente um ponto. Dividindo o triângulo
DBE em 4 triângulos congruentes de lado 3/2 pelo PCP temos que
pelo menos dois dos 6 pontos contidos em DBE estão num destes 4
triângulos, logo a distância entre eles não é maior que 3/2 <
√
3. Com
isto terminamos nossa prova.
4.5 Miscelânea
Os problemas que apresentamos a seguir usam o PCP combinado com
outras idéias que são muito empregadas nas suas soluções.
Exemplo 4.17. Em cada quadradinho de um tabuleiro 3×3 é colocado
um dos números: -1, 0 ou 1. Prove que entre todas as somas das
linhas, colunas e diagonais do tabuleiro há duas que são iguais. Por
exemplo, no tabuleiro abaixo a soma da segunda linha é 2, que coincide
com a soma da terceira coluna.
154 4 O Princípio da Casa dos Pombos
-1 -1 1
1 0 1
0 -1 0
Solução. Seja S = a1 + a2 + a3, onde cada a1, a2 e a3 podem tomar
valores: −1, 0 e 1. Então, temos 7 valores possíveis para S (casas),
que são: −3,−2,−1, 0, 1, 2, 3.
O tabuleiro 3×3 tem 3 linhas, 3 colunas e 2 diagonais, portanto, ao
somarmos os elementos de cada uma das linhas, colunas e diagonais,
obteremos 8 números (pombos). Como existem somente 7 valores
possíveis para estes números, pelo PCP pelo menos dois deles devem
ser iguais.
Exemplo 4.18. Dado qualquer conjunto A formado por 10 números
naturais escolhidos entre 1 e 99, inclusos, demonstre que existem dois
subconjuntos disjuntos e não vazios de A tal que a soma dos seus res-
pectivos elementos é igual.
Solução: É conhecido que A tem 210 − 1 = 1.023 subconjuntos não-
vazios diferentes. A soma dos elementos de cada um deles dá uma
quantidade menor do que 1.000, pois o subconjunto com no máximo
10 elementos de maior soma possível é o formado por 90, 91, . . . , 99,
e nesse caso 90+ 91+ · · ·+99 = 945. Agora consideramos os pombos
como sendo os 1.023 subconjuntos distintos de A e as casas como
sendo as somas possíveis dos elementos de cada um dos conjuntos.
Logo, como o número de conjuntos é maior que o número de somas
possíveis, devem existir dois conjuntos B e C de A, de tal modo que
a soma dos elementos de B é igual à soma dos elementos de C. Se B
4.5 Miscelânea 155
e C são disjuntos, acabou a prova. Se não, considere D = B −B ∩ C
e E = C − B ∩ C. Logo, os conjuntos D e E são disjuntos e a soma
dos seus elementos é a mesma, pois retiramos de ambos a mesma
quantidade.
Exemplo 4.19. Qual é o maior número de quadradinhos de um ta-
buleiro de 8 × 8 que podem ser pintados de preto, de forma tal que
qualquer arranjo de três quadradinhos, como mostra a Figura 4.4, te-
nha pelo menos um dos quadradinhos não pintado de preto?
Figura 4.4: Tridominós
Solução. Primeiramente, pintamos o tabuleiro de 8×8 como um tabu-
leiro de jogar xadrez, ou seja, 32 quadradinhos pintados de branco e
32 quadradinhos pintados de preto (ver Figura 4.5).
Figura 4.5: Tabuleiro de xadrez
156 4 O Princípio da Casa dos Pombos
Notemos que uma vez pintado o tabuleiro desta forma é satisfeita
a exigência do problema, pois nunca temos 2 quadradinhos vizinhos
(quadradinhos com um lado comum) pintados de preto.
Mostraremos agora que se pintamos 33 quadradinhos de preto en-
tão a condição exigida no problema falha. De fato, se dividimos o
tabuleiro em 16 quadrados de 2 × 2 (casas) e pintamos 33 quadra-
dinhos de preto (pombos); então, como 33 = 16 · 2 + 1, pela versão
geral do PCP um dos 16 quadrados de 2× 2 contém 3 quadradinhos
pintados de preto. Portanto, este último contém um arranjo como na
Figura 4.4 completamente pintado de preto.
Resumindo, o número máximo de quadradinhos que podemos pin-
tar de preto é 32.
Exemplo 4.20. Dados sete números reais arbitrários, demonstre que
existem dois deles, digamos x e y, tais que
0 ≤ x− y
1+ xy
≤ 1√
3
Solução. Primeiramente observamos que a expressão x−y
1+xy
nos faz pen-
sar na fórmula
tan(α− β) = tanα− tan β
1 + tanα tan β
. (4.2)
Sejam x1, x2, · · · , x7 os sete números selecionados arbitrariamente.
Lembramos que a função tangente é uma bijeção entre o intervalo
(−π
2
, π
2
) e os números reais R, logo para cada xi, 1 ≤ i ≤ 7, existe um
αi ∈ (−π2 , π2 ) tal que tan(αi) = xi. Dividimos o intervalo (−π2 , π2 ) em
seis subintervalos de comprimento π
6
, como mostra o desenho a seguir.
Pelo PCP dois dos números αi pertencem ao mesmo subintervalo.
Denotemos os mesmos por αi1 e αi2 e suponhamos, sem perda de
4.6 Exercícios 157
αi1 αi2
−π
2
π
2π
6
generalidade, que αi1 ≤ αi2 . Então vale
0 ≤ αi2 − αi1 ≤
π
6
.
Usando o fato de que a tangente é uma função crescente e a fórmula
(4.2) temos que
tan(0) ≤ tan(αi2 − αi1) ≤ tan(
π
6
).
Equivalentemente,
0 ≤ xi2 − xi1
1 + xi2xi1
≤ 1√
3
.
4.6 Exercícios
1. Seja C um conjunto formado por cinco pontos de coordenadas
inteiras no plano. Prove que o ponto médio de algum dos seg-
mentos com extremos em C tem também coordenadas inteiras.
2. O conjunto dos dígitos 1, 2, ..., 9 é dividido em três grupos.
Prove que o produto dos números de algum dos grupos deve ser
maior que 71.
3. Prove que se N é ímpar então para qualquer bijeção
p : IN → IN
158 4 O Princípio da Casa dos Pombos
do conjunto IN = {1, 2, . . . , N} o produto P (p) = (1−p(1))(2−
p(2)) · · · (N − p(N)) é necessariamente par.
(Dica: O produto de vários fatores é par se, e somente se, um dos
fatores é par.)
4. Dado um conjunto de 25 pontos no plano tais que entre quaisquer
3 deles existe um par com distância menor que 1. Prove que
existe um círculo de raio 1 que contém pelo menos 13 dos 25
pontos dados.
5. Prove que entre quaisquer 5 pontos escolhidos dentro de um
triângulo equilátero de lado 1 sempre existe um par deles cuja
distância não é maior que 0,5.
6. Marquemos todos os centros dos 64 quadradinhos de um ta-
buleiro de xadrez de 8× 8. É possível cortar o tabuleiro com 13
linhas retas que não passem pelos pontos marcados e de forma
tal que cada pedaço de recorte do tabuleiro tenha no máximo
um ponto marcado?
7. Prove que existem duas potências de 3 cuja diferença é divisível
por 1.997.
8. São escolhidos 6 números quaisquer pertencentes ao conjunto
A = {1, 2, 3, . . . , 10}.
Prove que existem dois desses seis números cuja soma é ímpar.
9. Seja x um número real arbitrário. Prove que entre os números
x, 2x, 3x, . . . , 101x
4.6 Exercícios 159
existe um tal que sua diferença com certo número inteiro é menor
0,011.
10. Mostre que entre nove números que não possuem divisores pri-
mos maiores que cinco, existem dois cujo produto é um qua-
drado.
11. Um disco fechado de raio um contém sete pontos, cujas distân-
cias entre quaisquer dois deles