number theory III In class we proved that there are an infin

number theory
III. In class we proved that there are an infinite number of primes 1 mod 4 as follows: Suppose there are only a finite number of primes 1 mod 4. Let p1, p2,..., pn be the complete list. Let A=(2p1p2...pn)2+1. Factor A into primes: A=q1q2...qm. Then for each q, (2p1p2...pn)2+10 mod q, so (2p1p2...pn)2-1 mod q. But (2p1p2...pn)20 mod p for each p, so none of the q\'s are equal to any of the p\'s. Because (2p1p2...pn)2-1 mod q, -1 must be a quadratic residue mod q for each q. Therefore (-1/q)=1, so (-1)q-1/21 mod q, and (-1)q-1/2=1. That means q-1/2 is even, so q-1 is divisible by 4. That is q-1 0 mod 4, so q 1 mod 4, but q is not on our\"complete\" list of primes 1 mod 4. This contradiction establishes the theorem.
Modify the above proof to show that there are infinite number of primes 7 mod 8. The main change you must make is your definition of A. Also, instead of proving that -1 is a quadratic residue mod q for each q, you will have to show that something else is a quadratic residue. And you will not be able to prove that all q\'s are 7 mod 9, but you can prove that at least one q is 7 mod 8.

Solution

2 is a quadratic residue modp if and only if p is congruent to +-1 mod8.

Suppose that there are only finitely many primes p_1, . . . , p_n congruent to 7 (mod 8). Consider the number k = (4p1 p2 · · · pn) ^2 2. So (4p1 p2 · · · pn) ^2 = 2 mod k. (4p1 p2 · · · pn) ^2 = 2 mod (every odd prime divisor of k). The number 2 is a quadratic residue of each odd prime divisor of k, each odd prime divisor of k is congruent to ±1 (mod 8).

We claim that it is not possible for all odd prime divisors of k to be congruent to 1 (mod 8). To see why, we note that the product of numbers congruent to 1 (mod 8) is another number congruent to 1 (mod 8). However k/2 = 8(p1 p2 · · · pn)^ 2 1 1 (mod 8). Hence k must have an odd prime factor q congruent to 1 (mod 8). The number q is relatively prime to each pi and hence not equal to any pi . This contradicts the assumption that there were only finitely many primes congruent to 1 (mod 8). Thus there are infinitely many primes in the residue class 7 (mod 8).