New Test for Primes form 8n =/- 3

[ramsey2879]

As Dodo noted, my prior test excluded some primes of the form 8n +/- 3, e.g. 29. I discovered a new property of the recursive series used in the prior test to allow a correction that apparently includes all primes of the form 8n +/- 3 but apparently includes no composites. The property of the recursive series (defined by S_0 = 2, S_1 = 3, S_n = 6S_(n-1) - S_(n-2) - 6) is that;

\sum_{i=0}^{2n} \binom{2n}{i}S_{k-n+i} + 3*(2^{n}-1)*2^{2n-1} = 2^{3n} * S_{k}

Now if 2n = P+1 and P is prime of the form 8n +/- 3 and k = (P-1)/2, the side on the right = 0 mod P and only the terms S_{-1}, (P+1)*S_{0},(P+1)*S_{P-1} \{and} S_{p} not divisible by P on the left are . My experience is that S(-1) = 3, S(0) = 2, S(P-1) = P*S + 10 and S(P) = P*R + 3. Thus my new conjecture is that If and only If 6*2^((P+1)/2) equals -12 mod P, where P is a number of the form 8n +/- 3, then P is prime. I checked all 45 of my false hits, F, under 3 million, i.e. where S_((F-1)/2) = 0 mod F. However, I hadn't yet gone back and checked whether any composite meets this latter test and also does not have a zero at S_((F-1)/2).
Edit I found ten false hits under 500,000. All were composites F such that S((F-1)/2) > 0 mod F. Thus there is a need to further check that in the series S_0 = 2, S_1 = 3, S_n = 6*S_(n-1) - S_(n-2) - 6 that S((P-1)/2) = 0 mod P to determine that P is prime. None the less, both of these checks take far less time than checking that each and every term S_i is not equal 0 for i < (p-1)/2 plus you have the advantage that all primes of the form 8n +/- 3 apparently meet the test.

 

[ramsey2879]

So the prime test for P of the form 8n +/- 3 is in two parts:

A) If P is prime then 2^((P-1)/2) = -1 mod P
B) If P is prime then S((P-1)/2)** = 0 mod P
** S is the recursive series S_0 = 2, S_1 = 3, S_n = 6*S_(n-1) - S_(n-2) - 6

I did some more exploring and came up with a similar test for primes of the form 8n +/- 1

A) If P is prime then 2^((P-1)/2) = 1 mod P
B) If P is prime then R((P-1)/2)** = 0 mod P
** R is the recursive series R_0 = 0, R_1 = 1, R_n = 6*R_(n-1) - R_(n-2) + 2, which is OEIS A001108.

Both discoveries came from the following observations.
.
I created the R' type series by taking R'_i as the sum of two adjacent S terms + 1 and dividing by 2, i.e. R'_i = (S_i + S_(i+1) + 1)/2 which is the series R'_0 = 3, R'_1 = 7, having the recurrence R'_n = 6*R'_(n-1) - R'_(n-2) - 4. Then I noted that S_(i+1) equals (R_i + R_(i+1) + 2)/4 for all i. From this I derived the summation property that I mentioned in the first post. Then I decide to check the R' series mod primes of the form 8n +/- 1 and discovered that R'_((P-1)/2) = 3 mod P. So I subtracted 3 from each term and got each term = 0 mod 4. Therefore, I divided each term by 4. What is interesting is that each term of the R series taken as an argument of a triangular number yields the square triangular numbers, that is R*(R+1)/2 is always a perfect square.

With the above discoveries a proof of these tests might be possible. Have the tests A already been proven? I would like to verify those frist if possible.

 

[dodo]

Hi, ramsey,

... P of the form 8n +/- 3 ...
A) If P is prime then 2^((P-1)/2) = -1 mod P
[...]
... primes of the form 8n +/- 1
A) If P is prime then 2^((P-1)/2) = 1 mod P

This follows from Euler's criterion (in that page, take a=2). And 2 is a 'quadratic residue' mod p (meaning, there is another number whose square is congruent to 2 mod p) whenever the prime is of the form 8k±1 (this statement is called the second suplement to the law of quadratic reciprocity).