Imgcity

外觀

Imgcity🧮 數學數論基礎符號和工具Wilson 定理

Wilson 定理 ​

Wilson 定理 ​

對於質數 p，我們有

(p−1)!≡−1 (mod p)

證明：

當 p=2,3 容易驗證，所以以下討論 p≥5：

在 mod p 底下，非零元素皆有唯一乘法反完素，所以要確認反元素為自己的 (x−1≡x) 的是那些，然後從 0...p−1 之間把他們抽出即可。

x2≡1 (mod p)⇒p∣x2−1⇒x≡1,(p−1)

所以，除去 1,p−1 剩下的元素乘起來為 1：

(p−1)!≡1×(p−1)≡−1 (mod p)

Fermat 小定理 ​

ap−1≡1 (mod p) when p∤a

和 Wilson 定理有關的證明 ​

第一個等號是把 a 乘進 (p−1)!，第二個是因為 a,2a... 在 mod p 底下是另一個 1...p−1 的排列(因為兩兩不同餘)。

ap−1(p−1)!=a(2a)...((p−1)a)≡(p−1)!

兩邊同時削掉 (p−1)!就可以得證。

另一個證明 ​

令 f(x)=xp−x，可以發現 p∣f(x+1)−f(x)：

f(x+1)−f(x)=(x+1)p−(x+1)−(xp−x)=∑i=1p−1Cipxi

然後因為 f(0)=0就可以知道 p∣f(x) ∀x。

習題 ​

  1. 給定 a 和質數 p ，若 ap−12≢1 (mod p)，則不存在 x 使得 x2≡a (mod p)。

頁面歷史

Just observe 👀