如下方法是一个确定性的素性检验方法吗

wsc810

设$N=4k+3$,  计算 $x=(a+bI)^N (mod N)$,如果$x=a-bI$,则$N$为素数. 其中基$a+bI$可以

任意取，但$a,b$不能相等,且$GCD[a+bI,N]=1$。在实际计算中，为了等式更好地比较，可以两边同乘以

$(a+bI)$  则有 $a^2+b^2=(a+bI)^{N+1} (mod N)$

郭先抢

哈哈哈,这个小论坛,一些计算机水平较高的人是有的,也有一些数学水平比较高的人,
但是要谈到数论水平很高的人,我觉得是找不到的.
我建议你自己找反例,应该很容易找到反例的.我觉得你可以很快找到反例,
凭借我对数论的感觉,我觉得你的算法应该是有伪素数的.

郭先抢

其实不是看不起你,而是基本上你能想到的方法,那些专门研究的人肯定能想到的,
其实我早就劝你不要折腾素数了,这个东西也许有统计规律,但是像你这么简单的
方法应该不行的

郭先抢

假设我取b=0,然后a=2,
N取一个除以4余3的伪素数,
这样你的算法不就被推翻了吗?

wsc810

4# 郭先抢

那就变为特殊情况了，这里虚数I就不起作用了

wsc810

$mathe$,$wanye$,数学星空,hujunhua能给出一个证明吗，我想只要稍努力思考一下，证明的方法是有的。

mathe

没有本质变化，由于$p|C_p^k$,所以二项式展开即可

mathe

本质是对于任意素数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

没人证明我给出自己的证明，用反证法：现在考虑以下何种情况下$(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无正整数解，到这里我卡住了，望高人指点。
我前面的证明有问题吗？

mathe

错误证明。不过这方法的确通常比没有虚部的要好，但是不同的底，可靠性不同