2.2 Μέγιστος κοινός διαιρέτης, ελάχιστο κοινό πολλαπλάσιο, αλγόριθμος του Ευκλείδη

Ορισμός 2.3   (Μέγιστος κοινός διαιρέτης) Αν είναι $a, b$ θετικοί ακέραιοι τότε ονομάζουμε μέγιστο κοινό διαιρέτη των $a, b$ το μέγιστο $d$ που διαιρεί και το $a$ και το $b$. Το συμβολίζουμε με $(a,b)$.

Ορισμός 2.4   (Ελάχιστο κοινό πολλαπλάσιο) Αν είναι $a, b$ θετικοί ακέραιοι τότε ονομάζουμε ελάχιστο κοινό πολλαπλάσιο των $a, b$ το ελάχιστο $n$ τέτοιο ώστε και το $a$ και το $b$ διαιρούν το $n$. Το συμβολίζουμε με $[a, b]$.

Οι παραπάνω ορισμοί γενικεύονται κατά προφανή τρόπο σε περισσότερους από δύο αριθμούς.

Παράδειγμα 2.1   Έχουμε

$$(10, 15) = 5, [10, 15] = 30.$$

Επίσης

$$(7, 11) = 1, [7, 11] = 77.$$

Για κάθε θετικό ακέραιο $a$ έχουμε $(1, a) = 1$, $[1, a] = a$, $(a, a) = a$, $[a, a] = a$.

Θεώρημα 2.2   Αν $a, b$ είναι δύο θετικοί ακέραιοι τότε υπάρχουν δύο ακέραιοι $k, l$ τέτοιοι ώστε

$$(a, b) = k a + l b.$$

Απόδειξη. Έστω το σύνολο $S = {\left\{{xa+yb: x, y\in{\mathbb{Z}}}\right\}}$ όλων των ακέραιων γραμμικών συνδυασμών των $a, b$. Κάθε στοιχείο του $S$ διαιρείται από το $(a,b)$. Ας είναι $d$ ο μικρότερος θετικός ακέραιος του $S$. Αν $d = k a + l b$ τότε κάθε πολλαπλάσιο του $d$ είναι επίσης στο $S$. Θα δείξουμε ότι ισχύει και το αντίστροφο, ότι κάθε στοιχείο του $S$ δηλ. είναι πολλαπλάσιο του $d$.

Έστω $u = xa+yb$, με $x, y \in {\mathbb{Z}}$ και ας γράψουμε την ακέραια διαίρεση $u/d$:

$$u = qd+r, 0 \le r < d.$$

Είναι φανερό ότι $r = u-qd \in S$ (αφού το $S$ είναι κλειστό ως προς ακέραιους γραμμικούς συνδυασμούς). Αν $r>0$ αυτό αντιφάσκει με το γεγονός ότι το $d$ είναι το μικρότερο θετικό στοιχείο του $S$. Άρα $r=0$ και $u=qd$ όπως θέλαμε να δείξουμε.

Αφού $a, b \in S$ έχουμε ότι το $d$ διαιρεί τα $a, b$ αλλά, από την άλλη, $(a,b) \mid d$, το οποίο σημαίνει ότι ο $d$ είναι ένας κοινός διαιρέτης των $a, b$, άρα $d \le (a,b)$. Όμως, όπως παρατηρήσαμε στην αρχή, $(a,b) \mid d$, άρα $d=(a,b)$ και άρα $(a,b) \in S$ και γράφεται ως ακέραιος γραμμικός συνδυασμός των $a, b$. $\qedsymbol$

Άσκηση 2.13   Δείξτε ότι ο μέγιστος κοινός διαιρέτης $k$ ακεραίων επίσης γράφεται ως ακέραιος γραμμικός συνδυασμός των ακεραίων αυτών.

Υπόδειξη: Επαγωγή ως προς $k$ και χρήση του Θεωρήματος 2.2.

Πόρισμα 2.1   Αν $a, b$ είναι θετικοί ακέραιοι και $d \mid a, d \mid b$ τότε $d \mid (a,b)$.

Απόδειξη. O $d$ διαιρεί κάθε ακέραιο γραμμικό συνδυασμό των $a, b$ άρα και το $(a,b)$ λόγω του Θεωρήματος 2.2. $\qedsymbol$

Ορισμός 2.5   (Πολλαπλασιαστικό αντίστροφο mod ένα ακέραιο) Λέμε ότι δύο ακέραιοι $x, y$ είναι πολλαπλασιαστικά αντίστροφα $\bmod b$ αν $xy=1 \bmod b$. Συνήθως γράφουμε $y = \overline{x}$ ή $y = x^{-1}$ αν το $b$ υποννοείται.

Θεώρημα 2.3   Ας είναι $a, b \ge 1$ δύο ακέραιοι. Τότε υπάρχει ακέραιος $x$ τέτοιος ώστε $ax = 1 \bmod b$ αν και μόνο αν $(a, b)=1$. (Υπάρχει δηλ. πολλαπλασιαστικό αντίστροφο του $a \bmod b$.)

Απόδειξη. Αν $d = (a, b)>1$ τότε για κάθε $x \in {\mathbb{Z}}$ έχουμε ότι $d \nmid ax - 1$, και άρα είναι αδύνατο ο $b$ να διαιρεί το $ax-1$.

Αντίστροφα, αν $(a, b)=1$ τότε από το Θεώρημα 2.2 έχουμε ότι υπάρχουν ακέραιοι $x, y$ τέτοιοι ώστε $1 = ax+by$ απ' όπου προκύπτει ότι $ax = 1 \bmod b$. $\qedsymbol$

Άσκηση 2.14   Αν $x, y$ είναι δύο πολλαπλασιαστικά αντίστροφα $\bmod b$ του $a$ τότε $x = y \bmod b$.

Πώς μπορείς κανείς να υπολογίσει το μέγιστο κοινό διαιρέτη δύο θετικών ακεραίων;

Λήμμα 2.1   Αν $a \ge b$ είναι δύο θετικοί ακέραιοι τότε

1. Αν $b \mid a$ τότε $(a, b) = b$.
2. Αν $b \nmid a$ τότε $(a, b) = (b, r)$ όπου $r>0$ είναι το υπόλοιπο της διαίρεσης $a/b$.

Απόδειξη. Η πρώτη πρόταση είναι προφανής.

Αν $a = qb+r$ είναι η ακέραια διαίρεση $a/b$ τότε $r = a-qb$ άρα $(a, b) \mid r$ και, αφού $(a, b) \mid b$ έπεται ότι $(a, b) \mid (b, r)$. Όμως $(b, r) \mid a$ και άρα $(b, r) \mid (a, b)$, άρα

$$(a, b) = (b, r),$$

όπως έπρεπε να δείξουμε. $\qedsymbol$

Η προηγούμενη πρόταση είναι ουσιαστικά ο αλγόριθμος του Ευκλείδη για τον υπολογισμό του μέγιστου κοινού διαιρέτη δύο θετικών ακεραίων $a, b$. Δηλ. αντικαθιστούμε τον μεγαλύτερο από τους δύο, έστω $a$, από το υπόλοιπο της διαίρεσής του διά του μικροτέρου. Αν το υπόλοιπο αυτό είναι 0 (δηλ. αν $b \mid a$) τότε η απάντηση είναι $b$. Αλλιώς συνεχίζουμε με τον υπολογισμό του $(b, a \bmod b)$ μέχρι το $a \bmod b$ να βγει 0.

Ιδού μια υλοποίηση του αλγορίθμου αυτού στη γλώσσα python:

def gcd(a, b): # find the gcd of a, b, where a >= b
    print a, b
    r = a % b # if a < b then this will reverse them at the next call
    if r == 0:
        return b
    else:
        return gcd(b, r)

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

$$7735, 3003$$

δίνοντας

print gcd(7735, 3003)

τότε παίρνουμε

7735 3003
3003 1729
1729 1274
1274 455
455 364
364 91
91

που είναι οι ενδιάμεσες κλήσεις στη συνάρτηση μαζί με το τελικό αποτέλεσμα (91).