Multiplikativní objednávka - Multiplicative order

v teorie čísel, vzhledem k celé číslo A a kladné celé číslo n coprime na A, multiplikativní pořadí z A modulo n je nejmenší kladné celé číslo k s

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

Jinými slovy, multiplikativní pořadí A modulo n je objednat z A v multiplikativní skupina z Jednotky v prsten celých čísel modulo n.

Pořadí A modulo n je obvykle psáno jako ${ displaystyle k = operatorname {ord} _ {n} (a)}$ nebo ${ displaystyle k = O_ {n} (a).}$

Příklad

Síly 4 modulo 7 jsou následující:

${ displaystyle { begin {array} {llll} 4 ^ {0} & = 1 & = 0 krát 7 + 1 & equiv 1 { pmod {7}} 4 ^ {1} & = 4 & = 0 krát 7 + 4 & ekviv 4 { pmod {7}} 4 ^ {2} & = 16 & = 2 krát 7 + 2 & ekviv 2 { pmod {7}} 4 ^ {3} & = 64 & = 9 krát 7 + 1 & ekviv 1 { pmod {7}} 4 ^ {4} & = 256 & = 36 krát 7 + 4 & ekviv 4 { pmod {7}} 4 ^ { 5} & = 1024 & = 146 krát 7 + 2 & ekviv 2 { pmod {7}} konec {pole}}}$

${ displaystyle , { text {atd ...}}}$

Nejmenší kladné celé číslo k tak, že 4^k = 1 (mod 7) je 3, takže Ó₇(4) = 3.

Vlastnosti

I bez vědomí, že pracujeme v multiplikativní skupina celých čísel modulo n, můžeme to ukázat A ve skutečnosti má pořádek tím, že uvádí, že pravomoci A může modulo přijímat pouze konečný počet různých hodnot n, tak podle princip pigeonhole musí existovat dvě síly, řekněme s a t a bez ztráty obecnosti s > t, takový, že A^s ≡ A^t (modn). Od té doby A a n jsou coprime, z toho vyplývá, že A má inverzní prvek A⁻¹ a můžeme obě strany kongruence znásobit A^−t, poddajný A^s−t ≡ 1 (modn).

Koncept multiplikativní objednávky je zvláštním případem pořadí skupinových prvků. Multiplikativní pořadí čísla A modulo n je řád A v multiplikativní skupina jehož prvky jsou zbytky modulo n z čísel coprime do n, a jehož skupinová operace je multiplikační modulon. To je skupina jednotek z prsten Z_n; má to φ(n) prvky, přičemž φ je Eulerova totientová funkce a je označen jako U(n) neboU(Z_n).

Jako důsledek Lagrangeova věta, ord_n(A) vždy rozděluje φ(n). Pokud je ord_n(A) je ve skutečnosti rovno φ(n), a tedy tedy co největší A se nazývá a primitivní kořen modulo n. To znamená, že skupina U(n) je cyklický a třída reziduí A generuje to.

Objednávka ord_n A také dělí λ (n), hodnota Funkce Carmichael, což je ještě silnější prohlášení než dělitelnostφ(n).

Programovací jazyky

• Maxima CAS : zn_order (a, n)^[1]
• Rosettský kód - příklady multiplikativního pořadí v různých jazycích^[2]

Viz také

• Diskrétní logaritmus
• Modulární aritmetika
• Objednávka (teorie skupin)
• Kongruenční vztah (modulární aritmetika)

Reference

• Weisstein, Eric W. „Multiplikativní objednávka“. MathWorld.