7. Teoria liczb#
7.1. Podzielność w zbiorze \(\zz\)#
Definicja 7.1
Liczba \(b\in\zz\) jest podzielna przez \(a\in\zz\) (liczba \(a\) dzieli \(b\)), co oznaczamy \(a\mid b\), jeśli
Liczbę \(a\) nazywamy wtedy dzielnikiem liczby \(b\), zaś liczbę \(b\) – wielokrotnością liczby \(a .\)
Stwierdzenie 7.1
Dla dowolnych \(a,b,c,d\in\zz\) zachodzi:
\(a\mid b \ \wedge\ b\mid c \ \imply\ a \mid c\)
\(a\mid b \ \wedge\ c\mid d \ \imply\ ac\mid bd\)
\(a\mid b \ \wedge\ a\mid c \ \imply\ a\mid (bx+cy)\) dla dowolnych \(x,y\in\zz\)
\(a\mid b \ \wedge\ b\mid a \ \imply\ a=b \ \vee\ a=-b .\)
Przykład 7.1
Ilustracja własności: \(\quad a\mid b \wedge b\mid c \implies a\mid c\)
mamy: \(\quad 3\mid 12 \quad\) oraz \(\quad 12\mid 36\)
zatem: \(\quad 3 \mid 36\)
rzeczywiście: \(\quad 36 = 3 \cdot 12\)
Ilustracja własności: \(\quad a\mid b \wedge c\mid d \implies ac\mid bd\)
mamy: \(\quad 3\mid 12 \quad\) oraz \(\quad 5\mid 20\)
zatem: \(\quad 3 \cdot 5 = 15 \quad\) dzieli \(\quad 12 \cdot 20 = 240\)
rzeczywiście: \(\quad 240 = 15 \cdot 16\)
Ilustracja własności: \(\quad a\mid b \wedge a\mid c \implies a\mid (bx+cy)\)
wiemy: \(\quad 3\mid 12 \quad\) oraz \(\quad 3\mid 15\)
weźmy \(\quad x = 2\), \(\quad y = -1\)
wtedy: \(\quad bx + cy = 12 \cdot 2 + 15 \cdot (-1) = 24 - 15 = 9\)
rzeczywiście: \(\quad 3\mid 9\)
Ilustracja własności: \(\quad a\mid b \wedge b\mid a \implies a = b \vee a = -b\)
niech \(\quad a = 6\), \(\quad b = -6\)
mamy: \(\quad 6\mid (-6) \quad\) oraz \(\quad (-6)\mid 6\)
zatem: \(\quad a = -b\)
Kontrprzykład:
jeśli \(\quad a = 4\), \(b = 8\): \(\quad 4\mid 8\), ale \(8\nmid 4\)
dlatego nie zachodzi \(\quad a = \pm b\)
7.1.1. Dzielenie z resztą#
Twierdzenie 7.2
Dla dowolnych liczb całkowitych \(a\) i \(d\neq 0\) istnieją jednoznacznie wyznaczone liczby całkowite \(q\) i \(r\) takie, że
Definicja 7.2
Dla danych liczb całkowitych \(a\) i \(d\neq 0\)
liczbę \(a\) z powyższego twierdzenia nazywamy dzielną
liczbę \(d\) – dzielnikiem
liczbę \(q\) – ilorazem
liczbę \(r\) – resztą z dzielenia \(a\) przez \(b\).
Przykład 7.2
Dzielenie z resztą liczb naturalnych jest dla nas intuicyjne, ale dla liczb całkowitych ujemnych pojawiają się niespodzianki:
dla \(\quad a=11, d=4, \quad\) dostajemy \(\quad q=2, r=3, \quad\) gdyż \(\quad 11=2\cdot 4+3\)
dla \(\quad a=11, d=-4, \quad\) dostajemy \(\quad q=-2, r=3, \quad\) gdyż \(\quad 11=(-2)\cdot(-4)+3\)
dla \(\quad a=-11, d=4, \quad\) dostajemy \(\quad q=-3, r=1, \quad\) gdyż \(\quad -11=(-3)\cdot 4+1\)
dla \(\quad a=-11, d=-4, \quad\) dostajemy \(\quad q=3, r=1, \quad\) gdyż \(\quad -11=3\cdot(-4)+1 .\)
7.1.2. Liczby pierwsze#
Definicja 7.3
Liczbę \(n\in\nn\) nazywamy liczbą pierwszą, jeśli
\(n>1\),
\(d\mid n \ \imply\ d=1 \ \vee\ d=n .\)
Każdą liczbę naturalną \(n>1\), która nie jest pierwsza, nazywamy liczbą złożoną.
Zbiór wszystkich liczb pierwszych oznaczamy \(\mathbb P .\)
Twierdzenie 7.3 (Euklides)
Istnieje nieskończenie wiele liczb pierwszych.
Dowód
Przypuśćmy, że liczb pierwszych jest skończenie wiele: \(p_1,\ldots,p_k .\)
Liczba
nie jest podzielna przez żadną z liczb \(p_1,\ldots,p_k\).
Zatem \(N\) jest liczbą pierwszą lub dzieli się przez jakąś inną liczbę pierwszą.
Jest to sprzeczność z założeniem, że \(p_1,\ldots,p_k\) są wszystkimi liczbami pierwszymi.
Twierdzenie 7.4
Każda liczba złożona \(n\) ma dzielnik pierwszy \(p\leq\sqrt n .\)
Dowód
Jeśli \(\quad n=ab, \quad\) przy czym \(\quad 1<a \leq b < n, \quad\) to \(\quad a^2\leq ab=n, \quad\) więc \(\quad a\leq\sqrt n .\)
Dowolny dzielnik pierwszy \(p\) liczby \(a\) spełnia \(\quad p\leq a\leq\sqrt n .\)
Uwaga 7.1 (Sito Eratostenesa)
Aby wypisać wszystkie liczby pierwsze \(\leq n\), wystarczy z listy liczb od \(2\) do \(n\) wykreślić wielokrotności każdej liczby pierwszej \(p\leq\sqrt n\) – liczby, które pozostaną, są dokładnie liczbami pierwszymi \(\leq n .\)
Stwierdzenie 7.5 (Istnienie rozkładu na czynniki pierwsze)
Każda liczba naturalna \(n > 1\) jest liczbą pierwszą lub da się przedstawić jako iloczyn liczb pierwszych.
7.1.3. Zasadnicze Twierdzenie Arytmetyki#
Stwierdzenie 7.6 (Zasada minimum)
Każdy niepusty podzbiór zbioru liczb naturalnych \(\mathbb{N}\) posiada element najmniejszy.
Twierdzenie 7.7 (Zasadnicze twierdzenie arytmetyki)
Każdą liczbę naturalną \(n\geq 2\) można jednoznacznie przedstawić w postaci kanonicznej
gdzie \(p_1 < p_2 < \ldots < p_r\) są liczbami pierwszymi, zaś \(\alpha_1, \ldots, \alpha_r \in\nn .\)
Dowód (Zermelo)
Jedyne co pozostaje pokazać, to jednoznaczności rozkładu na czynniki pierwsze.
Przypuśćmy nie wprost, że istnieją liczby naturalne posiadające więcej niż jeden rozkład na czynniki pierwsze.
Wybór najmniejszego kontrprzykładu
Na mocy zasady minimum istnieje najmniejsza liczba naturalna \(n > 1\), która ma dwa różne rozkłady na czynniki pierwsze:
\[n = p_1 \cdot p_2 \cdot \dots \cdot p_r = q_1 \cdot q_2 \cdot \dots \cdot q_s\]gdzie \(p_i\) oraz \(q_j\) są liczbami pierwszymi.
Brak wspólnych czynników
Żadna liczba \(p_i\) nie może być równa żadnej liczbie \(q_j\).
Gdyby np. \(p_1 = q_1\), moglibyśmy podzielić obie strony przez tę liczbę i otrzymać mniejszą liczbę \(n' = n / p_1\), która również miałaby dwa różne rozkłady.
To przeczyłoby założeniu, że \(n\) jest najmniejszym takim kontrprzykładem.
Bez straty ogólności przyjmijmy, że \(p_1 < q_1\).
Konstrukcja mniejszej liczby \(m\)
Rozważmy liczbę:
\[m = (q_1 - p_1) \cdot q_2 \cdot \dots \cdot q_s\]Zauważmy dwie własności liczby \(m\):
Ponieważ \(1 < q_1 - p_1 < q_1\), to \(1 < m < n\).
Przekształcając wzór na \(m\):
\[m = q_1 \cdot q_2 \cdot \dots \cdot q_s - p_1 \cdot q_2 \cdot \dots \cdot q_s = n - p_1 \cdot q_2 \cdot \dots \cdot q_s\]Podstawiając \(n = p_1 \cdot p_2 \cdot \dots \cdot p_r\):
\[m = p_1 \cdot p_2 \cdot \dots \cdot p_r - p_1 \cdot q_2 \cdot \dots \cdot q_s = p_1 \cdot (p_2 \dots p_r - q_2 \dots q_s)\]Sprzeczność
Ponieważ \(m < n\), a \(n\) było najmniejszym kontrprzykładem, liczba \(m\) musi mieć jednoznaczny rozkład na czynniki pierwsze.
Z drugiego wzoru wynika, że \(p_1\) dzieli \(m\), więc \(p_1\) musi występować w (jedynym) rozkładzie \(m\) na czynniki pierwsze.
Z pierwszego wzoru \(m = (q_1 - p_1) \cdot q_2 \dots q_s\) wynika zatem, że \(p_1\) musi dzielić iloczyn \((q_1 - p_1) \cdot q_2 \dots q_s\).
Liczba \(p_1\) jest pierwsza i różna od wszystkich \(q_2, \dots, q_s\), więc musi występować w rozkładzie czynnika \((q_1 - p_1)\).
Oznacza to, że \(p_1\) dzieli \((q_1 - p_1)\), czyli \(q_1 - p_1 = k \cdot p_1\) dla pewnego \(k \ge 1\).
Stąd \(q_1 = (k + 1) \cdot p_1\), co oznacza, że \(p_1\) dzieli \(q_1\).
Otrzymujemy sprzeczność z założeniem, że \(q_1\) jest liczbą pierwszą (gdyż \(1 < p_1 < q_1\)).
Uwaga 7.2
Liczby pierwsze są atomami konstrukcyjnymi wszystkich liczb złożonych.
Jeśli liczba ma rozkład \(n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_m^{\alpha_m}\), to jej łączna liczba dzielników wynosi:
\[ d(n) = (\alpha_1 + 1)(\alpha_2 + 1)\cdots(\alpha_m + 1). \]Brak jednoznaczności uniemożliwiłby definiowanie właściwości liczb, takich jak podzielność czy największy wspólny dzielnik lub najmniejsza wspolna wielokrotność (które zdefiniujemy w następnym rozdziale).
W wyższych działach algebry istnieją struktury (tzw. pierścienie), w których jednoznaczność rozkładu nie zachodzi.
Na przykład, w zbiorze liczb całkowitych parzystych \(2\zz\) (które są pierścieniem) liczby \(2, 6, 10, 30\) są nierozkładalne – nie są iloczynami dwóch liczb parzystych.
Tymczasem \(60 = 2\cdot 30 = 6\cdot 10\) – rozkład nie jest jednoznaczny.
To pokazuje, jak wyjątkowy i fundamentalny jest zbiór zwykłych liczb całkowitych.
Przykład 7.3
Ponieważ \(\quad 17640=2^3\cdot 3^2\cdot 5\cdot 7^2, \quad\) to liczba dzielników tej liczby jest równa
7.2. Współpodzielność w \(\zz\)#
7.2.1. \(\NWD\) i \(\NWW\)#
Narration
Niech \(a,b\in\zz\), przy czym \(a\neq 0\) lub \(b\neq 0 .\)
Definicja 7.4
Największym wspólnym dzielnikiem liczb całkowitych\(a\) i \(b\) nazywamy liczbę \(d\in\zz\) spełniającą warunki:
\(d\mid a \ \wedge\ d\mid b\),
\(\forall c\in\zz\quad (c\mid a \ \wedge\ c\mid b) \ \imply\ c\leq d .\)
Największy wspólny dzielnik liczb \(a,b\) oznaczamy \(\NWD(a,b) .\)
Definicja 7.5
Najmniejszą wspólną wielokrotnością liczb \(a\) i \(b\) nazywamy liczbę \(d\in\zz\) spełniającą warunki:
\(a\mid d \ \wedge\ b\mid d\),
\(\forall c\in\zz\quad (a\mid c \ \wedge\ b\mid c) \ \imply\ d\leq c .\)
Najmniejsza wspólna wielokrotność liczb \(a,b\) oznaczamy \(\NWW(a,b) .\)
Uwaga 7.3
Powyższe definicje nie mają sensu, gdy \(a=b=0\), gdyż zbiór dzielników \(0\) to \(\zz\). Jednak z pewnych powodów (związanych z pojęciem ideału w pierścieniach) wielu autorów przyjmuje, że \(\NWD(0,0) = \NWW(0,0) = 0\).
Twierdzenie 7.8
Niech \(a, b \in \zz\) będą dowolnymi liczbami całkowitymi takimi, że \((a, b) \neq (0, 0)\), zaś \(d \in \nn\). Następujące warunki są równoważne:
Definicja porządkowa (klasyczna):
\[ d = \NWD(a,b). \]Definicja algebryczna:
\(d \mid a\) oraz \(d \mid b ,\)
\(\forall c \in \zz \quad c \mid a \ \wedge\ c \mid b \ \imply\ c \mid d .\)
Własność uniwersalna
Dla dowolnego \(d\in\zz\) zachodzi
\[d\mid a \ \wedge\ d\mid b \quad\imply\quad d\mid \NWD(a,b).\]Tożsamość Bézouta:
\[ d = \min \{ xa + yb \mid x, y \in \zz \text{ oraz } xa + yb > 0 \} . \]Suma ideałów:
Zachodzi równość \(a\zz + b\zz = d\zz\), czyli zbiór
\[ \{ xa + yb : x, y \in \zz \} \]jest dokładnie równy zbiorowi wielokrotności liczby \(d\).
Kanoniczny rozkład na czynniki pierwsze:
Jeśli
\[ a = \pm \prod_{i=1}^k p_i^{\alpha_i}, \qquad b = \pm \prod_{i=1}^k p_i^{\beta_i} \]dla różnych liczb pierwszych \(p_i\) oraz wykładników \(\alpha_i, \beta_i \ge 0\), to
\[ d = \prod_{i=1}^k p_i^{\min(\alpha_i, \beta_i)} . \]Charakterystyka przez NWW:
\[ d \cdot \NWW(a, b) = \vert{}a \cdot b\vert{} . \]Warunek ilorazów względnie pierwszych:
\(d \mid a\) oraz \(d \mid b\), oraz \( \NWD \left(\frac{a}{d}, \frac{b}{d}\right) = 1. \)
Przykład 7.4
Niech \(a = 240\) oraz \(b = 560\).
Ich największy wspólny dzielnik wynosi \(d = 80\).
Oto ilustracja wszystkich warunków z twierdzenia dla tych liczb:
Definicja porządkowa:
Liczba \(80\) dzieli \(240\) i \(560\).
Każdy inny wspólny dzielnik (np. \(1, 2, 4, 8, 10, 16, 20, 40\)) jest mniejszy bądź równy \(80\).
Definicja algebraiczna:
Zachodzi \(80 \mid 240\) oraz \(80 \mid 560\). Każdy wspólny dzielnik liczb \(240\) i \(560\) dzieli także liczbę \(80\).
Własność uniwersalna:
Dla dowolnego \(c \in \zz\), jeśli \(c \mid 240\) oraz \(c \mid 560\), to \(c \mid \NWD(240, 560) = 80\).
Tożsamość Bézouta:
Liczba \(80\) jest najmniejszą dodatnią kombinacją liniową liczb \(240\) i \(560\):
\[80 = (-2) \cdot 240 + 1 \cdot 560\]Równość ideałów:
Zbiór wszystkich kombinacji \(240x + 560y\) dla \(x,y \in \zz\) to dokładnie zbiór wielokrotności liczby \(80\):
\[240\zz + 560\zz = 80\zz\]Kanoniczny rozkład na czynniki pierwsze:
Rozkłady liczb wynoszą \(240 = 2^4 \cdot 3^1 \cdot 5^1 \cdot 7^0\) oraz \(560 = 2^4 \cdot 3^0 \cdot 5^1 \cdot 7^1\).
Stąd:
\[\NWD(240, 560) = 2^{\min(4,4)} \cdot 3^{\min(1,0)} \cdot 5^{\min(1,1)} \cdot 7^{\min(0,1)} = 2^4 \cdot 3^0 \cdot 5^1 \cdot 7^0 = 80\]Charakterystyka przez NWW:
Najmniejsza wspólna wielokrotność to \(\text{NWW}(240, 560) = 1680\).
Iloczyn \(80 \cdot 1680 = 134400\) jest równy \(\vert{}240 \cdot 560\vert{} = 134400\).
Warunek ilorazów względnie pierwszych:
Zachodzi \(80 \mid 240\) oraz \(80 \mid 560\).
Ilorazy \(\dfrac{240}{80} = 3\) oraz \(\dfrac{560}{80} = 7\) mają tylko jeden wspólny dzielnik, czyli \(1 = \NWD(3, 7)\).
Twierdzenie 7.9
Niech \(a, b \in \zz\) będą dowolnymi liczbami całkowitymi takimi, że \((a, b) \neq (0, 0)\), zaś \(m \in \nn\). Następujące warunki są równoważne:
Definicja porządkowa (klasyczna):
\[ m = \NWW(a,b). \]Definicja algebraiczna:
\(a \mid m\) oraz \(b \mid m ,\)
\(\forall k \in \zz \quad a \mid k \ \wedge\ b \mid k \ \imply\ m \mid k .\)
Własność uniwersalna (kres górny):
Dla dowolnego \(k \in \zz\) zachodzi:
\[ a\mid k \ \wedge\ b\mid k \quad\imply\quad \NWW(a,b) \mid k . \]Przecięcie ideałów (podgrup):
Zachodzi równość \(a\zz \cap b\zz = m\zz\), czyli zbiór wspólnych wielokrotności liczb \(a\) i \(b\) jest dokładnie równy zbiorowi wielokrotności liczby \(m\).
Kanoniczny rozkład na czynniki pierwsze:
Jeśli
\[ a = \pm \prod_{i=1}^k p_i^{\alpha_i}, \qquad b = \pm \prod_{i=1}^k p_i^{\beta_i} \]dla różnych liczb pierwszych \(p_i\) oraz wykładników \(\alpha_i, \beta_i \ge 0\), to
\[ m = \prod_{i=1}^k p_i^{\max(\alpha_i, \beta_i)} . \]Charakterystyka przez NWD:
\[ m \cdot \NWD(a, b) = \vert{}a \cdot b\vert{} . \]
7.2.2. Algorytm Euklidesa#
Stwierdzenie 7.10
Niech \(a, d, q, r \in \zz\) spełniają równość \(a = d\cdot q + r\). Wówczas:
Algorytm 7.1 (Algorytm Euklidesa)
Wejście: Liczby całkowite \(a, b \in \zz\) takie, że \((a, b) \neq (0, 0)\).
Wyjście: \(d = \NWD(a, b)\).
Przyjmij \(r_0 = |a|\) oraz \(r_1 = |b|\).
Dopóki \(r_1 \neq 0\):
Wyznacz resztę \(r_2\) z dzielenia \(r_0\) przez \(r_1\), czyli
\[ r_0 = q \cdot r_1 + r_2, \quad \text{ gdzie } 0 \le r_2 < r_1. \]Przyjmij \(r_0 \leftarrow r_1\).
Przyjmij \(r_1 \leftarrow r_2\).
Zwróć \(d = r_0\).
Uwaga 7.4
Algorytm wykonuje skończoną liczbę kroków.
Ciąg reszt
jest ściśle malejący i ograniczony z dołu przez zero.
Gwarantuje to, że po pewnej liczbie kroków otrzymamy resztę równą zero.
Na mocy powyższego stwierdzenia zachodzą równości
Z definicji \(\NWD\) dla dowolnej liczby niezerowej zachodzi \(\NWD(r_k, 0) = r_k\).
Ostatnia niezerowa reszta jest więc szukanym największym wspólnym dzielnikiem.
Uwaga 7.5 (Współczynniki Bézouta – Rozszerzony Algorytm Euklidesa)
Współczynniki \(x, y \in \zz\) spełniające równość \(xa + yb = \NWD(a,b)\) znajdujemy, wykonując Algorytm Euklidesa „od tyłu”.
Każda reszta \(r_i\) z kolejnych kroków dzielenia
daje się zapisać jako kombinacja liniowa \(r_i = r_{i-2} - q_i \cdot r_{i-1}\).
Zaczynamy od ostatniej niezerowej reszty \(d = r_k\).
Krok po kroku podstawiamy w jej miejscu wcześniejsze reszty z odpowiednich równań.
Po zwinięciu wyrażenia do postaci \(xa + yb\) otrzymujemy szukane współczynniki.
W praktyce obliczenia te wykonuje się równolegle z krokami algorytmu (tzw. Rozszerzony Algorytm Euklidesa).
Przykład 7.5
Dla \(a=12378\), \(b=3054\):
Zatem \(\NWD(12378,3054)=6 .\)
Podstawiając wstecz, znajdujemy współczynniki Bézouta:
Ćwiczenie 7.1
Korzystając z algorytmu Euklidesa znajdźmy \(\NWD(252, 180)\) oraz liczby \(x,y\in\zz\) takie, że \(\NWD(252,180) = 252x+180y .\)
Rozwiązanie
Stąd \(\NWD(252,180)=36 .\) Podstawiając wstecz:
więc można przyjąć \(x=-2,\ y=3 .\)
7.2.3. Liczby względnie pierwsze#
Definicja 7.6
Liczby \(a,b\in\zz\) nazywamy względnie pierwszymi, jeśli
Wniosek 7.11
Niech \(a, b \in \zz\) będą dowolnymi liczbami całkowitymi takimi, że \((a, b) \neq (0, 0)\). Następujące warunki są równoważne:
Liczby \(a,b\) są względnie pierwsze.
Tożsamość Bézouta (odwracalność kombinacji):
Istnieją takie \(x, y \in \zz\), że:
\[ xa + yb = 1. \]Suma ideałów:
Zachodzi równość ideałów \(a\zz + b\zz = \zz\), czyli dla każdej liczby \(c\in\zz\) istnieją takie \(x, y \in \zz\), że:
\[ xa + yb = c. \]Własność NWW:
\[ \NWW(a, b) = |a \cdot b|. \]Brak wspólnych dzielników pierwszych:
Dla każdej liczby pierwszej \(p \in \nn\) zachodzi warunek:
\[ p \nmid a \quad \vee \quad p \nmid b. \]Lemat Euklidesa (dzielenie iloczynu):
Dla każdego \(c \in \zz\):
\[ a \mid bc \quad \imply \quad a \mid c. \]Jednoczesna podzielność:
Dla każdego \(c \in \zz\):
\[ (a \mid c \ \wedge \ b \mid c) \quad \imply \quad ab \mid c. \]
Przykład 7.6
Niech \(a = 8\) oraz \(b = 15\). Liczby te są względnie pierwsze.
Oto ilustracja poszczególnych warunków z twierdzenia dla tych liczb:
Definicja porządkowa:
Jedynymi dodatnimi dzielnikami liczby \(8\) są \(\{1, 2, 4, 8\}\), a liczby \(15\) to \(\{1, 3, 5, 15\}\).
Największym wspólnym dzielnikiem jest \(\NWD(8, 15) = 1\).
Tożsamość Bézouta:
Istnieje kombinacja liniowa równa \(1\):
\[2 \cdot 8 + (-1) \cdot 15 = 16 - 15 = 1\]Suma ideałów:
Każdą liczbę całkowitą \(k \in \zz\) można zapisać w postaci \(8x + 15y\).
Przykładowo dla \(k = 3\):
\[3 = 3 \cdot (2 \cdot 8 - 1 \cdot 15) = 6 \cdot 8 + (-3) \cdot 15\]Stąd \(8\zz + 15\zz = \zz\).
Własność NWW:
Najmniejsza wspólna wielokrotność wynosi \(\NWW(8, 15) = 120\).
Zachodzi równość \(120 = |8 \cdot 15|\).
Brak wspólnych dzielników pierwszych:
Rozkłady na czynniki pierwsze to \(8 = 2^3\) oraz \(15 = 3 \cdot 5\).
Zbiory ich czynników pierwszych \(\{2\}\) i \(\{3, 5\}\) są rozłączne.
Lemat Euklidesa:
Niech \(c = 24\). Liczba \(8\) dzieli iloczyn \(15 \cdot 24 = 360\) (gdyż \(360 = 8 \cdot 45\)).
Ponieważ \(\NWD(8, 15) = 1\), liczba \(8\) musi dzielić \(c = 24\) (gdyż \(24 = 8 \cdot 3\)).
Jednoczesna podzielność:
Niech \(c = 240\).
Liczba \(8\) dzieli \(240\) oraz liczba \(15\) dzieli \(240\).
Stąd ich iloczyn \(8 \cdot 15 = 120\) również dzieli \(240\) (gdyż \(240 = 120 \cdot 2\)).
7.3. Arytmetyka modularna#
Definicja 7.7
Przy ustalonym \(n\in\nn,\) liczby \(a,b\in\zz\) są przystające modulo \(n\) lub przystają modulo \(n\), co zapisujemy
jeśli \(n\mid (a-b) .\)
Twierdzenie 7.12
Niech \(n \in \nn\) będzie ustalone. Jeśli \(a \equiv b \pmod{n}\) i \(c \equiv d \pmod{n}\), to:
Dodawanie: \(a + c \equiv b + d \pmod{n}\)
Odejmowanie: \(a - c \equiv b - d \pmod{n}\)
Mnożenie: \(ac \equiv bd \pmod{n}\)
Potęgowanie: \(a^k \equiv b^k \pmod{n}\) dla każdego \(k \in \nn_0\).
Uwaga 7.6
Wcześniej dla ustalonego \(n\in \nn\), zdefiniowaliśmy relację przystawania modulo \(n\) w zbiorze \(\zz\) (zwaną również relacją kongruencji modulo \(n\)):
Jest ona zwrotna, symetryczna i przechodnia – jest relacją równoważności.
Jej klasami abstrakcji są zbiory
\[ [a]_{\equiv_n} = \Set{z \in \zz : z \equiv_n a} = \Set{z \in \zz : n\mid(z-a)}= \Set{a+k n : k \in \zz}, \]czyli zbiory liczb mających tę samą resztę z dzielenia przez \(n\), co liczba \(a\) – klasa reszt lub klasa kongruencji.
Zbiorem ilorazowym tej relacji jest
\[ \zz_n := \zz/_{\equiv_n}=\Set{[0]_{\equiv_n},[1]_{\equiv_n},\ldots,[n-1]_{\equiv_n}} . \]
Ponieważ \(\zz_n\) jest jednym z podstawowych obiektów badań w teorii liczb (i całej matematyce), to najczęściej upraszcza się zapis jego elementów do postaci
Na mocy twierdzenia Tw. 7.12 relacja przystawania modulo \(n\) jest zgodna z arytmetycznymi operacjami dodawania, odejmowania, mnożenia i potęgowania.
Możemy zatem wykonywać obliczenia „modulo \(n\)” na klasach kongruencji – wynik nie będzie będzie zależał od wyboru reprezentantów.
To pozwala zdefiniować operacje na elementach zbioru \(\zz_n\).
Definicja 7.8
W zbiorze \(\zz_n = \{0, 1, \ldots, n-1\}\) definiujemy operacje dodawania i mnożenia na klasach reszt:
Dodawanie: \([a]_n + [b]_n := [a + b]_n\)
Mnożenie: \([a]_n \cdot [b]_n := [ab]_n\)
gdzie po prawej stronie operacje wykonywane są w \(\zz\).
Twierdzenie 7.13
Dla operacji dodawania i mnożenia w \(\zz_n\) zachodzą następujące własności:
Przemienność dodawania:
\[ a + b \equiv b + a \pmod{n} \quad \text{ czyli } \quad [a]_n + [b]_n = [b]_n + [a]_n\]Łączność dodawania:
\[ (a + b) + c \equiv a + (b + c) \pmod{n} \quad \text{ czyli } \quad ([a]_n + [b]_n) + [c]_n = [a]_n + ([b]_n + [c]_n)\]Element neutralny dodawania:
\[ a + 0 \equiv a \pmod{n} \quad \text{dla każdego } a \in \zz_n\]Element przeciwny:
Dla każdego \(a \in \zz_n\) istnieje \(b \in \zz_n\) takie, że
\[ a + b \equiv 0 \pmod{n} \quad \text{ czyli } \quad [a]_n + [b]_n = [0]_n\](mianowicie \(b \equiv -a \equiv n - a \pmod{n}\) dla \(a \neq 0\))
Przemienność mnożenia:
\[ ab \equiv ba \pmod{n} \quad \text{ czyli } \quad [a]_n \cdot [b]_n = [b]_n \cdot [a]_n\]Łączność mnożenia:
\[ (ab)c \equiv a(bc) \pmod{n} \quad \text{ czyli } \quad ([a]_n \cdot [b]_n) \cdot [c]_n = [a]_n \cdot ([b]_n \cdot [c]_n)\]Element neutralny mnożenia:
\[ a \cdot 1 \equiv a \pmod{n} \quad \text{dla każdego } a \in \zz_n\]Element \(a \in \zz_n\) jest odwracalny (posiada element odwrotny \(a^{-1}\) taki, że
\[ a \cdot a^{-1} \equiv 1 \pmod{n} \quad \text{ czyli } \quad [a]_n \cdot [a^{-1}]_n = [1]_n\]wtedy i tylko wtedy, gdy \(\NWD(a, n) = 1\).
Rozdzielność mnożenia względem dodawania:
\[ a(b + c) \equiv ab + ac \pmod{n} \quad \text{ czyli } \quad [a]_n \cdot ([b]_n + [c]_n) = [a]_n \cdot [b]_n + [a]_n \cdot [c]_n\]
Przykład 7.7
Działania w \(\zz_5\).
Pracujemy z resztami \(\{0, 1, 2, 3, 4\}\) modulo \(5\):
\(3 + 4 \equiv 7 \equiv 2 \pmod{5}\)
\(3 \cdot 4 \equiv 12 \equiv 2 \pmod{5}\)
Element przeciwny do \(3\) to: \(\quad -3 \equiv 2 \pmod{5} .\)
Rzeczywiście \(3 + 2 = 5 \equiv 0 \pmod{5}\).
Element odwrotny do \(2\): \(\quad\) szukamy \(x\) takiego, że \(2x \equiv 1 \pmod{5}\).
Odpowiedź: \(x = 3 , \quad\) bo \(2 \cdot 3 = 6 \equiv 1 \pmod{5}\).
Działania w \(\zz_6\).
Pracujemy z resztami \(\{0, 1, 2, 3, 4, 5\}\) modulo \(6\):
\(4 + 5 \equiv 9 \equiv 3 \pmod{6}\)
\(4 \cdot 5 \equiv 20 \equiv 2 \pmod{6}\)
Element przeciwny do \(4\) to: \(\quad -4 \equiv 2 \pmod{6} .\)
Rzeczywiście \(4 + 2 = 6 \equiv 0 \pmod{6}\).
Element odwrotny do \(5\): \(\quad\) szukamy \(x\) takiego, że \(5x \equiv 1 \pmod{6}\).
Odpowiedź: \(x = 5 , \quad\) bo \(5 \cdot 5 = 25 = 4 \cdot 6 + 1 \equiv 1 \pmod{6}\).
Elementy odwracalne: \(\quad\) to te \(a\), dla których \(\NWD(a, 6) = 1\).
Są to \(\{1, 5\}\) – odpowiadające liczbom pierwszym względem \(6\).
Twierdzenie 7.14 (Twierdzenie Wilsona)
Liczba \(n>1\) jest pierwsza wtedy i tylko wtedy, gdy
Uwaga 7.7
Twierdzenie Wilsona daje charakteryzację liczb pierwszych.
Obliczeniowo – bardzo nieefektywną, ale jednak.
Dla liczby złożonej \(n > 4\) mamy \(\quad (n-1)! \equiv 0 \pmod{n}\).
Jeśli \(n = p^k\) (potęga liczby pierwszej, \(k \geq 2\)):
W iloczynie \((n-1)!\) pojawiają czynniki \(p, 2p, \ldots k p\).
Ich iloczyn \(p^k \cdot k!\) jest podzielny przez \(p^k\).
Zatem \(n\) dzieli \((n-1)!\).
Jeśli \(n = p \cdot q \cdot \ldots\) (co najmniej dwa różne dzielniki pierwsze):
Zarówno \(p\) jak i \(q\) są mniejsze od \(n\) – są czynnikami w \((n-1)!\).
Zatem \(n\) dzieli \((n-1)!\).
Dla liczby pierwszej \(p\) iloczyn wszystkich elementów odwracalnych w \(\zz_p\) (czyli liczb \(1, 2, \ldots, p-1\)) wynosi \(-1\) modulo \(p\).
Przykład 7.8
Sprawdzamy, czy \(7\) jest liczbą pierwszą, stosując twierdzenie Wilsona.
Obliczamy iloczyn kolejnych reszt modulo \(7\):
Otrzymujemy: \(6! \equiv -1 \pmod{7}\) – liczba \(7\) jest pierwsza.
Twierdzenie 7.15 (Małe Twierdzenie Fermata – MTF)
Niech \(p\in\mathbb P\) i niech \(a\in\zz .\) Wówczas
Jeśli dodatkowo \(p\nmid a\), to
Uwaga 7.8
MTF pozwala na szybki, probabilistyczny test sprawdzający, czy dana liczba jest pierwsza, co jest kluczowe przy generowaniu kluczy kryptograficznych.
Jeśli \(a^{n-1} \not\equiv 1 \pmod{n}\) dla pewnego \(a\) względnie pierwszego z \(n\), to \(n\) jest złożona.
To pozwala szybko eliminować liczby złożone bez rozkładania ich na czynniki.
Istnieją liczby złożone \(n\) zwane liczbami Carmichaela, dla których \(a^{n-1} \equiv 1 \pmod{n}\) dla każdego \(a\) względnie pierwszego z \(n\).
Najmniejszą liczbą Carmichaela jest \(561 = 3 \cdot 11 \cdot 17\).
Takie liczby są trudne do „złapania” za pomocą prostych testów opartych na MTF.
MTF drastycznie przyspiesza obliczanie dużych potęg modulo liczby pierwszej.
Zamiast obliczać \(a^{b} \pmod{p}\), redukujemy wykładnik:
\[ a^{b} \equiv a^{b \bmod (p-1)} \pmod{p}. \]Umożliwia to szybkie potęgowanie modularne w kryptografii.
Przykład 7.9
Obliczmy \(7^{200} \pmod{11}\) korzystając z Małego Twierdzenia Fermata.
Ponieważ \(11\) jest liczbą pierwszą i \(\NWD(7, 11) = 1\), z MTF wynika:
Redukujemy wykładnik modulo \(10\):
Stąd:
Porównanie efektywności:
Bez MTF musielibyśmy obliczać \(7^{200}\) przez wielokrotne podnoszenie do kwadratu modulo \(11\) – około \(8\) operacji.
Z MTF redukujemy do \(7^0 \equiv 1 \pmod{11}\) – praktycznie natychmiast.
Dla większych wykładników i modułów różnica jest dramatyczna.
7.4. Funkcja Eulera#
Definicja 7.9
Funkcja Eulera \(\varphi:\nn\to\nn\) zlicza, ile liczb ze zbioru \(\{1, \dots, n\}\) nie dzieli z \(n\) żadnego wspólnego czynnika poza jedynką:
Uwaga 7.9
Funkcja Eulera ma duże znaczenie zarówno teoretyczne, jak i praktyczne.
Arytmetyka modularna: Liczba elementów odwracalnych w \(\zz_n\) wynosi dokładnie \(\varphi(n)\).
Optymalizacja algorytmów: Umożliwia szybkie potęgowanie modularne dzięki twierdzeniu Eulera (patrz Tw. 7.17).
Kryptografia: Bezpieczeństwo kluczy w szyfrowaniu RSA opiera się na trudności obliczenia \(\varphi(n)\) bez znajomości rozkładu \(n\) na czynniki pierwsze.
Przykład 7.10
Dla liczby pierwszej \(p\):
Wszystkie liczby mniejsze są względnie pierwsze, więc \(\varphi(p) = p - 1\).
Dla potęgi liczby pierwszej \(p^k\):
Należy odrzucić tylko wielokrotności \(p\), stąd \(\varphi(p^k) = p^k - p^{k-1} = p^k \left(1 - \frac{1}{p}\right)\).
Pokażmy, że \(\varphi(100) = 40\).
Liczby względnie pierwsze z \(100\) to te, które nie dzielą się ani przez \(2\), ani przez \(5\).
W zakresie \(1\) do \(100\) jest \(50\) liczb nieparzystych (odrzucamy wielokrotności \(2\)).
Spośród nich odrzucamy te dzielące się przez \(5\): to \(5, 15, 25, 35, 45, 55, 65, 75, 85, 95\) – łącznie \(10\) liczb.
Pozostaje \(50 - 10 = 40\) liczb względnie pierwszych z \(100\).
Twierdzenie 7.16
Multiplikatywność:
Jeśli \(\NWD(m, n) = 1\), to \(\varphi(mn) = \varphi(m)\varphi(n)\).
Iloczyn Eulera:
Dla \(n = p_1^{\alpha_1}\cdots p_r^{\alpha_r}\) zachodzi:
\[ \varphi(n) = n \cdot \prod_{i=1}^r \left(1 - \frac{1}{p_i}\right) = n\cdot \left(1 - \frac{1}{p_1}\right)\cdots \left(1 - \frac{1}{p_2}\right). \]Tożsamość Gaussa:
Suma wartości \(\varphi\) po wszystkich dzielnikach daje liczbę \(n\):
\[ \sum_{d \mid n} \varphi(d) = n. \]
Przykład 7.11
Dla \(n = 360 = 2^3 \cdot 3^2 \cdot 5^1\) odrzucamy wielokrotności czynników \(2, 3, 5\) i korzystając z iloczynu Eulera otrzymujemy:
To jednocześnie oznacza, że istnieje dokładnie \(96\) liczb z zakresu \(1\dots 360\), które są odwracalne w modulo \(360\).
Twierdzenie 7.17 (Twierdzenie Eulera)
Jeśli \(\NWD(a,n)=1\), to
Uwaga 7.10
Małe Twierdzenie Fermata jest szczególnym przypadkiem Twierdzenia Eulera.
Istotnie, dla liczby pierwszej \(p\) mamy \(\varphi(p) = p - 1\), więc warunek \(a^{\varphi(p)} \equiv 1 \pmod{p}\) przyjmuje postać \(a^{p-1} \equiv 1 \pmod{p}\).
Ćwiczenie 7.2
Obliczmy \(\varphi(100)\), a następnie resztę z dzielenia \(7^{200}\) przez \(100 .\)
Rozwiązanie
Ponieważ \(100=2^2\cdot 5^2\), to
Ponieważ \(\NWD(7,100)=1\), z twierdzenia Eulera \(7^{40}\equiv 1\pmod{100} .\)
Ponieważ \(200=40\cdot 5\), to
7.5. Rozmieszczenie liczb pierwszych#
Twierdzenie 7.18 (Euler)
Szereg \(\displaystyle\sum_{p\in\mathbb P}\frac 1 p\) oraz iloczyn \(\displaystyle\prod_{p\in\mathbb P}\left(1-\frac 1 p\right)^{-1}\) są rozbieżne.
Definicja 7.10
Dla \(x\in\rr\) funkcję
nazywamy funkcją liczącą liczby pierwsze.
Twierdzenie 7.19 (Czebyszew)
Przykład 7.12
Dla \(n=10^6\): \(\pi(10^6)=78498\), natomiast \(\dfrac{10^6}{\ln 10^6}\approx 72382 .\)
Twierdzenie 7.20 (Postulat Bertranda)
Dla każdej liczby \(n\in\nn\) istnieje liczba pierwsza \(p\) taka, że \(n<p\leq 2n .\)
Uwaga 7.11
Z drugiej strony istnieją dowolnie długie ciągi kolejnych liczb naturalnych, wśród których nie ma ani jednej liczby pierwszej: dla \(n\geq 2\) wszystkie liczby
są złożone, bo \(k\mid n!+k\) dla każdego \(k=2,\ldots,n .\)
Twierdzenie 7.21 (Dirichlet)
Jeśli \(m\in\nn\), \(a\in\zz\) i \(\NWD(a,m)=1\), to ciąg arytmetyczny \((a+mk)_{k\in\nn_0}\) zawiera nieskończenie wiele liczb pierwszych.
Przykład 7.13
Istnieje nieskończenie wiele liczb pierwszych postaci \(4k+1\) oraz nieskończenie wiele postaci \(4k-1 .\)
Uwaga 7.12 (Hipoteza Goldbacha)
W 1742 roku pruski matematyk Christian Goldbach w liście do Leonharda Eulera postawił następującą hipotezę:
Każda parzysta liczba naturalna \(n\geq 4\) jest sumą dwóch liczb pierwszych.
Hipoteza pozostaje otwarta, ale została zweryfikowana komputerowo dla wszystkich \(n<4\cdot 10^{17} .\)