I: A PRIME NUMBER GENERATING THEOREM

We address the question:

Do we necessarily discover the primes, as in the sieve of Eratosthenes,

or can we also generate them sequentially?

In other words, given the first k primes, can we generate the prime p(k+1)

algorithmically, without testing any number larger than p(k) for primality?

We give an affirmative answer, defining two algorithms based on the

following theorem:

Theorem:

For all i < k, let p(i) denote the i'th prime, and define a(i) such that

a(i) < p(i), and:

p(k) + a(i) ≡ 0 (mod p(i))

Let d(k) be such that, for all d < d(k), there is some i such that:

d ≡ a(i) (mod p(i)).

Then:

p(k+1) = p(k) + d(k).

Proof:

For all d < d(k), there is some i such that:

p(k) + d ≡ 0 (mod p(i)).

Since p(k+1) < 2p(k):

d(k) < p(k).

Hence, p(k) + d(k) < p(k)*p(k), and so it is the prime p(k+1).