![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Euclid%2527s_algorithm_Book_VII_Proposition_2_3.png/640px-Euclid%2527s_algorithm_Book_VII_Proposition_2_3.png&w=640&q=50)
Αλγόριθμος του Ευκλείδη
From Wikipedia, the free encyclopedia
Στα μαθηματικά, ο αλγόριθμος του Ευκλείδη ή Ευκλείδειος αλγόριθμος είναι μια αποτελεσματική μέθοδος για τον υπολογισμό του μέγιστου κοινού διαιρέτη (ΜΚΔ) δύο ακέραιων αριθμών, είναι επίσης γνωστός ως ο μεγαλύτερος κοινός παράγοντας ή υψηλότερος κοινός παρονομαστής. Το όνομά του προέρχεται από τον Έλληνα μαθηματικό Ευκλείδη, ο οποίος τον περιγράφει στα βιβλία VII και X του βιβλίου του Στοιχεία.[1]
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/Euclid%27s_algorithm_Book_VII_Proposition_2_3.png/320px-Euclid%27s_algorithm_Book_VII_Proposition_2_3.png)
Στην απλούστερη μορφή του, ο αλγόριθμος του Ευκλείδη ξεκινά με ένα ζεύγος θετικών ακεραίων και σχηματίζει ένα νέο ζευγάρι που αποτελείται από το μικρότερο αριθμό και τη διαφορά μεταξύ των μεγαλύτερων και των μικρότερων αριθμών. Η διαδικασία επαναλαμβάνεται έως ότου οι αριθμοί είναι ίσοι. Αυτός ο αριθμός είναι τότε ο μέγιστος κοινός διαιρέτης του αρχικού ζεύγους.
Η παλαιότερη περιγραφή που υπάρχει για τον Ευκλείδειο αλγόριθμο είναι στα Στοιχεία του Ευκλείδη (περ. 300 π.Χ.), καθιστώντας τον ένα από τους παλαιότερους αριθμητικούς αλγορίθμους ακόμα σε κοινή χρήση. Ο αρχικός αλγόριθμος αφορούσε μόνο φυσικούς αριθμούς και γεωμετρικά μήκη (πραγματικοί αριθμοί), αλλά ο αλγόριθμος γενικεύτηκε τον 19ο αιώνα και σε άλλους τύπους αριθμών, όπως Gaussian ακέραιοι και πολυώνυμα μιας μεταβλητής. Αυτό οδήγησε στις σύγχρονες αφηρημένες αλγεβρικές έννοιες, όπως οι Ευκλείδειες δομές. Ο Ευκλείδειος αλγόριθμος έχει γενικευτεί περαιτέρω και σε άλλες μαθηματικές δομές, όπως κόμβους κύκλων nots και πολυώνυμα πολλών μεταβλητών .
Ο αλγόριθμος έχει πολλές θεωρητικές και πρακτικές εφαρμογές. Μπορεί να χρησιμοποιηθεί για να δημιουργήσει σχεδόν όλους τους πιο σημαντικούς παραδοσιακούς μουσικούς ρυθμούς που χρησιμοποιούνται σε διαφορετικούς πολιτισμούς σε όλο τον κόσμο.[2]Πρόκειται για ένα βασικό στοιχείο του RSA αλγορίθμου, μια μέθοδο κρυπτογράφησης δημόσιου κλειδιού που χρησιμοποιείται ευρέως στο ηλεκτρονικό εμπόριο. Χρησιμοποιείται για την επίλυση Διοφαντικών εξισώσεων, όπως η εξεύρεση αριθμών που ικανοποιούν πολλαπλά σχήματα με ίδιο ύψος και μέγεθος ( Κινέζικο θεώρημα υπολοίπων ) ή πολλαπλασιαστικά αντίστροφα ενός πεπερασμένου σώματος. Μπορεί επίσης να χρησιμοποιηθεί για την κατασκευή συνεχών κλασμάτων , στην αλυσίδα Sturm,μέθοδο για την εύρεση πραγματικών ριζών ενός πολυωνύμου, και σε πολλές σύγχρονες ακέραιες παραγοντοποιήσεις αλγορίθμων. Τέλος, είναι ένα βασικό εργαλείο για την απόδειξη θεωρημάτων στη σύγχρονη θεωρία αριθμών, όπως το θεώρημα των τεσσάρων τετραγώνων του Lagrange και το θεμελιώδες θεώρημα της αριθμητικής (μοναδική παραγοντοποίηση).
Εάν υλοποιηθεί με τη χρήση υπολοίπων της Ευκλείδειας διαίρεσης και όχι με αφαιρέσεις, ο αλγόριθμος του Ευκλείδη υπολογίζει το ΜΚΔ μεγάλων αριθμών αποτελεσματικά: Ποτέ δεν απαιτεί περισσότερα βήματα διαίρεσης από πέντε φορές τον αριθμό των ψηφίων (με βάση το 10) από τον μικρότερο ακέραιο. Αυτό αποδείχθηκε από τον Gabriel Lamé το 1844 και σηματοδοτεί την έναρξη της υπολογιστικής θεωρίας πολυπλοκότητας. Μέθοδοι για τη βελτίωση της απόδοσης του αλγορίθμου αναπτύχθηκαν τον 20ο αιώνα.
Ο ΜΚΔ των δύο αριθμών είναι ο μεγαλύτερος αριθμός που διαιρεί τους δύο χωρίς να αφήνει υπόλοιπο . Ο Ευκλείδειος αλγόριθμος βασίζεται στην αρχή ότι ο μέγιστος κοινός διαιρέτης των δύο αριθμών δεν αλλάζει εάν ο μικρότερος αριθμός αφαιρείται από το μεγαλύτερο αριθμό. Αν k , m και n είναι ακέραιοι, και το k είναι ένας κοινός παράγοντας των δύο ακεραίων αριθμών Α και Β , τότε Α = ΝΚ και Β = mk συνεπάγεται A − B = (n − m)k, συνεπώς, k είναι επίσης ένας κοινός παράγοντας της διαφοράς. Αυτό το k μπορεί επίσης να αντιπροσωπεύει τον μέγιστο κοινό διαιρέτη όπως αποδεικνύεται παρακάτω. Για παράδειγμα, το 21 είναι ο ΜΚΔ των 105 και 252 (252 = 12 × 21; 105 = 5 × 21). Από το 252 − 105 = (12 − 5) × 21 = 147, ο ΜΚΔ των 147 και 105 είναι επίσης 21.
Δεδομένου ότι ο μεγαλύτερος από τους δύο αριθμούς μειώνεται, επαναλαμβάνοντας τη διαδικασία, αυτή θα δίνει διαδοχικά μικρότερους αριθμούς μέχρι ένας από αυτούς να γίνει μηδέν. Όταν αυτό συμβεί, ο ΜΚΔ είναι ο μη μηδενικός αριθμός που απομένει. Αντιστρέφοντας τα βήματα του αλγόριθμου του Ευκλείδη , ο ΜΚΔ μπορεί να εκφραστεί ως το άθροισμα/γραμμικός συνδιασμός των δύο αρχικών αριθμών καθώς πολλαπλασιάζεται με ένα θετικό ή αρνητικό ακέραιο, π.χ. 21 = [5 × 105] + [(−2) × 252]. Αυτή η σημαντική ιδιότητα είναι γνωστή ως ταυτότητα του Bézout.