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

Ορισμός 2.6   (Πρώτος αριθμός) Ένας ακέραιος $n>1$ λέγεται πρώτος αριθμός αν δεν έχει μη τετριμμένους διαιρέτες, αν δηλ.

$$a \mid n, a>1 \Longrightarrow a=n.$$

Ένας ακέραιος $n>1$ που δεν είναι πρώτος λέγεται σύνθετος αριθμός.

Η ακολουθία των πρώτων αριθμών έχει το αρχικό κομμάτι

$$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, \ldots.$$

Η ακολουθία των σύνθετων αριθμών έχει το αρχικό κομμάτι

$$4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, \ldots.$$

Άσκηση 2.15   Ελέγξτε αν οι αριθμοί 101, 103, 107, 111, 113, 121 είναι πρώτοι.

Άσκηση 2.16   Αν ο $n>1$ δεν είναι πρώτος τότε έχει κάποιο γνήσιο διαιρέτη (όχι το 1 ή το $n$ δηλ.)

$$d<=\sqrt{n}.$$

Υπόδειξη: Αφού δεν είναι πρώτος θα έχει κάποιο γνήσιο διαιρέτη $k$. Υποθέστε ότι $k>\sqrt{n}$ και εξετάστε το μέγεθος του $n/k$.

Άσκηση 2.17  

Με βάση το αποτέλεσμα της Άσκησης 2.16 για να ελέγξουμε αν ένα θετικός ακέραιος $n$ είναι πρώτος αρκεί να ελέγξουμε αν τον διαιρεί κάποιος από τους ακεραίους από το 2 έως τον ακέραιο ${\left\lfloor{\sqrt{n}}\right\rfloor}$. Αυτή τη μέθοδο υλοποιεί η παρακάτω συνάρτηση python.

def isprime(n):
    if n<=1:
        return False
    d = 2
    while d*d <= n: # Check only up to the square root of n
        if n%d == 0:
            return False
        d = d+1
    return True

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

print [x for x in range(2,50) if isprime(x)]

οπότε παίρνετε

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

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

def isprime(n):
    if n<=1:
        return False
    d = 2
    d2 = 4
    while d2 <= n: # Check only up to the square root of n
        if n%d == 0:
            return False
        d2 = d2 + d + d +1
        d = d+1 
    return True

Γιατί δουλεύει;

Άσκηση 2.18   Έστω $n$ σύνθετος και υποθέστε ότι ο μικρότερος πρώτος παράγοντας $p$ του $n$ είναι $>n^{1/3}$. Δείξτε τότε ότι ο $n$ είναι γινόμενο δύο πρώτων (όχι αναγκαστικά διαφορετικών μεταξύ τους).

Θεώρημα 2.4   Υπάρχουν άπειροι πρώτοι αριθμοί.

Απόδειξη. Ας υποθέσουμε ότι υπάρχουν πεπερασμένοι μόνο πρώτοι αριθμοί, οι $p_1, p_2, \ldots, p_n$, και έστω

$$k = p_1 p_2 \cdots p_n + 1.$$

Με βάση την υπόθεσή μας ο $k$ δεν είναι πρώτος, άρα έχει κάποιο μη τετριμμένο διαιρέτη $s$, και ας υποθέσουμε ότι ο $s$ είναι ο μικρότερος μη τετριμμένος διαιρέτης του $k$. Τότε ο $s$ πρέπει να είναι πρώτος, αλλιώς θα είχε κι αυτός ένα μη τετριμμένο διαιρέτη, που θα ήταν και διαιρέτης του $k$ και μικρότερος από τον $s$, πράγμα που αντιφάσκει με το ότι ο $s$ είναι ο μικρότερος μη τετριμμένος διαιρέτης του $k$.

Αφού ο $s$ είναι πρώτος τότε είναι κάποιος από τους $p_1, p_2, \ldots, p_n$, έστω $s = p_t$. Όμως $k=1 \bmod p_t$, άτοπο. $\qedsymbol$

Άσκηση 2.19   Δείξτε ότι υπάρχουν οσοδήποτε μεγάλα διαστήματα $[a, b] \subseteq {\mathbb{N}}$ που δεν περιέχουν πρώτους αριθμούς.

Υπόδειξη: Υπάρχει πρώτος αριθμός ανάμεσα στους αριθμούς

$$10!+2, 10!+3, 10!+4, \ldots, 10!+10;$$

Άσκηση 2.20   Βρείτε τους μικρότερους 5 διαδοχικούς σύνθετους ακεραίους. Βρείτε $10^6$ διαδοχικούς ακεραίους που να είναι σύνθετοι.

Υπόδειξη: Ο αριθμός $2\cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 + 2$ και οι επόμενοι 8 αριθμοί είναι όλοι σύνθετοι.

Άσκηση 2.21   Ας είναι $p_1=2, p_2=3, p_3=5, p_4, \ldots$ οι πρώτοι αριθμοί σε αύξουσα σειρά. Χρησιμοποιώντας τη μέθοδο του Ευκλείδη (για το το ότι υπάρχουν άπειροι πρώτοι, Θεώρημα 2.4) δείξτε ότι

$$p_n \le 2^{2^{n-1}},$$

χρησιμοποιώντας επαγωγή.

Θεώρημα 2.5   Αν $p$ πρώτος αριθμός και $p \mid ab$ τότε $p \mid a$ ή $p \mid b$.

Απόδειξη. Έστω $ab=kp$, $k \in {\mathbb{Z}}$, και $p \nmid a$. Αφού $p$ πρώτος αυτό σημαίνει ότι $(p,a)=1$, και άρα, από το Θεώρημα 2.2, $1 = xa+yp$ για κάποιους $x, y \in {\mathbb{Z}}$. Πολλαπλασιάζοντας επί $b$ παίρνουμε

$$b = x a b + y p b = x k p + y b p = p(ak+yb)$$

άρα $p \mid b$ όπως έπρεπε να δείξουμε. $\qedsymbol$

Παρατήρηση 2.1   Ομοίως αν $p \mid a_1 a_2 \cdots a_k$ τότε το $p$ διαιρεί κάποιο από τα $a_j$ (επαγωγή ως προς $k$).

Θεώρημα 2.6   (Θεμελιώδες Θεώρημα της Αριθμητικής) Κάθε ακέραιος $n>1$ μπορεί να γραφεί με μοναδικό τρόπο ως γινόμενο πρώτων αριθμών στη μορφή

$$n = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$$

όπου $p_1 < p_2 < \cdots < p_r$ είναι διαφορετικοί πρώτοι αριθμοί και $r, e_1, e_2, \ldots, e_r$ είναι θετικοί ακέραιοι.

Παρατήρηση 2.2   Ένας άλλος τρόπος να εκφράσει κανείς αυτό το αποτέλεσμα είναι να πει ότι για κάθε ακέραιο είναι μοναδικά καθορισμένο το ποιοι πρώτοι αριθμοί (και πόσες φορές ο καθένας) εμφανίζονται αν τον διασπάσουμε πολλαπλασιαστικά όσο περισσότερο μπορούμε. Όποτε δηλ. υπάρχει κάποιος μη τετριμμένος διαιρέτης $a$ του αριθμού $n$ τότε γράφουμε $n = a \cdot \frac{n}{a}$ και συνεχίζουμε διασπώντας τους δύο ακεραίους $a$ και $\frac{n}{a}$ όσο αυτό είναι δυνατό (μέχρι αυτοί να γίνουν πρώτοι δηλαδή).

Απόδειξη. [Απόδειξη του Θεωρήματος 2.6] Είναι φανερό (ακολουθώντας την προηγούμενη παρατήρηση) ότι κάθε ακέραιος $n>1$ μπορεί να γραφεί ως γινόμενο πρώτων. Απλά διασπάμε συνεχώς σε γινόμενο μικρότερων αριθμών, όσο μπορούμε να το κάνουμε αυτό. Όταν δε μπορούμε πλέον έχουμε φτάσει σε γινόμενο πρώτων. Αν θέλουμε μπορούμε να δώσουμε και μια πιο τυπική (αλλά όχι περισσότερο διαφωτιστική) απόδειξη με επαγωγή ως προς $n$.

Συνεχίζουμε με επαγωγή για τη μοναδικότητα του αναπτύγματος σε γινόμενο πρώτων.

Για $n=2$ προφανώς ισχύει (η μικρότερη περίπτωση του $n$). Ας υποθέσουμε τώρα ότι ισχύει το θεώρημα για όλους τους ακεραίους μικροτερους από $n$ και πάμε να το αποδείξουμε για το $n$.

Ας υποθέσουμε ότι

$$n = p_1 p_2 \cdots p_r = q_1 q_2 \cdots q_s,$$

όπου $p_1, p_2, \ldots, q_1, q_2, \ldots$ πρώτοι αριθμοί, όχι κατ' ανάγκη πρώτοι μεταξύ τους. Τότε, με βάση το Θεώρημα 2.5 και την παρατήρηση που το ακολουθεί, έπεται ότι το $q_1$ είναι ένα από τα $q_1, q_2, \ldots$. Διαγράφοντας το $p_1$ και από τις δύο μεριές προκύπτει ένας μικρότερος ακέραιος $n' = n/p_1$ που γράφεται με δύο τρόπους ως γινόμενο πρώτων. Από επαγωγή αυτοί οι τρόποι πρέπει να είναι οι ίδιοι. $\qedsymbol$

Λήμμα 2.2   Αν $a, b \ge 1$ τότε $a \mid b$ αν και μόνο αν όλοι οι πρώτοι αριθμοί που εμφανίζονται στην ανάλυση του $a$ εμφανίζονται και στην ανάλυση του $b$ και μάλιστα σε εκθέτη μεγαλύτερο ή ίσο από τον εκθέτη τους στον $a$.

Απόδειξη. Ας υποθέσουμε ότι ο πρώτος $p$ εμφανίζεται στην ανάλυση του $a$ με εκθέτη $e \ge 1$:

$$a = p^e \cdots$$

(ακολουθούν διαφορετικοί πρώτοι). Αν $a \mid b$ τότε $b = ka$, για κάποιο $k \in {\mathbb{Z}}$, οπότε

$$b = ka = k p^e \cdots$$

και άρα ο $p$ εμφανίζεται στον $b$ με εκθέτη τουλάχιστον $e$.

Η αντίστροφη κατεύθυνση είναι εξίσου φανερή αφού αν

$$a = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$

και

$$b = p_1^{e_1'} p_2^{e_2'} \cdots p_k^{e_k'} p_{k+1}^{e_{k+1}'} \cdots p_r^{e_r'}$$

με $e_j' \ge e_j$, $j=1, 2, \ldots, k$, τότε είναι προφανές ότι ο $b$ είναι πολλαπλάσιο του $a$. $\qedsymbol$

Άσκηση 2.22   Ας είναι $a, b \ge 1$ δύο ακέραιοι.

Δείξτε ότι στον $(a,b)$ εμφανίζονται ακριβώς εκείνοι οι πρώτοι αριθμοί που εμφανίζονται και στον $a$ και στον $b$ και μάλιστα με εκθέτη ίσο με τον ελάχιστο εκθέτη που έχουν στους $a, b$.

Ομοίως δείξτε ότι στο $[a, b]$ εμφανίζονται ακριβώς εκείνοι οι πρώτοι αριθμοί που εμφανίζονται στον $a$ ή στον $b$ και μάλιστα με εκθέτη ίσο με το μέγιστο εκθέτη που έχουν στους $a, b$.

Γενικεύστε για περισσότερους από δύο ακεραίους.

Υπόδειξη: Χρησιμοποιήστε το Λήμμα 2.2.

Άσκηση 2.23   Αν $a, b \ge 1$ είναι ακέραιοι δείξτε ότι

$$(a, b) [a, b] = a\cdot b.$$

Άσκηση 2.24   Αν $a,b>0$ είναι μεταξύ τους πρώτοι βρείτε τον $(a^2+b^2, a+b)$.

Άσκηση 2.25   Αν $a$ άρτιος και $b$ περιττός δείξτε $(a,b) = (a/2,b)$. Αν και οι δύο είναι άρτιοι δείξτε $(a,b)=2(a/2,b/2)$.

Άσκηση 2.26   Αν $(a, b)=1$ και $c\mid a+b$ δείξτε $(c,a)=(c,b)=1$.

Άσκηση 2.27   Αν $\alpha$ είναι ρίζα του πολυωνύμου

$$x^n+c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots+c_1x+c_0,$$

όπου $c_0, c_1, \ldots, c_{n-1} \in {\mathbb{Z}}$, δείξτε ότι αν το $\alpha$ δεν είναι ακέραιος τότε είναι άρρητος.

Δείξτε ότι οι αριθμοί $\sqrt{2}, \sqrt[3]{5}, \sqrt[10]{17}$ είναι άρρητοι.

Υπόδειξη: Υποθέστε όχι και γράψτε $\alpha = \frac{k}{l}$ με $(k,l)=1$ και $l>1$. Ας είναι $p$ κάποιος πρώτος διαιρέτης του $l$.

Άσκηση 2.28   Βρείτε την ανάλυση του 4849845 σε γινόμενο πρώτων.

Άσκηση 2.29   Βρείτε όλους τους πρώτους που διαιρούν το 10!. Ομοίως για τον αριθμό ${30 \choose 10}$.

Άσκηση 2.30   Περιγράψτε όλους τους θετικούς ακεραίους που έχουν ακριβώς 3 διαιρέτες (συμπεριλαμβανομένου του 1 και τους εαυτού τους). Ομοίως για ακριβώς 4 διαιρέτες. Ομοίως για ακριβώς 5 διαιρέτες.

Άσκηση 2.31   Δείξτε ότι κάθε θετικός ακέραιος γράφεται σα γινόμενο ενός τέλειου τετραγώνου και ενός αριθμού ελεύθερου τετραγώνων (αυτοί είναι οι ακέραιοι πο υ δε διαιρούνται από το $p^2$ για κανένα πρώτο $p$).

Άσκηση 2.32   Δείξτε ότι η δύναμη με την οποία ο πρώτος $p$ εμφανίζεται στο $n!$ είναι το άθροισμα

$${\left\lfloor{n/p}\right\rfloor} + {\left\lfloor{n/p^2}\right\rfloor} + {\left\lfloor{n/p^3}\right\rfloor} + \cdots.$$

Παρατηρήστε ότι το άθροισμα αυτό έχει πεπερασμένους σε πλήθος μη μηδενικούς όρους αφού για αρκετά μεγάλο $j$ θα έχουμε $n/p^j<1$.

Βρείτε την ανάλυση του 20! σε γινόμενο πρώτων.

Πόσα μηδενικά υπάρχουν στο τέλος του αριθμού 1000!; Πόσα αν τον ίδιο αριθμό τον γράψουμε στο 8-αδικό σύστημα;

Άσκηση 2.33   Ποια ζεύγη ακεραίων $a, b$ έχουν μέγιστο κοινό διαιρέτη $(a,b)=18$ και ελάχιστο κοινό πολλαπλάσιο $[a,b]=240$;

Άσκηση 2.34   Δείξτε $c\mid ab \Longrightarrow c\mid(a,c) (b,c)$.

Άσκηση 2.35   Δείξτε $\sqrt{2}+\sqrt{3} \notin {\mathbb{Q}}$.

Άσκηση 2.36   Δείξτε $\log_2 3 \notin {\mathbb{Q}}$.

Άσκηση 2.37   Δείξτε ότι ο αριθμός

$$1+\frac12+\frac13+\frac14+\cdots+\frac{1}{n}$$

δεν είναι ποτέ ακέραιος αν $n\ge 2$.

Άσκηση 2.38   Δείξτε $(a,b) = (a+b, [a,b])$.

Άσκηση 2.39   Πόσα ζεύγη θετικών ακεραίων $a, b$ υπάρχουν με $[a,b]=n$. Η απάντηση εξαρτάται από την ανάλυση του $n$ σε πρώτους παράγοντες.

Άσκηση 2.40   Δείξτε ότι υπάρχουν άπειροι πρώτοι της μορφής $6k+5$.

Υπόδειξη: Δείξτε πρώτα ότι όλοι οι πρώτοι είναι της μορφής $6k+1$ ή $6k+5$. Υποθέστε ότι υπάρχουν πεπερασμένοι σε πλήθος πρώτοι της μορφής $6k+5$, οι $p_1, p_2, \ldots, p_r$, και εξετάστε τον αριθμό $n = 6p_1p_2\cdots p_r-1$.

Άσκηση 2.41   Αν πάρουμε ένα σύνολο από $n+1$ διαφορετικούς ακεραίους από 1 έως $2n$ δείξτε ότι υπάρχει κάποιος στο σύνολο που διαιρεί κάποιον άλλο αριθμό του συνόλου.