Generalized repunit pseudoprime construction (source code)

= Generalized repunit pseudoprime construction

Fix an <integer> $a>1$ and an <odd prime> $p$ not dividing $a^2-1$. Then
$$
N=\frac{a^{2p}-1}{a^2-1}=1+a^2+\cdots+a^{2p-2}
$$
is a <composite number> that is a <Fermat pseudoprime> to base $a$.

For compositeness, factor
$$
N=\frac{a^p-1}{a-1}\,\frac{a^p+1}{a+1}.
$$
Both factors are <integers> because $p$ is odd, and both exceed one for $a>1$ and $p\geq3$. Also $N\equiv1\pmod a$, so $a$ is <coprime> to $N$.

By <Fermat's little theorem>, $a^{2p}\equiv a^2\pmod p$. Since $a^2-1$ is invertible <modulo> $p$, this gives $N\equiv1\pmod p$. The displayed sum is odd for either <parity> of $a$, so $2p\mid N-1$. Finally $a^{2p}\equiv1\pmod N$, and raising this identity to the <integer> power $(N-1)/(2p)$ proves $a^{N-1}\equiv1\pmod N$.

For $a=2$ and $p=5$, this produces $N=341=11\cdot31$ and $2^{340}=(2^{10})^{34}\equiv1\pmod{341}$. The explicit restriction on $p$ matters: $a=2,p=3$ instead gives $21$, which fails the base-two test.