Mixing
Maximum runs of composites in arithmetic progressions
$begingroup$
Is there a proof that every arithmetic progression of gap $p$ has a prime in the interval $[p, p^2)$?
Put another way, can you prove the following:
For all primes $p$, and all integers $0 le m <p$, there exists $ninBbb{Z}$ with $1le n < p$ such that $np+m$ is prime.
I think I have a proof sketch but it's fiddly and I don't want to reinvent the wheel (likely badly).
To illustrate, here's the result checked for $p = 5$:
Arithmetic progressions with gaps $5$ from $5$ to $24$ ($p$ to $p^2-1$):
$boldsymbol{5},10,15,20$
$6,boldsymbol{11},16,21$
$boldsymbol{7},12,boldsymbol{17},22$
$8,boldsymbol{13},18,boldsymbol{23}$
$9,14,boldsymbol{19},24$
As you can see, in bold, all of these arithmetic progressions have at least one prime. If one of these sequences didn't have a prime the theorem would be disproven for $p = 5$.
Note that proving that every arithmetic progression of gap $p$ and length $(p-1)$ has at least one number coprime to $(p-1)!$ should also prove the above, and indeed is more general, as if $n$ is coprime to $(p-1)!$ and is less than $p^2$ then it has to be prime.
number-theory elementary-number-theory prime-numbers prime-gaps
asked Jan 8 at 0:35
ClintonClinton
226139
$endgroup$
add a comment |
$begingroup$
Is there a proof that every arithmetic progression of gap $p$ has a prime in the interval $[p, p^2)$?
Put another way, can you prove the following:
For all primes $p$, and all integers $0 le m <p$, there exists $ninBbb{Z}$ with $1le n < p$ such that $np+m$ is prime.
I think I have a proof sketch but it's fiddly and I don't want to reinvent the wheel (likely badly).
To illustrate, here's the result checked for $p = 5$:
Arithmetic progressions with gaps $5$ from $5$ to $24$ ($p$ to $p^2-1$):
$boldsymbol{5},10,15,20$
$6,boldsymbol{11},16,21$
$boldsymbol{7},12,boldsymbol{17},22$
$8,boldsymbol{13},18,boldsymbol{23}$
$9,14,boldsymbol{19},24$
As you can see, in bold, all of these arithmetic progressions have at least one prime. If one of these sequences didn't have a prime the theorem would be disproven for $p = 5$.
Note that proving that every arithmetic progression of gap $p$ and length $(p-1)$ has at least one number coprime to $(p-1)!$ should also prove the above, and indeed is more general, as if $n$ is coprime to $(p-1)!$ and is less than $p^2$ then it has to be prime.
number-theory elementary-number-theory prime-numbers prime-gaps
asked Jan 8 at 0:35
ClintonClinton
226139
$endgroup$
1
$begingroup$
What do you mean? There are progressions of period $p$ with no primes at all in them (or exactly one prime). Then again, there are arbitrarily large blocks of consecutive composite numbers. But I'm not sure what you mean by "the interval $[p,p^2)$".
$endgroup$
– lulu
Jan 8 at 0:42
$begingroup$
What I mean by the interval $[p, p^2)$ is ${p, p+1, ... , p^2-1}$ Arithmetic progressions have terms in that interval ofpm + nfor1 <= m < pand0 <= n < p.
$endgroup$
– Clinton
Jan 8 at 1:01
$begingroup$
I've added a more formal explanation.
$endgroup$
– Clinton
Jan 8 at 1:06
1
$begingroup$
@Clinton I edited the formatting and wording of the formal statement. If I have misunderstood your intentions, feel free to edit.
$endgroup$
– jgon
Jan 8 at 1:45
$begingroup$
@jgon I think that's right. Thanks!
$endgroup$
– Clinton
Jan 8 at 1:51
add a comment |
$begingroup$
Is there a proof that every arithmetic progression of gap $p$ has a prime in the interval $[p, p^2)$?
Put another way, can you prove the following:
For all primes $p$, and all integers $0 le m <p$, there exists $ninBbb{Z}$ with $1le n < p$ such that $np+m$ is prime.
I think I have a proof sketch but it's fiddly and I don't want to reinvent the wheel (likely badly).
To illustrate, here's the result checked for $p = 5$:
Arithmetic progressions with gaps $5$ from $5$ to $24$ ($p$ to $p^2-1$):
$boldsymbol{5},10,15,20$
$6,boldsymbol{11},16,21$
$boldsymbol{7},12,boldsymbol{17},22$
$8,boldsymbol{13},18,boldsymbol{23}$
$9,14,boldsymbol{19},24$
As you can see, in bold, all of these arithmetic progressions have at least one prime. If one of these sequences didn't have a prime the theorem would be disproven for $p = 5$.
Note that proving that every arithmetic progression of gap $p$ and length $(p-1)$ has at least one number coprime to $(p-1)!$ should also prove the above, and indeed is more general, as if $n$ is coprime to $(p-1)!$ and is less than $p^2$ then it has to be prime.
number-theory elementary-number-theory prime-numbers prime-gaps
asked Jan 8 at 0:35
ClintonClinton
226139
$endgroup$
Is there a proof that every arithmetic progression of gap $p$ has a prime in the interval $[p, p^2)$?
Put another way, can you prove the following:
For all primes $p$, and all integers $0 le m <p$, there exists $ninBbb{Z}$ with $1le n < p$ such that $np+m$ is prime.
I think I have a proof sketch but it's fiddly and I don't want to reinvent the wheel (likely badly).
To illustrate, here's the result checked for $p = 5$:
Arithmetic progressions with gaps $5$ from $5$ to $24$ ($p$ to $p^2-1$):
$boldsymbol{5},10,15,20$
$6,boldsymbol{11},16,21$
$boldsymbol{7},12,boldsymbol{17},22$
$8,boldsymbol{13},18,boldsymbol{23}$
$9,14,boldsymbol{19},24$
As you can see, in bold, all of these arithmetic progressions have at least one prime. If one of these sequences didn't have a prime the theorem would be disproven for $p = 5$.
Note that proving that every arithmetic progression of gap $p$ and length $(p-1)$ has at least one number coprime to $(p-1)!$ should also prove the above, and indeed is more general, as if $n$ is coprime to $(p-1)!$ and is less than $p^2$ then it has to be prime.
number-theory elementary-number-theory prime-numbers prime-gaps
number-theory elementary-number-theory prime-numbers prime-gaps
asked Jan 8 at 0:35
ClintonClinton
226139
asked Jan 8 at 0:35
ClintonClinton
226139
edited Jan 8 at 1:55
Clinton
asked Jan 8 at 0:35
ClintonClinton
226139
asked Jan 8 at 0:35
ClintonClinton
226139
asked Jan 8 at 0:35
ClintonClinton
226139
226139
1
$begingroup$
What do you mean? There are progressions of period $p$ with no primes at all in them (or exactly one prime). Then again, there are arbitrarily large blocks of consecutive composite numbers. But I'm not sure what you mean by "the interval $[p,p^2)$".
$endgroup$
– lulu
Jan 8 at 0:42
$begingroup$
What I mean by the interval $[p, p^2)$ is ${p, p+1, ... , p^2-1}$ Arithmetic progressions have terms in that interval ofpm + nfor1 <= m < pand0 <= n < p.
$endgroup$
– Clinton
Jan 8 at 1:01
$begingroup$
I've added a more formal explanation.
$endgroup$
– Clinton
Jan 8 at 1:06
1
$begingroup$
@Clinton I edited the formatting and wording of the formal statement. If I have misunderstood your intentions, feel free to edit.
$endgroup$
– jgon
Jan 8 at 1:45
$begingroup$
@jgon I think that's right. Thanks!
$endgroup$
– Clinton
Jan 8 at 1:51
add a comment |
1
$begingroup$
What do you mean? There are progressions of period $p$ with no primes at all in them (or exactly one prime). Then again, there are arbitrarily large blocks of consecutive composite numbers. But I'm not sure what you mean by "the interval $[p,p^2)$".
$endgroup$
– lulu
Jan 8 at 0:42
$begingroup$
What I mean by the interval $[p, p^2)$ is ${p, p+1, ... , p^2-1}$ Arithmetic progressions have terms in that interval ofpm + nfor1 <= m < pand0 <= n < p.
$endgroup$
– Clinton
Jan 8 at 1:01
$begingroup$
I've added a more formal explanation.
$endgroup$
– Clinton
Jan 8 at 1:06
1
$begingroup$
@Clinton I edited the formatting and wording of the formal statement. If I have misunderstood your intentions, feel free to edit.
$endgroup$
– jgon
Jan 8 at 1:45
$begingroup$
@jgon I think that's right. Thanks!
$endgroup$
– Clinton
Jan 8 at 1:51
1
1
$begingroup$
What do you mean? There are progressions of period $p$ with no primes at all in them (or exactly one prime). Then again, there are arbitrarily large blocks of consecutive composite numbers. But I'm not sure what you mean by "the interval $[p,p^2)$".
$endgroup$
– lulu
Jan 8 at 0:42
$begingroup$
What do you mean? There are progressions of period $p$ with no primes at all in them (or exactly one prime). Then again, there are arbitrarily large blocks of consecutive composite numbers. But I'm not sure what you mean by "the interval $[p,p^2)$".
$endgroup$
– lulu
Jan 8 at 0:42
$begingroup$
What I mean by the interval $[p, p^2)$ is ${p, p+1, ... , p^2-1}$ Arithmetic progressions have terms in that interval of
pm + n for 1 <= m < p and 0 <= n < p.$endgroup$
– Clinton
Jan 8 at 1:01
$begingroup$
What I mean by the interval $[p, p^2)$ is ${p, p+1, ... , p^2-1}$ Arithmetic progressions have terms in that interval of
pm + n for 1 <= m < p and 0 <= n < p.$endgroup$
– Clinton
Jan 8 at 1:01
$begingroup$
I've added a more formal explanation.
$endgroup$
– Clinton
Jan 8 at 1:06
$begingroup$
I've added a more formal explanation.
$endgroup$
– Clinton
Jan 8 at 1:06
1
1
$begingroup$
@Clinton I edited the formatting and wording of the formal statement. If I have misunderstood your intentions, feel free to edit.
$endgroup$
– jgon
Jan 8 at 1:45
$begingroup$
@Clinton I edited the formatting and wording of the formal statement. If I have misunderstood your intentions, feel free to edit.
$endgroup$
– jgon
Jan 8 at 1:45
$begingroup$
@jgon I think that's right. Thanks!
$endgroup$
– Clinton
Jan 8 at 1:51
$begingroup$
@jgon I think that's right. Thanks!
$endgroup$
– Clinton
Jan 8 at 1:51
add a comment |
0
active
oldest
votes
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
});
}
});
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%2f3065679%2fmaximum-runs-of-composites-in-arithmetic-progressions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
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%2f3065679%2fmaximum-runs-of-composites-in-arithmetic-progressions%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
1
$begingroup$
What do you mean? There are progressions of period $p$ with no primes at all in them (or exactly one prime). Then again, there are arbitrarily large blocks of consecutive composite numbers. But I'm not sure what you mean by "the interval $[p,p^2)$".
$endgroup$
– lulu
Jan 8 at 0:42
$begingroup$
What I mean by the interval $[p, p^2)$ is ${p, p+1, ... , p^2-1}$ Arithmetic progressions have terms in that interval of
pm + nfor1 <= m < pand0 <= n < p.$endgroup$
– Clinton
Jan 8 at 1:01
$begingroup$
I've added a more formal explanation.
$endgroup$
– Clinton
Jan 8 at 1:06
1
$begingroup$
@Clinton I edited the formatting and wording of the formal statement. If I have misunderstood your intentions, feel free to edit.
$endgroup$
– jgon
Jan 8 at 1:45
$begingroup$
@jgon I think that's right. Thanks!
$endgroup$
– Clinton
Jan 8 at 1:51