--- title: "Teoria liczb" lecture_number: 6 has_solutions: true has_exercises: true file_format: mystnb kernelspec: name: sagemath display_name: SageMath --- ```{include} ../_includes/sagecell-loader.md ``` # Teoria liczb ## Podzielność w zbiorze $\zz$ :::{prf:definition} Liczba $b\in\zz$ jest {index}`podzielność` **podzielna** przez $a\in\zz$ (liczba $a$ **dzieli** $b$), co oznaczamy $a\mid b$, jeśli ```{math} \exists c\in\zz\quad b=ac. ``` Liczbę $a$ nazywamy wtedy {index}`dzielnik` **dzielnikiem** liczby $b$, zaś liczbę $b$ -- {index}`wielokrotność` **wielokrotnością** liczby $a .$ ::: :::{prf:proposition} Dla dowolnych $a,b,c,d\in\zz$ zachodzi: 1. $a\mid b \ \wedge\ b\mid c \ \imply\ a \mid c$ 2. $a\mid b \ \wedge\ c\mid d \ \imply\ ac\mid bd$ 3. $a\mid b \ \wedge\ a\mid c \ \imply\ a\mid (bx+cy)$ dla dowolnych $x,y\in\zz$ 4. $a\mid b \ \wedge\ b\mid a \ \imply\ a=b \ \vee\ a=-b .$ ::: :::{prf:example} 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$ 2. 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$ 3. 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$ 4. 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$ 5. Kontrprzykład: - jeśli $\quad a = 4$, $b = 8$: $\quad 4\mid 8$, ale $8\nmid 4$ - dlatego **nie** zachodzi $\quad a = \pm b$ ::: ### Dzielenie z resztą :::{prf:theorem} :label: m-lec-07-thm-dzielenie Dla dowolnych liczb całkowitych $a$ i $d\neq 0$ istnieją jednoznacznie wyznaczone liczby całkowite $q$ i $r$ takie, że ```{math} a= d\cdot q + r, \qquad 0\leq r<|d|. ``` ::: :::{prf:definition} Dla danych liczb całkowitych $a$ i $d\neq 0$ - liczbę $a$ z powyższego twierdzenia nazywamy {index}`dzielna` **dzielną** - liczbę $d$ -- {index}`dzielnik` **dzielnikiem** - liczbę $q$ -- {index}`iloraz` **ilorazem** - liczbę $r$ -- {index}`reszta` **resztą** z dzielenia $a$ przez $b$. ::: :::{prf:example} 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 .$ ::: ### Liczby pierwsze :::{prf:definition} Liczbę $n\in\nn$ nazywamy {index}`liczba pierwsza` **liczbą pierwszą**, jeśli 1. $n>1$, 2. $d\mid n \ \imply\ d=1 \ \vee\ d=n .$ Każdą liczbę naturalną $n>1$, która nie jest pierwsza, nazywamy {index}`liczba złożona` **liczbą złożoną**. Zbiór wszystkich liczb pierwszych oznaczamy $\mathbb P .$ ::: :::{prf:theorem} Euklides Istnieje nieskończenie wiele liczb pierwszych. ::: :::{proof} :class: proof Przypuśćmy, że liczb pierwszych jest skończenie wiele: $p_1,\ldots,p_k .$ Liczba $$ N=p_1 p_2 \cdots p_k + 1 $$ 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. ::: :::{prf:theorem} Każda liczba złożona $n$ ma dzielnik pierwszy $p\leq\sqrt n .$ ::: :::{proof} :class: proof Jeśli $\quad n=ab, \quad$ przy czym $\quad 1 1$ jest liczbą pierwszą lub da się przedstawić jako iloczyn liczb pierwszych. ::: ### Zasadnicze Twierdzenie Arytmetyki :::{prf:proposition} Zasada minimum Każdy niepusty podzbiór zbioru liczb naturalnych $\mathbb{N}$ posiada element najmniejszy. ::: :::{prf:theorem} Zasadnicze twierdzenie arytmetyki Każdą liczbę naturalną $n\geq 2$ można jednoznacznie przedstawić w {index}`postać kanoniczna liczby` **postaci kanonicznej** ```{math} n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_r^{\alpha_r}, ``` gdzie $p_1 < p_2 < \ldots < p_r$ są liczbami pierwszymi, zaś $\alpha_1, \ldots, \alpha_r \in\nn .$ ::: :::{proof} Dowód (Zermelo) :class: proof dropdown 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. 1. **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. 2. **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$. 3. **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)$$ 4. **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$). ::: :::{prf:remark} 1. Liczby pierwsze są **atomami** konstrukcyjnymi wszystkich liczb złożonych. 2. 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). $$ 3. 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). 4. 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. ::: :::{prf:example} Ponieważ $\quad 17640=2^3\cdot 3^2\cdot 5\cdot 7^2, \quad$ to liczba dzielników tej liczby jest równa $$ d(17640) = 4\cdot 3\cdot 2 \cdot 3 = 72. $$ ::: ## Współpodzielność w $\zz$ ### $\NWD$ i $\NWW$ :::{narration} Niech $a,b\in\zz$, przy czym $a\neq 0$ lub $b\neq 0 .$ ::: :::{prf:definition} {index}`największy wspólny dzielnik` **Największym wspólnym dzielnikiem** liczb całkowitych$a$ i $b$ nazywamy liczbę $d\in\zz$ spełniającą warunki: 1. $d\mid a \ \wedge\ d\mid b$, 2. $\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) .$ ::: :::{prf:definition} {index}`najmniejsza wspólna wielokrotność` **Najmniejszą wspólną wielokrotnością** liczb $a$ i $b$ nazywamy liczbę $d\in\zz$ spełniającą warunki: 1. $a\mid d \ \wedge\ b\mid d$, 2. $\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) .$ ::: :::{prf:remark} 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$. ::: ::::{prf:theorem} 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: 1. **Definicja porządkowa (klasyczna):** $$ d = \NWD(a,b). $$ 2. **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 .$ 3. **Własność uniwersalna** Dla dowolnego $d\in\zz$ zachodzi ```{math} d\mid a \ \wedge\ d\mid b \quad\imply\quad d\mid \NWD(a,b). ``` 4. **Tożsamość Bézouta:** $$ d = \min \{ xa + yb \mid x, y \in \zz \text{ oraz } xa + yb > 0 \} . $$ 5. **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$. 6. **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)} . $$ 7. **Charakterystyka przez NWW:** $$ d \cdot \NWW(a, b) = \vert{}a \cdot b\vert{} . $$ 8. **Warunek ilorazów względnie pierwszych:** :::{container} center-text $d \mid a$ oraz $d \mid b$, oraz $ \NWD \left(\frac{a}{d}, \frac{b}{d}\right) = 1. $ ::: :::: :::{prf:example} 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: 1. **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$. 2. **Definicja algebraiczna:** Zachodzi $80 \mid 240$ oraz $80 \mid 560$. Każdy wspólny dzielnik liczb $240$ i $560$ dzieli także liczbę $80$. 3. **Własność uniwersalna:** Dla dowolnego $c \in \zz$, jeśli $c \mid 240$ oraz $c \mid 560$, to $c \mid \NWD(240, 560) = 80$. 4. **Tożsamość Bézouta:** Liczba $80$ jest najmniejszą dodatnią kombinacją liniową liczb $240$ i $560$: $$80 = (-2) \cdot 240 + 1 \cdot 560$$ 5. **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$$ 6. **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$$ 7. **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$. 8. **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)$. ::: ::::{prf:theorem} 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: 1. **Definicja porządkowa (klasyczna):** $$ m = \NWW(a,b). $$ 2. **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 .$ 3. **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 . $$ 4. **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$. 5. **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)} . $$ 6. **Charakterystyka przez NWD:** $$ m \cdot \NWD(a, b) = \vert{}a \cdot b\vert{} . $$ :::: ### Algorytm Euklidesa ::::{prf:proposition} Niech $a, d, q, r \in \zz$ spełniają równość $a = d\cdot q + r$. Wówczas: $$ \NWD(a, d) = \NWD(d, r). $$ :::: ::::{prf:algorithm} Algorytm Euklidesa **Wejście:** Liczby całkowite $a, b \in \zz$ takie, że $(a, b) \neq (0, 0)$. **Wyjście:** $d = \NWD(a, b)$. 1. Przyjmij $r_0 = |a|$ oraz $r_1 = |b|$. 2. 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$. 3. Zwróć $d = r_0$. :::: ::::{prf:remark} Algorytm wykonuje skończoną liczbę kroków. Ciąg reszt $$ r_0 > r_1 > r_2 > \dots \ge 0 $$ 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 $$ \NWD(a, b) = \NWD(r_0, r_1) = \NWD(r_1, r_2) = \dots = \NWD(r_k, 0). $$ 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. :::: ::::{prf:remark} 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 $$ r_{i-2} = q_i \cdot r_{i-1} + r_i $$ 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). :::: :::{prf:example} Dla $a=12378$, $b=3054$: ```{math} \begin{aligned} 12378 & = 4\cdot 3054+162, \\ 3054 & = 18\cdot 162+138, \\ 162 & = 1\cdot 138+24, \\ 138 & = 5\cdot 24+18, \\ 24 & = 1\cdot 18+6, \\ 18 & = 3\cdot 6+0. \end{aligned} ``` Zatem $\NWD(12378,3054)=6 .$ Podstawiając wstecz, znajdujemy współczynniki Bézouta: ```{math} \begin{aligned} 6 & = 24-18 = 24-(138-5\cdot 24)=6\cdot 24-138 \\ & = 6\cdot(162-138)-138 = 6\cdot 162-7\cdot 138 \\ & = 6\cdot 162-7\cdot(3054-18\cdot 162)=132\cdot 162-7\cdot 3054 \\ & = 132\cdot(12378-4\cdot 3054)-7\cdot 3054=132\cdot 12378+(-535)\cdot 3054. \end{aligned} ``` ::: ::::{exercise} :label: m-lec-07-ex-01 :class: [exercise] Korzystając z algorytmu Euklidesa znajdźmy $\NWD(252, 180)$ oraz liczby $x,y\in\zz$ takie, że $\NWD(252,180) = 252x+180y .$ :::: :::{solution-without-reference} :class: [solution] dropdown ```{math} \begin{aligned} 252 & = 1\cdot 180+72, \\ 180 & = 2\cdot 72+36, \\ 72 & = 2\cdot 36+0. \end{aligned} ``` Stąd $\NWD(252,180)=36 .$ Podstawiając wstecz: ```{math} 36 = 180-2\cdot 72 = 180-2\cdot(252-180)=3\cdot 180-2\cdot 252, ``` więc można przyjąć $x=-2,\ y=3 .$ ::: ### Liczby względnie pierwsze :::{prf:definition} Liczby $a,b\in\zz$ nazywamy {index}`liczby względnie pierwsze` **względnie pierwszymi**, jeśli ```{math} \NWD(a,b)=1. ``` ::: ::::{prf:corollary} 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: 1. Liczby $a,b$ są **względnie pierwsze**. 2. **Tożsamość Bézouta (odwracalność kombinacji):** Istnieją takie $x, y \in \zz$, że: $$ xa + yb = 1. $$ 3. **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. $$ 4. **Własność NWW:** $$ \NWW(a, b) = |a \cdot b|. $$ 5. **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. $$ 6. **Lemat Euklidesa (dzielenie iloczynu):** Dla każdego $c \in \zz$: $$ a \mid bc \quad \imply \quad a \mid c. $$ 7. **Jednoczesna podzielność:** Dla każdego $c \in \zz$: $$ (a \mid c \ \wedge \ b \mid c) \quad \imply \quad ab \mid c. $$ :::: ::::{prf:example} Niech $a = 8$ oraz $b = 15$. Liczby te są względnie pierwsze. Oto ilustracja poszczególnych warunków z twierdzenia dla tych liczb: 1. **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$. 2. **Tożsamość Bézouta:** Istnieje kombinacja liniowa równa $1$: $$2 \cdot 8 + (-1) \cdot 15 = 16 - 15 = 1$$ 3. **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$. 4. **Własność NWW:** Najmniejsza wspólna wielokrotność wynosi $\NWW(8, 15) = 120$. Zachodzi równość $120 = |8 \cdot 15|$. 5. **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. 6. **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$). 7. **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$). :::: ## Arytmetyka modularna :::{prf:definition} Przy ustalonym $n\in\nn,$ liczby $a,b\in\zz$ są **przystające modulo $n$** {index}`liczby; przystające modulo` lub **przystają modulo $n$**, co zapisujemy ```{math} a\equiv b \pmod n, ``` jeśli $n\mid (a-b) .$ ::: :::{prf:theorem} :label: thm-arytmetyka-modularna-wlasnosci Niech $n \in \nn$ będzie ustalone. Jeśli $a \equiv b \pmod{n}$ i $c \equiv d \pmod{n}$, to: 1. **Dodawanie:** $a + c \equiv b + d \pmod{n}$ 2. **Odejmowanie:** $a - c \equiv b - d \pmod{n}$ 3. **Mnożenie:** $ac \equiv bd \pmod{n}$ 4. **Potęgowanie:** $a^k \equiv b^k \pmod{n}$ dla każdego $k \in \nn_0$. ::: :::{prf:remark} Wcześniej dla ustalonego $n\in \nn$, zdefiniowaliśmy **relację przystawania modulo $n$** w zbiorze $\zz$ (zwaną również **relacją kongruencji modulo $n$**): ```{math} \equiv_n \ = \ \Set{(z_1,z_2)\in \zz\times \zz : n\mid(z_1-z_2)}. ``` - 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 $$ \zz_n = \Set{0, 1, \ldots, n-1}. $$ Na mocy twierdzenia {prf:ref}`thm-arytmetyka-modularna-wlasnosci` 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$. ::: :::{prf:definition} 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$. ::: :::{prf:theorem} Dla operacji dodawania i mnożenia w $\zz_n$ zachodzą następujące własności: 1. **Przemienność dodawania:** ```{math} a + b \equiv b + a \pmod{n} \quad \text{ czyli } \quad [a]_n + [b]_n = [b]_n + [a]_n ``` 2. **Łączność dodawania:** ```{math} (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) ``` 3. **Element neutralny dodawania:** ```{math} a + 0 \equiv a \pmod{n} \quad \text{dla każdego } a \in \zz_n ``` 4. **Element przeciwny:** Dla każdego $a \in \zz_n$ istnieje $b \in \zz_n$ takie, że ```{math} 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$) 5. **Przemienność mnożenia:** ```{math} ab \equiv ba \pmod{n} \quad \text{ czyli } \quad [a]_n \cdot [b]_n = [b]_n \cdot [a]_n ``` 6. **Łączność mnożenia:** ```{math} (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) ``` 7. **Element neutralny mnożenia:** ```{math} a \cdot 1 \equiv a \pmod{n} \quad \text{dla każdego } a \in \zz_n ``` 8. Element $a \in \zz_n$ jest **odwracalny** (posiada element odwrotny $a^{-1}$ taki, że ```{math} 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$. 9. **Rozdzielność mnożenia względem dodawania:** ```{math} 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 ``` ::: :::{prf:example} 1. 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}$. 2. 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$. ::: :::{prf:theorem} Twierdzenie Wilsona :label: m-lec-07-thm-wilson Liczba $n>1$ jest pierwsza wtedy i tylko wtedy, gdy ```{math} (n-1)!\equiv -1 \pmod n. ``` ::: :::{prf:remark} 1. Twierdzenie Wilsona daje charakteryzację liczb pierwszych. Obliczeniowo -- bardzo nieefektywną, ale jednak. 2. 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)!$. 3. Dla liczby pierwszej $p$ iloczyn wszystkich elementów odwracalnych w $\zz_p$ (czyli liczb $1, 2, \ldots, p-1$) wynosi $-1$ modulo $p$. ::: :::{prf:example} Sprawdzamy, czy $7$ jest liczbą pierwszą, stosując twierdzenie Wilsona. Obliczamy iloczyn kolejnych reszt modulo $7$: ```{math} \begin{aligned} 1 \cdot 2 &\equiv 2 \pmod{7} \\ 2 \cdot 3 &\equiv 6 \pmod{7} \\ 6 \cdot 4 &\equiv 24 \equiv 3 \pmod{7} \\ 3 \cdot 5 &\equiv 15 \equiv 1 \pmod{7} \\ 1 \cdot 6 &\equiv 6 \equiv -1 \pmod{7}. \end{aligned} ``` Otrzymujemy: $6! \equiv -1 \pmod{7}$ -- liczba $7$ jest pierwsza. ::: :::{prf:theorem} Małe Twierdzenie Fermata -- MTF :label: m-lec-07-thm-fermat Niech $p\in\mathbb P$ i niech $a\in\zz .$ Wówczas ```{math} a^p\equiv a \pmod p. ``` Jeśli dodatkowo $p\nmid a$, to ```{math} a^{p-1}\equiv 1 \pmod p. ``` ::: :::{prf:remark} 1. 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. 2. 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. 3. 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. ::: :::{prf:example} :class: [example] 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: ```{math} 7^{10} \equiv 1 \pmod{11}. ``` Redukujemy wykładnik modulo $10$: ```{math} 200 = 20 \cdot 10 + 0, \quad \text{zatem} \quad 200 \equiv 0 \pmod{10}. ``` Stąd: ```{math} 7^{200} = 7^{20 \cdot 10} = (7^{10})^{20} \equiv 1^{20} = 1 \pmod{11}. ``` **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. ::: ## Funkcja Eulera :::{prf:definition} {index}`funkcja Eulera` **Funkcja Eulera** $\varphi:\nn\to\nn$ zlicza, ile liczb ze zbioru $\{1, \dots, n\}$ nie dzieli z $n$ żadnego wspólnego czynnika poza jedynką: $$ \varphi(n) = \big| \{ k \in \{1, \dots, n\} : \NWD(k, n) = 1 \} \big|. $$ ::: ::::{prf:remark} Funkcja Eulera ma duże znaczenie zarówno teoretyczne, jak i praktyczne. 1. **Arytmetyka modularna:** Liczba elementów odwracalnych w $\zz_n$ wynosi dokładnie $\varphi(n)$. 2. **Optymalizacja algorytmów:** Umożliwia szybkie potęgowanie modularne dzięki twierdzeniu Eulera (patrz {prf:ref}`lec-07-thm-euler`). 3. **Kryptografia:** Bezpieczeństwo kluczy w szyfrowaniu RSA opiera się na trudności obliczenia $\varphi(n)$ bez znajomości rozkładu $n$ na czynniki pierwsze. :::: :::{prf:example} 1. **Dla liczby pierwszej $p$:** Wszystkie liczby mniejsze są względnie pierwsze, więc $\varphi(p) = p - 1$. 2. **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)$. 3. 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$. ::: :::{prf:theorem} 1. **Multiplikatywność:** Jeśli $\NWD(m, n) = 1$, to $\varphi(mn) = \varphi(m)\varphi(n)$. 2. **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). $$ 3. **Tożsamość Gaussa:** Suma wartości $\varphi$ po wszystkich dzielnikach daje liczbę $n$: $$ \sum_{d \mid n} \varphi(d) = n. $$ ::: :::{prf:example} 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: $$ \varphi(360) = 360 \cdot \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right) = 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96. $$ To jednocześnie oznacza, że istnieje dokładnie $96$ liczb z zakresu $1\dots 360$, które są odwracalne w modulo $360$. ::: :::{prf:theorem} Twierdzenie Eulera :label: lec-07-thm-euler Jeśli $\NWD(a,n)=1$, to ```{math} a^{\varphi(n)}\equiv 1 \pmod n. ``` ::: :::{prf:remark} 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}$. ::: ::::{exercise} :class: [exercise] Obliczmy $\varphi(100)$, a następnie resztę z dzielenia $7^{200}$ przez $100 .$ :::: :::{solution-without-reference} :class: [solution] dropdown Ponieważ $100=2^2\cdot 5^2$, to ```{math} \varphi(100)=100\left(1-\tfrac 1 2\right)\left(1-\tfrac 1 5\right)=100\cdot\tfrac 1 2\cdot\tfrac 4 5=40. ``` Ponieważ $\NWD(7,100)=1$, z twierdzenia Eulera $7^{40}\equiv 1\pmod{100} .$ Ponieważ $200=40\cdot 5$, to ```{math} 7^{200}=(7^{40})^5\equiv 1 \pmod{100}. ``` ::: ## Rozmieszczenie liczb pierwszych :::{prf:theorem} 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. ::: :::{prf:definition} Dla $x\in\rr$ funkcję ```{math} \pi(x)=\Absolute{\Set{p\in\mathbb P : p\leq x}} ``` nazywamy {index}`funkcja licząca liczby pierwsze` **funkcją liczącą liczby pierwsze**. ::: :::{prf:theorem} Czebyszew ```{math} \lim_{x\to\infty}\frac{\pi(x)\ln x}{x}=1, \qquad \text{czyli}\qquad \pi(x)\approx\frac{x}{\ln x}. ``` ::: :::{prf:example} Dla $n=10^6$: $\pi(10^6)=78498$, natomiast $\dfrac{10^6}{\ln 10^6}\approx 72382 .$ ::: :::{prf:theorem} Postulat Bertranda Dla każdej liczby $n\in\nn$ istnieje liczba pierwsza $p$ taka, że $n