Questão 6.(2,00 pontos) Enuncie e demonstre o Algoritmo da Divisão.

Passo 1

O enunciado pede para “Enunciar e demonstrar o Algoritmo da Divisão”, que faz parte da Teoria dos Números. Vamos precisar usar o Princípio do Bom Ordenamento para inteiros não-negativos e argumentos de divisão para provar existência e unicidade do quociente e resto.

Passo 2

Enunciado do Algoritmo da Divisão:
Sejam a e b inteiros com b>0. Então existem únicos inteiros q e r tais que
a = b\,q + r
e
0 \le r < b.

Passo 3

Demonstração da existência.
Considere o conjunto
S = \{\,a - b\,k \mid k\in\mathbb{Z}\text{ e }a - b\,k \ge 0\}.
Como b>0, ao escolhermos k suficientemente negativo temos a - b\,k grande e positivo, logo S\neq\varnothing. Pelo Princípio do Bom Ordenamento, S tem um menor elemento; chame-o de r. Seja q o valor de k correspondente, isto é,
r = a - b\,q,\quad r\ge0.
Falta mostrar r<b. Se fosse r\ge b, então
r - b = a - b\,q - b = a - b\,(q+1)\ge0,
o que contradiz a minimalidade de r em S. Logo r<b. Assim, encontramos q e r satisfazendo as condições.

Passo 4

Demonstração da unicidade.
Suponha que existam (q,r) e (q',r') cumprindo
a = b\,q + r,\quad 0\le r<b,
a = b\,q' + r',\quad 0\le r'<b.
Subtraindo as duas expressões,
b\,(q - q') = r' - r.
O lado esquerdo é múltiplo de b, logo b divide r'-r. Mas |r'-r|<b, pois ambos estão em [0,b-1]. A única maneira de um inteiro de valor absoluto menor que b ser múltiplo de b é ser zero. Logo r'-r=0, isto é, r=r', e então q=q'. Assim (q,r) é único.

Resposta

Sejam a e b inteiros com b>0. Então existem únicos inteiros q e r tais que
a = b\,q + r \quad\text{e}\quad 0 \le r < b.

Exercícios relacionados