Mostre a seguinte generalização do Pequeno Teorema de Fermat, devida a Euler. Se(a, m)=1, então a^Phi(m) equiv 1 bmod m.

Passo 1

Beleza, vamos lá! O exercício pede para a gente demonstrar uma generalização do Pequeno Teorema de Fermat, conhecida como Teorema de Euler. Isso está dentro da matéria de teoria dos números, especificamente lidando com congruências e funções como a função totiente de Euler, representada por Phi(m). Para resolver, vamos precisar entender conceitos como o máximo divisor comum e propriedades de números em congruência.

Passo 2

Primeiro, vamos entender o que significa dizer que gcd(a, m) = 1. Isso quer dizer que o maior número que divide tanto a quanto m é 1, ou seja, a e m são números primos entre si, não têm divisores comuns além de 1.

Passo 3

Agora, vamos falar sobre a função totiente de Euler, Phi(m). Essa função conta quantos números inteiros positivos menores que m são coprimos com m. Por exemplo, se m = 9, os números coprimos com 9 são 1, 2, 4, 5, 7 e 8, então Phi(9) = 6.

Passo 4

O próximo passo é entender o que significa a congruência a^Phi(m) equiv 1 pmodm. Isso quer dizer que, quando a gente divide a^Phi(m) por m, o resto da divisão é 1. Ou seja, a^Phi(m) deixa resto 1 quando dividido por m.

Passo 5

Para provar que a^Phi(m) equiv 1 pmodm, vamos usar o conceito de inverso multiplicativo e propriedades de grupos em aritmética modular. Como gcd(a, m) = 1, sabemos que a tem um inverso multiplicativo módulo m, o que é essencial para a nossa prova.

Passo 6

Vamos considerar o conjunto dos números que são coprimos com m, ou seja, os números que têm gcd igual a 1 com m. Esse conjunto forma um grupo multiplicativo sob a multiplicação módulo m, e o número de elementos desse grupo é exatamente Phi(m).

Passo 7

No contexto de grupos, sabemos que para qualquer elemento a no grupo, a ordem de a (o menor inteiro positivo k tal que a^k equiv 1 pmodm) divide a ordem do grupo, que é Phi(m). Portanto, temos que a^Phi(m) equiv 1 pmodm.

Resposta

Assim, mostramos que se gcd(a, m) = 1, então a^Phi(m) equiv 1 pmodm, confirmando a generalização do Pequeno Teorema de Fermat, conhecida como Teorema de Euler.

Exercícios relacionados