Math 310: Problem set 7
Instructions: This problem set is due
Friday, February 24, 2006.
- (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.)
- 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.