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

Στην θεωρία αριθμών, το **ελάχιστο κοινό πολλαπλάσιο (ΕΚΠ)** δύο ή περισσότερων ακεραίων ορίζεται ως ο μικρότερος θετικός ακέραιος αριθμός που διαιρείται ακριβώς με όλους αυτούς τους δεδομένους αριθμούς. Το ελάχιστο κοινό πολλαπλάσιο των a, b συμβολίζεται ως \operatorname{EK\Pi}(a, b), \operatorname{lcm}(a, b) ή [a, b].

Για παράδειγμα, το ελάχιστο κοινό πολλαπλάσιο του 5 και του 3 είναι το 15, ενώ του 6 και του 4 είναι το 12.

## Ορισμοί
**Πολλαπλάσια** ενός ακεραίου αριθμού a είναι οι θετικοί ακέραιοι που προκύπτουν όταν αυτός πολλαπλασιαστεί με όλους τους άλλους θετικούς ακέραιους αριθμούς, δηλαδή είναι οι αριθμοί |a|, |2a|, |3a|, |4a|, \ldots. Πιο συγκεκριμένα, το σύνολο ορίζεται ως εξής
:\Pi(a) = \{ |k \cdot a| : k \in \N_{> 0} \}.
Για παράδειγμα, \Pi(6) = \{ 6, 12, 18, 24, 30, 36, \ldots \} και \Pi(4) = \{ 4, 8, 12, 16, 20, 24, 28, 32, 36, \ldots \}. 

Τα **κοινά πολλαπλάσια** δύο ακεραίων a και b είναι οι αριθμοί που είναι πολλαπλάσια και των δύο αριθμών. Δηλαδή, 
:\operatorname{K\Pi}(a, b) = \Pi(a) \cap \Pi(b). 
Για παράδειγμα, \operatorname{K\Pi}(4, 6) = \{ 12, 24, 36, 48, \ldots \}.

To **ελάχιστο κοινό πολλαπλάσιο** δύο ακεραίων είναι το μικρότερο κοινό τους πολλαπλάσιο. Πάντοτε υπάρχει καθώς η απόλυτη τιμή του γινομένου τους είναι πολλαπλάσιο και των δύο, και επίσης όλα τα πολλαπλάσια είναι μεγαλύτερα ή ίσα από 1 (άρα υπάρχει ελάχιστο στοιχείο). Επομένως, 
:\operatorname{EK\Pi}(a, b) = \min \operatorname{K\Pi}(a, b).

## Ιδιότητες

* Αν a \mid b, τότε \Pi(b) \subseteq \Pi(a). 

* \operatorname{EK\Pi}(a, b) = \operatorname{EK\Pi}(b,a).

* Αν οι ακέραιοι a, b, παραγοντοποιούνται ως εξής
::a = \prod_{i = 1}^\infty p_i^{\alpha_i} και b = \prod_{i = 1}^\infty p_i^{\beta_i}, 
:όπου p_1, p_2, \ldots οι πρώτοι αριθμοί, τότε
::\operatorname{EK\Pi}(a, b) = \prod_{i = 1}^\infty p_i^{\max(\alpha_i, \beta_i)}.
* Αν \operatorname{MK\Delta}(a, b) ο μέγιστος κοινός διαιρέτης των a, b, τότε
::\operatorname{EK\Pi}(a, b) = \frac{\operatorname{MK\Delta}(a, b)}.

* Αν \operatorname{MK\Delta}(a, k) = 1, τότε \operatorname{EK\Pi}(a,kb) = |k| \cdot \operatorname{EK\Pi}(a,b). 

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

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


```c++
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 και 24. Έχουμε: 
:90 = 2  \cdot 3^2 \cdot 5 και 24 = 2^3 \cdot 3. 
Άρα
:\operatorname{EK\Pi}(90,24) = 2^{\max(1, 3)} \cdot 3^{\max(2,1)} \cdot 5^{\max(1, 0)} = 2^3 \cdot 3^2 \cdot 5^1 = 360.

### Με αλγορίθμους για τον ΜΚΔ
Υπάρχουν αρκετοί αποδοτικοί αλγόριθμοι για τον υπολογισμό του μέγιστου κοινού διαιρέτη δύο αριθμών (π.χ. ο αλγόριθμος του Ευκλείδη). Με την ιδιότητα 
:\operatorname{EK\Pi}(a, b) = \frac{\operatorname{MK\Delta}(a, b)},
μπορούν να χρησιμοποιηθούν και για τον υπολογισμό του ΕΚΠ. 

#### Παράδειγμα
Ο αλγόριθμος του Ευκλείδη δίνει 
:
\begin{align}
\operatorname{MK\Delta}(90,24) & = \operatorname{MK\Delta}(24, 18) & (\text{καθώς }90 = 24 \cdot 3 + 18) \\
& = \operatorname{MK\Delta}(18, 6) & (\text{καθώς }24 = 18 \cdot 1 + 6) \\
& = 6 & (\text{καθώς }18 = 6 \cdot 3 + 0).
\end{align}

\operatorname{MK\Delta}(90,24) = 6 και επομένως 
:\operatorname{EK\Pi}(90, 24) = \frac{90 \cdot 24}{6} = 360. 

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

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

Οι κοινοί παράγοντες των αριθμών a_1, a_2, \ldots , a_n είναι η τομή των συνόλων των παραγόντων των αριθμών αυτών, δηλαδή
:\operatorname{K\Pi}(a_1, \ldots, a_n) = \Pi(a_1) \cap \ldots \cap \Pi(a_n).
Το σύνολο αυτό περιέχει τουλάχιστον ένα στοιχείο (το γινόμενό τους a_1 \cdot \ldots \cdot a_n) και όλα του τα στοιχεία είναι μεγαλύτερα ή ίσα του 1.

Το ελάχιστο κοινό πολλαπλάσιο των αριθμών a_1, a_2, \ldots , a_n είναι το ελάχιστο στοιχείο του \operatorname{K\Pi}(a_1, \ldots, a_n), δηλαδή 
:\operatorname{EK\Pi}(a_1, \ldots, a_n) = \min\operatorname{K\Pi}(a_1, \ldots, a_n).

### Ιδιότητες
* \operatorname{EK\Pi}(a_1, \ldots, a_n) = \operatorname{EK\Pi}(a_1, \operatorname{EK\Pi}(a_2, \ldots, a_n)).
* Αν a_1 = \prod_{i = 1}^{\infty} p_i^{\alpha_{1,j}}, \ldots, a_n = \prod_{i = 1}^{\infty} p_i^{\alpha_{n,i}}, τότε 
::\operatorname{EK\Pi}(a_1, \ldots, a_n) = \prod_{i = 1}^\infty p_i^{\max(\alpha_{1,i}, \ldots , \alpha_{n,i})}.
* Για κάθε m \in \N, τότε \operatorname{EK\Pi}(a_1^m, \ldots, a_n^m) = (\operatorname{EK\Pi}(a_1, \ldots, a_n))^m.

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

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

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

## Παραπομπές


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