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.


closed as unclear what you're asking by mrtaurho, Dietrich Burde, YiFan, Lee David Chung Lin, Parcly Taxel Mar 26 at 3:25

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 11
    $\begingroup$ Your description is confusing--for instance, if the current prime number is $7$, then "the next number divisible by the current prime number, except for any numbers divisible by primes we already have" would be $77$, which is not the next prime (the next prime is $11$). $\endgroup$ – Eric Wofsey Mar 25 at 20:24
  • 1
    $\begingroup$ See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes $\endgroup$ – mfl Mar 25 at 20:25
  • $\begingroup$ sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify $\endgroup$ – David Mar 25 at 20:26
  • $\begingroup$ Welcome to Math Stack Exchange. Are you saying that, if $p_n$ is the $n^{th}$ prime number, then the next composite number after $p_n^2$ not divisible by $p_1,p_2,...,p_{n-1}$ is $p_n\times p_{n+1}$? $\endgroup$ – J. W. Tanner Mar 25 at 20:28
  • 2
    $\begingroup$ Hi. Your title & first sentence still don't make sense, a prime isn't divisible by anything but itself & 1. What are you asking? Use enough words, phrases & sentences to say what you mean. Clarify via edits, not commments. $\endgroup$ – philipxy Mar 26 at 1:57

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}$.


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}$.

  • $\begingroup$ gotcha. its like a numerical logical tautology. wish I could mark both correct. no disrespect to eric who also had a good answer and got there first, but this one i understood a bit easier. $\endgroup$ – David Mar 25 at 21:35
  • $\begingroup$ Actually on reading eric's it seems we really more or less have the same answer. $\endgroup$ – fleablood Mar 25 at 21:52
  • $\begingroup$ yes, i just meant i personally found your phrasing a little easier to understand, not being a mathematician, but both are good answers $\endgroup$ – David Mar 25 at 22:05

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).

  • $\begingroup$ Does your solution mean that we can predict the next prime $p_{k+1}$ if we know the prime $p_k$ and apply the op method? $\endgroup$ – user25406 Mar 25 at 23:21
  • $\begingroup$ Well, you can find the next prime by the OP's method. I'm not sure how this is a "prediction", though. $\endgroup$ – Eric Wofsey Mar 26 at 1:15
  • $\begingroup$ You are right. I realized that we are looking for a number $M=p_k*p_{k+1}=p_{k}^2 +m*p_k=p_k*(p_k+m)$ with $m=2,4,6,8...$ and $p_{k+1}=p_k+m$. So we can't predict the next prime since we have to check different values of $m$. For twin primes, $m=2$ and we just don't know which particular value of $m$ is going to provide the next prime. $\endgroup$ – user25406 Mar 26 at 12:17

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.