## 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: p
_{1}, p_{2}, ..., p_{t}.
Let P = p_{1}p_{2}...p_{t} 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 p_{1}, p_{2}, ..., p_{t}
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
p_{1}, p_{2}, ..., p_{t}. Conclude
that there must be infinitely many primes congruent to 3 mod 4.)
- Let a
_{1}=3 , a_{2}=5 , and define
a_{n+1}=3a_{n}-a_{n-1} for n > 1 .
The goal of this problem is to prove that
a_{k} > 2^{k} for each integer k > 0.
- (a) (2 points) First induction to prove that
a
_{k+1} > a_{k} for each integer k > 0.
- (b) (2 points) Use (a) and induction to prove that
a
_{k+1} > 2a_{k} for each integer k > 1.
- (c) (2 points) Use (b) and induction to prove that
a
_{k} > 2^{k} for each integer k > 0.