# Counterexamples to the Baillie-PSW primality test

 Importance: Medium ✭✭
 Author(s):
 Subject: Number Theory » Computational Number Theory
 Keywords:
 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]{http://www.research.att.com/~njas/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).

## Bibliography

% 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?"]{http://www.pseudoprime.com/dopo.pdf}

\href[Thomas R. Nicely. " The Baillie-PSW primality test."]{http://www.trnicely.net/misc/bpsw.html}

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.