MATH 319 Solutions Assignment 2

Page 29 #9

Prove that any prime of the form 3k + 1 is of the form 6k +1.

Proof: The only even prime is 2 and it is not of the form 3k + 1. Thus any prime of the form 3k + 1 is odd.  This means 3k must be even which implies that k must be even. Let k = 2m.  Then a prime of the form 3k + 1 is of the form 3(2m) = 1 = 6m+1.

#10

Prove that any positive integer of the form 4k + 3 must have a prime factor of the same form.

Proof: Any number of the form 4k + 3 must be odd so it can not have any factors of the form 4k or 4k + 2 which are even. Thus all the factors of a 4k + 3 must be of the forms 4k + 1 and 4k + 3.  Suppose that they were all of the form 4k + 1. Multiplying two such yields (4k+1)(4m+1) = 4(4km+k+m) +1, another 4k+1. Thus the product of any number of factors of the form 4k + 1 must be another 4k + 1. Thus a 4k + 3 must have a prime factor of the form 4k + 3.

Prove that any positive integer of the form 6k + 5 must have a prime factor of the same form.

Proof: Since a number of the form 6k + 5 is odd and not divisible by 3 it can’t have any factors of the form 6k, 6k + 2, 6k + 3, or 6k + 4.  Thus all its prime factors are of the form 6k + 1 or 6k + 5.  Multiplying any number of 6k + 1’s yields another 6k + 1. Thus it must have a prime factor of the form 6k + 5.

#11. If x and y are odd, prove that x2 + y2 can not be a perfect square.

Proof: If x and y are odd then x2 + y2  must be even. An even perfect square must be divisible by 4. (Why?)  Let x = 2k + 1 and y = 2m + 1. Then

x2 + y2 = (2k + 1)2 + (2m + 1)2 = 4(k2 + k + m2 + m) +2 which is not a multiple of 4 and hence not a perfect square.

#12.  If x and y are prime to 3, prove that x2 + y2 can not be a perfect square.

Proof:  By problem 23 from the last assignment a perfect square can be of the form 3k or 3k + 1 but never of the form 3k + 2.  Since (x,3) = 1 and (y,3) = 1 we have that x and y are of the form 3k + 1 or 3k + 2. In either case we have x2  and y 2 of the form 3k + 1. Thus x2 + y2 is of the form 3k + 2 and hence can’t be a perfect square.