Let $0\neq \beta\in\overline{\mathbb{Z}}$ and let $n$ be a positive integer coprime to $N_{\mathbb{Q}(\beta)/\mathbb{Q}}(\beta)$. Say that $n$ is a Fermat pseudoprime to base $\beta$ if
$$\beta^{n^{[\mathbb{Q}(\beta):\mathbb{Q}]}-1}\equiv 1\pmod n.$$
If $p$ is a prime which does not divide $N_{\mathbb{Q}(\beta)/\mathbb{Q}}(\beta)$ and $\mathcal{O}$ is the ring of integers of $\mathbb{Q}(\beta)$, then $\bar{\beta}\in\mathcal{O}/p\mathcal{O}$ is a unit, and $\mathcal{O}/p\mathcal{O}$ is a product of residue fields, each with degree dividing $[\mathbb{Q}(\beta):\mathbb{Q}]$, so $p$ passes the test. This justifies the use of the word 'pseudoprime'.
If $\beta\in\mathbb{Z}_{\ge 2}$, there are many ways to construct composite $n$ which are Fermat pseudoprimes to base $\beta$. For example, Cipolla's method: Let $p\nmid \beta(\beta^2-1)$ be an odd prime, then $(\beta^{2p}-1)/(\beta^2-1)$ is composite and a pseudoprime to base $\beta$.
Questions:
- For which $\beta$ do we have a way of constructing infinitely many composite base $\beta$ pseudoprimes?
- For which $\beta$ do we know there exist infinitely many composite base $\beta$ pseudoprimes?
Edit: Just read that if $n$ is a Carmichael number coprime to the discriminant of $\mathbb{Q}(\beta)$, such that the minimal polynomial of $\beta$ splits completely modulo $p$ for all $p\mid n$, then $\beta^n\equiv \beta\pmod n$. This suggests the answer to the second question is affirmative.
Best Answer
The answer to both questions is yes. Just like Alford, Granville and Pomerance's proof that there are infinitely many Carmichael numbers, my proof that there are infinitely many Carmichael numbers where the minimal polynomial splits completely is essentially a constructive proof.
Both proofs need to jump through some hoops to get provability that you would not need in practice.
Grantham, Jon. There are infinitely many Perrin pseudoprimes. J. Number Theory 130 (2010), no. 5, 1117–1128.