Euler定理

數學敘述

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為質數。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• Euler φ函數 — exponent與reduced residues。
• 最大公因數與互質 — unit hypothesis。
• 自然數模同餘 — 結論語義。
• 自然數冪與主平方根 — 整數冪。

驗證界線

本輪不把Euler congruence當primality test。

not_formalized

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

下一個義務

加入multiplicative order與Euler criterion。

同源結構化資料

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