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 2 módulo 11;

Passo 1

O enunciado pede a ordem de 2 módulo 11, isto é, o menor inteiro positivo k tal que
2^k equiv 1 pmod11
Como gcd(2,11)=1, sabemos pelo Teorema de Euler que essa ordem divide varphi(11).

Passo 2

Calculamos varphi(11). Sendo 11 primo,
varphi(11)=11-1=10
Logo a ordem de 2 em bmod,11 deve ser um divisor de 10. Os divisores positivos de 10 são 1,2,5,10.

Passo 3

Testamos os divisores menores em ordem crescente:
2^1 = 2 equiv 2 pmod11(neq1),
2^2 = 4 equiv 4 pmod11(neq1)

Passo 4

O próximo divisor é 5. Calculamos
2^5 = 32 equiv 32 - 2cdot11 = 10 pmod11(neq1)
Como ainda não obtivemos 1, o próximo e último divisor possível é 10.

Passo 5

Verificamos para k=10:
2^10 = l(2^5r)^2 equiv 10^2 = 100 equiv 100 - 9cdot11 = 1 pmod11
Portanto, 10 é o menor expoente que dá resto 1.

Resposta

A ordem de 2 módulo 11 é 10.

Exercícios relacionados