Teorema da Divisao de Euclides

Enuncie e prove o Teorema da Divisao de Euclides usando o :bounce: Principio
da Boa Ordem ao inves de usar o Teorema de Inducao

Demonstração retirada deste wikibook. O teorema ou algoritmo de divisão de Euclides diz que, se a e b são inteiros, com b diferente de zero, então existe um único par de inteiros q, r tal que a = bq + r, com 0 <= r < |b|.

Considere inicialmente que a > 0. Se , então (pois para t = 0 tem-se a - bt = a >0).

Logo, pelo princípio da boa ordenação, X' possui um menor elemento r = min (X'). Como r pertence a X', segue que r = a - bq, para algum inteiro q, e r >= 0.

Suponha que b > 0. Neste caso, segue que r < b. De fato, se ocorresse r >= b, então r' = r - b = (a - bq) - b = a - b(q + 1) seria elemento de X'. Além disso, 0 <= r' e r' < r (pois 0 < b), donde r não seria o menor elemento de X'.

Por outro lado, se b <= 0, então o algoritmo pode ser aplicado a a e -b (que não é negativo), obtendo:

a = (-b)q + r = b(-q) + r, com 0 <= r < -b = |b|

Quanto à unicidade do quociente e do resto, pode-se proceder da seguinte maneira: Seja a = mq + r = mq' + r', com 0 <= r < m e 0 <= r' < m. Nestas condições, tem-se:

0 = m(q - q') + (r - r'), ou seja, .

Por outro lado, como o valor de cada resto está entre 0 e m, sua diferença também está. Isto significa que:



Logo, |r' - r| < m. Mas o único elemento de com módulo menor que m é o 0. Assim, r' - r = 0 implica r' = r.

Consequentemente, de mq + r = mq' + r' se conclui que mq = mq', que equivale a q = q', pois m é diferente de zero.