quarta-feira, 28 de dezembro de 2011

O Algoritmo da Divisão Parte III


Nesta série de postagens estamos demonstrando 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 demonstramos a existência de $q$ e $r$, na segunda demonstramos a dupla desigualdade $0 \leq r < b$ e nesta, que é a terceira, vamos mostrar que $q$ e $r$, satisfazendo as  condições do enunciado acima, são únicos (em outros termos: vamos demonstrar a unicidade de $q$ e $r$).

Para cumprir nosso propósito vamos precisar de um "resultado preliminar" que enunciamos abaixo, mas antes lembremos que dizer que "o inteiro $d$ é divisível pelo inteiro $c$" significa que "existe um inteiro $t$ tal que $d = ct$" (isto entre aspas é uma definição. Exemplo: o número $20$ é divisível por $5$, pois existe um inteiro $t$ tal que $20 = 5t$. Neste caso temos $t = 4$).

Resultado preliminar: Se $d$ é um inteiro diferente de zero divisível por $c$, então a diferença $|d| - |c|$ nunca é negativa (note que isto equivale a dizer que todo inteiro não nulo é "maior do que" ou "igual a" seu divisor; em símbolos $|d| \geq |c|$) Exemplos: $-20$ é um número inteiro diferente de zero divisível por $10$. É fácil ver que a diferença $|-20| - |10|$ é positiva (e, portanto, não negativa); $8$ é divisível por $8$ e também é óbvio que $|8| - |8|$ não é negativa (pois é nula).

Observação: apesar de ser, em certo sentido, intuitivo, o "resultado preliminar" é uma proposição demonstrável: se $d$ é divisível por $c$, então (por definição) existe um inteiro $t$ tal que $d = ct$. Segue desta última igualdade que
$$|d| = |ct| = |c|\cdot|t| = |c|\cdot|t| + 0 = |c|\cdot|t| + |c| - |c| = |c| + |c|\cdot(|t| - 1)$$Assim, concluímos que $|d| = |c| + |c|\cdot(|t| - 1)$ e, por conseguinte, $|d| - |c| = |c|\cdot(|t| - 1)$. Agora nosso trabalho se reduz em mostrar que o número $|c|\cdot(|t| - 1)$ nunca é negativo. Ora, para ser negativo deveríamos ter $(|t| - 1) < 0$ (pois $|c|$ é positivo e para um produto ser negativo um, e apenas um, de seus fatores tem que ser negativo). Mas, se $(|t| - 1) < 0$, então tem que valer $|t| < 1$Observe que $|t|$ não pode ser negativo (pela própria definição de valor absoluto) e ao mesmo tempo é um inteiro menor do que um. O único inteiro menor do que $1$ que existe é o zero, assim tem que ser $|t| = 0$, por isso, $t = 0$, donde segue que $d = 0$ (pois $d = ct$). Mas isto é um absurdo, pois $d$ foi suposto diferente de zero. Resumindo: se a diferença $|d| - |c|$ é negativa, então $d = 0$ - o que não pode ocorrer - logo, a diferença não é negativa e o resultado está demonstrado.

Dito isto, vamos para a prova da unicidade. Começamos supondo que existam $r'$ e $q'$ tais que $a = bq' + r'$ com $0 \leq r' < b$. Vamos concluir, a partir desta suposição, que $r' = r$ e $q' = q$.

Como $0 \leq r < b$, obtém-se (multiplicando tudo por $-1$$-b < -r \leq 0$. Temos, então, quatro desigualdades:
$$\begin{aligned}
0&\leq r'\qquad &r'<b\\
-b&< -r'\qquad &-r'\leq 0\end{aligned}$$
Somando os termos das desigualdades obtemos:
$$0 - b < r' - r,\qquad r' - r < b + 0$$
Da primeira e da segunda desigualdade tiramos, respectivamente, $-(r'- r) < b$ e $r' - r < b$ , o que pode ser escrito como $|r'- r| < b$. Note que como $|r' - r|$ é não negativo, qualquer número maior do que ele também é não negativo. Concluímos, assim, que $b$ é positivo e, portanto (em virtude da definição de valor absoluto), que $|b| = b$. Sendo assim, nossa conclusão é que $|r' – r| < |b|$.

Agora, como $a = bq + r$ e $a = bq' + r'$ concluímos que $bq' + r' = bq + r$. Manipulando algebricamente esta última igualdade, podemos chegar ao ponto de escrevê-la do seguinte modo:
$$r'- r = b(q - q')$$
Da igualdade acima concluímos que a diferença $r' - r$ é divisível por $b$ (pois existe um inteiro $t$ que quando multiplicado por $b$ resulta em $r' – r$. Neste caso $t = q - q'$). Deste modo (em virtude do que nos diz o "resultado preliminar") se $r' - r$ for diferente de zero, então a diferença $|r' - r| - |b|$ será não negativa, ou seja, teremos $|r' - r| - |b| \geq 0$, donde segue que $|r' - r| \geq |b|$. Mas esta última desigualdade é um absurdo (pois já vimos que $|r' - r| < |b|$). Como o absurdo decorre da hipótese de $r' - r$ ser diferente de zero concluímos que ela deve ser falsa, isto é, tem que ser $r' - r = 0$. Segue-se disto duas coisas: em primeiro lugar $r' = r$ e, em segundo lugar, $q' = q$ (a primeira consequência é evidente, a segunda decorre do fato de ser $r' - r = b(q - q')$; com efeito, colocando $r' - r = 0$ nesta última igualdade vem $b(q - q') = 0$. Uma vez que se um produto é nulo um de seus fatores é, necessariamente, nulo e levando em conta que $b$ não pode ser nulo (pois, por hipótese, é positivo) segue-se $q - q' = 0$ e, por conseguinte, $q' = q$).

Observação: as demonstrações acima fazem uso de diversas propriedades dos conceitos de valor absoluto (ou módulo) e da relação de ordem $<$. Nesta exposição, supomos tudo isso conhecido, mas esperamos ter oportunidade futura de tratar sobre isso, aqui no BLOG MANTHANO.

Note que o algoritmo do modo como foi enunciado supõe $b > 0$. Na próxima postagem da série ele será generalizado, mostrando-se que as mesmas conclusões valem nos casos em que $b$ é negativo.

Referências: na última postagem da série.
Erros podem ser relatados aqui.

Nenhum comentário :

Postar um comentário

Atualizações dos nossos parceiros: