Seja a1, ldots, am um sistema completo de resíduos módulo m.
Se p é primo e a um inteiro que não é múltiplo de p, mostre que a^p-1 equiv 1 bmod p (Pequeno Teorema de Fermat);

Passo 1

Vamos resumir o exercício: Precisamos mostrar que se p é um número primo e a é um inteiro que não é múltiplo de p , então a^p-1 equiv 1 bmod p . Esse resultado é conhecido como o Pequeno Teorema de Fermat. Para resolver isso, vamos usar conceitos de congruências, sistemas completos de resíduos e propriedades de números primos.

Passo 2

Primeiro, vamos entender o que significa uma congruência. Dizemos que dois números a e b são congruentes módulo p , escrito a equiv b bmod p , se a diferença a - b é múltiplo de p . Ou seja, eles deixam o mesmo resto quando divididos por p .

Passo 3

Um sistema completo de resíduos módulo p é um conjunto que inclui todos os possíveis restos que você pode obter ao dividir números inteiros por p . No nosso caso, como p é primo, o sistema completo de resíduos será 0, 1, 2, ldots, p-1 .

Passo 4

Como p é primo e a não é múltiplo de p , isso significa que a não está no conjunto 0 do sistema de resíduos. Portanto, a está em 1, 2, ldots, p-1 , que são os números coprimos com p . Isso é importante porque números coprimos têm inversos multiplicativos no módulo p .

Passo 5

Agora, vamos aplicar o Pequeno Teorema de Fermat: se a e p são coprimos e p é primo, então a^p-1 equiv 1 bmod p . A ideia por trás disso é que, no conjunto dos números coprimos com p , multiplicar a por si mesmo p-1 vezes nos retorna a 1 no módulo p .

Resposta

Assim, mostramos que a^p-1 equiv 1 bmod p .

Exercícios relacionados