Sejam m \geq 2, a coprimo com m, e seja e=o_{m}(a). Dados inteiros não-negativos k e l, mostre que
a^{k} \equiv a^{l}(\bmod m) \text { se e somente se } k \equiv l(\bmod e)

Passo 1

O enunciado dá as seguintes informações e pede a seguinte equivalência.
  • Dados: m\ge 2 e a tal que \gcd(a,m)=1.
  • Define-se e=o_{m}(a) como a ordem multiplicativa de a módulo m, isto é, o menor inteiro positivo e tal que
a^{e}\equiv 1\pmod m.
  • Dados inteiros não-negativos k e l.
Pergunta: mostrar que
a^{k}\equiv a^{l}\pmod m \quad\text{se e somente se}\quad k\equiv l\pmod e.

Passo 2

Primeiro vou explicar e provar por que existe a ordem e e uma propriedade básica dela.
Definição/observação sobre existência: como \gcd(a,m)=1, os restos dos números a^{0},a^{1},a^{2},\dots ao dividir por m pertencem a um conjunto finito \{0,1,\dots,m-1\}. Pelo princípio da casa dos pombos, existem índices i<j tais que
a^{i}\equiv a^{j}\pmod m.
Multiplicando ambos os lados por um inverso de a^{i} (que existe porque \gcd(a,m)=1) obtemos
a^{j-i}\equiv 1\pmod m.
Assim existe algum inteiro positivo d=j-i com a^{d}\equiv1\pmod m. Definindo e como o menor desses inteiros positivos, e existe e satisfaz a^{e}\equiv1\pmod m. Essa e é a ordem o_m(a).
Propriedade minimal: pela definição de e como menor expoente positivo com a^{e}\equiv1, se um inteiro positivo d satisfaz a^{d}\equiv1\pmod m então necessariamente e divide d. Vou provar essa propriedade mais adiante como lema.

Passo 3

Mostro a implicação direta (fácil): se k\equiv l\pmod e então a^{k}\equiv a^{l}\pmod m.
Escrevendo a congruência dos expoentes, existe inteiro t tal que
k = l + t e.
Então, usando propriedades de potências e que a^{e}\equiv 1\pmod m, temos
a^{k}=a^{l+te}=a^{l}\,(a^{e})^{t}\equiv a^{l}\cdot 1^{t}\equiv a^{l}\pmod m.
Isso prova a direção \big(k\equiv l\pmod e\big)\Rightarrow \big(a^{k}\equiv a^{l}\pmod m\big).

Passo 4

Lema (necessário para a outra direção): se d é um inteiro tal que a^{d}\equiv1\pmod m, então e divide d.
Prova do lema: aplique o algoritmo da divisão a d por e. Existem inteiros q e r com 0\le r<e tais que
d = q e + r.
Então
a^{d} = a^{q e + r} = (a^{e})^{q} a^{r}.
Reduzindo módulo m e usando a^{e}\equiv1\pmod m e também a^{d}\equiv1\pmod m, obtemos
1\equiv a^{d}\equiv (a^{e})^{q} a^{r}\equiv 1^{q} a^{r}\equiv a^{r}\pmod m.
Portanto a^{r}\equiv1\pmod m. Mas e foi escolhido como o menor inteiro positivo com essa propriedade, e 0\le r<e. A única possibilidade compatível é r=0. Logo d = q e, isto é, e divide d. Isso conclui o lema.

Passo 5

Agora provamos a direção recíproca: se a^{k}\equiv a^{l}\pmod m então k\equiv l\pmod e.
Da congruência dada, multiplicamos ambos os lados por o inverso multiplicativo de a^{l} módulo m. Justificativa: como \gcd(a,m)=1, existe o inverso de a módulo m, e portanto existe também o inverso de a^{l} (a^{-1})^{l}). Multiplicando pela inversa de a^{l} obtemos
a^{k}\cdot (a^{l})^{-1}\equiv a^{l}\cdot (a^{l})^{-1}\pmod m,
ou seja
a^{k-l}\equiv 1\pmod m.
(Nota: aqui k-l pode ser negativo; a congruência a^{k-l}\equiv1\pmod m é interpretada no grupo multiplicativo dos invertíveis módulo m, e a potência com expoente negativo corresponde a usar a potência do inverso. Alternativamente, pode-se tratar separadamente o caso k\ge l e k<l; o ponto essencial é que existe um inteiro d=k-l com a^{d}\equiv1\pmod m.)
Pelo lema do Passo 4, como a^{k-l}\equiv1\pmod m, obrigatoriamente e divide k-l. Logo
k\equiv l\pmod e.
Isso prova a direção \big(a^{k}\equiv a^{l}\pmod m\big)\Rightarrow\big(k\equiv l\pmod e\big).

Passo 6

Juntando os dois sentidos demonstrados nos Passos 3 e 5, obtemos a equivalência desejada:
a^{k}\equiv a^{l}\pmod m \quad\Longleftrightarrow\quad k\equiv l\pmod e.

Resposta

a^{k}\equiv a^{l}\pmod m se e somente se k\equiv l\pmod e.

Exercícios relacionados