Page 86 - 'Blast_Into_Math

Blast into Math! The Euclidean algorithm: a computational recipe

4. Write a computer or calculator program that executes the Euclidean Algorithm to find
the greatest common divisor of two positive integers. Test your algorithm. The second
part of this problem you can do without a computer or programmable calculator: write an
algorithm based on the Euclidean Algorithm and the proof of the IUT which finds the r
and s in the IUT.
5. Show that if b|a and c|a and (b, c)= 1 then bc|a.
6. Prove if (b, c)= 1 then (a, bc)= (a, b)(a, c).
7. We can also define the greatest common divisor of three or more numbers: if not all the
numbers are zero, the greatest common divisor is the largest integer which divides them all.

Show that (a, b, c)= ((a, b),c) provided that a and b are not both 0.
8. Product notation is a short way to write a product of numbers. When we write
n

x k ,
k=1
with x 2 with x 3 and all the way up to x n . For example,
this means the product of x 1

n
1
1+
k
k=1
means the product

1 1 1 1

1+ 1+ 1+ ... 1+ .
1 2 3 n

Prove that for all n ∈ N ,

n
1
1+ = n +1.
k
k=1

9. Factorials: for n ∈ N, we write n! to mean the product of n and all the smaller positive
integers. For example
5! =5 ∗ 4 ∗ 3 ∗ 2 ∗ 1,

9! =9 ∗ 8 ∗ 7 ∗ 6 ∗ 5 ∗ 4 ∗ 3 ∗ 2 ∗ 1,

and in general, using product notation

n

n!= k.
k=1

86