Homework 2

Due Date: Friday, February 12

Instructions: Feel free to work together with other students in the class, though you must turn in your own copy of the solutions, and you must acknowledge anyone that you worked with. You can turn in your homework assignment by e-mailing me all of your associated files.

Note: The book doesn't actually prove much about greatest common divisors. For the purposes of this assignment, you should feel free to use the following facts:

• \(\mathrm{gcd}(a,b) = \mathrm{gcd}(a,b+na)\) for any integers \(a\), \(b\), and \(n\).
• If \(a\) and \(b\) are relatively prime then \(\mathrm{gcd}(a,bc) = \mathrm{gcd}(a,c)\) for any integer \(c\).

1. 1. Prove that \(\mathrm{gcd}(2^m - 1,2^n - 1) = 2^{\mathrm{gcd}(m,n)}-1\) for all positive integers \(m\) and \(n\).
   2. Use part (a) to provide an alternate proof of Proposition 1.18.
2. The Fibonacci sequence \(F_1,F_2,F_3,\ldots\) is defined by \(F_1 = 1\), \(F_2 = 1\), and \[ F_n \,=\, F_{n-1} + F_{n-2} \] for all \(n\geq 3\).
   1. Prove that \(F_{n-1}\) and \(F_n\) are relatively prime for all \(n \geq 2\).
   2. Prove that \(F_{m+n} = F_m F_{n+1} + F_{m-1} F_n\) for all \(m\geq 2\) and \(n\geq 1\).
   3. Prove that \(\mathrm{gcd}(F_m,F_n) = F_{\mathrm{gcd}(m,n)}\) for all \(m,n\geq 1\).
3. 1. Write a program that uses the Sieve of Eratosthenes to compute a list of all the primes less than 10,000. According to your program, how many primes are there less than 10,000?
   2. Write a program that uses trial division to find the prime factorization of a given number, using the list of primes you generated in part (a) for division. Use your program to find the prime factorization of 166433156800722414483107.
   3. Write a program that uses the Euclidean algorithm to find the greatest common divisor of two given positive integers. Use your program to find the greatest common divisor of 348153868589018633619876937115107 and 417313194961807259870190713481689.