Enuncie e demonstre o Algoritmo da Divisão em Z.

Passo 1

O objetivo é enunciar e demonstrar o Algoritmo da Divisão em Z. Estamos na teoria dos números inteiros e vamos usar o princípio da boa ordenação de N. O teorema afirma que, dado um inteiro dividendo e um divisor positivo, existe e é único o quociente e o resto.

Passo 2

Demonstração da existência de quociente e resto.
Sejam ain Z e bin Z com b>0. Considere o conjunto
S = ,a - b k mid kin Z,;a - b k >= 0
Como podemos escolher k muito negativo, existe algum k tal que a - b k seja não negativo, logo Sneqemptyset. Pelo princípio da boa ordenação, Ssubseteq N tem menor elemento; chame-o de r. Então há qin Z com
r = a - b q Longrightarrow a = b q + r e r>= 0
Só falta mostrar que r<b. Se fosse r>= b, então
r - b = (a - b q) - b = a - b(q+1)>= 0
pertenceria a S, mas r-b<r, contradizendo a minimalidade de r. Logo necessariamente 0<= r<b.

Passo 3

Demonstração da unicidade de quociente e resto.
Suponha que existam (q1,r1) e (q2,r2) tais que
a = b q1 + r1, a = b q2 + r2, 0<= r1,r2<b
Subtraindo as igualdades:
0 = b(q1 - q2) + (r1 - r2) Longrightarrow b(q1 - q2) = r2 - r1
O lado direito satisfaz |r2 - r1|<b, mas b divide r2 - r1. A única possibilidade é r2 - r1=0, isto é, r1=r2. Daí b(q1 - q2)=0 e como b>0 segue q1=q2. Portanto (q,r) é único.

Resposta

Para quaisquer inteiros a e b com b>0, existem únicos inteiros q e r tais que
a = b,q + r e 0 <= r < b

Exercícios relacionados