3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Doesn't the existence of Carmichael numbers in arithmetic progressions show that (2) can't happen? $\endgroup$ – LSpice Oct 10 at 3:34
  • $\begingroup$ @LSpice Please explain why. $\endgroup$ – I.Chekhov Oct 10 at 4:11
  • 2
    $\begingroup$ 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$. $\endgroup$ – LSpice Oct 10 at 15:42
3
$\begingroup$

(1) is true.

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.