Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

New Test for Primes form 8n =/- 3

  1. Mar 3, 2012 #1
    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: Mar 3, 2012
  2. jcsd
  3. Mar 5, 2012 #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.
  4. Mar 5, 2012 #3
    Hi, ramsey,

    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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook