Assignment 1-
1. (a) Using the Euclidean algorithm, determine gcd(248399, 282041).
(b) A plane has capacity 15, 921 pounds. A company wants to ship two types of motorcycles, one 957 pounds and one 609 pounds. Determine the ways to make up a full load with these two types of motorcycles.
2. (a) Suppose d, a, b are positive integers. Show that if d|a and d|b, then d|gcd(a, b).
(b) Given positive integers a, b, c, we define gcd(a, b, c) to be the (necessarily unique) positive integer d such that
- d|a, d|b, d|c
- If d' is a positive integer such that d'|a, d'|b, and d'|c, then d' ≤ d.
Using part (a), or otherwise, prove that gcd(a, b, c) = gcd(gcd(a, b), c). Use this to find gcd(2583409, 12819163, 56811127).
3. Suppose that you compute gcd(a, b) using the Euclidean algorithm, where b > a > 0 are integers, and you get remainders r0(= a), r1, r2, . . . , rn. That is, your calculation looks like:
b = q1a + r1
a = q2r1 + r2
r1 = q3r2 + r3
rn-2 = qnrn-1 + rn
rn-1 = qn+1rn
where rn = gcd(a, b). Show that there is a constant C > 0, that does not depend on a nor b, such that n ≤ C · log2(b).
4. Determine all triples of integers (x, y, z) such that
77x + 143y + 91z = 89.
5. Let b > a ≥ 2 be integers, with gcd(a, b) = 1.
(a) Show that there are no nonnegative integers x, y such that
ax + by = ab - b - a.
(b) Show that if N is an integer with N > ab - b, then there exists a nonnegative integer solution to the equation
ax + by = N.
(c) It is in fact true that for any integer N > ab - a - b, there exists a nonnegative integer solution to the equation
ax + by = N.
Show this for the example a = 9, b = 13.
6. In this problem, we investigate linear diophantine inequalities. Prove that there is a finite set of integer points (x1, y1), . . . ,(xm, ym) such that for any integer solution (x, y) to the system of inequalities
3y ≤ 5x
3x ≤ 5y
there is a unique index i and unique nonnegative integers t, s such that
(x, y) = (xi, yi) + t(3, 5) + s(5, 3).