## Math 310: Problem set 7

Instructions: This problem set is due Friday, February 24, 2006.
1. (2 points) Mimic Euclid's proof that there are infinitely many primes to show that there are infinitely many primes of congruent to 3 modulo 4. (Hint: Assume that there are only finitely many primes of congruent to 3 modulo 4. List them: p1, p2, ..., pt. Let P = p1p2...pt be the product. Show that P is congruent to either 1 or 3 mod 4. Now define an integer N as follows. If P is congruent to 1 mod 4, let N = P+2. If P is congruent to 3 mod 4, let N = P+4. Show that, either way, N is congruent to 3 mod 4. Show that none of the primes p1, p2, ..., pt divides N. Using the fact (that we already know) that N is either prime or a product of primes, conclude that N has some prime factor q congruent to 3 mod 4, and hence that q is not among the primes p1, p2, ..., pt. Conclude that there must be infinitely many primes congruent to 3 mod 4.)
2. Let a1=3 , a2=5 , and define an+1=3an-an-1 for n > 1 . The goal of this problem is to prove that ak > 2k for each integer k > 0.
• (a) (2 points) First induction to prove that ak+1 > ak for each integer k > 0.
• (b) (2 points) Use (a) and induction to prove that ak+1 > 2ak for each integer k > 1.
• (c) (2 points) Use (b) and induction to prove that ak > 2k for each integer k > 0.