Counterexamples to the Baillie-PSW primality test

Importance: Medium ✭✭
Recomm. for undergrads: yes
Prize: $620
Posted by: maxal
on: August 7th, 2007

\begin{problem}[1] Find a counterexample to \Def{Baillie-PSW primality test} or prove that there is no one. \end{problem}

\begin{problem}[2] Find a composite $n\equiv 3$ or $7\pmod{10}$ which divides both $2^{n-1} - 1$ (see \Def{Fermat pseudoprime}) and the Fibonacci number $F_{n+1}$ (see \Def{Lucas pseudoprime}), or prove that there is no such $n$. \end{problem}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}

Selfridge, Wagstaff, and Pomerance offered \$500 + \$100 + \$20 for $n$ satisfying Problem 2, and \$20 + \$100 + \$500 for a proof that there is no such $n$ (R. Guy, 1994).


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

\href[Carl Pomerance. "Are There Counterexamples to the Baillie-PSW Primality Test?"]{}

\href[Thomas R. Nicely. " The Baillie-PSW primality test."]{}

R. K. Guy. "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes". §A12 in "Unsolved Problems in Number Theory", 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

* indicates original appearance(s) of problem.