# 模n乘法階

gcd(a,n)=1時，ord_n(a)是a^k≡1 mod n的最小正整數k。

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



## 數學敘述

先核n≥2並normalize a mod n，gcd(a,n)=1。從k=1逐次建立完整power table到first return 1，禁止把任意return exponent當order。以完整residue enumeration計phi(n)，驗ord_n(a)|phi(n)。noncoprime與n<2時undefined；a≡1有order1，negative a先normalize。不自動宣稱order=phi、primitive root或混同additive order。





## 代表公式（精確 TeX）

M(a,n)=k





## 成立條件


- n與search範圍bounded exact integers。
- Euler theorem保證coprime case於phi(n)前回到1。





## 符號作用域


- M — 乘法階算子
- a — 整數剩餘類
- n — 模數
- k — 最小正回返指數





## 直觀、定義與常見誤解

normalize與coprime資格先行。

power table由k=1找到first return。

phi divisibility與undefined boundaries分開。

看到某次a^k=1就把k稱order，或對nonunit定義multiplicative order。





## 已採用的推導導讀

[第一個回到1的冪](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-multiplicative-order-mod-n-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [模反元素](https://ocme.evemisslab.com/zh-Hant/mko/mko-modular-inverse/) — unit qualification。
- [最大公因數與互質](https://ocme.evemisslab.com/zh-Hant/mko/mko-gcd-coprime/) — domain。
- [自然數整除](https://ocme.evemisslab.com/zh-Hant/mko/mko-natural-divisibility/) — order divides phi。
- [Euler定理](https://ocme.evemisslab.com/zh-Hant/mko/mko-euler-theorem-number-theory/) — return bound。





## 驗證界線

不推出primitive root或order=phi。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。





## 下一個義務

加入primitive roots與cyclic unit groups。





## 同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/multiplicative-order-mod-n.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-multiplicative-order-mod-n/index.md)