From: Robin Chapman Subject: Re: Primes of the form 8n+5 Date: Fri, 10 Dec 1999 12:27:22 GMT Newsgroups: sci.math Keywords: infinitude of primes in the congruence classes mod 8 In article , Amanda Pack wrote: > how should i go about proving the infinitude of primes of the above form? > i am currently studying quadratic reciprocity. > > would the case for primes of the form 8n+7 be similar. I'm sure both of these are in Nagell's book on number theory, but I don't have my copy to hand. Suppose we have an integer N which is (a) the sum of two mutually coprime squares and (b) congruent to 5 (mod 8). Then by (a) no prime factor of N is congruent to 3 mod 4, and as by (b) N is odd then each prime factor of N is congruent to 1 mod 4. Thus each prime factor of N is congruent to 1 or 5 modulo 8. But they can't all be congruent to 1 modulo 8 by (b). So N has a prime factor q congruent to 5 (mod 8). Let p_1, ... , p_k be a bunch of odd primes. Then (2 p_1 p_2 ... p_k)^2 + 1 satisfies (a) and (b). It has a prime factor q = 5 (mod 8) and q can't equal any of the p_j. One can modify this for the cases of primes congruent to 3 or congruent to 7 (mod 8). There are also modulo 12 versions. -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "`Well, I'd already done a PhD in X-Files Theory at UCLA, ...'" Greg Egan, _Teranesia_ Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: erick@sfu.ca (Erick Bryce Wong) Subject: Re: Primes of the form 8n+5 Date: 10 Dec 1999 07:33:10 GMT Newsgroups: sci.math Amanda Pack wrote: >how should i go about proving the infinitude of primes of the above form? >i am currently studying quadratic reciprocity. > >would the case for primes of the form 8n+7 be similar. In both cases, you typically start with a finite set of such primes, multiply them together to form N, then show that some polynomial in N is divisible by at least one prime of the desired form, which cannot be in the original set. For 8n+5, you might try 4N^2+1. Can any prime factors of this number divide into N? Can any prime factors be of the form 8k+7? What else can you say about the prime factors of 4N^2+1? Can /all/ of them be of the form 8k+1? (Note that N, being the product of odd primes, is necessarily odd.) For 8n+7, try to find another function of N that lets you argue similarly. (Hint: you should be able to use N^2 - c, provided you pick c carefully.) -- Erick ============================================================================== From: pete@bignode.southern.co.nz (Pete Moore) Subject: Re: Primes of the form 8n+5 Date: 10 Dec 99 20:32:48 +1300 Newsgroups: sci.math Amanda Pack (ap512@columbia.edu) wrote: >how should i go about proving the infinitude of primes of the above form? >i am currently studying quadratic reciprocity. If p1,...,pn are primes of this form, consider N=(2*p1*...*pn)^2+1. Let p|N. What does your knowledge of quadratic residues tell you about p? >would the case for primes of the form 8n+7 be similar. Very similar. In this case consider N=(p1*p2*...*pn)^2-2. -- +---------------- pete@bignode.southern.co.nz ----------------+ The effort to understand the universe is one of the very few things that lifts human life above the level of farce, and gives it some of the grace of tragedy - Steven Weinberg