Regra de Divisibilidade Utilizando Escalonamento e Aritmética Modular

Adaptado de um trabalho do amigo Fernando Manso, da UFTPR – Campo Mourão

A proposta aqui é a construção de um algoritmo que sirva como regra de divisibilidade por escalonamento, utilizando aritmética modular. (Para saber mais sobre aritmética modular, clique aqui)

Seja j um número que queremos saber se é divisível por m . Definimos um sistema de congruência módulo m:

com.

Ora, por que essa limitação? Logo veremos.

Seja k=ai, em representação decimal, tal que i seja o último dígito de . Façamos k=mn, geramos os valores de a como segue no exemplo: Seja m=17;

. E assim por diante, até

Assim, cada valor de m ao ser multiplicado por n gera um valor para k, que por sua vez define o valor de a. Para m=17, o quadro geral fica:

n(i)= 0      1 2   3   4 5 6   7 8 9

a(i)=17(0) 5 10 15 3 8 13 1 6 11

Definidos j e m, escalonamos j conforme segue:

Onde x_n é j_n desprezado o ultimo dígito.

Esse dígito i irá gerar a conforme definido acima. Esse valor a será utilizado na relação de congruência em n. Se obtivermos, no escalonamento, algum j=0, isto implica que j é divisível por m e são verdadeiras todas as congruências geradas. Caso contrário, j não é divisível por m e as congruências geradas não se verificam.

Ex: j=5984, m=17.

n(i)= 0 1 2 3 4 5 6 7 8 9

a(i)=17(0) 5 10 15 3 8 13 1 6 11

Suponhamos

Então

Poderíamos continuar com o algoritmo, mas agora sabemos que esta relação é óbvia.

Logo, j é divisível por m e são verdadeiras todas as relações de congruência. Assim,

Agora, por que esse método funciona?

Calma: comecemos respondendo à nossa pergunta inicial.

Para n>9, podemos decompor n como

Então, k vira

Agora, ao fazer  a_i, teremos

Como tm é sempre divisível por m, podemos eliminar, pois queremos a_i menor que m. Ou seja,

Logo, precisamos considerar apenas n de 1 a 9, pois os outros a_i se repetem periodicamente.

Assim, para achar a, devemos escalonar k, diminuindo i e dividindo por 10:

Logo, como o único número i que geral a_i=0 é 0, teremos que queremos j divisível por m. Assim,

Isso implica que, pela definição,

E, também, que

Mas, segundo a discussão já apresentada, podemos reduzir j, se este é múltiplo de m, a um número da forma algarismo vezes m na hora de escaloná-lo, pois “retiraremos” o algarismo da unidade. Entretanto, como vimos, ao definir x_n, este deve ser congruente ao a_n resultante do escalonamento de j_n, pois, pela nossa demonstração, há uma periodicidade na hora de analisar os a_n.. Logo, só teremos de repetir este processo o quanto quisermos para verificar que j é realmente divisível por m. Se, ao final, tivermos um resultado contraditório, mesmo se as contas intermediárias estiverem corretas, então o nosso início foi incorreto. Logo, j não é divisível por m.