ΜΚΔ και ΕΚΠ

Εισαγωγή στον ΜΚΔ και ΕΚΠ

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

Μέγιστος Κοινός Διαιρέτης (ΜΚΔ)

Ορισμός: Ο Μέγιστος Κοινός Διαιρέτης δύο ακεραίων $a$ και $b$ (όχι και οι δύο μηδέν) είναι ο μεγαλύτερος θετικός ακέραιος που διαιρεί και τον $a$ και τον $b$.

Συμβολισμός: $\gcd(a, b)$ ή $(a, b)$ ή $\text{ΜΚΔ}(a, b)$

Ιδιότητες ΜΚΔ

1. $\gcd(a, b) = \gcd(b, a)$ (αντιμεταθετική)
2. $\gcd(a, b) = \gcd(|a|, |b|)$
3. $\gcd(a, 0) = |a|$ για $a \neq 0$
4. $\gcd(a, 1) = 1$
5. $\gcd(a, a) = |a|$
6. Αν $a \mid b$, τότε $\gcd(a, b) = |a|$

Υπολογισμός με Ανάλυση σε Πρώτους

Αν $a = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots$ και $b = p_1^{b_1} \cdot p_2^{b_2} \cdot \ldots$, τότε:

$$\gcd(a, b) = p_1^{\min(a_1, b_1)} \cdot p_2^{\min(a_2, b_2)} \cdot \ldots$$

Ελάχιστο Κοινό Πολλαπλάσιο (ΕΚΠ)

Ορισμός: Το Ελάχιστο Κοινό Πολλαπλάσιο δύο θετικών ακεραίων $a$ και $b$ είναι ο μικρότερος θετικός ακέραιος που διαιρείται και από τον $a$ και από τον $b$.

Συμβολισμός: $\text{lcm}(a, b)$ ή $[a, b]$ ή $\text{ΕΚΠ}(a, b)$

Ιδιότητες ΕΚΠ

1. $\text{lcm}(a, b) = \text{lcm}(b, a)$
2. $\text{lcm}(a, 1) = |a|$
3. $\text{lcm}(a, a) = |a|$
4. Αν $a \mid b$, τότε $\text{lcm}(a, b) = |b|$

Υπολογισμός με Ανάλυση σε Πρώτους

$$\text{lcm}(a, b) = p_1^{\max(a_1, b_1)} \cdot p_2^{\max(a_2, b_2)} \cdot \ldots$$

Θεμελιώδης Σχέση ΜΚΔ-ΕΚΠ

Για θετικούς ακεραίους $a, b$ ισχύει:

$$\gcd(a, b) \cdot \text{lcm}(a, b) = a \cdot b$$

Επομένως:

$$\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}$$

Πρώτοι μεταξύ τους Αριθμοί

Ορισμός: Δύο ακέραιοι $a, b$ λέγονται πρώτοι μεταξύ τους (ή σχετικά πρώτοι) αν $\gcd(a, b) = 1$.

Ιδιότητες:

• Αν $\gcd(a, b) = 1$ και $a \mid bc$, τότε $a \mid c$
• Αν $\gcd(a, b) = 1$, τότε $\gcd(a^n, b^m) = 1$ για κάθε $n, m \geq 1$
• Διαδοχικοί ακέραιοι είναι πάντα πρώτοι μεταξύ τους: $\gcd(n, n+1) = 1$

Λήμμα του Ευκλείδη

Θεώρημα: Αν $p$ πρώτος και $p \mid ab$, τότε $p \mid a$ ή $p \mid b$.

Αυτό γενικεύεται: Αν $\gcd(a, b) = 1$ και $a \mid bc$, τότε $a \mid c$.

ΜΚΔ και ΕΚΠ Τριών ή Περισσότερων Αριθμών

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

$$\text{lcm}(a, b, c) = \text{lcm}(\text{lcm}(a, b), c)$$

Προσοχή: Η σχέση $\gcd \cdot \text{lcm} = a \cdot b$ δεν επεκτείνεται άμεσα για τρεις ή περισσότερους αριθμούς.