Wall–Sun–Sun prime

Wall–Sun–Sun prime
Named after	Donald Dines Wall, Zhi Hong Sun and Zhi Wei Sun
Publication year	1992
Number of known terms	0
Conjectured number of terms	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

The period of Fibonacci numbers $F_{n}$ modulo prime p is called the Pisano period and denoted $\pi (p)$ . It follows that p divides $F_{\pi (p)}$ . A prime p such that p² divides $F_{\pi (p)}$ is called Wall–Sun–Sun prime.

For a prime p ≠ 2, 5, the Pisano period $\pi (p)$ is known to divide $p-\left({\tfrac {p}{5}}\right)$ , where the Legendre symbol $\textstyle \left({\frac {p}{5}}\right)$ has the values

\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 definition that a prime p is a Wall–Sun–Sun prime if p² divides the Fibonacci number $F_{p-\left({\frac {p}{5}}\right)}$ .^[1]

Equivalently, a prime p is a Wall–Sun–Sun prime if L_p ≡ 1 (mod p²), where L_p is the p-th Lucas number.^[2]^:42

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 $k(p)$ , Donald Dines Wall determined that there are no Wall–Sun–Sun primes less than $10000$ . He writes:^[3]

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

It has since been conjectured that there are infinitely many Wall–Sun–Sun primes.^[4] 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×10¹⁴.^[5] 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] As of April 2016, PrimeGrid has extended the search limit to 1.9×10¹⁷ and continues.^[8]

History

Wall–Sun–Sun primes are named after Donald Dines Wall,^[3]^[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(p²), where h is the least positive integer satisfying [T_h,T_h+1,T_h+2] ≡ [T₀, T₁, T₂] (mod m) and T_n denotes the n-th tribonacci number. No tribonacci–Wieferich prime exists below 10¹¹.^[11]

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.

Near-Wall–Sun–Sun primes

A prime p such that $F_{p-\left({\frac {p}{5}}\right)}\equiv Ap{\pmod {p^{2}}}$ with small |A| is called near-Wall–Sun–Sun prime.^[12] 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 $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 natural number D, there are infinitely many Wall–Sun–Sun primes with discriminant D.

The case of $(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 p² divides the k-Fibonacci number $F_{k}(\pi _{k}(p))$ , where F_k(n) = U_n(k, −1) is a Lucas sequence of first kind with discriminant D = k² + 4 and $\pi _{k}(p)$ is the Pisano period of k-Fibonacci numbers modulo p.^[13] For a prime p ≠ 2 and not dividing D, this condition is equivalent to any of the following two:

p² divides $F_{k}\left(p-\left({\tfrac {D}{p}}\right)\right)$ , where $\left({\tfrac {D}{p}}\right)$ is the Kronecker 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 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 ( A013946)	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 10⁹)	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	3, ...
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 2 A.-S. Elsenhans, J. Jahnel (2010). "The Fibonacci sequence modulo p² -- An investigation by computer for p < 10¹⁴". arXiv:1006.0824.
↑ Andrejić, V. (2006). "On Fibonacci powers" (PDF). Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat. 17: 38–44. doi:10.2298/PETF0617038A.
1 2 Wall, D. D. (1960), "Fibonacci Series Modulo m", American Mathematical Monthly, 67 (6): 525–532, doi:10.2307/2309169
↑ Klaška, Jiří (2007), "Short remark on Fibonacci−Wieferich primes", Acta Mathematica Universitatis Ostraviensis, 15 (1): 21–25 .
↑ McIntosh, R. J.; Roettger, E. L. (2007). "A search for Fibonacci−Wieferich and Wolstenholme primes" (PDF). Mathematics of Computation. 76 (260): 2087–2094. doi:10.1090/S0025-5718-07-01955-2.
↑ Dorais, F. G.; Klyve, D. W. (2010). "Near Wieferich primes up to 6.7 × 10¹⁵" (PDF).
↑ Wall–Sun–Sun Prime Search project at PrimeGrid
↑ Wall–Sun–Sun Prime Search statistics at PrimeGrid
↑ Crandall, R.; Dilcher, k.; Pomerance, C. (1997). "A search for Wieferich and Wilson primes". 66: 447.
↑ Sun, Zhi-Hong; Sun, Zhi-Wei (1992), "Fibonacci numbers and Fermat's last theorem" (PDF), Acta Arithmetica, 60 (4): 371–388
↑ Klaška, Jiří (2008). "A search for Tribonacci–Wieferich primes". Acta Mathematica Universitatis Ostraviensis. 16 (1): 15–20.
↑ McIntosh, R. J.; Roettger, E. L. (2007), "A search for Fibonacci–Wieferich and Wolstenholme primes", Mathematics of Computation, AMS, 76 (260): 2087–2094, doi:10.1090/S0025-5718-07-01955-2, archived from the original (PDF) on 2010-12-10
↑ S. Falcon, A. Plaza (2009). "k-Fibonacci sequence modulo m". Chaos, Solitons & Fractals. 41 (1): 497–504. doi:10.1016/j.chaos.2008.02.014.

External links

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)

Prime number classes

By formula	Fermat (2^2ⁿ + 1) Mersenne (2^p − 1) Double Mersenne (2^{2^p−1} − 1) Wagstaff (2^p + 1)/3 Proth (k·2ⁿ + 1) Factorial (n! ± 1) Primorial (p_n# ± 1) Euclid (p_n# + 1) Pythagorean (4n + 1) Pierpont (2^u·3^v + 1) Quartan (x⁴ + y⁴) Solinas (2^a ± 2^b ± 1) Cullen (n·2ⁿ + 1) Woodall (n·2ⁿ − 1) Cuban (x³ − y³)/(x − y) Carol (2ⁿ − 1)² − 2 Kynea (2ⁿ + 1)² − 2 Leyland (x^y + y^x) Thabit (3·2ⁿ − 1) Mills (floor(A^3ⁿ))

By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin Partitions Bell Motzkin

By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient

Base-dependent	Happy Dihedral Palindromic Emirp Repunit (10ⁿ − 1)/9 Permutable Circular Truncatable Strobogrammatic Minimal Weakly Full reptend Unique Primeval Self Smarandache–Wellin

Patterns	Twin (p, p + 2) Bi-twin chain (n − 1, n + 1, 2n − 1, 2n + 1, …) Triplet (p, p + 2 or p + 4, p + 6) Quadruplet (p, p + 2, p + 6, p + 8) k−Tuple Cousin (p, p + 4) Sexy (p, p + 6) Chen Sophie Germain (p, 2p + 1) Cunningham chain (p, 2p ± 1, …) Safe (p, (p − 1)/2) Arithmetic progression (p + a·n, n = 0, 1, …) Balanced (consecutive p − n, p, p + n)

By size	Titanic (1,000+ digits) Gigantic (10,000+) Mega (1,000,000+) Largest known

Complex numbers	Eisenstein prime Gaussian prime

Composite numbers	Pseudoprime Almost prime Semiprime Interprime

Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap

First 50 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229

List of prime numbers

This article is issued from Wikipedia - version of the 11/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.