如下方法是一个确定性的素性检验方法吗
设N=4k+3,计算 x=(a+bI)^N (mod N),如果x=a-bI,则$N$为素数. 其中基$a+bI$可以任意取，但$a,b$不能相等,且$GCD=1$。在实际计算中，为了等式更好地比较，可以两边同乘以
$(a+bI)$则有 $a^2+b^2=(a+bI)^{N+1} (mod N)$ 哈哈哈,这个小论坛,一些计算机水平较高的人是有的,也有一些数学水平比较高的人,
但是要谈到数论水平很高的人,我觉得是找不到的.
我建议你自己找反例,应该很容易找到反例的.我觉得你可以很快找到反例,
凭借我对数论的感觉,我觉得你的算法应该是有伪素数的. 其实不是看不起你,而是基本上你能想到的方法,那些专门研究的人肯定能想到的,
其实我早就劝你不要折腾素数了,这个东西也许有统计规律,但是像你这么简单的
方法应该不行的 假设我取b=0,然后a=2,
N取一个除以4余3的伪素数,
这样你的算法不就被推翻了吗? 4# 郭先抢
那就变为特殊情况了，这里虚数I就不起作用了 本帖最后由 wsc810 于 2012-12-5 19:54 编辑
$mathe$,$wanye$,数学星空,hujunhua能给出一个证明吗，我想只要稍努力思考一下，证明的方法是有的。 没有本质变化，由于$p|C_p^k$,所以二项式展开即可 本质是对于任意素数p和非平方剩余u,多项式a+bx有
（a+bx)^p(mod p,x^2-u)=a+bx^p(mod p,x^2-u)=a+bu^((p-1)/2)x(mod p)=a-bx 本帖最后由 wsc810 于 2012-12-6 09:09 编辑
没人证明我给出自己的证明，用反证法：现在考虑以下何种情况下$(a+bI)^N=a-bI(mod N)$我们可以断定$N$没有$4k+1$ 的因子,假设$N$有$q=4k+1$ 的因子$N=q*d$ ,
then $(a+bI)^N=((a+bI)^q)^d=(a-bI)^d=a^d+b^d(-I)^{4k+3}=a^d+b^d*I\ne a-bI (mod q)$,
so所以 N 没有 $4k+1$ 的因子。
所以$N$ 只能含有3,or 5 or 7 个形如$4k+3$的因子 ，现在考虑3个因子的情况.
假设同余式成立 $(a+bI)^{q_1q_2q_3}=a-bI (mod q_1q_2q_3 )$
则有
$((a+bI)^{q_1})^{q_2q_3}=(a-bI)^{q_2q_3}=a-bI(mod q_1)$ (1)
$((a+bI)^{q_2})^{q_1q_3}=(a-bI)^{q_1q_3}=a-bI(mod q_2)$ (2)
$((a+bI)^{q_3})^{q_1q_2}=(a-bI)^{q_1q_2}=a-bI(mod q_3)$ (3)
因为 $ ((a-bI)^{q_1+1})^{(q_1-1)k}=(a^2+b^2)^{(q_1-1)k}=1(mod q_1) $
(1)式两边同乘以$(a-bI)$
$(a-bI)((a-bI)^{q_1+1})^{(q_1-1)*k_1}=(a-bI)^{(q_1^2-1)*k_1+1}(mod q_1)$
(2),(3)式同样处理
$(a-bI)((a-bI)^{q_2+1})^{(q_2-1)*k_2}=(a-bI)^{(q_2^2-1)*k_2+1}(mod q_2)$
$(a-bI)((a-bI)^{q_3+1})^{(q_3-1)*k_3}=(a-bI)^{(q_3^2-1)*k_3+1}(mod q_3)$
所以
$q_2q_3=(q_1^2-1)*k_1+1$(1)
$q_1q_3=(q_2^2-1)*k_2+1$(2)
$q_1q_2=(q_3^2-1)*k_3+1$(3)
(1)/(2)
$\frac{q_2}{q_1}=\frac{(q_1^2-1)*k_1+1}{(q_2^2-1)*k_2+1}$
$q_2*((q_2^2-1)*k_2+1)=q_1*((q_1^2-1)*k_1+1)$
因 $q_2,q_1$是素数，所以有
$(q_2^2-1)*k_2+1=q_1*t$ (3)
$(q_1^2-1)*k_1+1=q_2*t$ (4)
整理，得
$(q_1^2-1)k_1=q_2-1$ (3)
$(q_2^2-1)k_2=q_1-1$ (4)
将$q_2=\frac{(q_1^2-1)k_1+1 }{t}$带入(4)，整理得
$q_1t^3+(k_2-1)t_2^2-k_2((q_1^2-1)*k_1+1)^2=0$
现在只需证明该三次方程对t无正整数解，到这里我卡住了，望高人指点。
我前面的证明有问题吗？ 错误证明。不过这方法的确通常比没有虚部的要好，但是不同的底，可靠性不同