Last updated at October 28, 2026 by Teachoo
Transcript
Finding the Greatest Common Divisor After finding both divisor lists, we must identify the entries common to them. The procedure is: Start with an empty common-divisors list. Examine each entry in the first divisor list. Check whether it appears in the second list. If it does, append it to common-divisors. Example – find gcd (325, 825) Now, divisors(325) =[1, 3, 5, 15, 25, 75, 125, 375] divisors(825) =[1, 3, 5, 11, 15, 25, 33, 55, 75, 165, 275, 825] Then, we compare The completed list is: [1, 3, 5, 15, 25, 75] Because it is increasing, its rightmost entry is greatest. Thus, gcd(375, 825) = 75 divisors(325) | Is it present in divisors(825)? | Common-divisor list 1 | Yes | [1] 3 | Yes | [1, 3] 5 | Yes | [1, 3, 5] 15 | Yes | [1, 3, 5, 15] 25 | Yes | [1, 3, 5, 15, 25] 75 | Yes | [1, 3, 5, 15, 25, 75] 125 | No | Unchanged 375 | No | Unchanged gcd(375, 825) = 75 Why can the common-divisor list never be empty? Since 1 divides all numbers Therefore, 1 must divide both numbers So, common-divisor list will always have 1 Now, we can write our algorithm