Assignment 4 (pdf)

Make sure to write complete proofs. Try to avoid skipping steps. Write clear sentences.

1. True or False: If \(p,q\) are prime, then \(\gcd(p,q)\) is equal to either \(p\) or \(q\).
2. Show that if \(p > 3\) is a prime number then the remainder of diving \(p\) by \(6\) is either \(1\) or \(5\). Provide examples to show that both remainders are indeed possible.
3. Suppose that \(M\) is a number that is relatively prime to \(6\) and is also a perfect square (i.e. it is \(M=n^2\) of some integer \(n\)). Show that \(M\) divided by \(6\) leaves remainder \(1\).
4. Suppose that \(M\) is a perfect square. Show that its remainder when divided by \(4\) must be \(0\) or \(1\).
5. Use the previous problem to show that the number \(1403\) cannot possibly be the sum of two perfect squares.