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

Στην θεωρία αριθμών, ο **μέγιστος κοινός διαιρέτης** στη θεωρία αριθμών ονομάζεται ο μεγαλύτερος ακέραιος που διαιρεί δύο ή περισσότερους ακέραιους αριθμούς. Ο μέγιστος κοινός διαιρέτης των a, b συμβολίζεται με ΜΚΔ(a,b) ή gcd(a,b) ή απλούστερα (a,b). 

Για παράδειγμα, ο μέγιστος κοινός διαιρέτης του 12 και του 16  είναι το 4, ενώ του 120 και του 350 είναι το 10.

## Ορολογία
**[[Διαιρέτης]]** του ακεραίου a λέγεται κάθε φυσικός αριθμός d για τον οποίο υπάρχει ακέραιος αριθμός k τέτοιος, ώστε a = k \cdot d. Με άλλα λόγια όποιος από τους αριθμούς a, a/2, a/3, a/4, \ldots είναι ακέραιος, είναι διαιρέτης του a. Κάθε διαιρέτης του a είναι μικρότερος ή ίσος του a σε απόλυτη τιμή, αφού ο k είναι (μη μηδενικός) ακέραιος.

:Για παράδειγμα, οι διαιρέτες του 12 είναι οι αριθμοί \operatorname{\Delta}(12) = \{ 1, 2, 3, 4, 6, 12 \} και του 16 είναι οι αριθμοί \operatorname{\Delta}(16) = \{ 1, 2, 4, 8, 16 \}.

**Κοινός διαιρέτης** των ακεραίων a και b λέγεται κάθε αριθμός d, ο οποίος είναι ταυτόχρονα διαιρέτης του a και διαιρέτης του b. Δηλαδή υπάρχουν ακέραιοι αριθμοί k και k' τέτοιοι, ώστε a = k \cdot d και b = k' \cdot d. Κάθε ζεύγος a και b έχει τουλάχιστον ένα κοινό διαιρέτη το 1. Κάθε κοινός διαιρέτης είναι μικρότερος ή ίσος με τους |a| και |b|.

:Για παράδειγμα, κοινοί διαιρέτες των 12 και του 16 είναι οι αριθμοί \operatorname{K\Delta}(16) = \{ 1, 2, 4 \}, δηλαδή η τομή των συνόλων \operatorname{\Delta}(12) και \operatorname{\Delta}(16).

**Μέγιστος κοινός διαιρέτης** των ακεραίων a και b είναι ο μεγαλύτερος κοινός τους διαιρέτης. Επειδή το σύνολο \operatorname{K\Delta}(a, b) είναι πεπερασμένο και έχει τουλάχιστον ένα στοιχείο, έπεται ότι πάντα υπάρχει ο μέγιστος κοινός διαιρέτης δύο ακεραίων. Ο μέγιστος κοινός διαιρέτης των a, b συμβολίζεται με \operatorname{MK\Delta}(a,b) ή gcd(a,b) ή απλούστερα (a,b).

:Για παράδειγμα, ο μέγιστος κοινός κοινός διαιρέτης του 12 και του 16 είναι το 4 = \max \operatorname{K\Delta}(12,16).

Δύο ακέραιοι αριθμοί καλούνται **[[σχετικά πρώτοι]]** αν ο μέγιστος κοινός διαιρέτης αυτών είναι 1.

## Ιδιότητες

Ο μέγιστος κοινός διαιρέτης 
* \operatorname{MK\Delta}(a, b) = \operatorname{MK\Delta}(b, a).

* Για κάθε k \in \Z, ισχύει ότι \operatorname{K\Delta}(a -kb, b) = \operatorname{K\Delta}(a,b).
:**Σημείωση:** Η ιδιότητα αυτή χρησιμεύει στην απόδειξη της ορθότητας του αλγόριθμου του Ευκλείδη για την εύρεση του ΜΚΔ.

* Υπάρχουν ακέραιοι k, \ell ώστε \operatorname{MK\Delta}(a, b) = k a + \ell b.

* \operatorname{K\Delta}(a, b) = \Delta(\operatorname{MK\Delta}(a, b)).

* Για κάθε k \in \Z, ισχύει ότι \operatorname{MK\Delta}(ka, kb) = k \cdot \operatorname{MK\Delta}(a, b).

* \operatorname{MK\Delta}(a/\operatorname{MK\Delta}(a, b), b/\operatorname{MK\Delta}(a, b)) = 1.

* Ο μέγιστος κοινός διαιρέτης διαιρεί κάθε γραμμικό συνδυασμό των δύο αριθμών, δηλαδή \operatorname{MK\Delta}(a, b) \mid na + m b για κάθε n, m \in \Z.

* \operatorname{MK\Delta}(a, bc) \geq \operatorname{MK\Delta}(a, b).

* \operatorname{MK\Delta}(a, c) = 1, τότε \operatorname{MK\Delta}(ab, c) = \operatorname{MK\Delta}(b,c).

* (**[[Λήμμα Ευκλείδη]]**) Αν \operatorname{MK\Delta}(a, c) = 1 και c \mid ab, τότε c \mid ab.
* Αν a \mid c, b \mid c και \operatorname{MK\Delta}(a, b) = 1, τότε ab \mid c.

* Αν a | bc, τότε a | \operatorname{MK\Delta}(a, b) \cdot \operatorname{MK\Delta}(a,c).

* Αν \operatorname{MK\Delta}(a,b) = 1 και c \mid a, τότε  \operatorname{MK\Delta}(b, c) = 1.

## Τρόποι εύρεσης
### Με παραγοντοποίηση
Έστω ότι ψάχνουμε τον \operatorname{MK\Delta}(a, b). Παραγοντοποιούμε τους a και b σε γινόμενο πρώτων παραγόντων, έστω a = \prod_{i = 1}^\infty p_i^{\alpha_i} και b = \prod_{i = 1}^{\infty} p_i^{\beta_i}, όπου p_1, p_2, \ldots οι πρώτοι αριθμοί. Τότε, ο \operatorname{MK\Delta}(a, b) ισούται με το γινόμενο των κοινών πρώτων παραγόντων στη μικρότερη κοινή δύναμη, δηλαδή
:\operatorname{MK\Delta}(a, b) = \prod_{i = 1}^\infty p_i^{\min(\alpha_i, \beta_i)}.

#### Παράδειγμα 1ο
Έστω ότι a =120 και b = 350. Από την παραγοντοποίηση έχουμε
:120 = 2^3 \cdot 3 \cdot 5 και 350 = 2 \cdot 5^2 \cdot 7. 
Οι κοινοί πρώτοι παράγοντες είναι οι 2, 5 και οι μη κοινοί οι 3, 7. Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε 2, 5. Άρα 
:\operatorname{MK\Delta}(a,b) = 2 \cdot 5 = 10.

#### Παράδειγμα 2ο
Έστω ότι a=150 και b = 350. Από την παραγοντοποίηση έχουμε 
:150=2 \cdot 3 \cdot 5^2 και 350=2\cdot 5^2 \cdot 7.
Οι κοινοί πρώτοι παράγοντες είναι οι 2, 5 και οι μη κοινοί οι 3, 7. Υψώνοντας τον καθένα από τους κοινούς στη μικρότερη δύναμή του έχουμε 2, 5^2. Άρα 
:\operatorname{MK\Delta}(a,b) = 2 \cdot 5^2 = 50.

### Με τον αλγόριθμο του Ευκλείδη

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


```c++
int gcd(int a, int b) {
   if (a mod b == 0) return b;
   return gcd(b, a mod b);
}
```


Ο επεκταμένος αλγόριθμος που Ευκλείδη, επιστρέφει επίσης δύο αριθμούς x, y τέτοιους ώστε ax + by = \operatorname{MK\Delta}(a, b).

#### Παράδειγμα 1ο


\begin{align}
\operatorname{MK\Delta}(350, 120) & = \operatorname{MK\Delta}(120, 110) & (\text{καθώς }350 = 120 \cdot 2 + 110) \\
& = \operatorname{MK\Delta}(110, 10) & (\text{καθώς }350 = 120 \cdot 2 + 110) \\
& = 10 & (\text{καθώς }110 = 11 \cdot 10).
\end{align}


#### Παράδειγμα 2ο


\begin{align}
\operatorname{MK\Delta}(6434, 2070) & = \operatorname{MK\Delta}(2070, 224) & (\text{καθώς }350 = 2070 \cdot 3 + 224) \\
& = \operatorname{MK\Delta}(224, 54) & (\text{καθώς }2070 = 224 \cdot 9 + 54) \\
& = \operatorname{MK\Delta}(54, 8) & (\text{καθώς }224 = 54 \cdot 4 + 8) \\
& = \operatorname{MK\Delta}(8, 6) & (\text{καθώς }54 = 8 \cdot 6 + 6) \\
& = \operatorname{MK\Delta}(6, 2) & (\text{καθώς }8 = 6 \cdot 1 + 2) \\
& = 2 & (\text{καθώς }6 = 3 \cdot 2).
\end{align}


## Για παραπάνω από δύο ακεραίους

Ο ορισμός του μέγιστου κοινού διαιρέτη γενικεύεται για δύο ή περισσότερους ακέραιους αριθμούς. 

Οι κοινοί διαιρέτες των αριθμών a_1, a_2, \ldots , a_n είναι η τομή των συνόλων των διαιρετών των αριθμών αυτών, δηλαδή
:\operatorname{K\Delta}(a_1, \ldots, a_n) = \Delta(a_1) \cap \ldots \cap \Delta(a_n).
Το σύνολο αυτό περιέχει τουλάχιστον ένα στοιχείο (το 1) και είναι πεπερασμένο, καθώς κάθε στοιχείο είναι μικρότερο του \max\{ |a_1|, \ldots, |a_n| \}.

Ο μέγιστος κοινός διαιρέτης των αριθμών a_1, a_2, \ldots , a_n είναι το μέγιστο στοιχείο του \operatorname{K\Delta}(a_1, \ldots, a_n), δηλαδή 
:\operatorname{MK\Delta}(a_1, \ldots, a_n) = \max\operatorname{K\Delta}(a_1, \ldots, a_n).

### Ιδιότητες
Για κάθε ακεραίους a_1, \ldots, a_n ισχύουν οι εξής ιδιότητες:
* \operatorname{\Delta}(\operatorname{MK\Delta}(a_1, \ldots, a_n)) = \operatorname{\Delta}(a_1) \cap \ldots \cap \operatorname{\Delta}(a_n).

* \operatorname{MK\Delta}(a_1, \ldots, a_n) = \operatorname{MK\Delta}(a_1, \operatorname{MK\Delta}(a_2, \ldots, a_n)).
:**Σημείωση:** Η παραπάνω ιδιότητα ανάγει τον υπολογισμό του μέγιστου κοινού διαιρέτη πολλών αριθμών στον υπολογισμό του μέγιστου κοινού διαιρέτη δύο αριθμών.

* Υπάρχουν ακέραιοι k_1, k_2, \ldots, k_n τέτοιοι ώστε
::\operatorname{MK\Delta}(a_1, \ldots, a_n) = k_1 a_1 + k_2 a_2 + \ldots + k_n a_n.

* Αν d = \operatorname{MK\Delta}(a_1, \ldots , a_n), τότε \operatorname{MK\Delta}(a_1/d, \ldots, a_n/d) = 1.

* Αν a_1 = \prod_{i = 1}^{\infty} p_i^{\alpha_{1,j}}, \ldots, a_n = \prod_{i = 1}^{\infty} p_i^{\alpha_{n,i}}, τότε 
::\operatorname{MK\Delta}(a_1, \ldots, a_n) = \prod_{i = 1}^\infty p_i^{\min(\alpha_{1,i}, \ldots , \alpha_{n,i})}.
* Για κάθε m \in \N, τότε \operatorname{MK\Delta}(a_1^m, \ldots, a_n^m) = (\operatorname{MK\Delta}(a_1, \ldots, a_n))^m.
## Δείτε επίσης
*Ελάχιστο κοινό πολλαπλάσιο
*Παραγοντοποίηση
*Αλγόριθμος του Ευκλείδη

## Παραπομπές


 

Κατηγορία:Θεωρία αριθμών