a) Mostre que o inteiro 2 tem ordern n, bmod 2^n-1.
b) Prove que varphi(2^n-1) é múltiplo de n, para todo n>1.
c) Se p>1 é primo, pode-se concluir que varphi(p^n-1) é múltiplo de n , para todo n>1 ? Justifique a resposta.
Sugestäo para a): h<n Rightarrow 2^h-1<2^n-1.

Passo 1

O enunciado trata de ordem multiplicativa e da função totiente de Euler. Mais precisamente:
– Em (a) queremos mostrar que, no anel bmod,(2^n-1), o elemento 2 satisfaz
2^nequiv1pmod2^n-1
e que nenhum expoente menor faz isso, ou seja, a ordem de 2 é exatamente n.
– Em (b) vamos usar que, numa grupo cíclico de ordem varphi(m), a ordem de qualquer elemento divide varphi(m).
– Em (c) perguntam se para um primo p>1 o mesmo argumento mostra que varphi(p^n-1) é múltiplo de n.

Passo 2

Mostramos que 2^nequiv1pmod2^n-1 e que não há expoente menor. De fato,
2^n-1equiv0pmod2^n-1,
logo 2^nequiv1. Se existisse h<n tal que 2^hequiv1pmod2^n-1, então
2^n-1mid2^h-1
Mas para 1<= h<n tem-se 0<2^h-1<2^n-1, o que impede a divisibilidade não trivial. Logo nenhum h<n satisfaz 2^hequiv1.

Passo 3

Pelas definições, a ordem de 2 módulo 2^n-1 é o menor d>0 com 2^dequiv1. Dos argumentos anteriores segue d=n.

Passo 4

Sendo (Bbb Z/(2^n-1)Bbb Z)^times um grupo de ordem varphi(2^n-1) e sabendo que a ordem de 2 nesse grupo é n, a propriedade de Lagrange diz que
nmidvarphi(2^n-1)

Passo 5

Se p>1 é primo, basta repetir o raciocínio trocando 2 por p. Temos
p^nequiv1pmodp^n-1,
e para h<n segue 0<p^h-1<p^n-1, impedindo p^n-1mid p^h-1. Logo a ordem de p módulo p^n-1 é n e, pela mesma aplicação de Lagrange,
nmidvarphi(p^n-1)

Resposta

a) A ordem de 2 em bmod(2^n-1) é n.
b) Logo varphi(2^n-1) é múltiplo de n.
c) Sim. Para todo primo p>1 vale também nmidvarphi(p^n-1).

Exercícios de Livros Relacionados