Ελάχιστο κοινό πολλαπλάσιο

Στην θεωρία αριθμών, το ελάχιστο κοινό πολλαπλάσιο (ΕΚΠ) δύο ή περισσότερων ακεραίων ορίζεται ως ο μικρότερος θετικός ακέραιος αριθμός που διαιρείται ακριβώς με όλους αυτούς τους δεδομένους αριθμούς. Το ελάχιστο κοινό πολλαπλάσιο των  συμβολίζεται ως ,  ή .

Για παράδειγμα, το ελάχιστο κοινό πολλαπλάσιο του  και του  είναι το , ενώ του  και του  είναι το .

 Ορισμοί  
Πολλαπλάσια ενός ακεραίου αριθμού  είναι οι θετικοί ακέραιοι που προκύπτουν όταν αυτός πολλαπλασιαστεί με όλους τους άλλους θετικούς ακέραιους αριθμούς, δηλαδή είναι οι αριθμοί . Πιο συγκεκριμένα, το σύνολο ορίζεται ως εξής
.
Για παράδειγμα,  και . 

Τα κοινά πολλαπλάσια δύο ακεραίων  και  είναι οι αριθμοί που είναι πολλαπλάσια και των δύο αριθμών. Δηλαδή, 
. 
Για παράδειγμα, .

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

 Ιδιότητες 

 Αν , τότε . 

 .

 Αν οι ακέραιοι , παραγοντοποιούνται ως εξής
 και , 
όπου  οι πρώτοι αριθμοί, τότε
.
 Αν  ο μέγιστος κοινός διαιρέτης των , τότε
.

 Αν , τότε . 

 Τρόποι εύρεσης ΕΚΠ 

 Με υπολογισμό των κοινών πολλαπλασίων 
Λαμβάνουμε τον μεγαλύτερο από τους δοσμένους αριθμούς και υπολογίζουμε διαδοχικά τα πολλαπλάσιά του (αρχίζοντας από τον ίδιο), μέχρι να βρούμε εκείνο το πολλαπλάσιο που διαιρείται ακριβώς με όλους τους υπόλοιπους αριθμούς που έχουμε.

int lcm_set(int a, int b) {
   int pol_a = a; // Πολλαπλάσιο του α.
   int pol_b = b; // Πολλαπλάσιο του β.
   while (pol_a != pol_b) {
      // Αυξάνουμε το πολλαπλάσιο που είναι μικρότερο.
      if (pol_a < pol_b) pol_a = pol_a + a;
      else pol_b = pol_b + b;
   }
   return pol_a;
}

 Παράδειγμα 
Για παράδειγμα, για να υπολογίσουμε το ΕΚΠ του 90 και του 24 βρίσκουμε τα πολλαπλάσιά τους μέχρι να βρεθεί ένα κοινό πολλαπλάσιο.
 Πολλαπλάσια του 90:  90  180  270  360  ..  ..  ..  ..  ..  ..  ..  ..  ..  ..  .. Πολλαπλάσια του 24:  24  48  72  96  120  144  168  192  216  240  264  288  312  336  360

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

Παραγοντοποιούμε τους αριθμούς που μας έχουν δοθεί. Στη συνέχεια σχηματίζουμε το γινόμενο όλων των παραγόντων (πρώτων αριθμών), κοινών και μη κοινών, θέτοντας ως εκθέτη κάθε παράγοντα τον μεγαλύτερο. 

 Παράδειγμα 
Έστω ότι θέλουμε να βρούμε το ΕΚΠ δυο αριθμών, των 90 και 24. Έχουμε: 
 και . 
Άρα
.

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

 Παράδειγμα 
Ο αλγόριθμος του Ευκλείδη δίνει 

 και επομένως 
. 

 Για περισσότερους από δύο ακεραίους 

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

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

Το ελάχιστο κοινό πολλαπλάσιο των αριθμών  είναι το ελάχιστο στοιχείο του , δηλαδή 
.

 Ιδιότητες 
 .
 Αν , τότε 
.
 Για κάθε , τότε .

 Περαιτέρω ανάγνωση 

 Ελληνικά άρθρα 



 Δείτε επίσης 
 Μέγιστος κοινός διαιρέτης
 Θεωρία αριθμών

Παραπομπές

Κατηγορία:Θεωρία αριθμών
Κατηγορία:Στοιχειώδης αριθμητική