MultiplicativeOrder[k,n]
gives the multiplicative order of k modulo n, defined as the smallest integer 
such that 
.
MultiplicativeOrder[k,n,{r1,r2,…}]
gives the generalized multiplicative order of k modulo n, defined as the smallest integer 
such that 
for some 
.
MultiplicativeOrder
MultiplicativeOrder[k,n]
gives the multiplicative order of k modulo n, defined as the smallest integer 
such that 
.
MultiplicativeOrder[k,n,{r1,r2,…}]
gives the generalized multiplicative order of k modulo n, defined as the smallest integer 
such that 
for some 
.
Details
- 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. - For a FiniteFieldElement object a, MultiplicativeOrder[a] gives the multiplicative order of a, defined as the smallest positive integer m such that
is the multiplicative identity of the finite field.
Examples
open all close allBasic Examples (2)
The multiplicative order of 5 modulo 8:
MultiplicativeOrder[5, 8]Plot the sequence with a fixed modulus:
DiscretePlot[MultiplicativeOrder[k, 7], {k, 1, 50}]Plot the sequence, varying the modulus:
DiscretePlot[MultiplicativeOrder[7, n], {n, 1, 50}]Scope (7)
Numerical Evaluation (5)
MultiplicativeOrder[5, 7]MultiplicativeOrder[-5, 7]Generalized multiplicative order:
MultiplicativeOrder[5, 7, {3, 11}]MultiplicativeOrder[10 ^ 10000, 7919]Multiplicative order of finite field elements:
ℱ = FiniteField[1009, 7];
a = ℱ[1234]MultiplicativeOrder[a]a ^ %TraditionalForm formatting:
MultiplicativeOrder[k, n]//TraditionalFormSymbolic Manipulation (2)
Use Solve to find solutions of equations:
Solve[MultiplicativeOrder[17, n] == 2 && 0 < n < 15, n, Integers]Use FindInstance to find solutions:
FindInstance[MultiplicativeOrder[17, n] == MultiplicativeOrder[5, n], n, Integers]Applications (8)
Basic Applications (4)
Find all primitive roots modulo 43:
Select[Range[43], MultiplicativeOrder[#, 43] == EulerPhi[43]&]PrimitiveRootList[43]A rational number 
has a digit cycle of length 
if 
is prime and 10 is a primitive root for 
:
Select[Range[2, 500], Length[RealDigits[1 / #, 10][[1, -1]]] == # - 1&] == Select[Range[2, 500], MultiplicativeOrder[10, #] == # - 1&]Compute MultiplicativeOrder using NestWhileList:
ord[n_, m_] := NestWhileList[Mod[n #, m]&, Mod[n, m], Mod[#, m] != 1&]//LengthMultiplicativeOrder[4, 13] == ord[4, 13]Count number of possible multiplicative orders modulo a given prime number:
l1 = Table[Length[DeleteDuplicates[Table[MultiplicativeOrder[i, Prime[n]], {i, 1, Prime[n] - 1}]]], {n, 1, 50}];The number of divisors of 
where 
is prime:
l2 = Table[Length[Divisors[Prime[n] - 1]], {n, 1, 50}];These are in fact the same list:
l1 == l2Number Theory (4)
The repetition period in Rule 
for odd 
divides q[n]:
q[n_] = 2 ^ MultiplicativeOrder[2, n, {1, -1}] - 1;Table[q[n], {n, 3, 50, 2}]The digits of 
in base 
repeat with period 
:
With[{b = 4, n = 13}, MultiplicativeOrder[b, FixedPoint[# / GCD[#, b]&, n]]]With[{b = 4, n = 13}, RealDigits[1 / n, b, 20]]The function digitCycleLength gives the digit period for any rational number 
in base 
:
digitCycleLength[r_Rational, b_Integer ? Positive] :=
MultiplicativeOrder[b, FixedPoint[Quotient[#, GCD[#, b]]&, Denominator[r]]]This shows that the decimal representation of 
in base 10 repeats every 3 digits:
digitCycleLength[(123/999), 10]N[(123/999), 18]Build an RSA-like toy encryption scheme:
{p, q} = {47, 59};
n = p q;
ϕ = EulerPhi[n];
d = NestWhile[#1 + 1&, Round[n / 3], GCD[ϕ, #1] =!= 1&];
e = 17;
PlainText = 1504;
CypherText = PowerMod[PlainText, e, n];Perform a cycling attack. One of the outputs will be the plaintext:
Cy[1] = PowerMod[CypherText, e, n];
Cy[j_] := PowerMod[Cy[j - 1], e, n];
Table[Cy[i], {i, Divisors[MultiplicativeOrder[e, ϕ]]}]Properties & Relations (5)
The multiplicative order of a primitive root modulo n is EulerPhi[n]:
MultiplicativeOrder[PrimitiveRoot[109], 109] == EulerPhi[109]EulerPhi divides MultiplicativeOrder:
Divisible[EulerPhi[12], MultiplicativeOrder[5, 12]]The result is always positive:
MultiplicativeOrder[5, 3]MultiplicativeOrder[-5, 3]Find the smallest integer such that 
≡ 2, 3, or 4 mod 7:
MultiplicativeOrder[5, 7, {2, 3, 4}]Find which of the remainders satisfies 
:
PowerMod[5, 2, 7]Solve the discrete log problem with 
:
MultiplicativeOrder[5, 7, {4}]Possible Issues (1)
For nonzero integers k and n, MultiplicativeOrder[k,n] exists if and only if k and n are coprime:
CoprimeQ[10, 21]MultiplicativeOrder[10, 21]MultiplicativeOrder[21, 10]However, 10 and 22 are not coprime:
CoprimeQ[10, 22]MultiplicativeOrder[10, 22]MultiplicativeOrder[22, 10]Interactive Examples (1)
MultiplicativeOrder of each integer below a given prime number:
Manipulate[
DiscretePlot[MultiplicativeOrder[k, Prime[n]], {k, 1, Prime[n] - 1}],
{n, 10, 30, 1}]Neat Examples (2)
Visualize when a number has multiplicative order modulo 12:
ArrayMesh[Boole[Table[NumberQ[MultiplicativeOrder[a + b ^ 2 + c ^ 3, 12]], {a, 10}, {b, 10}, {c, 10}]]]Ulam spiral of MultiplicativeOrder:
ulam[n_] := Partition[Permute[Range[n ^ 2], Accumulate[Take[Flatten[{{n ^ 2 + 1} / 2, Table
[(-1) ^ j i, {j, n}, {i, {-1, n}}, {j}]}], n ^ 2]]], n]ArrayPlot[MapAt[MultiplicativeOrder[#, 61]&, ulam[101], {All, All}], ColorFunction -> "Rainbow"]Related Links
NKS|OnlineText
Wolfram Research (1999), MultiplicativeOrder, Wolfram Language function, https://reference.wolfram.com/language/ref/MultiplicativeOrder.html (updated 2023).
CMS
Wolfram Language. 1999. "MultiplicativeOrder." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2023. https://reference.wolfram.com/language/ref/MultiplicativeOrder.html.
APA
Wolfram Language. (1999). MultiplicativeOrder. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/MultiplicativeOrder.html