Multiplicative Order - Maple Help

Home : Support : Online Help : Mathematics : Number Theory : Multiplicative Order

NumberTheory

 MultiplicativeOrder
 order of a number under modular multiplication

 Calling Sequence MultiplicativeOrder(m, n)

Parameters

 m - positive integer n - positive integer greater than 1

Description

 • The MultiplicativeOrder function computes the multiplicative order of m modulo n, which is defined as the least positive integer exponent i such that m^i is congruent to $1$ modulo n.
 • Alternatively, the multiplicative order can be defined as the order of the cyclic group generated by m under multiplication modulo n.
 • The multiplicative order exists if and only if m and n are coprime. In the case that it does not exist, an error message is displayed.

Examples

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$
 > $\mathrm{MultiplicativeOrder}\left(7,18\right)$
 ${3}$ (1)
 > $\mathrm{seq}\left({7}^{i}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}\mathbf{mod}\phantom{\rule[-0.0ex]{0.5em}{0.0ex}}18,i=1..3\right)$
 ${7}{,}{13}{,}{1}$ (2)

If the multiplicative order of m is equal to the totient of n, then m is a primitive root modulo n.

 > $\mathrm{Totient}\left(18\right)$
 ${6}$ (3)
 > $\mathrm{MultiplicativeOrder}\left(11,18\right)$
 ${6}$ (4)
 > $\mathrm{PrimitiveRoot}\left(18,\mathrm{greaterthan}=10\right)$
 ${11}$ (5)

Since $5$ and $25$ are not coprime, the multiplicative order of $5$ modulo $25$ is not defined.

 > $\mathrm{MultiplicativeOrder}\left(5,25\right)$

Compatibility

 • The NumberTheory[MultiplicativeOrder] command was introduced in Maple 2016.