2012年12月28日星期五

Wilson's theorem

數學題:如 p|(p - 1)! + 1,証明p一定是prime。

初看這條題目熟口熟面,印像中在某theorem中看過,但又不想Wikipedia找答案,於是試試自行解決。

is_prime=lambda x: (math.factorial(x-1)+1) % x == 0

利用這個Python lambda,試了很多例子,若輸入的number是prime,的確return true,但為何呢?

以5為例,(n - 1)! = 4 × 3 × 2 × 1

除1以外,每個數都有multiplicative inverse,如3的multiplicative inverse是2,3 × 2 ≡ 1 (mod 5),4的inverse是自己,4 × 4 ≡ 1 (mod 5)。

再以7為例,(n - 1)! = 6 × 5 × 4 × 3 × 2 × 1

5的inverse是3,4的inverse是2,它們相乘全是1,餘下的只有一個number在factorial中沒有inverse,就是n - 1,n - 1  ≡ -1 (mod n)。

如果是composite呢,以10為例,它的餘數1至9當中,2,4,5,6和8都沒有inverse,只有3和7是multiplicative inverse,所以不會餘-1。

而這就是Wilson's theorem,但因要計算p的factorial,計算量十分大,所以並不適合作為Primality test

沒有留言:

發佈留言