※ 引述《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