2
$\begingroup$

The Wikipedia page for "Primality test", linked below [1], states that "all primes are of the form c#k + i for i < c# where c and k are integers, c# represents c primorial, and i represents the numbers that are coprime to c#."

I understand this to mean the following:

  • Pick a particular value for c, for example set c=11.
  • Compute the primorial of c, c#=2*3*5*7*11=2310.
  • The values that i can take on for this choice of c are: 1, 13, 17, ..., 2309. (The values 2, 3, 5, 7, and 11 are omitted due to being primes less than 11, and the list of possible i values ends at the largest prime smaller than c#=2310 or in this case 2309.)
  • For this c# every possible prime number above c#=2310, can be produced for some value k (any integer) and a particular value of i.
  • Note, I understand that the series will ALSO generate composite numbers, but my understanding is that it will be guaranteed to generate every prime above c#.

I tried to test this. Specifically, I checked to see if [(2^13)-1]=8191 (which is a prime number, specifically a Mersenne prime) can be generated by the sequence of numbers for c=11, c#=2310.

  • To find the appropriate value for k I computed [(2^13)-1]/(2310)=3.54... Thus I selected k=3 since the values of i are less than c#, and if k were any other value there would be no chance of reaching the number in question (8191).
  • Then I did [(2^13)-1]-3*2310=1261. And looked to see if 1261 is a possible value that i can take on. However, 1261 is not prime, so i can not equal 1261.
  • Thus I concluded that the series of numbers generated by c#k + i can not possibly equal [(2^13)-1] for the series generated by c=11.

So it would seem to me that the claim made in the Wikipedia page for Primality Tests that all prime numbers above c# can be generated by the series c#k+i is false. Am I misunderstanding the original claim? Or have a applied it incorrectly and make a mistake in the calculations? Any clarification regarding series of this form that generate all primes (plus some composites) would be greatly appreciated. (Is there a name for series of this type that I could use to search for more information?)

[1] Wikipedia page for "Primality test" https://en.wikipedia.org/wiki/Primality_test

$\endgroup$
2
  • 2
    $\begingroup$ It says coprime to $c\#$. Since $1261 = 13\cdot 97$, it is coprime to $11\#$. $\endgroup$ Commented Jul 25, 2018 at 21:54
  • $\begingroup$ @DanielFischer Thank you. I see now I have somehow misunderstood the original claim. The value 1261 is "coprime" with c# as it shares no common prime factors (2,3,5,7,11). This is many more possible values than I listed for i, or understood that i could take on. $\endgroup$
    – user669487
    Commented Jul 25, 2018 at 22:07

1 Answer 1

1
$\begingroup$

Yes, in the sense that , because it generates all numbers greater than c# that are coprime to it. It can generate, all primes greater than $c$ if $k$ is allowed to be 0.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .