How this calculation works
When a and m are coprime, Euler’s totient φ(m) supplies a power known to return one. Test prime-factor reductions of that bound to find the smallest working positive exponent.
ordₘ(a) = min{k>0 : a^k ≡ 1 (mod m)}A worked example
For a = 2 modulo 9, the remainders cycle through 2,4,8,7,5,1. The first return to 1 is at exponent 6.
Good to know
Requires a and m to be coprime. Non-coprime powers can never enter the multiplicative group, so this page rejects them. It does not assess cryptographic suitability.
Reference: MIT OpenCourseWare: Theory of Numbers lecture notes (opens in a new tab) ↗
A power cycle starts at one
Modulo 9, successive powers of 2 give remainders 2,4,8,7,5,1. The first positive exponent returning to one is 6, so the order of 2 modulo 9 is 6. The modular exponentiation calculator can check any selected step of that cycle directly.
The order exists only when the residue and modulus are coprime. If a shares a factor with m, no power can become one modulo m; the form flags that input instead of reporting a misleading cycle length.
The Euler totient calculator supplies a bound on the order, while modular exponentiation checks each candidate remainder.
Reduce a proved bound
Euler’s totient calculator gives φ(9)=6. Euler’s theorem makes this a working exponent for every residue coprime to 9. The smallest working exponent divides φ(9), so testing its prime-factor reductions can find the order without checking every exponent in sequence.
The reduction table shows the attempted smaller candidate and its actual remainder. A candidate with remainder one replaces the current bound; a candidate that fails cannot reduce by that prime at the current step.
Order is not the same as base size
A larger base need not produce a longer period. Only its residue modulo m matters; values differing by a multiple of m have the same powers modulo m.
The bounded calculation illustrates arithmetic structure. A short or long period alone says nothing about whether a scheme using modular arithmetic is secure, random or suitable for encryption.
A few questions, answered
Can the order be zero?
No. It is defined as the smallest positive exponent returning remainder one.
Does it always equal φ(m)?
No. It divides φ(m) and can be strictly smaller.
Why reject a not coprime to m?
A power of a non-coprime residue cannot equal one modulo m, so no multiplicative order exists.