Θεμελιώδες θεώρημα αριθμητικής

Αυτό το λήμμα αφορά σχετικό θεώρημα της αριθμητικής. Για το θεώρημα της άλγεβρας, δείτε: Θεμελιώδες θεώρημα άλγεβρας.

Στην θεωρία αριθμών, το θεμελιώδες θεώρημα της αριθμητικής είναι ένα από τα πιο σημαντικά θεωρήματα των μαθηματικών. Λέει ότι κάθε φυσικός αριθμός μεγαλύτερος της μονάδας αναλύεται σε γινόμενο πρώτων παραγόντων κατά ένα και μοναδικό τρόπο, αν δεν λάβουμε υπόψιν μας την σειρά των παραγόντων στο γινόμενο.

Για παράδειγμα, το θεώρημα λέει ότι ο αριθμός $120$ μπορεί να γραφτεί ως το γινόμενο $2\cdot 2\cdot 2\cdot 3\cdot 5$ δηλαδή ως το γινόμενο των πρώτων αριθμών $2,3,5$, και επιπλέον η παραγοντοποίηση αυτή είναι μοναδική (αν θεωρήσουμε ίδιες τις μορφές $2\cdot 2\cdot 3\cdot 2\cdot 5=2\cdot 3\cdot 2\cdot 2\cdot 5=\ldots$).

Η απόδειξη του Ευκλείδη

Η απόδειξη χωρίζεται σε δύο σκέλη. Στο πρώτο σκέλος θα αποδείξουμε ότι κάθε φυσικός αριθμός αναλύεται σε γινόμενο πρώτων και στο δεύτερο θα αποδείξουμε ότι αυτή η ανάλυση είναι μοναδική για κάθε φυσικό αριθμό.

Ανάλυση σε γινόμενο πρώτων: Έστω $k>1$, εφαρμόζουμε τη μέθοδο της μαθηματικής επαγωγής:

1. Για $k=2$ το πρώτο σκέλος είναι προφανές.
2. Έστω ότι για κάθε φυσικό αριθμό $n$ με $2\leq n\leq k-1$, υπάρχουν πρώτοι αριθμοί $p_{1},\ldots ,p_{m}$, όχι αναγκαστικά διαφορετικοί, έτσι ώστε $n=p_{1}\cdot \ldots \cdot p_{m}$. Αν ο αριθμός $k$ είναι πρώτος ο ισχυρισμός μας ισχύει. Αν ο $k$ είναι σύνθετος, τότε υπάρχουν $b,c\in \mathbb {N}$ τέτοια ώστε:

$k=bc$ και $1<b\leq c<k$.

Τότε, σύμφωνα με την υπόθεση της επαγωγής, μπορούμε να γράψουμε $b=p_{1}\cdot \ldots \cdot p_{a}$ και $c=q_{1}\cdot \ldots \cdot q_{d}$, όπου $p_{1},\ldots ,p_{a}$ και $q_{1},\ldots ,q_{d}$ είναι πρώτοι. Επομένως

$k=bc=p_{1}\cdot \ldots \cdot p_{a}\cdot q_{1}\cdot \ldots \cdot q_{d}$.

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

Μοναδικότητα ανάλυσης: Έστω $p_{1}\cdot \ldots \cdot p_{a}=k=q_{1}\cdot \ldots \cdot q_{d}$, με $a\leq d$, δύο αναλύσεις του $k$ σε πρώτους παράγοντες. Παρατηρούμε ότι το $p_{1}$ διαιρεί το $k$. Επομένως, $p_{1}|q_{1}...q_{d}$. Από το λήμμα του Ευκλείδη αυτό συνεπάγεται ότι $p_{1}|q_{j}$ για κάποιο δείκτη $j$. Και επειδή o $q_{j}$ είναι πρώτος, έπεται ότι $p_{1}=q_{j}$. Χωρίς βλάβη της γενικότητας μπορούμε να υποθέσουμε ότι $j=1$ Συνεπώς,

$p_{2}...p_{a}=q_{2}...q_{d}$.

Με την ίδια διαδικασία βρίσκουμε ότι ο πρώτος $p_{2}$ ταυτίζεται με κάποιον από τους πρώτους $q_{2},\ldots ,q_{d}$ που και πάλι χωρίς βλάβη της γενικότητας μπορούμε να υποθέσουμε ότι αυτός είναι ο $q_{2}$. Συνεχίζοντας αυτή την διαδικασία συμπεραίνουμε ότι οι $p_{1},\ldots ,p_{a}$ ταυτίζονται με κάποιους από τους $q_{1},\ldots ,q_{d}$. Χωρίς βλάβη της γενικότητας

$p_{i}=q_{i}$ για κάθε $1\leq i\leq a$.

Επιπλέον, $1=q_{d-a+1}\cdot \ldots \cdot q_{d}$. Αν $d>a$ η ισότητα αυτή είναι αδύνατο να ισχύει, άρα αναγκαστικά $a=d$.

Παρατηρήσεις

Το λήμμα του Ευκλείδη είναι απαραίτητο για την απόδειξη της μοναδικότητας. Το λήμμα ισχύει στο δακτύλιο των ακεραίων αριθμών αλλά δεν ισχύει γενικά σε οποιοδήποτε δακτύλιο αριθμών. Η παρατήρηση αυτή έγινε από τον Γερμανό μαθηματικό Ερνστ Κούμερ το 1843.

Για παράδειγμα, θεωρούμε το σύνολο των φυσικών αριθμών της μορφής $4k+1$. Σε αυτό το σύνολο οι "πρώτοι αριθμοί" είναι αυτοί που δεν μπορούν να γραφτούν σαν το γινόμενο δύο άλλων αριθμών από το σύνολο. Για παράδειγμα, το $9$ είναι "πρώτος" καθώς δεν μπορεί να γραφτεί σαν το γινόμενο δύο τέτοιων αριθμών, ενώ το $45$, δεν είναι καθώς $45=9\cdot 5=(4\cdot 2+1)\cdot (4\cdot 1+1)$.

Σε αυτό το σύνολο το $441$, μπορεί να γραφτεί με δύο τρόπους ως το γινόμενων δύο πρώτων παραγόντων, $441=21\cdot 21=49\cdot 9$.

Κανονική μορφή φυσικών αριθμών

Από το θεμελιώδες θεώρημα της αριθμητικής, αν ομαδοποιήσουμε τους πρώτους παράγοντες που είναι ίσοι, έχουμε ότι κάθε φυσικός αριθμός $n$ μπορεί να γραφτεί ως

$n=p_{1}^{a_{1}}\cdot \ldots \cdot p_{k}^{a_{k}}$,

όπου $a_{1},\ldots ,a_{k}>0$ και $p_{1}<\ldots <p_{k}$ είναι πρώτοι αριθμοί.

Για παράδειγμα,

$120=2^{3}\cdot 3^{1}\cdot 5$

$1200=2^{4}\cdot 3^{1}\cdot 5^{2}$

$385=5^{1}\cdot 7^{1}\cdot 11^{1}$.

Αν επιτρέψουμε τα $a_{i}$ να είναι μηδέν, τότε μπορούμε να εκφράσουμε τον αριθμό $n$ ως το γινόμενο των απείρων όρων

$n=p_{1}^{a_{1}}\cdot p_{2}^{a_{2}}\cdot \ldots$,

όπου $p_{1}=2,p_{2}=3,p_{3}=5,\ldots$ είναι οι πρώτοι αριθμοί.

Δυαδικές πράξεις

Η αναπαράσταση αριθμών στην κανονική τους μορφή επιτρέπει τον εύκολο υπολογισμό διαφόρων δυαδικών πράξεων. Για παράδειγμα, αν ${\textstyle A=\prod _{i=1}^{\infty }p_{i}^{a_{i}}}$ και ${\textstyle B=\prod _{i=1}^{\infty }p_{i}^{b_{i}}}$, τότε

• Ο πολλαπλασιασμός τους είναι ίσος με

$A\cdot B=\prod _{i=1}^{\infty }p_{i}^{a_{i}+b_{i}}$.

• Το ελάχιστο κοινό πολλαπλάσιο τους είναι ίσο με

$\gcd(A,B)=\prod _{i=1}^{\infty }p_{i}^{\min(a_{i},b_{i})}$.

• Ο μέγιστος κοινός διαιρέτης τους είναι ίσος με

$\operatorname {lcm} (A,B)=\prod _{i=1}^{\infty }p_{i}^{\max(a_{i},b_{i})}$.

Πολλαπλασιαστικές συναρτήσεις

Η κανονική μορφή χρησιμεύει στον υπολογισμό διαφόρων πολλαπλασιαστικών συναρτήσεων. Για παράδειγμα, για την συνάρτηση φ του Όιλερ ισχύει ότι

$\varphi (n)=\varphi (p_{1}^{a_{1}})\cdot \varphi (p_{2}^{a_{2}})\cdot \ldots \cdot \varphi (p_{k}^{a_{k}})$.

Πλήθος διαιρετών

Το πλήθος των διαιρετών ενός αριθμού δίνεται από το γινόμενο:

$(a_{1}+1)\cdot (a_{2}+1)\cdot \ldots \cdot (a_{k}+1)$.

Δείτε επίσης

• Λήμμα του Ευκλείδη
• Πρώτος αριθμός