[SOLVED] Homework 1 cs 417

Problem 1. Let a, b, d ∈ Z. Suppose that d | a and d | b.
(1) Show that d | a − b.
(2) Let m, n ∈ Z. Show that d | ma + nb.
Problem 2. Let a1, a2, . . . , an be integers. The greatest common divisor of a1, a2, . . . , an,
denoted by gcd(a1, a2, . . . , an), is the largest positive integer d such that d | ai
for each
1 ≤ i ≤ n. It is known that
gcd(a1, a2, . . . , an) = gcd(an, gcd(a1, . . . , an−1)).
Given a list of integers, say alist.
(1) Write a recursive function named recursive gcd(alist) that takes alist as an input
and return the greatest common divisor of all elements in alist.
(2) Write a non-recursive function, named non recursive gcd(alist) to achieve the same
goal.
For this problem, you can use any functions that we wrote to compute gcd(a, b) for two
given integers (this is the base case).