Multiplicative Order

Factorization difficulty depends on the size of the factors of n and of λ(n), not just the size of the input. If a factorization is incomplete the exact order is not shown. Computation runs locally in your browser.

The multiplicative order of a modulo n is defined when gcd(a, n) = 1. It is the smallest positive integer r satisfying

The order divides the Carmichael function, ord_n(a) | λ(n), and λ(n) | φ(n), so λ(n) is the better starting exponent. The calculator factors n, computes λ(n), finds the prime factorization of λ(n) by factoring p − 1 for each prime p of n (every prime of λ(n) divides one of them or is a repeated prime of n), and begins with r = λ(n). For each prime q dividing r, in increasing order, it checks whether

If so, the order divides r/q, so one copy of q is removed from r, and the test is repeated with the same q. If not, that copy of q is necessary and the calculator moves on to the next prime. When no prime can be removed, r is the order.

The result is checked independently: a^r ≡ 1 (mod n), and a^(r/q) ≢ 1 (mod n) for every prime q dividing r. These two facts prove minimality: if a proper divisor s of r satisfied a^s ≡ 1, then for some prime q dividing r/s the exponent r/q would be a multiple of s, so a^(r/q) ≡ 1, a contradiction.

If a is not congruent to a unit, that is gcd(a, n) ≠ 1, the order is undefined and no factoring is done. If a ≡ 1 the order is 1, and if a² ≡ 1 with a ≢ 1 it is 2, both without factoring.

The value ord_n(a) is the order of the element represented by a in the multiplicative group of units modulo n, (ℤ/nℤ)^×. If ord_n(a) = φ(n), then a generates the whole group of units, which is possible only when that group is cyclic; such an element is called a primitive root. Not every modulus has one.

Related: Modular Exponentiation · Carmichael Function · Euler Totient · Prime Factorization