 Generalized repunit pseudoprime construction

Fix an integer $a>1$ and an odd prime $p$ not dividing $a^2-1$. Thenis a composite number that is a Fermat pseudoprime to base $a$.

For compositeness, factorBoth factors are integers because $p$ is odd, and both exceed one for $a>1$ and $p\ge 3$. Also $N\equiv 1(\mathrm{mod}a)$, so $a$ is coprime to $N$.

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

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