# On pseudoprimes to the base $a$ (Fermat pseudoprimes)

In 1980, C. Pomerance, J. Selfridge, and S. S. Wagstaff defined a pseudoprime to the base a to be any composite odd $$n$$ such that $$n \mid a^{n-1} - 1$$.

More recently, in 2013, S. S. Wagstaff referred to such numbers as Fermat pseudoprimes.''

Are either of the following known to be true?---

(1) Every Lucas sequence of the form $$a^{n} - 1$$ contains at least one pseudoprime to the base $$a$$.

(2) There exists a value of $$a$$ for which no odd composite $$n$$ divides $$a^{n-1} - 1$$.

If neither are definitively true, could someone point me to any current research on item (2)

Thank you.

• Doesn't the existence of Carmichael numbers in arithmetic progressions show that (2) can't happen? – LSpice Oct 10 '20 at 3:34
• @LSpice Please explain why. – I. Chekhov Oct 10 '20 at 4:11
• Suppose that $a$ is a candidate for (2), and consider the arithmetic progression through $a - 1$ with spacing $a$. Any Carmichael number $n$ in this progression is relatively prime to $a$, so is a pseudoprime to base $a$, in the sense that $n$ divides $a^{n - 1} - 1$. – LSpice Oct 10 '20 at 15:42

Let $$p$$ be a prime such that $$p\nmid (a-1)a$$ and $$\frac{a^p-1}{a-1}$$ is composite. Then $$\frac{a^p-1}{a-1}$$ is a base-$$a$$ pseudoprime.
Also, if $$q$$ is a Carmichael number comprime to $$(a-1)a$$, then both $$q$$ and $$\frac{a^q-1}{a-1}$$ are base-$$a$$ pseudoprimes.