mersenneforum.org > Math Lucasian Criteria for the Primality of 2^n+3
 Register FAQ Search Today's Posts Mark Forums Read

 2012-04-10, 05:03 #1 princeps   Nov 2011 22×3 Posts Lucasian Criteria for the Primality of 2^n+3 Definition : Let $P_n$ be a number of the form : $P_n=2^n+3$ Definition : Let's define starting seed $S$ as : $S = \begin{cases} 3, & \text{if }n \equiv 0 \pmod 4 \\ 8, & \text{if }n \equiv 2 \pmod 4\\ 7, & \text{if }n \equiv 3 \pmod 4 \end{cases}$ Definition : Let's define sequence $S_i$ as : $S_i=S^2_{i-1}-2 ~\text { with }~ S_0=S$ Conjecture : $P_n ; (n \geq 3) ~\text{ is a prime iff }~ S_{n-1} \equiv S_0 \pmod {P_n}$ I have checked conjecture for all primes in this sequence with exponent below 200000 . Also , for $n<5000$ there is no composite $P_n$ that satisfies relation from conjecture . Are there similar criteria in the literature for the numbers of this form ?
 2012-04-10, 05:15 #2 Dubslow Basketry That Evening!     "Bunslow the Bold" Jun 2011 40
2012-04-10, 05:25   #3
princeps

Nov 2011

148 Posts

Quote:
 Originally Posted by Dubslow [Stupid Question] What if n mod 4 = 1? [/SQ] Also, the LL (and LLR) test(s) start with S0 and end with Si-2. Are you sure you meant Si-1, or did you mean S1=S?
$\text{ If } n \equiv 1 \pmod 4 ~\text { and }~n\geq1 ~\text { then }~ 5 \mid 2^n+3$ , so $5$ is only prime number of the form$2^n+3$ with property $n \equiv 1 \pmod 4$

Yes , I mean : $S_{i-1}$ .

Last fiddled with by princeps on 2012-04-10 at 05:26

2012-04-10, 16:25   #4
R.D. Silverman

Nov 2003

11100010000002 Posts

Quote:
 Originally Posted by princeps Definition : Let $P_n$ be a number of the form : $P_n=2^n+3$ Definition : Let's define starting seed $S$ as : $S = \begin{cases} 3, & \text{if }n \equiv 0 \pmod 4 \\ 8, & \text{if }n \equiv 2 \pmod 4\\ 7, & \text{if }n \equiv 3 \pmod 4 \end{cases}$ Definition : Let's define sequence $S_i$ as : $S_i=S^2_{i-1}-2 ~\text { with }~ S_0=S$ Conjecture : $P_n ; (n \geq 3) ~\text{ is a prime iff }~ S_{n-1} \equiv S_0 \pmod {P_n}$ I have checked conjecture for all primes in this sequence with exponent below 200000 . Also , for $n<5000$ there is no composite $P_n$ that satisfies relation from conjecture . Are there similar criteria in the literature for the numbers of this form ?
This has been discussed before in this forum. Note that P_n - 1 = 2^n + 2
= 2*(2^n-1 + 1).

This test is just a disguised prp test working in the field GF((P_n)^2).
The recursion is just a disguised way of performing exponentiation in this
field.

While the conjecture may be correct, (i.e. that the prp test is a true
prime test) I do not know how to prove this. (nor, I suspect, does anyone
else)

2012-04-10, 20:08   #5
R.D. Silverman

Nov 2003

26×113 Posts

Quote:
 Originally Posted by R.D. Silverman This has been discussed before in this forum. Note that P_n - 1 = 2^n + 2 = 2*(2^n-1 + 1). This test is just a disguised prp test working in the field GF((P_n)^2). The recursion is just a disguised way of performing exponentiation in this field. While the conjecture may be correct, (i.e. that the prp test is a true prime test) I do not know how to prove this. (nor, I suspect, does anyone else)
Note also what happens if n == 1 mod 3. Look at the factorization of
P_n -1 ...........

 Similar Threads Thread Thread Starter Forum Replies Last Post primus Miscellaneous Math 14 2015-07-04 15:42 Mini-Geek Math 8 2009-09-24 21:18 marco_calabresi Information & Answers 3 2009-04-17 19:44 Unregistered Homework Help 4 2007-07-18 08:36 HiddenWarrior Miscellaneous Math 5 2005-05-27 00:20

All times are UTC. The time now is 00:48.

Thu Nov 26 00:48:47 UTC 2020 up 76 days, 21:59, 3 users, load averages: 1.03, 1.09, 1.17