Can anyone give me the proof for Dirichlet's theorem ?
It states that the arithmetic progression a,a+d,a+2d,a+3d,...
conatins infinitely many primes if gcd(a,d) = 1.

I'm aware that the proof you're after is not very easy. Something which i know is quite feasible, though, is proving that the progression contains k consecutive terms (k> 0) which are composite. Don't forget that there is no arithmetic progression (a, a+d, a+2d...) that consists solely of prime numbers. That is also relatively straightforward to proof.

Hope this is of some help.
Dimitri

I don't think there is any simple proof of Dirichlet's. The easiest (non-trivial) case is when a=1 or -1, but it still requires a fair amount of work. You will need to know more algebraic number theory before proving the general theorem.

Kerwin

Just found a proof of Dirichlet using analytic number theory here . It will be quite a tough one if you haven't done any analytic number theory before.

Kerwin

The prime number theorem states that p(x) ~ x/(logx) as x tends to ¥. If there is a polynomial for p(x), let n be the degree and we see that P(x)/xⁿ tends to a non-zero limit as x tends to infinity, which gives a contradiction. Alternatively, any polynomial that is not linear must eventually be increasing too fast (i.e. the value at m and m+1 differ by more than 1), and clearly p(x) is not of degree 1.

We have done the second question some time ago on the board. Let P(n) be your polynomial N₀®N. Now P(0) is a prime, say p. Consider P(p), P(2p), ... all these must be prime and must be a multiple of p, so must be p. Hence P(x)-p has infinitely many zeros. Contradiction unless P(x)=p for all x.

Kerwin