Counterexamples to the Baillie-PSW primality test

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For odd $n>1$, write $n-1=2^su$ with $u$ odd. The strong base-two test passes if $2^u\equiv1\pmod n$ or $2^{2^ju}\equiv-1\pmod n$ for some $0\le j<s$. For the Lucas test, choose $D$ successively from $5,-7,9,-11,\ldots$ until the Jacobi symbol $(D/n)=-1$; reject an encountered nontrivial common divisor of $D$ and $n$, and reject perfect squares. Put $P=1,Q=(1-D)/4$ (equivalently use Method A*, changing $P,Q$ to $5,5$ when $Q=-1$). Define $U_0=0,U_1=1$, $V_0=2,V_1=P$, and \[ U_{j+2}=PU_{j+1}-QU_j,\qquad V_{j+2}=PV_{j+1}-QV_j. \] Writing $n+1=2^tv$ with $v$ odd, the strong Lucas test passes when $U_v\equiv0\pmod n$ or $V_{2^jv}\equiv0\pmod n$ for some $0\le j<t$. The Baillie--PSW test combines these strong tests with the preceding rejections; even $n>2$ are rejected and $2$ is prime. Here $(D/n)$ is the Jacobi symbol, computed multiplicatively from the Legendre symbols at the prime factors of odd $n$. Finally, $F_0=0,F_1=1,F_{j+2}=F_{j+1}+F_j$ defines the Fibonacci numbers. [S3]

Statement recorded in the supplied source.

Resolve both source questions:

1. Does some composite integer pass the Baillie--PSW test just specified? Exhibit one, or prove that none exists.
2. Does some composite $n\equiv3$ or $7\pmod{10}$ satisfy simultaneously \[ n\mid 2^{n-1}-1,\qquad n\mid F_{n+1}? \] Exhibit one, or prove nonexistence.

The second question is stated separately, rather than identified with the strong-test condition. [S2]

Short English statement

Find a composite passing the specified combined primality test, or prove its universal correctness; separately settle the specified base-two/Fibonacci divisibility question.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3389 (OPG-511). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Counterexamples to the Baillie-PSW primality test, OPG-511. Original problem statement, full mathematical discussion, bibliography and comments. https://www.openproblemgarden.org/op/counterexamples_to_the_baillie_psw_primality_test.
• S3 Robert Baillie, Andrew Fiori and Samuel S. Wagstaff, Jr., Strengthening the Baillie--PSW primality test, arXiv:2006.14425v2 (2021). Sections 2.2--2.4 and 3, original strong test and equivalence of Method A and A*. https://arxiv.org/abs/2006.14425v2.