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

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

Ο Αλγόριθμος του Ευκλείδη είναι μία από τις αρχαιότερες και πιο κομψές μεθόδους υπολογισμού του Μέγιστου Κοινού Διαιρέτη (ΜΚΔ) δύο ακεραίων. Παρουσιάστηκε στα «Στοιχεία» του Ευκλείδη (~300 π.Χ.).

Βασική Ιδέα

Ο αλγόριθμος βασίζεται στην εξής θεμελιώδη ιδιότητα:

Λήμμα: Για ακεραίους $a \geq b > 0$:

$$\gcd(a, b) = \gcd(b, a \mod b)$$

όπου $a \mod b$ είναι το υπόλοιπο της διαίρεσης του $a$ με το $b$.

Απόδειξη: Αν $a = bq + r$ (Ευκλείδεια διαίρεση), τότε κάθε κοινός διαιρέτης των $a, b$ διαιρεί και το $r = a - bq$, και αντίστροφα.

Ο Αλγόριθμος

Είσοδος: Δύο μη αρνητικοί ακέραιοι $a, b$ (όχι και οι δύο μηδέν)

Έξοδος: $\gcd(a, b)$

Βήματα:

1. Αν $b = 0$, επέστρεψε $a$
2. Αλλιώς, υπολόγισε $r = a \mod b$
3. Επανέλαβε με $(a, b) \leftarrow (b, r)$

Ψευδοκώδικας:

Συνάρτηση ΜΚΔ(a, b):
    Όσο b ≠ 0:
        r ← a mod b
        a ← b
        b ← r
    Επέστρεψε a

Παράδειγμα Εκτέλεσης

Να βρεθεί ο $\gcd(252, 105)$:

Άρα $\gcd(252, 105) = 21$.

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

Ο επεκτεταμένος αλγόριθμος βρίσκει, εκτός από τον ΜΚΔ, και ακεραίους $x, y$ τέτοιους ώστε:

$$\gcd(a, b) = ax + by$$

Αυτή είναι η Ταυτότητα του Bézout.

Θεώρημα (Bézout): Για ακεραίους $a, b$ (όχι και οι δύο μηδέν), υπάρχουν ακέραιοι $x, y$ ώστε:

$$ax + by = \gcd(a, b)$$

Ο Επεκτεταμένος Αλγόριθμος

Μέθοδος αντίστροφης αντικατάστασης:

1. Εκτέλεσε τον απλό αλγόριθμο, κρατώντας όλα τα βήματα
2. Ξεκίνα από το τελευταίο μη μηδενικό υπόλοιπο (= ΜΚΔ)
3. Εκφράζοντάς το ως γραμμικό συνδυασμό, αντικατέστησε αντίστροφα

Εφαρμογές

1. Εύρεση Αντιστρόφου modulo $n$

Αν $\gcd(a, n) = 1$, από την ταυτότητα Bézout:

$$ax + ny = 1$$

Άρα $ax \equiv 1 \pmod{n}$, δηλαδή $x = a^{-1} \pmod{n}$.

2. Επίλυση Γραμμικών Διοφαντικών Εξισώσεων

Η εξίσωση $ax + by = c$ έχει ακέραιες λύσεις αν και μόνο αν $\gcd(a, b) \mid c$.

3. Απλοποίηση Κλασμάτων

Το κλάσμα $\frac{a}{b}$ απλοποιείται διαιρώντας με $\gcd(a, b)$.

Πολυπλοκότητα

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

• Χειρότερη περίπτωση: Διαδοχικοί αριθμοί Fibonacci
• Πλήθος βημάτων: $O(\log(\min(a, b)))$

Θεώρημα Lamé: Ο αριθμός βημάτων δεν υπερβαίνει το πενταπλάσιο του πλήθους ψηφίων του μικρότερου αριθμού.