Ex. 13. Seja n \in \mathbb{N}. Um elemento r \in\{1, \ldots, n\} é dito ser uma unidade módulo \boldsymbol{n} se existe s \in\{1, \ldots, n\} tal que r s \equiv 1(\bmod n).
(a) Determine U_{12}.
(b) Mostre que o conjunto U_{n} das unidades módulo n formam um grupo multiplicativo com ordem
\left|U_{n}\right|=\varphi(n)=\#\{k \in\{1, \ldots, n\}:(k, n)=1\}
( \varphi é a função phi de Euler, que associa a cada natural n o número de inteiros entre 1 e n que são relativamente primos \operatorname{com} n.)

Passo 1

O enunciado define: para n\in\mathbb{N}, um elemento r\in\{1,\ldots,n\} é uma unidade módulo n se existe s\in\{1,\ldots,n\} tal que
r s \equiv 1 \pmod{n}.
As tarefas pedidas são:
  • (a) Determinar U_{12}, ou seja, listar todas as unidades módulo 12.
  • (b) Mostrar que o conjunto U_{n} das unidades módulo n forma um grupo multiplicativo (com a operação “multiplicação módulo n”) e que a ordem desse grupo é
\left|U_{n}\right|=\varphi(n)=\#\{k\in\{1,\ldots,n\}:(k,n)=1\},
onde \varphi é a função totiente de Euler.
As informações relevantes dadas pelo enunciado que vou usar:
  • A definição de unidade módulo n (existência de inverso multiplicativo módulo n).
  • A definição de \varphi(n) como o número de inteiros entre 1 e n que são coprimos com n.
    Não há figuras nem outros dados numéricos além de n e a definição acima.

Passo 2

Vamos resolver (a): encontrar U_{12}. Pelo enunciado é conveniente usar a equivalência que vou provar logo a seguir (essa equivalência também ajuda a responder (b)): um r\in\{1,\dots,n\} é unidade módulo n se e somente se (r,n)=1 (ou seja, r é coprimo com n). Para o caso n=12 vou aplicar diretamente a condição de coprimalidade: listar 1,\dots,12 e verificar quais têm \gcd igual a 1.
Os inteiros de 1 a 12 são:
1,2,3,4,5,6,7,8,9,10,11,12.
Fatores primos de 12 são 2 e 3. Portanto, um número entre 1 e 12 é coprimo com 12 exatamente quando não é divisível por 2 nem por 3. Eliminando múltiplos de 2 ou 3 sobra a lista:
1,\;5,\;7,\;11.
Logo, pela equivalência unidade \Leftrightarrow coprimo, temos
U_{12}=\{1,5,7,11\}.

Passo 3

Para fixar a intuição: verifico que cada elemento de U_{12} tem de fato um inverso módulo 12. Calculo produtos:
5\cdot 5 =25\equiv 1\pmod{12}, \qquad 7\cdot 7=49\equiv 1\pmod{12}, \qquad 11\cdot 11=121\equiv 1\pmod{12},
e 1\cdot1\equiv1\pmod{12}. Portanto 5,7,11 são suas próprias inversas (elementos de ordem 2 no grupo) e 1 é a identidade. Isso confirma a lista de (a).

Passo 4

Agora abordo (b). Primeiro provarei a equivalência fundamental: para r\in\{1,\dots,n\},
r \text{ é unidade módulo } n \quad\Longleftrightarrow\quad (r,n)=1.éó
Vou provar as duas implicações.
Direção “ \Rightarrow”: se r tem inverso módulo n. Suponha que existe s\in\{1,\dots,n\} tal que
r s \equiv 1 \pmod{n}.
Isto significa que existe k\in\mathbb{Z} com
r s - 1 = k n.
Reescrevendo:
r s + n(-k) = 1.
Essa escrita mostra que 1 é combinação linear inteira de r e n. Portanto o maior divisor comum (r,n) divide 1, o que implica (r,n)=1. Assim, se r tem inverso módulo n então r é coprimo com n.

Passo 5

Direção “ \Leftarrow”: se (r,n)=1 então r tem inverso módulo n. Aqui uso o Lema de Bézout (identidade de Bézout): se (r,n)=1 então existem inteiros x,y tais que
r x + n y = 1.
Isso é um teorema básico de teoria dos números (explicação rápida: os menores inteiros positivos que podem ser escritos como combinação r x + n y são exatamente os múltiplos do \gcd(r,n); quando \gcd=1 obtém-se 1). Reduzindo a congruência acima módulo n obtemos
r x \equiv 1 \pmod{n},
ou seja, x é um inverso de r módulo n. Tomando o representante de x no conjunto \{1,\dots,n\} (ou \{0,1,\dots,n-1\}) obtemos um s com rs\equiv1\pmod{n}. Assim, r é unidade módulo n. Isso conclui a equivalência.

Passo 6

A partir da equivalência temos
U_n = \{\,r\in\{1,\dots,n\}:(r,n)=1\,\}.
Por definição, o número de tais inteiros é exatamente \varphi(n). Portanto o conjunto de unidades modulo n tem cardinalidade \varphi(n):
|U_n|=\varphi(n).
Isso já resolve a parte do enunciado sobre a ordem do conjunto.

Passo 7

Agora mostro que U_n é um grupo multiplicativo (isto é, é um grupo com a operação “multiplicação módulo n”). Lembro rapidamente: para um conjunto com uma operação ser grupo precisamos verificar quatro axiomas: (i) fechamento, (ii) existência de elemento neutro, (iii) existência de inversos, (iv) associatividade. Vou tratar cada um.
(i) Fechamento: tomem a,b\in U_n. Então (a,n)=1 e (b,n)=1. Quero mostrar que ab\bmod n também pertence a U_n, isto é, (ab,n)=1. Uma maneira simples é por contradição: suponha um primo p divide (ab) e n. Se p\mid ab então p\mid a ou p\mid b. Mas p\mid n e (a,n)=1 e (b,n)=1, logo nenhum dos dois pode ser dividido por p. Contradição. Portanto nenhum primo divisor de n divide ab, e assim (ab,n)=1. Logo ab\in U_n. Em termos de congruências, o produto de duas classes com inverso tem inverso dado por produto dos inversos, o que também mostra fechamento.
(ii) Elemento neutro: 1 pertence a U_n pois (1,n)=1 para todo n. E 1 é neutro para a multiplicação módulo n.
(iii) Inversos: por definição de U_n, cada a\in U_n tem um inverso s com as\equiv1\pmod{n} (vemos isso pela equivalência com (a,n)=1 e o uso do lema de Bézout). Portanto todo elemento tem inverso em U_n.
(iv) Associatividade: a operação é multiplicação de classes residuais módulo n, e a multiplicação de inteiros é associativa; a passagem a classes modulo n preserva associatividade. Logo a operação é associativa em U_n.
Como os quatro axiomas são satisfeitos, U_n é um grupo sob multiplicação módulo n. Observação: é também um grupo abeliano porque a multiplicação é comutativa.

Passo 8

Resumo final do raciocínio (curto e prático para prova de prova): mostrei que
  • r é unidade módulo n \Longleftrightarrow (r,n)=1 (provas via congruência e identidade de Bézout);
  • portanto U_n é exatamente o conjunto dos inteiros em \{1,\dots,n\} coprimos com n, e assim |U_n|=\varphi(n);
  • U_n é fechado, tem identidade 1, cada elemento tem inverso (pela equivalência), e a operação é associativa; logo U_n é grupo multiplicativo finito de ordem \varphi(n).

Resposta

U_{12}=\{1,5,7,11\}
U_n é um grupo sob multiplicação módulo n e |U_n|=\varphi(n).

Exercícios relacionados