Determinação do resto da divisão de números

Aqui vou expor um método para simplificar a determinação do resto da divisão entre dois números inteiros. No decurso do texto irei utilizar o noção de congruência, vulgarmente denotada por \equiv e introduzida por Gauss no seu famigerado Disquisitiones Arithmeticae ou “Investigações Aritméticas”. Apesar de já ter feito uma descrição deste conceito em textos anteriores, sugiro aqui a leitura de Critérios de divisibilidade, uma vez que aí já é possível encontrar uma descrição suficientemente detalhada do que se pretende. No entanto, pretendo descrever como o método é aplicável à determinação dos restos. Trata-se efectivamente de uma aplicação do pequeno teorema de Fermat.

Dizemos então que dois números a e b são congruentes módulo p se o restos restos das divisões de a por p e b por p forem iguais e escrevemos a\equiv b\ mod\ p. Aqui, ao invés de considerarmos que o resto é um número entre 0 e p-1, vamos defini-lo como sendo um número entre -\frac{p-1}{2} e \frac{p-1}{2} se p for um número ímpar e entre -\frac{p-2}{2} e \frac{p}{2} se p for um númer par. Por exemplo, o resto da divisão de 17 por 10 é igual a -3, uma vez que 17 = 2\times 10 - 3.

Sabemos que um número n qualquer admite uma representação da forma

n=a_k10^k+a_{k-1}10^{k-1}+\cdots+a_1 10+a_0

onde os a_i são os algarismos de 0 a 9. Na notação árabe habitual escrevemos n=a_ka_{k-1}\cdots a_{1}a_0. Por exemplo, se n=345, então

n=3\times 10^2+4\times 10+5

De modo a tornar os passos claros, vou considerar um exemplo prático. Seja então p=7. Como sabemos da teoria das congruências binomiais, à qual se relaciona o pequeno teorema de Fermat, os números 10^k geram, módulo 7 um conjunto de números G cuja ordem divide 6. De um modo geral, temos 10^k\equiv 10^{k+6l}. Determinemos o conjunto G. Ora, módulo 7, temos

10^0\equiv 1
10 \equiv 3
10^2\equiv 3^2\equiv 2
10^4\equiv 3\times 2\equiv -1
10^5\equiv 3\times(-1)\equiv -3
10^6\equiv 3\times (-3)\equiv -2
10^7\equiv 3\times (-2)\equiv 1

Segue-se que G=\left\lbrace 1,3,2,-1,-3,-2\right\rbrace com 6 elementos que, obviamente, divide 6. Seja, por exemplo, n=9786248 do qual pretendemos determinar o resto da sua divisão por 7. Pomos então

n=9\times 10^6+7\times 10^5+8\times 10^4+6\times 10^3+2\times 10^2+4\times 10+8

O primeiro passo a seguir será determinar os restos positivos dos algarismos módulo 7. Esta redução é possível uma vez que 7 < 10. Então

n\equiv 2\times 10^6+1\times 10^4+6\times 10^3+2\times 10^2+4\times 10+1

Na prática, se n=a_ka_{k-1}\cdots a_1a_0 for a representação árabe de um número então, se substituirmos cada um dos algarismos a_k pelo resto da sua divisão por 7 obtemos um número n' menor ou igual a n que lhe é congruente. Assim, sendo n=9786248 então n'=2016241\equiv n. Por outro lado, sabemos que 10^k\equiv 10^{k+6l} módulo 7. Deste modo,

n\equiv 2\times 10^0+1\times 10^4+6\times 10^3+2\times 10^2+4\times 10+1=16243

Lembramos agora o conjunto G=\left\lbrace 1,3,2,-1,-3,-2\right\rbrace que possui as congruências das várias potências de 10 com expoentes entre 0 e 6. Então

n\equiv 1\times (-3)+6\times (-1)+2\times 2+4\times 3+3=10

Como 10\equiv 3, também 9786248\equiv 3. Na prática, a determinação do resto da divisão do número n'=16243 por 7 resulta da soma dos produtos dos elementos ordenados de G pelos algarismos de n'.

Vejamos outro exemplo. Façamos p=11 e n=25892847. Ora, 10\equiv -1 módulo 11 e, por conseguinte, temos G=\left\lbrace 1,-1\right\rbrace. Como o número de elementos em G é dois, dividimos o número n em grupos de dois algarismos (iniciando sempre nas unidades) e somamo-los, obtendo o número congruente

n' = 47+28+89+25=189

Como o número de algarismos ainda é superior a 2, repetimos o passo anterior vindo o número congruente

n''=89+1=90

Agora, multiplicamos os valores de G pelos algarismos de n'' começando nas unidades, vindo

n'''=0\times 1 + 9\times -1=-9\equiv 2

Concluímos que o resto da divisão de 25892847 por 11 é igual a 2.

Façamos agora p=37 e n=5234509805889372945. Em primeiro lugar, determinamos G=\left\lbrace 1,10,-11\right\rbrace que possui exactamente três elementos. Dividimos o número n em grupos de 3 elementos a começar nas unidades e somamos. Segue-se portanto que

n\equiv 945+372+889+805+509+234+5=3759

Como o número de algarismos continua a ser superior a 3, continuamos

n\equiv 759+3=762

Multiplicamos então os algarismos pelos elementos de G começando nas unidades, vindo

n\equiv 2+6\times 10+7\times (-11)=-15

Temos portanto 37-15=22 como sendo o resto procurado.

Sobre Sérgio O. Marques

Licenciado em Física/Matemática Aplicada (Astronomia) pela Faculdade de Ciências da Universidade do Porto e Mestre em Matemática Aplicada pela mesma instituição, desenvolvo trabalho no PTC (Porto Technical Centre) - Yazaki como Administrador de bases-de-dados. Dentro o meu leque de interesses encontram-se todos os temas afins às disciplinas de Matemática, Física e Astronomia. Porém, como entusiasta, interesso-me por temas relacionados com electrónica, poesia, música e fotografia.
Esta entrada foi publicada em Matemática. ligação permanente.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s