ΜΕΓΙΣΤΟΣ ΚΟΙΝΟΣ ΔΙΑΙΡΕΤΗΣ - ΕΛΑΧΙΣΤΟΚΟΙΝΟ ΠΟΛΛΑΠΛΑΣΙΟ

Σχεδιάγραμμα

Δική μας σύνοψη της ενότητας, για επανάληψη. Πηγή είναι πάντα το βιβλίο.

Τι έγινε

1. Μ.Κ.Δ. (α, β) δύο ακεραίων, όχι και των δύο μηδέν, είναι ο μεγαλύτερος θετικός κοινός διαιρέτης τους· π.χ. (−12, 30) = 6. Ισχύουν (α, α) = α, (α, 0) = α, (α, 1) = 1 για α > 0.
2. Αν (α, β) = 1 οι α, β λέγονται πρώτοι μεταξύ τους.
3. Θεώρημα 3: αν α = κβ + υ (ευκλείδεια διαίρεση), τότε (α, β) = (β, υ). Επαναλαμβάνοντας παίρνουμε τον ευκλείδειο αλγόριθμο: ο Μ.Κ.Δ. είναι το τελευταίο μη μηδενικό υπόλοιπο.
4. Θεώρημα 4: ο Μ.Κ.Δ. γράφεται ως γραμμικός συνδυασμός κα + λβ (τα κ, λ δεν είναι μοναδικά). Άρα (α, β) = 1 ⇔ κα + λβ = 1 για κάποιους ακέραιους, και (α/δ, β/δ) = 1 όταν δ = (α, β).
5. Οι κοινοί διαιρέτες δύο ακεραίων είναι οι διαιρέτες του Μ.Κ.Δ. τους. Αν α | βγ και (α, β) = 1, τότε α | γ.
6. Για περισσότερους αριθμούς, μπορούμε να βάλουμε στη θέση δύο από αυτούς τον Μ.Κ.Δ. τους χωρίς να αλλάξει το αποτέλεσμα· επίσης (α, β) = (α − κβ, β) και (α, α + 1) = 1.
7. Ε.Κ.Π. [α, β] μη μηδενικών ακεραίων είναι το μικρότερο θετικό κοινό πολλαπλάσιό τους· π.χ. [−4, 6] = 12. Κάθε κοινό πολλαπλάσιο διαιρείται με το Ε.Κ.Π.
8. Θεώρημα 5: (α, β)·[α, β] = αβ για θετικούς α, β· αν (α, β) = 1 τότε [α, β] = |αβ|. Επίσης [κα, κβ] = κ[α, β] και (κα, κβ) = κ(α, β) για κ > 0.

Πρόσωπα

Ευκλείδης

ο αλγόριθμος για τον Μ.Κ.Δ. φέρει το όνομά του

Όροι

μέγιστος κοινός διαιρέτης (α, β)

ο μεγαλύτερος θετικός κοινός διαιρέτης

(−12, 30)

6

(α, 0) για α > 0

α

(α, 1)

1

πρώτοι μεταξύ τους

(α, β) = 1

ευκλείδειος αλγόριθμος

διαδοχικές ευκλείδειες διαιρέσεις

Μ.Κ.Δ. στον αλγόριθμο

το τελευταίο μη μηδενικό υπόλοιπο

Θεώρημα 3

(α, β) = (β, υ), υ το υπόλοιπο

Μ.Κ.Δ. ως γραμμικός συνδυασμός

(α, β) = κα + λβ

(α, β) = 1 ⇔

κα + λβ = 1 για κάποια κ, λ ∈ ℤ

κοινοί διαιρέτες α, β

οι διαιρέτες του (α, β)

α | βγ και (α, β) = 1 ⇒

α | γ

(α, α + 1)

1

ελάχιστο κοινό πολλαπλάσιο [α, β]

το μικρότερο θετικό κοινό πολλαπλάσιο

[−4, 6]

12

(α, β)·[α, β]

α·β (για θετικούς α, β)

[α, β] αν (α, β) = 1

|α·β|

κοινά πολλαπλάσια α, β

τα πολλαπλάσια του [α, β]