Métodos de Demonstração2

Prévia do material em texto

Universidade Federal do Espírito Santo 
Centro de Ciências Exatas 
Departamento de Matemática 
 
Resolução de Problemas 
Florêncio Guimarães 
 
Métodos de Demonstração 2 
17/02/21 
 
Um número natural 𝑛 > 1 é um número primo quando seus únicos divisores são 1 e 𝑛. O Teorema 
Fundamental da Aritmética (TFA) estabelece que 
Todo número natural maior do que 1 é primo ou é um produto de números primos. Os 
fatores primos são únicos a menos da ordem. 
A prova da existência do produto de primos é feita por redução ao absurdo e utiliza o princípio do menor 
elemento. A essência da demonstração é a seguinte. Se houvesse um número não primo que não se fatora 
como um produto de primos, haveria o menor deles, e este, não sendo primo, seria um produto de dois 
números naturais, que por serem menores que ele, cada um se fatora em primos, consequentemente o 
próprio número se fatora num produto de primos, um absurdo. A prova da unicidade é mais exigente e 
utiliza um importante Lema: 
Se um número inteiro divide um produto e é primo com um dos fatores, então ele divide o outro fator. 
Um dos mais resultados em matemática é o seguinte. 
 
Teorema (Euclides). Existem infinitos números primos 
Demonstração. Por redução ao absurdo, suponha que existe apenas um número finito de números primos 
𝑝1, 𝑝2, 𝑝3, … , 𝑝𝑛 e considere o número 𝑁 = 𝑝1 ⋅ 𝑝2 ⋅ 𝑝3 ⋅ ⋯ ⋅ 𝑝𝑛 + 1. Todo número inteiro possui um fator 
primo. Logo algum primo 𝑝𝑘 divide 𝑁, com 1 ≤ 𝑘 ≤ 𝑛 . Como 𝑝𝑘 divide o produto 𝑝1 ⋅ 𝑝2 ⋅ 𝑝3 ⋅ ⋯ ⋅ 𝑝𝑛 
segue-se que 𝑝𝑘 divide 𝑁 − 𝑝1 ⋅ 𝑝2 ⋅ 𝑝3 ⋅ ⋯ ⋅ 𝑝𝑛 = 1. Ou seja, 𝑝𝑘 divide 1, um absurdo. 
Observação. 1) O fato de ter apenas um número finito de inteiros, a princípio não invalidaria o TFA, pois 
repetindo os primos na multiplicação produziria expoentes cada vez maiores, produzindo infinitos 
números. Porém, a construção de Euclides de fazer o produto de primos e somar 1 mostra que um número 
finito de primos não é tudo. 
2) A construção de Euclides dá um método direto de construir números primos. Também poderíamos 
fazer o produto de primos e diminuir 1 que funciona, veja. Os números 2 e 3 são primos, considere o 
número 2 × 3 + 1 = 7 e 2 × 3 − 1 = 5 são primos. Já o número 2 ⋅ 3 ⋅ 5 ⋅ 7 − 1 = 209 = 11 ⋅ 19 não é 
primo. Mas, com surpresa, ele guarda dois primos que são 11 e 19, melhor ainda, não? Façamos uma 
tabela para entendermos o aparecimento de números primos. 
Lista de primos Produto seguido de ±1 É primo? 
2, 3 2 ⋅ 3 − 1 = 5 Sim 
2, 3 2 ⋅ 3 + 1 = 7 Sim 
2, 5 2 ⋅ 5 − 1 = 9 = 32 
Não, mas apareceu o 3 que não foi 
usado na construção 
2, 5 2 ⋅ 5 + 1 = 11 Sim 
2, 7 2 ⋅ 7 − 1 = 13 Sim 
2, 7 2 ⋅ 7 + 1 = 15 = 3 ⋅ 5 
Não, mas apareceram o 3 e o 5 que 
não foram usados na construção 
3, 5 3 ⋅ 5 + 1 = 16 = 24 
Não, mas apareceu o 2 que não foi 
usado na construção 
2,2,2,2 24 + 1 = 17 Sim 
2,2,5 22 ⋅ 5 − 1 = 19 Sim 
2, 5 2 ⋅ 11 + 1 = 23 Sim 
2, 3, 5 2 ⋅ 3 ⋅ 5 − 1 = 29 Sim 
2, 3, 5 2 ⋅ 3 ⋅ 5 + 1 = 31 Sim 
2, 3, 5,7 2 ⋅ 3 ⋅ 5 ⋅ 7 − 1 = 209 = 11 ⋅ 19 
Não, mas apareceram o 11 e o 19 que 
não foram usados na construção 
2, 3, 5,7 2 ⋅ 3 ⋅ 5 ⋅ 7 + 1 = 211 Sim 
2, 3, 5,7,11 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 − 1 = 2309 Sim 
2, 3, 5,7,11 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 + 1 = 2311 Sim 
2, 3, 5,7,11,19 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 19 − 1 = 43889 Sim 
2, 3, 5,7,11,19 2 ⋅ 3 ⋅ 5 ⋅ 7 ⋅ 11 ⋅ 19 + 1 = 43891 Sim 
Demonstração direta. Dada qualquer quantidade finita de números primos podemos fazer o produto e 
somar (ou subtrair) 1. Este não é necessariamente primo, como mostra a tabela, mas é um produto de 
primos que estão fora da lista fora da lista de fatores do produto usados na construção. Logo sempre se 
obtém um número primo novo. Se no conjunto de primos sempre se consegue mais um, isto é que se 
chama de conjunto infinito. 
Para qualquer número primo 𝑝 a diferença 𝑝 − 1 é um número par, logo é um produto de primos 
𝑝 − 1 = 𝑝1 ⋅ 𝑝2 ⋅ 𝑝3 ⋅ ⋯ ⋅ 𝑝𝑛, todos menores do que 𝑝, alguns podendo ser iguais, por ex., 5 − 1 = 2
2. 
Portanto 
𝑝 = 𝑝1 ⋅ 𝑝2 ⋅ 𝑝3 ⋅ ⋯ ⋅ 𝑝𝑛 + 1 
 
No ensino médio, quando se ensina números primos, é possível utilizar essa construção para fazer 
aparecer outros primos a partir de uma quantidade fixada. Parece uma conta mais elementar. Ao mesmo 
tempo já mostrar a noção de quantidade infinita, sem usar o argumento de redução ao absurdo. 
 
Dois números primos cuja diferença é 2 são chamados de primos gêmeos. Por exemplo, os primos 
3 e 5; 5 e 7; 11 e 13, 17 e 19; 29 e 31, 2309 e 2311, 43889 e 43991 são gêmeos. A seguinte conjectura 
ainda está em aberto em matemática. 
Existem infinitos primos gêmeos? 
 
Indução e Indução Matemática 
Fazendo a soma dos cubos dos números naturais encontramos 
13 = 12 
13 + 23 = (1 + 2)2 
13 + 23 + 33 = (1 + 2 + 3)2 
13 + 23 + 33 + 43 = (1 + 2 + 3 + 4)2 
Nesse ponto somos levados a induzir (inferir, conjecturar) que 
13 + 23 + 33 + ⋯ + 𝑛3 = (1 + 2 + 3 + ⋯ + 𝑛)2 
para todo 𝑛 ≥ 1. Nesse momento, ainda não provamos a igualdade. Mesmo que façamos mais alguns 
exemplos não será suficiente. Servirá apenas para nos convencermos, cada vez mais, que a fórmula é essa 
mesma. Veja que Indução é diferente de Indução Matemática. Depois de induzir a fórmula, será preciso 
demonstrá-la para todo 𝑛 ≥ 1. Para isso fazemos uso do PIM. 
 
Prova usando o Princípio de Indução Matemática. Para todo 𝑛 ≥ 1, seja 𝑃𝑛 a igualdade dada por 
13 + 23 + 33 + ⋯ + 𝑛3 = (1 + 2 + 3 + ⋯ + 𝑛)2 
De início, 𝑃1 é verdadeira, pois 1
3 = 12. 
Supondo que 𝑃𝑛 é verdadeira vamos provar que 𝑃𝑛+1 também é verdadeira. Temos que provar que 
13 + 23 + 33 + ⋯ + 𝑛3 + (𝑛 + 1)3 = (1 + 2 + 3 + ⋯ + 𝑛 + (𝑛 + 1))2 
Com efeito, temos 
13 + 23 + 33 + ⋯ + 𝑛3 + (𝑛 + 1)3 = (1 + 2 + 3 + ⋯ + 𝑛)2 + (𝑛 + 1)3 
Sabe-se que 
1 + 2 + 3 + ⋯ + 𝑛 =
𝑛(𝑛 + 1)
2
 
logo 
13 + 23 + 33 + ⋯ + 𝑛3 + (𝑛 + 1)3 = [
𝑛(𝑛 + 1)
2
]
2
+ (𝑛 + 1)3 
 = (𝑛 + 1)2 (
𝑛2
4
+ 𝑛 + 1) =
(𝑛 + 1)2(𝑛2 + 4𝑛 + 4)
4
 
 =
(𝑛 + 1)2(𝑛 + 2)2
4
= [
(𝑛 + 1)(𝑛 + 2)
2
]
2
 
 = (1 + 2 + 3 + ⋯ + 𝑛 + (𝑛 + 1))2 
Logo, concluímos que 𝑃𝑛+1 também é verdadeira. 
Pelo Princípio de Indução Matemática, conclui-se que 𝑃𝑛 é verdadeira para todo 𝑛 ≥ 1. 
O processo de indução da igualdade é essencial numa fase anterior à demonstração, pois é preciso 
estabelecer a sentença que se quer provar por indução. Vejamos o seguinte exemplo. 
 
Exemplo. Vamos encontrar uma fórmula para a soma 
1
2!
+
2
3!
+
3
4!
+ ⋯ +
𝑛
(𝑛 + 1)!
 
Solução. Antes de tudo precisamos induzir uma fórmula para essa soma. Fazendo 𝑛 = 1 temos 
1
2!
=
1
2!
 
Calculando a soma para 𝑛 = 2 
1
2!
+
2
3!
=
3
3!
+
2
3!
=
5
3!
 
Calculando a soma para 𝑛 = 3 
1
2!
+
2
3!
+
3
4!
=
5
3!
+
3
4!
=
23
4!
 
Calculando a soma para 𝑛 = 4 
1
2!
+
2
3!
+
3
4!
+
4
5!
=
23
4!
+
4
5!
=
119
5!
 
Observe que os numeradores são as diferenças 1 = 2! − 1, 5 = 3! − 1, 23 = 4! − 1 e 119 = 5! − 1. A 
partir daí somos induzidos a pensar que o padrão para essa soma é 
1
2!
+
2
3!
+
3
4!
+ ⋯ +
𝑛
(𝑛 + 1)!
=
(𝑛 + 1)! − 1
(𝑛 + 1)!
= 1 −
1
(𝑛 + 1)!
 
Pronto, está feita a indução. Mas ela pode ser falsa. 
Prova usando o Princípio de Indução Matemática. Para todo 𝑛 ≥ 1, seja 𝑃𝑛 a igualdade dada por 
1
2!
+
2
3!
+
3
4!
+ ⋯ +
𝑛
(𝑛 + 1)!
= 1 −
1
(𝑛 + 1)!
 
De início, 𝑃1 é verdadeira, pois 
1
2!
= 1 −
1
(1+1)!
 . Supondo que 𝑃𝑛 é verdadeira vamos provar que 𝑃𝑛+1 
também é verdadeira. Temos que provar que 
1
2!
+
2
3!
+
3
4!
+ ⋯ +
𝑛
(𝑛 + 1)!
+
𝑛 + 1
(𝑛 + 1)!
= 1 −
1
(𝑛 + 2)!
 
Com efeito, temos 
1
2!
+
2
3!
+
3
4!
+ ⋯ +
𝑛
(𝑛 + 1)!
+
𝑛 + 1
(𝑛 + 1)!
= 1 −
1
(𝑛 + 1)!
+
𝑛 + 1
(𝑛 + 2)!
 
 = 1 −
(𝑛 + 2) −(𝑛 + 1)
(𝑛 + 2)!
= 1 −
1
(𝑛 + 2)!
 
Logo, concluímos que 𝑃𝑛+1 também é verdadeira. Pelo Princípio de Indução Matemática, conclui-se que 
𝑃𝑛 é verdadeira para todo 𝑛 ≥ 1. 
 
O Princípio da Boa Ordenação 
Se 𝑋 ⊂ ℕ é um subconjunto não vazio então X contém um menor elemento, isto é, existe 
um elemento 𝑛0 ∈ ℕ, tal que 𝑛0 ≤ 𝑛, para todo 𝑛 ≥ 1. 
Por exemplo, para verificar que 𝑛 = 5 é o menor elemento do conjunto 
𝑋 = {𝑛 ∈ ℕ; (𝑛 − 5)2(𝑛 − 7)2(𝑛2 − 9𝑛 − 10) ≥ 0} 
basta observar que 1, 2, 3, 4 ∉ 𝑋 e 5 ∈ 𝑋. Portanto, 𝑛 = 5 satisfaz a desigualdade 
(𝑛 − 5)2(𝑛 − 7)2(𝑛2 − 9𝑛 − 10) ≥ 0 
todo se 𝑛 ∈ ℕ satisfaz então 𝑛 ≥ 5. 
Esse método é muito eficiente para achar o menor elemento de um subconjunto de 
números naturais. Vá tomando números naturais, a partir de 1, sem pular nenhum e perguntando 
se está no complementar. Enquanto a resposta for sim continue. Quando chegar em um elemento 
que pertence ao conjunto pare, este é o menor elemento do conjunto. O menor elemento de 𝑋 é 
um número que pertence a 𝑋 tais que os naturais menores do que que ele não pertencem a 𝑋. 
 
Demonstração do Princípio da Boa Ordenação, a partir do PIM. Seja X ⊂ ℕ um subconjunto não 
vazio. Se 1 ∈ 𝑋, então 1 é o menor elemento de 𝑋. Suponha que 1 ∉ 𝑋 e seja 𝑌 o conjunto dos 
números naturais 𝑛 tais que 1, 2, 3, … , 𝑛 ∉ 𝑋. O conjunto 𝑌 não é necessariamente todo o 
complementar de 𝑋, ele é formado pelos números 𝑛 do complementar de 𝑋 tais que todos os 
naturais menores que 𝑛 também estão no complementar de 𝑋. Como 𝑋 é não vazio, para todo 
elemento 𝑥 ∈ 𝑋 tem-se 𝑥 ∉ 𝑌. Logo 1 ∈ 𝑌 e 𝑌 ≠ ℕ. Pelo Princípio de Indução Matemática existe 
𝑛 ∈ 𝑌, mas 𝑛 + 1 ∉ 𝑌. Logo é verdade que 1, 2, 3, … , 𝑛 ∉ 𝑋, mas é falso que 1, 2, 3, … , 𝑛, 𝑛 + 1 ∉
𝑋. Portanto 1, 2, 3, … , 𝑛 ∉ 𝑋 e 𝑛 + 1 ∈ 𝑋. Portanto 𝑛 + 1 é o menor elemento de 𝑋. 
 
Como usar o PBO no lugar do PIM 
Todo resultado provado pelo Princípio de Indução Matemática pode ser provado também usando 
o Princípio da Boa Ordenação. Veja como no exemplo seguinte. 
Exemplo. A soma dos 𝑛 primeiros números naturais é igual a 𝑛(𝑛 + 1)/2. Evidentemente, a 
igualdade vale para 𝑛 = 1. Por absurdo, suponha que existe um número natural 𝑛 > 1 tal que 
1 + 2 + 3 + ⋯ + 𝑛 ≠ 𝑛(𝑛 + 1)/2 
Pelo PBO, dentre os números naturais 𝑛 desse tipo, isto é, que não vale a igualdade para 𝑛, existe 
um menor número natural 𝑘. Então 
1 + 2 + 3 + ⋯ + 𝑘 ≠ 𝑘(𝑘 + 1)/2 
e vale a igualdade para todos os números naturais 𝑚 < 𝑘. Logo 𝑘 > 1, 𝑚 = 𝑘 − 1 ∈ ℕ e 
1 + 2 + 3 + ⋯ + 𝑚 = 𝑚(𝑚 + 1)/2 
 
Somando 𝑚 + 1 dos dois lados obtemos 
1 + 2 + 3 + ⋯ + 𝑚 + 𝑚 + 1 = 𝑚 + 1 + 𝑚(𝑚 + 1)/2 
1 + 2 + 3 + ⋯ + 𝑚 + 𝑚 + 1 = (𝑚 + 1)(𝑚 + 2)/2 
Levando em conta que 𝑘 = 𝑚 + 1, concluímos que 
1 + 2 + 3 + ⋯ + 𝑘 = 𝑘(𝑘 + 1)/2 
um absurdo, pois por hipótese, a igualdade é falsa para 𝑛 = 𝑘. Logo não existe um número 𝑛 para 
o qual a igualdade é falsa. Portanto a igualdade é verdadeira para todo 𝑛 ≥ 1. 
Com um raciocínio semelhante podemos transformar toda prova que usa o PIM numa 
prova pelo PBO. A recíproca também é verdadeira. 
O fato de um resultado ser verdadeiro para uma quantidade grande de vezes consecutivas 
não significa que é verdadeiro sempre. 
O polinômio de Euler. Seja 𝑝(𝑛) = 𝑛2 + 𝑛 + 41. Os números 𝑝(1) = 43, 𝑝(2) = 47, 𝑝(3) = 53, 
… , 𝑝(39) = 1601 são todos primos. Já 𝑝(40) = 412 e 𝑝(41) = 41 ⋅ 43 não são primos. 
Verifique!