Assignment, Week 3

Solutions

Reading in Silverman

Ch 6, Linear Equations and the Greatest Common Divisor
Ch 7, Factorization and the Fundamental Theorem of Arithmetic

Problems

A Problems

First edition: 5.2, 6.1, 6.2, 7.1, 7.2
Second edition: 5.3, 6.1, 6.2, 7.1, 7.2

B Problems

1. First edition: A5.1, A5.2, A6.1, A7.1. (See page 248-249).
   Second edition: 5.4, 5.5, 6.3, 7.5 (same as in first edition with different numbers).
   
   
2. Write a program to factor an integer into primes.
   
   Note. Programming problems are strictly optional but highly recommended. You may use any language you like. Please include some explanation of how your program works, e.g., as the form of program comments. You don't need to do every programming problem, but you will learn a lot from doing a few.
   
   
3. Is it feasible to factor a 1000 digit integer into primes? Explain.
   
   
4. Write a program to compute gcd's. Consider recursion.
   
   
5. Write a program to solve the linear Diophantine equation
   
        ax + by = c.
   
   
6. Is there unique factorization for the set of numbers of the form
   
            a + b*sqrt(-5) ?