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 e
inteiros com
. Então existem únicos inteiros
e
tais que
Sejam
e
Passo 3
Demonstração da existência.
Considere o conjunto
Considere o conjunto
Como
, ao escolhermos
suficientemente negativo temos
grande e positivo, logo
. Pelo Princípio do Bom Ordenamento,
tem um menor elemento; chame-o de
. Seja
o valor de
correspondente, isto é,
Falta mostrar
. Se fosse
, então
o que contradiz a minimalidade de
em
. Logo
. Assim, encontramos
e
satisfazendo as condições.
Passo 4
Demonstração da unicidade.
Suponha que existam e
cumprindo
Suponha que existam
Subtraindo as duas expressões,
O lado esquerdo é múltiplo de
, logo
divide
. Mas
, pois ambos estão em
. A única maneira de um inteiro de valor absoluto menor que
ser múltiplo de
é ser zero. Logo
, isto é,
, e então
. Assim
é único.
Resposta
Sejam
e
inteiros com
. Então existem únicos inteiros
e
tais que