Multiplicative Order Calculator

Don't test all k up to φ(n). Instead: (1) Factor φ(n) = p₁^e₁·...·pₖ^eₖ. (2) Start with d=φ(n). (3) For each prime factor p of d: if a^(d/p) ≡ 1, replace d with d/p. (4) Final d is the order. This runs in O(log²n · #factors).

By Euler's theorem, a^φ(n) ≡ 1 (mod n) for gcd(a,n)=1. If ord(a)=k, then k|φ(n) because: dividing φ(n)=qk+r gives a^r ≡ 1, and since k is minimal, r=0. This is the division algorithm applied to group theory.

For prime p: orders must divide p−1. All divisors d of p−1 occur, with exactly φ(d) elements of order d. For composite n: possible orders are more restricted and depend on the structure of (Z/nZ)* as a product of cyclic groups.