Ordem multiplicativa

Na teoria dos números, dado um inteiro ${\displaystyle a}$ e um inteiro positivo ${\displaystyle n}$ coprimo com ${\displaystyle a}$, a ordem multiplicativa de ${\displaystyle a}$ módulo ${\displaystyle n}$ é o menor inteiro positivo ${\displaystyle k}$ com

${\displaystyle a^{k}\ \equiv \ 1{\pmod {n}}\,}$

Em outras palavras, a ordem multiplicativa de ${\displaystyle a}$ módulo ${\displaystyle n}$ é a ordem de ${\displaystyle a}$ no grupo multiplicativo das unidades no anel dos inteiros módulo ${\displaystyle n}$.

A ordem de ${\displaystyle a}$ módulo ${\displaystyle n}$ é geralmente escrita como ${\displaystyle k=\operatorname {ord} _{n}(a)}$ ou ${\displaystyle k=O_{n}(a).}$

Exemplo

As potências do 4 módulo 7 são as seguintes:

${\displaystyle {\begin{array}{llll}4^{0}&=1&=0\times 7+1&\equiv 1{\pmod {7}}\\4^{1}&=4&=0\times 7+4&\equiv 4{\pmod {7}}\\4^{2}&=16&=2\times 7+2&\equiv 2{\pmod {7}}\\4^{3}&=64&=9\times 7+1&\equiv 1{\pmod {7}}\\4^{4}&=256&=36\times 7+4&\equiv 4{\pmod {7}}\\4^{5}&=1024&=146\times 7+2&\equiv 2{\pmod {7}}\\\end{array}}}$

${\displaystyle \,{\text{etc...}}}$

O menor inteiro positivo ${\displaystyle k}$ tal que ${\displaystyle 4^{k}=1\ (\mathrm {mod} \ 7)}$ é ${\displaystyle 3}$, então ${\displaystyle \mathrm {O} _{7}(4)=3}$.

Propriedades

Mesmo sem saber que estamos trabalhando no grupo multiplicativo de inteiros módulo n, podemos mostrar que ${\displaystyle a}$ realmente tem uma ordem, observando que as potências de ${\displaystyle a}$ só podem assumir um número finito de diferentes valores módulo ${\displaystyle n}$, portanto, de acordo com o princípio da casa dos pombos deve haver duas potências, digamos ${\displaystyle s}$ e ${\displaystyle t}$ e sem perda de generalidade ${\displaystyle s>t}$, tal que ${\displaystyle a^{s}\equiv a^{t}(\mathrm {mod} \ n)}$. Como ${\displaystyle a}$ e ${\displaystyle n}$ são coprimos, isso implica que a tem um elemento inverso ${\displaystyle a^{-1}}$ e podemos multiplicar ambos os lados da congruência por ${\displaystyle a^{-t}}$, resultando em ${\displaystyle a^{s-t}\equiv 1(\mathrm {mod} \ n)}$.

O conceito de ordem multiplicativa é um caso especial da ordem dos elementos do grupo. A ordem multiplicativa de um número ${\displaystyle a}$ módulo ${\displaystyle n}$ é a ordem de ${\displaystyle a}$ no grupo multiplicativo cujos elementos são os resíduos módulo ${\displaystyle n}$ dos números coprimos a ${\displaystyle n}$, e cuja operação de grupo é a multiplicação módulo ${\displaystyle n}$. Este é o grupo de unidades do anel ${\displaystyle \mathbf {Z} _{n}}$; tem ${\displaystyle \varphi (n)}$ elementos, sendo ${\displaystyle \varphi }$ a função totiente de Euler, e é denotado como ${\displaystyle U(n)}$ ou ${\displaystyle U(\mathbf {Z} _{n})}$.

Como consequência do teorema de Lagrange, ${\displaystyle \operatorname {ord} _{n}(a)}$ sempre divide ${\displaystyle \varphi (n)}$. Se ${\displaystyle \operatorname {ord} _{n}(a)}$ for realmente igual a ${\displaystyle \varphi (n)}$ e, portanto, o maior possível, então ${\displaystyle a}$ é chamado de raiz primitiva módulo n. Isso significa que o grupo ${\displaystyle U(n)}$ é cíclico e a classe de resíduos de ${\displaystyle a}$ o gera.

A ordem ${\displaystyle \operatorname {ord} _{n}(a)}$ também divide ${\displaystyle \lambda (n)}$, um valor da função de Carmichael, que é uma afirmação ainda mais forte do que a divisibilidade de ${\displaystyle \varphi (n)}$.

Linguagens de programação

• Maxima CAS : zn_order (a, n)^[1]
• Rosetta Code - exemplos de ordem multiplicativa em várias línguas^[2]

Ver também

• Logaritmo discreto
• Aritmética modular
• Ordem (teoria dos grupos)
• Relação de congruência (aritmética modular)

Referências

• Weisstein, Eric W. «Multiplicative Order» (em inglês). MathWorld 

• Portal da matemática