Multiplicative order modulo n

Mathematical statement

Require n≥2, normalize a modulo n and check gcd(a,n)=1 first. Starting at k=1, build the complete power table through the first return to 1; an arbitrary return exponent is not the order. Count phi(n) by complete residue enumeration and verify ord_n(a)|phi(n). Noncoprime residues and n<2 have undefined order here. a≡1 has order 1, and a negative a is normalized first. Do not infer order=phi(n), a primitive root or additive order.

Representative formula (exact TeX)

M(a,n)=k

Assumptions

• n and the search range are bounded exact integers.
• Euler theorem guarantees a coprime return by phi(n).

Symbol scope

• M — multiplicative-order operator
• a — integer residue
• n — modulus
• k — least positive return exponent

Intuition, definition, and misconceptions

Normalize and qualify coprimality first.

Start at exponent1 and retain the first return power table.

Separate phi divisibility from undefined-domain boundaries.

Seeing a^k=1 at some exponent does not make k the least positive return, and nonunits do not have this multiplicative order.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Modular inverse — Qualify a unit.
• Greatest common divisor and coprimality — Specify the domain.
• Natural-number divisibility — Check order divides phi.
• Euler's theorem in number theory — Use the return bound.

Verification boundary

No primitive-root conclusion or equality between order and phi is automatic.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Add primitive roots and cyclic unit groups.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.