Continuação do tópico anterior

No tópico anterior, foi apresentada uma demonstração do pequeno teorema de Femat. De acordo com este resultado, x^p\equiv x módulo p, onde p é um número primo. Vimos que se x^d\equiv 1 módulo p então d tem de dividir p-1. Se considerarmos o módulo p, as potências de cada um dos p-1 números inferiores a p geram conjuntos de números cujo cardinal divide p-1. Por exemplo, se considerarmos os restos das potências de 11 segundo a divisão por 19, obtemos o conjunto A={1,7,11}. Caso consideremos as potências de 2, obtemos todos os números entre 1 e 18. Expressamo-los por ordem:

B=\lbrace 1,2,4,8,16,13,7,14,9,18,17,15,11,3,6,12,5,10 \rbrace

O primeiro elemento do conjunto é 20, o segundo elemento é 21, o terceiro é 22 e assim sucessivamente. Como as potências de 2 gera todos os números inferiores ao módulo 19, dizemos que 2 é uma raíz primitiva desse módulo. Existirá uma raíz primitiva para qualquer módulo? Antes de responder a esta questão, é pertinente fazer algumas observações.

Como o número 11 se encontra na posição 13 então temos, módulo 19, 2^{12}\equiv 11. Deste modo, 11^2 é igual a 2^{24}\equiv 2^6, o qual estará na posição 7 do conjunto B. Temos ainda 11^3\equiv 2^6\times 2^{12}\equiv 1 que se encontra na primeira posição do conjunto. Daqui resulta o conjunto A. Para determinar as potências dos vários números entre 1 e 18 módulo 19, é suficiente considerar as posições que estes ocupam no conjunto A. Por exemplo, o número 16 ocupa a quinta posição. Se partirmos da primeira posição, teremos de nos deslocar quatro posições até encontrar o número 16. Então, para encontrar 16^2, deslocamo-nos novamente quatro posições para encontrar o valor 9. Por este processo vemos que 16^4\equiv 5 que se encontra na posição 17. Para encontrar o valor de 16^5, deslocamo-nos quatro posições considerando que, quando chegamos ao final do conjunto, a próxima posição é a primeira, isto é, saltamos os valores 10,1 e 2 para obtermos 16^5\equiv 4. Se, a partir do primeiro elemento, saltarmos de três em três posições, obtemos o conjunto C={1,8,7,18,11,12}, o qual tem seis elementos. Isto acontece porque 3 é divisor de 18. Por este processo é possível encontrar elementos que geram conjuntos cujo cardinal seja um qualquer divisor de 18.

Consideremos o módulo p e suponhamos que o número p-1 admite uma factoriação em números primos da forma

p-1=a^kb^lc^m...

Seja g um número entre p e p-1 que não satisfaça a congruência x^{\frac{p-1}{a}}\equiv 1, módulo p. Note-se que esta escolha é sempre possível. Se fizermos g^{\frac{p-1}{a^k}}\equiv h, temos h^{a^k}\equiv g^{p-1}\equiv 1. Mas h^{a^{k-1}}\equiv g^{\frac{p-1}{a}} que não é congruente à unidade devido à nossa escolha para g. Do mesmo modo verificamos que h^{a^{k-2}}, h^{a^{k-3}}, etc, não são congruentes à unidade. Como h gera um conjunto cujo cardinal tem de dividir a^k e este número apenas é divisível por ele próprio ou por potências inferiores de a, então o conjunto gerado por h terá exactamente a^k elementos. Com a mesma técnica construímos geradores de conjuntos com b^l, c^m, etc, elementos.

Consideremos o produto H=ABC... de todos os números que construímos no parágrafo anterior. Vamos mostrar, pelo método da redução ao absurdo, que este produto gera um conjunto com p-1 elementos. Começamos por considerar que H gera um conjunto com t elementos, onde t é um divisor de p-1. Então \frac{p-1}{t} será um inteiro superior a 1. Segue-se daqui que um dos números primos da factorização, a, b, c, … divide t. Sem perda de generalidade, imaginamos que é a (o raciocínio é semelhante se for outro número primo qualquer). Como t é divisível por a então divide \frac{p-1}{a}. Então o produto ABC... será congruente à unidade se o elevarmos a \frac{p-1}{a}. Mas, como \frac{p-1}{a} é múltiplo de todas as potências dos outros números primos na factorização de p-1, vemos que os números B,C,… são congruentes à unidade quando elevados a esta potência. Então

A^{\frac{p-1}{a}}B^{\frac{p-1}{a}}C^{\frac{p-1}{a}}\cdots \equiv A^{\frac{p-1}{a}} \equiv 1

Daqui segue que a^k terá de dividir \frac{p-1}{a}, isto é, que \frac{p-1}{a^{k+1}} deverá ser um inteiro, o que é um absurdo. Mostrámos, desta forma, que qualquer módulo primo contém uma raíz primitiva. Construir os números que utilizámos nesta demonstração (devida a Gauss) para o módulo 37 constitui um exercício interessante que não levarei a cabo aqui.

Para finalizar apresento uma consequência deste teorema. Seja

f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0

um polinómio de grau n. Se considerarmos a congruência módulo um número primo p, os coeficientes podem ser substituídos pelos respectivos restos da divisão por p. Além disso, as potências superiores a p são reduzidas, de acordo com o teorema, em potências inferiores. Por exemplo, o polinómio 13x^{11}-24x^6+x-3 é congruente ao polinómio 3x^3-4x^2+x-3 módulo 5, uma vez que 13\equiv 3, 24\equiv 4, x^{11}\equiv x^3 e x^6\equiv x^2 módulo 5. O estudo dos polinómios módulo números primos encontra aplicações em teoria de Galois.

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 Sem categoria. ligação permanente.

Uma resposta a Continuação do tópico anterior

  1. Pingback: O pequeno teorema de Femat – uma generalização | Sérgio's space

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