Is $n=1073$ a strong pseudoprime to bases $a=260, 813?$

159 Views Asked by At

The OEIS Wiki page http://oeis.org/wiki/Strong_pseudoprimes says that $n=1073\,$ is a strong pseudoprime to bases $a=260, 813.$

I think this is an error. $n=1073$ would be a strong pseudoprime to base $a=260$ if (using the decomposition $n-1=d\cdot 2^s, 1072=67\cdot2^4$) we have $$a^d \equiv 1 \pmod n$$ $$x_r \equiv a^{d\cdot 2^r}\equiv -1 \pmod n \quad \text{for some} \quad 0\le r < s$$ But for $a=260\;$ I get $$a^d \equiv x_0 \equiv 260^{67}\equiv 260 \not \equiv \pm 1\pmod n$$ $$x_1 \equiv 260^2 \equiv 1 \pmod n$$ $$x_2\equiv x_3 \equiv 1 \pmod n$$

For $a=813$ the analogous computations give $$x_0\equiv 813 \pmod n, \quad x_1 \equiv x_2 \equiv x_3\equiv 1 \pmod n$$

This shows that, that $1073$ is not a strong pseudoprime to bases $260, 813.$

Question: Is this proof correct (if not, where is the error) and OEIS is incorrect?

PS: I stumbled on this during commenting on Finding bases for which a number is a strong pseudoprime

1

There are 1 best solutions below

0
On

I have (re)checked it myself and really, there should be just numbers (191,302,771,882) working as bases for number 1073. So OEIS is wrong.