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 r₀(= a), r₁, r₂, . . . , r_n. That is, your calculation looks like:

b = q₁a + r₁

a = q₂r₁ + r₂

r₁ = q₃r₂ + r₃

r_n-2 = q_nr_n-1 + r_n

r_n-1 = q_n+1r_n

where r_n = gcd(a, b). Show that there is a constant C > 0, that does not depend on a nor b, such that n ≤ C · log₂(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 (x₁, y₁), . . . ,(x_m, y_m) 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) = (x_i, y_i) + t(3, 5) + s(5, 3).