Προβολή πηγαίου κώδικα για τη σελίδα Αλγόριθμος του Ευκλείδη

[[File:Euclid's algorithm Book VII Proposition 2 3.png|300px|thumb|right|Μέθοδος του Ευκλείδη για την εύρεση του μέγιστου κοινού διαιρέτη (ΜΚΔ) των δύο αρχικών μηκών BA και DC, και για τα δύο ορίζεται να είναι  τα πολλαπλάσια μιας κοινής «μονάδας» μήκους.Το γεγονός ότι μικραίνει το μήκος DC, χρησιμοποιείται για να "μετρήσει" το  BA, αλλά μόνο μια φορά, επειδή το υπόλοιπο ΕΑ είναι μικρότερο από το CD. Το EA μετρά πλέον (δύο φορές), το μικρότερο μήκος DC, με την υπόλοιπη ομάδα FC μικρότερη από EA. Στη συνέχεια το FC είναι (τρεις φορές) το μήκος EA .Επειδή δεν υπάρχει υπόλοιπο, η διαδικασία τελειώνει με το μήκος FC να είναι ο ΜΚΔ. Δεξιά  [[Νικάμαχος]] παράδειγμα με τους αριθμούς 49 και 21, με αποτέλεσμα ΜΚΔ τους να είανι το 7 (που προέρχεται από Heath 1908:300).]]

Στα [[μαθηματικά]], ο '''αλγόριθμος του Ευκλείδη''' ή '''Ευκλείδειος αλγόριθμος''' είναι μια αποτελεσματική μέθοδος για τον υπολογισμό του [[Μέγιστος κοινός διαιρέτης|μέγιστου κοινού διαιρέτη]] (ΜΚΔ) δύο [[Ακέραιος αριθμός|ακέραιων αριθμών]], είναι επίσης γνωστός ως ο μεγαλύτερος κοινός παράγοντας  ή υψηλότερος κοινός παρονομαστής. Το όνομά του προέρχεται από τον Έλληνα μαθηματικό [[Ευκλείδης|Ευκλείδη]], ο οποίος τον περιγράφει στα βιβλία VII και X του βιβλίου του ''Στοιχεία''.<ref>[[Thomas L. Heath]], ''The Thirteen Books of Euclid's Elements'', 2nd ed. [Facsimile. Original publication: Cambridge University Press, 1925], 1956, [[Dover Publications]]</ref>

Στην απλούστερη μορφή του, ο αλγόριθμος του Ευκλείδη ξεκινά με ένα ζεύγος θετικών ακεραίων και σχηματίζει ένα νέο ζευγάρι που αποτελείται από το μικρότερο αριθμό και τη διαφορά μεταξύ των μεγαλύτερων και των μικρότερων αριθμών. Η διαδικασία επαναλαμβάνεται έως ότου οι αριθμοί είναι ίσοι. Αυτός ο αριθμός είναι τότε ο μέγιστος κοινός διαιρέτης του αρχικού ζεύγους.

Η παλαιότερη περιγραφή που υπάρχει για τον Ευκλείδειο αλγόριθμο είναι στα ''Στοιχεία'' του Ευκλείδη (περ. 300 π.Χ.), καθιστώντας τον ένα από τους παλαιότερους αριθμητικούς [[Αλγόριθμος|αλγορίθμους]] ακόμα σε κοινή χρήση. Ο αρχικός αλγόριθμος αφορούσε μόνο φυσικούς αριθμούς και γεωμετρικά μήκη (πραγματικοί αριθμοί), αλλά ο αλγόριθμος γενικεύτηκε τον 19ο αιώνα και σε άλλους τύπους αριθμών, όπως Gaussian ακέραιοι και πολυώνυμα μιας μεταβλητής. Αυτό οδήγησε στις σύγχρονες αφηρημένες αλγεβρικές έννοιες, όπως οι [[Ευκλείδειες δομές]]. Ο Ευκλείδειος αλγόριθμος έχει γενικευτεί περαιτέρω και σε άλλες μαθηματικές δομές, όπως κόμβους κύκλων [[nots]] και [[Πολυώνυμο πολλών μεταβλητών|πολυώνυμα πολλών μεταβλητών]] .

Ο αλγόριθμος έχει πολλές θεωρητικές και πρακτικές εφαρμογές. Μπορεί να χρησιμοποιηθεί για να δημιουργήσει σχεδόν όλους τους πιο σημαντικούς παραδοσιακούς μουσικούς ρυθμούς που χρησιμοποιούνται σε διαφορετικούς πολιτισμούς σε όλο τον κόσμο.<ref>{{Citation |last=Toussaint |first=Godfried |author-link=Godfried Toussaint |url=http://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf |title=The Euclidean algorithm generates traditional musical rhythms |journal=Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science |location=Banff, Alberta, Canada |date=July 31 to August 3, 2005 |pages=47&ndash;56 |doi= }}</ref>Πρόκειται για ένα βασικό στοιχείο του [[RSA|RSA αλγορίθμου]], μια μέθοδο [[Κρυπτογράφηση Δημόσιου Κλειδιού|κρυπτογράφησης δημόσιου κλειδιού]] που χρησιμοποιείται ευρέως στο [[ηλεκτρονικό εμπόριο]]. Χρησιμοποιείται για την επίλυση [[Διοφαντική εξίσωση|Διοφαντικών εξισώσεων]], όπως η εξεύρεση αριθμών που ικανοποιούν πολλαπλά σχήματα με ίδιο ύψος και μέγεθος ( [[Κινέζικο θεώρημα υπολοίπων]] ) ή [[πολλαπλασιαστικά αντίστροφα]] ενός πεπερασμένου σώματος. Μπορεί επίσης να χρησιμοποιηθεί για την κατασκευή συνεχών κλασμάτων , [[στην αλυσίδα Sturm]],μέθοδο για την εύρεση πραγματικών ριζών ενός πολυωνύμου, και σε πολλές σύγχρονες ακέραιες παραγοντοποιήσεις αλγορίθμων. Τέλος, είναι ένα βασικό εργαλείο για την απόδειξη θεωρημάτων στη σύγχρονη [[θεωρία αριθμών]], όπως το [[θεώρημα των τεσσάρων τετραγώνων του Lagrange ]]και το [[θεμελιώδες θεώρημα της αριθμητικής]] (μοναδική παραγοντοποίηση).

Εάν υλοποιηθεί με τη χρήση [[Υπόλοιπο|υπολοίπων]] της Ευκλείδειας διαίρεσης και όχι με αφαιρέσεις, ο αλγόριθμος του Ευκλείδη υπολογίζει το ΜΚΔ μεγάλων αριθμών αποτελεσματικά: Ποτέ δεν απαιτεί περισσότερα βήματα διαίρεσης από πέντε φορές τον αριθμό των ψηφίων (με βάση το 10) από τον μικρότερο ακέραιο. Αυτό αποδείχθηκε από τον  [[Gabriel Lamé]] το 1844 και σηματοδοτεί την έναρξη της [[Υπολογιστική θεωρία πολυπλοκότητας|υπολογιστικής θεωρίας πολυπλοκότητας]]. Μέθοδοι για τη  βελτίωση της απόδοσης του αλγορίθμου αναπτύχθηκαν τον 20ο αιώνα.

Ο ΜΚΔ των δύο αριθμών είναι ο μεγαλύτερος αριθμός που διαιρεί τους δύο χωρίς να αφήνει [[υπόλοιπο]] . Ο Ευκλείδειος αλγόριθμος βασίζεται στην αρχή ότι ο μέγιστος κοινός διαιρέτης των δύο αριθμών δεν αλλάζει εάν ο μικρότερος αριθμός αφαιρείται από το μεγαλύτερο αριθμό. Αν ''k'' , ''m'' και ''n'' είναι ακέραιοι, και το ''k'' είναι ένας κοινός παράγοντας των δύο ακεραίων  αριθμών ''Α'' και ''Β'' , τότε ''Α''&nbsp;=&nbsp;''ΝΚ'' και ''Β''&nbsp;=&nbsp;''mk'' συνεπάγεται ''A''&nbsp;&minus;&nbsp;''B''&nbsp;=&nbsp;(''n''&nbsp;&minus;&nbsp;''m'')''k'', συνεπώς, ''k'' είναι επίσης ένας κοινός παράγοντας της διαφοράς. Αυτό το ''k'' μπορεί επίσης να αντιπροσωπεύει τον μέγιστο κοινό διαιρέτη όπως αποδεικνύεται παρακάτω. Για παράδειγμα, το 21 είναι ο ΜΚΔ των 105 και 252 (252&nbsp;=&nbsp;12&nbsp;×&nbsp;21; 105&nbsp;=&nbsp;5&nbsp;×&nbsp;21). Από το 252&nbsp;−&nbsp;105&nbsp;=&nbsp;(12&nbsp;&minus;&nbsp;5)&nbsp;×&nbsp;21&nbsp;=&nbsp;147, ο ΜΚΔ των 147 και 105 είναι επίσης 21.

Δεδομένου ότι ο μεγαλύτερος από τους δύο αριθμούς μειώνεται, επαναλαμβάνοντας τη διαδικασία, αυτή θα δίνει διαδοχικά μικρότερους αριθμούς μέχρι ένας από αυτούς  να γίνει μηδέν. Όταν αυτό συμβεί, ο ΜΚΔ είναι ο μη μηδενικός αριθμός που απομένει. Αντιστρέφοντας τα βήματα του αλγόριθμου του Ευκλείδη , ο ΜΚΔ μπορεί να εκφραστεί ως το άθροισμα/[[γραμμικός συνδιασμός]] των δύο αρχικών αριθμών καθώς  πολλαπλασιάζεται με ένα θετικό ή αρνητικό [[ακέραιο]], π.χ. {{nowrap|21 {{=}} [5 × 105] + [(−2) × 252].}} Αυτή η σημαντική ιδιότητα είναι γνωστή ως [[ταυτότητα του Bézout]].

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

Ο Ευκλείδειος αλγόριθμος υπολογίζει το μέγιστο κοινό διαιρέτη (ΜΚΔ) δύο [[Φυσικός αριθμός|φυσικούς αριθμούς]] ''a'' και ''b''. Ο μέγιστος κοινός διαιρέτης ''g'' είναι ο μεγαλύτερος φυσικός αριθμός που διαιρεί τόσο τόσο τον ''a'' οσο και τον ''b'' χωρίς να αφήνει υπόλοιπο. Συνώνυμα για το ΜΚΔ είναι ο ''μεγαλύτερος κοινός παράγοντας'' , ο ''υψηλότερος κοινός παρανομαστής'' , και το μεγαλύτερο κοινό μέτρο (GCM). Ο μέγιστος κοινός διαιρέτης συχνά γράφεται ως ΜΚΔ(''a'', ''b'') ή, πιο απλά, όπως (''a'',&nbsp;''b''),<ref>{{Harvnb|Stark|1978|p=16}}</ref> αν και το τελευταίο χρησιμοποιείται επίσης στη σημειογραφία για άλλες μαθηματικές έννοιες, όπως δισδιάστατα συγγραμικά διανύσματα.

Αν ΜΚΔ(''a'',&nbsp;''b'')&nbsp;=&nbsp;1, τότε λέγεται ότι  a και b είναι [[Πρώτος αριθμός|πρώτοι]] μεταξύ τους (ή [[σχετικά πρώτοι]]).<ref>{{Harvnb|Stark|1978|p=21}}</ref> Αυτή η ιδιότητα δεν σημαίνει ότι a ή b είναι οι ίδιοι [[πρώτοι αριθμοί]].<ref>{{Harvnb|LeVeque|1996|p=32}}</ref> Για παράδειγμα, ούτε το 6 ούτε το 35 είναι πρώτοι αριθμοί, δεδομένου ότι και οι δύο έχουν δύο πρώτους παράγοντες: 6&nbsp;=&nbsp;2&nbsp;×&nbsp;3 και 35&nbsp;=&nbsp;5&nbsp;×&nbsp;7. Παρ 'όλα αυτά, 6 και 35 είναι πρώτοι μεταξύ τους. Δεν υπάρχει φυσικός αριθμός εκτός από το 1 που διαιρεί τους 6 και 35, δεδομένου ότι δεν έχουν κοινούς πρώτους παράγοντες.

[[File:24x60.svg|thumb|upright|alt="Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall."|Ένα 24-επί-60 ορθογώνιο καλύπτεται με δέκα 12-επί-12 τετράγωνα πλακίδια, όπου 12 είναι ο ΜΚΔ των 24 και 60.Γενικότερα, ένα ''a''-by-''b'' ορθογώνιο μπορεί να καλυφθεί με τετράγωνα πλακίδια της πλευράς μήκους''c'' μόνο αν ''c'' είναι ένα κοινός διαιρέτης των ''a'' και ''b'' .]]

Έστω ''g'' = ΜΚΔ(''a'',&nbsp;''b''). Δεδομένου ότι ''a'' και ''b'' είναι και οι δύο πολλαπλάσια του ''g'' , μπορούν να γραφτούν ''a''&nbsp;=&nbsp;''mg'' και ''b''&nbsp;=&nbsp;''ng'', και δεν υπάρχει μεγαλύτερος αριθμός ''G''&nbsp;>&nbsp;''g''  για τον οποίο αυτό να ισχύει. Οι φυσικοί αριθμοί ''m'' και ''n'' πρέπει να είναι πρώτοι μεταξύ τους, δεδομένου ότι κάθε κοινός παράγοντας θα μπορούσε να υπολογιστεί από το ''m'' και το ''n'' ώστε να κάνει το ''g'' μεγαλύτερο. Έτσι, οποιοσδήποτε άλλος αριθμός ''c'' που διαιρεί και το ''a'' και ''b'' πρέπει να διαιρεί επίσης και το ''g'' . Ο μέγιστος κοινός διαιρέτης ''g'' των ''a'' και ''b'' είναι ο μοναδικός (θετικός) κοινός διαιρέτης του ''a'' και ''b'' που διαιρείται από οποιοδήποτε άλλο κοινό τους διαιρέτη ''c'' .<ref>{{Harvnb|LeVeque|1996|p=31}}</ref>

Ο ΜΚΔ μπορεί να απεικονιστεί ως εξής.<ref>{{cite book | author = Grossman JW | year = 1990 | title = Discrete Mathematics | publisher = Macmillan | location = New York | isbn = 0-02-348331-8 | page = 213}}</ref> Σκεφτείτε μια ορθογώνια περιοχή  ''a'' επι ''b'', και ''g'' κάθε κοινός διαιρέτης που διαιρεί ταυτόχρονα τα ''a'' και ''b'' ακριβώς. Οι πλευρές του ορθογωνίου μπορούν να διαιρεθούν σε τμήματα μήκους ''c'' , το οποίο διαιρεί το ορθογώνιο σε ένα πλέγμα από τετράγωνα με μήκος πλευράς ''c''. Ο μέγιστος κοινός διαιρέτης ''g'' είναι η μεγαλύτερη τιμή του ''c'' για τις οποίες αυτό είναι δυνατό. Για παράδειγμα, μια 24-επί-60 ορθογώνια περιοχή μπορεί να διαιρεθεί σε ένα πλέγμα από: 1-επί-1 τετραγώνα, 2-επί-2 τετράγωνα, 3-επί-3 τετράγωνα, 4-επί-4 τετράγωνα, από 6-επί -6 τετράγωνα ή 12-από-12 τετράγωνα. Ως εκ τούτου, 12 είναι ο μέγιστος κοινός διαιρέτης του 24 και 60. Μία 24-επί-60 ορθογώνια περιοχή μπορεί να διαιρεθεί σε ένα πλέγμα 12-επί-12 τετραγώνων, με δύο τετράγωνα κατά μήκος ενός άκρου (24/12&nbsp;=&nbsp;2) και πέντε τετράγωνα κατά μήκος του άλλου (60/12&nbsp;=&nbsp;5) .

Ο ΜΚΔ δύο αριθμών ''a'' και ''b'' είναι το γινόμενο των πρώτων παραγόντων που είναι κοινοί των δύο αριθμών, όπου ένας κοινός πρώτος παράγοντας  μπορεί να χρησιμοποιηθεί πολλές φορές, αλλά μόνο για όσο το γινόμενο αυτών των παραγόντων διαιρεί και το ''a'' και το ''b''.<ref name="Schroeder_21" >{{Harvnb|Schroeder|2005|pp=21–22}}</ref> Για παράδειγμα,αφού το 1386 μπορεί να υπολογιστεί σε 2&nbsp;×&nbsp;3&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;11 και το 3213 μπορεί να υπολογιστεί ως  3&nbsp;×&nbsp;3&nbsp;×&nbsp;3&nbsp;×&nbsp;7&nbsp;×&nbsp;17 , ο μέγιστος κοινός διαιρέτης των 1386 και 3213 ισούται με 63&nbsp;=&nbsp;3&nbsp;×&nbsp;3&nbsp;×&nbsp;7 , δηλαδή το αποτέλεσμα των κοινών τους πρώτων παραγόντων. Αν δύο αριθμοί δεν έχουν κοινούς πρώτους παράγοντες,ο μέγιστος κοινός διαιρέτης τους είναι το 1 (που λαμβάνεται εδώ ως παράδειγμα για το [[κενό]] ), με άλλα λόγια, είναι πρώτοι μεταξύ τους. Ένα βασικό πλεονέκτημα του Ευκλείδειου αλγόριθμου είναι ότι μπορεί να βρει το ΜΚΔ αποτελεσματικά χωρίς να χρειάζεται να υπολογίσει τους πρώτους παράγοντες.<ref>{{Harvnb|Schroeder|2005|p=19}}</ref><ref>{{cite book|title=Excursions in number theory|first=|author=Ogilvy CS, Anderson JT|publisher=[[Oxford University Press]]|isbn=|year=1966|location=New York|page=|pages=27–29|quote=}}</ref> Η [[ακέραια παραγοντοποίηση]] μεγάλων ακεραίων πιστεύεται ότι είναι υπολογιστικά πολύ δύσκολο πρόβλημα, και η ασφάλεια πολλών σύγχρονων συστημάτων κρυπτογραφίας βασίζεται στο γεγονός ότι αυτό είναι σχεδόν ακατόρθωτο εγχείρημα.<ref name="Schroeder_216" >{{Harvnb|Schroeder|2005|pp=216–219}}</ref>

Ένας άλλος ορισμός του ΜΚΔ είναι χρήσιμος στον τομέα των προηγμένων μαθηματικών, κυρίως στη [[θεωρία δακτυλίων]].<ref name="Leveque_p33" /> Ο μέγιστος κοινός διαιρέτης ''g''&nbsp;  δύο μη μηδενικών αριθμών ''a'' και ''b'' είναι επίσης ο μικρότερος θετικός ακέραιος γραμμικός τους συνδυασμός, δηλαδή, ο μικρότερος θετικός αριθμός της μορφής  ''ua''&nbsp;+&nbsp;''vb'' , όπου ''υ'' και ''ν'' είναι ακέραιοι. Το σύνολο όλων των ακέραιων γραμμικών συνδυασμών των ''a'' και ''b'' είναι στην πραγματικότητα το ίδιο με το σύνολο όλων των πολλαπλάσιων του ''g'' ( ''mg'' , όπου ''m'' είναι ένας ακέραιος αριθμός). Στη σύγχρονη μαθηματική γλώσσα, το [[ιδανικό]] που παράγεται από το ''a'' και το ''b'' είναι το ιδανικό που δημιουργείται από το  ''g'' μόνο (ένα ιδανικό που παράγεται από ένα μόνο στοιχείο ονομάζεται [[κύριο ιδανικό]] , και όλα τα ιδανικά των ακεραίων είναι τα κύρια ιδανικά). Μερικές ιδιότητες του ΜΚΔ είναι στην πραγματικότητα πιο εύκολο να γίνουν αντιληπτές με αυτή την περιγραφή, για παράδειγμα, το γεγονός ότι κάθε κοινός διαιρέτης του ''a'' και ''β'' διαιρεί επίσης τον ΜΚΔ τους (ο οποίος διαιρεί και τους δύο όρους της  ''ua''&nbsp;+&nbsp;''vb'' .Η ισοδυναμία αυτού του ορισμού του ΜΔΚ με τους άλλους ορισμούς περιγράφεται κατωτέρω.

Ο ΜΚΔ τριών ή περισσότερων αριθμών ισούται με το γινόμενο των πρώτων κοινών παραγόντων όλων των αριθμών,<ref>{{Harvnb|Stark|1978|p=25}}</ref> αλλά μπορεί επίσης να υπολογιστεί παίρνοντας διαδοχικά τον μέγιστο κοινό διαιρέτη ζευγών των αριθμών.<ref>{{Harvnb|Ore|1948|pp=47–48}}</ref> Για παράδειγμα,

: ΜΚΔ(''a'',&nbsp;''b'',&nbsp;''c'') = ΜΚΔ(''a'',&nbsp;ΜΚΔ(''b'',&nbsp;''c'')) = ΜΚΔ(ΜΚΔ(''a'',&nbsp;''b''),&nbsp;''c'') = ΜΚΔ(ΜΚΔ(''a'',&nbsp;''c''),&nbsp;''b'').

Έτσι, ο αλγόριθμος του Ευκλείδη, ο οποίος υπολογίζει το ΜΚΔ δύο ακεραίων χρησιμοποιείται επίσης για τον υπολογισμό του ΜΚΔ αυθαίρετα πολλών ακεραίων.

==Περιγραφή==

Η απλούστερη μορφή του αλγορίθμου του Ευκλείδη ξεκινά με ένα ζεύγος θετικών ακεραίων και σχηματίζει ένα νέο ζευγάρι που αποτελείται από το μικρότερο αριθμό και τη διαφορά μεταξύ των μεγαλύτερων και των μικρότερων αριθμών. Η διαδικασία επαναλαμβάνεται έως ότου οι αριθμοί είναι ίσοι. Στη συνέχεια ο αριθμός αυτός είναι ο μέγιστος κοινός διαιρέτης του αρχικού ζεύγους. Ωστόσο, εάν ένας αριθμός είναι πολύ μικρότερος από τον άλλο, πολλά βήματα αφαίρεσης θα είναι αναγκαία πριν ο μεγαλύτερος αριθμός μειωθεί σε μία τιμή μικρότερη ή ίση από τον άλλον αριθμό στο ζεύγος.
Αφαιρώντας ένα μικρό θετικό αριθμό από ένα μεγάλο αριθμό αρκετές φορές μέχρι αυτό που  απομένει  είναι μικρότερο από τον αρχικό ελάχιστο αριθμό,  μπορεί να αντικατασταθεί με την εύρεση του υπόλοιπο σε μεγάλη διαίρεση. Έτσι, η μορφή διαίρεσης του αλγορίθμου του Ευκλείδη ξεκινά με ένα ζεύγος θετικών ακεραίων και σχηματίζει ένα νέο ζεύγος που αποτελείται από το μικρότερο αριθμό και το υπόλοιπο που λαμβάνεται διαιρώντας τον μεγαλύτερο αριθμό από το μικρότερο αριθμό. Η διαδικασία επαναλαμβάνεται έως ότου ένας αριθμός είναι μηδέν. Ο άλλος αριθμός είναι τότε ο μέγιστος κοινός διαιρέτης του αρχικούζεύγους.

===Διαδικασία===

Ο Ευκλείδειος αλγόριθμος προχωρεί σε μια σειρά από βήματα έτσι ώστε το αποτέλεσμα από κάθε  βήμα να χρησιμοποιείται ως δεδομένο για το επόμενο βήμα. Ας είναι ''k'' ένας ακέραιος που μετράει τα βήματα του αλγορίθμου, ξεκινώντας από το μηδέν. Ετσι, το αρχικό στάδιο αντιστοιχεί σε ''k''&nbsp;=&nbsp;0 , το επόμενο βήμα αντιστοιχεί στο ''k''&nbsp;=&nbsp;1 , και ούτω καθεξής.
Κάθε βήμα ξεκινά με δύο μη αρνητικά  υπόλοιπα  ''r''<sub>''k''&minus;1</sub>  ''r''<sub>''k''&minus;2</sub>. Δεδομένου ότι ο αλγόριθμος εξασφαλίζει ότι τα υπόλοιπα  μειώνονται σταδιακά σε κάθε βήμα, το ''r''<sub>''k''&minus;1</sub>  είναι μικρότερο από το προηγούμενο  του ''r''<sub>''k''&minus;2</sub> . Ο στόχος στο  ''k'' βήμα  είναι να βρεθεί είναι [[πηλίκο]]  ''q''<sub>''k''</sub> και το [[υπόλοιπο]] ''r''<sub>''k''</sub> έτσι ώστε η εξίσωση να ικανοποιείται

: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>

όπου ''r''<sub>''k''</sub>&nbsp;<&nbsp;''r''<sub>''k''&minus;1</sub> . Με άλλα λόγια, τα πολλαπλάσια του μικρότερου αριθμού  ''r''<sub>''k''&minus;1</sub> αφαιρούνται από το μεγαλύτερο αριθμό  ''r''<sub>''k''&minus;2</sub> έως ότου το υπόλοιπο είναι μικρότερο από το ''r''<sub>''k''&minus;1</sub> .
Στο αρχικό στάδιο (''k''&nbsp;=&nbsp;0), τα υπόλοιπα  ''r''<sub>−2</sub> και ''r''<sub>−1</sub> αντιστοιχούν στα ''a'' και ''b'', οι αριθμοί για τους οποίους  ζητείται ο ΜΚΔ. Στο επόμενο βήμα (''k''&nbsp;=&nbsp;1), τα υπόλοιπα αντιστοιχούν στο  ''b'' και το υπόλοιπο  ''r''<sub>0</sub> του αρχικού βήματος, και ούτω καθεξής. Έτσι, ο αλγόριθμος μπορεί να γραφτεί ως μια ακολουθία των εξισώσεων:
: ''a'' = ''q''<sub>0</sub> ''b'' + ''r''<sub>0</sub>
: ''b'' = ''q''<sub>1</sub> ''r''<sub>0</sub> + ''r''<sub>1</sub>
: ''r''<sub>0</sub> = ''q''<sub>2</sub> ''r''<sub>1</sub> + ''r''<sub>2</sub>
: ''r''<sub>1</sub> = ''q''<sub>3</sub> ''r''<sub>2</sub> + ''r''<sub>3</sub>
: …

Εάν ''a'' είναι μικρότερο από το ''b'' , στο πρώτο βήμα του αλγορίθμου εναλάσσονται οι αριθμοί. Για παράδειγμα, εάν ''a''&nbsp;<&nbsp;''b'' , το αρχικό πηλίκο  ''q''<sub>0</sub>  ισούται με μηδέν, και το υπόλοιπο  ''r''<sub>0</sub> είναι ''a'' . Έτσι, το  ''r''<sub>''k''</sub>  είναι μικρότερο από το προηγούμενο  του r ''r''<sub>''k''−1</sub>  για όλα τα ''k''&nbsp;≥&nbsp;0.

Δεδομένου ότι τα υπόλοιπα μειώνονται  σε κάθε βήμα, αλλά ποτέ δεν μπορούν να γίνουν αρνητικά, ένα υπόλοιπο   ''r''<sub>''N''</sub> , τελικά θα γίνει ίσο με μηδέν, όπου και  ο αλγόριθμος σταματά.<ref>Stark 1978 , p. 18</ref>  Το τελευταίο μη μηδενικό υπόλοιπο ''r''<sub>''N''−1</sub> είναι ο μέγιστος κοινός διαιρέτης των "a" και "b" . Ο αριθμός "Ν" δεν μπορεί να είναι άπειρο, επειδή υπάρχουν μόνο  πεπερασμένοι το πλήθος  αριθμοί των μη αρνητικών ακέραιων ανάμεσα στο αρχικό υπολοίπο ''r''<sub>0</sub> και το μηδέν.

===Απόδειξη της ισχύος===
Η ισχύς του Ευκλείδειου αλγορίθμου μπορεί να αποδειχθεί από ένα  εγχείρημα δύο σταδίων.<ref>Stark 1978 , σελ. 16-20</ref> Στο πρώτο στάδιο, το τελευταίο μη μηδενικό υπόλοιπο ''r''<sub>''N''−1</sub> φαίνεται  να διαιρεί τόσο το ''a'' και το ''b'' . Δεδομένου ότι είναι ένας κοινός διαιρέτης, πρέπει να είναι μικρότερος ή ίσο με τον μέγιστο κοινό διαιρέτη ''g'' . Στο δεύτερο στάδιο, φαίνεται ότι κάθε κοινός διαιρέτης των ''a'' και ''b'' , συμπεριλαμβανομένου του  ''g'' , πρέπει να διαιρεί το ''r''<sub>''N''−1</sub>. Συνεπώς, το ''g'' πρέπει να είναι μικρότερο  ή ίσο του  ''r''<sub>''N''−1</sub>. Αυτά τα δύο συμπεράσματα είναι ασυμβίβαστα εκτός  αν ''r''<sub>''N''−1</sub>&nbsp;=&nbsp;''g''.

Για να δείξουμε ότι ''r''<sub>''N''−1</sub> διαιρεί τους ''a'' και ''b'' (στο πρώτο βήμα),το  ''r''<sub>''N''−1</sub>  διαιρεί  το προηγούμενο  του ''r''<sub>''N''−2</sub>
: ''r''<sub>''N''−2</sub> = ''q''<sub>''N''</sub> ''r''<sub>''N''−1</sub>
δεδομένου ότι το τελικό υπόλοιπο  ''r''<sub>''N''</sub> είναι μηδέν. Το  ''r''<sub>''N''−1</sub> διαιρεί επίσης και το  προπροηγούμενο του ''r''<sub>''N''−3</sub>
: ''r''<sub>''N''−3</sub> = ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub> + ''r''<sub>''N''−1</sub>
γιατί διαιρεί και  τους δύο όρους από τη δεξιά πλευρά της εξίσωσης. Επαναλαμβάνοντας  το ίδιο επιχείρημα, το  ''r''<sub>''N''−1</sub> διαιρεί όλα τα προηγούμενα υπόλοιπα, συμπεριλαμβανομένων του  ''a'' και του  ''b'' . Κανένα από τα προηγούμενα υπόλοιπα   ''r''<sub>''N''−2</sub> ,  ''r''<sub>''N''−3</sub>, κλπ. δε διαιρεί το  ''a'' και ''b'' , εφόσον αφήνουν  υπόλοιπο. Εφόσον το   ''r''<sub>''N''−1</sub> είναι κοινός διαιρέτης των ''a'' και ''b'' , ''r''<sub>''N''−1</sub>&nbsp;≤&nbsp;''g'' .

Στο δεύτερο στάδιο, κάθε φυσικός αριθμός ''c'', που διαιρεί και  το ''a'' και το  ''b''(με άλλα λόγια, κάθε κοινός διαιρέτης του ''a'' και ''b'' ) διαιρεί και τα υπόλοιπα  ''r''<sub>''k''</sub>. Εξ ορισμού, ''a'' και ''b'' μπορούν να γραφούν  ως πολλαπλάσια του ''c'': ''a''&nbsp;=&nbsp;''mc'' και ''b''&nbsp;=&nbsp;''nc'' , όπου ''m'' και ''n'' είναι φυσικοί αριθμοί. Ως εκ τούτου, ''c'' διαιρεί το αρχικό υπόλοιπο ''r''<sub>0</sub>, δεδομένου ότι ''r''<sub>0</sub>&nbsp;=&nbsp;''a''&nbsp;−&nbsp;''q''<sub>0</sub>''b''&nbsp;=&nbsp;''mc''&nbsp;−&nbsp;''q''<sub>0</sub>''nc''&nbsp;=&nbsp;(''m''&nbsp;−&nbsp;''q''<sub>0</sub>''n'')''c'' . Ένα ανάλογο επιχείρημα δείχνει ότι ''c'' διαιρεί επίσης, τα ακόλουθα υπόλοιπα ''r''<sub>1</sub>, ''r''<sub>2</sub> κλπ. Ως εκ τούτου, ο μέγιστος κοινός διαιρέτης g πρέπει να διαιρεί ''r''<sub>''N''−1</sub>  , πράγμα που σημαίνει ότι''g''&nbsp;≤&nbsp;''r''<sub>''N''−1</sub>  . Δεδομένου ότι το πρώτο μέρος του επιχειρήματος έδειξε το αντίθετο (''r''<sub>''N''−1</sub>&nbsp;≤&nbsp;''g''), προκύπτει ότι ''g''&nbsp;=&nbsp;''r''<sub>''N''−1</sub>  . Ετσι,  είναι ο ''g'' είναι ο  μεγαλύτερος κοινός διαιρέτης όλων των επόμενων ζευγών:<ref>Knuth, p. 320.</ref>
<ref>Lovász L, η Pelikan J, Vesztergombi K (2003) Διακριτά Μαθηματικά: Δημοτικό και πέρα . New York: Springer-Verlag. σελ. 100-101. ISBN  0-387-95584-4 .</ref>

:''g'' = GCD(''a'', ''b'') = GCD(''b'', ''r''<sub>0</sub>) = GCD(''r''<sub>0</sub>, ''r''<sub>1</sub>) = … = GCD(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''r''<sub>''N''−1</sub>.

===Παραδειγμα εργασίας===

[[File:Euclidean algorithm 1071 462.gif|upright|thumb|alt=Animation in which progressively smaller square tiles are added to cover a rectangle completely.|Animation της αφαίρεσης- έκδοση του αλγορίθμου. Το αρχικό πράσινο ορθογώνιο έχει διαστάσεις ''a''&nbsp;=&nbsp;1071 και ''b''&nbsp;=&nbsp;462 .Τετράγωνο 462&times;462 πλακίδια (κίτρινα) προστίθενται μέχρι ένα πράσινο να μείνει ένα 462&times;147 κομμάτι του ορθογωνίου . Αυτό είναι καλυμμένο με τετράγωνα 147&times;147 κεραμίδια (μπλε) μέχρι  να μείνει ένα 21&times;147 κομμάτι του ορθογωνίου. Αυτό το τρίτο ορθογώνιο αποτελείται από  21&times;21  τετράγωνα πλακίδια (κόκκινα), χωρίς να  αφήνει κανένα υπόλοιπο.Έτσι, το 21 είναι ο μέγιστος κοινός διαιρέτης των 1071 και 462.]]

Για παράδειγμα, ο Ευκλείδειος αλγόριθμος μπορεί να χρησιμοποιηθεί για να βρεθεί ο μέγιστος κοινός διαιρέτης ''a''&nbsp;=&nbsp;1071 και ''b''&nbsp;=&nbsp;462 .Ξεκινώντας ,πολλαπλάσια του 462 αφαιρούνται από το 1071 μέχρι το υπόλοιπο να γίνει μικρότερο από 462. Δύο τέτοια πολλαπλάσια μπορούν να αφαιρούνται (''q''<sub>0</sub>&nbsp;=&nbsp;2), αφήνοντας ένα υπόλοιπο του 147.

:1071 = 2 × 462 + 147.

Στη συνέχεια,πολλαπλάσια του 147 αφαιρούνται από το 462 μέχρι το υπόλοιπο είναι μικρότερο από 147. τρια πολλαπλάσια μπορούν να αφαιρεθούν (''q''<sub>1</sub>&nbsp;=&nbsp;3), αφήνοντας ένα υπόλοιπο του 21.

:462 = 3 × 147 + 21.

Στη συνέχεια,πολλαπλάσια του 21 αφαιρούνται από το 147 έως το υπόλοιπο είναι μικρότερο από 21. Επτά πολλαπλάσια μπορούν να αφαιρεθούν (''q''<sub>2</sub>&nbsp;=&nbsp;7), χωρίς να αφήσουν κανένα υπόλοιπο

:147 = 7 × 21 + 0.

Δεδομένου ότι το τελευταίο υπόλοιπο είναι μηδέν, ο αλγόριθμος τελειώνει με 21 ως το μέγιστο κοινό διαιρέτη των 1071 και 462. Αυτό συμφωνεί με τον ΜΚΔ(1071, 462) που βρέθηκε από την παραγοντοποίηση παραπάνω . Σε μορφή πίνακα, είναι τα βήματα

{| class="wikitable" id="basic_Euclidean_algorithm" style="margin-left:auto; margin-right:auto; text-align:center"
|-
! Βήμα ''k'' !! Εξίσωση	!!Πηλίκο και υπόλοιπο
|-
| 0 || 1071 = ''q''<sub>0</sub> 462 + ''r''<sub>0</sub> || ''q''<sub>0</sub> = 2 και ''r''<sub>0</sub> = 147
|-
| 1 || 462 = ''q''<sub>1</sub> 147 + ''r''<sub>1</sub> || ''q''<sub>1</sub> = 3 και ''r''<sub>1</sub> = 21
|-
| 2 || 147 = ''q''<sub>2</sub> 21 + ''r''<sub>2</sub> || ''q''<sub>2</sub> = 7 και ''r''<sub>2</sub> = 0  ,ο αλγόριθμος τελειώνει
|}

===Πραγματοποίηση===

Ο Ευκλείδειος αλγόριθμος μπορεί να γίνει αντιληπτός στα πλάισια της αναλογίας που περιγράφεται παραπάνω για τον μέγιστο κοινό διαιρέτη.<ref name="Kimberling_1983">{{cite journal | author = Kimberling C | year = 1983 | title = A Visual Euclidean Algorithm | url = https://archive.org/details/sim_mathematics-teacher_1983-02_76_2/page/108 | journal = Mathematics Teacher | volume = 76 | pages = 108–109}}</ref>Ας υποθέσουμε ότι θέλουμε να καλύψουμε ένα ''α''-επί- ''b'' ορθογώνιο με τετράγωνα πλακάκια ακριβώς, όπου α είναι ο μεγαλύτερος από τους δύο αριθμούς . Αρχικά προσπαθούμε να καλύψουμε το ορθογώνιο με ''b'' -by- ''b'' τετράγωνα πλακάκια. ωστόσο, αυτό αφήνει ένα ''r''<sub>0</sub>-by-''b''ορθογώνιο ακάλυπτο, όπου ''r''<sub>0</sub>&nbsp;<&nbsp;''b''. Στη συνέχεια προσπαθούμε να καλύψουμε το υπόλοιπο ορθογώνιο με ''r''<sub>0</sub>-by-''r''<sub>0</sub> τετράγωνα πλακάκια. Αυτό αφήνει ένα δδεύτερο ακάλυπτο ορθογώνιο ''r''<sub>1</sub>-by-''r''<sub>0</sub>,το οποίο προσπαθούμε να καλυψουμε με τετράγωνα πλακάκια χρησιμοποιώντας ''r''<sub>1</sub>-by-''r''<sub>1</sub> και ούτω καθεξής. Η διαδικασία τελειώνει όταν δεν υπάρχει ακάλυπτο ορθογώνιο, δηλαδή, όταν τα τετράγωνα πλακίδια καλύψουν ακριβώς, το ορθογώνιο που απέμεινε από το προηγούμενο βήμα. Το μήκος των πλευρών του μικρότερου τετράγωνου πλακιδίου είναι ο ΜΚΔ των διαστάσεων του αρχικού ορθογωνίου. Για παράδειγμα, το μικρότερο τετραγωνικό πλακίδιο στο παρακείμενο σχήμα είναι 21-επί-21 (φαίνεται σε κόκκινο), και το 21 είναι ο ΜΚΔ των 1071 και 462, οι διαστάσεις του αρχικού ορθογωνίου (που φαίνεται στο πράσινο).

=== Ευκλείδεια διαίρεση ===

Σε κάθε βήμα ''k'', ο Ευκλείδειος αλγόριθμος υπολογίζει το πηλίκο ''q''<sub>''k''</sub> και το υπόλοιπο ''r''<sub>''k''</sub> από δύο αριθμούς ''r''<sub>''k''−1</sub> and ''r''<sub>''k''−2</sub>

: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>

όπου η [[δύναμη]] του ''r''<sub>''k''</sub> είναι αυστηρά μικρότερη από εκείνη του ''r''<sub>''k''−1</sub>. Το θεώρημα που διέπει τον ορισμό της [[Ευκλείδεια διαίρεση|Ευκλείδειας διαίρεσης]] εξασφαλίζει ότι ένα τέτοιο πηλίκο και υπόλοιπο πάντα υπάρχουν και είναι μοναδικά.<ref name="Cohn_1962">{{Harvnb|Cohn|1962|pp=104–110}}</ref>

Στην αρχική έκδοση του αλγορίθμου του Ευκλείδη, το πηλίκο και το υπόλοιπο βρίσκονται από επανειλημμένη αφαίρεση, Δηλαδή, ''r''<sub>''k''−1</sub> αφαιρείται από ''r''<sub>''k''−2</sub> επανειλημμένα έως ότου το υπόλοιπο ''r''<sub>''k''</sub> είναι μικρότερο από ''r''<sub>''k''−1</sub>. Μετά από αυτό ''r''<sub>''k''</sub> και ''r''<sub>''k''−1</sub> ανταλλάσσονται και η διαδικασία επαναλαμβάνεται.Η ευκλείδεια διαίρεση μειώνει όλα τα βήματα μεταξύ δύο ανταλλαγών σε ένα ενιαίο βήμα, το οποίο είναι κατά συνέπεια πιο αποτελεσματικό. Επιπλέον, δεν είναι το πηλίκο που απαιτείται, έτσι μπορεί κανείς να αντικαταστήσει την Ευκλείδεια διαίρεση με τη [[modulo αριθμητική]], η οποία δίνει μόνο το υπόλοιπο. Έτσι, η επανάληψη του Ευκλείδειου αλγορίθμου γίνεται απλά

:''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>.

===Υλοποιήσεις===

Υλοποιήσεις του αλγορίθμου μπορεί να εκφραστούν σε [[ψευδοκώδικας|ψευδοκώδικα]].Για παράδειγμα,η μέθοδος που στηρίζεται σε διαιρέσεις μπορεί να [[προγραμματισμός|προγραμματιστεί]] ως <ref>Knuth, pp. 319–320.</ref>

 '''function''' gcd(a, b)
     '''while''' b ≠ 0
        t := b
        b := a '''mod''' t
        a := t
     '''return''' a

Στην αρχή της ''k'' επανάληψης, η μεταβλητή ''Β'' κατέχει το τελευταίο υπόλοιπο ''r''<sub>''k''−1</sub>, ενώ η μεταβλητή ''a'' κατέχει το προηγούμενό του, ''r''<sub>''k''−2</sub>. Το στάδιο ''b'' := ''a'' mod ''b'' είναι ισοδύναμο με τον ανωτέρω τύπο αναδρομής ''r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>. Η [[ψευδομεταβλητή]] ''t'' κρατά την τιμή της ''r''<sub>''k''−1</sub>, ενώ το επόμενο υπόλοιπο ''r''<sub>''k''</sub> υπολογίζεται συγχρόνως. Στο τέλος του βρόχου επανάληψης, η μεταβλητή ''b'' κατέχει το υπόλοιπο ''r''<sub>''k''</sub> , ενώ η μεταβλητή ''a'' κατέχει το προηγούμενό του , ''r''<sub>''k''−1</sub>.

Στην μέθοδο που βασίζεται στην αφαίρεση, που ήταν και η αρχική έκδοση του αλγορίθμου του Ευκλείδη, ο υπολογισμός του υπόλοιπου (''b''&nbsp;=&nbsp;''a'' mod ''b'') αντικαθίσταται από την επανειλημμένη αφαίρεση.<ref>Knuth, pp. 318–319.</ref> Αντίθετα με την βασισμένη στη διαίρεση έκδοση, η οποία λειτουργεί με αυθαίρετους ακέραιους ως πρωταρχικό δεδομένο, η βασισμένη στην αφαίρεση έκδοση  υποθέτει ότι η είσοδος αποτελείται από θετικούς ακέραιους και σταματά όταν ''a'' = ''b'':

 '''function''' gcd(a, b)
     '''while''' a ≠ b
         '''if''' a > b
            a := a − b
         '''else'''
            b := b − a
     '''return''' a

Οι μεταβλητές ''a'' και ''b'' εναλλάσονται διατηρώντας τα προηγούμενα υπόλοιπα ''r''<sub>''k''−1</sub> και ''r''<sub>''k''−2</sub>. Υποθέτοντας ότι ''a'' είναι μεγαλύτερο από ''b'' στην αρχή μιας επανάληψης, τότε ''a'' ισούται με ''r''<sub>''k''−2</sub>, εφόσον ''r''<sub>''k''−2</sub> > ''r''<sub>''k''−1</sub>. Κατά τη διάρκεια της επανάληψη του βρόχου, το ''a'' μειώνεται κατά πολλαπλάσια του προηγούμενου υπολοίπου ''b'' έως ότου ''a'' είναι μικρότερο από το ''b''. Τότε το ''a'' είναι το επόμενο υπόλοιπο ''r''<sub>''k''</sub>. Τότε το ''b'' μειώνεται κατά πολλαπλάσια του ''a'' έως ότου είναι πάλι μικρότερο από ''a'', δίνοντας το επόμενο υπόλοιπο ''r''<sub>''k''+1</sub>, και ούτω καθεξής.

Η αναδρομική έκδοση<ref>{{Harvnb|Stillwell|1997|p=14}}</ref> βασίζεται στην ισότητα των  ΜΚΔ των διαδοχικών υπολοίπων και τη συνθήκη τερματισμού ΜΚΔ(''r''<sub>''N''−1</sub>,&nbsp;0)&nbsp;=&nbsp;''r''<sub>''N''−1</sub>.

 '''function''' gcd(a, b)
     '''if''' b = 0
        '''return''' a
     '''else'''
        '''return''' gcd(b, a '''mod''' b)

Για παράδειγμα, ο ΜΚΔ(1071,&nbsp;462) υπολογίζεται από τον αντίστοιχο ΜΚΔ(462,&nbsp;1071&nbsp;mod&nbsp;462)&nbsp;= ΜΚΔ(462,&nbsp;147) Ο τελευταίος ΜΚΔ υπολογίζεται από τον ΜΚΔ(147,&nbsp;462&nbsp;mod&nbsp;147)&nbsp;=&nbsp;ΜΚΔ(147,&nbsp;21) ο οποίος με τη σειρά του υπολογίζεται από τον ΜΚΔ (21,&nbsp;147&nbsp;mod&nbsp;21)&nbsp;=&nbsp;ΜΚΔ (21,&nbsp;0)&nbsp;=&nbsp;21.

===Μέθοδος των μικρότερων απόλυτων υπολοίπων ===

Σε μια άλλη εκδοχή του αλγορίθμου του Ευκλείδη, το πηλίκο σε κάθε βήμα αυξάνεται κατά ένα, αν το προκύπτον αρνητικό υπόλοιπο είναι μικρότερο σε μέγεθος από το τυπικό θετικό υπόλοιπο.<ref name="Ore_least_abs_remainders" >{{Harvnb|Ore|1948|p=43}}</ref><ref name="Stewart_1964">{{cite book|title=Theory of Numbers|first=|author=Stewart BM|publisher=Macmillan|isbn=|year=1964|edition=2nd|location=New York|page=|pages=43–44|quote=}}</ref> Προηγουμένως, η εξίσωση

: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>

με την υπόθεση ότι |''r''<sub>''k''−1</sub>|&nbsp;>&nbsp;''r''<sub>''k''</sub>&nbsp;>&nbsp;0. Ωστόσο, ένα εναλλακτικό αρνητικό υπόλοιπο ''e''<sub>''k''</sub> μπορεί να υπολογιστεί:

: ''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> + 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>
αν ''r''<sub>''k''−1</sub>&nbsp;>&nbsp;0 ή
: ''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> &minus; 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>
αν ''r''<sub>''k''−1</sub>&nbsp;<&nbsp;0.

Αν |''e''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''</sub>|, τότε ''r''<sub>''k''</sub> αντικαθίσταται από το ''e''<sub>''k''</sub>.  Ως |''r''<sub>''k''&minus;1</sub>| = ''r''<sub>''k''</sub>&nbsp;&minus;&nbsp;''e''<sub>''k''</sub>, αυτό το νέο ''r''<sub>''k''</sub>  ικανοποιεί

:|''r''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''&minus;1</sub>|&nbsp;/&nbsp;2.

Ο [[Λέοπολντ Κρόνεκερ]] έχει δείξει ότι αυτή η έκδοση απαιτεί το μικρότερο αριθμό των βημάτων οποιασδήποτε έκδοσης του αλγορίθμου του Ευκλείδη.<ref name="Ore_least_abs_remainders" /><ref name="Stewart_1964" />

== Ιστορική εξέλιξη ==

[[File:Euklid.jpg|thumb|alt="Depiction of Euclid as a bearded man holding a pair of dividers to a tablet."|Ο Ευκλείδειος αλγόριθμος μάλλον επινοήθηκε αιώνες πριν από τον Ευκλείδη , που παρουσιάζεται εδώ.]]
Ο Ευκλείδειος αλγόριθμος είναι ένας από τους παλαιότερους αλγορίθμους ακόμα σε κοινή χρήση.<ref name="Knuth, p. 318">Knuth, p. 318.</ref>  Φαίνεται στα ''[[Στοιχεία]]'' του Ευκλείδη (περ. 300 π.Χ.), και συγκεκριμένα στο βιβλίο 7 (Προτάσεις 1-2) και βιβλίο 10 (Προτάσεις 2-3). Στο βιβλίο 7, ο αλγόριθμος είναι σχεδιασμένος για ακέραιους, ενώ στο βιβλίο 10, δεν έχει διατυπωθεί για μήκη τμημάτων γραμμής. (Στη σύγχρονη χρήση, θα έλεγε κανείς ότι διατυπώθηκε εκεί για [[πραγματικός αριθμός|πραγματικούς αριθμούς]]. Όμως, μήκη, εμδαδά, και όγκοι,που αντιμετωπίστηκαν ως πραγματικοί αριθμοί στη σύγχρονη χρήση, δεν μετρούνται στις ίδιες μονάδες και δεν υπάρχει καμία φυσική μονάδα μήκους, εμβαδού, ή ο όγκου, ενώ η έννοια των πραγματικών αριθμών ήταν άγνωστη εκείνη την εποχή.) Ο τελευταίος αλγόριθμος είναι γεωμετρικός. Ο ΜΚΔ των δύο μηκών ''α'' και ''β'' αντιστοιχεί στο μέγιστο μήκος ''γ'' που μετρά το ''α'' και ''β'' ομοιόμορφα, με άλλα λόγια, τα μήκη ''α'' και ''β'' είναι και τα δύο ακέραια πολλαπλάσια του μήκους &nbsp;''g''..

Ο αλγόριθμος μάλλον δεν ανακαλύφθηκε από τον [[Ευκλείδης|Ευκλείδη]], που συγκέντρωσε τα αποτελέσματα από προηγούμενους μαθηματικούς στο έργο του ''Στοιχεία''.<ref name="Weil_1983">{{cite book | author = [[André Weil|Weil A]] | year = 1983 | title = Number Theory | publisher = Birkhäuser | location = Boston | isbn = 0-8176-3141-0 | pages = 4–6}}</ref><ref name="Jones_1994">{{cite book | author = Jones A | year = 1994 | chapter = Greek mathematics to AD 300 | title = Companion encyclopedia of the history and philosophy of the mathematical sciences | publisher = Routledge | location = New York | isbn = 0-415-09238-8 | pages = 46–48}}</ref> Ο μαθηματικός και ιστορικός [[BL van der Waerden]] ισχυρίζεται ότι το Βιβλίο 7 προέρχεται από ένα βιβλίο σχετικά με τη [[θεωρία αριθμών]] που γράφτηκε από μαθηματικούς στη σχολή του [[Πυθαγόρας|Πυθαγόρα]].<ref name="van_der_Waerden_1954">{{cite book | author = [[Bartel Leendert van der Waerden|van der Waerden BL]] | year = 1954 | title = Science Awakening | url = https://archive.org/details/scienceawakening00waer| series = translated by Arnold Dresden | publisher = P. Noordhoff Ltd | location = Groningen | pages = [https://archive.org/details/scienceawakening00waer/page/114 114]–115}}</ref> Ο αλγόριθμος ήταν πιθανώς γνωστός από τον [[Εύδοξος ο Κνίδιος|Εύδοξο της Κνίδου]] (περίπου 375 π.Χ.).<ref name="Knuth, p. 318"/><ref>{{cite journal | author = von Fritz K | year = 1945 | title = The Discovery of Incommensurability by Hippasus of Metapontum | url = https://archive.org/details/sim_annals-of-mathematics_1945-04_46_2/page/242 | journal = Ann. Math. | volume = 46 | pages = 242–264 | doi = 10.2307/1969021 | jstor = 1969021 | issue = 2}}</ref>  Ο αλγόριθμος μπορεί ακόμη και να είναι προγενέστερος από τον Εύδοξο,<ref>{{cite book | author = [[T. L. Heath|Heath TL]] | year = 1949 | title = Mathematics in Aristotle | url = https://archive.org/details/mathematicsinari0000heat| publisher = Oxford Press | pages = [https://archive.org/details/mathematicsinari0000heat/page/80 80]–83}}</ref><ref>{{cite book | author = [[David Fowler (mathematician)|Fowler DH]] | year = 1987 | title = The Mathematics of Plato's Academy: A New Reconstruction | url = https://archive.org/details/mathematicsofpla0000fowl_h9l3 | publisher = Oxford University Press | location = Oxford | isbn = 0-19-853912-6 | pages = [https://archive.org/details/mathematicsofpla0000fowl_h9l3/page/31 31]–66}}</ref> αν κρίνουμε από τη χρήση του τεχνικού όρου ἀνθυφαίρεσις (αμοιβαία αφαίρεση) στα έργα του Ευκλείδη και του Αριστοτέλη.<ref>{{cite journal | author = Becker Ο | year = 1933 | title = Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid | volume = 2 | pages = 311–333 | journal = Quellen und Studien zur Geschichte der Mathematik B}}</ref>

Αιώνες αργότερα, ο αλγόριθμος του Ευκλείδη ανακαλύφθηκε ανεξάρτητα τόσο στην [[Ινδία]] όσο και στην [[Κίνα]],<ref name="Stillwell, p. 31">{{Harvnb|Stillwell|1997|p=31}}</ref> κυρίως για την επίλυση [[διοφαντική εξίσωση|διοφαντικών εξισώσεων]] που προκύπτουν στην αστρονομία και την δημιουργία ακριβών ημερολογίων. Στα τέλη του 5ου αιώνα, ο Ινδός μαθηματικός και αστρονόμος [[Αριαμπάτα]] περιέγραψε τον αλγόριθμο ως «κονιοποιητή»,<ref name="Tattersall, p. 70">{{Harvnb|Tattersall|2005|p=70}}</ref> ίσως λόγω της αποτελεσματικότητάς του στην επίλυση διοφαντικών εξισώσεων .<ref>{{Harvnb|Rosen|2000|pp=86–87}}</ref> Παρά το γεγονός ότι μια ειδική περίπτωση του [[Κινέζικου θεωρήματος των υπολοίπων]] είχε ήδη περιγραφεί από τον Κινέζο μαθηματικό και αστρονόμο [[Sun Tzu (mathematician)|Sun Tzu]],<ref>{{Harvnb|Ore|1948|pp=247–248}}</ref>  η γενική λύση δόθηκε στη δημοσιότητα από τον [[Qin Jiushao]] το 1247 στο βιβλίο του ''Shushu Jiuzhang'' (數書九章 [[Mathematical Treatise in Nine Sections]]).<ref>{{Harvnb|Tattersall|2005|pp=72, 184–185}}</ref> Ο Ευκλείδειος αλγόριθμος περιγράφηκε για πρώτη φορά στην Ευρώπη στη δεύτερη έκδοση του [[Claude Gaspard Bachet de Méziriac|Bachet's]] ''Problèmes plaisants et délectables'' (''Ευχάριστα και απολαυστικά προβλήματα'', 1624) <ref name="Tattersall, p. 70"/> Στην Ευρώπη, επίσης χρησιμοποιήθηκε για την επίλυση διοφαντικών εξισώσεων  και στην ανάπτυξη [[συνεχών κλασμάτων]]. Ο [[γενικευμένος Ευκλείδειος αλγόριθμος]], δόθηκε στη δημοσιότητα από τον Άγγλο μαθηματικό [[Nicholas Saunderson]], ο οποίος τον απέδωσε στον [[Roger Cotes]] ως αποτελεσματική μέθοδο για τον υπολογισμό συνεχών κλασμάτων.<ref>{{Harvnb|Tattersall|2005|pp=72–76}}</ref>

Τον 19ο αιώνα, ο Ευκλείδειος αλγόριθμος οδήγησε στην ανάπτυξη των νέων συστημάτων αριθμών, όπως οι [[Gaussian ακέραιοι]] και οι [[ακέραιοι του Eisenstein]] . Το 1815, ο [[Carl Friedrich Gauss|Carl Gauss]] χρησιμοποίησε τον Ευκλείδειο αλγόριθμο για να αποδείξει τη μοναδική παραγοντοποίηση των [[Gaussian ακεραίων]], μολονότι το έργο του εκδόθηκε για πρώτη φορά το 1832.<ref name="Gauss_1832" /> Ο Gauss ανάφερε τον αλγόριθμο του στο ''[[Disquisitiones Arithmeticae]]'' (δημοσιεύθηκε 1801), αλλά μόνο ως μια μέθοδο για συνεχή κλάσματα.<ref name="Stillwell, p. 31"/> Ο [[Πέτερ Γκούσταφ Λεζέν Ντίριχλετ|Πέτερ Γκούσταβ Λεζέν Ντίριχλετ]] φαίνεται να ήταν ο πρώτος που περιέγραψε την Ευκλείδειο αλγόριθμο ως βάση για ένα μεγάλο μέρος της θεωρίας αριθμών.<ref>{{Harvnb|Stillwell|1997|pp=31–32}}</ref>Ο Lejeune Dirichlet τόνισε ότι πολλά αποτελέσματα της θεωρίας αριθμών, όπως η μοναδική παραγοντοποίηση, θα ίσχυαν και για οποιοδήποτε άλλο σύστημα των αριθμών στους οποίους ο Ευκλείδειος αλγόριθμος θα μπορούσε να εφαρμοστεί.<ref>{{Harvnb|Dirichlet|1894|pp=29–31}}</ref>Οι διαλέξεις του Lejeune Dirichlet για τη θεωρία αριθμών επεξεργάστηκαν και επεκτάθηκαν από τον [[Richard Dedekind]] , ο οποίος χρησιμοποίησε τον αλγόριθμο του Ευκλείδη για τη μελέτη των [[αλγεβρικός ακέραιαος|αλγεβρικών ακέραιων]] , ένα νέο γενικό τύπο αριθμών. Για παράδειγμα, Dedekind ήταν ο πρώτος που απέδειξε το [[θεώρημα του fermat για το άθροισμα των τετραγώνων δύο αριθμών]] χρησιμοποιώντας τη μοναδική παραγοντοποίηση των Gaussian ακέραιων.<ref>[[Richard Dedekind]] in {{Harvnb|Dirichlet|loc=Supplement XI|1894}}</ref> Ο Dedekind επίσης όρισε την έννοια της [[Ευκλείδειας δομής]], ένα σύστημα αριθμών στο οποίο μια γενικευμένη εκδοχή του Ευκλείδειου αλγόριθμου μπορεί να οριστεί (όπως περιγράφεται κατωτέρω [[ευκλείδεις δομές]]). Στις τελευταίες δεκαετίες του 19ου αιώνα, ωστόσο, ο Ευκλείδειος αλγόριθμος σταδιακά υποκαταστάθηκε από την πιο γενική θεωρία του Dedekind των [[ιδανικών]] ([[θεωρία δακτυλίων]]).<ref>{{Harvnb|Stillwell|2003|pp=41–42}}</ref>

Άλλες εφαρμογές του αλγορίθμου του Ευκλείδη αναπτύχθηκαν τον 19ο αιώνα. Το 1829,ο [[Jacques Charles François Sturm|Charles Sturm]] έδειξε ότι ο αλγόριθμος ήταν χρήσιμος στη μέθοδο [[Sturm's theorem|Sturm chain]] για την εύρεση των πραγματικών ριζών των πολυωνύμων σε οποιοδήποτε διάστημα.<ref>{{cite journal | author = Sturm C | year = 1829 | title = Mémoire sur la résolution des équations numériques | journal = Bull. des sciences de Férussac | volume = 11 | pages = 419–422}}</ref>

Ο Ευκλείδιος αλγόριθμος ήταν ο πρώτος [[ακέραιος αλγόριθμος]] , ο οποίος είναι μια μέθοδος για την εύρεση ακέραιων σχέσεων μεταξύ ανάλογων πραγματικών αριθμών. Αρκετοί νέοι ακέραιοι αλγόριθμοι έχουν αναπτυχθεί τα τελευταία χρόνια, όπως ο αλγόριθμος [[Αλγόριθμος Ferguson–Forcade|Ferguson–Forcade]]  (1979) του [[Helaman Ferguson]] και RW Forcade,<ref>{{MathWorld|urlname=IntegerRelation|title=Integer Relation}}</ref> και οι παρεμφερείς του,ο [[δια βίου μάθησης αλγόριθμος]],ο [[HJLS αλγόριθμος]] , και ο [[αλγόριθμος PSLQ]].<ref>{{cite journal | author = Peterson I | date = 12 August 2002 | title = Jazzing Up Euclid's Algorithm | journal = ScienceNews | url=http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm}}</ref><ref>{{cite journal | author = Cipra BA | title = The Best of the 20th Century: Editors Name Top 10 Algorithms | journal = SIAM News | volume = 33 | date = 16 May 2000 | publisher = [[Society for Industrial and Applied Mathematics]] | issue = 4 | url = http://amath.colorado.edu/resources/archive/topten.pdf | accessdate = 2013-06-07 | archiveurl = https://web.archive.org/web/20090407080904/http://amath.colorado.edu/resources/archive/topten.pdf | archivedate = 2009-04-07 | url-status = dead }}</ref>

Το 1969,οι Cole και Davie ανέπτυξαν ένα παιχνίδι δύο παικτών που  βασίζεται στον Ευκλείδειο αλγόριθμο, που ονομάζεται ''The Game of Euclid''<ref>{{cite journal | author = Cole AJ, Davie AJT | year = 1969 | title = A game based on the Euclidean algorithm and a winning strategy for it | url = https://archive.org/details/sim_mathematical-gazette_1969-12_53_386/page/354 | journal = Math. Gaz. | volume = 53 | pages = 354–357 | doi = 10.2307/3612461 | jstor = 3612461 | issue = 386}}</ref> το οποίο έχει μια βέλτιστη στρατηγική.<ref>{{cite journal | doi = 10.2307/2689037 | author = Spitznagel EL | year = 1973 | title = Properties of a game based on Euclid's algorithm | jstor = 2689037 | journal = Math. Mag. | volume = 46 | issue = 2 | pages = 87–92}}</ref> Οι παίκτες ξεκινούν με δύο σωρούς από ''α'' και ''β'' πέτρες. Οι παίκτες αναλαμβάνουν εκ περιτροπής την αφαίρεση ''m'' πολλαπλασίων του μικρότερου σωρού από το μεγαλύτερο. Ετσι, αν οι δύο σωροί αποτελούνται από ''χ'' και ''y'' πέτρες, όπου το ''Χ'' είναι μεγαλύτερο από το ''y'' , ο επόμενος παίκτης μπορεί να ελαττώσει το μεγαλύτερο  σωρό από ''x'' πέτρες σε ''x'' − ''my'' πέτρες, εφ' όσον ο τελευταίος είναι ένας μη αρνητικός ακέραιος αριθμός. Ο νικητής είναι ο πρώτος παίκτης που θα έχει ένα σωρό από μηδέν πέτρες.<ref>{{Harvnb|Rosen|2000|p=95}}</ref><ref>{{cite book | author = Roberts J | year = 1977 | title = Elementary Number Theory: A Problem Oriented Approach | publisher = [[MIT Press]] | location = Cambridge, MA | isbn = 0-262-68028-9 | pages = [https://archive.org/details/Elementary_00_Robe/page/1 1–8] | url-access = registration | url = https://archive.org/details/Elementary_00_Robe/page/1 }}</ref>

==Μαθηματικές εφαρμογές==

===Ταυτότητα Bézout===

Η [[ταυτότητα του Bézout]]  δηλώνει ότι ο μεγιστος κοινός διαιρέτης ''g'' δύο ακεραίων ''a'' και ''b'' μπορεί να παρασταθεί ως ένα γραμμικό άθροισμα των δύο αρχικών αριθμών ''a'' και ''b'' .<ref>{{cite book | author = Jones GA, Jones JM | year = 1998 | chapter = Bezout's Identity | title = Elementary Number Theory | publisher = Springer-Verlag | location = New York | pages = 7–11}}</ref>Με άλλα λόγια, είναι πάντα δυνατό να βρεθούν ακέραιοι ''s'' και ''t'' τέτοιοι ώστε . ''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb''.<ref>{{Harvnb|Rosen|2000|p=81}}</ref><ref>{{Harvnb|Cohn|1962|p=104}}</ref>

Οι ακέραιοι ''s'' και ''t'' μπορούν να υπολογιστούν από τα πηλίκα ''q''<sub>0</sub>, ''q''<sub>1</sub>, κλπ. αντιστρέφοντας τη σειρά των εξισώσεων στον αλγόριθμο του Ευκλείδη.<ref>{{Harvnb|Rosen|2000|p=91}}</ref> Αρχίζοντας με την "επόμενη προς τα τελευταία εξίσωση",το ''g'' μπορεί να εκφραστεί συναρτήσει του πηλίκου  ''q''<sub>''N''−1</sub> και των δύο προηγούμενων υπολοίπων, ''r''<sub>''N''−2</sub> and ''r''<sub>''N''−3</sub>. .

: ''g'' = ''r''<sub>''N''−1</sub> = ''r''<sub>''N''−3</sub> − ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub>

Τα δύο αυτά υπόλοιπα μπορούν  ομοίως να εκφράζονται συναρτήσει των πηλίκων τους και των προηγούμενων υπολοίπων τους

: ''r''<sub>''N''−2</sub> = ''r''<sub>''N''−4</sub> − ''q''<sub>''N''−2</sub> ''r''<sub>''N''−3</sub>
: ''r''<sub>''N''−3</sub> = ''r''<sub>''N''−5</sub> − ''q''<sub>''N''−3</sub> ''r''<sub>''N''−4</sub>.

Αντικαθιστώντας αυτές τις φόρμουλες για ''r''<sub>''N''−2</sub> και ''r''<sub>''N''−3</sub> στην πρώτη εξίσωση εκφράζουν το ''g'' ως γραμμικό άθροισμα των υπολοίπων ''r''<sub>''N''−4</sub> and ''r''<sub>''N''−5</sub> . Η διαδικασία της αντικατάστασης υπολοίπων από τους τύπους που περιλαμβάνουν τα προηγούμενα τους υπόλοιπα μπορεί να συνεχίζεται έως ότου οι αρχικοί αριθμοί ''α'' και ''β'' καταλήγουν να είναι:
: ''r''<sub>2</sub> = ''r''<sub>0</sub> − ''q''<sub>2</sub> ''r''<sub>1</sub>
: ''r''<sub>1</sub> = ''b'' − ''q''<sub>1</sub> ''r''<sub>0</sub>
: ''r''<sub>0</sub> = ''a'' − ''q''<sub>0</sub> ''b''.

Αφού όλα τα υπολοιπα έχουν ''r''<sub>0</sub>, ''r''<sub>1</sub>,, κλπ. έχουν υποκατασταθεί, η τελική εξίσωση εκφράζει το ''g'' ως ένα γραμμικό άθροισμα των ''Α'' και ''Β'' :''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb''.Η [[ταυτότητα του bezout]] , και ως εκ τούτου  προηγούμενος αλγόριθμος, μπορεί να γενιεκυτεί και στις [[ευκλείδειες δομές]].

=== Πρωταρχικά ιδανικά και συναφή προβλήματα ===

Η ταυτότητα Bézout παρέχει ακόμη  τον ορισμό του μέγιστου κοινού διαιρέτη ''g'' δύο αριθμών ''a'' και ''b'' .<ref name="Leveque_p33" >{{Harvnb|LeVeque|1996|p=33}}</ref> Ας εξετάσουμε το σύνολο όλων των αριθμών  ''ua''&nbsp;+&nbsp;''vb'', όπου ''u'' και ''v'' είναι δύο οποιοιδήποτε ακέραιοι. Δεδομένου ότι και ο ''a'' και ο ''b'' διαιρούνται  από  τον ''g'', κάθε αριθμός του  συνόλου  είναι διαιρετός από τον  ''g''. Με άλλα λόγια, κάθε αριθμός του συνόλου είναι ένα ακέραιο πολλαπλάσιο του ''g''. Αυτό ισχύει για κάθε κοινό διαιρέτη του ''a'' και ''b''. Ωστόσο, σε αντίθεση με άλλους κοινούς [[Διαιρέτης|διαιρέτες]], ο μέγιστος κοινός διαιρέτης είναι ένα μέλος του συνόλου. Με την ταυτότητα του Bézout, επιλέγοντας''u''&nbsp;=&nbsp;''s'' και''v''&nbsp;=&nbsp;''t'' παίρονουμε τον  ''g''. Ένας μικρότερος κοινός διαιρέτης δεν μπορεί να είναι μέλος του συνόλου, αφού κάθε μέλος του συνόλου πρέπει να διαιρείται από τον  ''g''. Αντιστρόφως, οποιοδήποτε πολλαπλάσιο 'm'' του ''g'' μπορεί να ληφθεί με την επιλογή ''u''&nbsp;=&nbsp;''ms''  και ''v''&nbsp;=&nbsp;''mt'', όπου ''s'' και ''t'' είναι οι ακέραιοι της ταυτότητας Bézout. Αυτό μπορεί να φανεί από τον πολλαπλασιασμό της ταυτότητας Bézout επί ''m'',

: ''mg'' = ''msa'' + ''mtb''.

Ως εκ τούτου, το σύνολο όλων των αριθμών''ua''&nbsp;+&nbsp;''vb'' είναι ισοδύναμο με το σύνολο των πολλαπλασίων ''m'' του ''g''. Με άλλα λόγια, το σύνολο όλων των πιθανών αθροισμάτων των  ακεραίων  πολλαπλασίων  των δύο αριθμών(''a'' και ''b'')  είναι ισοδύναμο με το σύνολο των πολλαπλασίων του ΜΚΔ(''a'', ''b''). Ο ΜΚΔ λέγεται ότι είναι η γεννήτρια του [[Ιδανικό|ιδανικού]] του ''a'' και ''b''. Ο ορισμός αυτός του ΜΚΔ οδήγησε στις σύγχρονες αφηρημένες [[αλγεβρικές έννοιες]] του κύριου ιδεώδους (ένα ιδεώδες που παράγεται από ένα μόνο στοιχείο) και των ακέραιου πεδίου κυριών ιδεωδών (ένα ακέραιο πεδίο στο οποίο κάθε ιδεώδες είναι ένα κύριο ιδεώδες).

Ορισμένα προβλήματα μπορούν να επιλυθούν με αυτό το αποτέλεσμα.<ref>{{Harvnb|Schroeder|2005|p=23}}</ref> Για παράδειγμα, σκεφτείτε δύο κούπες μέτρησης του όγκου ''a'' και ''b''. Με την προσθήκη / αφαίρεση πολλαπλάσιων του πρώτου κυπέλλου και πολλαπλάσιων του δεύτερου κυπέλλου, κάθε όγκος ''ua''&nbsp;+&nbsp;''vb'' μπορεί να μετρηθεί. Οι όγκοι αυτοί είναι όλοι πολλαπλάσιοι του''g''&nbsp;=&nbsp;ΜΚΔ(''a'',&nbsp;''b'').

===Διευρυμένος Ευκλείδειος αλγόριθμος ===

Οι ακέραιοι s και t της ταυτότητας Bézout μπορούν να υπολογιστούν αποδοτικά χρησιμοποιώντας τον διευρυμένο Ευκλείδειο αλγόριθμο . Αυτή η επέκταση προσθέτει δύο αναδρομικές εξισώσεις στον αλγόριθμο του Ευκλείδη [ 58 ]
: ''s''<sub>''k''</sub> = ''s''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''s''<sub>''k''−1</sub>
: ''t''<sub>''k''</sub> = ''t''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''t''<sub>''k''−1</sub>

με τις τιμές έναρξης
: ''s''<sub>−2</sub> = 1, ''t''<sub>−2</sub> = 0
: ''s''<sub>−1</sub> = 0, ''t''<sub>−1</sub> = 1.

Χρησιμοποιώντας αυτή την αναδρομή,οι ακέραιοι Bézout ''s'' και ''t''  δίνονται από τις ''s''&nbsp;=&nbsp;''s''<sub>''N''</sub> και  ''t''&nbsp;=&nbsp;''t''<sub>''N''</sub> , όπου ''Ν'' είναι το βήμα στο οποίο ο αλγόριθμος τερματίζει με ''r''<sub>''N''</sub>&nbsp;=&nbsp;0.

Η ισχύς αυτής της προσέγγισης μπορεί να αποδειχθεί με επαγωγή. Ας υποθέσουμε ότι ο αναδρομικός τύπος  είανι σωστός μέχρι και το βήμα ''k''&nbsp;−&nbsp;1 του αλγορίθμου.Με άλλα λόγια, ας υποθέσουμε ότι
: ''r''<sub>''j''</sub> = ''s''<sub>''j''</sub> ''a'' + ''t''<sub>''j''</sub> ''b''

για όλα τα ''j'' μικρότερα του ''k'' . Το ''k'' στάδιο του αλγορίθμου δίνει την εξίσωση
: ''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''r''<sub>''k''−1</sub>.

Δεδομένου ότι υποθέσαμε ότι  ο αναδρομικός τύπος  είναι σωστός για ''r''<sub>''k''−2</sub> και  ''r''<sub>''k''−1</sub> , μπορούν να εκφραστούν ως προς τις μεταβλητές ''s'' και ''t'' , 
: ''r''<sub>''k''</sub> = (''s''<sub>''k''−2</sub> ''a'' + ''t''<sub>''k''−2</sub> ''b'') − ''q''<sub>''k''</sub>(''s''<sub>''k''−1</sub> ''a'' + ''t''<sub>''k''−1</sub> ''b'').

Αναδιατάσσοντας  αυτήν την εξίσωση παίρνουμε  τον αναδρομικό τύπο για το βήμα ''k'' , όπως απαιτείται
: ''r''<sub>''k''</sub> = ''s''<sub>''k''</sub> ''a'' + ''t''<sub>''k''</sub> ''b'' = (''s''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''s''<sub>''k''−1</sub>) ''a'' + (''t''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''t''<sub>''k''−1</sub>) ''b''.

===Μέθοδος πίνακα ===

Οι ακέραιοι s και t μπορεί επίσης να βρεθεί χρησιμοποιώντας μία ισοδύναμη [[Μέθοδος πίνακα|μέθοδο πίνακα]]. [ 59 ] Η σειρά των εξισώσεων του αλγορίθμου του Ευκλείδη

: ''a'' = ''q''<sub>0</sub> ''b'' + ''r''<sub>0</sub>
: ''b'' = ''q''<sub>1</sub> ''r''<sub>0</sub> + ''r''<sub>1</sub>
: …
: ''r''<sub>''N''−2</sub> = ''q''<sub>''N''</sub> ''r''<sub>''N''−1</sub> + 0

μπορεί να γραφτεί ως προϊόν 2-επί-2 πινάκων  πολλαπλασιάζοντας ένα δισδιάστατο  υπόλοιπο διανύσματος

:<math alt="A series of equations consisting of two-dimensional vectors multiplied by an ever-increasing number of 2-by-2 matrices. The vector a b equals the matrix q sub zero 1 1 0 times the vector b r sub zero. It also equals the matrix q sub zero 1 1 0 times the matrix q sub one 1 1 0 times the vector r sub zero r sub one. Continuing to the last step N of the algorithm, it equals the product of all 2-by-2 matrices of the form q sub i 1 1 0 times the vector r sub N minus one r sub N. The index i ranges from 0 to N and the last remainder r sub N is zero.">
\begin{pmatrix} a \\ b \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_{0} \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \end{pmatrix} =
\cdots =
\prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix}
</math>

Έστω ότι  ''M''  αντιπροσωπεύει το γινόμενο του συνόλου των πινάκων

:<math alt="The 2-by-2 matrix M has four components, m sub 1 1, m sub 1 2, m sub 2 1, and m sub 2 2. It is defined as the product of all 2-by-2 matrices of the form q sub i 1 1 0, where the index i ranges from 0 to N.">
\mathbf{M} = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} =
\prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} q_{N} & 1 \\ 1 & 0 \end{pmatrix}
</math>

Αυτό απλοποιεί την Ευκλείδειο αλγόριθμο  στη μορφή

:<math alt="The two-dimensional vector a b equals the matrix M times the final vector, r sub N minus one zero. The final non-zero remainder is the greatest common divisor g. Therefore, the vector a b equals the matrix M times the vector g zero.">
\begin{pmatrix} a \\ b \end{pmatrix} =
\mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} =
\mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix}
</math>

Για να εκφράσουμε το  ''g'' ως ένα γραμμικό συνδυασμό του  ''a'' και του ''b'' ,και οι δύο πλευρές της εξίσωσης αυτής μπορούν να πολλαπλασιαστούν με τον αντίστροφο του πίνακα  ''Μ'' . [ 59 ] [ 60 ] Η [[ορίζουσα]] του Μ ισούται με −1)<sup>''N''+1</sup> , αφού ισούται  με το γινόμενο των καθοριστικών παραγόντων των πινάκων, καθένα από τα οποία είναι αρνητικά. Δεδομένου ότι ο καθοριστικός παράγοντας του ''Μ'' δεν είναι ποτέ μηδέν, το διάνυσμα των τελευταίων  υπολοίπων μπορεί να επιλυθεί χρησιμοποιώντας τον αντίστροφο του ''Μ''

:<math alt="The two-dimensional vector g 0 equals the inverse of matrix M times the vector a b. This equals minus one to the Nth plus one power, times the matrix with components m sub 2 2, minus m sub 1 2, minus m sub 2 1, and m sub 1 1, times the vector a b.">
\begin{pmatrix} g \\ 0 \end{pmatrix} =
\mathbf{M}^{-1} \begin{pmatrix} a \\ b \end{pmatrix} =
(-1)^{N+1} \begin{pmatrix} m_{22} & -m_{12} \\ -m_{21} & m_{11} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix}
</math>

Δεδομένου ότι η πρώτη εξίσωση δίνει

:''g'' = (−1)<sup>''N''+1</sup> ( ''m''<sub>22</sub> ''a'' − ''m''<sub>12</sub> ''b'')

οι δύο ακέραιοι αριθμοί της ταυτότητας του Bézout είναι ''s''&nbsp;=&nbsp;(−1)<sup>''N''+1</sup>''m''<sub>22</sub> και ''t''&nbsp;=&nbsp;(−1)<sup>''N''</sup>''m''<sub>12</sub> . Η μέθοδος των πινάκων είναι τόσο αποτελεσματική όσο η χρήση του αναδρομικού τύπου, με δύο πολλαπλασιασμούς και δύο προσθέσεις ανά βήμα του Ευκλείδειου αλγορίθμου.

===Λήμμα του Ευκλείδη και μοναδική παραγοντοποίηση===

Η ταυτότητα Bézout είναι απαραίτητη για πολλές εφαρμογές του αλγορίθμου του Ευκλείδη, όπως αποδεικνύουν οι [[μοναδικές παραγοντοποιήσεις]] αριθμών σε πρώτους παράγοντες.<ref>Stark 1978 , σελ. 26-36</ref>  Για να φανεί αυτό, ας υποθέσουμε ότι ένας αριθμός ''L'' μπορεί να γραφτεί ως γινόμενο δύο παραγόντων ''u'' και ''v'' , δηλαδή , ''L''&nbsp;=&nbsp;''uv'' . Αν κάποιος άλλος αριθμός ''w'' διαιρεί επίσης τον ''L'' , αλλά είναι πρώτοι μεταξύ τους με τον ''u'' , τότεο ''w'' πρέπει να διαιρέσει τον ''ν'' ,σύμφωνα με την επόμενη πρόταση: Εάν ο μέγιστος κοινός διαιρέτης των ''u'' και ''w'' είναι 1, τότε οι ακέραιοι ''s'' και ''t'' μπορεί να βρεθούν, έτσι ώστε

: 1 = ''su'' + ''tw''

από την ταυτότητα του Bézout . Πολλαπλασιάζοντας και τις δύο πλευρές με ''v'' παίρνουμε τη σχέση

: ''v'' = ''suv'' + ''twv'' = ''sL'' + ''twv''

Αφού το ''w'' διαιρεί τους δύο όρους στη δεξιά πλευρά, θα πρέπει επίσης να διαιρεί και την αριστερή πλευρά, ''v'' . Το αποτέλεσμα είναι γνωστό ως [[λήμμα του Ευκλείδη]].<ref name="α β Ore 1948 , p. 44">α β Ore 1948 , p. 44</ref>   Συγκεκριμένα, αν ένας πρώτος αριθμός διαιρεί το ''L'' , τότε θα πρέπει να διαιρεί τουλάχιστον έναν παράγοντα του ''L'' . Αντιστρόφως, εάν ένας αριθμός ''w'' είναι πρώτος με κάθε ένα από μια σειρά αριθμών ''a''<sub>1</sub>, ''a''<sub>2</sub>, …, ''a''<sub>''n''</sub>, τότε ο ''w'' είναι επίσης πρώτος με το γινόμενό τους, ''a''<sub>1</sub>&nbsp;×&nbsp;''a''<sub>2</sub>&nbsp;×&nbsp;…&nbsp;×&nbsp;''a''<sub>''n''</sub>.<ref name="α β Ore 1948 , p. 44"/>   Το λήμμα του Ευκλείδη θέλει να αποδείξει ότι κάθε αριθμός παραγοντοποιήται σε πρώτους αριθμούς.<ref>Stark 1978 , σελ. 281-292</ref>  Για να το δούμε αυτό, ας υποθέσουμε το αντίθετο, ότι υπάρχουν δηλαδή δύο ανεξάρτητες παραγοντοποιήσεις της ''L'' σε ''m'' και ''n'' πρώτους όρους, αντίστοιχα,

: ''L'' = ''p''<sub>1</sub>''p''<sub>2</sub>…''p''<sub>''m''</sub> = ''q''<sub>1</sub>''q''<sub>2</sub>…''q''<sub>''n''</sub> .

Δεδομένου ότι κάθε πρώτος αριθμός ''p'' διαιρεί τον ''L'' σύμφωνα με την υπόθεση, θα πρέπει ακόμα να διαιρεί έναν από τους όρους ''q''. Δεδομένου ότι κάθε q είναι πρώτος αριθμός , πρέπει να ισχύει ότι ''p''&nbsp;=&nbsp;''q'' . Διαιρούμενοι διαρκώς με p όρους προκύπτει ότι κάθε ''p'' έχει έναν ίσο ομόλογο ''q'' .Οι δύο βασικές παραγοντοποιήσεις είναι πανομοιότυπες, με εξαίρεση τη σειρά τους. Η μοναδική παραγοντοποίηση των αριθμών σε πρώτους αριθμούς έχει πολλές εφαρμογές σε μαθηματικές αποδείξεις, όπως φαίνεται παρακάτω.

===Γραμμικές  Διοφαντικές εξισώσεις===

[[Διοφαντική εξίσωση|Διοφαντικές εξισώσεις]] είναι εξισώσεις στις οποίες οι λύσεις περιορίζονται σε ακέραιους αριθμούς.Πήραν το όνομά τους από τον μαθηματικό του 3ου αιώνα Αλέξανδρο [[Διόφαντος]].<ref>Rosen 2000 , σελ. 119-125</ref> Μια τυπική γραμμική Διοφαντική εξίσωση αναζήτησης ακεραίων ''x'' και ''y'' είναι η <ref>Schroeder 2005 , σελ. 106-107</ref> 
: ''ax'' + ''by'' = ''c''
 
όπου ''a'' , ''b'' και ''c'' είναι ακέραιοι αριθμοί . Αυτό μπορεί να γραφεί ως εξίσωση για ''x'' στην [[modular αριθμητική]] 
: ''ax'' &equiv; ''c'' mod ''b''. 
Έστω ''g'' είναι ο μέγιστος κοινός διαιρέτης των ''a'' και'' b'' . Και οι δύο όροι στη σχέση ''ax''&nbsp;+&nbsp;''by''  διαιρούνται με το ''g''.Ως εκ τούτου, ο ''c'' πρέπει επίσης να διαιρείται με το ''g'' , διαφορετικά η εξίσωση δεν έχει λύσεις. Διαιρώντας και τις δύο πλευρές με ''c'' /'' g'' , η εξίσωση μπορεί να μικρύνει με την ταυτότητα του Bezout
: ''sa'' + ''tb'' = ''g'' ,

όπου ''s'' και ''t'' μπορεί να βρεθούν από τον διευρυμένο Ευκλείδειο αλγόριθμο.<ref>Schroeder 2005 , σελ. 108-109</ref> Αυτό παρέχει μία λύση για το Διοφαντική εξίσωση, ''x''<sub>1</sub>&nbsp;=&nbsp;''s'' (''c''/''g'') και ''y''<sub>1</sub>&nbsp;=&nbsp;''t'' (''c''/''g''). . Σε γενικές γραμμές, μια γραμμική Διοφαντική εξίσωση δεν έχει καμία λύση ή έχει άπειρο αριθμό λύσεων.<ref>Rosen 2000 , σελ. 120-121</ref> Για να βρούμε το τελευταίο, εξετάζουμε δύο λύσεις, (''x''<sub>1</sub>,&nbsp;''y''<sub>1</sub>) και (''x''<sub>2</sub>,&nbsp;''y''<sub>2</sub>)

: ''ax''<sub>1</sub> + ''by''<sub>1</sub> = ''c'' = ''ax''<sub>2</sub> + ''by''<sub>2</sub>

ή ισοδύναμα

: ''a''(''x''<sub>1</sub> − ''x''<sub>2</sub>) = ''b''(''y''<sub>2</sub> − ''y''<sub>1</sub>). 
 
Ως εκ τούτου, η μικρότερη διαφορά μεταξύ δύο ''x'' λύσεων είναι ''b'' / ''g'' , ενώ η μικρότερη διαφορά μεταξύ δύο ''y'' λύσεων είναι ''a'' / ''g'' . Ετσι, οι λύσεις μπορούν να εκφραστούν ως 
:''x'' = ''x''<sub>1</sub> − ''bt''/''g''
 
:''y'' = ''y''<sub>1</sub> + ''at''/''g''.
 
Επιτρέποντας την τιμή του ''t'' να ποικίλλει σε όλους τους πιθανούς ακέραιους, μια άπειρη οικογένεια λύσεων μπορεί να παράγεται από ένα μόνο διάλυμα (''x''<sub>1</sub>,&nbsp;''y''<sub>1</sub>) . Εάν οι λύσεις απαιτούνται να είναι θετικοί ακέραιοι (''x''&nbsp;>&nbsp;0,&nbsp;''y''&nbsp;>&nbsp;0), μόνο ένας πεπερασμένος αριθμός λύσεων μπορεί να είναι δυνατός. Αυτός ο περιορισμός των αποδεκτών λύσεων επιτρέπει συστήματα Διοφαντικών εξισώσεων να επιλύονται με περισσότερους αγνώστους <ref>Stark 1978 , p. 47</ref>.Αυτό είναι αδύνατο για ένα [[σύστημα γραμμικών εξισώσεων]] , όταν οι λύσεις μπορεί να είναι ένας οποιοσδήποτε [[πραγματικός αριθμός]].

=== Πολλαπλασιαστικά αντίστροφα και ο αλγόριθμος RSA ===

Ένα [[πεπερασμένο σώμα]] είναι ένα σύνολο αριθμών με τέσσερις γενικευμένες πράξεις. Οι πράξεις ονομάζονται πρόσθεση, αφαίρεση, πολλαπλασιασμός και διαίρεση και έχουν τις συνήθεις ιδιότητές τους, όπως [[commutativity]], [[συσχέτιση]] και [[distributivity]]. Ένα παράδειγμα ενός πεπερασμένου σώματος είναι το σύνολο από 13 αριθμούς  {0,&nbsp;1,&nbsp;2,&nbsp;…,&nbsp;12} με [[modular αριθμητική]] . Στον τομέα αυτό, τα αποτελέσματα από κάθε μαθηματική πράξη (πρόσθεση / αφαίρεση / πολλαπλασιασμός / διαίρεση) μειώνονται στο [[modulo]] 13. Έτσι, πολλαπλάσια του 13, προστίθενται ή αφαιρούνται έως ότου το αποτέλεσμα γίνει μέσα στο εύρος 0-12. Για παράδειγμα, αποτέλεσμα του 5&nbsp;×&nbsp;7&nbsp;=&nbsp;35&nbsp;mod&nbsp;13&nbsp;=&nbsp;9 . Τέτοια πεπερασμένα σώματα μπορούν να εφαρμοστούν για κάθε πρώτο αριθμό p.Χρησιμοποιώντας πιο εξελιγμένε ερμηνείες, μπορούν επίσης να εφαρμοστούν για δύναμη m ενός πρώτου αριθμού ''p'' . Τα πεπερασμένα σώματα συχνά αποκαλούνται τομείς [[Εβαρίστ Γκαλουά|Γκαλουά]] και σε συντομογραφία γράφονται ως GF(''p'') ή GF(''p''<sup>&nbsp;''m''</sup>). Σε ένα τέτοιο σώμα με m αριθμούς, κάθε μη μηδενικό στοιχείο a έχει ένα μοναδικό [[αντίστροφο πολλαπλασιαστικό modular]],''a''<sup>−1</sup> τέτοιο ώστε ''aa''<sup>−1</sup>&nbsp;=&nbsp;''a''<sup>−1</sup>''a''&nbsp;≡&nbsp;1&nbsp;mod&nbsp;''m''  . Αυτό το αντίστροφο μπορεί να βρεθεί λύνοντας αντίστοιχα την εξίσωση ''ax''&nbsp;≡&nbsp;1&nbsp;mod&nbsp;''m'' ,<ref>Schroeder 2005 , σελ. 107-109</ref>   ή την ισοδύναμη Διοφαντική εξίσωση <ref>Stillwell 1997 , σελ. 186-187</ref>

: ''ax'' + ''my'' = 1.

Αυτή η εξίσωση μπορεί να λυθεί από τον Ευκλείδειο αλγόριθμο, όπως περιγράφηκε παραπάνω.Βρίσκοντας πολλαπλασιαστικά αντίστροφα είναι ένα ουσιαστικό βήμα στον [[RSA αλγόριθμο]] , ο οποίος χρησιμοποιείται ευρέως στο [[ηλεκτρονικό εμπόριο]] .Συγκεκριμένα, η εξίσωση που καθορίζει τον ακέραιο χρησιμοποιείται για να αποκρυπτογραφήσει το μήνυμα.<ref>Schroeder 2005 , p. 134</ref> Σημειώστε ότι αν και ο αλγόριθμος RSA χρησιμοποιεί [[δακτύλιους]] αντί για σώματα, ο Ευκλείδειος αλγόριθμος μπορεί ακόμη να χρησιμοποιηθεί για να βρει ένα πολλαπλασιαστικό αντίστροφο, αν υπάρχει. Ο Ευκλείδειος αλγόριθμος έχει και άλλες εφαρμογές σε [[κώδικες διόρθωτές λαθών]]. Για παράδειγμα, μπορεί να χρησιμοποιηθεί ως εναλλακτική λύση για τον [[αλγόριθμο Berlekamp-Massey]] για την αποκωδικοποίηση κωδίκων [[BCH]] και [[Reed-Solomon]] ,οι οποίοι βασίζονται στους Galois τομείς.<ref>"κωδικοποίηση διόρθωσης σφάλματος: μαθηματικές μέθοδοι και αλγόριθμοι", σελ. 266, Todd Κ. Moon, John Wiley and Sons, 2005, ISBN 0-471-64800-0</ref>

===Κινέζικο θεώρημα υπολοίπων ===

Ο Ευκλείδιος αλγόριθμος μπορεί επίσης να χρησιμοποιηθεί για την επίλυση πολλαπλών γραμμικών Διοφαντικών εξισώσεων.<ref>Rosen 2000 , σελ. 143-170</ref> Τέτοιες εξισώσεις προκύπτουν στο [[Κινέζικο θεώρημα υπολοίπου]] , το οποίο περιγράφει μία νέα μέθοδο για την αντιπροσώπευση ενός ακεραίου ''x'' . Αντί να εκπροσωπείται ένας ακέραιος από τα ψηφία του, μπορεί να εκπροσωπείται από το υπόλοιπο του ''x''<sub>''i''</sub>  modulo, ένα σύνολο ''N'' σχετικά πρώτων αριθμών ''m''<sub>''i''</sub> .<ref>Schroeder 2005 , σελ. 194-195</ref>

: ''x''<sub>1</sub> &equiv; ''x'' mod ''m''<sub>1</sub>
: ''x''<sub>2</sub> &equiv; ''x'' mod ''m''<sub>2</sub>
:…
: ''x''<sub>''N''</sub> &equiv; ''x'' mod ''m''<sub>''N''</sub>

Ο στόχος είναι να προσδιοριστεί το ''x'' από το υπόλοιπο του ''N'' με το  ''x''<sub>''i''</sub>. Η λύση είναι να συνδυάσει τις πολλαπλές εξισώσεις σε μια ενιαία γραμμική Διοφαντική εξίσωση με ένα πολύ μεγαλύτερο συντελεστή ''M'' , που είναι το γινόμενο όλων των επιμέρων moduli ''m''<sub>''i''</sub>, και να καθορίσει το  ''M''<sub>''i''</sub> ,

: ''M''<sub>''i''</sub> = ''M'' / ''m''<sub>''i''</sub>

Ετσι, κάθε ''M''<sub>''i''</sub>  είναι το γινόμενο όλων των moduli εκτός του ''m''<sub>''i''</sub> . Η λύση εξαρτάται από την εύρεση ''N'' νέων αριθμών ''h''<sub>''i''</sub> έτσι ώστε να ισχύει

:''M''<sub>''i''</sub>''h''<sub>''i''</sub> &equiv; 1 mod ''m''<sub>''i''</sub>

Με αυτούς τους αριθμούς  ''h''<sub>''i''</sub> , οποιοσδήποτε ακέραιος ''x'' μπορεί να ανακατασκευαστεί από τα υπόλοιπα ''x''<sub>''i''</sub> από την εξίσωση

: x &equiv; (''x''<sub>1</sub>''M''<sub>1</sub>''h''<sub>1</sub> + ''x''<sub>2</sub>''M''<sub>2</sub>''h''<sub>2</sub> + … + ''x''<sub>''N''</sub>''M''<sub>''N''</sub>''h''<sub>''N''</sub> ) mod ''M''

Δεδομένου ότι αυτοί οι αριθμοί  ''h''<sub>''i''</sub> είναι τα πολλαπλασιαστικά αντίστροφα του ''M''<sub>''i''</sub>  , μπορούν να βρεθούν χρησιμοποιώντας τον αλγόριθμο του Ευκλείδη, όπως περιγράφηκε στην προηγούμενη ενότητα.

===Δέντρο Stern-Brocot===

Η αλληλουχία των αφαιρέσεων που χρησιμοποιείται από τον Ευκλείδειο αλγόριθμο δίνει μια διαδρομή από τη ρίζα του [[Δέντρου Stern-Brocot]] σε οποιαδήποτε δεδομένο ρητό αριθμό. Το γεγονός αυτό μπορεί να χρησιμοποιηθεί για να αποδειχθεί ότι υπάρχει μια 1-1 αντιστοιχία μεταξύ των κορυφών των δέντρων και των θετικών ρητών αριθμών. Για παράδειγμα, το 3/4 μπορεί να βρεθεί ξεκινώντας από την ρίζα, προχωρώντας προς τα αριστερά μια φορά, και στη συνέχεια, προς τα δεξιά δύο φορές.

[[Image:SternBrocotTree.svg|thumb|400px|Το  Stern–Brocot δέντρο, και οι Stern–Brocot ακολουθίες με ''i'' για ''i'' = 1, 2, 3, 4.]]

:<math> 
\begin{align}
 & \gcd(3,4) & \leftarrow \\
= & \gcd(3,1) & \rightarrow \\
= & \gcd(2,1) & \rightarrow \\
= & \gcd(1,1)
\end{align}
</math>

Ο Ευκλείδειος αλγόριθμος είναι σχεδόν το ίδιο με το [[Calkin-Wilf δέντρο]] . Η διαφορά είναι ότι η διαδρομή αντιστρέφεται: αντί να παράγει μια διαδρομή από τη ρίζα του δέντρου σε ένα στόχο, παράγει μια διαδρομή από το στόχο προς τη ρίζα.

===Συνεχή κλάσματα ===

Ο Ευκλείδειος αλγόριθμος έχει μια στενή σχέση με τα [[συνεχή κλάσματα]] .<ref>Vinogradov IM (1954). Στοιχεία Θεωρίας Αριθμών . Νέα Υόρκη: Ντόβερ. σελ. 3-13.</ref>  Η σειρά των εξισώσεων μπορεί να γραφεί στη μορφή

:<math>
\begin{align}
\frac{a}{b} &= q_0 + \frac{r_0}{b} \\
\frac{b}{r_0} &= q_1 + \frac{r_1}{r_0} \\
\frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\
& {}\  \vdots \\
\frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\
& {}\  \vdots \\
\frac{r_{N-2}}{r_{N-1}} &= q_N
\end{align}
</math>

Ο τελευταίος όρος στη δεξιά πλευρά είναι πάντα ίσος με τον αντίστροφο της αριστερής πλευράς της επόμενης εξίσωσης. Έτσι, οι δύο πρώτες εξισώσεις μπορούν να συνδυαστούν για να σχηματίσουν

:<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}} </math>

Η τρίτη εξίσωση μπορεί να χρησιμοποιηθεί για να αντικαταστήσει τον όρο ''r''<sub>1</sub>/''r''<sub>0</sub> , αποδίδοντας

:<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}}} </math>

Η τελική αναλογία από το υπόλοιπο του ''r''<sub>''k''</sub>/''r''<sub>''k''−1</sub> μπορεί πάντα να αντικατασταθεί χρησιμοποιώντας την επόμενη εξίσωση στη σειρά, μέχρι την τελική εξίσωση. Το αποτέλεσμα είναι ένα συνεχές κλάσμα

:<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\ddots + \cfrac{1}{q_N}}}} = [ q_0; q_1, q_2, \ldots , q_N ] </math>

Στο αριθμητικό παραπάνω παράδειγμα , ο ΜΚΔ (1071, 462) υπολογίστηκε και το πηλίκο ''q''<sub>''k''</sub> ήταν 2, 3 και 7, αντίστοιχα. Ως εκ τούτου, το κλάσμα 1071/462 μπορεί να γραφεί

:<math>\frac{1071}{462} = 2 + \cfrac{1}{3 + \cfrac{1}{7}} = [2; 3, 7]</math>

όπως μπορεί να επιβεβαιωθεί από τον υπολογισμό.

=== Αλγόριθμοι Παραγοντοποίησης ===

Ο υπολογισμός ενός μέγιστου κοινού διαιρέτη είναι ένα ουσιαστικό βήμα σε πολλές [[παραγοντοποιήσεις ακεραίων]] αλγορίθμων,<ref>Crandall R, Pomerance C (2001). Prime Numbers: μια υπολογιστική προοπτικές (1η έκδοση.). New York: Springer-Verlag. σελ. 225-349. ISBN  0-387-94777-9 .</ref>   όπως [[αλγόριθμος r του Pollard]] ,<ref>Knuth, σελ. 369-371</ref>  ο [[αλγόριθμος του Shor]],<ref>Shor PW (1997). "Αλγόριθμοι πολυωνυμικού χρόνου για την παραγοντοποίηση και Διαφορετικοί λογάριθμοι σε ένα κβαντικό υπολογιστή". SIAM Journal για την επιστημονική και στατιστική Computing 26 : 1484.</ref> η [[μέθοδος παραγοντοποίησης Ντίξον]],<ref>Dixon JD (1981). "Ασυμπτωτικά γρήγορη παραγοντοποίηση των ακεραίων". Math.Ηλεκτρονικών υπολογιστών. 36 (153): 255-260. doi : 10.2307/2007743 . JSTOR  2007743 .</ref> και η ελλειπτική παραγοντοποίηση καμπύλης Lenstra .<ref>Lenstra νεώτερος HW (1987). "Ακέραιοι Factoring με ελλειπτικές καμπύλες." Annals of Μαθηματικών 126 (3): 649-673. doi : 10.2307/1971363 . JSTOR  1971363 .</ref>  Ο Ευκλείδειος αλγόριθμος μπορεί να χρησιμοποιηθεί για να βρεθεί το ΜΚΔ αποτελεσματικά. Συνεχή παραγοντοποιημένα κλάσματα χρησιμοποιούν συνεχή κλάσματα, τα οποία καθορίζονται χρησιμοποιώντας τον αλγόριθμο του Ευκλείδη.<ref>Knuth, σελ. 380-384.</ref>

== Αλγοριθμική αποδοτικότητα ==
[[Image:Euclidean algorithm running time X Y.png|thumb|alt="A set of colored lines radiating outwards from the origin of an ''x''-''y'' coordinate system. Each line corresponds to a set of number pairs requiring the same number of steps in the Euclidean algorithm."|Αριθμός βημάτων στον αλγόριθμο του Ευκλείδη για την εύρεση του ΜΚΔ(''x'',''y''). Τα κόκκινα σημεία φανερώνουν σχετικά λίγα βήματα (γρήγορο), ενώ κίτρινα , πράσινα και μπλε δείχνουν διαδοχικά περισσότερα βήματα  (αργό). Το μεγαλυτερο μέρος της μπλε περιοχής ακολουθεί τη γραμμή  ''y'' = Φ''x'', όπου  Φ αντιπροσωπεύει την  [[Χρυσή Τομή]].]]

Η υπολογιστική αποδοτικότητα του αλγορίθμου του Ευκλείδη έχει μελετηθεί διεξοδικά.<ref>Knuth, σελ. 339 - 364.</ref>  Αυτή η αποτελεσματικότητα μπορεί να περιγραφεί από τον αριθμό των βημάτων της διαίρεσης που απαιτεί ο αλγόριθμος, πολλαπλασιαζόμενο με το υπολογιστικό κόστος κάθε βήματος. Η πρώτη γνωστή ανάλυση του αλγορίθμου του Ευκλείδη έγινε από τον A.-A.-L. Reynaud το 1811,<ref>Reynaud A.-A.-L. (1811). Traité d'arithmétique à l'χρήσης des élèves qui se destinent à l'École Polytechnique . Courcier.</ref>  ο οποίος έδειξε ότι ο αριθμός των βημάτων διαίρεσης στην είσοδο των ( ''u'' , ''v'' ) οριοθετείται από το ''v''.Αργότερα το βελτίωσε αυτό σε ''ν'' / 2 + 2. Μετέπειτα , το 1841,ο P.-J.-E. Finck έδειξε <ref>Finck P.-J.-E. (1841). Traité élémentaire d'arithmétique à l'χρήσης des candidats aux SPECIALES écoles . Derivaux.</ref>  ότι ο αριθμός των βημάτων διαίρεσης είναι το πολύ 2 log<sub>2</sub> ''v'' + 1 , και ως εκ τούτου ο αλγόριθμος του Ευκλείδη τρέχει σε πολυωνυμικό χρόνο στο μέγεθος της εισόδου. βλέπε επίσης <ref>Shallit J (1994). "Προέλευση της ανάλυσης του Ευκλείδειος αλγόριθμος". Math Historia. 21 : 401 - 419.</ref>  Η ανάλυση του τελειοποιήθηκε από τον Gabriel Lamé σε 1844,<ref>Lamé G (1844). "Note sur la limite du Nombre des τμήματα dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus Ακαδ. . Sci 19 : 867-870.</ref>  ο οποίος έδειξε ότι ο αριθμός των βημάτων που απαιτούνται για την λύση δεν είναι ποτέ περισσότερα από πέντε φορές τον αριθμό h της βάσης-10 ψηφίων του μικρότερου αριθμού ''b'' .<ref>Η Grossman (1924). "Με τον αριθμό των υποδιαιρέσεων στην εύρεση ενός ΠΔΠ". The American Mathematical Monthly 31 (9): 443. doi : 10.2307/2298146 . JSTOR  2298146 .</ref><ref>Honsberger R (1976). Μαθηματική Gems II . Η Μαθηματική Association of America . σελ. 54-57. ISBN  0-88385-302-7 .</ref>  Αφού το υπολογιστικό βάρος κάθε βήματος είναι συνήθως της τάξης ''h'' , η συνολική δαπάνη μεγαλώνει κατά  ''h''<sup>2</sup>.

===Αριθμός βημάτων===

Ο αριθμός των βημάτων για τον υπολογισμό του ΜΚΔ δύο φυσικών αριθμών, ''a'' και ''b'' , μπορεί να συμβολίζεται με ''T''(''a'',&nbsp;''b'') .<ref name="α β γ Knuth, p. 344">α β γ Knuth, p. 344.</ref>  Αν ''g'' είναι ο ΜΚΔ του ''a'' και ''b'' , τότε ''a''&nbsp;=&nbsp;''mg'' και ''b''&nbsp;=&nbsp;''ng'' για δύο πρώτους μεταξύ τους αριθμούς ''m'' και ''n'' . Τότε

: ''T''(''a'', ''b'') = ''T''(''m'', ''n'')

όπως μπορεί να φανεί διαιρώντας όλα τα βήματα στην Ευκλείδειο αλγόριθμο ''g'' .<ref>Ore 1948 , p. 45</ref>  Με το ίδιο επιχείρημα, ο αριθμός των βημάτων παραμένει ο ίδιος, αν ''a'' και ''b'' πολλαπλασιάζονται με έναν κοινό συντελεστή ''w'': ''T''(''a'', ''b'') = ''T''(''wa'', ''wb''). Ως εκ τούτου, ο αριθμός των βημάτων ''Τ'' μπορεί να ποικίλλει δραματικά μεταξύ γειτονικών ζευγών αριθμών, όπως T(''a'', ''b'') και T(''a'',&nbsp;''b''&nbsp;+&nbsp;1) , ανάλογα με το μέγεθος των δύο ΜΚΔ.

Η αναδρομική φύση του αλγορίθμου του Ευκλείδη δίνει μια άλλη εξίσωση

: ''T''(''a'', ''b'') = 1 + ''T''(''b'', ''r''<sub>0</sub>) = 2 + ''T''(''r''<sub>0</sub>, ''r''<sub>1</sub>) = … = ''N'' + ''T''(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''N'' + 1

όπου ''T''(''x'', 0)&nbsp;=&nbsp;0  σύμφωνα με την υπόθεση.<ref name="α β γ Knuth, p. 344"/>

==== Η χειρότερη περίπτωση αριθμού βημάτων ====

Αν ο Ευκλείδειος αλγόριθμος απαιτεί ''N'' βήματα για ένα ζευγάρι φυσικών αριθμών ''a''&nbsp;>&nbsp;''b''&nbsp;>&nbsp;0 , οι μικρότερες τιμές των ''a'' και ''b'' για την οποία αυτός αληθεύει, είναι οι [[Αριθμοί Φιμπονάτσι|αριθμοί Φιμπονάτσ]]<nowiki/>ι ''F''<sub>''N''+2</sub> και ''F''<sub>''N''+1</sub>  , αντίστοιχα.<ref name="α β Knuth, p. 343">α β Knuth, p. 343.</ref>  Αυτό μπορεί να αποδειχθεί με [[Μαθηματική επαγωγή|επαγωγή]] .<ref>Mollin 2008 , p. 21</ref>  Εάν ''N''&nbsp;=&nbsp;1, ο ''b'' διαιρεί τον  ''a'' ακριβώς.Οι μικρότεροι φυσικοί αριθμοί για τους οποίους ισχύει είναι ''b''&nbsp;=&nbsp;1 και ''a''&nbsp;=&nbsp;2, τα οποία είναι τα ''F''<sub>2</sub> και ''F''<sub>3</sub> , αντιστοίχως. Ας υποθέσουμε τώρα ότι το αποτέλεσμα ισχύει για όλες τις τιμές του ''Ν'' έως ''M''&nbsp;−&nbsp;1 . Το πρώτο βήμα ενός αλγορίθμου με Μ-βήματα είναι ''a''&nbsp;=&nbsp;''q''<sub>0</sub>''b''&nbsp;+&nbsp;''r''<sub>0</sub> , και το δεύτερο βήμα είναι ''b''&nbsp;=&nbsp;''q''<sub>1</sub>''r''<sub>0</sub>&nbsp;+&nbsp;''r''<sub>1</sub> . Δεδομένου ότι ο αλγόριθμος είναι αναδρομικός,απαιτούνται ''M''&nbsp;−&nbsp;1 βήματα για να βρεθεί ο ΜΚΔ (''b'',&nbsp;''r''<sub>0</sub>) και οι μικρότερες τιμές τους είναι ''F''<sub>''M''+1</sub> και ''F''<sub>''M''</sub> . Έχουμε συνεπώς την μικρότερη τιμή του ''a'' , όταν ''q''<sub>0</sub>&nbsp;=&nbsp;1 , το οποίο δίνει ''a''&nbsp;=&nbsp;''b''&nbsp;+&nbsp;''r''<sub>0</sub>&nbsp;=&nbsp;''F''<sub>''M''+1</sub>&nbsp;+&nbsp;''F''<sub>''M''</sub>&nbsp;=&nbsp;''F''<sub>''M''+2</sub> . Η απόδειξη αυτή, η οποία δημοσιεύθηκε από τον [[Gabriel Lamé]] το 1844, αντιπροσωπεύει την αρχή της[[υπολογιστική θεωρία πολυπλοκότητας|υπολογιστικής θεωρίας πολυπλοκότητας]] ,<ref>Lévêque 1996 , p. 35</ref>   καθώς επίσης και την πρώτη πρακτική εφαρμογή των αριθμών Fibonacci.<ref name="α β Knuth, p. 343"/>  Το αποτέλεσμα αυτό αρκεί για να δείξει ότι ο αριθμός των βημάτων στον αλγόριθμο του Ευκλείδη δεν μπορεί ποτέ να είναι μεγαλύτερος από πέντε φορές τον αριθμό των ψηφίων του (βάση 10).<ref>Mollin 2008 , σελ. 21-22</ref>  Για το αν ο αλγόριθμος απαιτεί ''Ν'' βήματα, τότε ο ''b'' είναι μεγαλύτερος ή ίσος με το ''F''<sub>''N''+1</sub> το οποίο με τη σειρά του είναι μεγαλύτερο ή ίσο με  ''φ''<sup>''N''&minus;1</sup> , όπου ''φ'' είναι η [[χρυσή τομή]].Αφού ''b''&nbsp;≥&nbsp;''φ''<sup>''N''&minus;1</sup>, τότε  ''N''&nbsp;&minus;&nbsp;1&nbsp;≤&nbsp;log<sub>''φ''</sub>''b''. Αφού log<sub>10</sub>''φ''&nbsp;>&nbsp;1/5, (''N''&nbsp;&minus;&nbsp;1)/5&nbsp;<&nbsp;log<sub>10</sub>''φ''&nbsp;log<sub>''φ''</sub>''b''&nbsp;=&nbsp;log<sub>10</sub>''b'' . Έτσι, ''N''&nbsp;≤&nbsp;5&nbsp;log<sub>10</sub>''b'' . Επομένως, ο Ευκλείδειος αλγόριθμος χρειάζεται πάντα λιγότερες από [[Ο ( h )]] διαιρέσεις, όπου ''h'' είναι ο αριθμός των ψηφίων του μικρότερου αριθμού ''b'' .

===Υπολογιστική δαπάνη ανά βήμα===

Σε κάθε βήμα k τoy Ευκλείδειoυ αλγορίθμου, το πηλίκο ''q''<sub>''k''</sub> και υπόλοιπο ''r''<sub>''k''</sub> υπολογίζονται για ένα δεδομένο ζεύγος ακεραίων ''r''<sub>''k''−2</sub> και ''r''<sub>''k''−1</sub>
: ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>.

Η υπολογιστική δαπάνη ανά βήμα σχετίζεται κυρίως με την εύρεση του ''q''<sub>''k''</sub> , δεδομένου ότι το υπόλοιπο  ''r''<sub>''k''</sub>  μπορεί να υπολογιστεί γρήγορα από ''r''<sub>''k''−2</sub>, ''r''<sub>''k''−1</sub>, και ''q''<sub>''k''</sub>
: ''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>.

Η υπολογιστική δαπάνη διαίρεσης h -bit αριθμούς ως κλίμακες ''O''(''h''(''ℓ''+1)), όπου ℓ είναι το μήκος του πηλίκου.<ref>Knuth, pp. 257–261.</ref>

Για λόγους σύγκρισης,ο αρχικός αλγόριθμος του Ευκλείδη που χρησιμοποιεί τη μέθοδο της αφαίρεσης,μπορεί να είναι πολύ πιο αργός. Μια ακέραια διαίρεση  είναι ισοδύναμη με το πηλίκο Q προς τον αριθμό των αφαιρέσεων. Εάν η αναλογία του a και του Β είναι πολύ μεγάλη, το πηλίκο είναι μεγάλο και θα απαιτηθούν πολλές αφαιρέσεις. Από την άλλη πλευρά, έχει δειχθεί ότι τα πηλίκα είναι πολύ πιθανό να είναι μικροί ακέραιοι. Η πιθανότητα ενός δεδομένου πηλίκου q είναι περίπου ln|''u''/(''u''&nbsp;−&nbsp;1)| όπου ''u''&nbsp;=&nbsp;(''q''&nbsp;+&nbsp;1)<sup>2</sup>.<ref>Knuth, p. 352.</ref>  Για παράδειγμα, η πιθανότητα ενός πηλίκου 1, 2, 3 ή 4 είναι περίπου 41,5%, 17,0%, 9,3% και 5,9%, αντίστοιχα. Δεδομένου ότι η λειτουργία της αφαίρεσης είναι πιο γρήγορη από ό, τι της διαίρεσης, ιδιαίτερα για μεγάλους αριθμούς,<ref>{{cite book | author = Wagon S | year = 1999 | title = Mathematica in Action | publisher = Springer-Verlag | location = New York | isbn = 0-387-98252-3 | pages = 335–336}}</ref>η μέθοδος του Ευκλείδη που βασίζεται στην αφαίρεση είναι "ανταγωνιστική" με τη μέθοδο της διαίρεσης.<ref>{{Harvnb|Cohen|1993|p=14}}</ref> Αυτό αξιοποιείται στην [[δυαδική]] έκδοση του αλγορίθμου του Ευκλείδη.<ref>{{Harvnb|Cohen|1993|pp=14–15, 17–18}}</ref>

Συνδυάζοντας τον εκτιμώμενο αριθμό των βημάτων με την εκτιμώμενη υπολογιστική δαπάνη ανά βήμα φαίνεται ότι ο αλγόριθμος του Ευκλείδη μεγαλώνει συγγραμικά (''h''<sup>2</sup>) , με τον μέσο αριθμό των ψηφίων "h" των δύο πρώτων αριθμών a και b . Έστω ''h''<sub>0</sub>, ''h''<sub>1</sub>, …, ''h''<sub>''N''−1</sub>  -1 αντιπροσωπεύουν τον αριθμό των ψηφίων στο πλαίσιο των διαδοχικών υπολοίπων ''r''<sub>0</sub>,&nbsp;''r''<sub>1</sub>,&nbsp;…,&nbsp;''r''<sub>''N''−1</sub> . Δεδομένου ότι ο αριθμός των βημάτων "N" αναπτύσσεται γραμμικά με "h" , ο χρόνος είναι που οριοθετείται από

:<math>
O\Big(\sum_{i<N}h_i(h_i-h_{i+1}+2)\Big)\subseteq O\Big(h\sum_{i<N}(h_i-h_{i+1}+2)\Big)\subseteq O(h(h_0+2N))\subseteq O(h^2).</math>

===Αποδοτικότητα των εναλλακτικών μεθόδων===

Ο Αλγόριθμος του Ευκλείδη χρησιμοποιείται ευρέως στην πράξη, ιδίως για τους μικρούς αριθμούς, λόγω της απλότητάς του. Για λόγους σύγκρισης, η αποτελεσματικότητα των εναλλακτικών αλγόριθμων του Ευκλείδη μπορεί να προσδιοριστεί.

Μια αναποτελεσματική προσέγγιση για την εύρεση του ΜΚΔ δύο φυσικών αριθμών a και  Β είναι να υπολογιστούν όλοι οι κοινοί διαιρέτες τους.ο ΜΚΔ είναι τότε ο μεγαλύτερος κοινός διαιρέτης. Οι κοινοί διαιρέτες μπορούν να βρεθούν διαιρώντας τους δύο αριθμούς με διαδοχικούς ακέραιους από 2 έως τον μικρότερο αριθμό b . Ο αριθμός των βημάτων της προσέγγισης αυτής αυξάνει γραμμικά με το b , ή εκθετικά με τον αριθμό των ψηφίων. Μια άλλη προσέγγιση είναι αναποτελεσματική για να βρει τους πρωταρχικούς παράγοντες του ενός ή και των δύο αριθμών. Όπως σημειώνεται [[ανωτέρω]] , ο ΜΚΔ ισούται με το γινόμενο από των πρώτων κοινών παραγόντων των α και b.<ref name="Schroeder_21" />    Οι παρούσες μέθοδοι για την [[παραγοντοποίηση]] είναι επίσης αναποτελεσματικές. πολλά σύγχρονα συστήματα κρυπτογράφησης, ακόμη στηρίζονται στην εν λόγω αναποτελεσματικότητα.<ref name="Schroeder_216" />

Ο [[δυαδικός αλγόριθμος του ΜΚΔ]] είναι μια αποτελεσματική εναλλακτική λύση που περιλαμβάνει διαίρεση με πιο γρήγορες διαδικασίες, αξιοποιώντας τη [[δυαδική αναπαράσταση]] που χρησιμοποιείται από τους υπολογιστές. .<ref>Knuth, pp. 321–323.</ref><ref>{{cite journal | author = Stein J | year = 1967 | title = Computational problems associated with Racah algebra | journal = Journal of Computational Physics | volume = 1 | pages = 397–405 | doi = 10.1016/0021-9991(67)90047-2 | issue = 3}}</ref> Ωστόσο, αυτή η εναλλακτική επίσης εκτιμάται της τάξης του ''O''(''h''²). Είναι γενικά πιο γρήγορη από τον Ευκλείδειο αλγόριθμο για πραγματικούς υπολογιστές, μολονότι εξελίσεται με τον ίδιο τρόπο.<ref name="Crandall_2001">{{cite book | author = Crandall R, Pomerance C | year = 2001 | title = Prime Numbers: A Computational Perspective | url = https://archive.org/details/primenumberscomp0000cran | edition = 1st | publisher = Springer-Verlag | location = New York | isbn = 0-387-94777-9 | pages = [https://archive.org/details/primenumberscomp0000cran/page/77 77]–79, 81–85, 425–431}}</ref> επιπλέον η αποτελεσματικότητά του μπορεί να φανεί εξετάζοντας μόνο τα μεγαλύτερα ψηφία των δύο αριθμών α και b .<ref>Knuth, p. 328.</ref><ref>{{cite journal | author = Lehmer DH | year = 1938 | title = Euclid's Algorithm for Large Numbers | journal = The American Mathematical Monthly | volume = 45 | pages = 227–233 | doi = 10.2307/2302607 | jstor = 2302607 | issue = 4}}</ref> ο δυαδικός αλγόριθμος μπορεί να επεκταθεί και σε άλλες βάσεις ( k -ary αλγόριθμοι), ),<ref>{{cite journal | author = Sorenson J | year = 1994 | title = Two fast GCD algorithms | journal = J. Algorithms | volume = 16 | pages = 110–144 | doi = 10.1006/jagm.1994.1006}}</ref>  με έως και πενταπλάσια αύξηση στην ταχύτητα..<ref>{{cite journal | author = Weber K | year = 1995 | title = The accelerated GCD algorithm | journal = ACM Trans. Math. Soft. | volume = 21 | pages = 111–122 | doi = 10.1145/200979.201042}}</ref>

Μια αναδρομική προσέγγιση για όλους τους μεγάλους ακεραίους (με περισσότερα από 25.000 ψηφία) οδηγεί σε subquadratic  αλγορίθμων  ακεραίων για τον ΜΚΔ ,<ref>{{cite book|title=The Design and Analysis of Computer Algorithms|first=Hopcroft J|author=Aho A|last2=Ullman J|publisher=Addison–Wesley|isbn=0-201-00029-6|year=1974|location=New York|page=|pages=[https://archive.org/details/designanalysisof00ahoarich/page/300 300–310]|url=https://archive.org/details/designanalysisof00ahoarich/page/300|quote=|url-access=registration}}</ref>   όπως αυτές της Schönhage,<ref>{{cite journal | author = Schönhage A | title = Schnelle Berechnung von Kettenbruchentwicklungen | journal = Acta Informatica | volume = 1 | pages = 139–144 | doi = 10.1007/BF00289520 | year = 1971 | issue = 2}}</ref><ref>{{cite book | author = Cesari G | year = 1998 | chapter = Parallel implementation of Schönhage's integer GCD algorithm | title = Algorithmic Number Theory: Proc. ANTS-III, Portland, OR | url = https://archive.org/details/algorithmicnumbe00buhl | editor = G. Buhler | publisher = Springer-Verlag | location = New York | pages = [https://archive.org/details/algorithmicnumbe00buhl/page/n71 64]–76}} Volume 1423 in ''Lecture notes in Computer Science''.</ref> και Stehle και Zimmermann.<ref>{{cite book | author = Stehlé D, Zimmermann P | year = 2005 | chapter = Gal's accurate tables method revisited | title = Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17) | publisher = [[IEEE Computer Society Press]] | location = Los Alamitos, CA}}</ref> Αυτοί οι αλγόριθμοι εκμεταλλεύονται τον 2 × 2 μορφής πίνακα του Ευκλείδιου αλγόριθμου που δίνεται [[παραπάνω]] . Αυτές οι μέθοδοι γενικά της τάξης του {{nowrap|''O''(''h'' (log ''h'')<sup>2</sup> (log log ''h'')).}}.<ref name="Crandall_2001" /><ref>{{cite journal | author = Möller N | title = On Schönhage's algorithm and subquadratic integer gcd computation | journal = Mathematics of Computation | volume = 77 | pages = 589–607 | doi = 10.1090/S0025-5718-07-02017-0 | year = 2008 | url=http://www.lysator.liu.se/~nisse/archive/sgcd.pdf | issue = 261}}</ref>

==Άλλα συστήματα αριθμών==

Όπως περιγράφεται παραπάνω, ο Ευκλείδειος αλγόριθμος χρησιμοποιείται για να βρούμε τον μέγιστο κοινό διαιρέτη δύο φυσικών αριθμών (θετικοί ακέραιοι). Ωστόσο, μπορεί να γενικευτεί στους πραγματικούς αριθμούς, και σε πιο εξωτικά συστήματα αριθμών, όπως [[πολυώνυμα]] , [[τετραγωνικοί ακέραιοι]] και [[Hurwitz quaternions]] . Στις τελευταίες περιπτώσεις, ο Ευκλείδειος αλγόριθμος χρησιμοποιείται για να καταδείξει την κρίσιμη ιδιότητα της μοναδικής παραγοντοποίησης, δηλαδή, ότι οι αριθμοί μπορούν να αναλυθούν κατά μοναδικό τρόπο σε ανάγωγα στοιχεία , οι αντίστιχοι των πρώτων αριθμών. Αυτής της μορφής η παραγοντοποίηση είναι ιδιαιτέρως χρήσιμη για πολλές αποδείξεις της θεωρίας αριθμών.

===Ρητοί και πραγματικοί αριθμοί===

Ο αλγόριθμος του Ευκλείδη μπορεί να εφαρμοστεί σε [[πραγματικούς αριθμούς]] , όπως περιγράφεται από τον Ευκλείδη στο δέκατο βιβλίο των ''Στοιχείων''. ο  στόχος του αλγορίθμου είναι να προσδιορίσει έναν πραγματικό αριθμό g τέτοιον ώστε δύο δοσμένοι πραγματικοί αριθμοί, α και β ,να είναι ακέραια πολλαπλάσια του: α = mg και b = ng , όπου m και n είναι [[ακέραιοι]].<ref name="Weil_1983" /> Αυτή η ταυτοποίηση είναι ισοδύναμη με την εύρεση [[μια ακέραια σχέση]] μεταξύ των πραγματικών αριθμών α και β.δηλαδή, προσδιορίζει ακέραιους s και t , έτσι ώστε sa + tb = 0.Ευκλείδιος αλγόριθμος χρησιμοποιείται για την αντιμετώπιση του ζητήματος των [[ασύμμετρων μηκών]] .<ref>{{cite book | author = Boyer CB, Merzbach UC | year = 1991 | title = A History of Mathematics | edition = 2nd | publisher = Wiley | location = New York | isbn = 0-471-54397-7 | pages = [https://archive.org/details/historyofmathema00boye/page/116 116–117] | url-access = registration | url = https://archive.org/details/historyofmathema00boye/page/116 }}</ref><ref>{{cite book | author = [[Florian Cajori|Cajori F]] | year = 1894 | title = A History of Mathematics | url = https://archive.org/details/historyofmathema1894cajo| publisher = Macmillan | location = New York | page = [https://archive.org/details/historyofmathema1894cajo/page/70 70] | isbn = 0-486-43874-0}}</ref>

Ο αλγόριθμος του ευκλείδη για τους πραγματικούς αριθμούς διαφέρει από τον αντίστοιχο για ακεραίους σε δύο σημεία. Πρώτον,τα υπόλοιπα ''r''<sub>''k''</sub> είναι πραγματικοί αριθμοί, αν και τα πηλίκα ''q''<sub>''k''</sub> είναι ακέραιοι, όπως και πριν. Δεύτερον, ο αλγόριθμος δεν είναι εγγυημένο πως θα ολοκληρωθεί σε πεπερασμένο αριθμό Ν των βημάτων. Αν συμβεί αυτό, το κλάσμα α / b είναι ένας ρητός αριθμός, δηλαδή, ο λόγος δύο ακεραίων
: ''a''/''b'' = ''mg''/''ng'' = ''m''/''n''

και μπορεί να γραφτεί ως ένα πεπερασμένο συνεχές κλάσμα [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …, ''q''<sub>''N''</sub>[''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …, ''q''<sub>''N''</sub>. Αν ο αλγόριθμος δεν σταματά, το κλάσμα α / b είναι ένας [[άρρητος αριθμός]] και μπορεί να περιγραφεί σαν ένα άπειρο συνεχές κλάσμα  [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …].  Παραδείγματα από άπειρα συνεχή κλάσματα είναι η [[χρυσή τομή]] φ = [1? 1, 1, ...] και η [[τετραγωνική ρίζα του δύο]],√2 = [1; 2, 2, …]. Σε γενικές γραμμές, ο αλγόριθμος είναι απίθανο να σταματήσει, δεδομένου ότι [[Σχεδόν όλα|σχεδόν όλες]] οι αναλογίες α / β των δύο πραγματικών αριθμών είναι άρρητες.

Ένα άπειρο συνεχές κλάσμα μπορεί να ''σπάσει'' σε κάποιο στάδιο ''k'' [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …, ''q''<sub>''k''</sub>]  για να δώσει μια προσέγγιση του α / Β που γίνεται ολοένα καλύτερη καθώς το k αυξάνεται. Η προσέγγιση αυτή περιγράφεται από συκλίνοντες, ο αριθμητής και ο παρονομαστής είναι πρώτοι μεταξύ τους και συνδέονται με τη σχέση
:''m''<sub>''k''</sub> = ''q''<sub>''k''</sub> ''m''<sub>''k''−1</sub> + ''m''<sub>''k''−2</sub>
:''n''<sub>''k''</sub> = ''q''<sub>''k''</sub> ''n''<sub>''k''−1</sub> + ''n''<sub>''k''−2</sub>

όπου ''m''<sub>−1</sub> = ''n''<sub>−2</sub> = 1 and ''m''<sub>−2</sub> = ''n''<sub>−1</sub> = 0 είναι οι αρχικές τιμές της αναδρομικής σχέσης. Η συγκλίνουσα ''m''<sub>''k''</sub>/''n''<sub>''k''</sub> είναι η καλύτερη [[ρητή προσέγγιση]] στο a/b με παρονομαστή ''n''<sub>''k''</sub>::
:<math alt="The absolute value of the difference of two ratios (a over b minus m sub k over n sub k) is less than one over n sub k squared."> 
\left|\frac{a}{b} - \frac{m_k}{n_k}\right| < \frac{1}{n_k^2}.
</math>

===Πολυώνυμα===
Πολυώνυμα σε μια μόνο μεταβλητή x μπορεί να προστεθούν, πολλαπλασιάστούν και να αναλυθούν σε [[ανάγωγα πολυώνυμα]] , τα οποία είναι τα ανάλογα των πρώτων αριθμών για τους ακέραιους αριθμούς. Ο μέγιστος κοινός διαιρέτης πολυώνυμο ''g''(''x'') δύο πολυωνύμων ''a''(''x'') and ''b''(''x'') ορίζεται ως το γινόμενο των κοινών ανάγωγων πολυωνυμων τους, τα οποία μπορούν να προσδιοριστούν χρησιμοποιώντας τον Ευκλείδειο αλγόριθμο.<ref name="Lang_1984">{{cite book | author = [[Serge Lang|Lang S]] | year = 1984 | title = Algebra | url = https://archive.org/details/algebra0000lang | edition = 2nd | publisher = Addison–Wesley | location = Menlo Park, CA | isbn = 0-201-05487-6 | pages = [https://archive.org/details/algebra0000lang/page/190 190]–194}}</ref> Η βασική διαδικασία είναι παρόμοια με τους ακέραιους. Σε κάθε βήμα "k" , ένα πηλίκο πολυώνυμο  ''q''<sub>''k''</sub>(''x'') και ένα υπόλοιπο πολυώνυμο ''r''<sub>''k''</sub>(''x'') προσσδιορίζονται για να ικανοποιήσει την επαναληπτική εξίσωση
: ''r''<sub>''k''−2</sub>(''x'') = ''q''<sub>''k''</sub>(''x'') ''r''<sub>''k''−1</sub>(''x'') + ''r''<sub>''k''</sub>(''x'')

όπου ''r''<sub>−2</sub>(''x'')&nbsp;=&nbsp;''a''(''x'') και ''r''<sub>−1</sub>(''x'')&nbsp;=&nbsp;''b''(''x''). Το πολυώνυμο-πηλίκον επιλέγεται έτσι ώστε ο μεγαλύτερος όρος  ''q''<sub>''k''</sub>(''x'') ''r''<sub>''k''−1</sub>(''x'') να ισούται με τον μεγαλύτερο όρο του ''r''<sub>''k''−2</sub>(''x'');. αυτό εξασφαλίζει ότι ο βαθμός  κάθε υπόλοιπου είναι μικρότερος από το βαθμό του προηγουμένου του deg[''r''<sub>''k''</sub>(''x'')] < deg[''r''<sub>''k''−1</sub>(''x'')]. Δεδομένου ότι ο βαθμός είναι ένας μη αρνητικός ακέραιος αριθμός, και δεδομένου ότι μειώνεται με κάθε βήμα, ο αλγόριθμος του Ευκλείδη ολοκληρώνεται σε έναν πεπερασμένο αριθμό βημάτων. Το τελικό μη μηδενικό υπόλοιπο είναι ο μέγιστος κοινός διαιρέτης των αρχικών δύο πολυώνυμα,''a''(''x'') και ''b''(''x'').<ref>{{Harvnb|Cox|Little|O'Shea|1997|pp=37–46}}</ref>

Για παράδειγμα, σκεφτείτε τα εξής δύο τετραγωνικά πολυώνυμα, στα οποίο κάθε παράγοντας αναλύεται σε δύο τετραγωνικά πολυώνυμα
: ''a''(''x'') = ''x''<sup>4</sup> − 4''x''<sup>3</sup> + 4 ''x''<sup>2</sup> − 3''x'' + 14 = (''x''<sup>2</sup> − 5''x'' + 7)(''x''<sup>2</sup> + ''x'' + 2)

και
: ''b''(''x'') = ''x''<sup>4</sup> + 8''x''<sup>3</sup> + 12''x''<sup>2</sup> + 17''x'' + 6 = (''x''<sup>2</sup> + 7''x'' + 3)(''x''<sup>2</sup> + ''x'' + 2).

[[Διαίρεση|Διαιρώντας]] το ''a''(''x'') με το ''b''(''x'') προκύπτει ένα υπόλοιπο ''r''<sub>0</sub>(''x'') = ''x''<sup>3</sup> + (2/3) ''x''<sup>2</sup> + (5/3) ''x'' − (2/3). Στο επόμενο βήμα,  ''b''(''x'') διαιρείται δια ''r''<sub>0</sub>(''x'') δίνοντας ένα υπόλοιπο ,''r''<sub>1</sub>(''x'') = ''x''<sup>2</sup> + ''x'' + 2 . Τέλος, διαιρώντας  ''r''<sub>0</sub>(''x'') με ''r''<sub>1</sub>(''x'') προκύπτει ένα μηδενικό υπόλοιπο, που δείχνει ότι το ''r''<sub>1</sub>(''x'')  είναι ο μέγιστος κοινός διαιρέτης των πολυώνυμων  ''a''(''x'') και ''b''(''x'').
Πολλές από τις εφαρμογές που περιγράφονται παραπάνω για τους ακέραιους αριθμούς μεταφέρονται στο πολυώνυμα.<ref>{{Harvnb|Schroeder|2005|pp=254–259}}</ref> Ο Ευκλείδειος αλγόριθμος μπορεί να χρησιμοποιηθεί για την επίλυση γραμμικών διοφαντικών εξισώσεων και κινεζικων προβληματων  για τα υπόλοιπα των πολυωνύμων. συνεχή κλάσματα πολυωνύμων μπορούν επίσης να οριστούν.

Ο πολυωνυμικός Ευκλείδειος αλγόριθμος έχει και άλλες εφαρμογές, καθώς, όπως [[Sturm chains]] , μια μέθοδος για την μέτρηση του αριθμού των πραγματικών ριζών ενός πολυωνύμου εντός ενός δεδομένου διαστήματος στον πραγματικό άξονα. Αυτό έχει εφαρμογές σε πολλούς τομείς, όπως στο [[κριτήριο της σταθερότητας Routh-Hurwitz]] στη [[θεωρία ελέγχου]] .

Τέλος, δεν χρειάζεται οι συντελεστές των πολυωνύμων να ειναι ακέραιοι αριθμοί, πραγματικοί αριθμοί ή ακόμη και οι μιγαδικοί. Για παράδειγμα, οι συντελεστές μπορούν να εξαχθούν από ένα γενικό σώμα, όπως είναι τα πεπερασμένα σώματα  GF(''p'')  που περιγράφτηκαν ανωτέρω. Τα αντίστοιχα συμπεράσματα σχετικά με την Ευκλείδειο αλγόριθμο και τις εφαρμογές τους γενικεύονται και στον πολυωνυμικό αλγόριθμο.

=== Ακέραιοι Gaussian ===
[[File:Gaussian primes.svg|thumb|alt="A set of dots lying within a circle. The pattern of dots has fourfold symmetry, i.e., rotations by 90 degrees leave the pattern unchanged. The pattern can also be mirrored about four lines passing through the center of the circle: the vertical and horizontal axes, and the two diagonal lines at ±45 degrees."|Distribution of Gaussian primes ''u''&nbsp;+&nbsp;''vi'' in the complex plane, with norms ''u''<sup>2</sup>&nbsp;+&nbsp;''v''<sup>2</sup> less than 500]]

Οι ακέραιοι Gaussian είναι [[μιγαδικοί αριθμοί]] της μορφής α&nbsp;=&nbsp;''u''&nbsp;+&nbsp;''vi'' , όπου "u" και "v" είναι απλοί [[ακέραιοι]] και i είναι η τετραγωνική ρίζα του -1 .<ref name="Stillwell_2003" /> Με τον καθορισμό ενός αναλόγου Ευκλείδειου αλγόριθμο,οι Gaussian ακέραιοι ,μπορεί να αποδειχθεί ότι είναι μοναδικά κατασκευάσιμοι,σύμφωνα με το επιχείρημα [[#Bézout's identity|above]] .<ref name="Gauss_1832">{{cite journal | author = [[Carl Friedrich Gauss|Gauss CF]] | year = 1832 | title = Theoria residuorum biquadraticorum | journal = Comm. Soc. Reg. Sci. Gött. Rec. | volume = 4}} See also ''Werke'', '''2''':67–148.</ref> Αυτή η μοναδική παραγοντοποίηση είναι χρήσιμη σε πολλές εφαρμογές, όπως στις [[πυθαγόρειες τριάδες]] ή στην απόδειξη του [[Θεώρημα του Φερμά|θεώρηματος του Φερμά]] για τα άθροισμα των τετραγώνων δύο αριθμών .<ref name="Stillwell_2003">{{Harvnb|Stillwell|2003|pp=101–116}}</ref> Σε γενικές γραμμές, ο Ευκλείδειος αλγόριθμος είναι βολικός σε τέτοιες εφαρμογές, αλλά δεν είναι απαραίτητος, για παράδειγμα, τα θεωρήματα μπορούν συχνά να αποδειχθεί ,με άλλους τρόπους.

Ο Ευκλείδειος αλγόριθμος που αναπτύχθηκε για δύο Gaussian ακέραιους α και β είναι σχεδόν ίδιος με εκείνον για τους απλούς ακέραιους, αλλά διαφέρει σε δύο σημεία. Όπως και πριν, το έργο σε κάθε βήμα "k" είναι να προσδιορίσει ένα πηλίκο  ''q''<sub>''k''</sub> και ένα υπόλοιπο ''r''<sub>''k''</sub> τέτοια ώστε
: ''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>

όπου ''r''<sub>''k''−2</sub>&nbsp;=&nbsp;α, ''r''<sub>''k''−1</sub>&nbsp;=&nbsp;β, και κάθε υπόλοιπο είναι αυστηρά μικρότερο από το προηγούμενο του, |''r''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''−1</sub>|. Η πρώτη διαφορά είναι ότι τα πηλίκα και τα υπόλοιπα είναι ακέραιοι Gaussian, και έτσι είναι [[μιγαδικοί αριθμοί]] . Τα πηλίκα  ''q''<sub>''k''</sub> γενικά βρίσκονται στρογγυλοποιώντας τα πραγματικά και μιγαδικά μέρη της ακριβούς αναλογίας (όπως το μιγαδικό αριθμό α / β) στους πλησιέστερους ακέραιους. Η δεύτερη διαφορά έγκειται στην αναγκαιότητα του καθορισμού πώς ένα μιγαδικό υπόλοιπο μπορεί να είναι "μικρότερο" από ένα άλλο. Για να γίνει αυτό, ορίζουμε μια [[συνάρτηση]] ''f''(''u'' + ''v''i) = ''u''<sup>2</sup> + ''v''<sup>2</sup> , η οποία μετατρέπει κάθε Gaussian ακέραιο ''u'' + ''vi'' σε έναν κανονικό ακέραιο. Μετά από κάθε βήμα "k" του Ευκλείδειου αλγόριθμου, η τιμή του υπολοίπου ''f''(''r''<sub>''k''</sub>) είναι μικρότερη από την τιμή του προηγούμενου υπολοίπου, ''f''(''r''<sub>''k''−1</sub>). Δεδομένου ότι η τιμή είναι ένας μη αρνητικός ακέραιος αριθμός και μειώνεται σε κάθε βήμα, ο Ευκλείδειος αλγόριθμος για Gaussian ακέραιους ολοκληρώνεται σε ένα πεπερασμένο αριθμό βημάτων. Το τελικό μη μηδενικό υπόλοιπο αποτελεί το  ΜΚΔ(α, β), ο Gaussian ακέραιος με τη μεγαλύτερη τιμή που διαιρεί και το α και το β. Είναι μοναδικός με πολλαπλασιασμό με τη μονάδα, ± 1, ± ή i .

Πολλές από τις άλλες εφαρμογές του Ευκλείδειου αλγόριθμου μεταφέρονται στους Gaussian ακέραιους. Για παράδειγμα, μπορεί να χρησιμοποιηθεί για την επίλυση γραμμικών διοφαντικών εξισώσεων και Κινέζικα προβλήματα για τα υπολοιπα των Gaussian ακεραίων  Συνεχή κλάσματα Gaussian ακεραίων μπορούν επίσης να οριστούν.

===Ευκλείδειες δομές===

Μια σειρά από στοιχεία μεταξύ των οποίων γίνονται [[δυαδικές πράξεις]] ,+ και ·, ονομάζονται Euclidean domains όταν σχηματίζουν [[αντιμεταθετικό δακτύλιο R]] και, σε γενικές γραμμές, αν ο γενικός Ευκλείδειος αλγόριθμος μπορεί να εφαρμοστεί σε αυτούς <ref>{{Harvnb|Stark|1978|p=290}}</ref><ref>{{Harvnb|Cohn|1962|pp=104–105}}</ref>. Οι δύο πράξεις ενός τέτοιου δακτυλίου δεν χρειάζεται να είναι η πρόσθεση και πολλαπλασιασμός της συνήθους αριθμητικής.αντίθετα, μπορούν να είναι πιο γενικά, όπως οι πράξεις σε μια [[ομάδα]] ή σε ένα [[μονοειδές]] . Παρ 'όλα αυτά, αυτές οι γενικές πράξεις θα πρέπει να υπακούν τους κανόνες που διέπουν τις συνήθεις αριθμητικές πράξεις, όπως [[προσεταιριστικότητα]], [[αντιμεταθετικότητα]] και [[επιμεριστικότητα]] .

ο γενικευμένος Ευκλείδειος αλγόριθμος απαιτεί μια "Ευκλείδεια συνάρτηση" , δηλαδή, μια απεικόνιση ''f'' από το "R" στο σύνολο των θετικών ακέραιων τέτοια ώστε, για κάθε δύο μη μηδενικά στοιχεία a και b του "R" ,να υπάρχουν "q" και "r" στο "R" τέτοια ώστε ''a'' =''qb'' + ''r'' και ''f''(''r'') < ''f''(''b''). Ένα παράδειγμα αυτής της απεικόνισης είναι συνάρτηση που χρησιμοποιείται για να διατάξουμε του Gaussian ακέραιους . Η συνάρτηση f μπορεί να είναι η δύναμη ενός αριθμού, ή ο [[βαθμός ενός πολυωνύμου]] . Η βασική αρχή είναι ότι σε κάθε βήμα του αλγορίθμου η "f" μειώνεται συνεχώς. Ως εκ τούτου, εάν η "f" μπορεί να μειωθεί μόνο έναν πεπερασμένο αριθμό φορών, ο αλγόριθμος πρέπει να σταματήσει σε έναν πεπερασμένο αριθμό βημάτων. Η αρχή αυτή στηρίζεται σε μεγάλο βαθμό στην [[αρχή της καλής διάταξης]] των μη-αρνητικών ακεραίων.σε γενικές γραμμές, αυτό προϋποθέτει ότι κάθε σύνολο των μη-αρνητικών ακεραίων έχει ελάχιστο στοιχείο.

Το [[θεμελιώδες θεώρημα της αριθμητικής]] ισχύει για κάθε Ευκλείδεια δομή: Οποιοσδήποτε αριθμός από μία Ευκλείδεια δομη μπορεί να αναλυθεί κατά μοναδικό τρόπο σε [[ανάγωγα στοιχεία]]. Κάθε Ευκλείδεια δομή είναι [[πολλαπλασιαστικός δακτύλιος]], αν και το αντίστροφο δεν ισχύει. Η Ευκλείδεια δομή και το UFD είναι υποομάδες της ομάδας των ακεραίων που ανα δύο έχουν μέγιστο κοινό διαρέτη , ομάδες στις οποίες ο μέγιστος κοινός διαιρέτης δύο αριθμών υπάρχει πάντα. Με άλλα λόγια, ένας μέγιστος κοινός διαιρέτης μπορεί να υπάρχει (για όλα τα ζεύγη των στοιχείων μιας ομάδας), αν και μπορεί να μην είναι δυνατόν να βρεθεί χρησιμοποιώντας ένα Ευκλείδειο αλγόριθμο. Μια Ευκλείδεια δομή είναι πάντα μια ομάδα [[principal ideal domain]]  (PID), μια ακεραία περιοχή στην οποία το μοναδιαίο στοιχείο του δακτυλίου είναι μοναδικό  . Και πάλι, το αντίστροφο δεν ισχύει: δεν είναι κάθε PID είναι μια Ευκλείδεια δομή.

Η μοναδική παραγοντοποίηση της Ευκλείδειας δομής είναι χρήσιμη σε πολλές εφαρμογές. Για παράδειγμα, η μοναδική παραγοντοποίηση των ακεραίων Gaussian είναι χρήσιμη στο να προκύπτουν τύποι για όλες τις πυθαγόρειες τριάδες και οδηγεί στην απόδειξη του [[θεώρηματος του Φερμά]] για το άθροισμα των τετραγώνων δύο αριθμών . .<ref name="Stillwell_2003" /> Η μοναδική παραγοντοποίηση ήταν επίσης ένα βασικό στοιχείο σε μια απόπειρα απόδειξης του Τελευταίου Θεωρήματος του Φερμά [[Fermat's Last Theorem]] που δημοσιεύθηκε το 1847 από τον Gabriel Lamé, ο ίδιος μαθηματικός ο οποίος ανέλυσε την αποτελεσματικότητα του αλγορίθμου του Ευκλείδη, που βασίζεται σε πρόταση του [[Joseph Liouville]].<ref>{{cite journal | author = Lamé G | year = 1847 | title = Mémoire sur la résolution, en nombres complexes, de l'équation A<sup>n</sup> + B<sup>n</sup> + C<sup>n</sup> = 0 | journal = J. Math. Pures Appl. | volume = 12 | pages = 172–184}}</ref> η προσέγγιση Lamé απαιτούσε τη μοναδική παραγοντοποίηση των αριθμών της μορφής "x" + ω"y" , όπου "x" και "y" είναι ακέραιοι, και ω = ''e''<sup>2''i''π/''n''</sup> είναι "n" ρίζα της μονάδας, δηλαδή, ω<sup>''n''</sup> = 1.  Αν και αυτή η προσέγγιση ισχύει για ορισμένες τιμές των "n" (όπως το "n" = 3, τους [[ακέραιους Eisenstein]]), σε γενικές γραμμές τέτοιοι αριθμοί δεν παραγοντοποιούνται μοναδικά. Αυτή η αποτυχία της μοναδικής παραγοντοποίησης στους τομείς [[cyclotomic field]] οδήγησε τον [[Ernst Kummer]] στην σύλληψη των [[ideal numbers]] και, αργότερα,τον [[Richard Dedekind]] στην [[θεωρία των ιδανικών]].{{citation needed|date=March 2010}}

===Μοναδική παραγοντοποίηση των τετραγωνικών ακεραίων===

[[File:Eisenstein primes.svg|thumb|alt="A set of dots lying within a circle. The pattern of dots has sixfold symmetry, i.e., rotations by 60 degrees leave the pattern unchanged. The pattern can also be mirrored about six lines passing through the center of the circle: the vertical and horizontal axes, and the four diagonal lines at ±30 and ±60 degrees."|Distribution of Eisenstein primes ''u''&nbsp;+&nbsp;''v''ω in the complex plane, with norms less than 500. The number ω equals the [[root of unity|cube root of 1]].]]

Οι [[τετραγωνικοί ακέραιοι δακτυλίοι]]  είναι χρήσιμοι στις Ευκλείδειες δομές.Οι τετραγωνικοί ακέραιοι αποτελούν γενικευση των Gaussian ακεραίων στις οποίες το [[φανταστικό]] ''i'' αντικαθίσταται από ένα ω αριθμό. Έτσι, έχουν τη μορφή "u" + "v" ω, όπου "υ" και "ν" είναι ακέραιοι και ω έχει μία από τις δύο μορφές, ανάλογα με την παράμετρο "D" . Εάν "D" δεν ισούται με ένα πολλαπλάσιο του τέσσερα συν ένα, τότε
: ω = √''D''.

Εάν, ωστόσο, D είναι ίσο με ένα πολλαπλάσιο του τέσσερα συν ένα, τότε
: ω = (1 + √''D'')/2.

Αν η συνάρτηση f αντιστοιχεί σε μια [[field norm|norm]] συνάρτηση, όπως αυτή που χρησιμοποιείται για να διατάξει τους Gaussian ακέραιους [[#Gaussian integers|above]], τότε η δομή είναι γνωστή ως [[κανόνας-Ευκλείδη]]( ''[[Norm-Euclidean field|norm-Euclidean]]''). Οι norm-euclidean τετραγωνικοί ακέραιοι δακτύλιοι είναι ακριβώς εκείνοι όπου ''D''&nbsp;=&nbsp;  -11, -7, -3, -2, -1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29 , 33, 37, 41, 57 ή 73 .<ref name="Cohn_1962" /><ref>{{cite book | last = LeVeque | first = William J. | authorlink = William J. LeVeque | title = Topics in Number Theory, Volumes I and II | url = https://archive.org/details/topicsinnumberth0000leve | publisher = Dover Publications | location = New York | year = 2002 | origyear = 1956 | isbn = 978-0-486-42539-9 | zbl=1009.11001 | pages=II:57,81}}</ref> Οι τετραγωνικοί ακέραιοι με ''D''&nbsp;=&nbsp; -1 και -3  είναι γνωστοί ως [[Gaussian ακέραιοι]] και [[Eisenstein ακέραιοι]] αντίστοιχα.

Αν ''f'' επιτρέπεται να είναι οποιαδήποτε Ευκλείδεια συνάρτηση, τότε οι πιθανές τιμές του D  για τις οποίες η δομή είναι Ευκλείδεια δεν είναι ακόμη γνωστοί.<ref name="Clark_1994">{{cite journal | last = Clark | first = David A. | year = 1994 | title = A quadratic field which is Euclidean but not norm-Euclidean | journal = [[Manuscripta Mathematica]] | volume = 83 | pages = 327–330 | doi = 10.1007/BF02567617 | url = http://www.springerlink.com/content/6t9u2440402n1346/ | zbl = 0817.11047 }}{{Dead link|date=Φεβρουάριος 2020 }}</ref>   Το πρώτο παράδειγμα μιας Ευκλείδειας δομής που δεν ήταν κανόνας-Ευκλείδη (με ''D''  = 69) δημοσιεύθηκε το 1994.<ref name="Clark_1994" /> Το 1973,ο Weinberger απέδειξε ότι ένας τετραγωνικός ακέραιος δακτύλιος με ''D''&nbsp;>&nbsp;0 είναι Ευκλείδειος αν, και μόνο αν, είναι [[principal ideal domain]], υπό την προϋπόθεση ότι η γενικευμένη υπόθεση Riemann κατέχει..<ref>{{cite journal | author = Weinberger P | chapter = On Euclidean rings of algebraic integers | journal = Proc. Sympos. Pure Math. | volume = 24 | pages = 321–332}}</ref>

===Μη αντιμεταθετικοί δακύλιοι===

Είναι επίσης δυνατό να εφαρμοστεί ο Ευκλείδειος αλγόριθμος για μη αντιμεταθετικούς δακτυλίους όπως το σύνολο των [[Hurwitz quaternions]] .<ref>{{Harvnb|Stillwell|2003|pp=151–152}}</ref> Έστω α και β αντιπροσωπεύουν δύο στοιχεία από ένα τέτοιο δακτύλιο. Έχουν ένα κοινό δεξί διαιρέτη δ, αν α = ξδ και β = ηδ για κάποια επιλογή του ξ και η στο δακτυλίο. Ομοίως, έχουν ένα κοινό αριστερό διαιρέτη εάν α = δξ και β = δη για κάποια επιλογή του ξ και η στον δακτύλιο. μιας και ο πολλαπλασιασμός δεν είναι αντιμεταθετικός, υπάρχουν δύο εκδοχές του ευκλείδειου αλγόριθμου, μία για τους δεξιούς διαιρέτες και μία για τους αριστερούς διαιρέτες. Η επιλογή των σωστών διαιρέτων, πρώτο βήμα στην εύρεση του ΜΚΔ (α, β) από τον Ευκλείδειο αλγόριθμο, μπορεί να γραφτεί
: ρ<sub>0</sub> = α − ψ<sub>0</sub>β = (ξ − ψ<sub>0</sub>η)δ

όπου ψ<sub>0</sub> αντιπροσωπεύει το πηλίκο και το  ρ<sub>0</sub>  το υπόλοιπο. Αυτή η εξίσωση δείχνει ότι κάθε κοινός δεξιός διαιρέτης των α και β είναι επίσης κοινός διαιρέτης του υπολοίπου ρ<sub>0</sub> . Η ανάλογη εξίσωση για τους αριστερούς διαιρέτες θα ήταν
: ρ<sub>0</sub> = α − βψ<sub>0</sub> = δ(ξ − ηψ<sub>0</sub>)

Με οποιαδήποτε επιλογή, η διαδικασία επαναλαμβάνεται όπως παραπάνω έως ότου ο μεγαλύτερος κοινός δεξιός ή αριστερός διαιρέτης έχει βρεθεί. Όπως και στην Ευκλείδεια δομή, το "μέγεθος" του ρ<sub>0</sub> πρέπει να είναι αυστηρά μικρότερο από β, και πρέπει να υπάρχει μόνο ένας πεπερασμένος αριθμός πιθανών μεγεθών για  ρ<sub>0</sub> , έτσι ώστε ο αλγόριθμος να τερματίσει σίγουρα.

Τα περισσότερα από τα αποτελέσματα για το ΜΚΔ μεταφέρονται στους μη αντιμεταθετικούς αριθμούς. Για παράδειγμα, η [[ταυτότητα του Bézout]] δηλώνει ότι ο δεξιός ΜΚΔ(α, β) μπορεί να εκφραστεί ως γραμμικός συνδυασμός των α και β.Με άλλα λόγια, υπάρχουν σ και τ τέτοια ώστε
: Γ<sub>right</sub> = σα + τβ

Η ανάλογη ταυτότητα για τον αριστερό ΜΚΔ είναι σχεδόν η ίδια
: Γ<sub>left</sub> = ασ + βτ

Η ταυτότητα του Bézout μπορεί να χρησιμοποιηθεί για την επίλυση διοφαντικών εξισώσεων.

===Γενίκευση σε άλλες μαθηματικές δομές===
[[File:TorusKnot3D.png|thumb|alt="A cord wound seven times around a torus and reconnected to its beginning, forming a closed loop. In the process, the cord completes three circuits of the torus, forming a (3, 7) torus knot."|The Euclidean algorithm can be applied in [[knot theory]].<ref>{{cite arxiv | author = Yamada Y | year = 2007 | title = Generalized rational blow-down, torus knots, and Euclidean algorithm | publisher = | eprint=0708.2316 | class = math.GT}}</ref>]]

Ο Ευκλείδειος αλγόριθμος έχει τρία γενικά χαρακτηριστικά που εξασφαλίζουν από κοινού ότι δεν θα συνεχιστεί επ 'αόριστον. Πρώτον, αυτό μπορεί να γραφτεί ως μια ακολουθία των αναδρομικών εξισώσεων
: ''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>

όπου κάθε υπόλοιπο είναι αυστηρά μικρότερο από το προηγούμενο του, |''r''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''−1</sub>|. Δεύτερον, το μέγεθος του κάθε υπολοίπου έχει ένα ελάχιστο κατώτερο όριο, όπως στα |''r''<sub>''k''</sub>|&nbsp;≥&nbsp;0. . Τρίτον, υπάρχει μόνο ένας πεπερασμένος αριθμός μεγεθών μικρότερων από ένα συγκεκριμένο υπόλοιπο |''r''<sub>''k''</sub>|. Οι γενικεύσεις του αλγορίθμου του Ευκλείδη με αυτά τα βασικά χαρακτηριστικά έχουν εφαρμοστεί σε άλλες μαθηματικές δομές, όπως [[tangle (mathematics)|tangles]]<ref>{{cite book|title=Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967)|first=John|last=Conway|publisher=Pergamon|isbn=|year=1970|location=|page=|pages=329–358|quote=|contribution=An enumeration of knots and links, and some of their algebraic properties}}</ref> και στα [[transfinite number|transfinite]] [[ordinal number]]s.<ref>{{cite journal | author = Jategaonkar AV | year = 1969 | title = Rings with transfinite left division algorithm | journal = Bull. Amer. Math. Soc. | volume = 75 | pages = 559–561 | doi = 10.1090/S0002-9904-1969-12242-1 | url=http://projecteuclid.org/euclid.bams/1183530557 | issue = 3}}</ref>

Μια σημαντική γενίκευση του ευκλείδειου αλγόριθμου είναι η έννοια της [[Gröbner basis]] στην [[αλγεβρική γεωμετρία]] . Όπως φαίνεται από τα παραπάνω, ο ΜΚΔ g δύο ακεραίων a και b δημιουργεί τον [[ιδανικό]] τους . Με άλλα λόγια, για κάθε επιλογή των ακεραίων s και t , υπάρχει ένα άλλος ακέραιος m τέτοιος ώστε
: ''sa'' + ''tb'' = ''mg''.

Αν και αυτό εξακολουθεί να ισχύει όταν ''s'' , ''t'' , ''m'' , ''α'' και ''b'' αντιπροσωπεύουν πολυώνυμα μιας μεταβλητής, δεν ισχύει για τους δακτυλίους με περισσότερες από μία μεταβλητές.<ref>{{Harvnb|Cox|Little|O'Shea|1997|p=65}}</ref> Στην περίπτωση αυτή, ένα πεπερασμένο σύνολο των πολυωνύμων ''g''<sub>1</sub>, ''g''<sub>2</sub> , κλπ. μπορεί να οριστεί έτσι ώστε κάθε γραμμικός συνδυασμός των δύο πολυωνύμων πολλών μεταβλητών α και β μπορεί να εκφράζεται ως πολλαπλάσια των γεννητριών
: ''sa'' + ''tb'' = Σ<sub>''k''</sub> ''m''<sub>''k''</sub>''g''<sub>''k''</sub>

όπου ''s'', ''t'' και ''m''<sub>''k''</sub> είναι πολυώνυμα πολλών μεταβλητών.<ref>{{Harvnb|Cox|Little|O'Shea|1997|pp=73–79}}</ref> Κάθε τέτοιο πολυώνυμο πολυμεταβλητών η ''f'' μπορεί να εκφραστεί ως ένα τέτοιο άθροισμα των γενεσιουργών πολυωνύμων συν ένα μοναδικό πολυώνυμο-υπόλοιπο ''R'' ,που μερικές φορές ονομάζεται η κανονική μορφή του πολυωνύμου ''f''
: ''f'' = ''r'' + Σ<sub>''k''</sub> ''q''<sub>''k''</sub>''g''<sub>''k''</sub>

παρόλο που το πολυώνυμο πηλίκο ''q''<sub>''k''</sub>  μπορεί να μην είναι μοναδικό.<ref>{{Harvnb|Cox|Little|O'Shea|1997|pp=79–86}}</ref> The set of these generator polynomials is known as a Gröbner basis.<ref>{{Harvnb|Cox|Little|O'Shea|1997|p=74}}</ref>
Το σύνολο αυτών των γενεσιουργών πολυωνύμων  είναι γνωστό ως βάση.

==Παραπομπές==
<references />

==Βιβλιογραφία==
* {{cite book |last=Cohen |first=Henri |author-link=:en:Henri Cohen (number theorist) |year=1993 |title=A Course in Computational Algebraic Number Theory |url=http://books.google.com/?id=hXGr-9l1DXcC |publisher=Springer-Verlag |location=New York |isbn=0-387-55640-0 |ref=harv |doi=}}
* {{cite book |last=Cohn |first=H. |year=1962 |title=Advanced Number Theory |url=http://books.google.com/?id=yMGeElJ8M0wC |publisher=Dover |location = New York |isbn=0-486-64023-X |ref=harv |doi= }}
* {{cite book|first=[[:en:Ronald L. Rivest|Rivest RL]]|author=[[:en:Thomas H. Cormen|Cormen TH]]|first2=[[:en:Clifford Stein|Stein C]]|year=2001|title=Introduction to Algorithms|page=|url=http://books.google.com/?id=NLngYyWFl_YC|quote=|edition=2nd|location=|last2=[[:en:Charles E. Leiserson|Leiserson CE]]|publisher=MIT Press and McGraw–Hill|isbn=0-262-03293-7}}
* {{cite book |last1=Cox |first1=D |last2=Little |first2=J |last3=O'Shea |first3=D |year=1997 |title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra |url=http://books.google.com/?id=7eLkq0wQytAC |edition=2nd |publisher = Springer-Verlag |isbn=0-387-94680-2 |doi= |ref=harv }}
* {{cite book|last=Lejeune Dirichlet|first=Peter Gustav|author-link=:en:Peter Gustav Lejeune Dirichlet|isbn=|year=1894|title=Vorlesungen über Zahlentheorie (Lectures on Number Theory)|editor-last=Dedekind|editor-first=Richard|editor-link=:en:Richard Dedekind|publisher=Vieweg|location=Braunschweig|language=de|page=|url=http://books.google.com/books?id=WZIKAAAAYAAJ&printsec=frontcover&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false|lccn=03005859|oclc=490186017|doi=|quote=|ref=harv}}
* {{cite book | author = [[:en:G. H. Hardy|Hardy GH]], [[:en:E. M. Wright|Wright EM]] [revised by D.R. Heath-Brown and J.H. Silverman]. | year = 2008|url = http://books.google.com/?id=rey9wfSaJ9EC | title =An Introduction to the Theory of Numbers|edition = 6th|publisher=Clarendon Press|location =Oxford | isbn = 978-0-19-921986-5}}
* {{cite book|author=[[:en:Donald Knuth|Knuth D]]|year=1997|title=[[The Art of Computer Programming]], Volume 2: Seminumerical Algorithms|edition=3rd|publisher=Addison–Wesley| isbn=0-201-89684-2}}
* {{cite book | last=LeVeque |first=William J. |author-link=:en:William J. LeVeque |origyear=1977 |year=1996 |title=Fundamentals of Number Theory | url=https://archive.org/details/fundamentalsofnu0000leve |publisher=Dover |location=New York |isbn=0-486-68906-9 |ref=harv }}
* {{cite book |last=Mollin |first=R. A. |year=2008 |title=Fundamental Number Theory with Applications |edition=2nd |publisher=Chapman & Hall/CRC |location=Boca Raton |isbn=978-1-4200-6659-3 |ref=harv }}
* {{cite book |last=Ore |first=Øystein |author-link=:en:Øystein Ore |year=1948 |title=Number Theory and Its History |url=https://archive.org/details/numbertheoryitsh00ore |publisher=McGraw–Hill |location=New York |ref=harv |doi= }}
* {{cite book |last=Rosen |first=K. H. |year=2000 |title=Elementary Number Theory and its Applications |edition=4th |publisher=Addison–Wesley |location=Reading, MA |isbn=0-201-87073-8 |ref=harv |doi= }}
* {{cite book |last=Schroeder |first=Manfred |author-link=:en:Manfred R. Schroeder |year=2005 |title=Number Theory in Science and Communication |edition=4th |publisher=Springer-Verlag |isbn= 0-387-15800-6 |ref=harv |doi= }}
* {{cite book |last=Stark |first=Harold |author-link=:en:Harold Stark |year=1978 |title=An Introduction to Number Theory |publisher=MIT Press |isbn=0-262-69060-8 |ref=harv |url-access=registration |url=https://archive.org/details/introductiontonu00star_0 }}
* {{cite book |last=Stillwell |first=John |author-link=:en:John Stillwell |year=1997 |title=Numbers and Geometry |publisher=Springer-Verlag |location=New York |isbn=0-387-98289-2 |doi= |ref=harv }}
*{{cite book |last=Stillwell |first=John |author-link=:en:John Stillwell |year=2003 |title=Elements of Number Theory |publisher=Springer-Verlag |location=New York |isbn=0-387-95587-9 |doi= |ref=harv }}
* {{cite book |last=Tattersall |first=J. J. |year=2005 |title=Elementary number theory in nine chapters |url=https://archive.org/details/elementarynumber0000jame |publisher=[[Cambridge University Press]] |location=Cambridge |isbn = 978-0-521-85014-8 |ref=harv }}
* {{cite book | author = Uspensky JV, Heaslet MA | year = 1939 | title = Elementary Number Theory | publisher = McGraw–Hill | location = New York }}

==Εξωτερικοί σύνδεσμοι==
{{Commons category|Euclidean algorithm}}
* [http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html Demonstrations of Euclid's algorithm]
* {{MathWorld | urlname=EuclideanAlgorithm | title=Euclidean Algorithm}}
* [http://www.cut-the-knot.org/blue/Euclid.shtml Euclid's Algorithm] at cut-the-knot
* [http://www.mathpages.com/home/kmath384.htm The Euclidean Algorithm] at MathPages
* [http://www.cut-the-knot.org/blue/EuclidAlg.shtml Euclid's Game] at cut-the-knot
* [http://plus.maths.org/issue40/features/wardhaugh/index.html Music and Euclid's algorithm]

{{DEFAULTSORT:Euclidean Algorithm}}
[[Κατηγορία:Αλγόριθμοι]]