# Concept derivation guides

299 concept teaching guides, separate from the 36,000 individual question derivations.

[Search all questions & derivations →](/en/explore/)

1 1 results · Page 1 of 1



Concept guide



## [Greatest common divisor and coprimality: checking Euclid's algorithm against the divisibility characterization](/en/derivations/derivation-mko-gcd-coprime-01/?from=%2Fen%2Fderivations%2F%3Fq%3Dmko-gcd-coprime)

From the MKO's divisibility characterization (d∣a, d∣b, and every common divisor c divides d): (1) prove that at most one d satisfies it; (2) prove that each step of Euclid's algorithm preserves the set of common divisors and that the algorithm stops, use it to compute gcd(84,36)=12, and verify directly that 12 satisfies the characterization; (3) explain why the common divisor 6 is not the gcd; (4) compute gcd(8,15)=1 and explain that 8 and 15 are coprime although neither is prime; (5) treat the zero cases gcd(0,1)=1, gcd(0,6)=6 and gcd(0,0)=0.

Greatest common divisor and coprimality

derivation-mko-gcd-coprime-01





1 1 results · Page 1 of 1