THEORY OF NUMBERS, Math 115 A Homework 3 Due Wednesday October 16

1. Use the Euclidean and extended Euclidean algorithms to find the gcd of the following pairs of numbers and to represent them as a linear combination of the input data:

a) (45, 75), b) (666, 1414), c) (102, 222) d) (20785, 44350).

2. Let m, n be positive integers and let a be an integer greater than 1. Show that (a^{m} − 1, a^{n} − 1) = a^{(m,n)} − 1.

3. Show that every positive integer can be written as the product of possibly a square and a square-free integer. Recall a square free integer is an integer that is not divisible by any perfect square other than 1.

4. Let N(a+b\sqrt{−5}) = a^{2}+5b^{2}. Show that if m = a+b\sqrt{−5} and n = c+d\sqrt{−5}, where a, b, c, d are integer, then N(nm) = N(n)N(m).

5. Show that the numbers 1 + \sqrt{−5} and 1 − \sqrt{−5} are prime numbers inside the set of special numbers a + b\sqrt{−5}. Hint: use the previous exercise.

6. Find the least common multiple of each of the following pairs of integers:

a)7,11 b) 101,303 c) 1331, 5005 d) 5040, 7700.

7. Show that \sqrt{2} + \sqrt{3} is irrational.

8. Prove that there are infinitely many primes of the form 6k + 5, where k is a positive integer.