MATH 319 Solutions Assignment 4

page 58 #32.

Show that {2,4,6,…,2m} is a complete residue system (mod m) if m is odd.

Proof: Since m is odd, (2,m) = 1. By Theorem 2.6 (proved in class) we know that since {1,2,3,…,m} is a CRS (mod m ) then so is {2×1, 2×2, 2×3,…,2×m}.

#33. Show that {1², 2², …,m² }is not a CRS for m > 2.

Proof: If m > 2 then m-1 is not equal to 1 but and hence there are fewer than m incongruent numbers in the set {1², 2², …,m²} is not a CRS mod m.

#38. Prove there are infinitely many primes of the form 4k + 1.

Proof: Assume there are only finitely many primes of the form 4k + 1 and let be the set of all of them. Let be the product of all the primes of the form 4k + 1. Then let . Is Q a prime? No because it is of the form 4k + 1 and is greater than any of the complete list of primes of that form. Thus Q is composite. Does it have any prime factors of the form 4k + 3? By Lemma 2.14 if q is a prime factor of Q then q divides , and hence . But no number larger than 1 divides 1. So no such q exists. Thus all prime factors of Q must be of the form 4k + 1. (Clearly 2 does not divide Q). Let p_i be one such prime factor of Q. and so p_i must divide their difference which is 1. Again this is not true.