Multiplicative order calculator

Enter an integer base a and a modulus n, and the result includes the reduced base, Euler’s totient, the order, and a direct modular check. The calculation is defined only when a and n are coprime, so invalid pairs produce a clear error instead of a misleading number. It is useful for modular arithmetic exercises, cyclic subgroup analysis, recurring patterns, and elementary number theory.

What multiplicative order means

For integers a and n, the multiplicative order of a modulo n is the least positive integer k such that a^k leaves remainder 1 when divided by n. The phrase “least positive” matters: many later exponents may also produce 1, but the order is the first return to the identity in modular multiplication. For example, powers of 2 modulo 9 have residues 2, 4, 8, 7, 5, and then 1, so the order is 6. The concept describes the size of the cyclic subgroup generated by a among the invertible residue classes modulo n. This calculator reduces a to its standard nonnegative residue before doing any work, which means negative bases and bases larger than n are handled consistently. It also returns a check value computed from the reported order. A check of 1 confirms the defining congruence, while the reduction process ensures no proper divisor left in the candidate exponent can satisfy it.

Why coprimality is required

A multiplicative order modulo n exists only when gcd(a, n) is 1. This is not merely an input convention. An element must have a multiplicative inverse modulo n before its powers can belong to the finite group of units and return to 1. If a and n share a factor, every positive power of a retains a compatible divisibility obstruction, so it cannot be congruent to 1 modulo n. The calculator tests this condition immediately and reports the actual greatest common divisor when the condition fails. The modulus must also be at least 2, because the usual order problem is posed in a nontrivial residue system. The base may be zero, negative, or positive within the published bound, but zero succeeds only in no allowed modulus because it is never coprime to n. When preparing input, use exact integers rather than decimals or scientific approximations. This preserves the discrete arithmetic on which gcd, factorization, and modular powers depend.

How the calculator finds the smallest exponent

The calculator does not test every exponent one after another. It first factors n sufficiently to compute Euler’s totient phi(n). Euler’s theorem guarantees that a raised to phi(n) is congruent to 1 whenever gcd(a, n) is 1, so the desired order must divide phi(n). The algorithm then factors phi(n) and repeatedly asks whether dividing the current candidate by one of its prime factors still produces a modular power equal to 1. Whenever it does, the smaller candidate replaces the old one. After no prime factor can be removed, the remaining candidate is the multiplicative order. Modular exponentiation uses repeated squaring, keeping intermediate values reduced modulo n, and integer arithmetic is exact throughout. This approach is substantially faster than walking through every positive exponent, especially when the order is large. Inputs are bounded at one trillion so trial factorization has a clear deterministic ceiling suitable for both the browser tool and automated API calls.