Mixing
Proof that every arithmetic progression which might contain a prime does so.
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
It's been bugging me all afternoon - is there an easy proof that if $gcd(a,b) = 1$ there is a prime number $p$ of the form $p = an+b$?
I'm aware of Dirichlet's theorem that there are in fact infinitely many primes of this form but am hoping there is an elementary proof of this weaker form.
The fact that I have been unable to find any proof of this online suggests to me that it's in fact very easy and I am simply missing something obvious.
number-theory elementary-number-theory prime-numbers
edited Jul 28 at 17:09
Daniel Buck
2,3041623
asked Jul 25 at 16:31
Andrew
871211
 |Â
show 5 more comments
up vote
1
down vote
favorite
It's been bugging me all afternoon - is there an easy proof that if $gcd(a,b) = 1$ there is a prime number $p$ of the form $p = an+b$?
I'm aware of Dirichlet's theorem that there are in fact infinitely many primes of this form but am hoping there is an elementary proof of this weaker form.
The fact that I have been unable to find any proof of this online suggests to me that it's in fact very easy and I am simply missing something obvious.
number-theory elementary-number-theory prime-numbers
edited Jul 28 at 17:09
Daniel Buck
2,3041623
asked Jul 25 at 16:31
Andrew
871211
3
It's not hard to deduce the full form of Dirichlet from this special case.
– Lord Shark the Unknown
Jul 25 at 16:32
2
For any $k$ there is a prime of the form $a^kn+b$.
– Wojowu
Jul 25 at 16:41
2
Correct. $$
– Wojowu
Jul 25 at 16:47
1
Thank you 🙂 you've dissolved my problem
– Andrew
Jul 25 at 16:58
2
Yes, it's hard to prove, @AndrewSlattery. Whether it implies the full Dirichlet theorem depends on what precisely one considers the full theorem. What Dirichlet proved was more than just that there are infinitely many primes in every arithmetic progression $an + b$ with $gcd(a,b) = 1$, he proved that the sum of the reciprocals of the primes in such a progression diverges (and even some more). That "each such progression contains at least one prime" implies "each such progression contains infinitely many primes" is easy, but getting to "the sum of the reciprocals diverges" isn't.
– Daniel Fischer♦
Jul 25 at 18:34
 |Â
show 5 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
It's been bugging me all afternoon - is there an easy proof that if $gcd(a,b) = 1$ there is a prime number $p$ of the form $p = an+b$?
I'm aware of Dirichlet's theorem that there are in fact infinitely many primes of this form but am hoping there is an elementary proof of this weaker form.
The fact that I have been unable to find any proof of this online suggests to me that it's in fact very easy and I am simply missing something obvious.
number-theory elementary-number-theory prime-numbers
edited Jul 28 at 17:09
Daniel Buck
2,3041623
asked Jul 25 at 16:31
Andrew
871211
It's been bugging me all afternoon - is there an easy proof that if $gcd(a,b) = 1$ there is a prime number $p$ of the form $p = an+b$?
I'm aware of Dirichlet's theorem that there are in fact infinitely many primes of this form but am hoping there is an elementary proof of this weaker form.
The fact that I have been unable to find any proof of this online suggests to me that it's in fact very easy and I am simply missing something obvious.
number-theory elementary-number-theory prime-numbers
edited Jul 28 at 17:09
Daniel Buck
2,3041623
asked Jul 25 at 16:31
Andrew
871211
edited Jul 28 at 17:09
Daniel Buck
2,3041623
edited Jul 28 at 17:09
Daniel Buck
2,3041623
edited Jul 28 at 17:09
Daniel Buck
2,3041623
2,3041623
asked Jul 25 at 16:31
Andrew
871211
asked Jul 25 at 16:31
Andrew
871211
asked Jul 25 at 16:31
Andrew
871211
871211
3
It's not hard to deduce the full form of Dirichlet from this special case.
– Lord Shark the Unknown
Jul 25 at 16:32
2
For any $k$ there is a prime of the form $a^kn+b$.
– Wojowu
Jul 25 at 16:41
2
Correct. $$
– Wojowu
Jul 25 at 16:47
1
Thank you 🙂 you've dissolved my problem
– Andrew
Jul 25 at 16:58
2
Yes, it's hard to prove, @AndrewSlattery. Whether it implies the full Dirichlet theorem depends on what precisely one considers the full theorem. What Dirichlet proved was more than just that there are infinitely many primes in every arithmetic progression $an + b$ with $gcd(a,b) = 1$, he proved that the sum of the reciprocals of the primes in such a progression diverges (and even some more). That "each such progression contains at least one prime" implies "each such progression contains infinitely many primes" is easy, but getting to "the sum of the reciprocals diverges" isn't.
– Daniel Fischer♦
Jul 25 at 18:34
 |Â
show 5 more comments
3
It's not hard to deduce the full form of Dirichlet from this special case.
– Lord Shark the Unknown
Jul 25 at 16:32
2
For any $k$ there is a prime of the form $a^kn+b$.
– Wojowu
Jul 25 at 16:41
2
Correct. $$
– Wojowu
Jul 25 at 16:47
1
Thank you 🙂 you've dissolved my problem
– Andrew
Jul 25 at 16:58
2
Yes, it's hard to prove, @AndrewSlattery. Whether it implies the full Dirichlet theorem depends on what precisely one considers the full theorem. What Dirichlet proved was more than just that there are infinitely many primes in every arithmetic progression $an + b$ with $gcd(a,b) = 1$, he proved that the sum of the reciprocals of the primes in such a progression diverges (and even some more). That "each such progression contains at least one prime" implies "each such progression contains infinitely many primes" is easy, but getting to "the sum of the reciprocals diverges" isn't.
– Daniel Fischer♦
Jul 25 at 18:34
3
3
It's not hard to deduce the full form of Dirichlet from this special case.
– Lord Shark the Unknown
Jul 25 at 16:32
It's not hard to deduce the full form of Dirichlet from this special case.
– Lord Shark the Unknown
Jul 25 at 16:32
2
2
For any $k$ there is a prime of the form $a^kn+b$.
– Wojowu
Jul 25 at 16:41
For any $k$ there is a prime of the form $a^kn+b$.
– Wojowu
Jul 25 at 16:41
2
2
Correct. $$
– Wojowu
Jul 25 at 16:47
Correct. $$
– Wojowu
Jul 25 at 16:47
1
1
Thank you 🙂 you've dissolved my problem
– Andrew
Jul 25 at 16:58
Thank you 🙂 you've dissolved my problem
– Andrew
Jul 25 at 16:58
2
2
Yes, it's hard to prove, @AndrewSlattery. Whether it implies the full Dirichlet theorem depends on what precisely one considers the full theorem. What Dirichlet proved was more than just that there are infinitely many primes in every arithmetic progression $an + b$ with $gcd(a,b) = 1$, he proved that the sum of the reciprocals of the primes in such a progression diverges (and even some more). That "each such progression contains at least one prime" implies "each such progression contains infinitely many primes" is easy, but getting to "the sum of the reciprocals diverges" isn't.
– Daniel Fischer♦
Jul 25 at 18:34
Yes, it's hard to prove, @AndrewSlattery. Whether it implies the full Dirichlet theorem depends on what precisely one considers the full theorem. What Dirichlet proved was more than just that there are infinitely many primes in every arithmetic progression $an + b$ with $gcd(a,b) = 1$, he proved that the sum of the reciprocals of the primes in such a progression diverges (and even some more). That "each such progression contains at least one prime" implies "each such progression contains infinitely many primes" is easy, but getting to "the sum of the reciprocals diverges" isn't.
– Daniel Fischer♦
Jul 25 at 18:34
 |Â
show 5 more comments
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862586%2fproof-that-every-arithmetic-progression-which-might-contain-a-prime-does-so%23new-answer', 'question_page');
);
Post as a guest
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
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
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
3
It's not hard to deduce the full form of Dirichlet from this special case.
– Lord Shark the Unknown
Jul 25 at 16:32
2
For any $k$ there is a prime of the form $a^kn+b$.
– Wojowu
Jul 25 at 16:41
2
Correct. $$
– Wojowu
Jul 25 at 16:47
1
Thank you 🙂 you've dissolved my problem
– Andrew
Jul 25 at 16:58
2
Yes, it's hard to prove, @AndrewSlattery. Whether it implies the full Dirichlet theorem depends on what precisely one considers the full theorem. What Dirichlet proved was more than just that there are infinitely many primes in every arithmetic progression $an + b$ with $gcd(a,b) = 1$, he proved that the sum of the reciprocals of the primes in such a progression diverges (and even some more). That "each such progression contains at least one prime" implies "each such progression contains infinitely many primes" is easy, but getting to "the sum of the reciprocals diverges" isn't.
– Daniel Fischer♦
Jul 25 at 18:34