gives the multiplicative order of k modulo n, defined as the smallest integer such that .
gives the generalized multiplicative order of k modulo n, defined as the smallest integer such that for some .
- MultiplicativeOrder is also known as modulo order or haupt‐exponent.
- Integer mathematical function, suitable for both symbolic and numerical manipulation.
- Typically used in modular arithmetic and cryptography.
- MultiplicativeOrder[k,n] gives the smallest positive integer m such that the remainder when dividing km by n is equal to 1.
- MultiplicativeOrder returns unevaluated if there is no integer satisfying the necessary conditions.
Examplesopen allclose all
Basic Examples (2)
Numerical Manipulation (4)
Generalized multiplicative order:
Symbolic Manipulation (2)
Use Solve to find solutions of equations:
Use FindInstance to find solutions:
Basic Applications (5)
Find all primitive roots modulo 43:
A rational number has a digit cycle of length if is prime and 10 is a primitive root for :
Compute MultiplicativeOrder using NestWhileList:
Count number of possible multiplicative orders modulo a given prime number:
The number of divisors of where is prime:
Number Theory (4)
The repetition period in Rule for odd divides q[n]:
The digits of in base repeat with period :
The function digitCycleLength gives the digit period for any rational number in base :
This shows that the decimal representation of in base 10 repeats every 3 digits:
Build an RSA-like toy encryption scheme:
Perform a cycling attack. One of the outputs will be the plaintext:
Properties & Relations (5)
The multiplicative order of a primitive root modulo n is EulerPhi[n]:
EulerPhi divides MultiplicativeOrder:
The result is always positive:
Find the smallest integer such that ≡ 2, 3, or 4 mod 7:
Find which of the remainders satisfies :
Possible Issues (1)
For nonzero integers k and n, MultiplicativeOrder[k,n] exists if and only if k and n are coprime:
Interactive Examples (1)
MultiplicativeOrder of each integer below a given prime number:
Neat Examples (2)
Visualize when a number has multiplicative order modulo 12:
Ulam spiral of MultiplicativeOrder:
Wolfram Research (1999), MultiplicativeOrder, Wolfram Language function, https://reference.wolfram.com/language/ref/MultiplicativeOrder.html.
Wolfram Language. 1999. "MultiplicativeOrder." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/ref/MultiplicativeOrder.html.
Wolfram Language. (1999). MultiplicativeOrder. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/MultiplicativeOrder.html