Weak form of Dirichlet's theorem

  • Context: Graduate 
  • Thread starter Thread starter mikepol
  • Start date Start date
  • Tags Tags
    Form Theorem Weak
Click For Summary

Discussion Overview

The discussion revolves around the weaker form of Dirichlet's theorem, specifically whether every arithmetic progression of the form a + kb, where gcd(a, b) = 1, contains at least one prime. Participants explore the implications of this statement and its relationship to the original theorem.

Discussion Character

  • Exploratory
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant questions whether the weaker statement about containing at least one prime is indeed weaker than Dirichlet's theorem.
  • Another participant proposes a reasoning process suggesting that if there is at least one prime in the progression, it could imply there are infinitely many primes, thus linking the two statements.
  • Several participants discuss specific forms of primes, such as those of the form 3n+2, 4n+3, and 5n+4, and inquire about proofs for their infinitude.
  • A participant mentions a proof involving quadratic reciprocity for primes of the form 5n+4, while another expresses uncertainty about whether the proof should avoid this concept.
  • One participant reflects on their initial confusion regarding the context of the problem and their limited background in number theory, indicating a desire to understand the topic further.

Areas of Agreement / Disagreement

Participants exhibit a mix of agreement and disagreement regarding the implications of the weaker statement and its relationship to Dirichlet's theorem. There is no consensus on whether the weaker statement is indeed weaker or on the best approach to proving the infinitude of primes in specific forms.

Contextual Notes

Some participants express uncertainty about the definitions and implications of certain mathematical concepts, such as quadratic reciprocity, and the complexity of proofs related to the infinitude of primes in various forms. The discussion reflects varying levels of familiarity with number theory.

Who May Find This Useful

This discussion may be of interest to those studying number theory, particularly in relation to prime numbers and their distributions in arithmetic progressions, as well as individuals exploring foundational concepts in mathematics.

mikepol
Messages
19
Reaction score
0
Hi,

Dirichlet's theorem states that any arithmetic progression a+kb, where k is a natural number and a and b are relatively prime, contains infinite number of primes.

I'm wondering if there is an easy proof of a much weaker statement: every arithmetic progression a+kb where gcd(a,b)=1 contains at least one prime.

I can't come up with a satisfactory proof, but I have a feeling it shouldn't be too hard. Does anyone have any ideas?

Thanks.
 
Physics news on Phys.org
mikepol said:
I'm wondering if there is an easy proof of a much weaker statement: every arithmetic progression a+kb where gcd(a,b)=1 contains at least one prime.
Is that really a weaker statement?
 
Interesting question.
 
Last edited:
Well I was hoping the OP would see that him/herself!
 
morphism said:
Well I was hoping the OP would see that him/herself!

See what? *Whistles innocently*
 
Hi,

It might be that the above statement is not any weaker after all. Please correct me if I'm wrong:

Suppose we proved that arithmetic progression a+bk, k=1,2,... contains at least one prime. Suppose that prime p is formed when k=q, so p = a+bq. Then form another progression a+(k+q)b, where k=1,2,...

We have: a+(k+q)b = a + qb + kb = p + kb
But p is prime and p>a and p>b, so gcd(p,b)=1. And also for every k, p+kb>p. Then we know that arithmetic progression p+kb contains at least one prime which is greater than p. Continuing in this way we determine that there must be infinite number of primes in the original progression a+bk.

So then knowing that there is at least one prime implies that there are infinite number of primes. The other way works too, so this is an 'iff' implication.
 
Yup, that's it.
 
to go back to the original question, can you show that there are infinitely many primes of the form 3n+2, 4n + 3, 4n + 1, 4n + 3, 6n + 5 ? they're all quite easy. There's also a relatively simple proof that an + 1 contains infinitely many primes for any given a.
For the general case, I only know the proof using Dirichlet series.
 
In the spirit of gel's post, can you prove that there are infinitely many primes of the form 5n+4? Apparently an elementary proof of this does exist, but I've never been able to find it.
 
  • #10
morphism said:
In the spirit of gel's post, can you prove that there are infinitely many primes of the form 5n+4? Apparently an elementary proof of this does exist, but I've never been able to find it.

Interesting - I thought of a quick proof myself, but it involves quadratic reciprocity: For odd primes p,q, at least one of which is 1 mod 4, then p is a quadratic residue mod q iff q is a quadratic residue mod p.
The only quadratic residues (mod 5) are 1 and 4. So, taking q=5 says that an odd prime p is of the form 5n+4 if and only if 5 is a quadratic residue mod p and p != 1 mod 5.

Hopefully you can take it from there...
 
  • #11
The result is that every prime factor of 100 n^2 + 40 n - 1 is equal to 1 or 4 (mod 5), and they can't all be 1. Wonder if you can show this directly without using quadratic reciprocity?
 
  • #12
I think it was meant to be done without using quadratic reciprocity. Unfortunately I can't be sure -- I've lost contact with the person who gave me this problem.
 
  • #13
Hi,

First of all, sorry if my original post confused anyone, I should have thought more before I wrote. The problem I was trying to solve wasn't given in context of Dirichlet's theorem, so I didn't put much thought after generalizing it.

I know that proving that there are infinite number of primes of the form 3n+2, 4n + 3, 6n + 5 is fairly easy and is similar to showing that there are infinite number of primes. However, I'm pretty new to number theory (actually very new), and I don't know what quadratic reciprocity is, but from two books that I started reading, the proof for 4n+1 is postponed until much later chapters.

Anyways, my reason for studying number theory was to understand some cryptography and a couple of hashing functions, so I'm not going to dwell into this subject much more than basic congruences. It does sound interesting however and maybe I'll return to reading more about it when I get some free time.

Everyone who replied, thank you very much, it has been very helpful.
 

Similar threads

Prove that there exists a prime with at least ## n ## of its digits.
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Uniqueness of reduced row echelon form (proof verification)
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad ##(A/\mathfrak{a})_{\mathfrak{p}/\mathfrak{a}}## and its isomorphism?
  • · Replies 31 ·
2
Replies
31
Views
3K
Graduate Primes and arithmetic progressions.
  • · Replies 2 ·
Replies
2
Views
3K
Graduate Question about Dirichlet's theorem on arithmetic progressions
  • · Replies 2 ·
Replies
2
Views
3K
Graduate Proving (a weaker form of) Bertrand's postulate
  • · Replies 7 ·
Replies
7
Views
5K
Graduate Dirichlet's Approximation Theorem not working for n=8 and α= pi?
  • · Replies 2 ·
Replies
2
Views
2K
High School Extending the Fundamental Theorem of Arithmetic to the rationals
  • · Replies 35 ·
2
Replies
35
Views
5K
Graduate Question about proof of Great Picard Theorem
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Need clarification on a theorem about field extensions/isomorphisms
  • · Replies 14 ·
Replies
14
Views
3K