给我数学证明!

来源:百度知道 编辑:UC知道 时间:2024/05/29 10:25:53
判别M是否为素数,可以让M被2到根号M除,能给出数学证明吗?就是说为什么能用2到根号M之间的数除,而不用2到M-1之间的数除!谢谢!

证明;
假设a>根号M 能被M整除,则M/a能被M整除,

而M/a<根号M,即存在小于根号M的数能被M整除,

所以可以让M被2到根号M除

假设M有一个因数x,sqrt(M)<x<M.并且M无2到sqrt(M)的因素.
那么另y=M/x,显然有y也是M的因数.
由于x>sqrt(M),则有y<sqrt(M).
与假设矛盾.
由以上论述可知,只需要检验2到sqrt(M)的数即可,
事实上,只需检验这个范围内的素数即可.

因为任何一个合数都可以至少分为两个数的乘法,一大一小,或者是相等。所以你只要除到根号M就可以了

证明;
假设a>根号M 能被M整除,则M/a能被M整除,

而M/a<根号M,即存在小于根号M的数能被M整除,

所以可以让M被2到根号M除