Is the next prime number always the next number divisible by the current prime number, except for any numbers previously divisible by primes?There is a prime between $n$ and $n^2$, without BertrandThe number of numbers not divisible by $2,3,5,7$ or $11$ between multiples of $2310$Is the product of two primes ALWAYS a semiprime?Why are all non-prime numbers divisible by a prime number?Finding the rank of a particular number in a sequence of the sum of numbers and their highest prime factorA number n is not a Prime no and lies between 1 to 301,how many such numbers are there which is not divisible by 2,3,5,7.List of positive integers NOT divisible by smallest q prime numbersan upper bound for number of prime divisorsCan you propose a conjectural $textUpper bound(x)$ for the counting function of a sequence of primes arising from the Eratosthenes sieve?Interesting sequence involving prime numbers jumping on the number line.What is the maximum difference between these two functions?

Proof of Lemma: Every integer can be written as a product of primes

Why is delta-v is the most useful quantity for planning space travel?

What does the "3am" section means in manpages?

Hostile work environment after whistle-blowing on coworker and our boss. What do I do?

Are taller landing gear bad for aircraft, particulary large airliners?

node command while defining a coordinate in TikZ

Why isn't KTEX's runway designation 10/28 instead of 9/27?

Installing PowerShell on 32-bit Kali OS fails

Did US corporations pay demonstrators in the German demonstrations against article 13?

Can I create an upright 7ft x 5ft wall with Minor Illusion?

How to be able to process a large JSON response?

What is the term when two people sing in harmony, but they aren't singing the same notes?

Resetting two CD4017 counters simultaneously, only one resets

Can somebody explain Brexit in a few child-proof sentences?

How did Monica know how to operate Carol's "designer"?

Superhero words!

Freedom of speech and where it applies

Indicating multiple different modes of speech (fantasy language or telepathy)

Partial sums of primes

Pronouncing Homer as in modern Greek

Is it okay / does it make sense for another player to join a running game of Munchkin?

Left multiplication is homeomorphism of topological groups

Greatest common substring

Java - What do constructor type arguments mean when placed *before* the type?



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


There is a prime between $n$ and $n^2$, without BertrandThe number of numbers not divisible by $2,3,5,7$ or $11$ between multiples of $2310$Is the product of two primes ALWAYS a semiprime?Why are all non-prime numbers divisible by a prime number?Finding the rank of a particular number in a sequence of the sum of numbers and their highest prime factorA number n is not a Prime no and lies between 1 to 301,how many such numbers are there which is not divisible by 2,3,5,7.List of positive integers NOT divisible by smallest q prime numbersan upper bound for number of prime divisorsCan you propose a conjectural $textUpper bound(x)$ for the counting function of a sequence of primes arising from the Eratosthenes sieve?Interesting sequence involving prime numbers jumping on the number line.What is the maximum difference between these two functions?













2












$begingroup$


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.










share|cite|improve this question









New contributor




David is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$







  • 4




    $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
    2 hours ago










  • $begingroup$
    See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    $endgroup$
    – mfl
    2 hours ago










  • $begingroup$
    sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
    $endgroup$
    – David
    2 hours ago










  • $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_ntimes p_n+1$?
    $endgroup$
    – J. W. Tanner
    2 hours ago











  • $begingroup$
    ... i think so? i was just playing with prime numbers.. and noticed that after each square of the prime number, the next prime number was the next multiple that wasn't divisible by a smaller prime.. so 5x5 = 25, but the numbers not divisible by 2,3 above that are 29,31,35. 35 is 7x5 - i.e. the current prime times the next prime. i checked it held true for 7 and 11 but wondered if it was universal
    $endgroup$
    – David
    1 hour ago















2












$begingroup$


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.










share|cite|improve this question









New contributor




David is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$







  • 4




    $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
    2 hours ago










  • $begingroup$
    See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    $endgroup$
    – mfl
    2 hours ago










  • $begingroup$
    sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
    $endgroup$
    – David
    2 hours ago










  • $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_ntimes p_n+1$?
    $endgroup$
    – J. W. Tanner
    2 hours ago











  • $begingroup$
    ... i think so? i was just playing with prime numbers.. and noticed that after each square of the prime number, the next prime number was the next multiple that wasn't divisible by a smaller prime.. so 5x5 = 25, but the numbers not divisible by 2,3 above that are 29,31,35. 35 is 7x5 - i.e. the current prime times the next prime. i checked it held true for 7 and 11 but wondered if it was universal
    $endgroup$
    – David
    1 hour ago













2












2








2


1



$begingroup$


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.










share|cite|improve this question









New contributor




David is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$




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.







elementary-number-theory prime-numbers






share|cite|improve this question









New contributor




David is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|cite|improve this question









New contributor




David is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|cite|improve this question




share|cite|improve this question








edited 1 hour ago









Mr. Brooks

43411338




43411338






New contributor




David is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 2 hours ago









DavidDavid

1165




1165




New contributor




David is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





David is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






David is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







  • 4




    $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
    2 hours ago










  • $begingroup$
    See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    $endgroup$
    – mfl
    2 hours ago










  • $begingroup$
    sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
    $endgroup$
    – David
    2 hours ago










  • $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_ntimes p_n+1$?
    $endgroup$
    – J. W. Tanner
    2 hours ago











  • $begingroup$
    ... i think so? i was just playing with prime numbers.. and noticed that after each square of the prime number, the next prime number was the next multiple that wasn't divisible by a smaller prime.. so 5x5 = 25, but the numbers not divisible by 2,3 above that are 29,31,35. 35 is 7x5 - i.e. the current prime times the next prime. i checked it held true for 7 and 11 but wondered if it was universal
    $endgroup$
    – David
    1 hour ago












  • 4




    $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
    2 hours ago










  • $begingroup$
    See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    $endgroup$
    – mfl
    2 hours ago










  • $begingroup$
    sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
    $endgroup$
    – David
    2 hours ago










  • $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_ntimes p_n+1$?
    $endgroup$
    – J. W. Tanner
    2 hours ago











  • $begingroup$
    ... i think so? i was just playing with prime numbers.. and noticed that after each square of the prime number, the next prime number was the next multiple that wasn't divisible by a smaller prime.. so 5x5 = 25, but the numbers not divisible by 2,3 above that are 29,31,35. 35 is 7x5 - i.e. the current prime times the next prime. i checked it held true for 7 and 11 but wondered if it was universal
    $endgroup$
    – David
    1 hour ago







4




4




$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
2 hours ago




$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
2 hours ago












$begingroup$
See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– mfl
2 hours ago




$begingroup$
See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– mfl
2 hours ago












$begingroup$
sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
$endgroup$
– David
2 hours ago




$begingroup$
sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
$endgroup$
– David
2 hours ago












$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_ntimes p_n+1$?
$endgroup$
– J. W. Tanner
2 hours ago





$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_ntimes p_n+1$?
$endgroup$
– J. W. Tanner
2 hours ago













$begingroup$
... i think so? i was just playing with prime numbers.. and noticed that after each square of the prime number, the next prime number was the next multiple that wasn't divisible by a smaller prime.. so 5x5 = 25, but the numbers not divisible by 2,3 above that are 29,31,35. 35 is 7x5 - i.e. the current prime times the next prime. i checked it held true for 7 and 11 but wondered if it was universal
$endgroup$
– David
1 hour ago




$begingroup$
... i think so? i was just playing with prime numbers.. and noticed that after each square of the prime number, the next prime number was the next multiple that wasn't divisible by a smaller prime.. so 5x5 = 25, but the numbers not divisible by 2,3 above that are 29,31,35. 35 is 7x5 - i.e. the current prime times the next prime. i checked it held true for 7 and 11 but wondered if it was universal
$endgroup$
– David
1 hour ago










2 Answers
2






active

oldest

votes


















2












$begingroup$

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_kcdot 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_kcdot 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 $nne 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^mge 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$.






share|cite|improve this answer









$endgroup$












  • $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
    54 mins ago











  • $begingroup$
    Actually on reading eric's it seems we really more or less have the same answer.
    $endgroup$
    – fleablood
    37 mins ago










  • $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
    23 mins ago


















4












$begingroup$

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






share|cite|improve this answer











$endgroup$












    Your Answer





    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "69"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader:
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    ,
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );






    David is a new contributor. Be nice, and check out our Code of Conduct.









    draft saved

    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3162271%2fis-the-next-prime-number-always-the-next-number-divisible-by-the-current-prime-n%23new-answer', 'question_page');

    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    2












    $begingroup$

    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_kcdot 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_kcdot 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 $nne 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^mge 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$.






    share|cite|improve this answer









    $endgroup$












    • $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
      54 mins ago











    • $begingroup$
      Actually on reading eric's it seems we really more or less have the same answer.
      $endgroup$
      – fleablood
      37 mins ago










    • $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
      23 mins ago















    2












    $begingroup$

    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_kcdot 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_kcdot 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 $nne 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^mge 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$.






    share|cite|improve this answer









    $endgroup$












    • $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
      54 mins ago











    • $begingroup$
      Actually on reading eric's it seems we really more or less have the same answer.
      $endgroup$
      – fleablood
      37 mins ago










    • $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
      23 mins ago













    2












    2








    2





    $begingroup$

    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_kcdot 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_kcdot 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 $nne 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^mge 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$.






    share|cite|improve this answer









    $endgroup$



    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_kcdot 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_kcdot 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 $nne 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^mge 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$.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 1 hour ago









    fleabloodfleablood

    73.4k22791




    73.4k22791











    • $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
      54 mins ago











    • $begingroup$
      Actually on reading eric's it seems we really more or less have the same answer.
      $endgroup$
      – fleablood
      37 mins ago










    • $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
      23 mins ago
















    • $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
      54 mins ago











    • $begingroup$
      Actually on reading eric's it seems we really more or less have the same answer.
      $endgroup$
      – fleablood
      37 mins ago










    • $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
      23 mins ago















    $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
    54 mins ago





    $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
    54 mins ago













    $begingroup$
    Actually on reading eric's it seems we really more or less have the same answer.
    $endgroup$
    – fleablood
    37 mins ago




    $begingroup$
    Actually on reading eric's it seems we really more or less have the same answer.
    $endgroup$
    – fleablood
    37 mins ago












    $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
    23 mins ago




    $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
    23 mins ago











    4












    $begingroup$

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






    share|cite|improve this answer











    $endgroup$

















      4












      $begingroup$

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






      share|cite|improve this answer











      $endgroup$















        4












        4








        4





        $begingroup$

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






        share|cite|improve this answer











        $endgroup$



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







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited 1 hour ago

























        answered 1 hour ago









        Eric WofseyEric Wofsey

        190k14216348




        190k14216348




















            David is a new contributor. Be nice, and check out our Code of Conduct.









            draft saved

            draft discarded


















            David is a new contributor. Be nice, and check out our Code of Conduct.












            David is a new contributor. Be nice, and check out our Code of Conduct.











            David is a new contributor. Be nice, and check out our Code of Conduct.














            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid


            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.

            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3162271%2fis-the-next-prime-number-always-the-next-number-divisible-by-the-current-prime-n%23new-answer', 'question_page');

            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Oświęcim Innehåll Historia | Källor | Externa länkar | Navigeringsmeny50°2′18″N 19°13′17″Ö / 50.03833°N 19.22139°Ö / 50.03833; 19.2213950°2′18″N 19°13′17″Ö / 50.03833°N 19.22139°Ö / 50.03833; 19.221393089658Nordisk familjebok, AuschwitzInsidan tro och existensJewish Community i OświęcimAuschwitz Jewish Center: MuseumAuschwitz Jewish Center

            Valle di Casies Indice Geografia fisica | Origini del nome | Storia | Società | Amministrazione | Sport | Note | Bibliografia | Voci correlate | Altri progetti | Collegamenti esterni | Menu di navigazione46°46′N 12°11′E / 46.766667°N 12.183333°E46.766667; 12.183333 (Valle di Casies)46°46′N 12°11′E / 46.766667°N 12.183333°E46.766667; 12.183333 (Valle di Casies)Sito istituzionaleAstat Censimento della popolazione 2011 - Determinazione della consistenza dei tre gruppi linguistici della Provincia Autonoma di Bolzano-Alto Adige - giugno 2012Numeri e fattiValle di CasiesDato IstatTabella dei gradi/giorno dei Comuni italiani raggruppati per Regione e Provincia26 agosto 1993, n. 412Heraldry of the World: GsiesStatistiche I.StatValCasies.comWikimedia CommonsWikimedia CommonsValle di CasiesSito ufficialeValle di CasiesMM14870458910042978-6

            Typsetting diagram chases (with TikZ?) Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern)How to define the default vertical distance between nodes?Draw edge on arcNumerical conditional within tikz keys?TikZ: Drawing an arc from an intersection to an intersectionDrawing rectilinear curves in Tikz, aka an Etch-a-Sketch drawingLine up nested tikz enviroments or how to get rid of themHow to place nodes in an absolute coordinate system in tikzCommutative diagram with curve connecting between nodesTikz with standalone: pinning tikz coordinates to page cmDrawing a Decision Diagram with Tikz and layout manager