Hint 1: Use both parts of problem 4.2.8 and the Euclidean Algorithm.