ELEMENTOS: 055-Cálculo de Resto, sem Dividir

Neste artigo, escrevi sobre aritmética modular de uma forma diferente daquelas que já publiquei, de forma que o leitor tenha uma segunda visão sobre o assunto.

Ao final do post, estaremos em condições de resolver as seguintes questões.

Um número é divisível por [;4;]

quando o número formado pelos seus dois últimos dígitos for divisível por [;4;]

. Mas qual o critério da divisibilidade por [;4;]

para um número de dois dígitos? E como calcular o resto de uma divisão por [;4;]

, sem dividir?

Um número é divisível por [;6;]

quando for divisível por [;2;]

ao mesmo tempo. Mas caso não seja, como calcular o resto de uma divisão por [;6;]

, sem dividir?

Um número é divisível por [;8;]

quando o número formado pelos seus três últimos dígitos for divisível por [;8;]

. Mas qual o critério da divisibilidade por [;8;]

para um número de três dígitos? E como calcular o resto de uma divisão por [;8;]

, sem dividir?

De modo geral, como se calcula o resto [;r;]

da divisão de um número [;a;]

por

, sem dividir?

Na aritmética modular, aplicável com as operações de adição algébrica ( $[;\pm;]$ ) e multiplicação, no conjunto $[;\mathbb{Z};]$ , os múltiplos inteiros de um número [;m>0;]

, chamado de módulo de congruência, funcionam como se fossem "zeros". Nesta aritmética, o equivalente do sinal de igualdade é $[;\equi_m;]$ , que significa "é congruente módulo à".

Portanto, dados [;a;]

e $[;z \in \left{...-2,-1,0,+1,+2,...\right};]$ , temos

$[;zm \equiv_m 0;]$

$[;a \pm zm \equiv_m a;]$

$[;a.zm \equiv_m 0;]$

Assim, neste modelo aritmético, qualquer inteiro pode ser reduzido à um dos elementos do conjunto

$[;R_m=\left{0,1,2,...,m-1 \right};]$

porque, pelo algoritmo de Euclides, qualquer número $[;a \geq 0;]$ pode ser representado por [;a=qm+r;]

, com $[;0 \leq r < m;]$ e, portanto, $[;a=qm+r \equiv_m r;]$ , com $[;r \in R_m;]$ .

Da mesma forma, pelo mesmo algoritmo, qualquer número [;a^'<0;]

pode ser representado por [;a^'=-(q^'m+r^');]

, com $[;0 \leq r^' <m;]$ . Logo, $[;-(q^'m+r^')=-q^'m-r^' \equiv_m -r^' \equiv_m m-r^' ;]$ , com $[;0<m-r^'\leq m;]$ , de forma que $[;m-r^' \equiv_m r'' \in R_m;]$ .

O conjunto [;R_m;]

é chamado de sistema completo de resíduos módulo [;m;]

Exs . Seja o módulo [;m=7;]

e $[;R_7=\left{0,1,2,3,4,5,6 \right};]$ . Logo,

$[;80=11.7+3 \equiv_7 3;]$ , com $[;3 \in R_7;]$ ;

$[;-121=-(7.17+2)=-7.17-2 \equiv_7 -2 \equiv_7 7-2 \equiv_7 5;]$ , com $[;5 \in R_7;]$ .

Quando dois números inteiros quaisquer têm a mesma representação módulo [;m;]

, então eles são considerados congruentes módulo [;m;]

Ex: Seja o módulo [;m=5;]

. Se digo que $[;14 \equiv_5 99;]$ é porque $[;14=2.5+4 \equiv_5 4;]$ e $[;99=5.19+4 \equiv_5 4;]$ , com $[;4 \in R_5=\left{0,1,2,3,4 \right};]$ .

$[;\rightarrow;]$ O resto [;r;]

da divisão de um número [;a;]

por

é a representação de [;a;]

Então, para calcular este resto, basta eliminar todos os múltiplos de [;m;]

contidos em [;a;]

. Assim, calcula-se o resto por intermédio de uma subtração simplificadora, e não por uma divisão.

Por exemplo, se quero saber o resto da divisão de [;73;]

por

, basta levar em conta que

$[;73 \equiv_6 13 \equi_6 2.6+1 \equi_6 1;]$

O que fizemos aqui, foi apenas substituir o [;7;]

por

, tendo em vista que $[;7=6+1 \equiv_6 1;]$ .

Este caso foi bastante simples pois apenas a redução de um dos dígitos ( [;7;]

) facilitou a operação. No entanto, já estamos em condições de, caso seja possível, realizar uma simplificação preliminar em um inteiro, módulo [;m;]

.

Ex: Tendo em vista que $[;9 \equiv_8 1;]$ e $[;8 \equiv_8 0;]$ , na divisão por [;8;]

, o número [;2983;]

deixa o mesmo resto que o número [;2103;]

( confira! ). Já com o número [;3557;]

, com o mesmo divisor [;8;]

, nada podemos simplificar.

De modo geral, temos que lidar com as congruências módulo [;m;]

das potências de [;10;]

, que formam sequências padronizadas.

Exercícios Resolvidos. Calcular o resto da divisão de:

)

por

$[;10=2.4+2 \equi_4 2;]$

$[;10^2=(2.4+2)(2.4+2) \equiv_4 2.2=4 \equiv_4 0;]$

Assim, para $[;i \geq 2;]$ , temos $[;10^i \equiv_4 0;]$ . Logo, na redução de um número módulo [;4;]

, só nos interessa os dois últimos dígitos.

$[;111455671 \equiv_4 71 \equiv_4 2.7+1 \equiv_4 2.3+1 \equiv_4 6+1 \equiv_4 2+1 \equiv_4 3;]$ (Resto [;3;]

)

$[;\rightarrow;]$ Um número é divisível por quando o último dígito somado com o dobro do penúltimo dígito resultar em um múltiplo de ( ou seja, zero, na aritmética módulo ).

)

por

$[;10=6+4 \equiv_6 4;]$

$[;10^2=(6+4)(6+4) \equiv_6 4.4 \equiv_6 16 \equiv_6 2.6+4 \equiv_6 4;]$

Assim, para $[;i \geq 2;]$ , temos $[;10^i \equiv_6 4;]$ . Logo, todos os dígitos interessam.

$[;391212145 \equiv_6 4.3+4.9+4.1+4.2+4.1+4.2+4.1+4.4+5 \Rightarrow;]$

$[;391212145 \equiv_6 (2.6)+(6.6)+(4)+(6+2)+(4)+(6+2)+4+(2.6+4)+5 \Rightarrow;]$

$[;391212145 \equiv_6 0+0+4+2+4+2+4+4+5 \Rightarrow;]$

$[;391212145 \equiv_6 4+4+5 \Rightarrow;]$

$[;391212145 \equiv_6 13 \equi_6 1;]$ ( Resto [;1;]

)

$[;\rightarrow;]$ Um número é divisível por 6 quando ele é divisível por e ou quando a soma do último dígito com quatro vezes a soma dos outros dígitos resultar em um múltiplo de ( ou seja, zero, na aritmética módulo ).

)

por

$[;10=8+2 \equiv_8 2;]$

$[;10^2 =(8+2)(8+2) \equiv 2.2 \equiv_8 4;]$

$[;10^3=(8+2)(8+2)(8+2) \equiv_8 2.2.2 \equiv_8 8 \equiv_8 0;]$

Assim, para $[;i \geq 3;]$ , temos $[;10^i \equiv_8 0;]$ . Logo, na redução de um número módulo [;8;]

, só nos interessa os três últimos dígitos.

$[;45637893 \equiv_8 893 \equiv_8 4.8+2.9+3 \equiv_8 0+2+3 \equiv_8 5;]$ (Resto [;5;]

)

$[;\rightarrow;]$ Um número é divisível por quando o útimo dígito mais o dobro do penúltimo dígito mais o quádruplo do antipenúltimo dígito resultar em um múltiplo de . ( ou seja, zero, na aritmética módulo ).

Então a nossa resposta a pergunta: De modo geral, como se calcula o resto [;r;]