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
x^{2} + y^{2} can not be a perfect square.

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

x^{2}
+ y^{2} = (2k + 1)^{2} + (2m + 1)^{2} = 4(k^{2}
+ k + m^{2} + 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 x^{2}
+ y^{2} 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 x^{2 } and y ^{2} of the form 3k + 1.
Thus x^{2} + y^{2} is of the form 3k +
2 and hence can’t be a perfect square.