Dirichlet's Theorem

By Niranjan Srinivas on Friday, November 09, 2001 - 02:34 pm:

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.

By Dimitri Cleanis on Friday, November 09, 2001 - 04:29 pm:

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

By Kerwin Hui on Friday, November 09, 2001 - 04:39 pm:

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

By Yatir Halevi on Friday, November 09, 2001 - 06:43 pm:

What about the proof that there is no polynominal expression for

π (x)

? How is that proven?
Also, that there is not a polynominal that consists of only primes; how is that proven?

By Kerwin Hui on Friday, November 09, 2001 - 07:16 pm:

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

By Kerwin Hui on Friday, November 09, 2001 - 07:37 pm:

Yatir,

The prime number theorem states that $π (x) ~ x / (\log x)$ as $x$ tends to $\infty$ . If there is a polynomial for $π (x)$ , let $n$ be the degree and we see that $P (x) / x^{n}$ 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 $π (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_{0} \to N$ . Now $P (0)$ is a prime, say $p$ . Consider $P (p)$ , $P (2 p)$ , ... 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