Seja n um inteiro positivo e 1 <= b <= n-1. Chamamos ordem de b módulo n ao menor inteiro positivo k para o qual
b^k equiv 1(bmod n)
Por exemplo, a ordem de 2 módulo 31 é igual a 5 pois 2^5 equiv 1(bmod 31), sendo 5 o menor inteiro positivo que satisfaz essa propriedade. Determine:
a ordem de 5 módulo 31;

Passo 1

O enunciado pede a ordem de 5 módulo 31, ou seja, o menor inteiro positivo k tal que
5^k equiv 1 pmod31
Isso envolve teoria de grupos multiplicativos em Z/31Z e o fato de 31 ser primo.

Passo 2

Como 31 é primo, pelo Teorema de Fermat temos
5^30 equiv 1 pmod31,
logo a ordem de 5 deve dividir phi(31)=30. Os divisores positivos de 30 são
1,2,3,5,6,10,15,30

Passo 3

Testamos em ordem crescente até achar 5^kequiv1pmod31:
5^1 = 5 notequiv 1pmod31,
5^2 = 25 notequiv 1pmod31,
5^3 = 125 equiv 125 - 4cdot31 = 125 -124 = 1 pmod31

Passo 4

Como 5^3equiv1pmod31 e não houve expoente menor que isso que gerasse 1, concluímos que a ordem de 5 módulo 31 é 3.

Resposta

3

Exercícios relacionados