Αλγόριθμος του Ευκλείδη

Στα Στοιχεία του Ευκλείδη το Βιβλίο VII αρχίζει με τον αλγόριθμο του Ευκλείδη^[1], με τον οποίο βρίσκουμε το μέγιστο κοινό διαιρέτη (ΜΚΔ) δύο αριθμών. Είναι ένας από τους παλαιότερους αλγόριθμους με μεγάλη σπουδαιότητα, καθώς για την εύρεση του MΚΔ δεν απαιτείται παραγοντοποίηση των ακεραίων.

[Επεξεργασία] Αλγόριθμος

GCD(a, b)
1 IF b = 0 THEN 
2   RETURN a
3 ELSE 
4   RETURN GCD(b, a mod b)

Με δεδομένους δύο φυσικούς αριθμούς α και β με α>β (αν ισχύει α<β άλλαζουμε τη σειρά τους):

αν ο β είναι 0 τότε ο α είναι ο ΜΚΔ
αν ο β δεν είναι 0 τότε επαναλαμβάνουμε τη διαδικασία^[2] χρησιμοποιώντας τον β και το υπόλοιπο της διαίρεσης α/β

[Επεξεργασία] Παράδειγμα

Έστω ότι έχουμε τους αριθμούς 124, 34 και θέλουμε να βρούμε το μέγιστο κοινό διαιρέτη τους.

α	β	Επεξήγηση
124	34	124 > 34
34	22	22 = 124 mod^[3] 34 (δηλαδή το 22 είναι το υπόλοιπο του 124/34)
22	12	12 = 34 mod 22 (το 12 είναι το υπόλοιπο του 34/22)
12	10	κλπ.
10	2
2	0	αφού το β γίνεται 0 ο αλγόριθμος τερματίζει και το α (εδώ το 2) είναι ο μέγιστος κοινός διαιρέτης

Επομένως ο αριθμός 2 είναι ο μέγιστος κοινός διαιρέτης (ΜΚΔ) των 124, 34.

[Επεξεργασία] Σημειώσεις

↑ Αρχικός αλγόριθμος. Ο αρχικός αλγόριθμος όπως περιγράφηκε από τον Ευκλείδη αντιμετώπιζε το πρόβλημα γεωμετρικά, χρησιμοποιώντας επαναλαμβανόμενες αφαιρέσεις αντί για το υπόλοιπο της διαίρεσης (mod).
```
 GCD(a, b)
 1 WHILE b ≠ 0
 2   IF a > b THEN
 3     a := a - b
 4   ELSE
 5     b := b - a
 6 RETURN a
```
↑ με αναδρομή
↑ mod είναι η πράξη του υπολοίπου (στη C και στη Java συμβολίζεται με %)

[Επεξεργασία] Ανάλυση Ορθότητας

Έστω, $x$ και $y$ οι αριθμοί των οποίων μας ενδιαφέρει η εύρεση του ΜΚΔ, με $x\geq y>0$ . Ισχύει ότι $x=\pi*y+\upsilon$ , όπου $\pi$ είναι το πηλίκο και $\upsilon$ το υπόλοιπο της Ευκλείδιας διαίρεσης του $x$ με το $y$ . Μπορούμε εύκολα να παρατηρήσουμε ότι κάθε κοινός διαιρέτης του $x$ και του $y$ θα είναι και κοινός διαιρέτης του $y$ και του $\upsilon$ . Για να το δούμε αυτό, παίρνουμε την $x=\pi*y+\upsilon$ και την γράφουμε ως $\upsilon=x-\pi*y$ και έστω $\delta$ ένας κοινός διαιρέτης των $x$ και $y$ . Επειδή ακριβώς, ο $\delta$ διαιρεί ακριβώς τόσο τον $x$ όσο και τον $y$ , ισχύει $x=k*\delta$ και $y=l*\delta$ , όπου τα $k$ , $l$ είναι ακέραιοι. Άρα, $\upsilon=x-\pi*y=k*\delta-\pi*l*\delta=(k-\pi*l)*\delta$ , όμως και το $\pi$ είναι ακέραιος, αφού εκφράζει πηλίκο και επομένως, η ποσότητα $(k-\pi*l)$ είναι ακέραιος αριθμός και μάλιστα μεγαλύτερος ή ίσος του μηδενός. Άρα, το $\upsilon$ είναι και αυτό ίσο με κάποιο ακέραιο πολλαπλάσιο του $\delta$ , και συνεπώς το $\delta$ είναι διαιρέτης του $\upsilon$ . Ακόμα, με τον ίδιο περίπου τρόπο μπορούμε να δείξουμε ότι κάθε κοινός διαιρέτης του $y$ και του $\upsilon$ θα είναι και κοινός διαιρέτης των $x$ και $y$ (των οποίων η διαίρεση έδωσε το $\upsilon$ ). Παρατηρούμε, επομένως, ότι τα ζεύγη $(x,y)$ και $(y,\upsilon)$ έχουν ακριβώς τους ίδιους κοινούς διαιρέτες. Άρα, μπορούμε αναδρομικά να αναζητούμε τους κοινούς διαιρέτες σε μικρότερους αριθμούς και είμαστε βέβαιοι ότι η διαδικασία θα ολοκληρωθεί μετά από πεπερασμένο αριθμό βημάτων, αφού το υ είναι πάντοτε μικρότερο από το $y$ και η αρχική είσοδος είναι πάντοτε πεπερασμένη. Το προτελευταίο αναδρομικό βήμα του αλγορίθμου είναι πάντοτε αυτό κατά το οποίο η διαίρεση του $x$ με το $y$ δίνει υπόλοιπο μηδέν. Άρα, στο επόμενο και τελευταίο αναδρομικό βήμα θα επιστραφεί το $y$ ορθά ως ο μέγιστος κοινός διαιρέτης των αρχικών $x$ και $y$ , αφού είναι των τρέχοντων και ως εκ τούτου όλων των προηγούμενων ζευγών που έχουν παρουσιαστεί στην αναδρομή (με βάση το προηγούμενό μας επιχείρημα).