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

Στην θεωρία αριθμών, το ελάχιστο κοινό πολλαπλάσιο (ΕΚΠ) δύο ή περισσότερων ακεραίων ορίζεται ως ο μικρότερος θετικός ακέραιος αριθμός που διαιρείται ακριβώς με όλους αυτούς τους δεδομένους αριθμούς. Το ελάχιστο κοινό πολλαπλάσιο των $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 \mathbb {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)$.

Απόδειξη  

Έστω $a,b$ με $a\mid b$, δηλαδή $b=k\cdot a$ για κάποιον ακέραιο $k$. Έστω $d\in \Pi (b)$ τότε $d=b\cdot \ell$ για κάποιον ακέραιο $\ell$ και άρα $d=k\ell \cdot a$, δηλαδή $d\in \Pi (a)$. Συνεπώς, $\Pi (b)\subseteq \Pi (a)$.

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

Απόδειξη  

$\operatorname {EK\Pi } (a,b)=\min \operatorname {K\Pi } (a,b)=\min \operatorname {\Pi } (a)\cap \operatorname {\Pi } (b)=\min \operatorname {\Pi } (b)\cap \operatorname {\Pi } (a)=\min \operatorname {K\Pi } (b,a)=\operatorname {EK\Pi } (b)$.

• Αν οι ακέραιοι $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 {|ab|}{\operatorname {MK\Delta } (a,b)}}$.

Απόδειξη  

Έστω $d=\operatorname {MK\Delta } (a,b)$. Θα αποδείξουμε ότι $ab/d$ είναι (i) πολλαπλάσιο των $a$ και $b$ και (ii) είναι μικρότερο από κάθε άλλο πολλαπλάσιό τους.

(i) Από την υπόθεση, υπάρχουν ακέραιοι $k,\ell$ ώστε $a=k\cdot d$ και $b=\ell \cdot d$. Δηλαδή,

${\frac {ab}{d}}=b\cdot k$ και ${\frac {ab}{d}}=a\cdot \ell$.

Άρα ${\frac {ab}{d}}$ πολλαπλάσιο των $a$ και $b$.

(ii) Από τις ιδιότητες του ΜΚΔ, έχουμε ότι $d=na+mb$ για ακεραίους $n,m$. Έστω $x$ ένα πολλαπλάσιο των $a$ και $b$, δηλαδή $x=\rho a$ και $x=\sigma b$. Τότε,

${\frac {x}{ab/d}}={\frac {dx}{ab}}={\frac {(na+mb)x}{ab}}={\frac {nx}{b}}+{\frac {mx}{a}}=n\sigma +m\rho$,

που είναι ακέραιος. Άρα το $ab/d$ διαιρεί το $x$ και έπεται το ζητούμενο.

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

Απόδειξη  

$\operatorname {EK\Pi } (a,kb)={\frac {|akb|}{\operatorname {MK\Delta } (a,kb)}}=|k|\cdot {\frac {|ab|}{\operatorname {MK\Delta } (a,b)}}=|k|\cdot \operatorname {EK\Pi } (a,kb).$

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

Με υπολογισμό των κοινών πολλαπλασίων

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

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. Έχουμε:

$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 {|ab|}{\operatorname {MK\Delta } (a,b)}}$,

μπορούν να χρησιμοποιηθούν και για τον υπολογισμό του ΕΚΠ.

Παράδειγμα

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

${\begin{aligned}\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{aligned}}$

$\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}))$.
• Αν ${\textstyle 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 \mathbb {N}$, τότε $\operatorname {EK\Pi } (a_{1}^{m},\ldots ,a_{n}^{m})=(\operatorname {EK\Pi } (a_{1},\ldots ,a_{n}))^{m}$.

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

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

• Τζαβίδας, Β. (1978). «Για τη Β΄Τάξη Άλγεβρα: Διαιρετότητα στο σύνολο των ακεραίων Ζ». Ευκλείδης Β΄ (4): 165-173. http://niobe.hms.gr/apothema/?s=sa&i=4113. 
• Μέγας, Π. (1978). «Για τη Β΄Τάξη Άλγεβρα: Μέγιστος κοινός διαιρέτης και ελάχιστο κοινό πολλαπλάσιο ακεραίων πολυωνύμων». Ευκλείδης Β΄ (5): 214-218. http://niobe.hms.gr/apothema/?s=sa&i=4288. 

Δείτε επίσης

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