Seja n \in \mathbb{N}, n \geqslant 2.
(a) Dado \bar{k} \in \mathbb{Z}_{n}, prove que o(\bar{k})=\frac{n}{\operatorname{mdc}(k, n)}.
(b) Prove que \bar{k} é gerador de \mathbb{Z}_{n} se, e somente se, \operatorname{mdc}(k, n)=1.
Passo 1
O enunciado dá: n\in\mathbb{N} com n\ge 2 e um elemento \overline{k}\in\mathbb{Z}_n (classe de k módulo n). As perguntas são:
(a) Provar que o(\overline{k})=\dfrac{n}{\operatorname{mdc}(k,n)}, onde o(\overline{k}) é a ordem do elemento \overline{k} no grupo \mathbb{Z}_n.
(b) Provar que \overline{k} é gerador de \mathbb{Z}_n se, e somente se, \operatorname{mdc}(k,n)=1.
Informações relevantes dadas: o número n, o inteiro k (considerado módulo n) e a notação \operatorname{mdc}(k,n).
Passo 2
Definição e tradução do problema em termos aritméticos.
A ordem o(\overline{k}) é, por definição, o menor inteiro positivo m tal que m\overline{k}=\overline{0} em \mathbb{Z}_n.
A igualdade m\overline{k}=\overline{0} significa, em linguagem de restos, que
mk\equiv 0\pmod{n},
isto é,
n\mid mk.
Então determinar o(\overline{k}) equivale a achar o menor m>0 tal que n divide mk.
Passo 3
Fatorar pelo máximo divisor comum. Seja
d=\operatorname{mdc}(k,n).
Podemos escrever k=dk' e n=dn' com \operatorname{mdc}(k',n')=1. Esta escrita é sempre possível: divide-se k e n pelo seu máximo divisor comum e o que sobra tem gcd igual a 1.
Passo 4
Reescrever a condição n\mid mk usando a fatoração.
Substituindo k=d k' e n=d n' obtemos
n\mid mk \quad\Longleftrightarrow\quad d n' \mid m\cdot d k' \quad\Longleftrightarrow\quad n'\mid m k'.
Como \operatorname{mdc}(k',n')=1, se n'\mid m k' então necessariamente n'\mid m. (Isto é uma propriedade básica dos números inteiros: se \gcd(a,b)=1 e a\mid bc, então a\mid c.)
Portanto qualquer m>0 que satisfaça n\mid mk deve ser múltiplo de n'. Em particular o menor m>0 com essa propriedade é m=n'.
Passo 5
Concluir (a). Como o menor m>0 tal que m\overline{k}=\overline{0} é m=n' e lembrando que n'=n/d, obtemos
Exemplo rápido para fixar: seja n=12 e k=8. Então \operatorname{mdc}(8,12)=4, logo o(\overline{8})=\dfrac{12}{4}=3. De fato 1\cdot 8\equiv 8, 2\cdot 8\equiv 4, 3\cdot 8\equiv 0\pmod{12} e não havia m menor que 3 com m\cdot8\equiv0.
Passo 6
Provar (b) usando (a) e uma alternativa construtiva com o Lema de Bézout.
Primeira via (direta): \overline{k} é gerador de \mathbb{Z}_n exatamente quando sua ordem é n (porque o grupo \mathbb{Z}_n tem ordem n). Pela parte (a),
Logo o(\overline{k})=n se, e somente se, \dfrac{n}{\operatorname{mdc}(k,n)}=n, o que acontece exatamente quando \operatorname{mdc}(k,n)=1. Isso prova a equivalência.
Segunda via (construtiva, para intuição): se \operatorname{mdc}(k,n)=1 então, pelo Lema de Bézout, existem inteiros a,b tais que
ak+bn=1.
Passando para classes em \mathbb{Z}_n obtemos a\overline{k}+\;b\overline{n}=\overline{1}, mas \overline{n}=\overline{0}, então a\overline{k}=\overline{1}. Assim \overline{1} está no subgrupo gerado por \overline{k}, e então todos os elementos \overline{0},\overline{1},\overline{2},\dots,\overline{n-1} (que são múltiplos de \overline{1}) estão no subgrupo — logo \overline{k} gera todo \mathbb{Z}_n.
Contraposição (para mostrar necessidade): se \operatorname{mdc}(k,n)=d>1, então todos os múltiplos m\overline{k} são classes cujos representantes são múltiplos de d (em \{0,d,2d,\dots\} módulo n), portanto \overline{1} não pode ser obtida como múltiplo de \overline{k}. Logo \overline{k} não gera \mathbb{Z}_n.