Math Homework #3 Solution



Do problems 2; 3; 7; 8; 9; 11; 12; 20; 24 from Chapter 3 (Section 3:13)

Do computer problems 1; 2; 3; 4; 6 from Chapter 3 (Section 3:14)

Hint for the computer exercises: Write a function (or something) that does the extended Euclidean algorithm, i.e. that takes any integers a and b and gives you gcd(a; b) and integers x and y such that ax + by = gcd(a; b). That should be the only complicated thing you need to write. All the problems can be done pretty easily using this function. I gave fairly thorough details about how to do this in class this past week.

Hint #2: Remember that most languages have a built-in “modulo” operator. In C, C++, Java, Python, and many many others, it’s %. Be cautious if you happen to use this with negative numbers, because in some languages, it doesn’t give the mathematically correct result. If you happen to be using Python, you can get the quotient and remainder in a single operation using the built-in divmod function:

q; r = divmod(a; b)

The result of this will be such that a = b q + r, just like the division algorithm.