COT 3100H Spring 2008 Homework #7 Solutions
Assigned: 3/4/08 (Tuesday)
Due: 3/6/08 (Thursday)
1) Find GCD(729, 321) using Euclid's Algorithm.
729 = 2 x 321 + 87
321 = 3 x 87 + 60
87 = 1 x 60 + 27
60 = 2 x 27 + 6
27 = 4 x 6 + 3
6 = 2 x 3
GCD(729, 321) = 3
2) Find all integer solutions for x and y to the equation 729x + 321y = gcd(729, 321).
Running the Extended Euclidean Algorithm, we find:
27 – 4 x 6 = 3
27 – 4 x (60 – 2 x 27) = 3
27 – 4 x 60 + 8 x 27 = 3
9 x 27 – 4 x 60 = 3
9 x (87 – 60) – 4 x 60 = 3
9 x 87 – 13 x 60 = 3
9 x 87 – 13 x (321 – 3 x 87) = 3
9 x 87 – 13 x 321 + 39 x 87 = 3
48 x 87 – 13 x 321 = 3
48 x (729 – 2 x 321) – 13 x 321 = 3
48 x 729 – 96 x 321 – 13 x 321 = 3
48 x 729 – 109 x 321 = 3
One solution is x = 48, y = -109.
To get the others, divide 729x = 321y by 3 (the gcd) to get 243x = 107y. Settting x = 107 and y = 243 is the smallest positive solution to this equation. It follows that all solutions are the following:
x = 48 + 107n, y = -109 – 243n, where n is an integer.
3)Find all integer solutions for x and y to the equation 729x + 321y = 36.
Starting with the last line from the previous question, we have
48 x 729 – 109 x 321 = 3
(12x48) x 729 – (12x109) x 321 = 12 x 3
576 x 729 – 1308 x 321 = 36
So one way to express all solutions to this equation is
x = 576 + 107n, y = -1308 – 243n, where n is an integer.
We can subtract out 5 multiples of 107 to yield an equivalent solution:
x = 41 + 107n, y = -93 – 243n, where n is an integer.
4) What is the least common multiple of 729 and 321?
LCM(729, 321) =
5) Prove that is irrational.
Assume to the contrary that it's rational. Then there exist integers a and b with gcd(a,b) = 1 such that . Thus,
, it follows that since 3 is prime, that 3 | a. Let a = 3x, where x is an integer.
, similarly, it follows that 3 | b. Thus, gcd(a,b) ≥ 3, contradicting the assumption.
It follows that our assumption was incorrect and is irrational.
6) Determine the number of positive integer divisors of 2534108.
2534108 = 25342858 = 2133458. Since 2, 3 and 5 are prime, the number of divisors is (13 + 1)(4 + 1)(8 + 1) = 630.
7) Determine the sum of the divisors in question #6.
The sum of these divisors is