O pequeno teorema de Fermat estabelece que mod p onde p é um número primo. De facto se, para algum tivermos , 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, , , , , , , 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, e módulo 11. Para calcularmos o resto da divisão de por 11, é suficiente notar que . Como modulo 11 então módulo 11. Temos, módulo 11:

Não vale a pena continuar para concluir que formámos um ciclo. De facto, donde, por consequência resulta que , , … 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, 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 . Escolhemos um número a do conjunto, por exemplo, . Como a é primo com 11 então 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 mod p. Como é primo com p (e apenas nesta circunstância o podemos fazer), podemos divir ambos os membros da congruência para obtermos módulo p. O produto de qualquer elemento do ciclo pela unidade mantém-se inalterável. Definimos onde . Deste modo, , 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 , isto é, módulo p e q é a inversa de a. Deste modo são verificados todos os axiomas de grupo.

Sabemos que  é um grupo se considerarmos a multiplicação módulo 11. Além disso, o subconjunto é 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

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 , de modo que g não esteja em B. Entao h=gb, vindo onde é 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 . 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 é, . Como 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 . Escolhemos um número que não esteja contido neste conjunto, por exemplo, o 2. Daqui resulta . Escolhemos um número que não esteja em nenhum dos dois subconjuntos anteriores, 4. Deste resulta o subconjunto . 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.