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