※ 引述《wwiillllyy (戀嵐)》之銘言：
: <維基百科> http://zh.wikipedia.org/zh-tw/%E8%B2%BB%E9%A6%AC%E5%B0%8F%E5%AE%
: 9A%E7%90%86
: 若n不能整除a - b，x>0，(x,n)=1，則n也不能整除x(a-b)
: 取整數集A為所有小於p的集（A構成p的完全剩餘系,即A中不存在兩個數同餘p）
: B是A中所有的元素乘以a組成的集合
: 因為A中的任何兩個元素之差都不能被p整除
: 所以B中的任何兩個元素之差也不能被p整除
: 因此
: 1*2*3*...*(p-1)同餘(1*a)(2*a)(3*a)*...*[(p-1)*a] (mod p)
: 即
: p-1
: W 同餘 W * a (mod p)
: 在這裡W=123...(p-1)，且(W, p) = 1，因此將整個公式除以W即得到：
: p-1
: a 同餘 1 (mod p)
: 想問一下
: 1.那個 p 一定要質數嗎?
: 還是只要 (a,p)=1就好?
如果不是質數的話,那我們可以找一反例:
a = 3, p = 10
10-1 9
=> 3 = 3 = 19683(想偷懶,就打計算機吧^ ^) ≡ 3 (mod 10)(被10除餘3)
如此一來就不成立,實際上如果用尤拉定理,可以知道
4
3 ≡ 1(mod 10) (上面的次方是小於10且與10互質的正整數數量,
以這個例子來說:小於10且和10互值的數有1,3,7,9,有4個)
但是4不是10的因數,所以自然無法得到同餘於1的結果
**所以 p 一定要是質數**
: 2.為甚麼 W 一定要是 1*2*3*...*(p-1)?
: 假如是 1*2*3*...*(p-2) 會不合嗎?
: 其它情況呢?
其實這和證明的解題精神有關,因為你希望1*2*3*...*(p-1)和a,2a,3a,...(p-1)a
被p除後,可得相同的餘數
但是你的a被p除後不一定和1被p除所得的餘數相同,但你知道a除p的餘數必定落在
1到p-1之間(因為已假設a不能被p整除
( (a,p)=1 => p不是a的因數(可用反證法) =>a不能被p整除 )
但是你現在唯一的訊息是:任何數被p除,餘數都會落於1到p-1之中,
如果你只取p-2個,那a,2a,3a,...,(p-2)這個序列中的每個數被p除,
不見得會得到餘數1,2,...,(p-2),可能中間會有一些會漏掉(就是餘數是p-1,
而不是1,2,...,(p-2)的某一個)
如此一來,等式就不會成立了(所以其他情況也一樣)
另外,ma和na, m,n < p,不可能會得到 ma≡na(mod p),
因為如果是的話,則 p | (m-n)a
又因為 (a,p)=1,所以 p | (m-n)
但是 m,n < p,則 |m-n| < p,則不可能 p | (m-n),造成矛盾
所以a,2a,...(p-1)a被p除的餘數,必定兩兩相異
所以我們可以保證,a,2a,...,(p-1)a 把所有被p除所得的餘數,都收集完畢
________
所以a,2a,...,(p-1)a的乘積被p除後,必定和1,2,....(p-1)的乘積被p除後相同
p-1
則 (p-1)! ≡ a (p-1)! (mod p)
p-1
則 p |(a - 1)(p-1)!
很明顯的(p-1)!不能被p整除,因為p是質數
p-1
所以, p | a - 1
p-1 p-1
所以 a ≡ 1 (mod p) => a 被p除餘1
---------------------------------------------------------------------------
: 3.先暫時問到這樣好了...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.243.170.15