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?
Indicating multiple different modes of speech (fantasy language or telepathy)
How to deal with or prevent idle in the test team?
How can I raise concerns with a new DM about XP splitting?
How will losing mobility of one hand affect my career as a programmer?
Partial sums of primes
What was required to accept "troll"?
I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?
Is exact Kanji stroke length important?
Proof of Lemma: Every integer can be written as a product of primes
Could solar power be utilized and substitute coal in the 19th century?
Stereotypical names
Should my PhD thesis be submitted under my legal name?
My boss asked me to take a one-day class, then signs it up as a day off
Would it be legal for a US State to ban exports of a natural resource?
word describing multiple paths to the same abstract outcome
Is there enough fresh water in the world to eradicate the drinking water crisis?
Hostile work environment after whistle-blowing on coworker and our boss. What do I do?
What does the "3am" section means in manpages?
Can I create an upright 7-foot × 5-foot wall with the Minor Illusion spell?
Can the electrostatic force be infinite in magnitude?
Teaching indefinite integrals that require special-casing
Is there an Impartial Brexit Deal comparison site?
Can I use my Chinese passport to enter China after I acquired another citizenship?
Can I rely on these GitHub repository files?
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?
$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.
elementary-number-theory prime-numbers
New contributor
$endgroup$
add a comment |
$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.
elementary-number-theory prime-numbers
New contributor
$endgroup$
9
$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
5 hours ago
1
$begingroup$
See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– mfl
5 hours ago
$begingroup$
sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
$endgroup$
– David
5 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
5 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
5 hours ago
add a comment |
$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.
elementary-number-theory prime-numbers
New contributor
$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
elementary-number-theory prime-numbers
New contributor
New contributor
edited 4 hours ago
Mr. Brooks
43411338
43411338
New contributor
asked 5 hours ago
DavidDavid
1215
1215
New contributor
New contributor
9
$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
5 hours ago
1
$begingroup$
See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– mfl
5 hours ago
$begingroup$
sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
$endgroup$
– David
5 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
5 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
5 hours ago
add a comment |
9
$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
5 hours ago
1
$begingroup$
See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– mfl
5 hours ago
$begingroup$
sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
$endgroup$
– David
5 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
5 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
5 hours ago
9
9
$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
5 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
5 hours ago
1
1
$begingroup$
See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– mfl
5 hours ago
$begingroup$
See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– mfl
5 hours ago
$begingroup$
sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
$endgroup$
– David
5 hours ago
$begingroup$
sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
$endgroup$
– David
5 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
5 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
5 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
5 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
5 hours ago
add a comment |
3 Answers
3
active
oldest
votes
$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$.
$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
4 hours ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
3 hours 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
3 hours ago
add a comment |
$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).
$endgroup$
$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
2 hours ago
$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
30 mins ago
add a comment |
$begingroup$
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 $fracNp_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 multiication), the next one not eliminated by previous members as a least in progression factor, is the product of the next two not used up.
$endgroup$
add a comment |
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$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$.
$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
4 hours ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
3 hours 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
3 hours ago
add a comment |
$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$.
$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
4 hours ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
3 hours 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
3 hours ago
add a comment |
$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$.
$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$.
answered 4 hours 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
4 hours ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
3 hours 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
3 hours ago
add a comment |
$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
4 hours ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
3 hours 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
3 hours 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
4 hours 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
4 hours ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
3 hours ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
3 hours 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
3 hours 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
3 hours ago
add a comment |
$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).
$endgroup$
$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
2 hours ago
$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
30 mins ago
add a comment |
$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).
$endgroup$
$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
2 hours ago
$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
30 mins ago
add a comment |
$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).
$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).
edited 4 hours ago
answered 5 hours ago
Eric WofseyEric Wofsey
190k14216348
190k14216348
$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
2 hours ago
$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
30 mins ago
add a comment |
$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
2 hours ago
$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
30 mins ago
$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
2 hours ago
$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
2 hours ago
$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
30 mins ago
$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
30 mins ago
add a comment |
$begingroup$
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 $fracNp_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 multiication), the next one not eliminated by previous members as a least in progression factor, is the product of the next two not used up.
$endgroup$
add a comment |
$begingroup$
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 $fracNp_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 multiication), the next one not eliminated by previous members as a least in progression factor, is the product of the next two not used up.
$endgroup$
add a comment |
$begingroup$
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 $fracNp_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 multiication), the next one not eliminated by previous members as a least in progression factor, is the product of the next two not used up.
$endgroup$
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 $fracNp_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 multiication), the next one not eliminated by previous members as a least in progression factor, is the product of the next two not used up.
answered 11 mins ago
Roddy MacPheeRoddy MacPhee
573118
573118
add a comment |
add a comment |
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.
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.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
9
$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
5 hours ago
1
$begingroup$
See Sieve of Eratosthenes en.wikipedia.org/wiki/Sieve_of_Eratosthenes
$endgroup$
– mfl
5 hours ago
$begingroup$
sorry, i mean that 77 is the next prime, times the previous prime. ill edit to clarify
$endgroup$
– David
5 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
5 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
5 hours ago