Αρθρωτή Αριθμητική

Εισαγωγή στην Αρθρωτή Αριθμητική

Η αρθρωτή αριθμητική (modular arithmetic) είναι ένα σύστημα αριθμητικής για ακεραίους όπου οι αριθμοί «τυλίγονται» μετά από μια συγκεκριμένη τιμή, τον μέτρο. Είναι η αριθμητική των υπολοίπων.

Ορισμός Ισοδυναμίας

Ορισμός: Δύο ακέραιοι $a$ και $b$ λέγονται ισοδύναμοι modulo $n$ (ή συμβατοί κατά μέτρο $n$) αν έχουν το ίδιο υπόλοιπο όταν διαιρεθούν με $n$.

Ισοδύναμα: $a \equiv b \pmod{n}$ αν και μόνο αν $n \mid (a - b)$.

Συμβολισμός: $a \equiv b \pmod{n}$

Παράδειγμα: $17 \equiv 5 \pmod{6}$ διότι $17 - 5 = 12$ και $6 \mid 12$.

Κλάσεις Υπολοίπων

Για μέτρο $n$, οι ακέραιοι χωρίζονται σε $n$ κλάσεις υπολοίπων:

$$[0], [1], [2], \ldots, [n-1]$$

όπου $[r] = \{\ldots, r-2n, r-n, r, r+n, r+2n, \ldots\}$

Το σύνολο $\mathbb{Z}_n = \{[0], [1], \ldots, [n-1]\}$ ονομάζεται σύνολο κλάσεων υπολοίπων modulo $n$.

Βασικές Ιδιότητες

Για $a \equiv b \pmod{n}$ και $c \equiv d \pmod{n}$:

1. Πρόσθεση: $a + c \equiv b + d \pmod{n}$
2. Αφαίρεση: $a - c \equiv b - d \pmod{n}$
3. Πολλαπλασιασμός: $a \cdot c \equiv b \cdot d \pmod{n}$
4. Δύναμη: $a^k \equiv b^k \pmod{n}$ για κάθε $k \geq 0$

Προσοχή: Η διαίρεση ΔΕΝ ισχύει πάντα!

Διαίρεση στην Αρθρωτή Αριθμητική

Η διαίρεση $a \equiv bc \pmod{n}$ μπορεί να απλοποιηθεί σε $\frac{a}{c} \equiv b \pmod{\frac{n}{\gcd(c,n)}}$ μόνο αν $\gcd(c, n) \mid a$.

Ειδική περίπτωση: Αν $\gcd(c, n) = 1$, τότε μπορούμε να «διαιρέσουμε» με $c$.

Αντίστροφο Στοιχείο

Το αντίστροφο του $a$ modulo $n$ είναι ο αριθμός $a^{-1}$ τέτοιος ώστε:

$$a \cdot a^{-1} \equiv 1 \pmod{n}$$

Θεώρημα: Το $a$ έχει αντίστροφο modulo $n$ αν και μόνο αν $\gcd(a, n) = 1$.

Μικρό Θεώρημα Fermat

Θεώρημα: Αν $p$ πρώτος και $\gcd(a, p) = 1$, τότε:

$$a^{p-1} \equiv 1 \pmod{p}$$

Πόρισμα: Για κάθε $a$ και πρώτο $p$:

$$a^p \equiv a \pmod{p}$$

Θεώρημα Euler

Συνάρτηση Euler: $\phi(n)$ = πλήθος ακεραίων $1 \leq k \leq n$ με $\gcd(k, n) = 1$.

Θεώρημα: Αν $\gcd(a, n) = 1$, τότε:

$$a^{\phi(n)} \equiv 1 \pmod{n}$$

Υπολογισμός $\phi(n)$: Αν $n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots$, τότε:

$$\phi(n) = n \cdot \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$

Κινέζικο Θεώρημα Υπολοίπων

Θεώρημα: Αν $\gcd(m, n) = 1$, το σύστημα:

$$x \equiv a \pmod{m}$$

$$x \equiv b \pmod{n}$$

έχει μοναδική λύση modulo $mn$.