# Euler定理

n>=2且gcd(a,n)=1時，a的phi(n)次方模n同餘於1。

mko-euler-theorem-number-theory · theorem · v0.10.0



## 數學敘述

exact列舉reduced residue system並核乘a造成permutation，或用safe modular exponentiation核a^phi(n) mod n=1。負a先正規化。nonunit不適用，單次congruence沒有primality converse；Fermat小定理是prime modulus特例。





## 代表公式（精確 TeX）

E(a,n)=1





## 成立條件


- n為至少2的正整數且gcd(a,n)=1。
- phi(n)與modular powers以exact integer arithmetic計算。





## 符號作用域


- phi — Euler phi函數
- a — 可逆剩餘類





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

unit hypothesis不可省略。

乘法在reduced residue system上為permutation。

single passing congruence不證prime。

對gcd(a,n)>1仍套Euler定理，或把結果反推n為質數。





## 已採用的推導導讀

[模10的完整unit排列](https://ocme.evemisslab.com/zh-Hant/derivations/derivation-mko-euler-theorem-number-theory-01/)原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。





## 前置知識


- [Euler φ函數](https://ocme.evemisslab.com/zh-Hant/mko/mko-euler-totient-function/) — exponent與reduced residues。
- [最大公因數與互質](https://ocme.evemisslab.com/zh-Hant/mko/mko-gcd-coprime/) — unit hypothesis。
- [自然數模同餘](https://ocme.evemisslab.com/zh-Hant/mko/mko-modular-congruence/) — 結論語義。
- [自然數冪與主平方根](https://ocme.evemisslab.com/zh-Hant/mko/mko-power-root/) — 整數冪。





## 驗證界線

本輪不把Euler congruence當primality test。

not_formalized

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





## 下一個義務

加入multiplicative order與Euler criterion。





## 同源結構化資料

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

[原始 MKO JSON](https://ocme.evemisslab.com/data/mko/euler-theorem-number-theory.json) · [純文字 Markdown](https://ocme.evemisslab.com/zh-Hant/mko/mko-euler-theorem-number-theory/index.md)