1. Prove that if an integer n is the sum of two squares (n = a2 + b2 for a, b ∈ ℤ) then n = 4q or n = 4q + 1 or n = 4q + 2 for some q ∈ ℤ. Deduce that 1234567 cannot be written as the sum of two squares.
2. Let a be an integer. Prove that a2 is divisible by 5 if and only if a is divisible by 5.
3. Use the result of Question 2 to prove that there does not exist a rational number whose square is 5.
4. Prove that there is no rational number whose square is 98.
5. Prove that every infinite decimal representing a rational number is recurring (the converse of Theorem 13.3.4) and furthermore that if the fraction in lowest terms representing a fraction is a/b then the number of recurring digits in its decimal representation is less than b.
[See Exercise 15.6.]
6. Use the Euclidean algorithm to find the greatest common divisors of (i) 165 and 252, (ii) 4284 and 3480.
7. Let un be the nth Fibonacci number (for the definition see Definition 5.4.2). Prove that the Euclidean algorithm takes precisely n steps to prove that gcd(un+1,un) = 1.
8. Suppose that a and b are two positive integers with a ≥ b. Let a0, a1, …, an be the sequence of integers generated by the Euclidean algorithm so that an = gcd(a, b).
Review the options below to login to check your access.
Log in with your Cambridge Aspire website account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.