Μέγιστος κοινός διαιρέτης: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
μ Bot: Migrating 54 langlinks, now provided by Wikidata on d:Q131752 |
→Με παραγοντοποίηση: παράθεση απόδειξης, βελτιώσεις |
||
Γραμμή 13:
== Τρόποι εύρεσης μέγιστου κοινού διαιρέτη των α και β ==
=== Με παραγοντοποίηση ===
Παραγοντοποιούμε τους α και β σε
''Απόδειξη'': Έστω δύο αριθμοί ''α'' και ''β'' και ο ΜΚΔ τους ''γ''. Αφού ο ''γ'' διαιρεί το ''α'' τότε έχει κοινούς πρώτους παράγοντες με το ''α''. Αφού διαιρεί και το ''β'' τότε έχει κοινούς πρώτους παράγοντες με το ''β''. Συνεπάγεται ότι ο ''γ'' έχει για πρώτους παράγοντες αυτούς οι οποίοι είναι κοινοί για το ''α'' και το ''β''. Αν δεν υπάρχουν κοινοί πρώτοι παράγοντες τότε ο ΜΚΔ είναι το ένα αφού όλοι οι αριθμοί διαιρούνται με τη μονάδα. Μένει να αποδείξουμε ότι οι πρώτοι παράγοντες είναι υψωμένοι στη μικρότερη κοινή δύναμη. Έστω ο κοινός πρώτος παράγοντας ''π'' ο οποίος είναι υψωμένος εις την ''μ'' στην περίπτωση του ''α'' και εις την ''ν'' στην περίπτωση του ''β''. Έστω ''ξ'' το ελάχιστο των ''μ'' και ''ν''. Αν ''ν''=''μ'' τότε ''ξ''=''ν''=''μ'' και φαίνεται αμέσως ότι το ''ξ'' είναι η κατάλληλη δύναμη για το γινόμενο πρώτων παραγόντων του ''γ''. Αν ''ν''>''μ'', τότε ''ξ''=''μ''. Αν θέσουμε την τιμή του εκθέτη της ζητούμενης δύναμης για το ''γ'' μεγαλύτερη από το ''ξ'' τότε δεν θα διαιρεί τη δύναμη με εκθέτη ''μ'' καθώς το πηλίκο θα είναι μικρότερο του ενός και φυσικά όχι μηδέν. Αν τη θέσουμε μικρότερη από το ''ξ'' τότε το πηλικό θα είναι δύναμη του πρώτου παράγοντα με εκθέτη τουλάχιστον ένα και για το ''μ'' και για το ''ν''. Άρα η μέγιστη δύναμη που διαιρεί και τις δύο δυνάμεις είναι το ''ξ''. Ομοίως και για ''ν''<''μ''.
Έστω ότι α =120 και β =350. Από τη διαδικασία της παραγοντοποίησης προκύπτει ότι 120 = 2<sup>3</sup>*3*5 και 350 = 2*5<sup>2</sup>*7. Οι πρώτοι παράγοντες είναι οι 2, 5 οι κοινοί και 3, 7 οι μη κοινοί. Υψωμένοι ο καθένας από τους '''κοινούς''' στη μικρότερη δύναμή του είναι 2, 5. Άρα ΜΚΔ(α,β)= 2*5 = 10.▼
▲''Παράδειγμα α'': Έστω ότι α =120 και β =350. Από
''Παράδειγμα β'': Έστω ότι α=150 και β=350. Από
▲Έστω ότι α=150 και β=350. Από τη διαδικασία της παραγοντοποίησης προκύπτει ότι 150=2*3*5<sup>2</sup> και 350=2*5<sup>2</sup>*7. Οι πρώτοι παράγοντες είναι οι 2, 5 οι κοινοί και 3, 7 οι μη κοινοί. Υψωμένοι ο καθένας από τους κοινούς παράγοντες στη μικρότερη δύναμή του είναι 2, 5<sup>2</sup>. Άρα ΜΚΔ(α,β)=2*5<sup>2</sup>=50.
=== Με τον [[αλγόριθμος του Ευκλείδη|αλγόριθμο του Ευκλείδη]] ===
== Δείτε επίσης ==
| |||