multiplicative order
mathematical function
≈ 1 min read
Names in other languages
- РусскийПоказатель числа по модулю
- УкраїнськаПоказник числа по модулю
- ItalianoOrdine moltiplicativo
- Englishmultiplicative order
- EspañolOrden multiplicativo
- FrançaisOrdre multiplicatif
- MagyarMultiplikatív rend
- Svenskaordning
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In number theory, given a positive integer n and an integer a coprime to n, the multiplicative order of a modulo n is the smallest positive integer k such that . In other words, the multiplicative order of a modulo n is the order of a in the multiplicative group of the units in the ring of the integers modulo n. The order of a modulo n is sometimes written as ord n (a). 4^0 &= 1 &=0 \times 7 + 1 &\equiv 1\pmod7 \\ 4^1 &= 4 &=0 \times 7 + 4 &\equiv 4\pmod7 \\ 4^2 &= 16 &=2 \times 7 + 2 &\equiv 2\pmod7 \\ 4^3 &= 64 &=9 \times 7 + 1 &\equiv 1\pmod7 \\ 4^4 &= 256 &=36 \times 7 + 4 &\equiv 4\pmod7 \\ 4^5 &= 1024 &=146 \times 7 + 2 &\equiv 2\pmod7 \\ \vdots\end{array} The smallest positive integer k such that is 3, so the order of is 3.
Note that a^0 = 1 \equiv 1 \pmod n is trivially true for any non-zero a , but since zero is not a positive integer, trivial solutions are not valid.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1363920538 under CC BY-SA 4.0; modifications have been made.