一題同餘與階乘的證明題

Q:

一題同餘與階乘的證明題

已知P為質數

試證明：

(P-1)!≡(-1) (mod P)

Sol:

證明[Wilson定理]

法1:

1,2,3,一直到p－1這p－1個元素

在mod p下進行乘法

可以構成一個有限群

單位元是1

只有在k=1或 k= p－1時

元素p－k才會是自身的反元素

其他元素的反元素都是群中的另一個元素

p是質數

所以p-1是偶數

1×2×乘到p－1這偶數個相乘

除了1和p－1以外

2×3×4乘到p-2其實是一組一組的元素和反元素相乘

所以

1×2×乘到p－1＝1×（p－1）＝－1

http://tw.knowledge.yahoo.com/question/question?qi...

法2:

即證：若p為質數，則 (p-1)!≡－1 (mod p)　　→即[Wilson定理]

即證：若p為質數，則 (p-2)!≡1 (mod p)　　→因為(p-1)≡－1

p=2，3時顯然成立。

p>3時(p大於等於5)，對2,3,…,(p-2)中任一個數a，必存在另一個數b，使得ab≡1 (mod p)，且a不同餘於b (mod p)。(註1)

∴2,3,…,(p-2)可兩兩配對相乘，皆同餘於1

=>23…(p-2)≡1 (mod p)

=>(p-2)!≡1 (mod p)

故得證。

http://tw.knowledge.yahoo.com/question/question?qi...

By hy

2010-05-13 05:40:44 補充：

法1:

更正:1×2×乘到p－1＝1×（p－1）!＝－1

請搜尋wilson定理,一堆文章都有證明