Sieving by primes $< p_n = n$'th prime yields all primes $< p_n p_{n+1}$ (and $\,p_n^2)$

Question

Is the next prime number always the next number divisible by the current prime number, except for any numbers previously divisible by primes?

E.g. take prime number $7$, squared is $49$. The next numbers not previously divisible by $2,3,5$ are $53,59,61,67,71,73,77$ -i.e. the next number divisible by $7$ is $11 \times 7$ - the next prime number times the previous one.

Similarly, take $11$: squared $121$. the next numbers not divisible by $2,3,5,7$ are: $127,131,137,139,143$. i.e. $143$ is the next number divisible by $11$, which is $13 \times 11$, $13$ being the next prime in the sequence.

Is this always the case? Can it be that the next prime number in sequence is not neatly divisible by the previous one or has one in between?

Appreciate this may be a silly question, i'm not a mathematician.

Answer 1

Think of it this way. Let $p_k$ be the $k$ prime. Let $n$ be the first composite number greater than $p_k$ so that $n$ is not divisible by $p_1,..., p_{k-1}$.

Claim: $n = p_k\cdot p_{k+1}$.

Pf:

What else could it be? $n$ must have a prime factors. And those prime factor must be greater the $p_{k+1}$. The smallest number with at least two prime factors all bigger than $p_{k-1}$ must be $p_{k}\cdot p_{k+1}$ because $p_k, p_{k+1}$ are the smallest choices for prime factors and the fewer prime factors the smaller the number will be.

so $n= p_kp_{k+1}$ IF $n$ has at least two prime factors.

So if $n\ne p_kp_{k+1}$ then 1) $n \le p_kp_{k+1}$ and 2) $n$ has only one prime factor so $n=q^m$ for some prime $q$ and integer $m$.

If so, then $q \ge p_{k+1}$ then $q^m \ge p_{k+1}^m\ge p_{k+1}^2 > p_k*p_{k+1}$ which is a contradiction so $q= p_k$ and $n = p_k^m > p_k^2$. As $n$ is the smallest possible number, $n = p_k^3$ and $p_k^3 < p_k*p_{k+1}$.

That would mean $p_k^2 < p_{k+1}$.

This is impossible by Bertrands postulate.

So indeed the next composite number not divisible by $p_1,..., p_{k-1}$ larger than $p_k^2$ is $p_kp_{k+1}$.

Answer 2

Yes. First let me clarify what you are trying to say. Suppose we have a prime number $p$, and consider the smallest integer $n$ greater than $p^2$ which is a multiple of $p$ but which is not divisible by any prime less than $p$. The pattern you are observing is then that $n/p$ is the smallest prime number greater than $p$.

This is indeed true in general. To prove it, note that the multiples of $p$ are just numbers of the form $ap$ where $a$ is an integer. So in finding the smallest such multiple $n$ which is not divisible by any primes less than $p$, you are just finding the smallest integer $a>p$ which is not divisible by any prime less than $p$ and setting $n=ap$. Every prime factor of this $a$ is greater than or equal to $p$. Let us first suppose that $a$ has a prime factor $q$ which is greater than $p$. Then by minimality of $a$, we must have $a=q$ (otherwise $q$ would be a smaller candidate for $a$). Moreover, by minimality $a$ must be the smallest prime greater than $p$ (any smaller such prime would be a smaller candidate for $a$). So, $a=n/p$ is indeed the smallest prime greater than $p$.

The remaining case is that $a$ has no prime factors greater than $p$, which means $p$ is its only prime factor. That is, $a$ is a power of $p$. Then $a\geq p^2$ (and in fact $a=p^2$ by minimality). As before, $a$ must be less than any prime greater than $p$ by minimality. This means there are no prime numbers $q$ such that $p<q<p^2$. However, this is impossible, for instance by Bertrand's postulate (or see There is a prime between $n$ and $n^2$, without Bertrand for a simpler direct proof).

Answer 3

Yes. It follows from each composite, needing a least prime factor. Since you've eliminated possibilities up to $p_{k}$, the least prime factor of $\frac{N}{p_k}$ for N greater than the square, needs fall to the next non eliminated number (the next prime in this case). This can be generalized to arithmetic progressions in general that is closed under multiplication (aka form a magma along with multiplication), the next one not eliminated by previous members as a least in progression factor, is the product of the next two not used up.