O Algoritmo da Divisão Parte II

Nesta série de postagens estamos nos dedicando a demonstrar o

Algoritmo da Divisão: Se $a$ é um número inteiro qualquer e $b$ é um número inteiro maior do que zero, então existem dois números inteiros $q$ e $r$ tais que $a = bq + r$, onde $0 \leq r < b$. Além disso, $q$ e $r$ são únicos.

Na primeira postagem da série demonstramos a existência dos inteiros $q$ e $r$ tais que $a = bq + r$ (utilizamos, para tanto, o princípio da boa ordenação - o que, evidentemente, justifica o nome alternativo daquela postagem).

Na postagem de hoje vamos mostrar que $0 \leq r < b$. Isto faremos em duas etapas: em primeiro lugar, vamos mostrar que $0 \leq r$ e, em segundo lugar, que $r < b$.

Na demonstração de ambas as desigualdades, ainda vamos utilizar o conjunto

$$S = \{y;\; y = a - bx\text{ com } x \in\mathbb{Z}\text{ e } y ≥ 0\}$$

definido na primeira parte da demonstração. Além disso, continuaremos a chamar o menor elemento deste conjunto de $r$ e continuaremos a escrever $r = a - bq$ (isto significa que a argumentação seguinte é uma continuação da argumentação lá apresentada - por isso recomendamos o leitor ler aquela antes desta).

Observamos, ainda, que para demonstrar a segunda desigualdade acima mencionada vamos utilizar a técnica de demonstração conhecida como "redução ao absurdo" que, grosso modo, consiste em (1) supor que a conclusão a que se quer chegar seja falsa, (2) deduzir, por meio de procedimentos matemáticos legítimos, uma contradição e (3) concluir que a suposição feita é verdadeira (ou seja, que a conclusão pretendida não é falsa, pois não pode haver contradições na matemática).

Vamos, então, à demonstração:

Como $r$ pertence a $S$, tem-se imediatamente $r \geq 0$ ou, equivalentemente, $0 \leq r$ (pois o conjunto $S$, em virtude de sua própria definição, só contém números não negativos).

Agora, supõe por absurdo que $r \geq b$.

Segue-se desta suposição que $r - b \geq 0$. Uma vez que $r = a - bq$ obtém-se $$r - b = a - bq - b = a - b(q + 1)$$

Assim, o número $a - b(q + 1)$ pertence a $S$ (de fato: o número $a - b(q + 1)$ é positivo (pois é igual a $r - b$ que é positivo) e além disso "se encaixa" na definição de $S$ - basta colocar $x=q + 1$).

Observe agora que $r - b$ é menor do que $r$. De fato, uma vez que $b > 0$ (em virtude do enunciado da proposição) obtém-se $-b < 0$ (bastar somar $-b$ a ambos os lados da desigualdade) donde segue (desta vez somando $r$ a ambos lados) que $-b + r < 0 + r$ ou, equivalentemente, que $r - b < r$.

Mas se $r - b$ é menor do que $r$ então $S$ contém um elemento menor do que $r$ (pois $a - b(q + 1) = r - b$). Isto é um absurdo, pois $r$ é o menor elemento de $S$! Obtemos, assim, uma contradição que resulta da hipótese de ser $r \geq b$, logo tem que ser $r < b$.

Resumindo: se $r \geq b$, então $S$ possui um elemento menor do que o seu menor elemento - o que não pode acontecer (pois é uma contradição). Como esta implicação é matematicamente válida (pois nenhuma regra foi violada), o elo fraco da argumentação deve ser a hipótese $r \geq b$. Concluímos, assim, que não vale $r \geq b$ e que, portanto, $r < b$ é, de fato, verdadeiro.

Ficou, assim, demonstrado que $0 \leq r$ e que $r < b$ ou, equivalentemente, que $0 \leq r < b$.

Na próxima postagem da série mostramos que $q$ e $r$ são únicos.

Observação: Dados quaisquer dois números $b$ e $r$, só existem três possibilidades, as quais se excluem mutuamente (o que significa que apenas uma delas ocorre): (i) $b = r$, (ii) $b < r$ e (iii) $r < b$. Foi por isso que, na demonstração acima, quando afirmamos que por não valer nem (i) e nem (ii) (isto é, não valer $r \geq b$) deveria valer (iii). Esta propriedade é conhecida como tricotomia.

Referências: na última postagem da série.

Erros podem ser relatados aqui.