Register to reply

New Test for Primes form 8n =/- 3

by ramsey2879
Tags: form, primes, test
Share this thread:
Mar3-12, 03:22 PM
P: 894
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;

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

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 [tex]S_{-1}, (P+1)*S_{0},(P+1)*S_{P-1} \{and} S_{p}[/tex] 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.
Phys.Org News Partner Science news on
'Office life' of bacteria may be their weak spot
Lunar explorers will walk at higher speeds than thought
Philips introduces BlueTouch, PulseRelief control for pain relief
Mar5-12, 10:14 AM
P: 894
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.
Mar5-12, 02:18 PM
P: 688
Hi, ramsey,
Quote Quote by ramsey2879 View Post
... 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).

Register to reply

Related Discussions
Primes of form 10^k + 1? Linear & Abstract Algebra 21
Twin Primes of the form (8n+5,8n+7) Linear & Abstract Algebra 11
Primes of the form 4n+1 Introductory Physics Homework 10
Infinetely many primes of the form 3n+1 Linear & Abstract Algebra 4
Primes of the form 2^m + 1 Introductory Physics Homework 1