Μέγιστος κοινός διαιρέτης

Μέγιστος κοινός διαιρέτης δύο ακεραίων αριθμών είναι ο αριθμός που διαιρεί και τους δύο αριθμούς χωρίς υπόλοιπο και για τον οποίο δεν υπάρχει άλλος μεγαλύτερος αριθμός που να διαιρεί και τους δύο αριθμούς χωρίς υπόλοιπο.

Για παράδειγμα ας πάρουμε τους αριθμούς 24 και 32. Ποιος είναι ο μέγιστος κοινός διαιρέτης τους; Ψάχνουμε πρώτα έναν αριθμό που να διαιρεί και τους δύο αριθμούς.

• Π.χ. ο αριθμός 12 διαιρεί μεν τον αριθμό 24, αλλά δεν διαιρεί τον αριθμό 32, επειδή το 32 / 12 ισούται με 2,666… που δεν είναι ακέραιος. Άρα ο αριθμός 12 δεν μπορεί να είναι ο μέγιστος κοινός διαιρέτης των αριθμών 24 και 32.
• Και ο αριθμός 4; Αυτός διαιρεί και τους δύο αριθμούς, το 24 / 4 ισούται με 6 και το 32 / 4 ισούται με 8. Ο αριθμός 4 είναι λοιπόν ο πρώτος υποψήφιός μας. Υπάρχει κάποιος μεγαλύτερος αριθμός που να διαιρεί και τους δύο αριθμούς;
• Ο αριθμός 8 διαιρεί και τον αριθμό 24 και τον αριθμό 32 και ταυτόχρονα είναι μεγαλύτερος από τον αριθμό 4.
• Κανένας άλλος αριθμός μεγαλύτερος από το 8 που να διαιρεί και τους δύο αριθμούς δεν υπάρχει. Ο αριθμός 8 είναι λοιπόν ο μέγιστος κοινός διαιρέτης των αριθμών 24 και 32.

Ο αλγόριθμος του Ευκλείδη για την εύρεση του μέγιστου κοινού διαιρέτη

Υπάρχει ένας σχετικά απλός τρόπος να βρούμε τον μέγιστο κοινό διαιρέτη δύο αριθμών με τον αλγόριθμο του Ευκλείδη. Ας έχουμε στην αρχή δύο αριθμούς x και y, για τους οποίους θέλουμε να βρούμε τον μέγιστο κοινό διαιρέτη. Για παράδειγμα θα το δοκιμάσουμε στους αριθμούς x = 50 και y = 35. Τότε θα προχωρήσουμε ως εξής:

1. Διαιρούμε x / y και κρατάμε το υπόλοιπο της διαίρεσης. Αυτό το υπόλοιπο το σημειώνουμε ως z. Για το παράδειγμά μας παίρνουμε 50 / 35, που μας δίνει υπόλοιπο z = 15.
2. Τώρα εναλλάσσουμε τις μεταβλητές και στη μεταβλητή x αποθηκεύουμε την τιμή του y και στο y αποθηκεύουμε την τιμή του z. Την αρχική τιμή του x την πετάμε. Μετά από αυτό το βήμα παίρνουμε x = 35 και y = 15.
3. Τώρα κοιτάμε αν το y ισούται με μηδέν. Αν ναι, ο μέγιστος κοινός διαιρέτης είναι ο αριθμός x. Επειδή το y δεν ισούται με μηδέν, συνεχίζουμε και επαναλαμβάνουμε ολόκληρη τη διαδικασία από το πρώτο βήμα.
4. Διαιρούμε πάλι x / y, δηλαδή διαιρούμε 35 / 15, που μας δίνει υπόλοιπο διαίρεσης z = 5.
5. Εκτελούμε την εναλλαγή των μεταβλητών, παίρνουμε λοιπόν x = 15 και y = 5. Επειδή το y δεν ισούται με μηδέν, συνεχίζουμε.
6. Διαιρούμε x / y, δηλαδή διαιρούμε 15 / 5. Το υπόλοιπο της διαίρεσης είναι z = 0.
7. Εναλλάσσουμε τις μεταβλητές και παίρνουμε x = 5 και y = 0.
8. Αυτή τη στιγμή είναι y = 0 και ο αλγόριθμός μας τελειώνει. Μέγιστος κοινός διαιρέτης είναι ο αριθμός x = 5.

Σημαντικό είναι ότι η σειρά των αριθμών δεν παίζει ρόλο. Αν είχαμε εναλλάξει τους αριθμούς του παραδείγματος, θα παίρναμε το ζεύγος x = 35 και y = 50. Η διαδικασία θα ήταν η ίδια:

1. Διαιρούμε x / y, δηλαδή διαιρούμε 35 / 50, που μας δίνει υπόλοιπο z = 35.
2. Εναλλάσσουμε τις μεταβλητές x = 50 και y = 35.
3. Βλέπουμε ότι μετά από αυτό το βήμα απλώς αλλάξαμε μεταξύ τους το περιεχόμενο των μεταβλητών x και y…

Αριθμομηχανή

Αυτή η αριθμομηχανή υπολογίζει τον μέγιστο κοινό διαιρέτη.