数论中 如何证明一个很大的数是素数

数论中 如何证明一个很大的数是素数
数论中 如何证明一个很大的数是素数

数论中 如何证明一个很大的数是素数
很大的数一般用筛法或计算器.
比如说这个数是N,只要证出所有≤根号N的素数都不能被N整除,N就是素数

楼上的那个论文看着真太深奥了。下面是我用的笨方法　
如果一个数A等于其它两个数M和N的乘积（1和本身除外），则M和N之中（除非M=N），必然有一个小于A的二次方根，另一个大于A的二次方根。
计算出A的二次方根，再找出小于A的二次方根的所有素数。用A分别除这些素数，如果均不能整除，则A就是素数。...

全部展开

楼上的那个论文看着真太深奥了。下面是我用的笨方法　
如果一个数A等于其它两个数M和N的乘积（1和本身除外），则M和N之中（除非M=N），必然有一个小于A的二次方根，另一个大于A的二次方根。
计算出A的二次方根，再找出小于A的二次方根的所有素数。用A分别除这些素数，如果均不能整除，则A就是素数。

收起

我还有一种方法，但是操作性不强，不强求你的采纳，但请你务必看下。
若数p为质数，（p-1）！≡-1(mod p)，若p为合数，（p-1)!≡0(mod p)。这是15世纪由英国的威尔逊爵士发明的威尔逊定理，虽然看上去很漂亮，但是计算难度大，我用C语言做了这个程序，到15！就因为数据溢出而无法判断。
证明的话是这样的，若p是质数，1≡-1（mod 2），而当p为奇质数，1到p-1共p...

全部展开

我还有一种方法，但是操作性不强，不强求你的采纳，但请你务必看下。
若数p为质数，（p-1）！≡-1(mod p)，若p为合数，（p-1)!≡0(mod p)。这是15世纪由英国的威尔逊爵士发明的威尔逊定理，虽然看上去很漂亮，但是计算难度大，我用C语言做了这个程序，到15！就因为数据溢出而无法判断。
证明的话是这样的，若p是质数，1≡-1（mod 2），而当p为奇质数，1到p-1共p-1个数，有偶数个数，每个数都有乘法逆元，除了1和p-1的乘法逆元是自己本身，其余的数都有两两配对的乘法逆元组。这样就可以证明了。
而当p为合数，至少是某个质数的平方或者由两个不同质数一次方相乘。而最小合数是4，若p为完全平方数，p>=4时，根号p小于于等于p-2，所以p-2阶乘能被p整除。如果p=ab，a与b互质，a与b必定小于等于p-1，也有p-1的阶乘被p整除。

收起