From: Alexander Bogomolny <alexb@cut-the-knot.com>
Subject: Re: Number Theory question
Date: Tue, 19 Dec 2000 22:02:33 EST
Newsgroups: sci.math
Summary: [missing]

lena wrote:
> 
> Show that there are infinitely many primes of the type 4n+3, and of the type
> 6n+5.
> 
> This is an easy consequence of Dirchlet's theorem that says that are
> infinitely many primes of the type an + b, with a and b relatively prime.
> 
> However, the obove question should be a lot easier to prove without using
> such a powerful theorem.  I can't see a proof yet.

Theorem 98 (p 173) from "Introduction to Number Theory" by T. Nagell
(Chelsea Publishing, 1981, distributed by AMS) states 

"If n is a natural number, there are infinitely many primes 
which are = -1 (mod n)."

The proof does not use Dirichlet's theorem but takes 4 Lemmas over the 
space of 3 pages. 

Alexander Bogomolny,
http://www.cut-the-knot.com