sábado, 21 de janeiro de 2012

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

Assombre os seus amigos e calcule, de cabeça, a raíz cúbica de [;1000 < n^3 < 1000000;], com [;n \in N;].
Para isso, apenas memorize a seguinte tabela numérica. 

[;0;]        [;0;]     [;0;]
[;1;]        [;1;]     [;1;]
[;2;]        [;8;]     [;8;]
[;3;]     [;27;]    [;7;]
[;4;]     [;64;]    [;4;]
[;5;]    [;125;]     [;5;]
[;6;]    [;216;]     [;6;]
[;7;]   [;343;]    [;3;]
[;8;]    [;512;]     [;2;]
[;9;]   [;729;]    [; 9;]

Observe que os números da coluna esquerda são os números naturais de [;0;] à [;9;].
Na coluna do meio temos os cubos dos números da primeira coluna.
E na coluna direita temos os últimos dígitos dos números da coluna do meio.

[;\rightarrow;] Antes de mais nada, o número, cuja raíz 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 raíz cúbica achada tem sempre [;2;] dígitos.

Primeiro exemplo. Qual a raíz 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 meio.   Assim, verifique que [;373;]está entre [;343;] e [;512;].          
Passo3: Pegue o menor número do enquadramento ([;343;]) e verifique a sua correspondência com a coluna  esquerda. Portanto, encontramos o [;7;] , o primeiro dígito da raíz cúbica procurada.
Passo 4: Pegue o último dígito de [;373248;], que é [;8;]. Localize-o ( [;8;] ) na coluna direita e verifique sua correspondência com a coluna esquerda. Veja, então, que [;8;] na coluna direita corresponde com [;2;] na coluna esquerda. Assim, [;2;] é o segundo dígito da raíz cúbica procurada.

Resposta [;\rightarrow;] a raíz cúbica de [;373248;] é [;72;].

[;0;]        [;0;]     [;0;]
[;1;]        [;1;]     [;1;]
[;2;]        [;8;]     [;8;]
[;3;]     [;27;]    [;7;]
[;4;]     [;64;]    [;4;]
[;5;]    [;125;]     [;5;]
[;6;]    [;216;]     [;6;]
[;7;]   [;343;]    [;3;]
[;8;]    [;512;]     [;2;]
[;9;]   [;729;]    [; 9;]

Segundo exemplo. Qual a raíz cúbica de [;2197;]?

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

Resposta[;\rightarrow;]  a raíz 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 ( [;\equi;]: inventada pelo grande matemático alemão Carl Friedrich Gauss [;\rightarrow;] [; 1777-1855;] ) são explanados a seguir.

Dados [;a;], [;b;] [;\in Z;] e [;m \in 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);] .

[; \right;] Lema 1 : Se [;k;] é divisor de [;a;], então podemos fazer [;a \equiv 0 ( mod k );], porque [;k;] divide [;a-0=a;].
[; \right;] 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;].
 [; \right;] 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 Z;], nas operaçãos 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 Z;] . No entanto, nesta propriedade, 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 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 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;],...etc com últimos dígitos iguais ao último dígito de [;a_1=4;] . Assim,

[;4\equiv 14 \equiv 24 \equiv 34 \equiv 34 \equiv 44 \equiv 54 \equiv...;]etc, [;( 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;].

De modo geral, 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 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;][;\right;] 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);][;\rightarrow;]   [;0,0,0,0;]
[;b=(...1);]   [;\rightarrow;] [;1,1,1,1;]
[;b=(...2);] [;\rightarrow;]  [;2,4,8,6;]
[;b=(...3);]  [;\rightarrow;] [;3,9,7,1;] 
[;b=(...4);]  [;\rightarrow;] [;4,6,4,6;]
[;b=(...5);] [;\rightarrow;]  [;5,5,5,5;]
[;b=(...6);] [;\rightarrow;]  [;6,6,6,6;]
[;b=(...7);]  [;\rightarrow;] [;7,9,3,1;] 
[;b=(...8);]  [;\rightarrow;]  [;8,4,2,6;]
[;b=(...9);] [;\rightarrow;]  [;9,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;], vemos 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:

  1. 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
  2. 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
  3. Ou melhor, a ilusão de querer demonstrar....

    ResponderExcluir
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
    1. Oi, Valdir!

      Obrigado pelo incentivo!

      Ainda não vizualizei este emprego das classes módulo 4 conforme mencionou. Mas fico contente quando um artigo meu fornece uma luz sobre um novo assunto.

      Um grande abraço!

      Excluir