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

Το θεμελιώδες θεώρημα της αριθμητικής μας λέει ότι κάθε φυσικός αριθμός μεγαλύτερος από το 1 μπορεί να αναλυθεί μονοσήμαντα σε γινόμενο πρώτων αριθμών. Για παράδειγμα, ο αριθμός 15 αναλύεται σε γινόμενο δύο πρώτων αριθμών 3 · 5, ο αριθμός 30 σε γινόμενο τριών πρώτων αριθμών 2 · 3 · 5 και ο αριθμός 16 σε γινόμενο τεσσάρων πρώτων αριθμών 2 · 2 · 2 · 2. Ένα τέτοιο γινόμενο το λέμε ανάλυση σε γινόμενο πρώτων παραγόντων. Λέμε λοιπόν ότι η ανάλυση του αριθμού 10 σε γινόμενο πρώτων παραγόντων είναι 2 · 5.

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

Υπολόγισε την ανάλυση σε γινόμενο πρώτων παραγόντων

Τι μας λέει το θεμελιώδες θεώρημα της αριθμητικής

Το θεμελιώδες θεώρημα της αριθμητικής μας λέει δύο πράγματα:

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

Ας αποδείξουμε ότι πράγματι ισχύει αυτό.

Απόδειξη της ύπαρξης

Πρώτα θα αποδείξουμε ότι για κάθε φυσικό αριθμό μεγαλύτερο από το 1 υπάρχει πράγματι τουλάχιστον μία ανάλυση σε γινόμενο πρώτων παραγόντων. Θα χρησιμοποιήσουμε τη μαθηματική επαγωγή. Το αρχικό βήμα της επαγωγής είναι να πούμε ότι ο μικρότερος φυσικός αριθμός που είναι μεγαλύτερος από το 1, δηλαδή ο αριθμός 2, είναι πρώτος.

Τώρα θα δείξουμε ότι αν έχουμε μια ακολουθία αριθμών 2, …, n, για τους οποίους μπορούμε να βρούμε ανάλυση σε γινόμενο πρώτων παραγόντων, τότε όταν προσθέσουμε σε αυτή την ακολουθία τον αριθμό n + 1, υπάρχει ανάλυση και για αυτόν τον νέο αριθμό. Πρώτα ας το δούμε σε ένα παράδειγμα.

Στην αρχή η ακολουθία μας 2, …, n είναι κάπως εκφυλισμένη, επειδή περιέχει μόνο έναν αριθμό, τον αριθμό 2. Λέμε ότι όταν προσθέσουμε σε αυτή την ακολουθία τον αριθμό n + 1, δηλαδή τον αριθμό 3, τότε για αυτόν τον αριθμό θα υπάρχει ανάλυση σε γινόμενο πρώτων παραγόντων. Επειδή ο αριθμός 3 είναι πρώτος, για αυτόν φυσικά υπάρχει ανάλυση – είναι ο αριθμός 3.

Η ακολουθία μας 2, …, n έχει τώρα δύο όρους: 2, 3. Προσθέτουμε στην ακολουθία τον αριθμό 4. Ο αριθμός 4 δεν είναι πρώτος, άρα πρέπει να μπορεί να αναλυθεί σε γινόμενο δύο άλλων φυσικών αριθμών, που είναι μεγαλύτεροι από το 1, αλλά μικρότεροι από το 4. Όλοι αυτοί οι αριθμοί όμως ανήκουν στην ακολουθία μας! Και σε αυτή την ακολουθία υπάρχουν μόνο αριθμοί που έχουν ανάλυση σε γινόμενο πρώτων παραγόντων! Άρα και ο αριθμός 4 πρέπει να έχει ανάλυση: 2 · 2.

Επιστρέφοντας στη γενική απόδειξη, μπορούμε να γράψουμε ότι ο αριθμός 2 είναι πρώτος και άρα έχει ανάλυση σε γινόμενο πρώτων παραγόντων. Ας υποθέσουμε τώρα ότι κάθε αριθμός της ακολουθίας 2, …, n μπορεί να αναλυθεί σε γινόμενο πρώτων παραγόντων – αυτή είναι η επαγωγική μας υπόθεση. Τότε ο αριθμός n + 1 είναι είτε πρώτος και άρα αναλύεται τετριμμένα σε πρώτους, είτε είναι σύνθετος αριθμός. Για αυτόν τον αριθμό πρέπει λοιπόν να υπάρχουν αριθμοί a, b τέτοιοι ώστε

$$n+1=a\cdot b$$

και πρέπει να ισχύει ότι αυτοί οι φυσικοί αριθμοί είναι φυσικά μικρότεροι από το n + 1 και μεγαλύτεροι από το 1:

$$\begin{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

Οι αριθμοί a, b πρέπει επομένως να ανήκουν στην ακολουθία 2, …, n. Για κάθε αριθμό αυτής της ακολουθίας όμως υπάρχει ανάλυση σε γινόμενο πρώτων παραγόντων (αυτή είναι η επαγωγική μας υπόθεση), δηλαδή μπορούμε να γράψουμε

$$\begin{array}{rcl}a& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ b& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Όπου όλα τα p_i και q_j είναι πρώτοι αριθμοί και τα p₁ · p₂ · … · p_i και q₁ · q₂ · … · q_j είναι έτσι οι αναλύσεις τους σε γινόμενο πρώτων παραγόντων. Επειδή όμως είπαμε ότι το n + 1 αναλύεται στο γινόμενο n + 1 = a · b, ισχύει ταυτόχρονα

$$\begin{array}{rcl}n+1& =& a\cdot b\\ & =& p_1\cdot p_2\cdot \dots \cdot p_i\cdot q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Ο αριθμός n + 1 αναλύεται λοιπόν σε γινόμενο πρώτων αριθμών p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j, δηλαδή και ο νέος αριθμός n + 1 έχει ανάλυση σε γινόμενο πρώτων παραγόντων. Από αυτό προκύπτει ότι κάθε φυσικός αριθμός μεγαλύτερος από το 1 έχει τουλάχιστον μία ανάλυση σε γινόμενο πρώτων παραγόντων.

Απόδειξη της μοναδικότητας

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

$$\begin{array}{rcl}n& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ n& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

Υποθέτουμε επίσης ότι από όλους τους αριθμούς που έχουν περισσότερες αναλύσεις, το n είναι ο μικρότερος. Δηλαδή δεν υπάρχει μικρότερος φυσικός αριθμός που να έχει περισσότερες από μία αναλύσεις. Επειδή το q₁ είναι ένας από τους πρώτους αριθμούς που διαιρούν τον αριθμό n, πρέπει φυσικά να ισχύει ότι το q₁ διαιρεί και τον αριθμό p₁ · p₂ · … · p_i.

Στη συνέχεια πρέπει να χρησιμοποιήσουμε το λήμμα του Ευκλείδη. Αυτό λέει ότι αν ένας πρώτος αριθμός p διαιρεί το γινόμενο δύο ακεραίων αριθμών a · b, τότε το p διαιρεί τουλάχιστον έναν από τους αριθμούς a ή b. Για παράδειγμα: ο πρώτος αριθμός 3 διαιρεί τον αριθμό 84. Τον αριθμό 84 μπορούμε να τον αναλύσουμε στο γινόμενο 12 · 7. Το λήμμα του Ευκλείδη λέει ότι ο πρώτος αριθμός 3 διαιρεί τουλάχιστον έναν από τους αριθμούς 12 ή 7 – σε αυτή την περίπτωση διαιρεί τον αριθμό 12.

Χρησιμοποιώντας αυτό το λήμμα μπορούμε να πούμε ότι αφού το q₁ διαιρεί το p₁ · p₂ · … · p_i, πρέπει να διαιρεί και τουλάχιστον έναν από τους αριθμούς p₁, p₂, …, p_i. Μπορούμε να υποθέσουμε – χωρίς βλάβη της γενικότητας – ότι το q₁ διαιρεί τον αριθμό p₁. Το p₁ όμως είναι επίσης πρώτος αριθμός. Πότε μπορεί ένας πρώτος αριθμός να διαιρεί έναν άλλο πρώτο αριθμό; Για παράδειγμα, ποιος πρώτος αριθμός διαιρείται με τον πρώτο αριθμό 7; Πάλι μόνο ο πρώτος αριθμός 7. Δεν μπορεί να διαιρεί άλλον πρώτο αριθμό, γιατί τότε εκείνος δεν θα ήταν πρώτος. Πρέπει λοιπόν να ισχύει p₁ = q₁.

Αυτό σημαίνει ότι και στις δύο αναλύσεις υπάρχει ένας πρώτος αριθμός που είναι ο ίδιος: ο πρώτος αριθμός p₁, αντίστοιχα q₁. Ας διαιρέσουμε τις δύο εξισώσεις με το p₁, αντίστοιχα με το q₁:

$$\begin{array}{rcl}\frac{n}{p_1}& =& \frac{p_1\cdot p_2\cdot \dots \cdot p_i}{p_1}\\ \frac{n}{q_1}& =& \frac{q_1\cdot q_2\cdot \dots \cdot q_j}{q_1}\end{array}$$

Επειδή p₁ = q₁, στο αριστερό μέλος παίρνουμε τον ίδιο αριθμό, ας τον συμβολίσουμε, ας πούμε, με m. Ισχύει λοιπόν ότι

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

Στο δεξιό μέλος απλώς απλοποιούμε τα κλάσματα:

$$\begin{array}{rcl}m& =& p_2\cdot p_3\cdot \dots \cdot p_i\\ m& =& q_2\cdot q_3\cdot \dots \cdot q_j\end{array}$$

Ο αριθμός m είναι σίγουρα φυσικός αριθμός που είναι μικρότερος από τον αριθμό n, επειδή το m προέκυψε διαιρώντας το n με έναν από τους πρώτους παράγοντές του. Στο δεξιό μέλος των εξισώσεων έχουμε όμως και στις δύο περιπτώσεις ανάλυση του αριθμού m σε γινόμενο πρώτων παραγόντων. Καταφέραμε λοιπόν να κατασκευάσουμε έναν άλλο αριθμό m, που είναι μικρότερος από το n και που έχει επίσης δύο διαφορετικές αναλύσεις. Αυτό όμως έρχεται σε αντίφαση με την υπόθεσή μας ότι το n είναι ο μικρότερος αριθμός που έχει περισσότερες από μία αναλύσεις.

Η μόνη εξήγηση λοιπόν είναι ότι δεν υπάρχει κανένας «μικρότερος αριθμός με περισσότερες από μία αναλύσεις». Και το ότι δεν υπάρχει «μικρότερος αριθμός με περισσότερες από μία αναλύσεις» σημαίνει ότι δεν υπάρχει ούτε ένας αριθμός με περισσότερες αναλύσεις – κάθε ακέραιος αριθμός μεγαλύτερος από το ένα έχει επομένως ακριβώς μία μοναδική ανάλυση σε γινόμενο πρώτων παραγόντων.