Μια Χρήσιμη Ταυτότητα για τον ΜΚΔ

Μια πολύ χρήσιμη και θεμελιώδης ταυτότητα για τον Μέγιστο Κοινό Διαιρέτη (ΜΚΔ) δύο φυσικών αριθμών είναι η εξής:

$$\text{ΜΚΔ}(\alpha ,\beta )=\text{ΜΚΔ}(\alpha -\beta ,\beta )$$

Αυτή η σχέση βρίσκεται στον πυρήνα του Αλγορίθμου του Ευκλείδη, ο οποίος μας επιτρέπει να βρίσκουμε τον ΜΚΔ με απλές αφαιρέσεις. Μπορεί να εφαρμοστεί επαναληπτικά μέχρι να φτάσουμε σε αριθμούς που έχουν προφανή κοινό διαιρέτη.

Για παράδειγμα:

$$\text{ΜΚΔ}(20,8)=\text{ΜΚΔ}(12,8)=\text{ΜΚΔ}(4,8)=4$$

Η ουσία αυτής της ταυτότητας είναι ότι η πράξη της αφαίρεσης δεν επηρεάζει το σύνολο των κοινών διαιρετών δύο αριθμών.