ELEMENTOS: 009-Congruências mod 10, mod 4 e Potências

Assombre os seus amigos e calcule, de cabeça, a raiz cúbica de $1000 < n^3 < 1000000$ , com $n \in \mathbb{N}$ .

Para isso, apenas memorize a seguinte tabela numérica.

Observe que os números da coluna A são os números naturais de $0$ a $9$ .

Na coluna B temos os cubos dos números da primeira coluna.

E na coluna C consta os últimos dígitos dos números da coluna B.

$\rightarrow$ Antes de mais nada, o número, cuja raiz cúbica se quer encontrar por este método, tem que ser um cubo perfeito e tem que ter de $4$ à $6$ dígitos ( para satisfazer a condição $1000 < n^3 < 1000000$ ). Portanto, a raiz cúbica achada tem sempre $2$ dígitos.

Primeiro exemplo. Qual a raiz cúbica de $373248$ ?

Passo 1: Separa-se o número de três em três dígitos da direita para a esquerda $\leftarrow$ : $373$ . $248$ .

Passo2: Enquadra-se a primeira parte desta separação, que é $373$ , entre os números da coluna do B. Assim, verifique que $373$ está entre $373$ e $512$ .

Passo3: Pegue o menor número do enquadramento ( $373$ ) e verifique a sua correspondência com a coluna A. Portanto, encontramos o $7$ , o primeiro dígito da raiz cúbica procurada.

Passo 4: Pegue o último dígito de $373248$ , que é $8$ . Localize-o ( $8$ ) na coluna C e verifique sua correspondência com a coluna esquerda. Veja, então, que $8$ na coluna C corresponde com $2$ na coluna A. Assim, $2$ é o segundo dígito da raiz cúbica procurada.

Resposta $\rightarrow$ a raiz cúbica de $373248$ é $72$ .

Segundo exemplo. Qual a raiz cúbica de $2197$ ?

Passo1: $2$ . $197$ .
Passo2: Na coluna do B, $2$ está entre $1$ e $8$ .
Passo3: O menor número do enquadramento ( $1$ ) corresponde a $1$ na coluna A. Portanto $1$ é o primeiro dígito procurado.
Passo4: O último dígito de $2197$ é $7$ . Sua localização ( $7$ ) na coluna C corresponde à $3$ na coluna A. Portanto, $3$ é o segundo dígito procurado.

Resposta $\rightarrow$ a raiz cúbica de $2197$ é $13$ .

Porque este processo funciona? A resposta está nas RELAÇÕES DE CONGRUÊNCIA.

O conceito e a notação de congruência ( $\equiv$ ) inventada pelo grande matemático alemão Carl Friedrich Gauss $(1777-1855)$ são explanados a seguir.

Dados $a$ , $b$ $\in \mathbb{Z}$ e $m \in \mathbb{N}^*$ :

Diz-se que $a$ é congruente a $b$ módulo $m$ [ anota-se $a \equiv b ( mod m )$ ] quando $a$ e $b$ , divididos por $m$ , deixam o mesmo resto $0\leq r < m$ .

Se deixam o mesmo resto $r$ , então $a=mq_1+r$ e $b=mq_2+r$ e a diferença $a-b=(q_1-q_2)m$ fornece uma nova interpretação:

$a \equiv b ( mod m )$ quando $m$ divide $a-b$ .

Exemplos: $23 \equiv 39 ( mod 4 )$ , $7 \equiv 41 ( mod 2 )$ e $-8 \equiv -13 ( mod 5 )$

Quando $a$ não é congruente à $b$ , módulo $m$ , utilizamos $a \not \equiv b ( mod m)$ .

$\rightarrow$ Lema 1 : Se $k$ é divisor de $a$ , então podemos fazer $a \equiv 0 ( mod k )$ , porque $k$ divide $a-0=a$ .
$\rightarrow$ Lema 2: Se $r<m$ é o resto de $a/m$ então $a \equiv r (mod m)$ porque $a=mq_1+r$ e $m$ divide $a-r=mq_1$ .
$\rightarrow$ Lema 3: Se $a+m \equiv b ( mod m)$ , então $a \equiv b ( mod m)$ , porque $m$ divide $b-a=m$ .

A relação de congruência $(\equiv)$ possui a maioria das propriedades ( ver art 048 ) da relação de igualdade $(=)$ :

I) $a \equiv b ( mod m )$
II) Se $a \equiv b ( mod m )$ , então $b \equiv a (mod m)$
III) Se $a \equiv b (mod m )$ e $b \equiv c ( mod m)$ então $a \equiv c ( mod m )$

Dados $a_1, b_1, a_2, b_2 \in \mathbb{Z}$ , nas operações de adição e multiplicação, temos:

IV) $a_1 \equiv b_1 ( mod m ) \Longleftrightarrow a_1 - b_1 \equiv 0 ( mod m )$
V) Se $a_1 \equiv b_1 ( mod m )$ e $a_2 \equiv b_2 ( mod m)$ , então $a_1 \pm a_2 \equiv b_1 \pm b_2 ( mod m )$
VI) Se $a_1 \equiv b_1 ( mod m )$ e $a_2 \equiv b_2 ( mod m)$ , então $a_1a_2 \equiv b_1b_2 ( mod m)$
VII) Se $a \equiv b (mod m )$ então $ax \equiv bx ( mod m )$ para todo $x \in \mathbb{Z}$ . No entanto, a recíproca não é de toda verdadeira: a propriedade do cancelamento vale apenas se $mdc (x,m)=1$ .

A Progressão Aritmética ( PA ) $N^* \rightarrow \mathbb{Z}$ : $( a_1, a_2, a_3,...,a_n,....)$ é um exemplo de congruência.

$a_n=a_1+(n-1)r$ , sendo $a_1$ o primeiro termo e $r$ a razão.

Como sabemos, a diferença de seus termos

$a_2-a_1=a_3-a_2=a_4-a_3=...=a_n-a_{n-1}=r$

fornece sempre a razão $r$ e, portanto, todos os pares $a_i-a_{i-1}$ são divisíveis pela mesma. Assim,

$a_1 \equiv a_2 \equiv a_3 \equiv a_4 \equiv ...\equiv a_{n-1} \equiv a_n ( mod r )$

E pela propriedade III) conclui-se que, quaisquer que sejam $p$ e $q$ $\in \mathbb{N}*$ , teremos $a_p \equiv a_q ( mod r )$ .

Se a PA tem o primeiro termo $0 \leq a_1 < 10$ e razão $r=10$ , então os últimos dígitos de todos os seus termos são iguais ao último dígito de $a_1$ . Por exemplo, se $a_1=4$ e $r=10$ teremos a sucessão $(4,14,24,34,44,54,...)$ com os últimos dígitos de cada termo iguais ao último dígito do primeiro termo $a_1=4$ . Assim,

$4\equiv 14 \equiv 24 \equiv 34 \equiv 34 \equiv 44 \equiv 54 \equiv...(mod 10)$

Isto ocorre devido a própria particularidade dos números escritos na base decimal que sempre tem o formato $10p+s$ , com $0\leq s < 10$ .

Ou seja, se $a \equiv b ( mod 10)$ então $a$ e $b$ possuem os mesmos últimos dígitos.

$\rightarrow$ Existe uma relação interessante entre a PA de razão $r=4$ ( números congruentes módulo $4$ ), a PA de razão $r=10$ ( números congruentes módulo $10$ ) e as potências.

Por exemplo, a sequência potencial definida por $b_n=(n-1)^3$ tem a particularidade que, a partir de $0^3$ , os últimos dígitos dos seus termos se repetem periodicamente em $10$ números, nesta ordem, $0,1,8,7,4,5,6,3,2,9$ . O que, na linguagem de congruência:

Se $s \equiv t ( mod 10)$ então $s^3 \equiv t^3 ( mod 10)$ , para $s$ e $t$ $\in \mathbb{N}$ .

Na verdade, a sucessão $0,1,8,7,4,5,6,3,2,9$ é válida para $b_n=(n-1)^p$ quando $p=3, 7, 11,...,3+(m-1)4$ .
E, ao todo, temos $4$ classes de sucessões de últimos dígitos para a sequência potencial $b_n=(n-1)^p$ relativos à $4$ grupos de expoentes $p$ .:

Classe 1: para $p= 1,5,9,...1+(k-1)4$ $\rightarrow C1( 0,1,2,3,4,5,6,7,8,9 )$
Classe 2: para $p=2,6,10,...2+(k-1)4$ $\rightarrow C2( 0,4,9,6,5,6,9,4,1)$
Classe 3: para $p=3,7,11,...,3+(k-1)4$ $\rightarrow C3(0,1,8,7,4,5,6,3,2,9)$
Classe 4: para $p=4, 8,12,...,4+(k-1)4$ $\rightarrow C4(0,1,6,1,6,5,6,1,6,1)$

Para identificar a classe de $(n-1)^p$ divide-se o expoente $p$ por $4$ e se o resto for $1,2,3$ ou $0$ então a classe a qual pertence esta potência é classe $1$ , classe $2$ , classe $3$ ou classe $4$ , respectivamente.

Dentro de uma mesma classe, todos os expoentes são congruentes módulo $4$ e podemos escrever o TEOREMA GERAL:

Se $a \equiv b ( mod 10 )$ e $p_1 \equiv p_2 (mod 4 )$ , então $a^{p_1} \equiv b^{p_2} (mod 10)$

Justificativa: Em relação aos últimos dígitos de $b$ e $b^m$

a sequência exponencial $a_m=b^m$ possui um padrão periódico horizontal conforme a seguir:

$b$ $b^m$

$b=(...0)\rightarrow0,0,0,0$

$b=(...1)\rightarrow1,1,1,1$

$b=(...2)\rightarrow2,4,8,6$

$b=(...3)\rightarrow3,9,7,1$

$b=(...4)\rightarrow4,6,4,6$

$b=(...5)\rightarrow5,5,5,5$

$b=(...6)\rightarrow6,6,6,6$

$b=(...7)\rightarrow7,9,3,1$

$b=(...8)\rightarrow8,4,2,6$

$b=(...9)\rightarrow9,1,9,1$

De forma que, se na horizontal temos os padrões $b^m$ , na vertical são formadas as $4$ classes de $(n-1)^p$ .

Problema: Qual o último dígito de $3457^{567}$ ? . Resolução: dividindo $567$ por $4$ , encontramos o resto $3$ , logo, pelo lema 2, $567 \equiv 3 ( mod 4)$ o que indica que esta potência pertence à classe $3$ : $(0,1,8,7,4,5,6,3,2,9)$ . Como $3457 \equiv 7 ( mod 10 )$ , então $3457^{567} \equiv 7^3 ( mod 10)$ e, pelos elementos da classe $3$ , vimos que $7^3 \equiv 3 (mod 10)$ .

Resumo: De $3457^{567}$ , $567 \equiv 3 ( mod 4)$ e $3457 \equiv 7 ( mod 10 )$ $\rightarrow$ $3457^{567} \equiv 7^3 ( mod 10)$ $\equiv 3 ( mod 10 )$ .

Resposta: o último dígito de $3457^{567}$ é $3$ .

Observação: Como podem ver pelos grupos de expoentes $p$ e pelas classes C de sucessão dos últimos dígitos de $(n-1)^p$ é também fácil calcular, de memória, as raízes quínticas de números $10^5 < n < 10^{10}$ e raízes sétimas de números $10^7 < n < 10^{14}$ , com um método semelhante ao descrito no início desta postagem, bastando para isso, fazer um ajuste na tabela.

Fonte ( congruências ):

Teoria dos Números, de
Salahoddin Shokranian,
Marcus Soares,
Hemar Godinho;
Editora UNB, 1998.

9 comentários:

Prof. Paulo Sérgio21 de janeiro de 2012 às 14:36
Excelente post! Ele pode ser uma das respostas a pergunta: Para que servem as congruências modulares? Parabéns por compartilhar este assunto conosco.
ResponderExcluir
Respostas
Aloisio Teixeira21 de janeiro de 2012 às 16:22
Algum tempo atrás tive a ilusão de demonstrar o Último Teorema de Fermat com esta teoria ( rs ). Obrigado e seja sempre bem-vindo!
ResponderExcluir
Respostas
Aloisio Teixeira21 de janeiro de 2012 às 16:26
Ou melhor, a ilusão de querer demonstrar....
ResponderExcluir
Respostas
Kleber Kilhian21 de janeiro de 2012 às 17:14
Gostei do post. Eu não conhecia muita coisa sobre congruências modulares. Aqui deu para entender bastante coisa de forma simples.
Um abraço.
ResponderExcluir
Respostas
Aloisio Teixeira21 de janeiro de 2012 às 19:12
Kleber, a congruência está bastante presente em nossas vidas e é um atalho para provar muitos teoremas ligados a Teoria dos Números. Este assunto que abordei fica interessante de mudarmos a base numérica. Surgirão outras classes e o TEOREMA GERAL se "deformará", mas na essência, permanecerá o mesmo. Valeu!
ResponderExcluir
Respostas
BLOG MANTHANO22 de janeiro de 2012 às 11:53
Olá Aloísio. As congruências são bem interessantes. Curiosamente eu estava preparando uma postagem sobre este tema. Mas eu ia mostrar como utilizá-las para demonstrar alguns critérios de divisibilidade.
Abraço.
Pedro R.
ResponderExcluir
Respostas
Aloisio Teixeira22 de janeiro de 2012 às 13:25
Pedro R., eu acho que os internautas estão precisando de uma matéria de qualidade sobre critérios de divisibilidade. Principalmente para os números primos. Obrigado pela visita!
ResponderExcluir
Respostas
Francisco Valdir15 de abril de 2012 às 15:12
Olá, Aloísio!!!!

Achei superinteressante o seu post e como é o primeiro da listagem desse carnaval, é o que me dedico a ler e comentar! Rapaz, que coisa boa isso aqui!!! Lembrei dos tempos da universidade quando estudava álgebra!!
Logo no início do post, pensei que aquilo era (e não deixa de ser) uma matemágica para se responder de cabeça o valor da raiz cúbica de um número de até cinco dígitos e que seja um cubo perfeito!!!
Relembrando essas clsses, me disparou um pensamento que a classe de módulo 4, poderá ser usada para se tentar prever a sua saída (probabilidade) por ocasião de um próximo sorteio, tipo... a mega sena!!! Mas, não vou tentar me debruçar sobre isso agora, o importante é que a matéria do seu artigo me indicou isso!!
Então, meus parabéns pelo artigo, pela presença no evento e pela continuação das postagens no blog Elementos de Teixeira!!!!

Um abraço!!!!!
ResponderExcluir
Respostas

Adicionar comentário

Páginas

sábado, 21 de janeiro de 2012

009-Congruências mod 10, mod 4 e Potências

9 comentários:

V.O