Wilson 定理|大學三年級|數學學院

觀念

Wilson 定理:對整數 $p>1$ , $p$ 是質數 ⟺ $(p-1)!\equiv-1\pmod p$ 。證明的關鍵是把 $1$ 到 $p-1$ 兩兩配成互為反元素的對(只有 $1$ 與 $p-1$ 是自己的反元素),乘積就剩 $1\cdot(p-1)\equiv-1$ 。

它是少數「若且唯若」的質數刻畫,但算階乘太慢,實務上不用來判質數;真正的價值在證明技巧(配對論證)與推論,如質數 $p\equiv1\pmod4$ 時 $-1$ 是模 $p$ 的二次剩餘。

求 $39! \bmod 41$ (填最小非負餘數)。

看解法與答案

Wilson: $40! = 40\cdot 39! \equiv -1$ 。而 $40\equiv -1$ ,所以 $-39!\equiv -1$ , $39!\equiv 1\pmod{41}$ 。

重點:不用真的算階乘,把 $p-1, p-2, \ldots$ 換成 $-1, -2, \ldots$ 再用 $(p-1)!\equiv -1$ 。

答案:

1

金融交易所產生 RSA 金鑰不用 Wilson 定理判質數,因為 2048 位元的 $(p-1)!$ 根本算不完,正確不等於可行。
電腦Wilson 定理 $(p-1)!\equiv-1\pmod p$ 是完美的質數判準,但驗證 20 位數就要做天文數字次乘法,實務改用 Miller–Rabin。

這個網站是觀念與例題的閱讀版。互動練習(每次出不同數字的新題、自動判對錯、錯題本、熟練度與複習排程)在「數學學院」本機版,目前還沒對外開放。