# Wall–Sun–Sun prime

(Redirected from Wall-Sun-Sun prime)
Named after Donald Dines Wall, Zhi Hong Sun and Zhi Wei Sun 1992 0 Infinite

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.

## Definition

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 p2 divides ${\displaystyle F_{\pi (p)}}$ is called a Wall–Sun–Sun prime.

### Equivalent definitions

If ${\displaystyle \alpha (m)}$ denotes the rank of apparition modulo ${\displaystyle m}$ (i.e., ${\displaystyle \alpha (m)}$ is the smallest 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({\frac {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}}}}$

## Existence

 Unsolved problem in mathematics:Are there any Wall–Sun–Sun primes? If yes, are there an infinite number of them?(more unsolved problems in mathematics)

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] No Wall–Sun–Sun primes are known as of April 2016.

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

In December 2011, another search was started by the PrimeGrid project[7], however it was suspended in May of 2017.[8]

## History

Wall–Sun–Sun primes are named after Donald Dines Wall,[4][9] 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.[10] As a result, prior to Andrew Wiles' 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.

## Generalizations

A tribonacci–Wieferich prime is a prime p satisfying h(p) = h(p2), where h is the least positive integer satisfying [Th,Th+1,Th+2] ≡ [T0, T1, T2] (mod m) and Tn denotes the n-th tribonacci number. No tribonacci–Wieferich prime exists below 1011.[11]

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

### Near-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.

### Wall–Sun–Sun primes with discriminant D

Wall–Sun–Sun primes can be considered in 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 = P2 – 4Q.[1] In this definition, the prime p should be odd and not divide D.

It is conjectured that for every natural number D, 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 a special case with k = 1. The k-Wall–Sun–Sun primes can be explicitly defined as primes p such that p2 divides the k-Fibonacci number ${\displaystyle F_{k}(\pi _{k}(p))}$, where Fk(n) = Un(k, −1) is a Lucas sequence of first kind with discriminant D = k2 + 4 and ${\displaystyle \pi _{k}(p)}$ is the Pisano period of k-Fibonacci numbers modulo p.[12] For a prime p ≠ 2 and not dividing D, this condition is equivalent to any of the following two:

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

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

13, 241, 2, 3, 191, 5, 2, 3, 2683, ... (sequence A271782 in the OEIS)
k square-free part of D () k-Wall–Sun–Sun primes notes
1 5 ...
2 2 13, 31, 1546463, ...
3 13 241, ...
4 5 2, 3, ... Since this is the second time for which D=5, thus plus the prime factors of 2*2−1 which does not divide 5. Since k is divisible by 4, thus plus the prime 2.
5 29 3, 11, ...
6 10 191, 643, 134339, 25233137, ...
7 53 5, ...
8 17 2, ... Since k is divisible by 4, thus plus the prime 2.
9 85 3, 204520559, ...
10 26 2683, 3967, 18587, ...
11 5 ... Since this is the third time for which D=5, thus plus the prime factors of 2*3−1 which does not divide 5.
12 37 2, 7, 89, 257, 631, ... Since k is divisible by 4, thus plus the prime 2.
13 173 3, 227, 392893, ...
14 2 3, 13, 31, 1546463, ... Since this is the second time for which D=2, thus plus the prime factors of 2*2−1 which does not divide 2.
15 229 29, 4253, ...
16 65 2, 1327, 8831, 569831, ... Since k is divisible by 4, thus plus the prime 2.
17 293 1192625911, ...
18 82 3, 5, 11, 769, 256531, 624451181, ...
19 365 11, 233, 165083, ...
20 101 2, 7, 19301, ... Since k is divisible by 4, thus plus the prime 2.
21 445 23, 31, 193, ...
22 122 3, 281, ...
23 533 3, 103, ...
24 145 2, 7, 11, 17, 37, 41, 1319, ... Since k is divisible by 4, thus plus the prime 2.
25 629 5, 7, 2687, ...
26 170 79, ...
27 733 3, 1663, ...
28 197 2, 1431615389, ... Since k is divisible by 4, thus plus the prime 2.
29 5 7, ... Since this is the fourth time for which D=5, thus plus the prime factors of 2*4−1 which does not divide 5.
30 226 23, 1277, ...
D Wall–Sun–Sun primes with discriminant D (checked up to 109) OEIS sequence
1 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All odd primes) A065091
2 13, 31, 1546463, ... A238736
3 103, 2297860813, ... A238490
4 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All odd primes)
5 ...
6 (3), 7, 523, ...
7 ...
8 13, 31, 1546463, ...
9 (3), 5, 7, 11, 13, 17, 19, 23, 29, ... (All odd primes)
10 191, 643, 134339, 25233137, ...
11 ...
12 103, 2297860813, ...
13 241, ...
14 6707879, 93140353, ...
15 (3), 181, 1039, 2917, 2401457, ...
16 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All odd primes)
17 ...
18 13, 31, 1546463, ...
19 79, 1271731, 13599893, 31352389, ...
20 ...
21 46179311, ...
22 43, 73, 409, 28477, ...
23 7, 733, ...
24 7, 523, ...
25 3, (5), 7, 11, 13, 17, 19, 23, 29, ... (All odd primes)
26 2683, 3967, 18587, ...
27 103, 2297860813, ...
28 ...
29 3, 11, ...
30 ...

## References

1. ^ a b A.-S. Elsenhans, J. Jahnel (2010). "The Fibonacci sequence modulo p2 -- An investigation by computer for p < 1014". arXiv:1006.0824.
2. ^ Andrejić, V. (2006). "On Fibonacci powers" (PDF). Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. 17: 38–44. doi:10.2298/PETF0617038A.
3. ^ a b c McIntosh, R. J.; Roettger, E. L. (2007). "A search for Fibonacci−Wieferich and Wolstenholme primes" (PDF). Mathematics of Computation. 76 (260): 2087–2094. Bibcode:2007MaCom..76.2087M. doi:10.1090/S0025-5718-07-01955-2.
4. ^ a b Wall, D. D. (1960), "Fibonacci Series Modulo m", American Mathematical Monthly, 67 (6): 525–532, doi:10.2307/2309169
5. ^ Klaška, Jiří (2007), "Short remark on Fibonacci−Wieferich primes", Acta Mathematica Universitatis Ostraviensis, 15 (1): 21–25.
6. ^ Dorais, F. G.; Klyve, D. W. (2010). "Near Wieferich primes up to 6.7 × 1015" (PDF). Cite journal requires |journal= (help)
7. ^ Wall–Sun–Sun Prime Search project at PrimeGrid
8. ^ [1] at PrimeGrid
9. ^ Crandall, R.; Dilcher, k.; Pomerance, C. (1997). "A search for Wieferich and Wilson primes". 66: 447. Cite journal requires |journal= (help)
10. ^ Sun, Zhi-Hong; Sun, Zhi-Wei (1992), "Fibonacci numbers and Fermat's last theorem" (PDF), Acta Arithmetica, 60 (4): 371–388
11. ^ Klaška, Jiří (2008). "A search for Tribonacci–Wieferich primes". Acta Mathematica Universitatis Ostraviensis. 16 (1): 15–20.
12. ^ S. Falcon, A. Plaza (2009). "k-Fibonacci sequence modulo m". Chaos, Solitons & Fractals. 41 (1): 497–504. Bibcode:2009CSF....41..497F. doi:10.1016/j.chaos.2008.02.014.