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

Στην θεωρία αριθμών, ο μέγιστος κοινός διαιρέτης στη θεωρία αριθμών ονομάζεται ο μεγαλύτερος ακέραιος που διαιρεί δύο ή περισσότερους ακέραιους αριθμούς. Ο μέγιστος κοινός διαιρέτης των $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)$.

Απόδειξη  

$\operatorname {MK\Delta } (a,b)=\max \Delta (a)\cap \Delta (b)=\max \Delta (b)\cap \Delta (a)=\operatorname {MK\Delta } (b,a)$.

• Για κάθε $k\in \mathbb {Z}$, ισχύει ότι $\operatorname {K\Delta } (a-kb,b)=\operatorname {K\Delta } (a,b)$.

Σημείωση: Η ιδιότητα αυτή χρησιμεύει στην απόδειξη της ορθότητας του αλγόριθμου του Ευκλείδη για την εύρεση του ΜΚΔ.

Απόδειξη  

Η απόδειξη προκύπτει από τις ιδιότητες της διαιρετότητας: Αν $d\mid (a-kb)$ και $d\mid b$ τότε $d\mid ((a-kb)+kb)$ και $d\mid b$.

Αντίστοιχα, αν $d\mid a$ και $d\mid b$, τότε $d\mid (a-kb)$.

Επομένως, $\operatorname {K\Delta } (a-kb,b)=\operatorname {K\Delta } (a,b)$.

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

Απόδειξη  

Η απόδειξη προκύπτει κατασκευαστικά από τον επεκταμένο αλγόριθμο του Ευκλείδη.

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

Απόδειξη  

Αν $d\in \operatorname {K\Delta } (a,b)$, τότε $d\mid a$ και $d\mid b$, και επομένως $a=d\cdot k$ και $b=d\cdot \ell$. Από την παραπάνω ιδιότητα

$\operatorname {MK\Delta } (a,b)=n\cdot a+m\cdot b=n\cdot d\cdot k+m\cdot d\cdot \ell =(nk+m\ell )\cdot d$.

Επομένως, $d\mid \operatorname {MK\Delta } (a,b)$.

Αντίστροφα, αν $d\mid \operatorname {MK\Delta } (a,b)$, τότε $d\mid a$ και $d\mid b$, επομένως $d\in \operatorname {K\Delta } (a,b)$.

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

Απόδειξη  

Έστω $d=\operatorname {MK\Delta } (a,b)$ και $d'=\operatorname {MK\Delta } (ka,kb)$. Αρκεί να δείξουμε ότι $kd\mid d'$ και $d'\mid kd$.

Το πρώτο μέρος έπεται από τις ιδιότητες της διαιρετότητας,

• καθώς $d\mid a$ έχουμε ότι $kd\mid ka$,
• καθώς $d\mid b$ έχουμε ότι $kd\mid kb$.

Επομένως, $kd\mid d'$.

Για το δεύτερο μέρος, γράφουμε τον μέγιστο κοινό διαιρέτη των $a,b$ ως γραμμικό τους συνδυασμό

$d=na+mb$ για κάποιους ακεραίους $n,m\in \mathbb {Z}$.

Πολλαπλασιάζοντας επί $k$ και τα δύο μέλη έχουμε ότι

$kd=nka+mkb$

και επομένως $d'\mid kd$.

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

Απόδειξη  

Από την προηγούμενη ιδιότητα για $k=\operatorname {MK\Delta } (a,b)$ έχουμε ότι

$\operatorname {MK\Delta } (a,b)=\operatorname {MK\Delta } (a,b)\cdot \operatorname {MK\Delta } (a/\operatorname {MK\Delta } (a,b),b/\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+mb$ για κάθε $n,m\in \mathbb {Z}$.

Απόδειξη  

Έστω $d=\operatorname {MK\Delta } (a,b)$, τότε

$a=k\cdot d$ και $b=\ell \cdot d$.

Επομένως,

$na+mb=nk\cdot d+m\ell \cdot d=(nk+m\ell )\cdot d$

και καταλήγουμε ότι $d\mid (na+mb)$.

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

Απόδειξη  

Έχουμε ότι αν $d\mid b$ τότε $d\mid bc$, επομένως $\Delta (b)\subseteq \Delta (bc)$. Άρα $\Delta (a)\cap \Delta (b)\subseteq \Delta (a)\cap \Delta (bc)$ και επομένως

$\max \Delta (a)\cap \Delta (bc)\geq \max \Delta (a)\cap \Delta (b)$.

Από τον ορισμό του μέγιστου κοινού διαιρέτη, λαμβάνουμε το ζητούμενο.

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

Απόδειξη  

Χρησιμοποιώντας την υπόθεση και τις παραπάνω ιδιότητες έχουμε ότι

${\begin{aligned}\operatorname {MK\Delta } (b,c)&=\operatorname {MK\Delta } (b\cdot \operatorname {MK\Delta } (a,c),c)\\&=\operatorname {MK\Delta } (\operatorname {MK\Delta } (ab,bc),c)\\&=\operatorname {MK\Delta } (ab,\operatorname {MK\Delta } (bc,c))\\&=\operatorname {MK\Delta } (ab,c\cdot \operatorname {MK\Delta } (b,1))\\&=\operatorname {MK\Delta } (ab,c\cdot 1)\\&=\operatorname {MK\Delta } (ab,c).\end{aligned}}$

• (Λήμμα Ευκλείδη) Αν $\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$.

Απόδειξη  

Από την υπόθεση $b\mid c$, έχουμε $c=kb$. Από το λήμμα του Ευκλείδη, καθώς $\operatorname {MK\Delta } (a,b)=1$, έχουμε ότι $a\mid k$, δηλαδή $k=\ell a$ και $c=\ell ab$. Επομένως, $ab\mid c$.

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

Απόδειξη  

Έστω $d_{1}=\operatorname {MK\Delta } (a,b)$ και $d_{2}=\operatorname {MK\Delta } (a,c)$ και επομένως υπάρχουν ακέραιοι $k_{1},k_{2},\ell _{1},\ell _{2}$ ώστε

$k_{1}a+\ell _{1}b=d_{1}$,

$k_{2}a+\ell _{2}c=d_{2}$.

Πολλαπλασιάζοντας κατά μέλη, έχουμε ότι

$k_{1}k_{2}a^{2}+k_{1}\ell _{2}ac+k_{2}\ell _{1}ab+\ell _{1}\ell _{2}bc=d_{1}d_{2}$.

Από την υπόθεση $a\mid bc$ έχουμε ότι υπάρχει ακέραιος $m$ ώστε $bc=m\cdot a$ και άρα

$d_{1}d_{2}=k_{1}k_{2}a+k_{1}\ell _{2}ac+k_{2}\ell _{1}ab+\ell _{1}\ell _{2}ma=a\cdot (k_{1}k_{2}a+k_{1}\ell _{2}c+k_{2}\ell _{1}b+\ell _{1}\ell _{2}m)$,

και άρα $a\mid d_{1}d_{2}$.

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

Απόδειξη  

Έχουμε ότι $ka+\ell b=1$. Επομένως,

$km\cdot c+\ell \cdot b=1$,

και από την παραπάνω ιδιότητα $\operatorname {MK\Delta } (b,c)\mid 1$. Άρα καταλήγουμε ότι $\operatorname {MK\Delta } (b,c)=1$.

Τρόποι εύρεσης

Με παραγοντοποίηση

Έστω ότι ψάχνουμε τον $\operatorname {MK\Delta } (a,b)$. Παραγοντοποιούμε τους $a$ και $b$ σε γινόμενο πρώτων παραγόντων, έστω ${\textstyle a=\prod _{i=1}^{\infty }p_{i}^{\alpha _{i}}}$ και ${\textstyle 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})}$.

Απόδειξη  

Έστω δύο αριθμοί $a$ και $b$ και ο ΜΚΔ τους $c$. Αφού ο $c$ διαιρεί το $a$ τότε έχει κοινούς πρώτους παράγοντες με το $a$. Αφού διαιρεί και το $b$ τότε έχει κοινούς πρώτους παράγοντες με το $b$. Συνεπάγεται ότι ο $c$ έχει για πρώτους παράγοντες αυτούς οι οποίοι είναι κοινοί για το $a$ και το $b$. Αν δεν υπάρχουν κοινοί πρώτοι παράγοντες τότε ο ΜΚΔ είναι το ένα αφού όλοι οι αριθμοί διαιρούνται με τη μονάδα. Μένει να αποδείξουμε ότι οι πρώτοι παράγοντες είναι υψωμένοι στη μικρότερη κοινή δύναμη. Έστω ο κοινός πρώτος παράγοντας π ο οποίος είναι υψωμένος εις την μ στην περίπτωση του $a$ και εις την ν στην περίπτωση του $b$. Έστω ξ το ελάχιστο των μ και ν. Αν $\nu =\mu$ τότε $\xi =\nu =\mu$ και φαίνεται αμέσως ότι το ξ είναι ο κατάλληλος εκθέτης για το γινόμενο πρώτων παραγόντων του γ. Αν ν>μ, τότε $\xi =\mu$. Αν θέσουμε την τιμή του εκθέτη της ζητούμενης δύναμης για το γ μεγαλύτερη από το ξ τότε δεν θα διαιρεί τη δύναμη με εκθέτη μ καθώς το πηλίκο θα είναι μικρότερο του ενός και φυσικά όχι μηδέν. Αν τη θέσουμε μικρότερη από το ξ τότε το πηλικό θα είναι δύναμη του πρώτου παράγοντα με εκθέτη τουλάχιστον ένα και για το μ και για το ν. Άρα η μέγιστη δύναμη που διαιρεί και τις δύο δυνάμεις έχει εκθέτη ξ. Ομοίως και για ν<μ.

Παράδειγμα 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$.

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

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

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{aligned}\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{aligned}}$

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

${\begin{aligned}\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{aligned}}$

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

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

Οι κοινοί διαιρέτες των αριθμών $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}))$.

Σημείωση: Η παραπάνω ιδιότητα ανάγει τον υπολογισμό του μέγιστου κοινού διαιρέτη πολλών αριθμών στον υπολογισμό του μέγιστου κοινού διαιρέτη δύο αριθμών.

Απόδειξη  

${\begin{aligned}\operatorname {MK\Delta } (a_{1},\operatorname {MK\Delta } (a_{2},\ldots ,a_{n}))&=\max \operatorname {\Delta } (a_{1})\cap \operatorname {\Delta } (\operatorname {MK\Delta } (a_{2},\ldots ,a_{n}))\\&=\max \operatorname {\Delta } (a_{1})\cap (\operatorname {\Delta } (a_{2})\cap \ldots \cap \operatorname {\Delta } (a_{n}))\\&=\max \operatorname {\Delta } (a_{1})\cap \operatorname {\Delta } (a_{2})\cap \ldots \cap \operatorname {\Delta } (a_{n})\\&=\operatorname {MK\Delta } (a_{1},\ldots ,a_{n}).\end{aligned}}$

• Υπάρχουν ακέραιοι $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}$.

Απόδειξη  

Θα το αποδείξουμε με την χρήση μαθηματικής επαγωγής. Για $n=2$ ισχύει από τις παραπάνω ιδιότητες.

Από την προηγούμενη ιδιότητα έχουμε ότι

$\operatorname {MK\Delta } (a_{1},\ldots ,a_{n})=\operatorname {MK\Delta } (a_{1},\operatorname {MK\Delta } (a_{2},\ldots ,a_{n}))$.

Από την επαγωγική υπόθεση έχουμε ότι

$\operatorname {MK\Delta } (a_{2},\ldots ,a_{n})=k_{2}'a_{2}+\ldots +k_{n}'a_{n}$.

Από την ιδιότητα για δύο ακεραίους έχουμε ότι

${\begin{aligned}\operatorname {MK\Delta } (a_{1},\operatorname {MK\Delta } (a_{2},\ldots ,a_{n}))&=\ell _{1}a_{1}+\ell _{2}\operatorname {MK\Delta } (a_{2},\ldots ,a_{n})\\&=\ell _{1}a_{1}+\ell _{2}\cdot (k_{2}'a_{2}+\ldots +k_{n}'a_{n})\\&=\ell _{1}a_{1}+\ell _{2}k_{2}'a_{2}+\ldots +\ell _{2}k_{n}'a_{n}\\\end{aligned}}$.

Επομένως για $k_{1}=\ell _{1},k_{2}=\ell _{2}k_{2}',\ldots k_{n}'=\ell _{2}k_{n}'$ λαμβάνουμε το ζητούμενο.

• Αν $d=\operatorname {MK\Delta } (a_{1},\ldots ,a_{n})$, τότε $\operatorname {MK\Delta } (a_{1}/d,\ldots ,a_{n}/d)=1$.

Απόδειξη  

Έστω $\operatorname {MK\Delta } (a_{1}/d,\ldots ,a_{n}/d)=d'$, τότε $d'\mid a_{1}/d,\ldots ,d'\mid a_{n}/d$ και $dd'\mid a_{1},\ldots ,dd'\mid a_{n}$. Επομένως, $dd'\mid \operatorname {MK\Delta } (a_{1},\ldots ,a_{n})=d$ και άρα $dd'\leq d$, δηλαδή $d'=1$.

• Αν ${\textstyle 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 \mathbb {N}$, τότε $\operatorname {MK\Delta } (a_{1}^{m},\ldots ,a_{n}^{m})=(\operatorname {MK\Delta } (a_{1},\ldots ,a_{n}))^{m}$.

Δείτε επίσης

• Ελάχιστο κοινό πολλαπλάσιο
• Παραγοντοποίηση
• Αλγόριθμος του Ευκλείδη