2_TeoremaDaDivisao

Prévia do material em texto

Prova do Teorema da Divisão
Carlos A. Prolo
DIMAp-UFRN
IMD0013 - Elementos de Matemática para Computação
Setembro, 2013
1 Teorema
Para todo par de inteiros a, b ∈ Z, com b > 0, existem inteiros únicos q, r, tal
que a = qb+ r e 0 ≤ r < b.
2 Prova
A prova está organizada em uma introdução e quatro partes. Primeiro assume-se
que a, b sejam dois inteiros quaisquer com b > 0 e mostra-se que existem infinitos
pares (q, r) que são soluções da equação a = qb + r. Depois mostra-se ainda
que há infinitos destes pares que adicionalmente satisfazem 0 ≤ r. Na terceira
parte mostra-se que uma destas soluções tem r < b, e por fim mostra-se que esta
solução é única. Esta prova poderia ter sido organizada como uma seqüência de
lemas. No entanto, as quatro partes acima não são exatamente estanques. Em
cada parte são introduzidos também elementos e caracterizações do problema
usados nas partes subsequentes e por isto optou-se por fazer uma única prova.
2.1 Introdução
Sejam a, b dois inteiros, com b > 0. A equação a = qb + r pode ser reescrita
como r = a− qb, que mostra que r é uma função linear em q (r(q) = a+(−b)q,
com coeficiente angular −b e termo independente a. Como b é positivo, como
expresso na premissa do teorema, o coeficiente linear −b é negativo, e r(q) é
uma função monotônica decrescente, como caracterizado na Figura 1.
2.2 Parte 1: Dados a, b ∈ Z com b > 0, existem infinitos
pares (q, r) que satisfazem, q, r ∈ Z ∧ a = qb+ r.
O gráfico da Figura 1 é um pouco enganoso porque os pontos são do domínio
dos reais - R × R. Mas no nosso caso são soluções apenas os pontos (q, r)
em que tanto q como r são inteiros. Percebe-se, no entanto, que, para cada
inteiro q ∈ Z, r = a − qb também é inteiro (pois a expressão contém apenas
multiplicação e subtração de inteiros). Portanto, para cada q ∈ Z, (q, a− qb) é
uma solução e existem infinitas soluções. (Note que o inverso não é verdadeiro:
nem todo valor de r corresponde a uma solução porque o correspondente q pode
não ser inteiro.) As soluções foram marcadas na Figura 1 com pequenos círculos
sólidos.
2.3 Parte 2: Existem infinitos pares (q, r) que satisfazem,
q, r ∈ Z ∧ a = qb+ r ∧ 0 ≤ r.
Para ver isto basta considerar os pontos do gráfico na região em que r é não
negativo. Formalmente basta resolver r = a − qb ≥ 0 sse a ≥ qb sse q ≤ a/b.
1
1 2 3 4 5
q
q = a div b = a/b 
3
8
13
18
r = a= 13
q= a/b=2.6
=2
com b>0
r(q) = a − qb 
==> 
Para a=13, b=5
r(q) = 13 − 5q
−2
r = a − qb
Figura 1: Gráfico de r em função de q: r(q) = a − qb. A função é linear, e
como b > 0, −b < 0 e a função tem a forma monotonia decrescente. O exemplo
ilustrado é para a = 13 e b = 5: r = 13− 5q (ou 13 = 5q + r).
(Cuidado, o último passo só vale porque na premissa do teorema temos b >
0.) Como q tem que ser inteiro, não necessariamente q = a/b é uma solução.
Podemos escrever, mais precisamente, que as infinitas soluções em que r é não
negativo são aquelas em que q ∈ Z e q ≤ ⌊a/b⌋. No exemplo da Figura 1, o
valor a/b de q quando a linha cruza o eixo das abscissas é 13/5 = 2.6. Todos os
pontos com q ≤ 2 tem r ≥ 0.
2.4 Parte 3: Existe uma solução (q, r) que satisfaz, q, r ∈
Z ∧ a = qb+ r ∧ 0 ≤ r < b.
O ponto aqui é mostrar que pelo menos uma das soluções da parte 2 satisfazem
r < b. Considere o conjunto dos r ≥ 0 tal que (q, r) é uma solução (conjunto
das infinitas soluções da parte 2, mas projetando apenas o r). S = {r | 0 ≤
r ∧ ∃q : r = a − qr}. Note que cada solução tem tanto valor de q como de r
diferente. Não pode haver mais de uma solução como o mesmo valor de q nem
de r, uma vez que a relação define r e q como funções um do outro (uma função
é a inversa da outra). Desta forma, Para cada r ∈ S também corresponde um
q dado pela inversa de r(q) : q(r) = (a− r)/b, que será obviamente inteiro para
os r em S por construção de S.
O conjunto S tem um menor elemento. Aqui precisamos fazer um comen-
tário importante. Nem todo o conjunto infinito ordenado linearmente tem um
menor elemento. Reflita e conclua que os seguintes conjuntos não tem elemento
mínimo: R,Z,Q,R+,Q+. Os dois últimos casos são interessantes e ligados à
característica de que na ordenação usual dos reais e racionais, entre quaisquer
dois números existem infinitos números. No entanto, qualquer subconjunto de
inteiros não negativos sempre tem um elemento mínimo. Isto é garantido pelo
Princípio da boa ordem dos inteiros.
Desta forma, seja rmin o menor elemento de S. Vamos provar que rmin < b
por contradição.
1. rmin é o menor elemento de S (definição).
2
2. Assuma que rmin ≥ b (hipótese a ser contrariada).
3. Seja (q, rmin) a solução correspondente a rmin.
4. rmin = a− qb
5. Considere a solução (q′, r′) para q′ = q + 1
6. r′ < rmin (porque q
′ > q e r(q) é monotônica decrescente)
7. r′ = a− q′b = a− (q + 1)b = a− qb− b = rmin − b.
8. Como rmin ≥ b, rmin − b ≥ b− b = 0, isto é, r
′ ≥ 0
9. Portanto r′ ∈ S,
10. Chegamos a uma contradição pois r′ está em S e é menor que rmin, e isto
contradiz o fato de que rmin é o menor elemento de S. A única hipótese
feita sem comprovação feita na linha da prova foi que rmin ≥ b. Isto,
portanto, é falso.
Provamos acima que rmin, o menor elemnto de S é menor do que b. Desta
forma, existe uma solução (q, r) tal que 0 ≤ r < b qual seja, aquela em que r é
o rmin.
2.5 Parte 4: A solução (q, rmin) da parte 3 é a única que
satisfaz, 0 ≤ r < b e q, r ∈ Z ∧ a = qb+ r.
Suponha que existam duas soluções distintas (q1, r1), (q2, r2) que satisfazem as
condições acima. Assuma, w.l.o.g. (without loss of generality, sem perda de
generalidade) que r1 = rmin.
1. r1 = a− q1b, 0 ≤ r1 < b
2. r2 = a− q2b, 0 ≤ r2 < b
3. r1, r2 ∈ S, porque ambos são não negativos
4. r2 > r1, porque r1 é o menor elemento de S
5. q2 < q1, pela característica monotônica decrescente da função r(q)
6. q2 ≤ q1 − 1, porque q1, q2 são inteiros
7. q2b ≤ (q1− 1)b = q1b− b, porque b é positivo, caso contrário o ≤ viraria ≥
8. −q2b ≥ −q1b+ b, multiplica os dois lados por −1
9. a− q2b ≥ a− q1b+ b, adiciona a dos dois lados.
10. r2 ≥ a− q1b+ b, segunda linha desta seqüência
11. r2 ≥ r1 + b substituindo da primeira linha
12. Como r1 ≥ 0, então, r2 ≥ r1 + b ≥ 0 + b, ou seja,
13. r2 ≥ b
14. A linha acima contradiz a linha 2. Ou seja, não existe uma segunda solução
com r < b, apenas uma, a de rmin.
3
3 Generalização do Teorema da Divisão
Para todo para de inteiros a, b ∈ Z, com b 6= 0, existem inteiros únicos q, r, tal
que a = qb+ r e 0 ≤ r < |b|. A prova fica como exercício. Basta considerar dois
casos. O caso de b > 0 foi feito acima. O caso de b < 0 pode ser feito adaptando
a prova acima para esta condição. Por exemplo, com b < 0 a relação entre q e r
passa a ser monotônica crescente, ao invés de decrescente. E possível também
derivar diretamente do teorema da divisão mostrado acima.
4