证明:n为素数则(n—1)!≡—1(modn)

Question

证明:n为素数则(n—1)!≡—1(modn)

Answer 1

此题的证明,需先假设以下结论成立,即
若a,b是正整数,且（a,b）=d(最大公因数),则必存在整数m和k
使得d=ma+kb ,
当a,b互素时d=1,结论变为存在整数m和k,使得1=ma+kb成立.
以下证明(n—1)!≡—1(modn)
n为一素数,当n=2,3时,结论显然成立.
现设n>3是一奇素数,S={2,3,…,n-2},a∈S.
因为(a,n)=1,存在整数m和k,使am+nk=1,
令m＝nq＋b,0≤b＜n,下面说明b≠1,b≠n－1,b≠a.
若b＝a,则有anq＋a^2＋nk＝1,n|(a^2－1),此不可能,所以b≠a.
若b＝1,则有anq＋a＋nk＝1,n|(a-1),此不可能,所以b≠1.
同理,b≠n－1
于是b∈S且b≠a.
因为ab＝1－anq－nk,所以ab≡1(mod n).
由于S中的数可分成(p-3)/2对,
每一对数a和b,满足ab≡1(mod n),
故得
2·3…(n-2) ≡ 1(mod n),
(n-1)≡-1(mod n)
将上两式相乘即可得(n-1)!≡ -1 (mod n).
下面证明“若a,b是正整数,且（a,b）=d(最大公因数),则必存在整数m和k,使得d=ma+kb”.
设两数b＜a,求它们最大公约数(a、b)的步骤如下：用b除a,得a＝bq1＋r1（0≤r＜b）.若r1=0,则(a,b)＝b；若r1≠0,则再用r1除b,得b＝rq2＋r2（0≤r2＜r1）.若r2＝0,则(a,b)＝r1,若r2≠0,则继续用r2除r1,……如此下去,直到能整除为止.其最后一个非零余数即为(a,b).
即,
a=bq1+r1(0