威尔逊定律与费马小定理能互相导出吗?

cn8888

威尔逊定律与费马小定理能互相导出吗?
感觉以前好像看到过,但是.................

kastin

相关趣事一则[引用]：
威尔逊[英]是18世纪剑桥大学的数学高才生，他曾猜想这个定理是正确的，其实与牛顿同创微积分的莱布尼兹[德]早在1682年就已经提出了它；但是第一个证明是由大数学家拉格朗日[法]在1773年给出的；当时曾有人声称“威尔逊定理是不可证明的，因为人们没有好的符号来处理质数。”这句惊人的话传到了古今最伟大的数学家高斯[德]耳中，高斯站着想了5分钟，也证明了威尔逊定理，而且还说了一句后来被人们广为传之的名言：“它需要的是概念，而不是符号！”

先给出大家熟悉的表述形式
威尔逊定理：若`p`为素数，则`(p-1)! \equiv -1 \pmod{p}`
费马小定理：若`p`为素数，且`(a,p)=1`，则`\enspace a^{p-1}\equiv 1 \pmod{p}`
显然，费马小定理只是欧拉定理中模为素数的特殊情形。所以不使用欧拉定理，仿照其证法也能直接证明费马小定理，而且无需用到威尔逊定理的结果。
`\{1,2,3,...,p-1\}`是素数模`p`的缩系，对于`(a,p)=1`，`\{a,2a,3a,...,(p-1)a\}`也是`p`的缩系，故有`1\times2\times3\times\cdots\times(p-1)\equiv a\*2a\cdots(p-1)a \pmod{p}`，即`(p-1)!=a^{p-1}(p-1)!\pmod{p}`,因为`(p-1)!`与`p`互质，可以同时去掉同余式两端的`(p-1)!`，便可得到`a^{p-1}=1\pmod{p}`。这里完全不需要用到威尔逊定理中`(p-1)!\equiv -1 \pmod{p}`中`-1`这个值。

不过，威尔逊定理倒是可以用费马小定理来证明。下面摘录如下：
只需构造`f(x)=(x-1)(x-2)\cdots(x-p+1)-(x^{p-1}-1)`即可，取`x=1,2,3,\cdots,p-1`均满足`f(x)\equiv 0 \pmod{p}`，而`\,\deg f=p-2`，根据数论中的拉格朗日定理，可知`x`各项系数必是`p`的倍数（为什么？），展开后有`(p-1)!+1\equiv 0 \pmod{p}`

如果费马小定理和威尔逊定理可以相互证明，是否说明二者是等价的？

cn8888

不等价？
威尔逊定理可作为p是否素数的判定定理，费马小定理则不能？

hujunhua

cn8888 发表于 2015-9-11 12:51
不等价？
威尔逊定理可作为p是否素数的判定定理，费马小定理则不能？

可以互相导出，等价。但3#的质疑不正确，因为作为素数判定定理的是逆定理

hujunhua

记等幂和`S_k=1^k+2^k+\cdot+(p-1)^k, (k=1,2,\cdots, p-2)`（`k`范围下同）
由等幂和公式可得`S_k\equiv0\pmod p`。
记`t_k`为`(p-1)`元 `k` 阶基本对称多项式，利用有关对称多项式的牛顿公式及`S_k\equiv0\pmod p`，可以证明
`(x-1)(x-2)\cdot\ldots\cdot(x-p+1)`的完全展开式中，`x^k`项系数皆≡0(modp)，所以
`(x-1)(x-2)\cdot\ldots\cdot(x-p+1)\equiv x^{p-1}+(p-1)!\pmod p`
对任意的`x\in(1,2,3,\cdots,p-1)`, 从上式及威尔逊定理就得到了费马小定理。

cn8888

hujunhua 发表于 2015-9-17 18:13
记等幂和`S_k=1^k+2^k+\cdot+(p-1)^k, (k=1,2,\cdots, p-2)`（`k`范围下同）
由等幂和公式可得`S_k\equiv0 ...

如果两者能够互相推导,那就意味着费马小定理可以用来判定一个数是否是素数.
可以费马小定理不能够判定一个数是否是素数,所以我觉得肯定是某处逻辑有问题.
你说呢?或者说两个定理本身不等价!

hujunhua

2#所示的用费马小定理推导威尔逊定理过程，并不表明仅使用`\gcd(x,p)=1,x^{p-1}\equiv1\pmod p`就足以得出`(p-1)!+1\equiv0\pmod p`。
其中用到的拉格朗日定理是以`p`是素数为前提的。所以“费马小定理→威尔逊定理→威尔逊逆定理→素数”的链条没有意义，是循环论证。
实际的逻辑链是: `p`是素数 +`\gcd(x,p)=1,x^{p-1}\equiv1\pmod p`→`(p-1)!+1\equiv0\pmod p`。

你再延伸一步为： `p`是素数 +`\gcd(x,p)=1,x^{p-1}\equiv1\pmod p`→`(p-1)!+1\equiv0\pmod p`→`p`是素数
省掉中间链节，就是：`p`是素数 +`\gcd(x,p)=1,x^{p-1}\equiv1\pmod p`→`p`是素数，这是成立的，但是有意义吗？

hujunhua

费马小定理是可以略为加强的。如果一个合数 p 对任意与之互质的数 a 均成立`a^{p-1}\equiv1\pmod p`, 就称为绝对伪素数（又叫卡迈克尔数）。
341不是卡迈克尔数，最小的卡迈克尔数是561。
但是，我们这里且把素数和绝对伪素数的合集称卡迈克尔数。于是费马小定理可以扩展为：
强费马小定理：若`p`为卡迈克尔数，且`(a,p)=1`，则`a^{p−1}\equiv1\pmod p`

@cn8888, 你还能由强费马小定理推导出`(p-1)!+1\equiv0\pmod p`吗？

cn8888

hujunhua 发表于 2015-9-18 17:31
费马小定理是可以略为加强的。如果一个合数 p 对任意与之互质的数 a 均成立`a^{p-1}\equiv1\pmod p`, 就称 ...

2楼与你不是推导了吗?

cn8888

对于p>2的整数
对于威尔逊定理:如果(p-1)!+1=0(modp) 则p是素数,如果(p-1)!+1=0(modp) 不成立,则p是合数
对于费马小定理:如果a^p=a(modp),则p未必是素数(2^341=2(mod341)但是341是合数),如果a^p=a(modp)不成立,则p肯定是合数,
问题来了,如果两个定理等价,为什么会出现上面的情况??

请不要再改变编辑我的这个回复!!!上次不知道是谁编辑的!因为你的编辑没能表达我的意思