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?
Could solar power be utilized and substitute coal in the 19th century?
Is it okay / does it make sense for another player to join a running game of Munchkin?
Resetting two CD4017 counters simultaneously, only one resets
What does the "3am" section means in manpages?
Is it possible to build a CPA Secure encryption scheme which remains secure even when the encryption of secret key is given?
Latex for-and in equation
What (else) happened July 1st 1858 in London?
How to interpret the phrase "t’en a fait voir à toi"?
The One-Electron Universe postulate is true - what simple change can I make to change the whole universe?
Is the next prime number always the next number divisible by the current prime number, except for any numbers previously divisible by primes?
Superhero words!
Meta programming: Declare a new struct on the fly
You're three for three
Can somebody explain Brexit in a few child-proof sentences?
Giant Toughroad SLR 2 for 200 miles in two days, will it make it?
Freedom of speech and where it applies
How do ultrasonic sensors differentiate between transmitted and received signals?
For airliners, what prevents wing strikes on landing in bad weather?
Why are all the doors on Ferenginar (the Ferengi home world) far shorter than the average Ferengi?
word describing multiple paths to the same abstract outcome
Is there an Impartial Brexit Deal comparison site?
Can a malicious addon access internet history and such in chrome/firefox?
Fast sudoku solver
Organic chemistry Iodoform Reaction
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$
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
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 1 hour ago
Mr. Brooks
43411338
43411338
New contributor
asked 2 hours ago
DavidDavid
1165
1165
New contributor
New contributor
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
add a comment |
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
add a comment |
2 Answers
2
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
55 mins ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
38 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
25 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$
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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
2 Answers
2
active
oldest
votes
2 Answers
2
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
55 mins ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
38 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
25 mins 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
55 mins ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
38 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
25 mins 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 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
55 mins ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
38 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
25 mins 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
55 mins ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
38 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
25 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
55 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
55 mins ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
38 mins ago
$begingroup$
Actually on reading eric's it seems we really more or less have the same answer.
$endgroup$
– fleablood
38 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
25 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
25 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$
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$
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 1 hour ago
answered 2 hours ago
Eric WofseyEric Wofsey
190k14216348
190k14216348
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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');
var $window = $(window),
onScroll = function(e)
var $elem = $('.new-login-left'),
docViewTop = $window.scrollTop(),
docViewBottom = docViewTop + $window.height(),
elemTop = $elem.offset().top,
elemBottom = elemTop + $elem.height();
if ((docViewTop elemBottom))
StackExchange.using('gps', function() StackExchange.gps.track('embedded_signup_form.view', location: 'question_page' ); );
$window.unbind('scroll', onScroll);
;
$window.on('scroll', onScroll);
);
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
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