Ordem multiplicativa

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

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

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

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

Exemplo

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

${\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}}$

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

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

Propriedades

Mesmo sem saber que estamos trabalhando no grupo multiplicativo de inteiros módulo n, podemos mostrar que $a$ realmente tem uma ordem, observando que as potências de $a$ só podem assumir um número finito de diferentes valores módulo $n$, portanto, de acordo com o princípio da casa dos pombos deve haver duas potências, digamos $s$ e $t$ e sem perda de generalidade $s>t$, tal que $a^{s}\equiv a^{t}(\mathrm {mod} \ n)$. Como $a$ e $n$ são coprimos, isso implica que a tem um elemento inverso $a^{-1}$ e podemos multiplicar ambos os lados da congruência por $a^{-t}$, resultando em $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 $a$ módulo $n$ é a ordem de $a$ no grupo multiplicativo cujos elementos são os resíduos módulo $n$ dos números coprimos a $n$, e cuja operação de grupo é a multiplicação módulo $n$. Este é o grupo de unidades do anel $\mathbf {Z} _{n}$; tem $\varphi (n)$ elementos, sendo $\varphi$ a função totiente de Euler, e é denotado como $U(n)$ ou $U(\mathbf {Z} _{n})$.

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

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

Linguagens de programação

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

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