# MACM 101 Lecture Notes - Lecture 12: Euclidean Algorithm, Mathematical Induction

18 views3 pages

13 Aug 2016

School

Department

Course

Professor

Cameron has a lot of quarters and dimes with which to make change. How many different ways can he make change for

(a) $1.39

(b) $1.45

Solution

(a) since 5 doesn't divide 139, its not possible for Cameron to make change for $1.39. (5|10 and 5|25 => 5|(10x + 25y)

(b)

First, try finding a single solution. Maybe use the most quarters: 5 quarters, 2 dimes. Now, 2 quarters = 5

dimes, so we can obtain 2 other solutions by swapping dimes for quarters.

Hence, 3 solutions are possible

Definition

For a, b, d integers, if d|a and d|b then d is a common divisor.

And if d satisfies:

whenever c|a and c|b then c|d

Then d is a greatest common divisor

If a, b are small, it is a fairly quick to find gcd(a,b) by trial and error/factor terms

But what if a, b is large

Problem: find gcd(481,1053)

The Euclidean Algorithm

Let a, b be intergers, a =/= 0. The gcd(a,b) equals the last nonzero remainder, rn, in the list of equations

obtained from the Division Algorithm

Lecture 12

February 1, 2016

10:24 AM

Lecture Notes Page 1