O pequeno teorema de Fermat

O pequeno teorema de Fermat estabelece que a^{p}\equiv a mod p onde p é um número primo. De facto se, para algum k \le p-1 tivermos a^k\equiv 1, então k é um divisor inteiro de p-1. Existem várias demonstrações deste resultado mas uma sobressai por encontrar suporte em teoria dos grupos. Talvez seja conveniente analisar um exemplo.
Estudemos todas as potências de 2 módulo 7, isto é, elevamos o dois às várias potências e determinamos o resto da divisão do resultado por 7. Assim, 2^0 =1, 2^1=2, 2^2=4, 2^3=8\equiv 1, 2^4=16\equiv 2, 2^5=32\equiv 4, 2^6=64\equiv 1 mod 7. O padrão parece emergir do cálculo. De facto, os restos da divisão das várias potências de 2 por 7 parecem repetir-se de três em três. Imaginamos uma forma de nos simplificar as contas, caso estejamos a trabalhar sobre bases e módulos maiores.
Consideremos, agora, todas as potências de 5 módulo 11. Ora, 5^0=1 e 5^2=25\equiv 3 módulo 11. Para calcularmos o resto da divisão de 5^3 por 11, é suficiente notar que 5^3=5\times 5^2. Como 5^2\equiv 3 modulo 11 então 5^3\equiv 3\times 5\equiv 4 módulo 11. Temos, módulo 11:

5^0\equiv 1\\  5^1\equiv 5\\  5^2\equiv 3\\  5^3\equiv 3\times 5\equiv 4\\  5^4\equiv 4\times 5\equiv 9\\  5^5\equiv 9\times 5\equiv 1

Não vale a pena continuar para concluir que formámos um ciclo. De facto, 5^5\equiv 5^0 donde, por consequência resulta que 5^6\equiv 5^1, 5^7\equiv 5^2, … módulo 11.
Sabemos que, se a e b são dois números primos com p, então o produto ab também é primo com p. Tal segue imediatamente do teorema fundamental da aritmética (factorização única). Deste modo, como todos os números entre 1 e p-1 são primos com p, os respectivos produtos são primos com p. Por exemplo, 9\times 7\equiv 8 módulo 11, isto é, obtivemos o número 8 que também é primo com 11. Daqui segue que as várias potências de qualquer número que seja primo com 11 são congruentes a um valor do conjunto A=\left\lbrace1,2,3,4,5,6,7,8,9,10,11\right\rbrace. Escolhemos um número a do conjunto, por exemplo, a=3. Como a é primo com 11 então a\times a também o é e, por conseguinte, pertence ao conjunto especificado. Como o conjunto tem um número finito de elementos então, a partir de um determinado n, obtemos um ciclo.

A unidade pertence a qualquer ciclo assim gerado. De facto, temos a congruência a^{n+k}\equiv a^n mod p. Como a^n é primo com p (e apenas nesta circunstância o podemos fazer), podemos divir ambos os membros da congruência para obtermos a^k\equiv 1 módulo p. O produto de qualquer elemento do ciclo pela unidade mantém-se inalterável. Definimos a^{-n}=a^{k-n} onde 0<n<k. Deste modo, a^n\times a^{-n}=a^k\equiv 1, isto é, todos os elementos do ciclo possuem inversa. Obviamente, cada ciclo é fechado relativamente à multiplicação e esta é comutativa e associativa. Então, cada ciclo é um grupo.

O conjunto A é um grupo. Para o verificar, é suficiente mostrar que existe unidade e uma inversa para cada elemento (o conjunto é obviamente fechado relativamente à multiplicação e esta é associativa). A unidade é 1, como seria de esperar. Seja a um elemento do conjunto. Pelo teorema de Bézout (ver http://www.youtube.com/watch?v=IpsNej-8Ihw), existem números q e r tais que qa-rp=1, isto é, qa\equiv 1 módulo p e q é a inversa de a. Deste modo são verificados todos os axiomas de grupo.

Sabemos que A=\lbrace 1,2,3,4,5,6,7,8,9,10\rbrace é um grupo se considerarmos a multiplicação módulo 11. Além disso, o subconjunto B=\lbrace 5,3,4,9,1\rbrace é um subgrupo, uma vez que se trata do ciclo gerado pelo número 5. Escolhemos um número em A que não esteja em B, por exemplo o 8 e definimos o conjunto

H=8B=\left\lbrace 7,2,10,6,8\right\rbrace

Cada elemento deste conjunto é obtido multiplicando 8 por cada elemento de B e determinando o respectivo resto da divisão por 11. Observamos que nenhum dos elementos de H está em B. Será sempre este o caso?

Seja b um elemento de B e h um elemento de H=gB, de modo que g não esteja em B. Entao h=gb, vindo g=hb^{-1} onde b^{-1} é a inversa de b. Se h estivesse contido em B, como este é um grupo, então g teria de estar contido em B, contrariamente à nossa hipótese. Escolhemos, agora, um elemento l que não esteja contido nem em B nem em H e formamos o conjunto H'=lB. Com o mesmo argumento, mostramos que nenhum elemento de H’ está contido em B. Poderá algum elemento de H’ estar contido em H? Suponhamos que h’=h para algum h em H e algum h’ em H’. Seja b’ um elemento de B de modo que h’=lb’ e b outro elemento de B de modo que h=gb. Então, de h’=h vem lb’=gb, isto é, l=gbb'^{-1}. Como bb'^{-1} está em B, concluímos que l está em H, contrariamente à nossa hipótese. Estes argumentos permitem construir uma série de subconjuntos disjuntos de A, cada um com o mesmo número de elementos. Como o conjunto A tem um número finito de elementos, o processo termina. Assim, o número de elementos num ciclo tem de dividir o número de elementos de A, isto é, p-1. Fica concluída a prova do teorema de Fermat.

Vejamos mais um exemplo. Consideramos o conjunto de todos os naturais inferiores a 19 e o produto sobre este módulo. Todas as potências de 7 resultam no ciclo \left\lbrace1,7,11\right\rbrace. Escolhemos um número que não esteja contido neste conjunto, por exemplo, o 2. Daqui resulta \left\lbrace 2,14,3\right\rbrace. Escolhemos um número que não esteja em nenhum dos dois subconjuntos anteriores, 4. Deste resulta o subconjunto \left\lbrace 4,9,6\right\rbrace. Procedemos deste modo até exaurir os elementos do conjunto.

Desenvolvi em C# uma pequena função para determinar os ciclos módulo algum número. O código é como se segue:

 class Program
    {
        static void Main(string[] args)
        {
            NumberModulus modulus = new NumberModulus(19);
            for (int i = 1; i < modulus.Modulus; ++i)
            {
                Console.Write("{0}: ", i);
                PrintCollection<int>(modulus.GeneratePeriod(i));
                Console.WriteLine();
            }
            Console.ReadKey();
        }

        private static void PrintCollection<T>(IEnumerable<T> collection)
        {
            Console.Write("[");
            if (collection.Count() > 0)
            {
                Console.Write(collection.ElementAt(0));
                for (int i = 1; i < collection.Count(); ++i)
                {
                    Console.Write(",");
                    Console.Write(collection.ElementAt(i));
                }
            }
            Console.Write("]");
        }
    }

    class NumberModulus
    {
        private int modulus;

        public int Modulus
        {
            get { return this.modulus; }
        }

        public NumberModulus(int modulus)
        {
            if (modulus == 0 || modulus == 1)
            {
                throw new Exception("Modulus can't be 0 nor 1");
            }
            this.modulus = modulus;
        }

        public List<int> GeneratePeriod(int generatingNumber)
        {
            List<int> result = new List<int>();
            result.Add(generatingNumber);
            int temp = (generatingNumber * generatingNumber) % this.modulus;
            while (temp != generatingNumber && temp != 0)
            {
                result.Add(temp);
                temp = (temp * generatingNumber) % this.modulus;
            }
            return result;
        }
    }

Na função Main começamos por instanciar um objecto da classe NumberModules, passando-lhe o respectivo módulo como argumento. Se pretendermos obter o ciclo gerado pelo número n, chamamos a função NumberModulus.GeneratePeriod(n) a qual retorna uma lista de inteiros com todos os elementos do respectivo ciclo.

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 O pequeno teorema de Fermat

  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