Wall–Sun–Sun prime

In number theory, a Wall–Sun–Sun prime or Fibonacci–Wieferich prime is a certain kind of prime number which is conjectured to exist, although none are known.

Let ${\displaystyle p}$ be a prime number. When each term in the sequence of Fibonacci numbers ${\displaystyle F_{n}}$ is reduced modulo ${\displaystyle p}$, the result is a periodic sequence. The (minimal) period length of this sequence is called the Pisano period and denoted ${\displaystyle \pi (p)}$. Since ${\displaystyle F_{0}=0}$, it follows that p divides ${\displaystyle F_{\pi (p)}}$. A prime p such that p² divides ${\displaystyle F_{\pi (p)}}$ is called a Wall–Sun–Sun prime.

If ${\displaystyle \alpha (m)}$ denotes the rank of apparition modulo ${\displaystyle m}$ (i.e., ${\displaystyle \alpha (m)}$ is the smallest positive index such that ${\displaystyle m}$ divides ${\displaystyle F_{\alpha (m)}}$), then a Wall–Sun–Sun prime can be equivalently defined as a prime ${\displaystyle p}$ such that ${\displaystyle p^{2}}$ divides ${\displaystyle F_{\alpha (p)}}$.

For a prime p ≠ 2, 5, the rank of apparition ${\displaystyle \alpha (p)}$ is known to divide ${\displaystyle p-\left({\tfrac {p}{5}}\right)}$, where the Legendre symbol ${\displaystyle \textstyle \left({\frac {p}{5}}\right)}$ has the values

${\displaystyle \left({\frac {p}{5}}\right)={\begin{cases}1&{\text{if }}p\equiv \pm 1{\pmod {5}};\\-1&{\text{if }}p\equiv \pm 2{\pmod {5}}.\end{cases}}}$

This observation gives rise to an equivalent characterization of Wall–Sun–Sun primes as primes ${\displaystyle p}$ such that ${\displaystyle p^{2}}$ divides the Fibonacci number ${\displaystyle F_{p-\left({\frac {p}{5}}\right)}}$.^[1]

A prime ${\displaystyle p}$ is a Wall–Sun–Sun prime if and only if ${\displaystyle \pi (p^{2})=\pi (p)}$.

A prime ${\displaystyle p}$ is a Wall–Sun–Sun prime if and only if ${\displaystyle L_{p}\equiv 1{\pmod {p^{2}}}}$, where ${\displaystyle L_{p}}$ is the ${\displaystyle p}$-th Lucas number.^[2]: 42

McIntosh and Roettger establish several equivalent characterizations of Lucas–Wieferich primes.^[3] In particular, let ${\displaystyle \epsilon =\left({\tfrac {p}{5}}\right)}$; then the following are equivalent:

• ${\displaystyle F_{p-\epsilon }\equiv 0{\pmod {p^{2}}}}$
• ${\displaystyle L_{p-\epsilon }\equiv 2\epsilon {\pmod {p^{4}}}}$
• ${\displaystyle L_{p-\epsilon }\equiv 2\epsilon {\pmod {p^{3}}}}$
• ${\displaystyle F_{p}\equiv \epsilon {\pmod {p^{2}}}}$
• ${\displaystyle L_{p}\equiv 1{\pmod {p^{2}}}}$

In a study of the Pisano period ${\displaystyle k(p)}$, Donald Dines Wall determined that there are no Wall–Sun–Sun primes less than ${\displaystyle 10000}$. In 1960, he wrote:^[4]

The most perplexing problem we have met in this study concerns the hypothesis ${\displaystyle k(p^{2})\neq k(p)}$. We have run a test on digital computer which shows that ${\displaystyle k(p^{2})\neq k(p)}$ for all ${\displaystyle p}$ up to ${\displaystyle 10000}$; however, we cannot prove that ${\displaystyle k(p^{2})=k(p)}$ is impossible. The question is closely related to another one, "can a number ${\displaystyle x}$ have the same order mod ${\displaystyle p}$ and mod ${\displaystyle p^{2}}$?", for which rare cases give an affirmative answer (e.g., ${\displaystyle x=3,p=11}$; ${\displaystyle x=2,p=1093}$); hence, one might conjecture that equality may hold for some exceptional ${\displaystyle p}$.

It has since been conjectured that there are infinitely many Wall–Sun–Sun primes.^[5]

In 2007, Richard J. McIntosh and Eric L. Roettger showed that if any exist, they must be > 2×10¹⁴.^[3] Dorais and Klyve extended this range to 9.7×10¹⁴ without finding such a prime.^[6]

In December 2011, another search was started by the PrimeGrid project;^[7] however, it was suspended in May 2017.^[8] In November 2020, PrimeGrid started another project that searches for Wieferich and Wall–Sun–Sun primes simultaneously.^[9] The project ended in December 2022, proving that any Wall–Sun–Sun prime must exceed ${\displaystyle 2^{64}}$ (about ${\displaystyle 18\cdot 10^{18}}$).^[10]

Wall–Sun–Sun primes are named after Donald Dines Wall,^[4][11] Zhi Hong Sun and Zhi Wei Sun; Z. H. Sun and Z. W. Sun showed in 1992 that if the first case of Fermat's Last Theorem was false for a certain prime p, then p would have to be a Wall–Sun–Sun prime.^[12] As a result, prior to Wiles's proof of Fermat's Last Theorem, the search for Wall–Sun–Sun primes was also the search for a potential counterexample to this centuries-old conjecture.

A tribonacci–Wieferich prime is a prime p satisfying h(p) = h(p²), where h(m) is the least positive integer k satisfying [T_k,T_k+1,T_k+2] ≡ [T₀, T₁, T₂] (mod m) and T_n denotes the n-th tribonacci number. No tribonacci–Wieferich prime exists below 10¹¹.^[13]

A Pell–Wieferich prime is a prime p satisfying p² divides P_p−1, when p congruent to 1 or 7 (mod 8), or p² divides P_p+1, when p congruent to 3 or 5 (mod 8), where P_n denotes the n-th Pell number. For example, 13, 31, and 1546463 are Pell–Wieferich primes, and no others below 10⁹ (sequence A238736 in the OEIS). In fact, Pell–Wieferich primes are 2-Wall–Sun–Sun primes.

A prime p such that ${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv Ap{\pmod {p^{2}}}}$ with small |A| is called near-Wall–Sun–Sun prime.^[3] Near-Wall–Sun–Sun primes with A = 0 would be Wall–Sun–Sun primes. PrimeGrid recorded cases with |A| ≤ 1000.^[14] A dozen cases are known where A = ±1 (sequence A347565 in the OEIS).

Wall–Sun–Sun primes can be considered for the field ${\displaystyle Q_{\sqrt {D}}}$ with discriminant D. For the conventional Wall–Sun–Sun primes, D = 5. In the general case, a Lucas–Wieferich prime p associated with (P, Q) is a Wieferich prime to base Q and a Wall–Sun–Sun prime with discriminant D = P² − 4Q.^[1] In this definition, the prime p should be odd and not divide D.

It is conjectured that for every fundamental discriminant D not equal to 1, there are infinitely many Wall–Sun–Sun primes with discriminant D.

The case of ${\displaystyle (P,Q)=(k,-1)}$ corresponds to the k-Wall–Sun–Sun primes, for which Wall–Sun–Sun primes represent the special case k = 1. The k-Wall–Sun–Sun primes can be explicitly defined as primes p such that p² divides the k-Fibonacci number ${\displaystyle F_{k}(\pi _{k}(p))}$, where F_k(n) = U_n(k, −1) is a Lucas sequence of the first kind with discriminant D = k² + 4 and ${\displaystyle \pi _{k}(p)}$ is the Pisano period of k-Fibonacci numbers modulo p.^[15] For a prime p ≠ 2 and not dividing D, this condition is equivalent to either of the following.

• p² divides ${\displaystyle F_{k}\left(p-\left({\tfrac {D}{p}}\right)\right)}$, where ${\displaystyle \left({\tfrac {D}{p}}\right)}$ is the Legendre symbol;
• V_p(k, −1) ≡ k (mod p²), where V_n(k, −1) is a Lucas sequence of the second kind.

The smallest k-Wall–Sun–Sun primes for k = 2, 3, ... are

13, 241, 2, 3, 191, 5, 2, 3, 2683, ... (sequence A271782 in the OEIS)

• Wieferich prime
• Wolstenholme prime
• Wilson prime
• PrimeGrid
• Fibonacci prime
• Pisano period
• Table of congruences

• Crandall, Richard E.; Pomerance, Carl (2001). Prime Numbers: A Computational Perspective. Springer. p. 29. ISBN 0-387-94777-9.
• Saha, Arpan; Karthik, C. S. (2011). "A Few Equivalences of Wall–Sun–Sun Prime Conjecture". arXiv:1102.1636 [math.NT].

• Chris Caldwell, The Prime Glossary: Wall–Sun–Sun prime at the Prime Pages.
• Weisstein, Eric W. "Wall–Sun–Sun prime". MathWorld.
• Richard McIntosh, Status of the search for Wall–Sun–Sun primes (October 2003)
• OEIS sequence A000129 (Primes p that divide their Pell quotients, where the Pell quotient of p is A000129(p - (2/p))/p and (2/p) is a Jacobi symbol)