New Test for Primes form 8n =/- 3

In summary, Dodo discovered a new property of a recursive series used in a prior test, which allows for a correction that includes all primes of the form 8n +/- 3 and excludes composites. This property states that a certain sum is congruent to 0 mod P, where P is a prime of the form 8n +/- 3. Dodo also found a similar test for primes of the form 8n +/- 1. Both of these tests have been derived from observations made about the recursive series and have not yet been proven. They can be verified by checking the properties A) and B) listed for each form of primes.
  • #1
ramsey2879
841
3
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.
 
Last edited:
Physics news on Phys.org
  • #2
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.
 
  • #3
Hi, ramsey,
ramsey2879 said:
... 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).
 

1. What is the "New Test for Primes form 8n =/- 3"?

The "New Test for Primes form 8n =/- 3" is a mathematical method that can be used to determine whether a number is a prime number. It involves checking if a number can be written in the form of 8n =/- 3, where n is a whole number.

2. How is the "New Test for Primes form 8n =/- 3" different from other prime tests?

The "New Test for Primes form 8n =/- 3" is different from other prime tests because it is specifically designed to work with numbers that are multiples of 8. This makes it more efficient for finding primes in this particular form.

3. What are the advantages of using the "New Test for Primes form 8n =/- 3"?

The "New Test for Primes form 8n =/- 3" has several advantages, including its simplicity and efficiency for numbers in the form of 8n =/- 3. It also has a lower chance of producing false positives compared to other prime tests.

4. Can the "New Test for Primes form 8n =/- 3" be used for all numbers?

No, the "New Test for Primes form 8n =/- 3" is specifically designed to work with numbers that are multiples of 8. It may not be as effective for numbers outside of this form.

5. How can the "New Test for Primes form 8n =/- 3" be used in real-world applications?

The "New Test for Primes form 8n =/- 3" can be used in cryptography and security systems to generate large prime numbers. It can also be used in number theory research to study the properties of primes in this particular form.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
13
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
705
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Precalculus Mathematics Homework Help
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
899
  • Calculus and Beyond Homework Help
Replies
20
Views
1K
  • Precalculus Mathematics Homework Help
Replies
7
Views
1K
  • Precalculus Mathematics Homework Help
Replies
17
Views
2K
  • Precalculus Mathematics Homework Help
Replies
16
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
Back
Top