# Weak form of Dirichlet's theorem

1. Aug 28, 2008

### mikepol

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.

2. Aug 28, 2008

### morphism

Is that really a weaker statement?

3. Aug 28, 2008

### CRGreathouse

Interesting question.

Last edited: Aug 28, 2008
4. Aug 28, 2008

### morphism

Well I was hoping the OP would see that him/herself!

5. Aug 28, 2008

### CRGreathouse

See what? *Whistles innocently*

6. Aug 28, 2008

### mikepol

Hi,

It might be that the above statment 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.

7. Aug 28, 2008

### morphism

Yup, that's it.

8. Aug 28, 2008

### gel

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.

9. Aug 28, 2008

### morphism

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. Aug 29, 2008

### gel

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. Aug 29, 2008

### gel

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. Aug 30, 2008

### morphism

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. Sep 2, 2008

### mikepol

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.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?