Euler二次剩餘判準

數學敘述

domain先要求odd prime p及a mod p非零。Legendre值必須由完整nonzero square table獨立重算；modular exponent以repeated squaring獨立計算，再把p-1解讀為-1。residue case輸出+1，nonresidue輸出-1。完整有限square table只核指定p與a，不能取代全體奇質數上的一般定理證明。p=2、composite modulus與a≡0 mod p不屬本定理domain；不得反過來用Euler criterion定義Legendre symbol，composite modulus也無此一般converse。

代表公式（精確 TeX）

P(a,p)=L(a,p)

成立條件

• p為bounded odd prime；a為safe integer並先normalize。
• square-table與powmod使用兩條獨立計算路徑。

符號作用域

• P — 半指數冪剩餘
• a — 整數參數
• p — 奇質數模數
• L — Legendre符號

直觀、定義與常見誤解

domain qualification先於公式。

square-table與half exponent比對避免循環定義。

zero、even與composite boundaries分離。

把zero class套成+1、對composite modulus照搬判準，或用判準自身定義Legendre。

已採用的推導導讀

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

前置知識

• Euler定理 — 非零mod-p群中的冪關係。
• 二次剩餘 — square classification。
• Legendre符號 — 三值編碼。

驗證界線

本輪不物化Jacobi symbol、quadratic reciprocity或一般合數平方根判定。

not_formalized

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

下一個義務

加入二次互反律與Jacobi符號。

同源結構化資料

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