# Multiplicative order modulo n

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

For gcd(a,n)=1, the multiplicative order is the smallest positive k with a^k congruent to1 modulo n.

mko-multiplicative-order-mod-n · definition · v0.10.0



## 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 first power returning to one](https://ocme.evemisslab.com/en/derivations/derivation-mko-multiplicative-order-mod-n-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Modular inverse](https://ocme.evemisslab.com/en/mko/mko-modular-inverse/) — Qualify a unit.
- [Greatest common divisor and coprimality](https://ocme.evemisslab.com/en/mko/mko-gcd-coprime/) — Specify the domain.
- [Natural-number divisibility](https://ocme.evemisslab.com/en/mko/mko-natural-divisibility/) — Check order divides phi.
- [Euler's theorem in number theory](https://ocme.evemisslab.com/en/mko/mko-euler-theorem-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.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/multiplicative-order-mod-n.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-multiplicative-order-mod-n/index.md)