Fundamentos da Aritmética

Prévia do material em texto

1 Os Nu´meros Naturais
Neste cap´ıtulo estudamos os nu´meros naturais. Alguns autores assumem o nu´mero zero como um
nu´mero natural, outros na˜o, dependendo do tipo de construc¸a˜o e de utilizac¸a˜o desse conjunto.
Neste livro, o zero pertence ao conjunto dos nu´meros naturais (que denotaremos por N). Assim,
N = {0, 1, 2, 3, . . .}. Mesmo assim, e´ conveniente introduzir um s´ımbolo para denotar o conjunto
dos nu´meros naturais diferentes de 0, e denotamos N∗ = {1, 2, 3, . . .}.
1.1 Induc¸a˜o Matema´tica
Na pro´xima sec¸a˜o vamos introduzir os nu´meros naturais de uma maneira rigorosa. No conjunto
N dos nu´meros naturais vamos ter duas operac¸o˜es ba´sicas, a adic¸a˜o e a multiplicac¸a˜o, e mais duas
operac¸o˜es, a subtrac¸a˜o e a divisa˜o, que sera˜o definidas a partir das duas operac¸o˜es ba´sicas. Muitas
propriedades importantes e interessantes sa˜o va´lidas. Outras na˜o sera˜o va´lidas, por exemplo, nem
sempre sera´ poss´ıvel subtrair ou dividir em N, o resultado poderia na˜o ser um nu´mero natural.
Em conjuntos nu´mericos mais amplos, por exemplo, no conjunto dos nu´meros racionais ou no
conjunto dos nu´meros reais, todas essas operac¸o˜es sera˜o poss´ıveis, com excec¸a˜o da divisa˜o por
0. No entanto, existe uma propriedade que, dentre todos esses conjuntos nume´ricos, vale apenas
para o conjunto dos nu´meros naturais. E´ o Princ´ıpio da Induc¸a˜o Matema´tica. Iniciaremos, por
razo˜es dida´ticas, por essa propriedade u´nica dos nu´meros naturais. Nesta sec¸a˜o ainda trataremos
da induc¸a˜o matema´tica de maneira informal, deixando para a pro´xima sec¸a˜o um tratamento mais
rigoroso, onde sera´ revelado o seu papel verdadeiramente fundamental na teoria.
Para que fique mais claro, preferimos nesta sec¸a˜o proceder da maneira mais informal poss´ıvel.
Antes mesmo de dizer o que e´ a induc¸a˜o matema´tica, daremos alguns exemplos. Esperamos que
assim as ideias fiquem mais claras.
Exemplo 1.1.1. Suponhamos que se queira obter uma expressa˜o para a soma
Sn = 1 + 3 + 5 + · · ·+ (2n− 1)
dos n primeiros nu´meros ı´mpares.
Iniciamos calculando os Sn para os primeiros valores de n e organizando uma tabela.
n Sn n Sn
1 1 6 1 + 3 + 5 + · · ·+ 11 = 36
2 1 + 3 = 4 7 1 + 3 + 5 + · · ·+ 13 = 49
3 1 + 3 + 5 = 9 8 1 + 3 + 5 + · · ·+ 15 = 64
4 1 + 3 + 5 + 7 = 16 9 1 + 3 + 5 + · · ·+ 17 = 81
5 1 + 3 + · · ·+ 9 = 25 10 1 + 3 + 5 + · · ·+ 19 = 100
Observando a tabela acima, chama a atenc¸a˜o o fato que os resultados obtidos sa˜o quadrados
perfeitos: 1 = 12, 4 = 22, 9 = 32, 16 = 42, . . .
Neste momento fazemos uma conjectura (uma conjectura e´ uma afirmac¸a˜o para a qual existe ja´
um forte ind´ıcio de que ela seja verdadeira, mas para a qual na˜o temos ainda uma demonstrac¸a˜o).
Conjectura: Para qualquer nu´mero natural n ≥ 1, vale Sn = 1 + 3 + 5 + · · ·+ (2n− 1) = n2.
Agora que ja´ temos nossa conjectura, passamos a uma fase totalmente diferente, que e´ a de
provar que nossa conjectura e´ verdadeira. Para isto usaremos a induc¸a˜o matema´tica. A demons-
trac¸a˜o de que uma determinada propriedade e´ verdadeira para qualquer nu´mero natural n, pode
ser feita em duas etapas independentes:
1
a) Verificar que a propriedade vale para o primeiro valor de n;
b) Verificar que se a propriedade valer para um certo nu´mero natural n, enta˜o a propriedade
vale tambe´m para o nu´mero seguinte n+ 1.
Voltemos a` proposic¸a˜o
1 + 3 + 5 + · · ·+ (2n− 1) = n2.
Note que o menor n para o qual nossa proposic¸a˜o faz sentido e´ n = 1. Vamos provar por induc¸a˜o
que ela vale para qualquer n ≥ 1. Como explicado acima, a demonstrac¸a˜o se da´ em duas etapas,
usualmente chamadas de base de induc¸a˜o e passagem de induc¸a˜o, respectivamente.
Base de induc¸a˜o: Verificar que vale para n = 1. No caso de n = 1, nossa proposic¸a˜o afirma
que 1 = 12, que e´ verdadeira.
Passagem de induc¸a˜o: Supondo que para um certo n a igualdade 1+3+5+ · · ·+(2n−1) = n2
se verifica, vamos provar que isto implica que para o nu´mero seguinte, n+1, a igualdade tambe´m
se verifica. Fazemos enta˜o a hipo´tese (usualmente chamada de hipo´tese de induc¸a˜o) de que para
um certo n vale
1 + 3 + 5 + · · ·+ (2n− 1) = n2.
Temos que mostrar que
1 + 3 + 5 + · · ·+ (2(n+ 1)− 1) = (n+ 1)2,
ou seja, temos que mostrar que
1 + 3 + 5 + · · ·+ (2n− 1) + (2n+ 1) = (n+ 1)2.
Aplicando a hipo´tese de induc¸a˜o e o produto nota´vel, segue que
1 + 3 + 5 + · · ·+ (2n− 1) + (2n+ 1) = n2 + (2n+ 1) = (n+ 1)2.
Esta´ justificado que se a propriedade valer para um certo n, enta˜o vale tambe´m para n+1. Assim,
fica conclu´ıdo o racioc´ınio, provando que a propriedade vale para qualquer n ≥ 1.
Exemplo 1.1.2. Suponhamos que nos perguntamos quem e´ maior, 2n ou n2? Calculando para os
n 2n n2
0 1 0
1 2 1
2 4 4
3 8 9
4 16 16
5 32 25
6 64 36
7 128 49
8 256 64
9 512 81
10 1024 100
primeiros valores de n, temos a tabela ao lado. Nossos ca´lculos
sugerem que ha´ um forte ind´ıcio de que, a partir de n = 5,
vamos ter sempre 2n > n2.
Consideremos agora a proposic¸a˜o P (n) : 2n > n2 e vamos
tentar provar por induc¸a˜o que P (n) e´ verdadeira para todo
n ≥ 5.
O primeiro passo sera´ mostrar que P (n) e´ va´lida para o
primeiro n em questa˜o, ou seja
Base de induc¸a˜o: P (5) e´ verdadeira. De fato, P (5) e´ 25 > 52,
que e´ verdadeira, pois 32 > 25.
Passagem de induc¸a˜o: Suponhamos que, para um certo n ≥ 5,
P (n) seja verdadeira. Enta˜o,
2n > n2 =⇒ 2 · 2n > 2n2 =⇒ 2n+1 > n2 + n2. (∗)
Acontece que, como n ≥ 5, enta˜o n2 > 2n + 1. De fato, se
n ≥ 5, multiplicando por n obtemos
n2 ≥ 5n = 2n+ 3n ≥ 2n+ 15,
ja´ que n ≥ 5 =⇒ 3n ≥ 15 (basta multiplicar por 3 > 0).
2
Como 15 > 1, somando 2n obtemos 2n + 15 ≥ 2n + 1. Logo, pela propriedade transitiva da
desigualdade n2 > 2n+ 1.
Somando n2 a ambos os lados da u´ltima desigualdade, obtemos n2+n2 > n2+2n+1 = (n+1)2.
Voltando para (∗) e usando a transitividade obtemos 2n+1 > (n+ 1)2. Segue que se 2n > n2 para
um certo n ≥ 5, enta˜o 2n+1 > (n + 1)2, concluindo a passagem de induc¸a˜o. Fica assim provado
que P (n) vale para todo nu´mero natural n ≥ 5.
Observac¸a˜o 1.1.3. Os exemplos acima mostram que a induc¸a˜o matema´tica na˜o e´ um me´todo para
descobrir fatos em Matema´tica, e sim uma te´cnica de demonstrar esses fatos. Nos exemplos vistos,
por outros me´todos fomos levados a fazer uma conjectura. A induc¸a˜o matema´tica nos possibilitou,
enta˜o, provar que nossa conjectura era verdadeira. Em outras palavras, se ja´ temos um forte ind´ıcio
de que uma certa propriedade possa ser verdadeira, podemos enta˜o usar a te´cnica da induc¸a˜o para
tentar prova´-la. Pode tambe´m acontecer que ja´ sabemos que uma certa propriedade e´ verdadeira
e ja´ temos ate´ uma demonstrac¸a˜o para ela, mas desejamos obter uma demonstrac¸a˜o diferente
(por exemplo, para explicar para uma pessoa que ainda na˜o tem os pre´-requisitos necessa´rios para
entender a demonstrac¸a˜o ja´ conhecida). Podemos, enta˜o, tentar obter uma demonstrac¸a˜o por
induc¸a˜o para nossa propriedade.
Exemplo 1.1.4. (O problema da moeda falsa.)
Sejam dadas M moedas de mesmo valor, uma das quais e´ falsa. Todas teˆm o mesmo peso,
exceto a falsa, que pesa menos. Dispomos de uma balanc¸a de dois pratos, mas de nenhum peso.
Consideremos o problema de encontrar a moeda falsa atrave´s da realizac¸a˜o de pesagens.
Vamos resolver esse problema no caso em que M = 2n. Queremos encontrar a moeda falsa
utilizando um me´todo sistema´tico, evitando a comparac¸a˜o duas a duas, que resultaria em 2n−1
pesagens, que e´ um nu´mero excessivamente grande.
Quando n = 0, temos M = 20 = 1, portanto, a u´nica moeda e´ a falsa. Assim, nem precisamos
pesar, ou seja, pesamos 0 vezes.
Quando n = 1, temos M = 21 = 2; colocando uma moeda em cada prato da balanc¸a, a de
menor peso sera´ a moeda falsa. Nesse caso, precisamos de uma pesagem.
Quando n = 2, temos M = 22 = 4; colocando duas moedas em cada prato da balanc¸a,o prato
com menor peso conte´m a moeda falsa. Agora pesamos as duas moedas retiradas do prato com
menor peso, colocando uma moeda em cada prato; a de menor peso sera´ a moeda falsa. Nesse
caso, precisamos de duas pesagens.
Quando n = 3, temos M = 23 = 8; colocando quatro moedas em cada prato da balanc¸a, o
prato com menor peso conte´m a moeda falsa. Agora pesamos as quatro moedas retiradas do prato
com menor peso, colocando duas moedas em cada prato; o prato com menor peso conte´m a moeda
falsa. Pesamos agora, as duas moedas retiradas do prato de menor peso, colocando uma moeda
em cada prato; a de menor peso e´ a moeda falsa. Nesse caso necessitamos de treˆs pesagens.
Neste ponto ja´ estamos inclinados a conjecturar.
Conjectura: Para todo n ∈ N e´ poss´ıvel encontrar a moeda falsa, dentre as 2n moedas, com n
pesagens.
Testamos mais uma vez. Quando n = 4 temos M = 24 = 16; colocando oito moedas em cada
prato da balanc¸a, o prato com menor peso conte´m a moeda falsa. Agora pesamos as oito moedas
retiradas do prato com menor peso, colocando quatro moedas em cada prato; o prato com menor
peso conte´m a moeda falsa. Pesamos, agora, as quatro moedas retiradas do prato com menor peso,
colocando duas moedas em cada prato; o prato com menor peso conte´m a moeda falsa. Pesamos
agora, as duas moedas retiradas do prato com menor peso, colocando uma moeda em cada prato;
a de menor peso e´ a moeda falsa. Nesse caso necessitamos de quatro pesagens.
Note que sempre que vamos resolver um caso acabamos utilizando o caso anterior; e´ esse
racioc´ınio que nos permite usar a induc¸a˜o.
Provamos a nossa conjectura por induc¸a˜o.
3
Base de induc¸a˜o: Ja´ foi feita acima, no caso n = 0.
Passagem de induc¸a˜o: Suponhamos que para um certo n ∈ N, se temos 2n moedas e´ poss´ıvel
encontrar a moeda falsa com n pesagens. Vamos mostrar que se temos 2n+1 moedas e´ poss´ıvel
encontrar a moeda falsa com n+ 1 pesagens.
De fato, se temos 2n+1 moedas, colocamos a metade delas (2n) em cada prato. O prato de
menor peso conte´m a moeda falsa. Pesamos, agora, as 2n moedas retiradas do prato de menor
peso. Pela hipo´tese de induc¸a˜o, sa˜o suficientes n pesagens para encontrar a moeda falsa. Logo,
junto com a pesagem inicial, utilizamos n+ 1 pesagens para determinar a moeda falsa.
Observac¸a˜o: Note que se temos 2n moedas, n na˜o e´ o nu´mero mı´nimo de pesagens necessa´rias
para obter a moeda falsa; por exemplo, para 8 moedas podemos proceder da seguinte forma,
primeiro separamos as moedas em dois grupos, o grupo 1 com 6 moedas e o grupo 2 com 2 moedas.
Tomamos as 6 moedas do grupo1 e colocamos 3 em cada prato da balanc¸a. Se os pesos de cada
prato forem iguais, enta˜o a moeda falsa esta´ no grupo 2 e com mais uma pesagem determinamos a
moeda falsa; neste caso necessitamos apenas de 2 pesagens (e na˜o 3). Se os pesos forem diferentes,
o prato com o menor peso conte´m a moeda falsa. Retiramos uma moeda do prato com o menor
peso e pesamos as outras duas colocando uma em cada prato. Se os pesos forem iguais, a moeda
falsa e´ a retirada do prato, se forem diferentes a moeda falsa e´ a de menos peso, em ambos os casos
necessitamos apenas 2 pesagens. O que demonstramos por induc¸a˜o foi que o nu´mero mı´nimo de
pesagens para encontrar a moeda falsa dentre 2n moedas e´ menor do que ou igual a n. Voltaremos
ao problema da moeda falsa mais adiante.
Observac¸a˜o 1.1.5. A induc¸a˜o matema´tica e´ um me´todo para demonstrar proposic¸o˜es a respeito
de um nu´mero natural n. Uma proposic¸a˜o do tipo “A soma dos aˆngulos internos de qualquer
triaˆngulo e´ 180o”na˜o pode ser provada por induc¸a˜o, pois na˜o e´ uma afirmac¸a˜o a respeito de um
nu´mero natural.
Exemplo 1.1.6. (Desigualdade de Bernoulli) Provar que (1+ x)n ≥ 1+ nx, ∀x ∈ [−1,+∞),
∀n ≥ 0. Em primeiro lugar, vamos nos convencer que apesar da Desigualdade de Bernoulli envolver
um nu´mero real x ∈ [−1,+∞), e´ uma afirmac¸a˜o a respeito de um nu´mero natural e, portanto,
tem sentido querer demonstra´-la por induc¸a˜o. Para cada n natural, consideremos a proposic¸a˜o
P (n) : (1 + x)n ≥ 1 + nx , ∀ x ∈ [−1,+∞).
Note que P (n) e´ uma propriedade do nu´mero natural n. Passemos a` demonstrac¸a˜o dessa pro-
priedade por induc¸a˜o.
Base de induc¸a˜o: P (0) e´ verdadeira. De fato, como (1 + x)0 = 1, P (0) afirma que 1 ≥ 1, que
e´ verdadeira.
Passagem de induc¸a˜o: Suponhamos que, para um certo n, P (n) seja verdadeira, ou seja, que
(1 + x)n ≥ 1 + nx , ∀x ∈ [−1,+∞). Podemos multiplicar ambos os lados dessa desigualdade por
1 + x, pois 1 + x > 0, ∀ x ∈ [−1,+∞). Obtemos
(1 + x)(1 + x)n ≥ (1 + x)(1 + nx) = 1 + x+ nx+ nx2 = 1 + (n+ 1)x+ nx2.
Como nx2 ≥ 0, segue que
(1 + x)n+1 ≥ 1 + (n+ 1)x , ∀x ∈ [−1,+∞).
A induc¸a˜o e´ usada na˜o so´ para demonstrar, mas tambe´m para definir. Temos o que se chama
de definic¸a˜o por induc¸a˜o ou, mas frequentemente, definic¸a˜o recursiva. E´ aquela definic¸a˜o em que
se define em duas etapas, inicialmente para o primeiro nu´mero e, num segundo momento, supondo
que o conceito ja´ esteja definido para um determinado n, define-se para o pro´ximo.
4
Exemplo 1.1.7. (Poteˆncia) Para x real, xn e´ o produto de x por si pro´prio n vezes,
xn = x · x · x · · · · x︸ ︷︷ ︸
n vezes
,
entendendo-se ainda que x1 = x e x0 = 1. Essa definic¸a˜o e´ pouco rigorosa, por causa dos treˆs
pontinhos. Uma maneira de torna´-la mais rigorosa e´ dar uma definic¸a˜o recursiva, dizendo que
(i) x0 = 1;
(ii) xn+1 = xn · x.
Exemplo 1.1.8. (Fatorial) O fatorial de um nu´mero natural e´ o produto de todos os naturais
de 1 ate´ n,
n! = 1 · 2 · 3 · · ·n,
definindo-se ainda 1! = 0! = 1. Neste caso tambe´m temos uma certa falta de rigor por causa
das reticeˆncias. Para melhorar isso, podemos dar uma definic¸a˜o recursiva para o fatorial de um
nu´mero natural, dizendo
(i) 0! = 1;
(ii) (n+ 1)! = n! · (n+ 1).
Observac¸a˜o 1.1.9. Vamos nos perguntar agora, qual e´ a propriedade que o conjunto dos nu´meros
naturais tem que permite que se tenha o me´todo da induc¸a˜o matema´tica. Suponhamos que se
queira provar uma certa proposic¸a˜o P (n) envolvendo um nu´mero natural n. Podemos considerar
o conjunto A de todos os nu´meros naturais para os quais P (n) e´ verdadeira,
A = {n ∈ N | P (n) e´ verdadeira}.
Enta˜o, provar que P (n) e´ verdadeira para todo n ∈ N equivale a provar que A = N. Ora, a base de
induc¸a˜o que consiste em verificar que P (0) e´ verdadeira, nada mais e´ do que verificar que 0 ∈ A.
E a passagem de induc¸a˜o P (n) =⇒ P (n+1) equivale a mostrar que se o conjunto A conte´m um
elemento n enta˜o A tambe´m conte´m o nu´mero seguinte n+ 1 (o sucessor de n),
n ∈ A =⇒ n+ 1 ∈ A.
Portanto, a propriedade que o conjunto dos nu´meros naturais possui, que faz com que o me´todo
de induc¸a˜o matema´tica funcione, e que os outros conjuntos nume´ricos usuais na˜o possuem e´ a
seguinte.
Propriedade. Seja A ⊆ N um subconjunto de N. Se valem
(i) 0 ∈ A;
(ii) n ∈ A =⇒ n+ 1 ∈ A,
enta˜o A = N.
Podemos nos convencer facilmente que se (i) e (ii) sa˜o va´lidas enta˜o A = N. De fato, por (i)
0 ∈ A, logo, por (ii) 1 = 0+1 ∈ A. Agora 1 ∈ A logo, por (ii) 2 = 1+1 ∈ A. Assim, 2 ∈ A logo,
por (ii) 3 = 2 + 1 ∈ A. E assim por diante.
Na pro´xima sec¸a˜o, veremos que propriedade acima tera´ uma importaˆncia fundamental.
5
1.2 Os Axiomas de Peano
A Matema´tica e´ uma cieˆncia que estuda principalmente a estrutura das coisas, se preocupando
menos com a natureza nos objetos. Por isso, em Matema´tica frequentemente adotamos o me´todo
axioma´tico. No caso presente, dos nu´meros naturais, isto significa que na˜o vamos nos preocupar
com questo˜es como o que e´ um nu´mero natural, o que e´ o 0, o que e´ o 1, o que e´ a soma de
dois nu´meros naturais, etc. Em vez disso, vamos apresentar uma lista de axiomas, que sa˜o as
propriedades fundamentais que caracterizam a estrutura do conjunto dos nu´meros naturais e o
papel que o nu´mero 0, por exemplo,desempenha nessa estrutura.
Assim, o conjunto N = {0, 1, 2, 3, . . .} dos nu´meros naturais e´ caracterizado por algumas noc¸o˜es
primitivas, que na˜o sa˜o definidas, mas teˆm suas propriedades descritas por uma lista de axiomas,
conhecidos como Axiomas de Peano (Giuseppe Peano, 1858–1932, matema´tico italiano).
Sa˜o treˆs os conceitos primitivos: nu´mero natural, zero e sucessor. Esses treˆs conceitos primi-
tivos sa˜o caracterizados por cinco axiomas:
1. 0 e´ um nu´mero natural.
2. Todo nu´mero natural n tem um u´nico sucessor s(n) ∈ N.
3. 0 na˜o e´ sucessor de nenhum nu´mero natural.
4. Se dois nu´meros naturais n e m teˆm o mesmo sucessor s(n) = s(m), enta˜o n = m.
5. Princ´ıpio da Induc¸a˜o Matema´tica. Se A ⊆ N e´ um subconjunto dos naturais tal que
0 ∈ A
n ∈ A =⇒ s(n) ∈ A
enta˜o A = N.
Uma primeira consequeˆncia desses axiomas e´ que 0 e´ o U´NICO nu´mero natural que na˜o e´
sucessor de nenhum nu´mero natural. De fato, se existe u ∈ N∗ tal que u na˜o e´ sucessor de nenhum
nu´mero natural, ou seja u 6= s(n), ∀n ∈ N, enta˜o tomamos A = N − {u} e temos que 0 ∈ A
e n ∈ A =⇒ s(n) ∈ A, pela definic¸a˜o de A. Pelo Princ´ıpio da Induc¸a˜o A = N, o que e´ uma
contradic¸a˜o.
Usando essa primeira consequeˆncia podemos reformular os quatro primeiros axiomas acima em
uma linguagem mais formal dizendo que existe uma func¸a˜o s : N→ N e existe um elemento 0 ∈ N
tais que
1’. A func¸a˜o s e´ injetora;
2’. A imagem da func¸a˜o s e´ o conjunto s(N) = N \ {0}.
Proposic¸a˜o 1.2.1. (∀n ∈ N)(s(n) 6= n).
Demonstrac¸a˜o. Seja A = {n ∈ N | s(n) 6= n}. Basta mostrar que A = N. Para isto, vamos usar o
Princ´ıpio da Induc¸a˜o Matema´tica (Axioma 5).
Segue do Axioma 2’ que s(0) ∈ N \ {0} e, portanto, s(0) 6= 0. Logo, 0 ∈ A
Suponhamos que um certo nu´mero natural n ∈ N pertenc¸a a A. Enta˜o, s(n) 6= n. Como a
func¸a˜o s e´ injetora, conclu´ımos que s(s(n)) 6= s(n). Enta˜o, pela definic¸a˜o do conjunto A, temos
que s(n) ∈ A.
Do Princ´ıpio da Induc¸a˜o Matema´tica, segue que A = N.
6
1.3 A adic¸a˜o em N
Definic¸a˜o 1.3.1. A soma de dois nu´meros naturais e´ definida recursivamente por
(i) m+ 0 = m, ∀m ∈ N;
(ii) m+ s(n) = s(m+ n), ∀m,n ∈ N.
Observac¸a˜o 1.3.2. Note que, pela definic¸a˜o de soma,
s(m) = s(m+ 0) = m+ s(0). (1)
Definimos o nu´mero natural 1 como
1 = s(0).
Enta˜o, a igualdade (1) acima pode ser reescrita como
s(m) = m+ 1. (2)
Proposic¸a˜o 1.3.3. (Propriedade associativa) ∀ a, b, c ∈ N, (a+ b) + c = a+ (b+ c).
Demonstrac¸a˜o. A demonstrac¸a˜o e´ por induc¸a˜o. Vamos provar por induc¸a˜o a seguinte propriedade
do nu´mero natural c
P (c) : ∀ a, b ∈ N, (a+ b) + c = a+ (b+ c).
Base de induc¸a˜o: Verificamos que vale para c = 0, ou seja, que (a + b) + 0 = a + (b + 0). De
fato,
(a+ b) + 0 = a+ b = a+ (b+ 0).
Passagem de induc¸a˜o: Suponhamos que para um certo c ∈ N vale
(a+ b) + c = a+ (b+ c), ∀ a, b ∈ N. (3)
Enta˜o,
(a+ b) + s(c) = s((a+ b) + c) = s(a+ (b+ c)) = a+ s(b+ c) = a+ (b+ s(c)).
Logo, se (3) valer para um certo c ∈ N, enta˜o vale tambe´m para s(c). Aplicando o Princ´ıpio de
Induc¸a˜o, segue que (3) vale para qualquer c ∈ N, concluindo a demonstrac¸a˜o.
Proposic¸a˜o 1.3.4. Valem as seguintes igualdades:
(i) n+ 1 = s(n) = 1 + n, ∀n ∈ N;
(ii) (Elemento neutro) 0 e´ o elemento neutro da adic¸a˜o, ou seja,
n+ 0 = 0 + n = n, ∀n ∈ N.
Demonstrac¸a˜o. Conforme foi observado em (2), acima, temos n+ 1 = s(n), ∀n ∈ N. A igualdade
1+n = s(n) vai ser mostrada por induc¸a˜o (note que ainda na˜o provamos a propriedade comutativa,
ela vai ser provada na pro´xima proposic¸a˜o).
Base de induc¸a˜o: Verificar que 1 + 0 = s(0). De fato, 1 + 0 = 1 pela definic¸a˜o de soma, logo
1 + 0 = 1 = s(0).
Passagem de induc¸a˜o: Suponhamos que 1+ n = s(n) vale para um certo n. Enta˜o, 1 + s(n) =
1+(n+1), pela parte ja´ mostrada. Usando a propriedade associativa, obtemos 1+s(n) = (1+n)+1.
Enta˜o, pela hipo´tese de induc¸a˜o, temos que 1 + s(n) = s(n) + 1. E, novamente pela parte ja´
7
mostrada, segue que 1 + s(n) = s(s(n)), ou seja, se a propriedade valer para um certo n ∈ N,
enta˜o vale tambe´m para s(n), terminando a demonstrac¸a˜o.
A segunda igualdade tem uma parte que decorre diretamente da definic¸a˜o de soma, n+0 = n.
A demonstrac¸a˜o de que 0 + n = n tambe´m e´ feita por induc¸a˜o.
Base de induc¸a˜o: Verificar que 0 + 0 = 0. Segue diretamente da definic¸a˜o.
Passagem de induc¸a˜o: Suponhamos que 0 + n = n vale para um certo n. Enta˜o, 0 + s(n) =
0+ (n+1) = (0+n) + 1, pela propriedade associativa. Aplicando a hipo´tese de induc¸a˜o, obtemos
0 + s(n) = n + 1 = s(n), provando que se valer para um certo n, enta˜o a igualdade vale tambe´m
para s(n).
Proposic¸a˜o 1.3.5. (Propriedade comutativa) ∀ a, b ∈ N, a+ b = b+ a.
Demonstrac¸a˜o. A demonstrac¸a˜o e´ por induc¸a˜o. Vamos mostrar que para qualquer a ∈ N vale a
seguinte afirmac¸a˜o a respeito de a
P (a) : ∀ b ∈ N, a+ b = b+ a.
Base de induc¸a˜o: Verificamos que 0 + b = b+ 0, ∀ b ∈ N.
De fato, b + 0 = b = 0 + b, pela propriedade de que 0 e´ o elemento neutro da soma (proposic¸a˜o
anterior).
Passagem de induc¸a˜o: Suponhamos que para um certo a ∈ N vale
a+ b = b+ a, ∀ b ∈ N. (4)
Enta˜o, s(a)+ b = (1+ a)+ b = 1+ (a+ b) = 1+ (b+ a) = (1+ b)+ a = (b+1)+ a = b+(1+ a) =
b + s(a), ∀ b ∈ N, ou seja, se a propriedade (4) valer para um certo a ∈ N, enta˜o vale tambe´m
para s(a).
Proposic¸a˜o 1.3.6. (Lei do cancelamento para a adic¸a˜o)
∀ a, b, c ∈ N, a+ b = a+ c =⇒ b = c. (5)
Demonstrac¸a˜o. A demonstrac¸a˜o e´ por induc¸a˜o em a.
Base de induc¸a˜o: (5) vale para a = 0.
E´ imediato.
Passagem de induc¸a˜o: Suponhamos que (5) vale para um certo a ∈ N. Vamos verificar que
vale tambe´m para s(a). De fato,
s(a) + b = s(a) + c =⇒ s(a+ b) = s(a+ c) =⇒ a+ b = a+ c =⇒ b = c.
Observac¸a˜o 1.3.7. A Adic¸a˜o e´ uma operac¸a˜o bina´ria, ou seja, tem sentido a soma de dois nu´meros
naturais, apenas. Quando escrevemos uma expressa˜o do tipo a + b + c, na˜o estamos somando os
treˆs nu´meros de uma so´ vez, pois isso na˜o tem sentido; podemos somar (a+b)+c ou a+(b+c). No
entanto, pela propriedade associativa da adic¸a˜o, somando de qualquer uma dessas maneiras obte´m-
se o mesmo resultado. Portanto, na˜o e´ necessa´rio indicarmos em que ordem estamos considerando
a soma, e podemos escrever sem os pareˆnteses a + b + c, ficando assim com uma escrita menos
carregada.
8
1.4 Multiplicac¸a˜o em N
Definic¸a˜o 1.4.1. O produto de dois nu´meros naturais e´ definido recursivamente por
(i) a · 0 = 0, ∀ a ∈ N;
(ii) a · s(b) = a · b+ a, ∀ a, b ∈ N.
Observac¸a˜o 1.4.2. Em primeiro lugar, notemos que, a partir da definic¸a˜o de produto, para
qualquer n ∈ N temos
n · 1 = n · s(0) = n · 0 + n = 0 + n = n. (6)
Proposic¸a˜o 1.4.3. (Absorc¸a˜o). Vale a propriedade
0 · b = 0, ∀ b ∈ N. (7)
Demonstrac¸a˜o. Base de Induc¸a˜o: A condic¸a˜o (7) vale para b = 0.
E´ imediato.
Passagem de Induc¸a˜o: Suponhamos que (7) vale para um certo b ∈ N. Enta˜o,
0 · s(b) = 0 · b+ 0 = 0 · b = 0.
Segue que se (7) vale para um certo b, enta˜o vale tambe´m para s(b). Logo, (7) vale para todo
b ∈ N.
Proposic¸a˜o 1.4.4. (Elemento neutro do produto). n · 1 = 1 · n = n, ∀n ∈ N.
Demonstrac¸a˜o. Conforme foi observado em (6) acima, temos n · 1 = n, ∀n ∈ N. A igualdade
1 · n = n, ∀n ∈ N vai ser provada por induc¸a˜o.
Base de Induc¸a˜o: 1 · 0 = 0 segue da definic¸a˜o de produto.
Passagem de Induc¸a˜o: Suponhamos que para um certo nu´mero natural n vale 1 ·n = n. Enta˜o,
1 · s(n) = 1 · n+ 1 = n+ 1 = s(n).
Lema 1.4.5. (a+ 1)b = ab+ b, ∀ a, b ∈ N.
Demonstrac¸a˜o. Vamos provar por induc¸a˜o a seguinte propriedade do nu´mero natural b
P (b) : (a+ 1)b = ab+ b, ∀ a ∈ N.
P (0) e´ verdadeira pela definic¸a˜o da multiplicac¸a˜o. Supondo que P (b) seja verdadeira para um certo
b, vamos mostrar que P (s(b)) tambe´m e´ verdadeira. De fato, usando a definic¸a˜o de multiplicac¸a˜o
e a hipo´tese deinduc¸a˜o, temos
(a+ 1)s(b) = (a+ 1)b+ a+ 1 = ab+ b+ a+ 1.
Usando as propriedades comutativa e associativa da adic¸a˜o e novamente a definic¸a˜o da multi-
plicac¸a˜o, segue que
(a+ 1)s(b) = (ab+ a) + (b+ 1) = a · s(b) + s(b).
O racioc´ınio acima mostra que se P (b) for verdadeira para algum b ∈ N, enta˜o P (s(b)) tambe´m e´
verdadeira. Logo, P (b) e´ verdadeira para qualquer b ∈ N.
9
Proposic¸a˜o 1.4.6. (Comutatividade). ab = ba, ∀ a, b ∈ N.
Demonstrac¸a˜o. Vamos provar por induc¸a˜o em a. Consideremos a afirmac¸a˜o
ab = ba, ∀ b ∈ N. (8)
Base de induc¸a˜o: A condic¸a˜o (8) vale para a = 0. De fato, pela definic¸a˜o de produto, temos
b · 0 = 0. Por outro lado, por (7), temos 0 · b = 0. Logo, 0 · b = b · 0.
Passagem de induc¸a˜o: Suponhamos que a condic¸a˜o (8) vale para um certo a ∈ N. Enta˜o,
s(a)b = (a+ 1)b = ab+ 1 · b = ba+ b = b · s(a), ∀ b ∈ N.
Logo, se a condic¸a˜o (8) vale para um certo a ∈ N, enta˜o ela tambe´m, vale para s(a). Logo, a
condic¸a˜o (8) vale para qualquer a ∈ N.
Proposic¸a˜o 1.4.7. (Distributividade). (i) (a+ b)c = ac+ bc, ∀ a, b, c ∈ N.
(ii) a(b+ c) = ab+ ac, ∀ a, b, c ∈ N.
Demonstrac¸a˜o. Vamos provar a afirmac¸a˜o (i) por induc¸a˜o em c. Consideremos a afirmac¸a˜o
(a+ b)c = ac+ bc, ∀ a, b ∈ N. (9)
Base de induc¸a˜o: (9) vale para c = 0. De fato,
(a+ b) · 0 = 0 = 0 + 0 = a · 0 + b · 0.
Passagem de induc¸a˜o: Suponhamos que (9) vale para um certo c ∈ N. Vamos mostrar que ela
vale tambe´m para s(c). Usando a definic¸a˜o de produto e a hipo´tese de induc¸a˜o, temos
(a+ b)s(c) = (a+ b)c+ a+ b = ac+ bc+ a+ b = (ac+ a) + (bc+ b) = as(c) + bs(c).
Portanto, se (9) vale para um certo c ∈ N, enta˜o ela tambe´m vale para s(c). Logo, (9) vale para
todo c ∈ N.
A propriedade (ii) segue da propriedade (i) e da comutatividade da multiplicac¸a˜o.
Proposic¸a˜o 1.4.8. (Associatividade). (a · b) · c = a · (b · c), ∀ a, b, c ∈ N.
Demonstrac¸a˜o. A demonstrac¸a˜o e´ por induc¸a˜o em c. Consideremos a afirmac¸a˜o
(a · b) · c = a · (b · c), ∀ a, b ∈ N. (10)
Base de induc¸a˜o: (10) vale para c = 0. De fato,
(a · b) · 0 = 0 = a · 0 = a · (b · 0).
Passagem de induc¸a˜o: Suponhamos que (10) vale para um certo c. Enta˜o, pela definic¸a˜o
recursiva da multiplicac¸a˜o e pela hipo´tese de induc¸a˜o,
(a · b) · s(c) = (a · b) · c+ a · b = a · (b · c) + a · b.
Utilizando a distributividade, obtemos
(a · b) · s(c) = a · (b · c+ b).
Utilizando novamente a definic¸a˜o do produto, segue que
(a · b) · s(c) = a · (b · s(c)).
Portanto, se (10) vale para um certo c, enta˜o vale tambe´m para s(c). Logo, (10) vale para qualquer
c ∈ N.
10
Proposic¸a˜o 1.4.9. (Integridade). ∀ a, b ∈ N, a · b = 0 =⇒ a = 0 ou b = 0.
Demonstrac¸a˜o. Por contraposic¸a˜o basta mostrar que a 6= 0 e b 6= 0 =⇒ ab 6= 0. Suponhamos que
a 6= 0 e b 6= 0.
Como a 6= 0, enta˜o existe u ∈ N tal que a = s(u) = u+ 1. Da mesma forma b 6= 0 implica que
existe v ∈ N tal que b = s(v) = v + 1. Enta˜o,
ab = (u+ 1)(v + 1) = (u+ 1)v + (u+ 1) = uv + u+ v + 1.
Portanto, ab e´ o sucessor do elemento uv + u + v. Conclu´ımos que ab 6= 0, pois 0 na˜o e´ sucessor
de nenhum outro natural.
Proposic¸a˜o 1.4.10. (Lei do cancelamento). ∀ a, b, c ∈ N, a · c = b · c e c 6= 0 =⇒ a = b.
Demonstrac¸a˜o. Vamos provar por induc¸a˜o a sequinte proposic¸a˜o
P (a) : ∀b, ∀c 6= 0, a · c = b · c =⇒ a = b.
Base de Induc¸a˜o: P (0) e´ verdadeira.
De fato, se a = 0, enta˜o a · c = 0, de modo que P (0) e´ a afirmac¸a˜o ∀b, ∀c 6= 0, b · c = 0 =⇒
b = 0 = a, que e´ verdadeira pela propriedade de integridade.
Passagem de Induc¸a˜o: Suponhamos P (a) verdadeira para um certo a. Vamos mostrar que
P (a + 1) tambe´m e´ verdadeira. Para isso, suponhamos que (a + 1) · c = b · c e c 6= 0. Como
a + 1 6= 0 e c 6= 0, pela propriedade de integridade, temos que (a + 1) · c 6= 0, logo b · c 6= 0 e,
portanto, b 6= 0. Segue que existe u ∈ N tal que b = u+ 1. Portanto,
(a+ 1) · c = (u+ 1) · c =⇒ ac+ c = uc+ c =⇒ ac = uc.
Aplicando a hipo´tese de induc¸a˜o de que P (a) e´ verdadeira, temos que a = u. Logo, a+1 = u+1,
ou seja, a+ 1 = b. Portanto, P (a+ 1) tambe´m e´ verdadeira.
Obs. Uma nova demonstrac¸a˜o da Lei do Cancelamento sera´ vista na pro´xima sec¸a˜o, como
aplicac¸a˜o da Tricotomia.
Proposic¸a˜o 1.4.11. Valem as implicac¸o˜es:
(i) ∀ a, b ∈ N, a+ b = 0 =⇒ a = b = 0;
(ii) ∀ a, b ∈ N, a · b = 1 =⇒ a = b = 1.
Demonstrac¸a˜o. Para provar a propriedade (i) acima, suponhamos que a, b ∈ N, com a + b = 0.
Existem duas possibilidades, ou o nu´mero natural b e´ 0 (b = 0), ou b e´ o sucessor de algum outro
nu´mero natural (∃ d ∈ N tal que b = s(d)). Se valesse essa segunda alternativa, b = s(d), enta˜o,
pela definic¸a˜o de soma, ter´ıamos a + b = a + s(d) = s(a + d), contrariando a hipo´tese de que
a + b = 0, pois 0 na˜o e´ o sucessor de nenhum nu´mero natural. Portanto, o que vale e´ que b = 0.
Enta˜o, como a+ b = 0, temos que a = a+ 0 = a+ b = 0.
Agora vamos provar a propriedade (ii). Suponhamos que a, b ∈ N com a · b = 1. Pela
propriedade de absorc¸a˜o, a 6= 0 e b 6= 0, pois se um dos dois nu´meros se anulasse, o produto seria
0. Enta˜o, existem u, v ∈ N tais que a = s(u) e b = s(v), pois 0 e´ o u´nico natural que na˜o sucessor
de nenhum outro. Enta˜o,
1 = ab = a · s(v) = av + a = av + s(u) = (av + u) + 1.
Segue que 0 + 1 = (av + u) + 1. Aplicando a Lei do Cancelamento, conclu´ımos que av + u = 0.
Enta˜o, pela parte (i), ja´ demonstrada, conclu´ımos que av = 0 e u = 0. Mas de u = 0, segue que
a = s(u) = s(0) = 1, que e´ uma das afirmac¸o˜es que queremos mostrar. A outra agora e´ fa´cil,
b = 1 · b = a · b = 1.
11
1.5 Ordem em N
Definic¸a˜o 1.5.1. Dizemos que o nu´mero natural a e´ menor ou igual a b e anotamos por a ≤ b se
existe c ∈ N tal que a + c = b. Dizemos que a e´ menor do que b e anotamos por a < b se existe
c ∈ N, com c 6= 0 e tal que a+ c = b. Em outras palavras a < b se a ≤ b e a 6= b. Dizemos que b e´
maior ou igual a a e anotamos b ≥ a se a ≤ b. Analogamente, b > a se a < b.
Segue diretamente da definic¸a˜o que 0 ≤ n, ∀n ∈ N e que ∀ a, b ∈ N, a ≤ a+ b.
Proposic¸a˜o 1.5.2. A relac¸a˜o de ordem tem as seguintes propriedades:
(i) Reflexiva: a ≤ a, ∀ a ∈ N;
(ii) Anti-sime´trica: a ≤ b e b ≤ a =⇒ a = b.
(iii) Transitiva: a ≤ b e b ≤ c =⇒ a ≤ c.
Demonstrac¸a˜o. Reflexiva: a+ 0 = a =⇒ a ≤ a, ∀ a ∈ N.
Anti-sime´trica: Suponhamos que a ≤ b e b ≤ a. Enta˜o, existem c, d ∈ N tais que a + c = b e
b+ d = a. Segue que a+ (c+ d) = (a+ c) + d = b+ d = a, isto e´, a+ (c+ d) = a+ 0. Pela Lei do
Cancelamento, temos c+ d = 0. Enta˜o, pela Proposic¸a˜o 1.4.11, temos que c = d = 0. Logo, a = b.
Transitiva: Suponhamos que a ≤ b e b ≤ c. Enta˜o, existem s, t ∈ N tais que a+ s = b e b+ t = c.
Segue que a+ (s+ t) = (a+ s) + t = b+ t = c. Enta˜o, pela definic¸a˜o da desigualdade, a ≤ c.
Proposic¸a˜o 1.5.3. (Compatibilidade da ordem com as operac¸o˜es).
(i) ∀ a, b, c ∈ N, a < b =⇒ a+ c < b+ c.
(i)′ ∀ a, b, c ∈ N, a ≤ b =⇒ a+ c ≤ b+ c.
(ii) ∀ a, b ∈ N, ∀ c ∈ N∗, a < b =⇒ a · c < b · c.
(Propriedade cancelativa) Valem as rec´ıprocas das afirmac¸o˜es (i) e (ii) acima,
(iii) ∀ a, b, c ∈ N, a+ c < b+ c =⇒ a < b.
(iv) ∀ a, b ∈ N, ∀ c ∈ N∗, a · c < b · c =⇒ a < b.
Demonstrac¸a˜o. Para provar a propriedade (i), suponhamos que a < b. Enta˜o, pela Definic¸a˜o 1.5.1,
existe u ∈ N∗ tal que a+ u = b. Segue que a+ u+ c = b+ c e, usando as propriedades comutativa
e associativa, (a + c) + u = b + c. Novamente, pela Definic¸a˜o 1.5.1, temos que a + c < b + c.
A demonstrac¸a˜o da propriedade (i)′ e´ ana´loga, substituindo a condic¸a˜o u ∈ N por u ∈ N∗. A
demonstrac¸a˜o da propriedade (ii) tambe´m e´ ana´loga e na˜o faremos aqui.
Para provar (iii), suponhamos que a+ c < b+ c. Enta˜o, ∃u ∈ N∗ tal que a+ c+ u = b+ c, ou
seja, (a+ u) + c = b+ c. Pela lei do cancelamento para a adic¸a˜o, segue que a+ u = b com u ∈ N∗
e, portanto, a < b.
O item (iv) vai ser demonstrado depois da pro´xima proposic¸a˜o.
Proposic¸a˜o 1.5.4. (Tricotomia).Se a, b ∈ N, vale uma e apenas uma das alternativas: a < b,
b < a ou a = b.
Demonstrac¸a˜o. Primeiro vamos mostrar que na˜o podem valer ao mesmo tempo duas das alter-
nativas. Por exemplo, na˜o podem valer ambas a < b e b < a. De fato, supondo que valem
a < b e b < a, enta˜o existem u, v ∈ N∗ tais que a + u = b e b + v = a. Conclu´ımos que
a+ 0 = a = b+ v = a+ (u+ v). Pela propriedade cancelativa, segue que u+ v = 0. Aplicando a
parte (i) da Proposic¸a˜o 1.4.11, temos que u = v = 0, mas isto e´ uma contradic¸a˜o pois u, v ∈ N∗.
12
Portanto, as duas desigualdades na˜o podem ocorrer simultaneamente. Da mesma forma, mostra-se
que a igualdade a = b na˜o pode ocorrer simultaneamente com nenhuma das desigualdades.
Agora precisamos mostrar que sempre ocorre pelo menos uma das treˆs alternativas. Basta
mostrar que dados dois quaisquer a, b ∈ N, vale pelo menos uma das duas a ≤ b ou b ≤ a. Vamos
adotar a seguinte estrate´gia de demonstrac¸a˜o. Fixamos um a ∈ N arbitrariamente e consideramos,
para qualquer b ∈ N, a propriedade
P (b) : a ≤ b ou b ≤ a.
Provamos que vale P (b), ∀ b ∈ N, por induc¸a˜o.
Base de Induc¸a˜o: P (0) e´ verdadeira.
De fato, como 0 ≤ a, enta˜o vale P (0).
Passagem de Induc¸a˜o: Se P (b) e´ verdadeira para um certo b, enta˜o P (s(b)) tambe´m e´ ver-
dadeira.
De fato, suponhamos que, para um certo b ∈ N, P (b) seja verdadeira. Enta˜o vale que a ≤ b
ou b ≤ a. Precisamos mostrar que a ≤ s(b) ou s(b) ≤ a.
Se a ≤ b, enta˜o ∃u ∈ N tal que a+ u = b. Logo, a+ u+ 1 = b+ 1 = s(b) e, portanto, a ≤ s(b)
e temos que a ≤ s(b) ou s(b) ≤ a.
Se b ≤ a, temos duas possibilidades, ou b = a ou b < a. Se b = a enta˜o s(b) = b + 1 = a + 1,
logo s(b) > a. Se b < a, enta˜o ∃ v ∈ N∗ tal que b+ v = a. Mas v 6= 0 =⇒ ∃ p ∈ N tal que v = s(p).
Segue que a = b + v = b + s(p) = b + p + 1 = s(b) + p, de onde se deduz que s(b) ≤ a e tambe´m
temos que a ≤ s(b) ou s(b) ≤ a.
Como aplicac¸a˜o da Lei da Tricotomia, vamos dar uma outra demonstrac¸a˜o da Proposic¸a˜o 1.4.10
(lei do cancelamento para a multiplicac¸a˜o).
2 a Demonstrac¸a˜o da Proposic¸a˜o 1.4.10. Suponhamos que a, b ∈ N, c ∈ N∗ e a · c = b · c. Queremos
provar que a = b. Pela propriedade da Tricotomia, vale uma e apenas uma das treˆs a = b, a < b
ou b < a. Portanto, para mostrar que a = b basta justificar que nenhuma das duas desigualdades
pode ocorrer. Se a < b, enta˜o, pela parte (ii) da Proposic¸a˜o 1.5.3, seguiria que ac < bc, o que
contraria a hipo´tese de que ac = bc. Portanto, a < b na˜o ocorre. Pela mesma raza˜o b < a n ao
ocorre. Logo, a = b, provando a proposic¸a˜o.
Demonstrac¸a˜o da Proposic¸a˜o 1.5.3 (iv). Provamos por contraposic¸a˜o. Sejam a, b ∈ N e c ∈ N∗.
Se na˜o valer a < b, enta˜o, pela Tricotomia, temos b ≤ a. Pela parte (i)′ desta mesma Proposic¸a˜o
1.5.3, segue que bc ≤ ac e, portanto, na˜o vale ac < bc, concluindo a demonstrac¸a˜o.
1.6 Resumindo N
Vimos na sec¸a˜o anterior que podemos construir N atrave´s dos Axiomas de Peano e assim definir
uma soma e um produto com as seguintes propriedades.
• Associatividade
da soma ∀ a, b, c ∈ N, (a+ b) + c = a+ (b+ c).
do produto ∀ a, b, c ∈ N, (a · b) · c = a · (b · c).
• Comutatividade
13
da soma ∀ a, b ∈ N, a+ b = b+ a.
do produto ∀ a, b ∈ N, a · b = b · a.
• Elemento neutro
da soma ∀n ∈ N, n+ 0 = n = 0 + n.
do produto ∀n ∈ N, n · 1 = n = 1 · n.
• Distributividade
∀ a, b, c ∈ N, (a+ b) · c = a · c+ b · c = c · (a+ b).
• Leis do cancelamento
para a soma ∀ a, b, c ∈ N, a+ b = a+ c =⇒ b = c.
para o produto ∀ a, b, c ∈ N, ac = bc e c 6= 0 =⇒ a = b.
• Absorc¸a˜o
∀ a ∈ N, a · 0 = 0 = 0 · a.
• Integridade
∀ a, b ∈ N, a · b = 0 =⇒ a = 0 ou b = 0.
• Propriedades u´nicas de N
∀ a, b,∈ N, a+ b = 0 =⇒ a = b = 0.
∀ a, b,∈ N, a · b = 1 =⇒ a = b = 1.
Tambe´m definimos uma ordem ≤ dada por
a ≤ b⇐⇒ ∃ c ∈ N tal que a+ c = b,
que satisfaz as seguintes propriedades.
• 0 ≤ n, ∀n ∈ N.
• ∀ a, b ∈ N, a ≤ a+ b.
• Reflexiva
a ≤ a, ∀ a ∈ N.
• Anti-sime´trica
a ≤ b e b ≤ a =⇒ a = b.
• Transitiva
a ≤ b e b ≤ c =⇒ a ≤ c.
• E´ compat´ıvel e cancelativa
com a soma ∀ a, b, c ∈ N, a < b ⇐⇒ a+ c < b+ c.
e o produto ∀ a, b ∈ N, ∀ c ∈ N∗, a < b ⇐⇒ ac < bc.
• Tricotomia
Se a, b ∈ N, vale uma e apenas uma das alternativas: a < b, b < a ou a = b.
14
1.7 Subtrac¸a˜o em N
Sejam a e b dois nu´meros naturais, se a ≤ b, enta˜o, por definic¸a˜o, existe um nu´mero natural c tal
que a+c = b. E´ importante notar que esse nu´mero c tal que a+c = b e´ u´nico. De fato, se a+c = b
e a + c′ = b, enta˜o a + c = a + c′. Podemos, enta˜o, definir o nu´mero b menos a, denotado por
b− a, como sendo esse nu´mero c. Assim, por essa definic¸a˜o,
c = b− a⇐⇒ b = a+ c.
Observamos que nos nu´meros naturais a subtrac¸a˜o entre dois nu´meros quaisquer nem sem-
pre existe, note que para definir b menos a acima necessitamos que a ≤ b. Ale´m disso, muitas
propriedades que valem para a soma na˜o sa˜o verdadeiras para a subtrac¸a˜o. Um exemplo e´ a
associatividade.
(10− 4)− 2 = 6− 2 = 4, mas 10− (4− 2) = 10− 2 = 8.
Mostramos a seguir, alguns resultados envolvendo a subtrac¸a˜o.
Proposic¸a˜o 1.7.1. ∀ a ∈ N, a− a = 0.
Demonstrac¸a˜o. Como 0 e´ o elemento neutro da soma temos que ∀ a ∈ N, a + 0 = a, logo, pela
definic¸a˜o de subtrac¸a˜o, a− a = 0.
Proposic¸a˜o 1.7.2. ∀ a, b ∈ N, (a+ b)− b = a.
Demonstrac¸a˜o. Para t = b, temos que a+t = a+b. Enta˜o, pela definic¸a˜o da ordem e da subtrac¸a˜o,
temos que a ≤ a+ b e (a+ b)− a = t = b.
Proposic¸a˜o 1.7.3. ∀ a, b ∈ N, a ≤ b =⇒ (b− a) + a = b.
Demonstrac¸a˜o. Como a ≤ b existe, por definic¸a˜o, c ∈ N tal que b = a + c e, portanto, b− a = c ;
somando a obtemos (b− a) + a = c+ a = b, pela primeira igualdade.
Proposic¸a˜o 1.7.4. ∀ a, b, c ∈ N, c ≤ b =⇒ (a+ b)− c = a+ (b− c).
Demonstrac¸a˜o. Suponhamos que c ≤ b. Enta˜o, ∃ t ∈ N tal que b = t+ c. Enta˜o, pela Proposic¸a˜o
1.7.2, (a+ b)− c = (a+ t+ c)− c esta´ bem definido e e´ igual a a+ t, isto e´, (a+ b)− c = a+ t =
a+ (b− c).
Proposic¸a˜o 1.7.5. ∀ a, b, c ∈ N, a ≤ b =⇒ c · (b− a) = c · b− c · a
Demonstrac¸a˜o. Como a ≤ b, existe, por definic¸a˜o, t ∈ N tal que b = a + t e portanto b − a = t.
Multiplicando as duas igualdades por c obtemos b · c = (a+ t) · c = a · c+ t · c e (b− a) · c = t · c.
Assim, pela definic¸a˜o de subtrac¸a˜o, b · c− a · c = t · c = (b− a) · c.
Proposic¸a˜o 1.7.6. Sejam a, b, c ∈ N tais que a − (b − c) esta´ definido, enta˜o (a + c) − b esta´
definido e a− (b− c) = (a+ c)− b.
Demonstrac¸a˜o. Como a − (b − c) esta´ definido sabemos que (b − c) ≤ a e c ≤ b. Somando c na
primeira desigualdade e usando a Proposic¸a˜o 1.7.3, obtemos b = (b − c) + c ≤ a + c e, portanto,
(a+c)− b esta´ definido. Agora, como ambos esta˜o definidos, existe s, t ∈ N tais que a− (b−c) = s
e (a+ c)− b = t. Logo, pela definic¸a˜o de subtrac¸a˜o temos que a = s+(b− c) (∗) e (a+ c) = t+ b,
somando c em (*) e usando a Proposic¸a˜o 1.7.3, obtemos a + c = s + (b − c) + c = s + b. Assim,
s+ b = a+ c = t+ b. Pela lei do cancelamento, temos a− (b− c) = s = t = (a+ c)− b.
15
1.8 Mais propriedades u´nicas de N
Ja´ vimos nas sec¸o˜es anteriores propriedades de N que na˜o sa˜o va´lidas nos conjuntos nume´ricos
mais populares Z, Q, R e C. Sa˜o elas:
• Induc¸a˜o
• ∀ a, b ∈ N, a+ b = 0 =⇒ a = b = 0
• ∀ a, b ∈ N, a · b = 1 =⇒ a = b = 1.
Nesta sec¸a˜o exploramos outras propriedades desse tipo.
Proposic¸a˜o 1.8.1. ∀ a, b ∈ N, a + b = 1 =⇒ a = 1 ou b = 1. Em particular, se a 6= 0 enta˜o
b = 0.
Demonstrac¸a˜o. Suponhamos que a + b = 1. Temos que mostrar que um dos dois, a ou b, e´ igual
a 1. Temos duas possibilidades a considerar, a = 0 ou a 6= 0.
Se a = 0, enta˜o 1 = a+ b = 0 + b = b. Nesse caso, a = 0 e b = 1.
Se a 6= 0, sabemos que a e´ sucessor de algum nu´mero natural, ou seja, ∃ u ∈ N tal que a = s(u).
Desse modo, temos
s(u+ b) = s(u) + b = a+ b = 1 = s(0).
Como s e´ uma func¸a˜o injetora, temos que u+ b = 0, logo, pela segunda propriedade acima, u= 0
e b = 0 e, portanto, a = s(u) = s(0) = 1 e b = 0.
A proposic¸a˜o acima nos diz que as u´nicas decomposic¸o˜es do nu´mero 1 como soma de dois
nu´meros naturais sa˜o 1 = 0 + 1 e 1 = 1 + 0.
Na Sec¸a˜o 1.3 vimos que 0 ≤ n, ∀n ∈ N, em particular, 0 < 1. Em seguida perguntamos,
sera´ que existe algum nu´mero natural entre 0 e 1? A resposta e´ na˜o. De fato, se existe x ∈ N e
x 6= 0 tal que 0 < x < 1, enta˜o existe u, v ∈ N∗ tais que 0 + u = x e x + v = 1. Desse modo,
1 = x + v = (0 + u) + v = 0 + (u + v) = u + v. Assim, pela Proposic¸a˜o 1.8.1, como u 6= 0,
temos v = 0 que e´ uma contradic¸a˜o (consequentemente, n ∈ N∗ =⇒ n ≥ 1). Estendemos esse
argumento na seguinte proposic¸a˜o.
Proposic¸a˜o 1.8.2. Na˜o existe nenhum nu´mero natural entre um nu´mero natural e o seu sucessor.
Ou seja,
(∀n ∈ N)(@ x ∈ N) n < x < n+ 1.
Demonstrac¸a˜o. Dado n ∈ N seja x ∈ N tal que n < x < n + 1. Logo, existem u e v ∈ N∗
tais que x = n + u e n + 1 = x + v. Substituindo a primeira igualdade na segunda obtemos,
n+ 1 = (n+ u) + v = n + (u+ v). Pela lei do cancelamento, temos 1 = u+ v e, pela Proposic¸a˜o
1.8.1, uma contradic¸a˜o, ja´ que u e v ∈ N∗.
Outra propriedade interessante e´ a seguinte (que tambe´m vale em Z).
(∀n ∈ N)(∀m ∈ N) n < m =⇒ n+ 1 ≤ m
Demonstrac¸a˜o. Faremos a demonstrac¸a˜o por contraposic¸a˜o. Suponhamos que n + 1 > m. Logo,
por definic¸a˜o de < existe u ∈ N∗ tal que m + u = n + 1. Logo, pela definic¸a˜o de subtrac¸a˜o,
(m + u) − 1 = n. Como u ∈ N∗, temos 1 ≤ u, logo u − 1 ∈ N e, pela Propisic¸a˜o 1.7.2 temos
n = (m+ u)− 1 = m+ (u− 1), ou seja, m ≤ n.
16
Uma consequeˆncia importante do Princ´ıpio da Induc¸a˜o Matema´tica e´ que N e´ bem ordenado
(todo subconjunto na˜o vazio de N possui menor elemento). Na verdade, o Princ´ıpio da Induc¸a˜o
Matema´tica e o Princ´ıpio da Boa Ordenac¸a˜o sa˜o equivalentes, ou seja, supondo um obtemos
o outro. Como em nossa construc¸a˜o de N tomamos o Princ´ıpio da Induc¸a˜o Matema´tica como
axioma, vamos mostrar agora que este implica o da Boa Ordenac¸a˜o.
Definic¸a˜o 1.8.3. Seja A ⊆ N. Dizemos que
(i) A possui um menor elemento, ou um elemento mı´nimo, se e somente se existe a∗ ∈ A tal que
a∗ ≤ a, ∀ a ∈ A.
(ii) A possui um maior elemento, ou um elemento ma´ximo, se e somente se existe a′ ∈ A tal que
a ≤ a′, ∀ a ∈ A.
Note que se A possui um menor elemento, enta˜o ele e´ u´nico. De fato, se a∗ e a∗∗ sa˜o elementos
mı´nimos de A enta˜o, como ambos esta˜o em A, temos a∗ ≤ a∗∗ e a∗∗ ≤ a∗; ou seja, a∗ = a∗∗. Agora
podemos falar no elemento mı´nimo (e na˜o um elemento mı´nimo), que denotaremos por min A. Da
mesma maneira, se A possui um maior elemento, enta˜o ele e´ u´nico e sera´ denotado por max A.
Existem va´rias demonstrac¸o˜es diferentes para o Princ´ıpio da Boa Ordenac¸a˜o (supondo o
Princ´ıpio da Induc¸a˜o) escolhemos uma que usa a contraposic¸a˜o do Princ´ıpio da Induc¸a˜o.
Teorema 1.8.4. (Princ´ıpio da Boa Ordenac¸a˜o). Se A ⊆ N e´ na˜o vazio, enta˜o A possui menor
elemento, ou seja, existe a∗ ∈ N tal que a∗ ≤ x, ∀x ∈ A.
Demonstrac¸a˜o. Seja A ⊆ N e A 6= ∅. Se 0 ∈ A enta˜o 0 e´ o menor elemento de A, ja´ que
0 ≤ n, ∀n ∈ N. Podemos supor, enta˜o, que 0 6∈ A, ou seja, que {0} ∩ A = ∅. Seja B o conjunto
de todos os nu´meros naturais n tais que {0, 1, 2, 3, . . . , n} ∩ A = ∅, temos que 0 ∈ B. Como
A 6= ∅, existe m ∈ A, mas m ∈ {0, 1, 2, 3, . . . ,m} ∩ A, logo m 6∈ B, ou seja, B 6= N. Como
0 ∈ B 6= N, o Princ´ıpio da Induc¸a˜o nos garante que existe n∗ ∈ B tal que n∗ + 1 6∈ B (caso
contra´rio B = N). Portanto, {0, 1, 2, 3, . . . , n∗} ∩ A = ∅ e {0, 1, 2, 3, . . . , n∗ + 1} ∩ A 6= ∅. Segue
que n∗ + 1 ∈ A ⊆ {n∗ + 1, n∗ + 2, . . .}, e assim, a∗ = n∗ + 1 e´ o elemento mı´nimo de A.
Essa proposic¸a˜o garante que todo o subconjunto na˜o vazio de N possui menor elemento, mas
e maior elemento? Sera´ que tem? A resposta e´, evidentemente, que na˜o, pois, por exemplo, o
conjunto dos nu´meros pares na˜o possui maior elemento. Nos perguntamos quando possui.
Dizemos que um conjunto A ⊆ N e´ limitado superiormente se e somente se existir um nu´mero
n ∈ N tal que a ≤ n, ∀ a ∈ A. Neste caso, diremos que n e´ uma cota superior para A. A
pergunta que surge naturalmente depois dessa definic¸a˜o e´: qual a diferenc¸a entre o maior elemento
da Definic¸a˜o 1.8.3 e de cota superior? A diferenc¸a e´ que o maior elemento tem que pertencer ao
conjunto, em particular isso garante que ele e´ u´nico, ja´ uma cota superior na˜o, e portanto qualquer
nu´mero maior que uma cota superior tambe´m e´ cota superior. O seguinte resultado decorre do
Princ´ıpio da Boa Ordenac¸a˜o.
Corola´rio 1.8.5. Se A ⊆ N e´ na˜o vazio e limitado superiormente, enta˜o A possui maior elemento.
Demonstrac¸a˜o. Seja A ⊆ N, A 6= ∅ e limitado superiormente. Logo, ∃n ∈ N que e´ cota superior
de A, ou seja, a ≤ n, ∀ a ∈ A. Tomamos B = {y ∈ N; y = n− a, a ∈ A}. Como A 6= ∅, temos que
B 6= ∅, logo B possui menor elemento n− a∗ para algum a∗ ∈ A. Afirmamos que max A = a∗. De
fato, para cada a ∈ A temos que n− a ∈ B e, portanto, n− a∗ ≤ n− a, ja´ que min B = n− a∗.
Somando a∗ + a e aplicando a Proposic¸a˜o 1.7.3, obtemos n+ a ≤ n+ a∗. Cancelando n, obtemos
a ≤ a∗.
17
1.9 Binoˆmio de Newton
Nesta sec¸a˜o estudaremos o Binoˆmio de Newton, que e´ uma ferramenta importante para o estudo
da Aritme´tica. Nossa abordagem sera´ de um ponto de vista puramente alge´brico. Isto sera´
complementado por uma abordagem do ponto de vista combinato´rio, que sera´ feita posteriormente,
na disciplina de Combinato´ria.
Consideremos a expressa˜o f(x) = (1 + x)n, onde n ∈ N e x e´ uma varia´vel. Enta˜o f(x) e´ um
polinoˆmio de grau n. Por exemplo,
(1 + x)2 = 1 + 2x+ x2,
(1 + x)3 = (1 + 2x+ x2)(1 + x) = 1 + 3x+ 3x2 + x3,
(1 + x)4 = (1 + 3x+ 3x2 + x3)(1 + x) = 1 + 4x+ 6x2 + 4x3 + x4.
Enta˜o,
(1 + x)n = a0 + a1x+ a2x
2 + · · ·+ akxk + · · ·+ anxn, (11)
para certos coeficientes a0, a1, a2, . . . , an. Queremos determinar esses coeficientes ak. Os nu´meros
ak sa˜o chamados de coeficientes binomiais e sera˜o denotados por
ak =
(
n
k
)
.
Com isto, (11) se torna
(1 + x)n =
(
n
0
)
+
(
n
1
)
x+
(
n
2
)
x2 + · · ·+
(
n
k
)
xk + · · ·+
(
n
n
)
xn =
n∑
k=0
(
n
k
)
xk. (12)
Nosso objetivo e´ determinar uma expressa˜o em forma fechada para os coeficientes binomiais
(
n
k
)
.
Observac¸a˜o 1.9.1. Dado um polinoˆmio p(x) = bnx
n+bn−1xn−1+· · ·+b1x+b0, costuma-se chamar
de rec´ıproco de p(x) o polinoˆmio b0x
n+ b1x
n−1+ · · ·+ bn−1x+ bn, que se obte´m invertendo a ordem
dos coeficientes de p(x). Por exemplo, o rec´ıproco do polinoˆmio p(x) = 2x4+x3− 5x2− 3x+4 e´ o
polinoˆmio 4x4− 3x3− 5x2+ x+2. O rec´ıproco de um polinoˆmio p(x) de grau n e´ obtido primeiro
substituindo x por
1
x
e, em seguida, multiplicando por xn. De fato, se p(x) = bnx
n + bn−1xn−1 +
· · ·+ b1x+ b0, enta˜o
p
(
1
x
)
= bn
(
1
x
)n
+ bn−1
(
1
x
)n−1
+ · · ·+ b1
(
1
x
)
+ b0,
de modo que
xnp
(
1
x
)
= b0x
n + b1x
n−1 + · · ·+ bn−1x+ bn.
Assim, o rec´ıproco de um polinoˆmio p(x) de grau n e´ xnp(1/x). Outra observac¸a˜o importante e´
que o polinoˆmio (1 + x)n e´ o rec´ıproco de si mesmo. De fato, xn · (1 + 1/x)n = (x · (1 + 1/x))n =
(1+x)n. Este fato sera´ usado na demonstrac¸a˜o do lema abaixo. Finalmente, observemos que se um
polinoˆmio p(x) = bnx
n+bn−1xn−1+ · · ·+b1x+b0 e´ o rec´ıproco de si mesmo, enta˜o seus coeficientes
sa˜o sime´tricos, ou seja, b0 = bn, b1 = bn−1, b2 = bn−2, . . . .
18
Lema 1.9.2. Para todo n ∈ N∗ e para todo k ∈ N com 0 ≤ k ≤ n, valem as propriedades(
n
0
)
= 1; (13)(
n
n
)
= 1; (14)(
n
k
)
=
(
n
n− k
)
. (15)
Demonstrac¸a˜o. Para justificar que vale (13), basta tomar x = 0 em (12).
Para provar que vale (15), utilizamos os fatos mencionados na Observac¸a˜o 1.9.1 acima. Vimos
que o polinoˆmio(1 + x)n =
(
n
0
)
+
(
n
1
)
x+
(
n
2
)
x2 + · · ·+
(
n
k
)
xk + · · ·+
(
n
n
)
xn
e´ o rec´ıproco de si mesmo. Logo, seus coeficientes sa˜o sime´tricos, isto e´,(
n
0
)
=
(
n
n
)
,
(
n
1
)
=
(
n
n− 1
)
,
(
n
2
)
=
(
n
n− 2
)
, · · ·
(
n
k
)
=
(
n
n− k
)
, · · ·
provando que vale a propriedade (15).
A propriedade (14) segue de (13) e (15).
Proposic¸a˜o 1.9.3. (Relac¸a˜o de Stifel) Para todo n ∈ N∗ e todo k ∈ N, com 0 ≤ k ≤ n − 1,
vale (
n
k
)
+
(
n
k + 1
)
=
(
n+ 1
k + 1
)
, (16)
Demonstrac¸a˜o. Por um lado, temos que
(1 + x)n+1 =
(
n+ 1
0
)
+
(
n+ 1
1
)
x+
(
n+ 1
2
)
x2 + · · ·+
(
n+ 1
n+ 1
)
xn+1. (17)
Por outro lado,
(1 + x)n+1 = (1 + x) · (1 + x)n
= (1 + x)
[(
n
0
)
+
(
n
1
)
x+ · · ·+
(
n
n− 1
)
xn−1 +
(
n
n
)
xn
]
=
(
n
0
)
+
[(
n
0
)
+
(
n
1
)]
x+ · · ·+
[(
n
n− 1
)
+
(
n
n
)]
xn +
(
n
n
)
xn+1.
(18)
Para cada k ∈ {0, 1, 2, . . . , n − 1}, comparando o coeficiente de xk em (17) e na u´ltima linha de
(18), obtemos (16).
Proposic¸a˜o 1.9.4. Para todos k, n ∈ N∗, com 1 ≤ k ≤ n, temos
k!
(
n
k
)
= n(n− 1)(n− 2) · · · (n− (k − 1)).
19
Demonstrac¸a˜o. Vamos provar por induc¸a˜o que para todo n ∈ N∗ vale a propriedade
P (n) : k!
(
n
k
)
= n(n− 1)(n− 2) · · · (n− (k − 1)), ∀ k ∈ N∗, com 1 ≤ k ≤ n.
Base de Induc¸a˜o: Verificar que vale P (1).
De fato, n = 1 =⇒ k = 1, logo 1!
(
1
1
)
= 1 se verifica. Logo, P (1) e´ verdadeira.
Passagem de Induc¸a˜o: Suponhamos que, para algum n, P (n) seja verdadeira.
Vamos mostrar que P (n+ 1) tambe´m e´ verdadeira.
Se k = 1 temos, pela relac¸a˜o de Stifel, 1!
(
n+ 1
1
)
= 1! ·
[(
n
1
)
+
(
n
0
)]
. Ja´ sabemos que(
n
0
)
= 1 e por hipo´tese de induc¸a˜o que
(
n
1
)
= n. Logo, 1!
(
n+ 1
1
)
= 1! ·
[(
n
1
)
+
(
n
0
)]
= n+1.
Se k = n+ 1 temos, (n+ 1)!
(
n+ 1
n+ 1
)
= (n+ 1)! · 1 = (n+ 1)!.
Se 2 ≤ k ≤ n, enta˜o, pela Relac¸a˜o de Stifel,
k!
(
n+ 1
k
)
= k! ·
[(
n
k
)
+
(
n
k − 1
)]
= k!
(
n
k
)
+ k · (k − 1)!
(
n
k − 1
)
.
Aplicando a hipo´tese de induc¸a˜o, obtemos
k!
(
n+ 1
k
)
=
[
n(n− 1)(n− 2) · · · (n− (k − 1))
]
+ k ·
[
n(n− 1)(n− 2) · · · (n− (k − 2))
]
= n(n− 1)(n− 2) · · · (n− (k − 2)) · [(n− (k − 1)) + k]
= n(n− 1)(n− 2) · · · (n− (k − 2)) · (n+ 1)
= (n+ 1)n(n− 1) · · · ((n+ 1)− (k − 1),
ou seja, vale para todo k com 2 ≤ k ≤ n. Portanto, se P (n) for verdadeira para algum n enta˜o
P (n+ 1) tambe´m e´ verdadeira. Logo, P (n) e´ verdadeira para qualquer n ≥ 1.
Corola´rio 1.9.5. Para todos n, k ∈ N, com 0 ≤ k ≤ n, temos(
n
k
)
=
n!
k!(n− k)! . (19)
Demonstrac¸a˜o. Pela Proposic¸a˜o 1.9.4, (19) vale para todo k com 1 ≤ k ≤ n. E´ imediato verificar
que (19) vale tambe´m para k = 0.
Exemplo 1.9.6. Usando (12), podemos calcular facilmente
100∑
i=0
(
100
i
)
·7i. De fato, tomando x = 7
em (12), obtemos
100∑
i=0
(
100
i
)
· 7i = (1 + 7)100 = 8100 = (23)100 = 2300.
Teorema 1.9.7. (Binoˆmio de Newton) Sejam a, b ∈ R e seja n ∈ N∗. Enta˜o,
(a+ b)n = an +
(
n
1
)
an−1b+
(
n
2
)
an−2b2 + · · ·+
(
n
n− 1
)
abn−1 + bn. (20)
20
Demonstrac¸a˜o. Se a = 0, o resultado e´ imediato. Se a 6= 0, aplicando (12) com x = b
a
, temos
(a+ b)n = an
(
1 +
b
a
)n
= an
[
1 +
(
n
1
)
b
a
+
(
n
2
)(
b
a
)2
+ · · ·+
(
n
n
)(
b
a
)n]
= an +
(
n
1
)
an−1b+
(
n
2
)
an−2b2 + · · ·+
(
n
n− 1
)
abn−1 + bn.
Exemplo 1.9.8. Como uma aplicac¸a˜o direta do Binoˆmio de Newton obtemos, por exemplo,
(a+ b)0 = 1
(a+ b)1 = a+ b
(a+ b)2 = a2 + 2ab+ b2
(a+ b)3 = a3 + 3a2b+ 3ab2 + b3
(a+ b)4 = a4 + 4a3b+ 6a2b2 + 4ab3 + b4
(a+ b)5 = a5 + 5a3b+ 10a3b2 + 10a2b3 + 5ab4 + b5
Olhando apenas para os coeficientes da tabela acima, costuma-se considerar o chamado triaˆngulo
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
de Pascal, mostrado a` esquerda. Note que somando as
linhas do triaˆngulo de Pascal, obtemos os nu´meros 1,
2, 4, 8, 16, etc, ou seja, poteˆncias de 2. Somos levados
assim a conjecturar a seguinte propriedade.
Propriedade.
(
n
0
)
+
(
n
1
)
+
(
n
2
)
+ · · · +
(
n
n
)
= 2n,
ou seja, a soma da linha n do triaˆngulo de Pascal vale
2n.
Para provar a propriedade que acabamos de conjecturar, basta tomar a = 1 = b no Binoˆmio de
Newton (20).
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1±°²¯
Vamos agora somar os elementos iniciais de uma coluna
do triaˆngulo de Pascal. Somando, por exemplo, os ele-
mentos da coluna indicada na figura a` esquerda, temos
1+3+6+10+15 = 35. O resultado, 35, e´ um elemento
da pro´xima coluna, que aparece circulado na figura. O
resultado que encontramos foi(
2
2
)
+
(
3
2
)
+
(
4
2
)
+
(
5
2
)
+
(
6
2
)
=
(
7
3
)
.
Somos levados a conjecturar uma outra propriedade.
Propriedade. Para quaisquer n, k ∈ N com 0 ≤ k ≤ n, vale(
k
k
)
+
(
k + 1
k
)
+
(
k + 2
k
)
+ · · ·+
(
n
k
)
=
(
n+ 1
k + 1
)
. (21)
Demonstrac¸a˜o. Do lado esquerdo da igualdade temos(
k
k
)
= coeficiente de xk no desenvolvimento de (1 + x)k
21
(
k + 1
k
)
= coeficiente de xk no desenvolvimento de (1 + x)k+1(
k + 2
k
)
= coeficiente de xk no desenvolvimento de (1 + x)k+2
...(
n
k
)
= coeficiente de xk no desenvolvimento de (1 + x)n.
Portanto, o lado esquerdo de (21) e´ igual ao coeficiente de xk no desenvolvimento de
(1 + x)k + (1 + x)k+1 + (1 + x)k+2 + · · ·+ (1 + x)n. (22)
Mas (22) e´ a soma de uma p.g. de raza˜o (1+ x), cujo primeiro termo e´ (1+x)k cujo u´ltimo termo
e´ (1 + x)n e, portanto, vale
(1 + x)n+1 − (1 + x)k
(1 + x)− 1 .
Enta˜o,
lado esquerdo de (21) = coeficiente de xk no desenvolvimento de
(1 + x)n+1 − (1 + x)k
x
= coeficiente de xk+1 no desenvolvimento de (1 + x)n+1 − (1 + x)k
= coeficiente de xk+1 no desenvolvimento de (1 + x)n+1
=
(
n+ 1
k + 1
)
,
pois o desenvolvimento de (1+x)k na˜o conte´m nenhum termo em xk+1. Esta´ provada a propriedade.
Exemplo 1.9.9. O objetivo deste exemplo e´ dar uma aplicac¸a˜o interessante da propriedade (21)
do triaˆngulo de Pascal.
1
1 2
1 2 3
1 2 3 4
...
1 2 3 4 · · · n
(a) Comec¸amos mostrando que a soma da
k−e´sima linha do triaˆngulo ao lado vale
(
k + 1
2
)
.
De fato, a soma da k−e´sima linha do triaˆngulo e´
1 + 2 + 3 + · · ·+ k = k(k + 1)
2
=
(
k + 1
2
)
.
(b) A seguir, calculamos a soma de todos os elementos do triaˆngulo de duas maneiras diferentes.
A primeira maneira consiste em somar as linhas e depois somar os resultados. Somando desse
modo, obtemos (
2
2
)
+
(
3
2
)
+
(
4
2
)
+ · · ·+
(
n+ 1
2
)
,
que, pela propriedade (21), e´ igual a
(
n+ 2
3
)
. A segunda maneira e´ somando primeiro as diagonais
e depois somando os resultados. A soma da primeira diagonal e´ 1 + 1 + · · · + 1 = n, a soma da
22
segunda diagonal e´ 2 + 2 + · · ·+ 2 = 2 · (n− 1), e assim por diante. Somando todos os elementos
do triaˆngulo dessa segunda maneira, obtemos
1 · n+ 2 · (n− 1) + 3 · (n− 2) + · · ·+ n · 1.
Como somamos de maneiras diferentes os mesmos nu´meros, os resultados obtidos, devem coincidir.
Obtemos assim a igualdade
1 · n+ 2 · (n− 1) + 3 ·(n− 2) + · · ·+ n · 1 =
(
n+ 2
3
)
.
­
­
­
­
­
­
­­
J
J
J
J
J
J
JJ
­
­
­
­
­
­­
­
­
­
­­
­
­
­­
­­J
J
J
J
J
JJ
J
J
J
JJ
J
J
JJ
JJ
a a′
b b′
c c′
v
(c) Vamos agora contar o nu´mero de triaˆngulos com ve´rtice para
cima e base para baixo que podem ser vistos em um reticulado
como o que esta´ mostrado ao lado, mas formado por n fileiras.
Dividimos esses triaˆngulos em casos, conforme em qual linha
horizontal esta´ a base. O nu´mero de triaˆngulos com base na linha
aa′ e´ 1. O nu´mero de triaˆngulos com base na linha bb′ e´ 1+2, um
com ve´rtice em v e dois com ve´rtice sobre a linha aa′. O nu´mero
de triaˆngulos com base na linha cc′ e´ 1 + 2 + 3, um com ve´rtice
em v, dois com ve´rtice sobre a linha aa′ e treˆs com ve´rtice sobre a linha cc′. E assim por diante.
Conclu´ımos que o nu´mero total de triaˆngulos e´ a soma considerada no item (b), ou seja, o total
de triaˆngulos e´
(
n+ 2
3
)
.
Exemplo 1.9.10. Outra aplicac¸a˜o interessante dos coeficientes binomiais e´ a sua relac¸a˜o com o
nu´mero de subconjuntos de um conjunto.
Seja A um conjunto com n elementos, n 6= 0. Enta˜o,
(i) O nu´mero de subconjuntos de A distintos com i elementos, 0 ≤ i ≤ n, e´
(
n
i
)
;
(ii) O nu´mero de elementos do conjunto das partes de A e´ 2n.
Note que utilizando (i) e (ii) temos uma outra demonstrac¸a˜o de
(
n
0
)
+
(
n
1
)
+
(
n
2
)
+· · ·+
(
n
n
)
=
2n, ja´ que o conjunto das partes de A e´ o conjunto formado por todos os subconjuntos de A.
Demonstrac¸a˜o. Ambas demonstrac¸o˜es sa˜o por induc¸a˜o em n ∈ N∗.
(i) Base de induc¸a˜o: Se n = 1 enta˜o os u´nicos subconjuntos de A sa˜o ∅ e Amesmo, confirmando(
1
0
)
= 1 e
(
1
1
)
= 1.
Passagem de induc¸a˜o: Suponhamos que para um certo n ∈ N∗, o nu´mero de subconjuntos
distintos (de um conjunto com n elementos) com i elementos e´
(
n
i
)
, ∀i com 0 ≤ i ≤ n.
Seja A um conjunto com n + 1 elementos. Podemos escrever A = A′ ∪ {x}, onde x ∈ A e
A′ = A − {x}. Logo, A′ tem n elementos. Seja B um subconjunto de A com i elementos, onde
0 ≤ i ≤ n+ 1.
Se x 6∈ B, enta˜o B ⊆ A′ e temos, por hipo´tese de induc¸a˜o
(
n
i
)
conjuntos desse tipo.
Se x ∈ B, enta˜o B = {x} ∪ C com C ⊆ A′ e o nu´mero de elementos de C e´ i − 1. Neste caso
temos
(
n
i− 1
)
conjuntos distintos desse tipo.
23
Logo, o nu´mero total de subconjuntos de A com i elementos e´
(
n
i− 1
)
+
(
n
i
)
=
(
n+ 1
i
)
,
onde a igualdade vale pela fo´rmula de Stiffel.
(ii) A demonstrac¸a˜o e´ muito semelhante a anterior e e´ deixada como exerc´ıcio.
2 Divisibilidade em N
2.1 Mu´ltiplos e Divisores
Definic¸a˜o 2.1.1. Dados a, b ∈ N e b 6= 0 dizemos que b divide a, ou que a e´ um mu´ltiplo de b,
ou ainda que b e´ um divisor de a , e anotamos b | a, se e somente se existe c ∈ N tal que a = b · c.
Assim, 3 | 6 pois 6 = 2 · 3. Cuidado! Na˜o devemos confundir o s´ımbolo | com o trac¸o de frac¸a˜o.
Note que o c da definic¸a˜o e´ uma soluc¸a˜o da equac¸a˜o bx = a. Esta equac¸a˜o pode na˜o ter soluc¸a˜o
em N, por exemplo, 3x = 8 na˜o tem soluc¸a˜o em N, mas sempre tem soluc¸a˜o em Q. Logo, a
definic¸a˜o de divisibilidade na˜o faria sentido em Q. Por esse motivo, so´ estudamos divisibilidade
em N e posteriormente em Z.
Ale´m disso, se bx = a tem soluc¸a˜o, enta˜o esta soluc¸a˜o e´ u´nica. De fato, se c1 e c2 satisfazem a
equac¸a˜o, enta˜o bc1 = a = bc2. Como b 6= 0, podemos cancela´-lo e obtemos c1 = c2. Esse inteiro e´
denominado o “quociente” de a por b.
Se b = 0, enta˜o bx = 0, para qualquer x ∈ N, portanto, a equac¸a˜o bx = a tem soluc¸a˜o se e
somente se a = 0. Nesse caso a soluc¸a˜o da equac¸a˜o na˜o so´ na˜o e´ u´nica, como existe uma infinidade
de soluc¸o˜es. Se a = 0 na Definic¸a˜o 2.1.1, temos que b = 0 ou c = 0; em ambos os casos, 0 | a.
Assim, 0 | a se, e somente se, a = 0. Desse modo, vemos que o caso b = 0 “estraga” a nossa
definic¸a˜o de divisibilidade e, por isso, b 6= 0 na definic¸a˜o.
Se bx = a na˜o tem soluc¸a˜o em N, dizemos que b na˜o divide a e anotamos b - a.
Observac¸a˜o 2.1.2. Note que a relac¸a˜o de divisibilidade ( | ) tem uma certa semelhanc¸a com a
relac¸a˜o de ordem (≤); ela e´ a versa˜o multiplicativa da relac¸a˜o de ordem.
• b ≤ a ⇐⇒ (∃ c ∈ N) a = b+ c
• b | a ⇐⇒ (∃ c ∈ N) a = b · c
Ale´m disso, elas esta˜o relacionadas da seguinte maneira.
∀ a, b ∈ N, b | a e a 6= 0 =⇒ b ≤ a.
De fato, b | a e a 6= 0 =⇒ ∃ c ∈ N tal que 0 6= a = b · c, logo, c 6= 0 e portanto 1 ≤ c.
Multiplicando por b, temos b ≤ b · c = a.
Destacamos treˆs consequeˆncias imediatas dessa relac¸a˜o.
(i) ∀ a ∈ N , 1 | a; ja´ que a = a · 1.
(ii) ∀ a ∈ N∗ , a | a; ja´ que a = a · 1. (reflexiva)
(iii) ∀ a ∈ N∗ , a | 0; ja´ que 0 = a · 0.
A seguir coletamos va´rias propriedades de | em uma mesma proposic¸a˜o.
Proposic¸a˜o 2.1.3. As seguintes propriedades sa˜o va´lidas.
D1 : ∀ a, b ∈ N∗, a | b e b | a =⇒ a = b (anti-sime´trica)
D2 : ∀ a, b, c ∈ N∗, a | b e b | c =⇒ a | c (transitiva)
24
D3 : ∀ a, b, c ∈ N , a 6= 0 , a | b e a | c =⇒ a | (b · x+ c · y) , ∀ x, y ∈ N
Em particular: a | b =⇒ a | b · x, ∀x ∈ N e a 6= 0 , a | b e a | c =⇒ a | (b+ c).
D4 : ∀ a, b, c, d ∈ N , a 6= 0 , c 6= 0 , a | b e c | d =⇒ a · c | b · d.
D5 : ∀ a, b, c ∈ N , a 6= 0 e a | (b+ c) =⇒
[
a | b⇐⇒ a | c].
D6 : ∀ a, b, c ∈ N , a 6= 0 , a | b , a | c e c ≤ b =⇒ a | (b− c).
Demonstrac¸a˜o. Demonstraremos apenas D1, D3 e D5 as outras provas sa˜o similares e deixamos a
cargo do leitor.
D1 : Suponhamos que a | b e b | a, logo pela definic¸a˜o de | , ∃u, v ∈ N tais que b = a · u e
a = b · v. Substituindo a segunda igualdade na primeira, obtemos b = a · u = b · v · u. Como b 6= 0,
cancelamos b e obtemos 1 = v · u, logo u = v = 1; o que implica que a = b.
D3 : Suponhamos que a 6= 0 , a | b e a | c, logo, pela definic¸a˜o de divisibilidade, ∃u, v ∈ N
tais que b = a · u e c = a · v. Assim, b · x+ c · y = a · u · x+ a · v · y = a · (u · x+ v · y), ∀x, y ∈ N.
Logo, a | (b · x+ c · y) , ∀x, y ∈ N.
D5 : Suponhamos que a, b, c ∈ N , a 6= 0 e a | (b + c). Enta˜o, ∃ t ∈ N tal que b + c = a · t.
Temos que mostrar que vale a equivaleˆncia a | b⇐⇒ a | c.
(=⇒) Se a | b, enta˜o ∃ u ∈ N, b = a · u, logo, a · u = b ≤ b + c = a · t; cancelamos a 6= 0
e obtemos u ≤ t. Enta˜o, o elemento t − u ∈ N esta´ definido. Aplicando a Proposic¸a˜o 1.7.5 do
cap´ıtulo anterior, temos que c = a · t − b = a · t − a · u = a · (t − u). Assim, existe um elemento
v = t− u ∈ N tal que c = a · v. Enta˜o, da definic¸a˜o de divisibilidade, segue que a | c.
(⇐=) Ana´logo.
Passamos agora a alguns resultados sobre divisibilidade em N que tambe´m podem ser vistos
como uma aplicac¸a˜o da divisa˜o polinomial e vice-versa.
Dados b, n ∈ N∗ e x uma varia´vel, tomamos o polinoˆmio f(x) = xn − bn. Como b e´ uma raiz
de f(x), pois f(b) = bn − bn = 0, sabemos que f(x) e´ divis´ıvel por (x − b), ou seja, existe um
polinoˆmio g(x) tal que f(x) = (x− b) ·g(x). Esse polinoˆmio g(x) pode ser obtido fazendo a divisa˜o
polinomial usual, onde obtemos
f(x) = xn − bn = (x− b) · (xn−1 + b · xn−2 + b2 · xn−3 + · · ·+ bn−2 · x+ bn−1).
Fazendo x = a ∈ N, com b < a obtemos an − bn = (a− b) · g(a). Como os coeficientes de g(x) sa˜o
nu´meros naturais temos que g(a) ∈ N e portanto (a− b) | (an − bn). Esse resultado tambe´m pode
ser demonstrado por induc¸a˜o.
Proposic¸a˜o 2.1.4. Sejam a, b, n ∈ N∗ tais que b < a. Enta˜o (a− b) | (an − bn).
Demonstrac¸a˜o. Vamos provar por induc¸a˜o que para todo n ∈ N∗ vale a propriedade
P (n) : (a− b) | (an − bn) ∀ a, b ∈ N∗, com b < a.
Base de Induc¸a˜o: Verificar que vale P (1). E´ claro que (a− b) | (a− b).
Passagem de Induc¸a˜o: Suponhamos que, para algum n, P (n) seja verdadeira.
Vamos mostrar que P (n+1) tambe´m e´ verdadeira, ou seja, que (a−b) | (an+1−bn+1), ∀ a, b ∈ N∗,
com b< a.
De fato, an+1 − bn+1 = a · an − b · an + b · an − b · bn = (a− b) · an + (an − bn) · b. Como por
hipo´tese de induc¸a˜o, (a− b) | (an− bn) e (a− b) | (a− b), temos, por D3, que (a− b) | (an+1− bn+1).
Portanto, se P (n) for verdadeira para algum n enta˜o P (n + 1) tambe´m e´ verdadeira. Logo,
P (n) e´ verdadeira para qualquer n ≥ 1.
25
No caso n = 2 podemos usar a diferenc¸a de quadrados e nem necessitamos fazer a divisa˜o;
f(x) = x2 − b2 = (x − b) · (x + b). Para n = 4 tambe´m, f(x) = x4 − b4 = (x2 − b2) · (x2 + b2) =
(x+b) · [(x−b) · (x2+b2)]. Note que nos dois casos acima o fator (x+b) esta´ presente; isso acontece
em geral. Se o polinoˆmio f(x) = xn − bn, acima, tiver grau par, enta˜o −b tambe´m e´ raiz de f(x),
logo, f(x) e´ divis´ıvel por (x − (−b)) = (x + b). Desse modo, existe um polinoˆmio h(x) tal que
f(x) = (x+ b) · h(x). Calculando h(x) obtemos,
f(x) = xn− bn = (x+ b) · (xn−1− b ·xn−2+ b2 ·xn−3+ · · ·+(−1)kbkxn−(k+1)+ · · ·+ bn−2 ·x− bn−1).
Novamente tomando x = a ∈ N, com b ≤ a obtemos an− bn = (a+ b) · h(a). Agora os coeficientes
de h(x) na˜o sa˜o todos nu´meros naturais, mas, apesar disso, ainda temos que h(a) ∈ N. De fato,
h(a) = (an−1 − b · an−2) + (b2 · an−3 − b3 · an−4) + · · ·+ (bn−2 · a− bn−1)
= (a− b) · (an−2 + b2 · an−4 + · · ·+ bn−2).
Como a − b ∈ N∗, ja´ que b < a, vemos que h(a) ∈ N∗, pois pode ser obtido multiplicando e
somando elementos (a− b), an−2, an−4, . . . , 1, b2, b4, . . . , bn−2, todos eles pertencentes a N∗.
Como no caso do resultado anterior, este u´ltimo tambe´m pode ser provado por induc¸a˜o (Exer-
c´ıcio). Vejamos uma terceira maneira de provar esse resultado.
Proposic¸a˜o 2.1.5. Sejam a, b, n ∈ N∗ tais que b ≤ a. Enta˜o (a+ b) | (a2n − b2n).
Demonstrac¸a˜o. Pela Proposic¸a˜o 2.1.4, (a2 − b2) | ((a2)n − (b2)n), ou seja, (a2 − b2) | (a2n − b2n).
Mas (a + b) | (a2 − b2), pois a2 − b2 = (a + b)(a − b). Logo, pela propriedade D2 (transitiva) da
Proposic¸a˜o 2.1.3, temos que (a+ b) | (a2n − b2n).
Um fato similar ocorre quando tomamos q(x) = x2n+1+b2n+1 para b, n ∈ N, −b e´ raiz de q(x) ja´
que q(−b) = (−b)2n+1+b2n+1 = −b2n+1+b2n+1 = 0. Logo, q(x) e´ divis´ıvel por (x−(−b)) = (x+b).
Desse modo, existe um polinoˆmio r(x) tal que q(x) = (x+ b) · r(x). Calculando r(x) obtemos,
q(x) = x2n+1+b2n+1 = (x+b) ·(x2n−b ·x2n−1+b2 ·x2n−2+ · · ·+(−1)kbkx2n−k+ · · ·−b2n−1 ·x+b2n).
Novamente tomando x = a ∈ N, obtemos a2n+1 + b2n+1 = (a + b) · r(a). Do mesmo modo que
na proposic¸a˜o anterior, os coeficientes de r(x) na˜o sa˜o todos nu´meros naturais, mas apesar disso
temos que r(a) ∈ N. Como no caso anterior, isso pode ser justificado de duas maneiras diferentes,
diretamente ou por induc¸a˜o. Para uma justificativa direta, podemos dividir em casos, conforme
a ≥ b ou a ≤ b. Por exemplo, se a ≤ b, enta˜o
r(a) = a2n + (b2 · a2n−2 − b · a2n−1) + (b4 · a2n−4 − b3 · a2n−3) + · · ·+ (b2n − b2n−1 · a)
= a2n + (b− a) · (b · a2n−2 + b3 · a2n−4 + · · ·+ b2n−1)
podemos concluir que r(a) ∈ N. No caso em que a ≥ b, por um procedimento ana´logo, obtemos
r(a) = (a− b) · (a2n−1 + b2 · a2n−3 + · · ·+ b2n−2 · a)+ b2n
e conclu´ımos da mesma forma que r(a) ∈ N.
Vejamos agora a justificativa por induc¸a˜o.
Proposic¸a˜o 2.1.6. Sejam a, b, n ∈ N tais que a+ b 6= 0. Enta˜o (a+ b) | (a2n+1 + b2n+1).
26
Demonstrac¸a˜o. Vamos provar por induc¸a˜o que para todo n ∈ N vale a propriedade
P (n) : (a+ b) | (a2n+1 + b2n+1) ∀ a, b ∈ N, com a+ b 6= 0.
Base de Induc¸a˜o: Verificar que vale P (0). E´ claro que (a+ b) | (a1 + b1) = (a+ b).
Passagem de Induc¸a˜o: Suponhamos que, para algum n, P (n) seja verdadeira.
Vamos mostrar que P (n+ 1) tambe´m e´ verdadeira, ou seja, que
(a+ b) | (a2(n+1)+1 + b2(n+1)+1) ∀ a, b ∈ N, com a+ b 6= 0.
De fato, sem perda de generalidade (spg), podemos supor que b ≤ a. Enta˜o
a2(n+1)+1+b2(n+1)+1 = a2 ·a2n+1−b2 ·a2n+1+b2 ·a2n+1+b2 ·b2n+1 = (a2−b2)·a2n+1+(a2n+1+b2n+1)·b2.
Pela hipo´tese de induc¸a˜o, temos que (a+ b) | (a2n+1 + b2n+1) e a proposic¸a˜o anterior garante que
(a+ b) | (a2 − b2), logo, por D3, (a+ b) | (a2(n+1)+1 + b2(n+1)+1).
Note que se a < b, somamos a2 · b2n+1 − a2 · b2n+1 a a2(n+1)+1 + b2(n+1)+1 e obtemos
a2(n+1)+1+b2(n+1)+1 = a2 ·a2n+1+a2 ·b2n+1−a2 ·b2n+1+b2 ·b2n+1 = a2 ·(a2n+1+b2n+1)+b2n+1 ·(b2−a2).
Do mesmo modo obtemos P (n+ 1).
Portanto, se P (n) for verdadeira para algum n enta˜o P (n + 1) tambe´m e´ verdadeira. Logo,
P (n) e´ verdadeira para qualquer n ∈ N.
De posse das treˆs proposic¸o˜es acima podemos determinar divisores de certos nu´meros grandes
de maneira fa´cil.
Exemplo 2.1.7. Como 44− 27 = 17 e 44 + 27 = 71, temos
17 | (4419 − 2719) e 71 | (4419 + 2719)
17 | (4422 − 2722) e 71 | (4422 − 2722)
Note que esses nu´meros sa˜o muito grandes,
4419 − 2719 = 16809712730159890806101837810141
4419 + 2719 = 16812852815958054969325118879267
4422 − 2722 = 1432021408585872913854623018673462007
4422 + 2722 = 1432083214894638179079346859957069065
2.2 Divisa˜o Euclidiana
2.2.1 A segunda forma do Princ´ıpio de Induc¸a˜o
Dada uma proposic¸a˜o P (n) envolvendo nu´meros naturais nem sempre e´ fa´cil, ou ate´ poss´ıvel,
demonstrar que P (n) =⇒ P (n + 1), muitas vezes necessitamos mais informac¸o˜es. A segunda
forma do princ´ıpio de induc¸a˜o garante que podemos usar todos os P (i) anteriores a P (n+ 1).
Teorema 2.2.1. (Segunda forma do Princ´ıpio de Induc¸a˜o) Sejam P (n) uma proposic¸a˜o
envolvendo um nu´mero natural n e a ∈ N. Se
(i) P (a) e´ verdadeira;
(ii) P (a) e P (a+ 1) e . . . e P (n) =⇒ P (n+ 1)
27
enta˜o P (n) e´ verdadeira ∀n ≥ a.
Demonstrac¸a˜o. Suponhamos que as condic¸o˜es (i) e (ii) sa˜o verdadeiras. Tomamos o conjunto
A = {t ∈ N | P (a + t) e´ falsa}. Se A 6= ∅ , enta˜o, pelo Princ´ıpio da Boa Ordenac¸a˜o, existe
m ∈ N∗ tal que m = minA. Note que m 6= 0, ja´ que P (a) e´ verdadeira. Assim, se n < m, enta˜o
n 6∈ A e, consequentemente, P (a+n) e´ verdadeira. Desse modo, P (a) e P (a+1) e . . . P (a+m−1)
sa˜o verdadeiras e por (ii) isso implica que P (m) e´ verdadeira. Contradic¸a˜o. Assim, A = ∅.
O exemplo a seguir sera´ revisitado quando estudarmos equac¸o˜es diofantinas.
Exemplo 2.2.2. (Problema de Postagem) Qualquer valor de postagem maior ou igual a 12
reais pode ser formado utilizando exclusivamente selos de 4 e 5 reais. Ou seja,
(∀n ∈ N) n ≥ 12 =⇒ (∃ k, l ∈ N) t.q. n = 4 · k + 5 · l.
Demonstrac¸a˜o. Utilizando a Segunda Forma do Princ´ıpio de Induc¸a˜o, vamos provar que para todo
n ≥ 12 vale a propriedade
P (n) : (∃ k, l ∈ N) n = 4 · k + 5 · l.
Base de Induc¸a˜o: Verificar que vale P (12).
De fato, 12 = 3 · 4 + 0 · 5 .
Passagem de Induc¸a˜o: Suponhamos que, para algum n, P (i) e´ verdadeira para cada i com
12 ≤ i ≤ n. Vamos mostrar que P (n+ 1) tambe´m e´ verdadeira.
Se n = 12, P (12 + 1), ou seja, P (13) e´ verdadeira, pois 13 = 2 · 4 + 1 · 5.
Se n = 13, P (14) e´ verdadeira, pois 14 = 1 · 4 + 2 · 5.
Se n = 14, P (15) e´ verdadeira, pois 15 = 0 · 4 + 3 · 5.
Se n ≥ 15, notamos que n+ 1 = (n− 3) + 4, e assim utilizamos os selos da postagem de n− 3
mais um selo de 4 reais. Note que 12 ≤ n − 3 ≤ n. Portanto, se P (i) for verdadeira para cada i
com 12 ≤ i ≤ n, enta˜o P (n − 3) e´ verdadeira, e conclu´ımos que P (n + 1) tambe´m e´ verdadeira.
Logo, P (n) e´ verdadeira para qualquer n ≥ 12.
O pro´ximo exemplo usa a sequeˆncia de Fibonacci.
Exemplo 2.2.3. Sejam Fn a sequeˆncia de Fibonacci definida por
F0 = 0, F1 = 1 e Fk = Fk−1 + Fk−2, para k ≥ 2.
e α =
1 +
√
5
2
o nu´mero de ouro, ou seja, a soluc¸a˜o positiva da equac¸a˜o x2 − x− 1 = 0 . Enta˜o,
(∀n ≥ 3) Fn > αn−2 .
Antes de iniciarmos a prova desta proposic¸a˜o fazemos duas observac¸o˜es.
(1) Como 2 <
√
5 < 3, temos que 3 < 1 +
√
5 < 4 e assim
3
2
<
1 +
√
5
2
<
4
2
; ou seja, α < 2.
(2) Como α e´ raiz de x2 − x− 1 = 0, temos que α2 − α− 1 = 0, e assim α2 = α+ 1.
Demonstrac¸a˜o. Vamos provar por induc¸a˜o que, para todo n ≥ 3, vale a propriedade
P(n) : Fn > α
n−2.
Base de Induc¸a˜o: Verificar que vale P (3). De fato, F3 = F2+F1 = 1+1 = 2 e α
3−2 = α. Logo,
pela observac¸a˜o (1), F3 > α.
28
Passagem de Induc¸a˜o: Suponhamos que, para algum n, P (i) e´ verdadeira para cada 3 ≤ i ≤ n.
Vamos mostrar que P (n+ 1) tambe´m e´ verdadeira, ou seja, Fn+1 > α
(n+1)−2 = αn−1.
De fato, pela definic¸a˜o da sequeˆncia de Fibonacci, temos que Fn+1 = Fn + Fn−1. Como P (n) e
P (n− 1) sa˜o verdadeiras pela hipo´tese de induc¸a˜o, temos
Fn+1 = Fn + Fn−1 > αn−2 + α(n−1)−2 = αn−2 + αn−3 = αn−3 · (α + 1) = αn−3 · α2 = αn−1,
onde a penu´ltima igualdade e´ va´lida pela observac¸a˜o (2). Portanto, se P (i) for verdadeira para
cada 3 ≤ i ≤ n, enta˜o P (n + 1) tambe´m e´ verdadeira. Logo, P (n) e´ verdadeira para qualquer
n ≥ 3.
2.2.2 O Algoritmo da Divisa˜o (de Euclides)
Sejam n, d ∈ N com d 6= 0. Se n na˜o e´ um mu´ltiplo de d, ou seja, se d - n, podemos nos perguntar
dentre os mu´ltiplos de d qual chega mais perto de n. A verdade e´ que sempre poderemos colocar
n entre dois mu´ltiplos consecutivos (muito bem escolhidos e determinados) de d.
Teorema 2.2.4. (Algoritmo da Divisa˜o) Sejam n, d ∈ N com d 6= 0. Enta˜o, existem e sa˜o
u´nicos q, r ∈ N tais que
n = q · d+ r, com r < d.
Demonstrac¸a˜o. O teorema conte´m duas afirmac¸o˜es independentes, a existeˆncia e a unicidade dos
nu´meros q e r. Vamos provar esses dois fatos separadamente.
Existeˆncia: Fixemos d ∈ N∗. Vamos mostrar que para qualquer n ∈ N vale
P (n) : ∃ q, r ∈ N t.q. n = q · d+ r e r < d.
Para isto, vamos utilizar a Segunda Forma do Princ´ıpio da Induc¸a˜o.
Base de Induc¸a˜o: P (0) e´ verdadeira.
De fato, se n = 0, tomamos q = 0 e r = 0.
Passagem de Induc¸a˜o: Suponhamos que, para algum n ∈ N, P (i) e´ verdadeira para todo i ≤ n.
Vamos mostrar que P (n+ 1) tambe´m e´ verdadeira.
Dividimos em dois casos.
Se n+ 1 < d, tomamos q = 0 e r = n+ 1.
Se n + 1 ≥ d, enta˜o o elemento (n + 1 − d) ∈ N esta´ bem definido e satisfaz n + 1 − d ≤ n.
Enta˜o, pela hipo´tese de induc¸a˜o, existem q′, r′ ∈ N tais que n+ 1− d = q′ · d+ r′ e r′ < d. Segue
que
n+ 1 = d+ q′ · d+ r′ = (q′ + 1) · d+ r′.
Enta˜o, definindo q = q′ + 1 e r′ = r, temos que existem q, r ∈ N tais que n+ 1 = q · d+ r e
r < d, ou seja, P (n+ 1) tambe´m e´ verdadeira.
Logo, P (n) e´ verdadeira para todo n ∈ N. Desse modo a existeˆncia esta´ demonstrada. Passemos
agora a` prova da unicidade.
Unicidade: Sejam q1, q2, r1, r2 ∈ N tais que n = q1 · d+ r1 , n = q2 · d+ r2 , r1 < d e r2 < d.
Precisamos mostrar que r1 = r2 e q1 = q2.
Sem perda de generalidade, podemos supor que r1 ≤ r2 (temos um par de restos, reservamos
o s´ımbolo r1 para o menor dos dois). Assim, esta´ bem definido r2 − r1 ∈ N. Da igualdade
q1 · d + r1 = n = q2 · d + r2 e da definic¸a˜o de subtrac¸a˜o, temos q1 · d = q2 · d + (r2 − r1). Como
d | q1 · d, temos que d divide a soma d |
(
q2 · d + (r2 − r1)
)
e d divide a parcela d | q2 · d. Logo,
pela propriedade D5, d | (r2 − r1). Mas r2 − r1 ≤ r2 < d. Se r2 − r1 fosse diferente de 0, enta˜o
d ≤ r2 − r1, o que contradiz que r2 − r1 < d. Logo, r2 − r1 = 0, isto e´, r1 = r2.
29
Segue que q1d = q2d. Como d 6= 0, pela lei do cancelamento, conclu´ımos que q1 = q2.
Os nu´meros q e r do teorema anterior sa˜o chamados, respectivamente, de quociente e resto da
divisa˜o de n por d.
Corola´rio 2.2.5. Sejam a, b ∈ N tais que 1 ≤ a ≤ b. Enta˜o existe n ∈ N tal que n·a ≤ b < (n+1)·a.
Demonstrac¸a˜o. Pelo Teorema 2.2.4 acima, existem e sa˜o u´nicos os nu´meros q e r ∈ N tais que
b = q · a + r com r < a. Tomamos q = n e obtemos, b = n · a + r; como r < a, temos
b = n · a+ r < n · a+ a = (n+1) · a. Por outro lado, n · a ≤ n · a+ r = b. Assim, n · a ≤ n · a+ r =
b < n · a+ a = (n+ 1) · a.
O Algoritmo da Divisa˜o e´ um dos resultados mais ba´sicos e importantes da Aritme´tica. A
seguir, veremos alguns exemplos, com o objetivo de dar uma ideia de sua utilidade.
Exemplo 2.2.6. Vamos determinar o quociente e o resto da divisa˜o de 53 por 7. Calculando os
mu´ltiplos de 7, vemos que 49 = 7 · 7 < 53 < 7 · 8 = 56. Logo, r = 53 − 7 · 7 = 53 − 49 = 4 < 7 e
q = 7.
A ideia em geral e´ a mesma. Quando dividimos n por d, determinamos o menor m ∈ N tal que
md > n e o quociente q sera´ o antecessor desse m. O resto e´ obtido calculando r = n− q · d. Isso
legitima o algoritmo conhecido.
53 | 7
−49 7
4
Exemplo 2.2.7. Vamos agora dividir 533 por 7. Pelo algoritmo usual temos,
533 | 7
−49 76
43
−42
1
Na primeira etapa do algoritmo, o 7 do quociente e´ o algarismo das dezenas do quociente
procurado. Pelo exemplo anterior 53 = 7 · 7 + 4, multiplicando por 10 temos 530 = 70 · 7 + 40,
somando 3 finalizamos com 533 = 70 · 7+43. Utilizando o teorema para dividir 43 por 7 obtemos,
43 = 6 · 7 + 1.
Substituindo na u´ltima equac¸a˜o, temos 533 = 70 · 7 + 43 = 70 · 7 + 6 · 7 + 1 = 76 · 7 + 1.
Exemplo 2.2.8. Na coluna da esquerda abaixo, esta´ mostrado um ca´lculo, como se costuma fazer
2
−1 1 9
1 2 1
−8 5
8 6
−6 8
7 6
−5 1
5 8 6 6 2 1 1 7
3 4 5 0 7
58 = 3 · 17 + 7
76 = 4 · 17 + 8
86 = 5 · 17 + 1
12 = 0 · 17 + 12
121 = 7 · 17 + 2
580000− 70000 = 30000 · 17
76000− 8000 = 4000 · 17
8600− 100 = 500 · 17
120− 120 = 00 · 17
121− 2 = 7 · 17
»»»
»
¡ »»
»»
¡ »»»
¡ »
»»
¡¡
utilizando o algoritmo usual. Na coluna do meio esta˜o mostrados os ca´lculos que foram feitos na
coluna da esquerda. Finalmante, na coluna da direita, o resto foi subtra´ıdo de ambos os lados e
as igualdades foram multiplicadas por poteˆncias convenientes de 10.
30
Somando as igualdades da u´ltima coluna, os cancelamentos indicados surgem naturalmente e
obtemos
580000 + 6000 + 600 + 20 + 1− 2 = 30000 · 17 + 4000 · 17 + 500 · 17 + 7 · 17
e, portanto,
586621 = 34507 · 17 + 2 .
Exemplo 2.2.9. Quando dividimos um nu´mero natural n por d = 2, temos apenas duas possibi-
lidades para o resto r, r = 0 ou r = 1, pois r < 2 = d.
Se r = 0 enta˜o n = 2 · k para algum k ∈ N, neste caso dizemos que n e´ par.
Se r = 1 enta˜o n = 2 · t+ 1 para algum t ∈ N, neste caso dizemos que n e´ ı´mpar.
Assim podemos dividir o conjunto dos nu´meros naturais em dois subconjuntos disjuntos, o
conjunto dos nu´meros pares e o conjunto dos nu´meros ı´mpares.
A classificac¸a˜o feita no exemplo acima pode ser generalizada, faremos isso com mais detalhes
no cap´ıtulo dos nu´meros inteiros; entretanto ilustramos ainda os casos d = 3 e d = 4.
Exemplo 2.2.10. Quando dividimos um nu´mero natural n por d = 3 temos treˆs possibilidades
para o resto r, r = 0 ou r = 1 ou r = 2. Assim, n pode ser escrito de uma e somente uma da
seguintes formas, n = 3 · k ou n = 3 · k + 1 ou n = 3 · k + 2. Assim, de maneira semelhante
a` classificac¸a˜o dos nu´meros naturais em pares e ı´mpares, podemos classifica´-los (na˜o existe uma
nomenclatura especial, neste caso) como pertencentes a um e apenas um dos subconjuntos da
decomposic¸a˜o
N = {0, 3, 6, 9, . . .} ∪ {1, 4, 7, 10, . . .} ∪ {2, 5, 8, 11, . . .}.
Analogamente, considerando o resto na divisa˜o por 4, qualquer nu´mero natural n pode ser escrito
de uma e somente uma das formas, n = 4 · k ou n = 4 · k + 1 ou n = 4 · k + 2 ou n = 4 · k + 3.
Como uma aplicac¸a˜o interessante dessa classificac¸a˜o, vamos provar a propriedade seguinte.
Propriedade. ∀n ∈ N, 3 | n(n + 1)(n + 2). Em outras palavras, o produto de treˆs nu´meros
naturais consecutivos e´ sempre um mu´ltiplo de 3.
Demonstrac¸a˜o. Para provar, dividimos em treˆs casos.
Caso 1 : Se n e´ da forma n = 3k. Enta˜o,
n(n+ 1)(n+ 2) = 3k(n+ 1)(n+ 2).
Segue que ∃ c = k(n+ 1)(n+ 2) ∈ N tal que n(n+ 1)(n+ 2) = 3c. Logo, 3 | n(n+ 1)(n+ 2).
Caso 2 : Se n e´ da forma n = 3k + 1. Enta˜o, n+ 2 = 3k + 1 + 2 = 3(k + 1) e, portanto,
n(n+ 1)(n+ 2) = 3n(n+ 1)(k + 1).
Logo, temos, tambe´m neste caso, que 3 | n(n+ 1)(n+ 2).
Caso 3 : Se n e´ da forma n = 3k + 2. Enta˜o, n+ 1 = 3k + 2 + 1 = 3(k + 1) e, portanto,