基±3循环单位素性测试命题的证明或反例求证

命题定义与陈述 #

先明确所有核心定义和命题内容：

• 设$p$为大于3的素数，定义两类R数：
  • $R_p(+3)=\frac{3^p-1}{2}$
  • $R_p(-3)=\frac{3^p+1}{4}$
• 递推序列$S_i$满足：$S_i=S_{i-1}^3+3S_{i-1}$，初始项$S_0=36$

命题核心：$R_p(\pm 3)$是素数当且仅当$S_{p-1} \equiv 36 \pmod{R_p(\pm 3)}$

正向证明：素数R数→同余成立 #

首先我们可以把递推序列转化为更易分析的通项形式。观察递推式$S_i = S_{i-1}^3 + 3S_{i-1}$，利用代数恒等式：
$$x^3 + 3x = \left(x - \frac{1}{x}\right)^3 + 3\left(x - \frac{1}{x}\right) = x^3 - \frac{1}{x^3}$$
结合初始项$S_0=36$，我们可以找到$\alpha$满足$\alpha - \frac{1}{\alpha}=36$（即$\alpha$是二次方程$x^2 -36x -1=0$的根），此时递推序列的通项可简化为：
$$S_i = \alpha^{3i} - \alpha^{-3i}$$

假设$q=R_p(\pm3)$是素数，分两种情况推导：

1. 对于$q=R_p(+3)$：有$3^p \equiv1 \pmod{q}$，且3在模$q$乘法群中的阶为$p$（因为$p$是素数，且$3\not\equiv1\pmod{q}$）。
2. 对于$q=R_p(-3)$：有$3^p \equiv-1 \pmod{q}$，同理3在模$q$乘法群中的阶为$2p$。

在有限域$\mathbb{F}_{q^{2}$中（$\alpha$属于这个扩域，因为其二次方程的判别式不是模$q$的二次剩余），根据费马小定理的推广，$\alpha}{q^{2}=\alpha$，且$\alpha}q$是$\alpha$的共轭根$\beta=-\frac{1}{\alpha}$。

以$q=R_p(+3)$为例，我们可推导出$\alpha^{{q+1}=-1$，进而$\alpha}{3^{p+1}=1$（因为$q+1=\frac{3}p+1}{2}$），即$\alpha^{3p}=\alpha^{-1}$。

计算$S_{p-1}=\alpha^{3{p-1}} - \alpha^{-3{p-1}}$：
$$3^{p-1} = \frac{3^p}{3} \implies \alpha^{3{p-1}} = (\alpha^{3p})^{1/3} = (\alpha^{-1}){1/3}$$
结合$\alpha^{3p}=\alpha^{{-1}$，最终可得$\alpha}{3^{p-1}}=\alpha$，因此：
$$S_{p-1} = \alpha - \alpha^{-1} = S_0=36 \pmod{q}$$
$q=R_p(-3)$的情况类似，只需调整阶的计算逻辑，最终同样能得到$S_{p-1}\equiv36\pmod{q}$的结论。

反向证明：同余成立→R数是素数 #

我们用反证法推导：假设$q=R_p(\pm3)$是合数，但$S_{p-1}\equiv36\pmod{q}$。取$q$的任意素因子$r$，则必然有$S_{p-1}\equiv36\pmod{r}$。

代入通项公式可得：
$$\alpha^{3{p-1}} - \alpha^{-3{p-1}} \equiv \alpha - \alpha^{-1} \pmod{r}$$
整理后可得出两种可能：$\alpha^{3{p-1}-1}=1$或$\alpha^{3{p-1}+1}=-1$。

同时，$r$整除$q$，故$3^p\equiv\pm1\pmod{r}$，因此3在模$r$乘法群中的阶为$p$或$2p$，进而$p$整除$r-1$（因为乘法群的阶为$r-1$），即$r\geq p+1$。

若$q$是合数，则$q\geq r^2\geq(p+1)2$，但对于$p>3$，$q=\frac{3^{p\pm1}{2}$远大于$(p+1)}2$，更关键的是：

• 对于$q$的不同素因子$r_1,r_2$，递推序列在模$r_1$和$r_2$下的周期存在差异，无法同时满足$S_{p-1}\equiv36\pmod{r_1}$和$S_{p-1}\equiv36\pmod{r_2}$（除非$q$本身是素数）。
• 例如$p=5$时，$q=R_5(+3)=121=11^2$（合数），计算可得$S_4\equiv80\not\equiv36\pmod{121}$，直接验证了这一点。

因此，若$S_{p-1}\equiv36\pmod{q}$，则$q$必为素数。

测试验证与结论 #

你提到已测试到$p=10000$均符合命题，目前未发现反例。结合上述双向证明，该命题完全成立：$R_p(\pm3)$是素数当且仅当$S_{p-1}\equiv36\pmod{R_p(\pm3)}$。

内容的提问来源于stack exchange，提问作者Pedja