Wilson定理、費馬小定理、尤拉定理(筆記)

Wilson’s Theorem：

設p為質數，則(p－1)!≡－1 mod p。

Pf:

首先證明：若正整數i＜p，則必存在一正整數j＜p，使得ij≡1 mod p。

因為i、p互質，所以由輾轉相除法原理(Euclidean’s Algorithm)可推得，存在整數m和n，使得mi＋np＝1，即mi≡1 mod p，故只要取j＜p且j≡m mod p即可。

接下來證明，若i²≡1 mod p，則i≡±1 mod p：

這也很容易，因為若p∣i²－1＝(i＋1)(i－1)，又p是質數，所以p∣i＋1或p∣i－1，即i≡1或i≡－1 mod p。

也就是說，若i是小於p的自然數，且i²≡1 mod p，則i必為1或p－1，而其他小於p的正整數，必定可以兩兩配成一對，使得相乘後模p會同餘1，故得(p－1)!≡1×(p－1)≡－1 mod p。

費馬小定理(Fermat’s Little Theorem)：

設p為質數，a為與p互質的整數，則a^p-1≡1 mod p。

Pf:

考慮a、2a、3a、…、(p－1)a。顯然，這些數也與p互質。又若ia≡ja mod p，則p∣(i－j)a，但a和p互質，所以p∣i－j，即i≡j mod p。故可知{a、2a、3a、…、(p－1)a}≡{1、2、3、…、p－1} mod p，也就是說，a、2a、3a、…、(p－1)a這p－1個數在模p之下，只是1、2、3、…、p－1變換次序的結果。因此，a×(2a)×(3a)×…×((p－1)a)≡1×2×3×…×(p－1) mod p，即(p－1)!a^p-1≡(p－1)! mod p。因為(p－1)!和p互質，所以a^p-1≡1 mod p。(或由Wilson’s Theorem知，(p－1)!≡－1 mod p，所以(p－1)!a^p-1≡－a^p-1≡－1 mod p，故a^p-1≡1 mod p。)

將費馬小定理推廣，將質數p改成任意的整數n，即為尤拉定理。

尤拉定理(Euler-Fermat’s Theorem)：

設n為自然數，a為與n互質的整數，則a^φ(n)≡1 mod n，其中φ為尤拉φ函數。

Pf:

令x₁、x₂、…、x_φ(n)為不大於n且與n互質的所有相異自然數，則x₁a、x₂a、…、x_φ(n) a都與n互質，且若x_ia≡x_ja mod n，則n∣x_ia－x_ja＝(x_i－x_j)a，但n與a互質，又x_i和x_j都是不大於n的自然數，所以x_i＝x_j。因此x₁a、x₂a、…、x_φ(n) a在模n下，是x₁、x₂、…、x_φ(n)的重排，故(x₁a)×(x₂a)×…×(x_φ(n) a)≡x₁×x₂×…×x_φ(n) mod n，即n∣(a^φ(n)－1)(x₁×x₂×…×x_φ(n))，又n與x₁×x₂×…×x_φ(n)互質，所以n∣(a^φ(n)－1)，即a^φ(n)≡1 mod n。