如何在不知道一个数因子的情况下证明它是合数 这个在梅森素数判断时有过例子

题目

如何在不知道一个数因子的情况下证明它是合数 这个在梅森素数判断时有过例子

答案

利用费尔马小定理的逆定理可以在不得到因数的前提下证明是否是合数（但是不能百分百确定是素数）
费马小定理是数论中的一个定理.其内容为假如a是一个整数,p是一个质数的话,且a、p互素
则 a^p-a≡0(mod p)
或写成p|(a^p-a) 意为p能整除(a^p-a);
假如我不知道91是否是素数!
因为(2^91-2)/91除不断,即有余数35,故91是合数!
但是要注意,这种方法只能确定它是合数,而不能确定它是否是素数!如果想了解更多,可以去看看这方面的书籍!