有关数论的一道题n=kp^2,2^(n-1)模n为1,2^k模n不为1,证明：n必为素数上面打错了,n=kp^2+1

首先 可发现 题目近似于 费马小定理的逆命题 但多了一个条件
其次 须知 费马小定理的逆命题 是错误的
定义卡迈克尔数 为正合成数n,且使得对于所有跟n互质的整数b 有b^(n-1)≡1(modn)
易知 逆命题中所得到的数 不是素数 就是卡迈克尔数
设n为合数 则它为卡迈克尔数
由Korselt定理:一个正合成数n是卡迈克尔数,当且仅当n无平方数因子且对于所有n的质因子p,p − 1 | n − 1.
设n的质因数为p1,p2.pr
由于n-1=kp^2
由于 2^(pi-1)≡1(modpi) 则有2^(k)≡1(modpi)(i=1,2,3.r) 则2^(k)≡1(modn) 矛盾
所以n为素数.