*16. Considere a função
dada por
, em que
é o resto da divisão de
por 11 .
a) Mostre que
é uma permutação, ou seja,
.
b) Determine a paridade de
.
a) Mostre que
b) Determine a paridade de
Passo 1
O enunciado dá uma função
definida assim: para cada
(interpreta-se aqui
),
onde
é o resto da divisão de
por
.
O que o problema pede:
- (a) Mostrar que
é uma permutação de , isto é, . - (b) Determinar a paridade de
(se é par ou ímpar).
Informações relevantes fornecidas:
- A operação de resto é tomada módulo
(ou seja, trabalhamos em ). - O domínio contém exatamente os inteiros
(todos coprimos com ), logo para todo vale (Teorema de Fermat).
Passo 2
Usar aritmética modular e o Teorema de Fermat para simplificar a fórmula de
.
Pelo Teorema de Fermat, para todo
temos
Dessa igualdade segue que
, isto é, para cada
vale
Agora fatoramos a expressão que define
:
Portanto, dependendo de
(ser
ou
em
), o valor de
toma duas formas simples.
Passo 3
Separar os casos e descrever explicitamente
.
Defina os subconjuntos
Como
, cada
pertence a exatamente um dos conjuntos
ou
; e como o grupo multiplicativo
tem ordem
, temos
e
.
Usando a fatoração do passo anterior:
- Se
(ou seja ), então
- Se
(ou seja ), então
ou seja
.
Concluímos a fórmula compacta:
Passo 4
Mostrar que
é bijetora (logo uma permutação) usando a estrutura dos subconjuntos
e
.
Observações úteis (explicadas de forma simples):
-
é um subgrupo cíclico de ordem de . Numa grupo cíclico de ordem a aplicação é um automorfismo porque . Logo, a restrição é bijetiva de sobre . - Para
temos (pois ), ou seja, o mapa envia em . Esse mapa é bijetivo porque, em termos de expoentes em um gerador de , multiplica índices ímpares por e isso é bijeção entre índices ímpares e índices pares modulo . - A multiplicação por
é bijetora em (pois tem inverso módulo ). Além disso, calcula-se que
logo
. Assim a multiplicação por
envia
bijetivamente em
, e como
tem-se
(um coseto do subgrupo
).
Agora combine:
- Para
, é bijeção e depois multiplicar por é bijeção . Logo é bijeção . - Para
, é bijeção .
Portanto
é bijetora em
e em
simultaneamente, logo
é bijetora em
. Conclui-se que
é permutação de
, isto é
.
Passo 5
Para determinar a paridade de
é conveniente obter a decomposição em ciclos. Vamos escolher um gerador explícito de
e calcular imagens concretas (isso é seguro e didático).
Tomemos
. Verifica-se que
e
, portanto
é gerador de
. Assim podemos listar os elementos:
Dessa listagem obtemos os subconjuntos
e
:
Passo 6
Calcular
para cada
usando as fórmulas do passo 3 e montar os ciclos.
Para
(usar
):
Logo a ação em
é os ciclos
e
.
Para
(usar
):
Logo a ação em
é os ciclos
e
.
Juntando tudo, a decomposição em ciclos de
em
é
Passo 7
Calcular a paridade usando a decomposição em ciclos.
Lembrete rápido: um ciclo de comprimento
é produto de
transposições, logo tem sinal
. Na decomposição acima temos dois 1-ciclos (fixos) e duas 4-ciclos. Cada 4-ciclo tem sinal
. O sinal total de
é o produto dos sinais dos ciclos:
Portanto
é uma permutação par.