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

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

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

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

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

1) Για  το πρώτο σκέλος είναι προφανές.

2) Έστω ότι για κάθε φυσικό αριθμό  με  ≤  ≤, υπάρχουν πρώτοι αριθμοί , όχι αναγκαστικά διαφορετικοί, έτσι ώστε . Αν ο αριθμός  είναι πρώτος ο ισχυρισμός μας ισχύει. Αν ο  είναι σύνθετος, τότε υπάρχουν  ∈  τέτοια ώστε:
 και <≤<
Τότε, σύμφωνα με την υπόθεση της επαγωγής, μπορούμε να γράψουμε  και , όπου  και  είναι πρώτοι. Επομένως

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

Μοναδικότητα ανάλυσης: Έστω , με ≤, δύο πρωτογενείς αναλύσεις του . Παρατηρούμε ότι το  διαιρεί το . Επομένως, . Από το λήμμα του Ευκλείδη αυτό συνεπάγεται ότι  για κάποιο δείκτη . Και επειδή o  είναι πρώτος, . Χωρίς βλάβη της γενικότητας μπορούμε να υποθέσουμε ότι  Συνεπώς, 

Με την ίδια διαδικασία βρίσκουμε ότι ο πρώτος  ταυτίζεται με κάποιον από τους πρώτους  που και πάλι χωρίς βλάβη της γενικότητας μπορούμε να υποθέσουμε ότι αυτός είναι ο . Συνεχίζοντας αυτή την διαδικασία συμπεραίνουμε ότι οι  ταυτίζονται με κάποιους από τους . Χωρίς βλάβη της γενικότητας
 για κάθε 1≤  ≤ 
Επιπλέον, . Αν  η ισότητα αυτή είναι αδύνατο να ισχύει, άρα αναγκαστικά .

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

Πρώτοι αριθμοί