Ένας αλγόριθμος 2.300 ετών και ένα απρόσμενο μυστικό

Ο Εμίλ Λεζέ (Émile Léger) γεννήθηκε στις 15 Αυγούστου 1795 στο Lagrange-aux-Bois της Γαλλίας και πέθανε στις 15 Δεκεμβρίου 1838 στο Παρίσι. Αν και δημοσίευσε μόλις τέσσερις μαθηματικές εργασίες, σε μία από αυτές φαίνεται να υπάρχει ίσως η πρώτη αναφορά σε ένα γεγονός που σήμερα είναι πολύ γνωστό και αφορά τον Ευκλείδειο αλγόριθμο.

Ο Léger μελέτησε σε βάθος τη σχέση ανάμεσα στον Ευκλείδειο αλγόριθμο και στην ανάπτυξη των πραγματικών αριθμών σε συνεχή κλάσματα. Εφόσον ο Ευκλείδειος αλγόριθμος βρίσκεται ουσιαστικά στη βάση της ανάπτυξης ενός ρητού αριθμού (a/b) σε συνεχές κλάσμα, τον ενδιέφεραν ιδιαίτερα:

-ο αριθμός των βημάτων που απαιτούνται μέχρι να τερματιστεί ο αλγόριθμος,

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

-η δομή και η περιοδικότητα των συνεχών κλασμάτων στην περίπτωση των τετραγωνικών αρρήτων και το πώς αυτή αντανακλάται στα βήματα του Ευκλείδειου αλγορίθμου.

Ο Émile Léger φαίνεται πως ήταν ο πρώτος —ή ο δεύτερος, αν συνυπολογιστεί παλαιότερη εργασία του de Lagny— που αναγνώρισε ότι η χειρότερη περίπτωση του Ευκλείδειου αλγορίθμου εμφανίζεται όταν οι δύο αριθμοί εισόδου είναι διαδοχικοί αριθμοί Fibonacci.

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

                                                   13,21,    21,34,     34,55,

δηλαδή διαδοχικοί όροι της ακολουθίας Fibonacci.

Ο Ευκλείδειος αλγόριθμος, που συχνά διδάσκεται ήδη από τις πρώτες σχολικές βαθμίδες ως μια απλή μέθοδος εύρεσης του Μέγιστου Κοινού Διαιρέτη (ΜΚΔ) δύο αριθμών, κρύβει έτσι πίσω του μια εντυπωσιακή σύνδεση με τα συνεχή κλάσματα και με μία από τις διασημότερες ακολουθίες των μαθηματικών: την ακολουθία Fibonacci.