2.1 Διαιρετότητα, ισοϋπόλοιποι αριθμοί

Θεώρημα 2.1   Αν $a, b \in {\mathbb{Z}}$.$b>0$, τότε υπάρχουν μοναδικοί

$$q \in {\mathbb{Z}},$$

(το πηλίκο), και

$$r \in {\left\{{0, 1, \ldots, b-1}\right\}},$$

(το υπόλοιπο), τέτοιοι ώστε

$$a = b \cdot q + r.$$

Ορισμός 2.1   (Διαιρετότητα, ισοϋπόλοιποι αριθμοί) Αν το υπόλοιπο είναι 0 τότε $a = bq$ και λέμε τότε ότι ο $b$ διαιρεί τον $a$. Γράφουμε $b \mid a$. Το ίδιο λέμε ακόμη και όταν ο $b$ είναι αρνητικός (χωρίς να μιλάμε τότε για το υπόλοιπο της διαίρεσης).

Αν δύο αριθμοί $a_1, a_2$ δίνουν το ίδιο υπόλοιπο $r$ διαιρούμενοι διά $b$ τότε λέμε ότι είναι ισοϋπόλοιποι διά $b$ ή ισοϋπολοιποι $\bmod b$. Γράφουμε επίσης σε αυτή την περίπτωση

$$a_1 \equiv a_2 (b)$$

ή

$$a_1 = a_2 \bmod b.$$

Είναι φανερό ότι δύο ακέραιοι είναι ισοϋπόλοιποι $\bmod b$ αν και μόνο αν το $b$ διαιρεί τη διαφορά τους.

Άσκηση 2.1  

Υπολογίστε τα πηλίκα και υπόλοιπα των διαιρέσεων 5/3 και -5/3.

Στη γλώσσα python η πράξη / υπολογίζει το πηλίκο της διαίρεσης των δύο ακεραίων ορισμάτων της ενώ η πράξη % υπολογίζει το υπόλοιπο. Εκτελέστε και τις δύο παραπάνω διαιρέσεις στην python.

Απόδειξη. [Του Θεωρήματος 2.1:] Η ακέραια ευθεία ${\mathbb{Z}}$ διαμερίζεται στα σύνολα (διαστήματα) της μορφής

$${\left\{{kb, kb+1, kb+2, \ldots, kb+(b-1)}\right\}},$$

στα διαστήματα δηλ. από το ένα πολλαπλάσιο του $b$ στο επόμενο. Ο αριθμός $a$ ανήκει σε ένα μοναδικό τέτοιο διάστημα, έστω στο διάστημα

$$[qb, (q+1)b) \cap {\mathbb{Z}}.$$

Αυτό σημαίνει ότι υπάρχει ένα $r \in {\left\{{0, 1, \ldots, b-1}\right\}}$ τέτοιο ώστε

$$a = qb+r.$$

Ας υποθέσουμε τώρα ότι το $a$ μπορεί να γραφεί και με τη μορφή

$$a = q' b + r',$$

όπου $q' \in {\mathbb{Z}}$, $r \in {\left\{{0, 1, \ldots, b-1}\right\}}$. Αφαιρώντας κατά μέλη τις δύο παραπάνω σχέσεις παίρνουμε

$$r-r' = (q'-q)b,$$

δηλ. ότι ο αριθμός $r-r'$ είναι κάποιο ακέραιο πολλαπλάσιο του $b$. Επειδή όμως

$$0 \le r < b, 0 \le r' < b,$$

έχουμε ότι

$$-b < r-r' < b,$$

και το μόνο πολλαπλάσιο του $b$ σε αυτό το εύρος είναι το 0. Άρα $r = r'$ και επίσης $q = q'$, οπότε έχουμε αποδείξει και τη μοναδικότητα του ζεύγους πηλίκου, υπολοίπου πέρα από την ύπαρξη. $\qedsymbol$

Άσκηση 2.2   Αποδείξτε τις παρακάτω βασικές ιδιότητες της διαιρετότητας:

1. $a \mid \pm a$
2. $a \mid b, b \mid a \Longrightarrow a = \pm b$
3. $a \mid b, b \mid c \Longrightarrow a \mid c$
4. $a \mid b, a \mid c \Longrightarrow a \mid kb+lc, \forall k, l \in {\mathbb{Z}}$
5. $a = b \bmod c, a' = b' \bmod c \Longrightarrow a \pm a' = b \pm b' \bmod c$
6. $a = b \bmod c, a' = b' \bmod c \Longrightarrow a \cdot a' = b \cdot b' \bmod c$

Άσκηση 2.3   Αν $a \mid b$ και $k \ge 1$ δείξτε $a^k \mid b^k$.

Ορισμός 2.2   (Ακέραιο μέρος, κλασματικό μέρος) Με ${\left\lfloor{x}\right\rfloor}$ συμβολίζουμε το ακέραιο μέρος του πραγματικού αριθμού $x$, δηλ. το μεγαλύτερο ακέραιο $k$ που ικανοποιεί $k \le x$. Επίσης με ${\left\{{x}\right\}}$ συμβολίζουμε το κλασματικό μέρος του πραγματικού αριθμού $x$, δηλ. ${\left\{{x}\right\}} = x-{\left\lfloor{x}\right\rfloor}$.

Άσκηση 2.4   Δείξτε ότι $n$ άρτιος αν και μόνο αν $n = 2{\left\lfloor{n/2}\right\rfloor}$.

Άσκηση 2.5   Πόσοι ακέραιοι $\le 1000$ δε διαιρούνται ούτε από το 3 ούτε από το 5.

Άσκηση 2.6   Δείξτε $3 \mid n^3-n$.

Υπόδειξη: Παραγοντοποιήστε το $n^3-n$ πρώτα. Εναλλακτικά χρησιμοποιήστε την Άσκηση 2.2: αν $r$ είναι το υπόλοιπο του $n$ διά 3 τότε $n^3-n = r^3-r \bmod 3$ και άρα αρκεί να εξετάσετε όλα τα διαφορετικά $r$.

Άσκηση 2.7   Δείξτε ότι το τετράγωνο κάθε περιττού είναι της μορφής $8n+1$.

Άσκηση 2.8   Το γινόμενο δύο ακεραίων της μορφής $6n+5$ είναι της μορφής $6n+1$.

Άσκηση 2.9   Δείξτε ότι $5 \mid n^5-n$.

Υπόδειξη: Χρησιμοποιήστε την Άσκηση 2.2 και εξετάστε όλα τα δυνατά υπόλοιπα του $n$ διά 5.

Άσκηση 2.10  

Δείξτε ότι $9 \mid n^3 + (n+1)^3 + (n+2)^3$.

Υπόδειξη: Μπορείτε να το λύσετε χρησιμοποιώντας και πάλι την Άσκηση 2.2. Αν βαριέστε να εξετάσετε και τις 9 περιπτώσεις τότε μπορείτε να χρησιμοποιήσετε το παρακάτω απλό πρόγραμμα σε python.

for r in range(9):
    k = r**3+(r+1)**3+(r+2)**3
    print k%9

Εναλλακτικά μπορείτε να κάνετε πράξεις στο δεξί μέλος και να χρησιμοποιήσετε την Άσκηση 2.6.

Άσκηση 2.11   Η ακολουθία Fibonacci ορίζεται ως εξής:

$$f_1 = f_2 = 1, f_n = f_{n-1} + f_{n-2} \gamma\iota\alpha n\ge 3.$$

Δείξτε με επαγωγή ότι:
(α) $2 \mid f_n \Longleftrightarrow 3 \mid n$.
(β) $3 \mid f_n \Longleftrightarrow 4 \mid n$.
(γ) $4 \mid f_n \Longleftrightarrow 6 \mid n$.

Άσκηση 2.12   Δείξτε ότι ${\left\lfloor{(2+\sqrt{3})^n}\right\rfloor}$ είναι περιττός.

Υπόδειξη: Δείξτε πρώτα χρησιμοποιώντας το διωνυμικό θεώρημα $(a+b)^N = \sum_{j=0}^N {N \choose j}a^jb^{N-j}$ ότι

$$(2+\sqrt{3})^n+(2-\sqrt{3})^n$$

είναι ακέραιος και μάλιστα άρτιος. Έπειτα παρατηρήστε ότι $-1 < (2-\sqrt{3})^n <0$.