Seja a um inteiro. Mostre que
se \operatorname{mdc}(a, 35)=1, então a^{24} \equiv 1(\bmod 35).

Passo 1

Vou listar claramente o que o enunciado dá e o que pede, sem resolver nada ainda.
  • Dado: a é um inteiro tal que \operatorname{mdc}(a,35)=1.
  • Pedido: mostrar que a^{24}\equiv 1\pmod{35}.
Informações relevantes extraídas do enunciado:
  • O módulo é 35.
  • A condição \operatorname{mdc}(a,35)=1 significa que a é invertível módulo 35 (não divide 5 nem 7).
  • Não há outro dado numérico.

Passo 2

Idéia geral que vamos usar (explicação didática do resultado que será aplicado).
Existe um resultado geral que diz que, para todo inteiro n\ge1 e todo inteiro a com \operatorname{mdc}(a,n)=1, vale
a^{\varphi(n)}\equiv 1\pmod{n},
onde \varphi(n) é a função totiente de Euler (número de inteiros entre 1 e n que são coprimos com n). Esse resultado é conhecido como o Teorema de Euler. Vamos explicar o que é \varphi(n) e provar por que o teorema é verdade de maneira elementar.

Passo 3

O que é \varphi(n) e como calcular \varphi(35).
  • Definição: \varphi(n) é o número de inteiros 1\le r\le n tais que \operatorname{mdc}(r,n)=1.
  • Propriedade útil: se p é primo então \varphi(p)=p-1 porque todos os inteiros 1,2,\dots,p-1 são coprimos com p.
  • Para produto de primos distintos, \varphi é multiplicativa: se \operatorname{mdc}(m,n)=1 então \varphi(mn)=\varphi(m)\varphi(n). No caso de potências de primo vale \varphi(p^k)=p^k-p^{k-1}=p^k(1-\tfrac{1}{p}).
Aplicando isso a 35=5\cdot7 (5 e 7 são primos e são coprimos entre si):
\varphi(35)=\varphi(5)\varphi(7)=(5-1)(7-1)=4\cdot6=24.
Também é possível usar a fórmula \varphi(n)=n\prod_{p\mid n}(1-\tfrac{1}{p}) e obter o mesmo: \varphi(35)=35(1-\tfrac{1}{5})(1-\tfrac{1}{7})=35\cdot\tfrac{4}{5}\cdot\tfrac{6}{7}=24.

Passo 4

Prova elementar do Teorema de Euler (por que a^{\varphi(n)}\equiv1\pmod{n} quando \operatorname{mdc}(a,n)=1).
Construa o conjunto dos resíduos reduzidos módulo n:
R=\{r_1,r_2,\dots,r_{\varphi(n)}\},
onde cada r_i satisfaz 1\le r_i\le n e \operatorname{mdc}(r_i,n)=1. Multiplicar todos os elementos de R por a módulo n dá outro conjunto
aR=\{a r_1 \bmod n,\; a r_2 \bmod n,\;\dots,\; a r_{\varphi(n)} \bmod n\}.
Porque \operatorname{mdc}(a,n)=1, a multiplicação por a modulo n é uma permutação dos elementos de R: nenhum produto a r_i é congruente a 0 (pois r_i é coprimo a n) e se a r_i\equiv a r_j\pmod{n} então, multiplicando por inverso de a modulo n, obtemos r_i\equiv r_j\pmod{n}, logo i=j. Assim os dois produtos abaixo são congruentes módulo n:
\prod_{i=1}^{\varphi(n)} a r_i \equiv \prod_{i=1}^{\varphi(n)} r_i \pmod{n}.
No lado esquerdo podemos tirar a^{\varphi(n)} em fator:
a^{\varphi(n)}\cdot \prod_{i=1}^{\varphi(n)} r_i \equiv \prod_{i=1}^{\varphi(n)} r_i \pmod{n}.
Agora note que \prod_{i=1}^{\varphi(n)} r_i é coprimo com n (produto de números cada um coprimo com n), então esse produto tem inverso multiplicativo módulo n. Cancelando (ou multiplicando ambos os lados pelo inverso), obtém-se
a^{\varphi(n)}\equiv 1\pmod{n}.
Isso prova o Teorema de Euler.

Passo 5

Aplicando o Teorema de Euler ao caso concreto n=35.
Temos calculado que \varphi(35)=24. Pela prova do Teorema de Euler, para qualquer inteiro a com \operatorname{mdc}(a,35)=1 vale
a^{\varphi(35)}\equiv 1\pmod{35}.
Substituindo \varphi(35)=24 obtemos
a^{24}\equiv 1\pmod{35}.

Passo 6

Comentário didático extra e alternativa curta usando primos (opcional, para fixar a ideia).
  • Como 35=5\cdot7 e \operatorname{mdc}(a,35)=1, temos \operatorname{mdc}(a,5)=1 e \operatorname{mdc}(a,7)=1. Pelo pequeno teorema de Fermat:
a^{4}\equiv 1\pmod{5}\quad\text{e}\quad a^{6}\equiv 1\pmod{7}.
Como \operatorname{lcm}(4,6)=12, segue a^{12}\equiv 1\pmod{5} e a^{12}\equiv 1\pmod{7}, e portanto a^{12}\equiv 1\pmod{35} (pelo CRT). Isso é ainda mais forte que o pedido a^{24}\equiv1\pmod{35}; em particular a^{24}\equiv (a^{12})^2\equiv1^2\equiv1\pmod{35}. Essa via alternativa ajuda a entender que o expoente 24 aparece naturalmente por \varphi(35), mas às vezes há expoentes menores que também funcionam.

Resposta

\displaystyle a^{24}\equiv 1\pmod{35}

Exercícios relacionados