Last updated at October 28, 2026 by Teachoo
Transcript
Ex 11.3, 2 What about the last algorithm described above? What happens when we look at common divisors starting from min(m, n) and work backwards to 1? The last algorithm described above is Final improved algorithm for gcd Set most-recent-common-divisor to 1. For each number π from 2 to min(π,π) : If π divides both π and π, set most-recent-common-divisor to π. Report most-recent-common-divisor as gcd(π,π) In the last algorithm, We store only the most recently found common divisor When scanning upwards, each new common divisor is greater than the previous one. When scanning downwards, each new common divisor is smaller Therefore, we must change how we use the result. The first common divisor found is the GCD. Stop immediately when it is found. Algorithm using a decreasing scan For each number π from min(π,π) down to 1 : If π divides both π and π, report π as the GCD and stop. There is no need to store or search for further common divisors. Example: Find π ππ(ππ,ππ) Begin at: min(12, 18)=12 Example: Find π ππ(ππ,ππ) Begin at: min(12, 18)=12 Candidate k | Does it divide both numbers? | Action 12 | No: it does not divide 18 | Continue 11 | No | Continue 10 | No | Continue 9 | No: it does not divide 12 | Continue 8 | No | Continue 7 | No | Continue 6 | Yes | Report 6 and stop Thus: gcd(12,18)=6 Why is the first successful candidate the greatest? We have already checked every larger possible candidate and rejected it. Therefore, no greater common divisor exists.