As the numbers in question become larger and larger,
the factoring task becomes more and more difficult and time-consuming. Euclid discovered an algorithm that
systematically and quickly reduces the size of the problem by replacing the original pair of numbers by smaller
pairs until one of the pair becomes zero, at which point the GCD is the other number of the pair (the GCD
of any number and 0 is that number).
Here is Euclid??™s algorithm for finding the GCD of any two numbers A and B.
Repeat:
If B is zero, the GCD is A.
Otherwise:
find the remainder R when dividing A by B
replace the value of A with the value of B
replace the value of B with the value of R
For example, to find the GCD of 372 and 84, which we will show as:
GCD(372, 84)
Find GCD(84, 36) because 372/84 ??”> remainder 36
Find GCD(36, 12) because 84/36 ??”> remainder 12
Find GCD(12, 0) because 36/12 ??”> remainder 0; Solved! GCD = 12
More formally, an algorithm is a sequence of computations that operates on some set of inputs and produces
a result in a finite period of time. In the example of the algorithm for designing stairs, the inputs are the total rise
and total run. The result is the best specification for the number of steps, and for the rise and run of each step.
Pages:
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50