weak form of Dirichlet's theorem

[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.

[morphism]

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?

[CRGreathouse]

Interesting question.

[morphism]

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

[CRGreathouse]

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

See what? *Whistles innocently*

[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.

[morphism]

Yup, that's it.

[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.

[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.

[gel]

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...

[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?

[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.

[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.