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(\mathrm{mod}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={\mathrm{ord}}_n(a)$ ou $k=O_n(a).$

Exemplo

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

$\begin{array}{cccc}{4}^0& =1& =0\times 7+1& \equiv 1(\mathrm{mod}7)\\ 4^1& =4& =0\times 7+4& \equiv 4(\mathrm{mod}7)\\ 4^2& =16& =2\times 7+2& \equiv 2(\mathrm{mod}7)\\ 4^3& =64& =9\times 7+1& \equiv 1(\mathrm{mod}7)\\ 4^4& =256& =36\times 7+4& \equiv 4(\mathrm{mod}7)\\ 4^5& =1024& =146\times 7+2& \equiv 2(\mathrm{mod}7)\end{array}$

$\text{etc...}$

O menor inteiro positivo $k$ tal que $4^k=1(\mathrm{m}\mathrm{o}\mathrm{d}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{m}\mathrm{o}\mathrm{d}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{m}\mathrm{o}\mathrm{d}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 ${𝐙}_n$; tem $\phi (n)$ elementos, sendo $\phi$ a função totiente de Euler, e é denotado como $U(n)$ ou $U({𝐙}_n)$.

Como consequência do teorema de Lagrange, ${\mathrm{ord}}_n(a)$ sempre divide $\phi (n)$. Se ${\mathrm{ord}}_n(a)$ for realmente igual a $\phi (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 ${\mathrm{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 $\phi (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)

• Predefinição:MathWorld