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

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

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

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

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

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

1) Για ${\displaystyle k=2}$ το πρώτο σκέλος είναι προφανές.

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

${\displaystyle k=bc}$ και ${\displaystyle 1}$<${\displaystyle b}$≤${\displaystyle c}$<${\displaystyle k}$

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

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

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

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

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

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

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

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

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

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