Różnica pomiędzy stronami "Twierdzenie Czebyszewa o funkcji π(n)" i "Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera"
Linia 1: | Linia 1: | ||
− | <div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;"> | + | <div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">22.12.2023</div> |
__FORCETOC__ | __FORCETOC__ | ||
Linia 5: | Linia 5: | ||
− | == | + | == Największy wspólny dzielnik == |
− | + | <span id="H1" style="font-size: 110%; font-weight: bold;">Definicja H1</span><br/> | |
+ | Niech będą dane dwie liczby całkowite <math>a</math> i <math>b</math> niebędące jednocześnie zerami. Największym wspólnym dzielnikiem<ref name="GCD1"/> liczb <math>a</math> i <math>b</math> będziemy nazywali liczbę całkowitą <math>D</math> taką, że | ||
− | : | + | :# <math> D \mid a \quad \text{i} \quad D \mid b</math> |
− | + | :# <math>\,\, d \mid a \quad \text{i} \quad \; d \mid b \qquad \Longrightarrow \qquad d \leqslant D</math> | |
− | |||
− | : | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | gdzie <math>d</math> jest dowolną liczbą całkowitą. | ||
− | |||
− | + | <span id="H2" style="font-size: 110%; font-weight: bold;">Uwaga H2</span><br/> | |
− | + | Tak zdefiniowaną liczbę <math>D</math> będziemy oznaczali przez <math>\gcd (a, b)</math>. Ponieważ <math>1 \mid a \;</math> i <math>\; 1 \mid b</math>, to z definicji wynika natychmiast, że <math>\gcd (a, b) \geqslant 1</math>. | |
− | |||
− | |||
− | |||
− | |||
− | + | <span id="H3" style="font-size: 110%; font-weight: bold;">Zadanie H3</span><br/> | |
+ | Pokazać, że | ||
− | ::<math> | + | ::<math>d \mid \gcd (a, b) \qquad \Longleftrightarrow \qquad d \mid a \quad \text{i} \quad d \mid b</math> |
− | |||
− | |||
− | |||
− | |||
− | |||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
+ | <math>\Large{\Longrightarrow}</math> | ||
+ | Z założenia <math>d \mid \gcd (a, b)</math>. Z definicji największego wspólnego dzielnika <math>\gcd (a, b) \mid a</math>, zatem <math>d \mid a</math>. Analogicznie pokazujemy, że <math>d \mid b</math>. | ||
+ | <math>\Large{\Longleftarrow}</math> | ||
− | == | + | Z założenia <math>a = r d</math>, <math>b = s d</math>. Z lematu Bézouta (zobacz C73) istnieją takie liczby całkowite <math>x, y</math>, że |
− | + | ::<math>\gcd (a, b) = a x + b y = r d x + s d y = d (r x + s y)</math> | |
− | + | Zatem <math>d \mid \gcd (a, b)</math>.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
+ | <span id="H4" style="font-size: 110%; font-weight: bold;">Twierdzenie H4</span><br/> | ||
+ | Jeżeli liczby całkowite <math>a, b</math> nie są jednocześnie równe zero i <math>\gcd (a, b) = a x + b y</math>, to <math>\gcd (x, y) = 1</math>. | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | |
+ | Z lematu Bézouta (zobacz C73) wiemy, że liczby całkowite <math>x, y</math> zawsze istnieją. Niech <math>\gcd (a, b) = d > 0</math>, zatem <math>a = d k</math> i <math>b = d m</math>, czyli | ||
− | + | ::<math>(d k) x + (d m) y = d</math> | |
+ | Co oznacza, że <math>k x + m y = 1</math>, ale <math>\gcd (x, y)</math> jest dzielnikiem <math>k x + m y</math> (bo jest dzielnikiem <math>x</math> i <math>y</math>), zatem <math>\gcd (x, y) \mid 1</math>, czyli <math>\gcd (x, y) = 1</math>. Co należało pokazać.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | ::< | + | <span id="H5" style="font-size: 110%; font-weight: bold;">Twierdzenie H5</span><br/> |
+ | Niech <math>a, b, k \in \mathbb{Z}</math>. Prawdziwy jest wzór | ||
+ | ::<math>\gcd (a + k b, b) = \gcd (a, b)</math> | ||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
+ | Niech <math>d_1 = \gcd (a + k b, b) \;</math> i <math>\; d_2 = \gcd (a, b)</math>. | ||
− | + | Z definicji <math>d_1 \mid (a + k b) \;</math> i <math>\; d_1 \mid b</math>, zatem <math>a + k b = x d_1 \;</math> i <math>\; b = y d_1</math>, czyli <math>a + k x d_1 = x d_1</math>, skąd natychmiast wynika, że <math>d_1 \mid a</math>. Ponieważ <math>d_1 \mid b</math>, to <math>d_1 \mid d_2</math> (zobacz [[#H3|H3]]). | |
+ | Z definicji <math>d_2 \mid a \;</math> i <math>\; d_2 \mid b</math>, zatem <math>d_2 \mid (a + k b) \;</math> i <math>\; d_2 \mid b</math>, czyli <math>d_2 \mid d_1</math>. | ||
+ | Ponieważ <math>d_1 \mid d_2 \;</math> i <math>\; d_2 \mid d_1</math>, to <math>| d_1 | = | d_2 |</math>. Co kończy dowód.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="H6" style="font-size: 110%; font-weight: bold;">Twierdzenie H6</span><br/> |
− | + | Niech <math>a, b, m \in \mathbb{Z}</math>. Prawdziwa jest następująca równoważność | |
+ | ::<math>\gcd (a, m) = 1 \quad \text{i} \quad \gcd (b, m) = 1 \quad \qquad \Longleftrightarrow \quad \qquad \gcd (a b, m) = 1</math> | ||
− | :: | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} |
+ | <math>\Large{\Longrightarrow}</math> | ||
− | + | Niech <math>\gcd (a b, m) = d</math>. Z definicji <math>d \mid a b</math> i <math>d \mid m</math>. Gdyby było <math>d > 1</math>, to istniałaby liczba pierwsza <math>p</math> taka, że <math>p \mid d</math> i mielibyśmy <math>p \mid a b</math> i <math>p \mid m</math>. Jeżeli <math>p \mid a b</math>, to <math>p \mid a</math> lub <math>p \mid b</math> (zobacz C74). W przypadku, gdy <math>p \mid a</math> dostajemy <math>\gcd (a, m) \geqslant p > 1</math>, wbrew założeniu, że <math>\gcd (a, m) = 1</math>. Analogicznie pokazujemy sprzeczność, gdy <math>p \mid b</math>. | |
+ | <math>\Large{\Longleftarrow}</math> | ||
− | + | Niech <math>\gcd (a, m) = d</math>. Z definicji <math>d \mid a</math> i <math>d \mid m</math>, zatem również <math>d \mid a b</math> i <math>d \mid m</math>. Mamy stąd | |
+ | ::<math>1 = \gcd (a b, m) \geqslant d \geqslant 1</math> | ||
+ | Czyli musi być <math>d = 1</math>. Analogicznie pokazujemy, że <math>\gcd (b, m) = 1</math>.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
− | == | + | <span id="H7" style="font-size: 110%; font-weight: bold;">Twierdzenie H7</span><br/> |
+ | Dla <math>a, b, m \in \mathbb{Z}</math> jest | ||
− | + | ::<math>\gcd (a b, m) \mid \gcd (a, m) \cdot \gcd (b, m)</math> | |
− | |||
− | |||
− | |||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | + | Wprowadźmy oznaczenia | |
− | |||
− | |||
− | |||
− | |||
− | ::<math> | + | ::<math>r = \gcd (a b, m)</math> |
− | + | ::<math>s = \gcd (a, m)</math> | |
− | ::<math> | + | ::<math>t = \gcd (b, m)</math> |
− | + | Z lematu Bézouta (zobacz C73) istnieją takie liczby <math>x, y, X, Y</math>, że | |
− | |||
− | |||
+ | ::<math>s = a x + m y</math> | ||
+ | ::<math>t = b X + m Y</math> | ||
− | + | Zatem | |
− | |||
− | + | ::<math>s t = (a x + m y) (b X + m Y) = a b x X + a m x Y + m b y X + m^2 y Y</math> | |
− | |||
− | + | ale <math>r \mid a b</math> i <math>r \mid m</math>, skąd otrzymujemy, że <math>r \mid s t</math>. Co należało pokazać.<br/> | |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 135: | Linia 130: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="H8" style="font-size: 110%; font-weight: bold;">Twierdzenie H8</span><br/> |
− | + | Jeżeli liczby <math>a, b</math> są względnie pierwsze, to | |
− | ::<math> | + | ::<math>\gcd (a b, m) = \gcd (a, m) \cdot \gcd (b, m)</math> |
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | + | Wprowadźmy oznaczenia | |
− | ::<math> | + | ::<math>r = \gcd (a b, m)</math> |
+ | ::<math>s = \gcd (a, m)</math> | ||
− | + | ::<math>t = \gcd (b, m)</math> | |
− | + | Z założenia <math>\gcd (a, b) = 1</math>. Ponieważ <math>s \mid a</math> oraz <math>t \mid b</math>, to <math>\gcd (s, t) = 1</math>, zatem (zobacz C75) | |
− | |||
− | |||
+ | ::<math>s \mid a \qquad \,\, \text{i} \qquad t \mid b \qquad \qquad \;\, \Longrightarrow \qquad \qquad s t \mid a b</math> | ||
+ | ::<math>s \mid m \qquad \text{i} \qquad t \mid m \qquad \qquad \Longrightarrow \qquad \qquad s t \mid m</math> | ||
− | + | Wynika stąd, że <math>s t \mid \gcd (a b, m)</math>, czyli <math>s t \mid r</math>. Z poprzedniego twierdzenia wiemy, że <math>r \mid s t</math>, zatem <math>|r| = |s t|</math>. Co kończy dowód.<br/> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 169: | Linia 156: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="H9" style="font-size: 110%; font-weight: bold;">Twierdzenie H9</span><br/> |
− | + | Jeżeli liczby <math>b, m</math> są względnie pierwsze, to | |
+ | |||
+ | ::<math>\gcd (a b, m) = \gcd (a, m)</math> | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | + | Wprowadźmy oznaczenia | |
− | ::<math>\ | + | ::<math>r = \gcd (a b, m)</math> |
− | + | ::<math>s = \gcd (a, m)</math> | |
+ | Z lematu Bézouta istnieją takie liczby <math>x, y</math>, że | ||
+ | ::<math>r = a b x + m y</math> | ||
− | + | Ale <math>s \mid a \;</math> i <math>\; s \mid m</math>, zatem <math>s \mid r</math>. | |
− | + | Z założenia <math>\gcd (b, m) = 1</math>, zatem z twierdzenia [[#H7|H7]] wynika natychmiast, że <math>r \mid s</math>. Ponieważ <math>s \mid r \;</math> i <math>\; r \mid s</math>, to <math>| r | = | s |</math>. Co należało pokazać.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | ::<math>\ | + | <span id="H10" style="font-size: 110%; font-weight: bold;">Twierdzenie H10</span><br/> |
+ | Jeżeli liczby <math>a, b</math> nie są jednocześnie równe zero i <math>m \neq 0</math>, to | ||
− | ::<math>\ | + | ::<math>\gcd (a m, b m) = | m | \cdot \gcd (a, b)</math> |
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
+ | Oznaczmy <math>d = \gcd (a, b) \;</math> i <math>\; D = \gcd (a m, b m)</math>. Pokażemy, że <math>d m \mid D</math>. | ||
− | + | <div style="margin-top: 1.5em; margin-bottom: 1em;"> | |
+ | ::<math> | ||
+ | \begin{array}{llll} | ||
+ | d = \gcd (a, b) & \qquad \Longrightarrow \qquad & d \mid a \quad \text{i} \quad d \mid b & \text{(zobacz H3)} \\ | ||
+ | & & & \\ | ||
+ | & \qquad \Longrightarrow \qquad & d m \mid a m \quad \text{i} \quad d m \mid b m & \\ | ||
+ | & & & \\ | ||
+ | & \qquad \Longrightarrow \qquad & d m \mid \gcd (a m, b m) & \text{(zobacz H3)} \\ | ||
+ | & & & \\ | ||
+ | & \qquad \Longrightarrow \qquad & d m \mid D & \\ | ||
+ | \end{array} | ||
+ | </math> | ||
+ | </div> | ||
− | + | Pokażemy, że <math>D \mid d m</math>. | |
− | ::<math>\qquad \ | + | <div style="margin-top: 1.5em; margin-bottom: 1em;"> |
+ | ::<math> | ||
+ | \begin{array}{llll} | ||
+ | d = \gcd (a, b) & \qquad \Longrightarrow \qquad & d = a x + b y & \text{(lemat Bézouta C73)} \\ | ||
+ | & & & \\ | ||
+ | & \qquad \Longrightarrow \qquad & d m = a m x + b m y & \\ | ||
+ | & & & \\ | ||
+ | & \qquad \Longrightarrow \qquad & D \mid d m & \\ | ||
+ | \end{array} | ||
+ | </math> | ||
+ | </div> | ||
− | + | Ostatnia implikacja korzysta z tego, że <math>D \mid a m \;</math> i <math>\; D \mid b m</math> (zobacz [[#H3|H3]]). Ponieważ <math>d m \mid D \;</math> i <math>\; D \mid d m</math>, to <math>| D | = | d m |</math>. Co należało pokazać.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | + | <span id="H11" style="font-size: 110%; font-weight: bold;">Zadanie H11</span><br/> | |
+ | Pokazać, że <math>a \mid b</math> wtedy i tylko wtedy, gdy <math>a \mid \gcd (a, b)</math>. | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | |
− | + | <math>\Large{\Longrightarrow}</math> | |
+ | Zakładając, że <math>a \mid b</math>, dostajemy | ||
− | + | <div style="margin-top: 1.5em; margin-bottom: 1em;"> | |
+ | ::<math> | ||
+ | \begin{array}{llll} | ||
+ | a \mid b & \qquad \Longrightarrow \qquad & b = k a & \\ | ||
+ | & & & \\ | ||
+ | & \qquad \Longrightarrow \qquad & \gcd (a, b) = \gcd (a, k a) = | a | \cdot \gcd (1, k) = | a | & \qquad \text{(zobacz H10)} \\ | ||
+ | & & & \\ | ||
+ | & \qquad \Longrightarrow \qquad & a \mid \gcd (a, b) & \\ | ||
+ | \end{array} | ||
+ | </math> | ||
+ | </div> | ||
− | + | <math>\Large{\Longleftarrow}</math> | |
− | + | Jeżeli <math>a \mid \gcd (a, b)</math>, to <math>a \mid b</math> (zobacz [[#H3|H3]]). Co należało pokazać.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | ::<math>\ | + | <span id="H12" style="font-size: 110%; font-weight: bold;">Zadanie H12</span><br/> |
+ | Niech <math>\gcd (a, d) = 1</math>. Pokazać, że <math>d \nmid a b</math> wtedy i tylko wtedy, gdy <math>d \nmid b</math>. | ||
− | :: | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} |
+ | Korzystając z rezultatu pokazanego w zadaniu [[#H11|H11]], dostajemy | ||
+ | <div style="margin-top: 1.5em; margin-bottom: 1em;"> | ||
+ | ::<math> | ||
+ | \begin{array}{llll} | ||
+ | d \nmid a b & \qquad \Longleftrightarrow \qquad & d \nmid \gcd (d, a b) & \\ | ||
+ | & & & \\ | ||
+ | & \qquad \Longleftrightarrow \qquad & d \nmid \gcd (d, b) & \text{(zobacz H9)} \\ | ||
+ | & & & \\ | ||
+ | & \qquad \Longleftrightarrow \qquad & d \nmid b & \\ | ||
+ | \end{array} | ||
+ | </math> | ||
+ | </div> | ||
− | + | Co należało pokazać.<br/> | |
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 236: | Linia 275: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="H13" style="font-size: 110%; font-weight: bold;">Twierdzenie H13</span><br/> |
− | + | Jeżeli dodatnie liczby <math>a, b</math> są względnie pierwsze, to każdy dzielnik <math>d</math> iloczynu <math>a b</math> można przedstawić jednoznacznie w postaci <math>d = d_1 d_2</math>, gdzie <math>d_1 \mid a ,</math> <math>\; d_2 \mid b \;</math> <math>\text{i} \; \gcd (d_1, d_2) = 1</math>. | |
− | |||
− | |||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | + | Niech <math>d_1 = \gcd (d, a) \;</math> i <math>\; d_2 = \gcd (d, b)</math>. Z twierdzenia [[#H8|H8]] mamy | |
− | |||
− | |||
− | |||
− | |||
− | &# | ||
− | |||
+ | ::<math>d_1 d_2 = \gcd (d, a) \cdot \gcd (d, b) = \gcd (d, a b) = d</math> | ||
+ | Bo z założenia <math>d \mid a b</math>. Z definicji największego wspólnego dzielnika i zadania [[#H3|H3]] dostajemy | ||
− | + | ::<math>\gcd (d_1, d_2) = e \qquad \Longrightarrow \qquad e \mid d_1 \quad \text{i} \quad e \mid d_2</math> | |
− | |||
− | + | ::::::::<math>\, \Longrightarrow \qquad e \mid \gcd (d, a) \quad \text{i} \quad e \mid \gcd (d, b)</math> | |
− | |||
− | ::<math>\ | + | ::::::::<math>\, \Longrightarrow \qquad e \mid a \quad \text{i} \quad e \mid b</math> |
− | + | ::::::::<math>\, \Longrightarrow \qquad e \mid \gcd (a, b)</math> | |
− | ::<math>\ | + | ::::::::<math>\, \Longrightarrow \qquad \gcd (a, b) \geqslant e</math> |
− | + | Gdyby było <math>\gcd (d_1, d_2) = e > 1</math>, to mielibyśmy <math>\gcd (a, b) \geqslant e > 1</math>. Wbrew założeniu, że <math>\gcd (a, b) = 1</math>. Co kończy dowód.<br/> | |
− | |||
− | |||
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 274: | Linia 301: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="H14" style="font-size: 110%; font-weight: bold;">Twierdzenie H14</span><br/> |
− | + | Jeżeli <math>a, m, n \in \mathbb{Z}_+</math>, to | |
+ | |||
+ | ::<math>\gcd (a^m - 1, a^n - 1) = a^{\gcd (m, n)} - 1</math> | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | + | Pokażemy najpierw, że jeżeli <math>d</math> jest dzielnikiem lewej strony dowodzonej równości, to jest również dzielnikiem prawej strony i odwrotnie. | |
− | + | <math>\Large{\Longrightarrow}</math> | |
− | + | Z założenia <math>d</math> jest dzielnikiem <math>\gcd (a^m - 1, a^n - 1)</math>, czyli <math>d \mid (a^m - 1) \;</math> i <math>\; d \mid (a^n - 1)</math>, co możemy zapisać w postaci | |
− | + | ::<math>a^m \equiv 1 \!\! \pmod{d} \quad \qquad \text{oraz} \quad \qquad a^n \equiv 1 \!\! \pmod{d}</math> | |
− | + | Z lematu Bézouta (zobacz C73) wiemy, że istnieją takie liczby <math>x, y</math>, że <math>\gcd (m, n) = m x + n y</math>. Łatwo znajdujemy, że | |
− | + | ::<math>a^{\gcd (m, n)} \equiv a^{m x + n y} \equiv (a^m)^x \cdot (a^n)^y \equiv 1^x \cdot 1^y \equiv 1 \!\! \pmod{d}</math> | |
− | |||
− | {{\ | ||
+ | Czyli <math>d \, \biggr\rvert \left( a^{\gcd (m, n)} - 1 \right)</math>. | ||
+ | <math>\Large{\Longleftarrow}</math> | ||
− | + | Z założenia <math>d \, \biggr\rvert \left( a^{\gcd (m, n)} - 1 \right)</math>, czyli | |
− | |||
− | + | ::<math>a^{\gcd (m, n)} \equiv 1 \!\! \pmod{d}</math> | |
− | |||
− | + | Zatem | |
− | + | ::<math>a^m \equiv \left[ a^{\gcd (m, n)} \right]^{\tfrac{m}{\gcd (m, n)}} \equiv 1 \!\! \pmod{d}</math> | |
− | + | Podobnie otrzymujemy | |
− | + | ::<math>a^n \equiv 1 \!\! \pmod{d}</math> | |
− | + | Zatem <math>d</math> dzieli <math>a^m - 1 \;</math> i <math>\; a^n - 1</math>, czyli | |
− | + | ::<math>d \mid \gcd (a^m - 1, a^n - 1)</math> | |
− | |||
− | |||
+ | W szczególności wynika stąd, że | ||
− | + | :* <math>\gcd (a^m - 1, a^n - 1) \, \biggr\rvert \left( a^{\gcd (m, n)} - 1 \right)</math> | |
− | |||
− | + | :* <math>\left( a^{\gcd (m, n)} - 1 \right) \, \biggr\rvert \, \gcd (a^m - 1, a^n - 1)</math> | |
− | |||
− | + | Czyli <math>\left| \gcd (a^m - 1, a^n - 1) \right| = \left| a^{\gcd (m, n)} - 1 \right|</math>. Co kończy dowód.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | + | <span id="H15" style="font-size: 110%; font-weight: bold;">Uwaga H15</span><br/> | |
+ | W dowodzie twierdzenia [[#H14|H14]] pominęliśmy milczeniem fakt, że jedna z liczb <math>x, y</math> może być (i często jest) ujemna. Choć rezultat jest prawidłowy, to nie wiemy, co oznacza zapis | ||
− | ::<math> | + | ::<math>a^{- 1000} \equiv 1^{- 10} \equiv 1 \!\! \pmod{d}</math> |
− | + | Omówimy ten problem w następnej sekcji. Zauważmy, wyprzedzając materiał, że z kongruencji | |
− | ::<math>\ | + | ::<math>a^m \equiv 1 \!\! \pmod{d} \quad \qquad \text{oraz} \quad \qquad a^n \equiv 1 \!\! \pmod{d}</math> |
− | |||
− | |||
+ | wynika, że <math>\gcd (a, d) = 1</math> i liczba <math>a</math> ma element odwrotny modulo <math>d</math>. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | == Element odwrotny modulo <math>m</math> == | |
− | a | + | <span id="H16" style="font-size: 110%; font-weight: bold;">Twierdzenie H16</span><br/> |
+ | Niech <math>m \in \mathbb{Z}_+</math>. Dla liczby <math>a \in \mathbb{Z}</math> istnieje taka liczba <math>x</math>, że | ||
− | ::<math>\ | + | ::<math>a x \equiv 1 \!\! \pmod{m}</math> |
− | + | wtedy i tylko wtedy, gdy <math>\gcd (a, m) = 1</math>. | |
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | |
− | + | <math>\Large{\Longrightarrow}</math> | |
− | + | Z założenia istnieje taka liczba <math>x</math>, że | |
− | + | ::<math>a x \equiv 1 \!\! \pmod{m}</math> | |
− | + | Zatem dla pewnego <math>k \in \mathbb{Z}</math> jest | |
− | + | ::<math>a x = 1 + k m</math> | |
− | + | Czyli <math>a x - k m = 1</math>. Wynika stąd, że <math>\gcd (a, m)</math> dzieli <math>1</math>, co oznacza, że <math>\gcd (a, m) = 1</math>. | |
− | + | <math>\Large{\Longleftarrow}</math> | |
− | + | Z założenia <math>\gcd (a, m) = 1</math>. Z lematu Bézouta (zobacz C73) wynika, że istnieją takie liczby całkowite <math>x, y</math>, że | |
− | + | ::<math>a x + m y = 1</math> | |
− | + | Zatem modulo <math>m</math> dostajemy | |
− | + | ::<math>a x \equiv 1 \!\! \pmod{m}</math> | |
− | + | Co kończy dowód.<br/> | |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 386: | Linia 406: | ||
+ | <span id="H17" style="font-size: 110%; font-weight: bold;">Definicja H17</span><br/> | ||
+ | Niech <math>m \in \mathbb{Z}_+</math>. Liczbę <math>x</math> taką, że | ||
+ | ::<math>a \cdot x \equiv 1 \!\! \pmod{m}</math> | ||
− | + | będziemy nazywali elementem odwrotnym liczby <math>a</math> modulo <math>m</math> i oznaczali jako <math>a^{- 1}</math>. | |
− | |||
− | <span style="font-size: 110%; font-weight: bold;"> | + | <span id="H18" style="font-size: 110%; font-weight: bold;">Uwaga H18</span><br/> |
− | + | Oznaczenie elementu odwrotnego ma naturalne uzasadnienie. Zauważmy, że jeżeli <math>b \mid a</math> oraz <math>b</math> ma element odwrotny modulo <math>m</math>, to prawdziwa jest kongruencja | |
+ | ::<math>{\small\frac{a}{b}} \equiv a b^{- 1} \!\! \pmod{m}</math> | ||
+ | Istotnie | ||
− | + | ::<math>{\small\frac{a}{b}} = {\small\frac{a}{b}} \cdot 1 \equiv {\small\frac{a}{b}} \cdot b b^{- 1} \equiv a b^{- 1} \!\! \pmod{m}</math> | |
− | |||
− | + | W PARI/GP odwrotność liczby <math>a</math> modulo <math>m</math> znajdujemy, wpisując <code>Mod(a, m)^(-1)</code>. | |
− | |||
− | |||
− | |||
− | + | <span id="H19" style="font-size: 110%; font-weight: bold;">Twierdzenie H19</span><br/> | |
− | + | Niech <math>a, k \in \mathbb{Z}</math>, <math>m \in \mathbb{Z}_+</math>. Poniższa tabelka przedstawia elementy odwrotne do elementu <math>a</math> w przypadku niektórych modułów <math>m</math>. W szczególności, jeżeli moduł <math>m</math> jest liczbą nieparzystą, to <math>2^{- 1} \equiv {\small\frac{m + 1}{2}} \!\! \pmod{m}</math>. | |
− | < | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | < | ||
− | |||
− | |||
− | |||
− | |||
+ | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: center; margin-right: auto;" | ||
+ | |- | ||
+ | ! || postać <br/> modułu <math>\boldsymbol{m}</math> || odwrotność <br/> elementu <math>\boldsymbol{a}</math> || uwagi | ||
+ | |- | ||
+ | | <math>1.</math> || <math>m = 2</math> || <math>1</math> || rowspan = 3 | liczba <math>a</math> <br/> jest liczbą <br/> nieparzystą | ||
+ | |- | ||
+ | | <math>2.</math> || <math>m = 4</math> || <math>R_4(a)</math> | ||
+ | |- | ||
+ | | <math>3.</math> || <math>m = 8</math> || <math>R_8(a)</math> | ||
+ | |- | ||
+ | | <math>4.</math> || <math>m = a k - 1</math> || <math>{\small\frac{m + 1}{a}}</math> || <math></math> | ||
+ | |- | ||
+ | | <math>5.</math> || <math>m = a k + 1</math> || <math>- {\small\frac{m - 1}{a}}</math> || <math></math> | ||
+ | |- | ||
+ | | <math>6.</math> || <math>m = a k - 2</math> || <math>{\small\frac{m + 1}{2}} \cdot {\small\frac{m + 2}{a}}</math> || rowspan = 2 | liczby <math>a , m</math> <br/> są liczbami <br/> nieparzystymi | ||
+ | |- | ||
+ | | <math>7.</math> || <math>m = a k + 2</math> || <math>{\small\frac{m - 1}{2}} \cdot {\small\frac{m - 2}{2}}</math> | ||
+ | |} | ||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | + | '''Punkty 1. - 3.''' | |
− | |||
− | + | Ponieważ dla liczb nieparzystych jest | |
− | |||
− | ::<math> | + | ::<math>a^2 \equiv 1 \!\! \pmod{2}</math> |
− | + | ::<math>a^2 \equiv 1 \!\! \pmod{4}</math> | |
− | |||
− | |||
+ | ::<math>a^2 \equiv 1 \!\! \pmod{8}</math> | ||
+ | to liczba nieparzysta <math>a</math> jest swoją odwrotnością modulo <math>2</math>, <math>4</math> i <math>8</math>. Ponieważ element odwrotny jest definiowany modulo, zatem możemy napisać | ||
− | + | ::<math>a^{- 1} \equiv R_2 (a) \!\! \pmod{2}</math> | |
+ | ::<math>a^{- 1} \equiv R_4 (a) \!\! \pmod{4}</math> | ||
− | + | ::<math>a^{- 1} \equiv R_8 (a) \!\! \pmod{8}</math> | |
− | |||
− | + | W pierwszym przypadku wynik jest oczywisty, bo <math>R_2 (a) = 1</math>. | |
+ | '''Punkt 4.''' | ||
+ | Zauważmy, że | ||
− | + | ::<math>\gcd (a, m) = \gcd (a, a k - 1) = \gcd (a, - 1) = 1</math> | |
− | <math> | ||
+ | oraz <math>a \mid (m + 1)</math>. Zatem | ||
+ | ::<math>a \cdot a^{- 1} = a \cdot {\small\frac{m + 1}{a}} = m + 1 \equiv 1 \!\! \pmod{m}</math> | ||
− | + | '''Punkt 5.''' | |
+ | Zauważmy, że | ||
− | + | ::<math>\gcd (a, m) = \gcd (a, a k + 1) = \gcd (a, 1) = 1</math> | |
− | + | oraz <math>a \mid (m - 1)</math>. Zatem | |
− | :: | + | ::<math>a \cdot a^{- 1} = a \cdot \left[ - \left( {\small\frac{m - 1}{a}} \right) \right] = - m + 1 \equiv 1 \!\! \pmod{m}</math> |
− | |||
− | |||
− | |||
+ | '''Punkt 6.''' | ||
+ | Ponieważ zakładamy, że <math>2 \mid (m + 1)</math>, to <math>m</math> musi być liczbą nieparzystą, czyli <math>a</math> też musi być liczbą nieparzystą. Zauważmy, że | ||
− | + | ::<math>\gcd (a, m) = \gcd (a, a k - 2) = \gcd (a, - 2) = 1</math> | |
− | |||
− | + | oraz <math>a \mid (m + 2)</math>. Zatem | |
− | |||
− | ::<math>1 \cdot | + | ::<math>a \cdot a^{- 1} = a \cdot \left( {\small\frac{m + 1}{2}} \cdot {\small\frac{m + 2}{a}} \right) = {\small\frac{m + 1}{2}} \cdot (m + 2) \equiv {\small\frac{m + 1}{2}} \cdot 2 \equiv m + 1 \equiv 1 \!\! \pmod{m}</math> |
− | + | Podobnie pokazujemy punkt 7. Co kończy dowód.<br/> | |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 481: | Linia 508: | ||
− | <span style="font-size: 110%; font-weight: bold;"> | + | <span id="H20" style="font-size: 110%; font-weight: bold;">Twierdzenie H20</span><br/> |
− | + | Niech <math>a, b \in \mathbb{Z}</math>, <math>m \in \mathbb{Z}_+</math> i liczba <math>a</math> ma element odwrotny modulo <math>m</math>. Jeżeli liczby <math>u_1, u_2, \ldots, u_r</math> są liczbami różnymi modulo <math>m</math>, to liczby | |
+ | |||
+ | ::1. <math>a u_1, a u_2, \ldots, a u_r</math> | ||
+ | ::2. <math>a u_1 + b, a u_2 + b, \ldots, a u_r + b</math> | ||
+ | są liczbami różnymi modulo <math>m</math>. Jeżeli ponadto liczby <math>u_1, u_2, \ldots, u_r</math> są względnie pierwsze z <math>m</math>, to również liczby | ||
− | + | ::3. <math>u^{- 1}_1, u^{- 1}_2, \ldots, u^{- 1}_r</math> | |
− | + | są liczbami różnymi modulo <math>m</math>. | |
− | |||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | |||
− | + | '''Punkt 1.''' | |
− | + | Przypuśćmy dla uzyskania sprzeczności, że istnieją takie różne wskaźniki <math>i, j</math>, że | |
− | ::<math> | + | ::<math>a u_i \equiv a u_j \!\! \pmod{m}</math> |
− | + | Z założenia liczba <math>a</math> ma element odwrotny modulo <math>m</math>, zatem mnożąc obie strony kongruencji przez <math>a^{- 1}</math>, otrzymujemy | |
− | ::<math> | + | ::<math>u_i \equiv u_j \!\! \pmod{m}</math> |
− | + | dla <math>i \neq j</math>, wbrew założeniu, że liczby <math>u_1, u_2, \ldots, u_r</math> są różne modulo <math>m</math>. Dowód punktu 2. jest analogiczny. | |
− | + | '''Punkt 3.''' | |
− | + | Przypuśćmy dla uzyskania sprzeczności, że istnieją takie różne wskaźniki <math>i, j</math>, że | |
− | ::<math> | + | ::<math>u^{- 1}_i \equiv u^{- 1}_j \!\! \pmod{m}</math> |
− | + | ::<math>u_j u^{- 1}_i \equiv 1 \!\! \pmod{m}</math> | |
− | + | ::<math>u_j u^{- 1}_i u_i \equiv u_i \!\! \pmod{m}</math> | |
− | + | ::<math>u_j \equiv u_i \!\! \pmod{m}</math> | |
− | + | Ponownie otrzymujemy <math>u_i \equiv u_j \!\! \pmod{m}</math> dla <math>i \neq j</math>, wbrew założeniu, że liczby <math>u_1, u_2, \ldots, u_r</math> są różne modulo <math>m</math>. Co należało pokazać.<br/> | |
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 526: | Linia 553: | ||
− | <span style="font-size: 110%; font-weight: bold;"> | + | <span id="H21" style="font-size: 110%; font-weight: bold;">Zadanie H21</span><br/> |
− | + | Niech <math>p</math> będzie liczbą pierwszą. Pokazać, że dla <math>k \in [0, p - 1]</math> prawdziwa jest kongruencja | |
− | ::<math> | + | ::<math>\binom{p - 1}{k} \equiv (- 1)^k \pmod{p}</math> |
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | |
+ | Zauważmy, że modulo <math>p</math> mamy | ||
− | ::<math>\frac{ | + | ::<math>\binom{p - 1}{k} = {\small\frac{(p - 1) !}{k! \cdot (p - 1 - k) !}}</math> |
− | + | ::::<math>\;\;\;\; = {\small\frac{(p - 1) (p - 2) \cdot \ldots \cdot (p - k)}{k!}}</math> | |
+ | ::::<math>\;\;\;\; \equiv (p - 1) (p - 2) \cdot \ldots \cdot (p - k) \cdot (k!)^{- 1}</math> | ||
+ | ::::<math>\;\;\;\; \equiv (- 1)^k \cdot k! \cdot (k!)^{- 1}</math> | ||
− | + | ::::<math>\;\;\;\; \equiv (- 1)^k \pmod{p}</math> | |
− | |||
− | + | Co należało pokazać.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | :: | + | <span id="H22" style="font-size: 110%; font-weight: bold;">Zadanie H22</span><br/> |
+ | Niech <math>A</math> i <math>B</math> będą zbiorami skończonymi. Pokazać, że jeżeli <math>A \subseteq B \;\; \text{i} \;\; | A | = | B |</math>, to <math>\; A = B</math>. | ||
− | ::::<math> | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} |
+ | <span style="border-bottom-style: double;">Pierwszy sposób</span><br/><br/> | ||
+ | Z definicji zbiory <math>A</math> i <math>B</math> są równe wtedy i tylko wtedy, gdy jednocześnie spełnione są warunki | ||
− | :: | + | :# <math>x \in A \qquad \Longrightarrow \qquad x \in B</math> |
+ | :# <math>x \in B \qquad \Longrightarrow \qquad x \in A</math> | ||
− | + | Z założenia <math>A \subseteq B</math>, zatem warunek 1. jest spełniony. Przypuśćmy, że istnieje taki element <math>x</math>, że <math>x \in B</math>, ale <math>x \notin A</math>. Jeśli tak, to | |
− | + | ::<math>| B | = | A | + 1</math> | |
− | + | Co jest sprzeczne z założeniem, że <math>| A | = | B |</math>. | |
− | + | '''Uwaga'''<br/> | |
+ | Łatwo zauważyć, że wybierając z trzech warunków <math>A \subseteq B</math>, <math>B \subseteq A</math> i <math>| A | = | B |</math> dowolne dwa, zawsze otrzymamy z nich trzeci. Oczywiście nie dotyczy to zbiorów nieskończonych. Przykładowo liczby parzyste stanowią podzbiór liczb całkowitych, liczb parzystych jest tyle samo, co liczb całkowitych<ref name="cardinality1"/>, ale zbiór liczb całkowitych nie jest podzbiorem zbioru liczb parzystych. | ||
− | |||
− | : | + | <span style="border-bottom-style: double;">Drugi sposób</span><br/><br/> |
+ | Ponieważ zbiór <math>A</math> jest z założenia podzbiorem zbioru <math>B</math>, to zbiór <math>B</math> można przedstawić w postaci sumy zbioru <math>A</math> i pewnego zbioru <math>C</math> takiego, że żaden element zbioru <math>C</math> nie jest elementem zbioru <math>A</math>. Zatem | ||
+ | ::<math>B = A \cup C \qquad \text{i} \qquad A \cap C = \varnothing</math> | ||
+ | Ponieważ zbiory <math>A</math> i <math>C</math> są rozłączne, to wiemy, że | ||
+ | ::<math>| A \cup C | = | A | + | C |</math> | ||
− | + | Czyli | |
+ | ::<math>| B | = | A \cup C | = | A | + | C |</math> | ||
− | < | + | Skąd wynika, że <math>| C | = 0</math>, zatem zbiór <math>C</math> jest zbiorem pustym i otrzymujemy natychmiast <math>B = A</math>. Co należało pokazać. |
− | |||
− | + | '''Uwaga (przypadek zbiorów skończonych)'''<br/> | |
+ | Najczęściej prawdziwe jest jedynie oszacowanie <math>| A \cup C | \leqslant | A | + | C |</math>, bo niektóre elementy mogą zostać policzone dwa razy. Elementy liczone dwukrotnie to te, które należą do iloczynu zbiorów <math>| A |</math> i <math>| C |</math>, zatem od sumy <math>| A | + | C |</math> musimy odjąć liczbę elementów iloczynu zbiorów <math>| A |</math> i <math>| C |</math>. Co daje ogólny wzór<ref name="sumazbiorow"/> | ||
− | + | ::<math>| A \cup C | = | A | + | C | - | A \cap C |</math><br/> | |
− | |||
− | |||
− | |||
− | <br/> | ||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 587: | Linia 621: | ||
− | <span style="font-size: 110%; font-weight: bold;"> | + | <span id="H23" style="font-size: 110%; font-weight: bold;">Definicja H23</span><br/> |
− | + | Niech elementy każdego ze zbiorów <math>A = \{ a_1, a_2, \ldots, a_r \}</math> oraz <math>B = \{ b_1, b_2, \ldots, b_r \}</math> będą różne modulo <math>m</math>. Powiemy, że zbiory <math>A, B</math> są równe modulo <math>m</math>, jeżeli dla każdego <math>k = 1, \ldots, r</math> istnieje takie <math>j = 1, \ldots, r</math>, że prawdziwa jest kongruencja <math>a_k \equiv b_j \!\! \pmod{m}</math>. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="H24" style="font-size: 110%; font-weight: bold;">Twierdzenie H24</span><br/> |
− | Niech <math> | + | Niech elementy każdego ze zbiorów <math>A = \{ a_1, a_2, \ldots, a_r \}</math> oraz <math>B = \{ b_1, b_2, \ldots, b_r \}</math> będą różne modulo <math>m</math>. Zbiory <math>A, B</math> są równe modulo <math>m</math> wtedy i tylko wtedy, gdy zbiory <math>A' = \{ R_m (a_1), R_m (a_2), \ldots, R_m (a_r) \}</math> i <math>B' = \{ R_m (b_1), R_m (b_2), \ldots, R_m (b_r) \}</math> są równe. |
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | |||
− | + | <math>\Large{\Longrightarrow}</math> | |
− | + | Ponieważ elementy każdego ze zbiorów <math>A, B</math> są różne modulo <math>m</math>, to elementy zbiorów <math>A'</math> i <math>B'</math> są wszystkie różne. Czyli <math>| A' | = | B' | = r</math>. Ponieważ warunek | |
− | ::<math> | + | ::<math>a_k \equiv b_j \!\! \pmod{m}</math> |
− | |||
− | |||
+ | oznacza, że reszty z dzielenia liczb <math>a_k</math> i <math>b_j</math> przez <math>m</math> są równe, to z założenia dla każdego <math>k = 1, \ldots, r</math> istnieje takie <math>j = 1, \ldots, r</math>, że | ||
+ | ::<math>R_m (a_k) = R_m (b_j)</math> | ||
+ | A to oznacza, że każdy element zbioru <math>A'</math> należy do zbioru <math>B'</math>, czyli <math>A' \subseteq B'</math>. Wynika stąd, że <math>A' = B'</math> (zobacz [[#H22|H22]]). Co należało pokazać. | ||
+ | <math>\Large{\Longleftarrow}</math> | ||
− | + | Ponieważ zbiory <math>A', B'</math> są równe, to zbiór <math>A'</math> jest podzbiorem zbioru <math>B'</math>, czyli dla każdego elementu <math>R_m (a_k) \in A'</math> istnieje taki element <math>R_m (b_j) \in B'</math>, że | |
− | + | ::<math>R_m (a_k) = R_m (b_j)</math> | |
+ | Ponieważ równość reszt oznacza równość modulo, zatem | ||
− | + | ::<math>a_k \equiv b_j \!\! \pmod{m}</math> | |
− | |||
− | + | Wynika stąd, że dla każdego <math>k = 1, \ldots, r</math> istnieje takie <math>j = 1, \ldots, r</math>, że prawdziwa jest kongruencja | |
+ | ::<math>a_k \equiv b_j \!\! \pmod{m}</math> | ||
− | + | czyli zbiory <math>A, B</math> są równe modulo <math>m</math>. Co kończy dowód.<br/> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 646: | Linia 663: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="H25" style="font-size: 110%; font-weight: bold;">Twierdzenie H25</span><br/> |
− | + | Niech będą dane zbiory <math>A = \{ 1, 2, \ldots, p - 1 \}</math>, <math>B = \{ b_1, b_2, \ldots, b_{p - 1} \}</math>, gdzie <math>p</math> jest liczbą pierwszą. Jeżeli wszystkie elementy zbioru <math>B</math> są różne modulo <math>p</math> i żadna z liczb <math>b_k \in B</math> nie jest podzielna przez <math>p</math>, to zbiory <math>A, B, C = \{ b^{- 1}_1, b^{- 1}_2, \ldots, b^{- 1}_{p - 1} \}</math> są równe modulo <math>p</math>. | |
− | |||
− | |||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | + | Z definicji zbioru <math>A</math> wszystkie elementy tego zbioru są różne modulo <math>p</math>. Łatwo zauważamy, że | |
− | ::<math>\ | + | ::<math>A = \{ 1, 2, \ldots, p - 1 \} = \{ R_p (1), R_p (2), \ldots, R_p (p - 1) \} = A'</math> |
− | + | Ponieważ wszystkie liczby <math>b_k \in B</math>, gdzie <math>k = 1, \ldots, p - 1</math> są różne modulo <math>p</math> i nie są podzielne przez <math>p</math>, to reszty <math>R_p (b_1), R_p (b_2), \ldots, R_p (b_{p - 1})</math> są wszystkie dodatnie i różne, a ponieważ jest ich <math>p - 1</math>, czyli dokładnie tyle, ile jest różnych i dodatnich reszt z dzielenia przez liczbę <math>p</math>, to zbiór tych reszt jest identyczny ze zbiorem dodatnich reszt z dzielenia przez <math>p</math>, czyli ze zbiorem <math>A</math>. Zatem mamy | |
− | ::<math>\ | + | ::<math>A = A' = \{ R_p (b_1), R_p (b_2), \ldots, R_p (b_{p - 1}) \} = B'</math> |
− | + | Na mocy twierdzenia [[#H24|H24]] zbiory <math>A</math> i <math>B</math> są równe modulo <math>p</math>. | |
− | + | Z twierdzenia [[#H20|H20]] wiemy, że wszystkie liczby <math>b^{- 1}_k \in C</math> są różne modulo <math>p</math>. Zauważmy, że każda z tych liczb jest względnie pierwsza z <math>p</math>, zatem nie może być podzielna przez <math>p</math>. Wynika stąd, że reszty <math>R_p (b^{- 1}_1), R_p (b^{- 1}_2), \ldots, R_p (b^{- 1}_{p - 1})</math> są wszystkie dodatnie i różne, a ponieważ jest ich <math>p - 1</math>, czyli dokładnie tyle, ile jest różnych i dodatnich reszt z dzielenia przez liczbę <math>p</math>, to zbiór tych reszt jest identyczny ze zbiorem dodatnich reszt z dzielenia przez <math>p</math>, czyli ze zbiorem <math>A</math>. Zatem mamy | |
− | ::<math>( | + | ::<math>A = A' = \{ R_p (b^{- 1}_1), R_p (b^{- 1}_2), \ldots, R_p (b^{- 1}_{p - 1}) \} = C'</math> |
− | + | Na mocy twierdzenia [[#H24|H24]] zbiory <math>A</math> i <math>C</math> są równe modulo <math>p</math>. Ponieważ <math>A' = B'</math> i <math>A' = C'</math>, to <math>B' = C'</math> i ponownie na mocy twierdzenia [[#H24|H24]] zbiory <math>B</math> i <math>C</math> są równe modulo <math>p</math>. Co należało pokazać.<br/> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 684: | Linia 687: | ||
− | <span style="font-size: 110%; font-weight: bold;"> | + | <span id="H26" style="font-size: 110%; font-weight: bold;">Zadanie H26</span><br/> |
− | Niech <math> | + | Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Pokazać, że suma <math>\sum_{k = 1}^{p - 1} {\small\frac{(p - 1) !}{k}}</math> jest podzielna przez <math>p</math>. |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show= | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} |
− | + | Zauważmy najpierw, że modulo <math>p</math> następujące sumy są równe | |
− | |||
− | |||
− | + | ::<math>\sum_{k = 1}^{p - 1} k \equiv \sum_{k = 1}^{p - 1} k^{- 1} \!\! \pmod{p}</math> | |
− | + | Istotnie, jeśli przyjmiemy w twierdzeniu [[#H25|H25]], że zbiór <math>B = \{ 1, 2, \ldots, p - 1 \}</math>, to zbiór <math>C</math> będzie zbiorem liczb, które są odwrotnościami liczb <math>1, 2, \ldots, p - 1</math> modulo <math>p</math> i możemy napisać | |
− | + | ::<math>\sum_{x \in B} x \equiv \sum_{y \in C} y \!\! \pmod{p}</math> | |
− | + | bo | |
− | + | :* gdy <math>x</math> przebiega kolejne wartości <math>b_k</math>, to <math>x</math> przyjmuje kolejno wartości <math>1, 2, \ldots, p - 1</math> | |
− | + | :* gdy <math>y</math> przebiega kolejne wartości <math>b_k^{- 1}</math>, to <math>y</math> (modulo <math>p</math>) przyjmuje wszystkie wartości ze zbioru <math>A = \{ 1, 2, \ldots, p - 1 \}</math>, czyli liczba <math>y</math> (modulo <math>p</math>) przyjmuje wszystkie wartości <math>1, 2, \ldots, p - 1</math>, ale w innej kolejności | |
− | + | Ponieważ kolejność sumowania tych samych składników nie wpływa na wartość sumy, to prawdziwa jest wyżej wypisana równość sum modulo <math>p</math>. | |
− | + | Zatem modulo <math>p</math> otrzymujemy | |
− | + | ::<math>\sum_{k = 1}^{p - 1} {\small\frac{(p - 1) !}{k}} \equiv \sum_{k = 1}^{p - 1} (p - 1)! \cdot k^{- 1}</math> | |
− | ::<math> | + | :::::<math>\;\;\: \equiv (p - 1) ! \cdot \sum_{k = 1}^{p - 1} k^{- 1}</math> |
− | + | :::::<math>\;\;\: \equiv (p - 1) ! \cdot \sum_{k = 1}^{p - 1} k</math> | |
− | + | :::::<math>\;\;\: \equiv (p - 1) ! \cdot {\small\frac{(p - 1) p}{2}}</math> | |
− | + | :::::<math>\;\;\: \equiv (p - 1) ! \cdot {\small\frac{p - 1}{2}} \cdot p</math> | |
− | ::<math> | + | :::::<math>\;\;\: \equiv 0 \!\! \pmod{p}</math> |
− | + | Należy zauważyć, że dla liczby pierwszej nieparzystej <math>p</math> liczba <math>{\small\frac{p - 1}{2}}</math> jest liczbą całkowitą.<br/> | |
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 730: | Linia 729: | ||
+ | == Funkcje multiplikatywne == | ||
+ | <span id="H27" style="font-size: 110%; font-weight: bold;">Definicja H27</span><br/> | ||
+ | Powiemy, że funkcja <math>f(n)</math> określona w zbiorze liczb całkowitych dodatnich jest funkcją multiplikatywną, jeżeli <math>f(1) = 1</math> i dla względnie pierwszych liczb <math>a, b</math> spełniony jest warunek <math>f(a b) = f (a) f (b)</math>. | ||
+ | <span id="H28" style="font-size: 110%; font-weight: bold;">Uwaga H28</span><br/> | ||
+ | Założenie <math>f(1) = 1</math> możemy równoważnie zastąpić założeniem, że funkcja <math>f(n)</math> nie jest tożsamościowo równa zero. | ||
+ | Gdyby <math>f(n)</math> spełniała jedynie warunek <math>f(a b) = f (a) f (b)</math> dla względnie pierwszych liczb <math>a, b</math>, to mielibyśmy | ||
+ | ::a) <math>f(n)</math> jest tożsamościowo równa zeru wtedy i tylko wtedy, gdy <math>f(1) = 0</math> | ||
− | + | ::b) <math>f(n)</math> nie jest tożsamościowo równa zeru wtedy i tylko wtedy, gdy <math>f(1) = 1</math> | |
− | + | Ponieważ <math>f(1) = f (1 \cdot 1) = f (1) f (1)</math>, zatem <math>f(1) = 0</math> lub <math>f (1) = 1</math>. | |
− | + | Jeżeli <math>f(1) = 0</math>, to dla dowolnego <math>n</math> mamy | |
− | |||
− | ::<math> | + | ::<math>f(n) = f (n \cdot 1) = f (n) f (1) = 0</math> |
− | + | Czyli <math>f(n)</math> jest funkcją tożsamościowo równą zero. | |
− | + | Jeżeli <math>f(n)</math> nie jest funkcją tożsamościowo równą zero, to istnieje taka liczba <math>a \in \mathbb{Z}_+</math>, że <math>f(a) \neq 0</math>. Zatem | |
− | + | ::<math>f(a) = f (a \cdot 1) = f (a) f (1)</math> | |
− | + | I dzieląc obie strony przez <math>f(a) \neq 0</math>, dostajemy <math>f(1) = 1</math>. | |
− | |||
− | |||
− | |||
+ | <span id="H29" style="font-size: 110%; font-weight: bold;">Przykład H29</span><br/> | ||
+ | Ponieważ <math>\gcd (1, c) = 1</math>, to <math>\gcd (n, c)</math> rozpatrywana jako funkcja <math>n</math>, gdzie <math>c</math> jest ustaloną liczbą całkowitą, jest funkcją multiplikatywną (zobacz [[#H8|H8]]). | ||
− | == | + | <span id="H30" style="font-size: 110%; font-weight: bold;">Twierdzenie H30</span><br/> |
− | + | Jeżeli funkcja <math>f(n)</math> jest funkcją multiplikatywną, to funkcja | |
+ | ::<math>F(n) = \sum_{d \mid n} f (d)</math> | ||
− | + | gdzie sumowanie przebiega po wszystkich dzielnikach dodatnich liczby <math>n</math>, jest również funkcją multiplikatywną. | |
− | |||
− | |||
− | |||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | + | Ponieważ | |
− | ::<math> | + | ::<math>F(1) = \sum_{d \mid 1} f (d) = f (1) = 1</math> |
− | + | to funkcja <math>F(n)</math> spełnia pierwszy warunek definicji [[#H27|H27]]. | |
− | + | Niech <math>a, b</math> będą względnie pierwszymi liczbami dodatnimi. Każdy dzielnik dodatni iloczynu <math>a b</math> można zapisać w postaci <math>d = d_1 d_2</math>, gdzie <math>d_1 \mid a</math>, <math>\; d_2 \mid b \,</math> oraz <math>\, \gcd (d_1, d_2) = 1</math> (zobacz [[#H13|H13]]). Niech zbiory | |
− | + | ::<math>S_a = \{ d \in \mathbb{Z}_+ : d \mid a \}</math> | |
− | + | ::<math>S_b = \{ d \in \mathbb{Z}_+ : d \mid b \}</math> | |
− | + | ::<math>S_{a b} = \{ d \in \mathbb{Z}_+ : d \mid a b \}</math> | |
− | + | będą zbiorami dzielników dodatnich liczb <math>a, b</math> i <math>a b</math>. Dla przykładu | |
− | + | ::<math>S_5 = \{ 1, 5 \}</math> | |
− | + | ::<math>S_7 = \{ 1, 7 \}</math> | |
− | |||
− | |||
+ | ::<math>S_{35} = \{ 1, 5, 7, 35 \}</math> | ||
+ | Dla dowolnego <math>d_1 \in S_a \,</math> i <math>\, d_2 \in S_b</math> musi być <math>\gcd (d_1, d_2) = 1</math>, bo gdyby było <math>\gcd (d_1, d_2) = g > 1</math>, to | ||
− | + | ::<math>g \mid d_1 \quad \; \text{i} \quad \; d_1 \mid a \qquad \quad \Longrightarrow \qquad \quad g \mid a</math> | |
− | |||
− | ::<math>\ | + | ::<math>g \mid d_2 \quad \; \text{i} \quad \; d_2 \mid b \qquad \quad \Longrightarrow \qquad \quad g \mid b</math> |
− | + | Zatem <math>g \mid \gcd (a, b)</math> i mielibyśmy <math>\gcd (a, b) \geqslant g > 1</math>, wbrew założeniu. | |
− | |||
− | + | Przekształcając, otrzymujemy | |
− | + | ::<math>F(a b) = \sum_{d \mid a b} f (d)</math> | |
− | ::<math>\ | + | :::<math>\;\;\;\;\: = \sum_{d \in S_{a b}} f (d)</math> |
− | + | :::<math>\;\;\;\;\: = \underset{d_2 \in S_{b}}{\sum_{d_1 \in S_{a}}} f (d_1 d_2)</math> | |
− | ::<math> | + | :::<math>\;\;\;\;\: = \underset{d_2 \in S_{b}}{\sum_{d_1 \in S_{a}}} f (d_1) f (d_2)</math> |
− | + | :::<math>\;\;\;\;\: = \sum_{d_1 \in S_{a}} f (d_1) \sum_{d_2 \in S_{b}} f (d_2)</math> | |
− | ::<math>\ | + | :::<math>\;\;\;\;\: = \sum_{d_1 \mid a} f (d_1) \sum_{d_2 \mid b} f (d_2)</math> |
− | + | :::<math>\;\;\;\;\: = F (a) F (b)</math> | |
− | + | Co należało pokazać.<br/> | |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 825: | Linia 825: | ||
− | |||
− | |||
− | |||
− | + | == Funkcja Eulera <math>\varphi (n)</math> == | |
− | + | <span id="H31" style="font-size: 110%; font-weight: bold;">Definicja H31</span><br/> | |
+ | Funkcja Eulera <math>\varphi (n)</math><ref name="Euler1"/> jest równa ilości liczb całkowitych dodatnich nie większych od <math>n</math> i względnie pierwszych z <math>n</math>. | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | <span id="H32" style="font-size: 110%; font-weight: bold;">Twierdzenie H32</span><br/> | ||
+ | Funkcja Eulera <math>\varphi (n)</math> jest multiplikatywna, czyli dla względnie pierwszych liczb <math>m, n</math> jest <math>\varphi (m n) = \varphi (m) \varphi (n)</math>. | ||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
+ | Niech <math>m, n</math> będą dodatnimi liczbami całkowitymi takimi, że <math>\gcd (m, n) = 1</math>. Twierdzenie jest prawdziwe dla <math>n = 1</math>, zatem nie zmniejszając ogólności, możemy założyć, że <math>n > 1</math>. Wypiszmy w tabeli wszystkie liczby od <math>1</math> do <math>m n</math>. | ||
− | + | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: right; margin-right: auto;" | |
− | + | |- | |
+ | | <math>1</math> || <math>2</math> || <math>…</math> || <math>k</math> || <math>…</math> || <math>m</math> | ||
+ | |- | ||
+ | | <math>m + 1</math> || <math>m + 2</math> || <math>…</math> || <math>m + k</math> || <math>…</math> || <math>2 m</math> | ||
+ | |- | ||
+ | | <math>2 m + 1</math> || <math>2 m + 2</math> || <math>…</math> || <math>2 m + k</math> || <math>…</math> || <math>3 m</math> | ||
+ | |- | ||
+ | | <math>…</math> || <math>…</math> || <math>…</math> || <math>…</math> || <math></math> || <math></math> | ||
+ | |- | ||
+ | | <math>(n - 1) m + 1</math> || <math>(n - 1) m + 2</math> || <math>…</math> || <math>(n - 1) m + k</math> || <math>…</math> || <math>n m</math> | ||
+ | |} | ||
− | + | '''1.''' Natychmiast widzimy, że w pierwszym wierszu mamy <math>\varphi (m)</math> liczb względnie pierwszych z <math>m</math>. Tak samo jest w każdym kolejnym wierszu, bo (zobacz [[#H5|H5]]) | |
− | + | ::<math>\gcd (r m + k, m) = \gcd (k, m)</math> | |
+ | Zatem mamy dokładnie <math>\varphi (m)</math> kolumn liczb względnie pierwszych z <math>m</math>. | ||
+ | '''2.''' Załóżmy, że liczba <math>k</math> jest jedną z liczb względnie pierwszych z <math>m</math>, czyli <math>\gcd (k, m) = 1</math>. Przy tym założeniu <math>k</math>-ta kolumna (pokazana w tabeli) jest kolumną liczb względnie pierwszych z <math>m</math>. | ||
− | + | '''3.''' Zauważmy, że reszty z dzielenia liczb wypisanych w <math>k</math>-tej kolumnie przez <math>n</math> są wszystkie różne. Gdyby tak nie było, to dla pewnych <math>i, j</math>, gdzie <math>0 \leqslant i, j \leqslant n - 1</math>, różnica liczb <math>i m + k</math> oraz <math>j m + k</math> byłaby podzielna przez <math>n</math>. Mielibyśmy | |
− | + | ::<math>n \mid ((i m + k) - (j m + k))</math> | |
− | + | Skąd wynika natychmiast | |
− | |||
− | ::<math> | + | ::<math>n \mid (i - j) m</math> |
− | + | Ponieważ założyliśmy, że <math>\gcd (n, m) = 1</math>, to musi być <math>n \mid (i - j)</math> (zobacz C74), ale | |
− | |||
− | ::<math> | + | ::<math>0 \leqslant | i - j | \leqslant n - 1</math> |
− | + | Czyli <math>n</math> może dzielić <math>i - j</math> tylko w przypadku, gdy <math>i = j</math>. Wbrew naszemu przypuszczeniu, że istnieją różne liczby dające takie same reszty przy dzieleniu przez <math>n</math>. | |
− | |||
− | + | '''4.''' Ponieważ w <math>k</math>-tej kolumnie znajduje się dokładnie <math>n</math> liczb i reszty z dzielenia tych liczb przez <math>n</math> są wszystkie różne, to reszty te tworzą zbiór <math>S = \{ 0, 1, \ldots, n - 1 \}</math>. Wynika stąd, że liczby wypisane w <math>k</math>-tej kolumnie mogą być zapisane w postaci | |
− | ::<math>\ | + | ::<math>a_r = b_r \cdot n + r</math> |
− | + | gdzie <math>r = 0, 1, \ldots, n - 1</math> i <math>b_r \in \mathbb{Z}</math>. | |
− | + | Zauważmy, że następujące ilości liczb są sobie równe | |
− | + | :* ilość liczb w <math>k</math>-tej kolumnie względnie pierwszych z <math>n</math> | |
− | + | :* ilość liczb <math>r</math> względnie pierwszych z <math>n</math>, gdzie <math>r = 0, \ldots, n - 1</math>, bo <math>\gcd (b_r \cdot n + r, n) = \gcd (r, n)</math> | |
− | : | + | :* ilość liczb <math>r</math> względnie pierwszych z <math>n</math>, gdzie <math>r = 1, \ldots, n</math>, bo <math>\gcd (n, n) = \gcd (0, n) = | n | > 1</math> |
− | + | Ostatnia ilość liczb jest równa <math>\varphi (n)</math>, co wynika wprost z definicji funkcji <math>\varphi (n)</math>. | |
− | |||
− | : | + | '''5.''' Zbierając: mamy w wypisanej tabeli dokładnie <math>\varphi (m) \varphi (n)</math> liczb <math>u \in [1, m n]</math>, dla których jednocześnie jest |
− | + | ::<math>\gcd (u, m) = 1 \quad \text{i} \quad \gcd (u, n) = 1</math> | |
− | + | Z twierdzenia [[#H6|H6]] wynika, że w tabeli jest dokładnie <math>\varphi (m) \varphi (n)</math> liczb <math>u \in [1, m n]</math>, dla których jest | |
− | + | ::<math>\gcd (u, m n) = 1</math> | |
− | + | Zatem <math>\varphi (m n) = \varphi (m) \varphi (n)</math>. Co należało pokazać.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | ::<math> | + | <span id="H33" style="font-size: 110%; font-weight: bold;">Twierdzenie H33</span><br/> |
+ | Dla dowolnej liczby całkowitej dodatniej <math>n</math> jest | ||
− | + | ::<math>\varphi (n) = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right)</math> | |
− | + | gdzie iloczyn obliczamy po wszystkich liczbach pierwszych <math>p</math>, będących dzielnikami liczby <math>n</math>. | |
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | |
+ | Ponieważ wszystkie liczby naturalne mniejsze od liczby pierwszej <math>p</math> są jednocześnie pierwsze względem <math>p</math>, to <math>\varphi (p) = p - 1</math>. | ||
− | + | Równie łatwo znajdujemy wartość funkcji <math>\varphi (n)</math> w przypadku gdy <math>n</math> jest potęgą liczby pierwszej <math>n = p^k</math>. Wystarczy zauważyć, że w ciągu kolejnych liczb | |
− | ::<math> | + | ::<math>1, 2, 3, 4, \ldots, p^k - 1, p^k</math> |
− | + | jedynymi liczbami, które nie są pierwsze względem <math>p^k</math>, są te, które dzielą się przez <math>p</math> i jest ich <math>p^{k - 1}</math>, co widać natychmiast po ich bezpośrednim wypisaniu | |
− | & | ||
− | |||
+ | ::<math>1 \cdot p, 2 \cdot p, 3 \cdot p, \ldots, (p^{k - 1} - 1) \cdot p, p^{k - 1} \cdot p</math> | ||
+ | Zatem | ||
− | + | ::<math>\varphi (p^k) = p^k - p^{k - 1} = p^k \left( 1 - {\small\frac{1}{p}} \right)</math> | |
− | |||
− | + | Ponieważ <math>\varphi (n)</math> jest funkcją multiplikatywną, to dla <math>n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math> otrzymujemy | |
− | |||
− | ::<math>\ | + | ::<math>\varphi (n) = \prod^s_{k = 1} \varphi (p^{\alpha_k}_k)</math> |
− | + | :::<math>\;\;\; = \prod^s_{k = 1} p^{\alpha_k}_k \left( 1 - {\small\frac{1}{p_k}} \right)</math> | |
− | :: | + | :::<math>\;\;\; = \left[ \prod^s_{k = 1} p^{\alpha_k}_k \right] \cdot \left[ \prod^s_{k = 1} \left( 1 - {\small\frac{1}{p_k}} \right) \right]</math> |
− | |||
− | |||
+ | :::<math>\;\;\; = n \cdot \prod^s_{k = 1} \left( 1 - {\small\frac{1}{p_k}} \right)</math> | ||
+ | :::<math>\;\;\; = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right)</math> | ||
− | + | Co należało pokazać.<br/> | |
− | + | □ | |
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | |||
− | :: | + | <span id="H34" style="font-size: 110%; font-weight: bold;">Twierdzenie H34</span><br/> |
+ | Niech <math>n \in \mathbb{Z}_+</math>. Jeżeli <math>q</math> jest liczbą pierwszą, to | ||
− | :: | + | ::<math>\varphi (q n) = \left\{ \begin{array}{rl} |
+ | (q - 1) \varphi (n) & \quad \text{gdy} \quad q \nmid n \\ | ||
+ | q \varphi (n) & \quad \text{gdy} \quad q \mid n \\ | ||
+ | \end{array} \right.</math> | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
+ | Jeżeli <math>q \nmid m</math>, to <math>\gcd (q, m) = 1</math>, zatem <math>\varphi (q m) = \varphi (q) \varphi (m) = (q - 1) \varphi (m)</math>. Jeżeli <math>q \mid m</math>, to liczby <math>m</math> oraz <math>q m</math> mają taki sam zbiór dzielników pierwszych, zatem | ||
− | + | ::<math>\varphi (q m) = q m \prod_{p \mid q m} \left( 1 - {\small\frac{1}{p}} \right) = q \cdot \left[ m \prod_{p \mid m} \left( 1 - {\small\frac{1}{p}} \right) \right] = q \varphi (m)</math> | |
− | + | Co należało pokazać.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | ::<math> | + | <span id="H35" style="font-size: 110%; font-weight: bold;">Zadanie H35</span><br/> |
+ | Niech <math>q \in \mathbb{P}</math> i <math>a, b, m, n \in \mathbb{Z}_+</math>. Pokazać, że | ||
− | + | :* <math>\varphi (q^{a + b}) = q^a \varphi (q^b)</math> | |
− | + | :* <math>\varphi (n^m) = n^{m - 1} \varphi (n)</math> | |
− | |||
− | |||
− | '''Punkt | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} |
+ | '''Punkt 1.''' | ||
− | + | ::<math>\varphi (q^{a + b}) = (q - 1) q^{a + b - 1} = q^a \cdot (q - 1) q^{b - 1} = q^a \varphi (q^b)</math> | |
− | + | '''Punkt 2.''' | |
− | + | Niech <math>n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math> | |
− | ::<math>\ | + | ::<math>\varphi (n^m) = \varphi (p^{m \alpha_1}_1 \cdot \ldots \cdot p^{m \alpha_s}_s)</math> |
− | + | ::::<math>\, = \varphi (p^{m \alpha_1}_1) \cdot \ldots \cdot \varphi (p^{m \alpha_s}_s)</math> | |
− | + | ::::<math>\, = \varphi (p^{(m - 1) \alpha_1 + \alpha_1}_1) \cdot \ldots \cdot \varphi (p^{(m - 1) \alpha_s + \alpha_s}_s)</math> | |
− | + | ::::<math>\, = p^{(m - 1) \alpha_1}_1 \varphi (p^{\alpha_1}_1) \cdot \ldots \cdot p^{(m - 1) \alpha_s}_s \varphi (p^{\alpha_s}_s)</math> | |
− | ::<math> | + | ::::<math>\, = p^{(m - 1) \alpha_1}_1 \cdot \ldots \cdot p^{(m - 1) \alpha_s}_s \cdot \varphi (p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s)</math> |
− | + | ::::<math>\, = n^{m - 1} \varphi (n)</math> | |
− | + | Co należało pokazać.<br/> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 1023: | Linia 1002: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="H36" style="font-size: 110%; font-weight: bold;">Twierdzenie H36</span><br/> |
− | + | Niech <math>m, n \in \mathbb{Z}_+</math>. Jeżeli <math>m \mid n</math>, to <math>\varphi (m) \mid \varphi (n)</math>. | |
− | ::<math> | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} |
+ | Niech <math>n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>. Ponieważ założyliśmy, że <math>m \mid n</math>, to <math>m</math> musi być postaci <math>m = p^{\beta_1}_1 \cdot \ldots \cdot p^{\beta_s}_s</math>, gdzie <math>0 \leqslant \beta_i \leqslant \alpha_i</math>, dla <math>i = 1, \ldots, s</math>. Łatwo zauważamy, że | ||
− | : | + | :* jeżeli <math>\beta_i = 0</math>, to <math>\varphi (p^{\beta_i}_i) = 1</math> i dzieli <math>\varphi (p^{\alpha_i}_i)</math> |
− | + | :* jeżeli <math>1 \leqslant \beta_i \leqslant \alpha_i</math>, to <math>(p_i - 1) p_i^{\beta_i - 1} \mid (p_i - 1) p_i^{\alpha_i - 1}</math>, zatem <math>\varphi (p^{\beta_i}_i) \mid \varphi (p^{\alpha_i}_i)</math> | |
− | < | ||
− | + | Skąd natychmiast wynika, że <math>\varphi (p^{\beta_1}_1) \cdot \ldots \cdot \varphi (p^{\beta_s}_s)</math> dzieli <math>\varphi (p^{\alpha_1}_1) \cdot \ldots \cdot \varphi (p^{\alpha_s}_s)</math>, czyli <math>\varphi (m) \mid \varphi (n)</math>. | |
− | + | Zauważmy, że twierdzenie odwrotne nie jest prawdziwe, bo <math>\varphi (7) \mid \varphi (19)</math>, ale <math>7 \nmid 19</math>.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
+ | <span id="H37" style="font-size: 110%; font-weight: bold;">Zadanie H37</span><br/> | ||
+ | Dla <math>n \geqslant 3</math> wartości <math>\varphi (n)</math> są liczbami parzystymi. | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | |
+ | Jeżeli liczba <math>n \geqslant 3</math> jest podzielna przez liczbę pierwszą nieparzystą <math>p</math>, zaś <math>k</math> jest wykładnikiem, z jakim <math>p</math> wchodzi do rozwinięcia <math>n</math> na czynniki pierwsze, to | ||
− | ::<math>n | + | ::<math>\varphi (n) = \varphi \left( p^k \cdot {\small\frac{n}{p^k}} \right) = (p - 1) p^{k - 1} \cdot \varphi \left( {\small\frac{n}{p^k}} \right)</math> |
− | + | zatem <math>\varphi (n)</math> jest liczbą parzystą, ponieważ <math>p - 1</math> jest liczbą parzystą. | |
+ | Jeżeli żadna liczba nieparzysta nie dzieli <math>n</math>, to liczba <math>n</math> jest postaci <math>n = 2^a</math> i <math>\varphi (n) = 2^{a - 1}</math>, ale z założenia <math>n \geqslant 3</math>, zatem <math>a \geqslant 2</math> i <math>\varphi (n)</math> jest liczbą parzystą.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | + | <span id="H38" style="font-size: 110%; font-weight: bold;">Twierdzenie H38</span><br/> | |
+ | Jeżeli <math>n</math> jest liczbą złożoną, to <math>\varphi (n) \leqslant n - \sqrt{n}</math>. | ||
− | :: | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} |
+ | <span style="border-bottom-style: double;">Pierwszy sposób</span><br/> | ||
+ | Niech <math>n = a b</math>, gdzie <math>1 < a \leqslant b < n</math>. Liczby <math>1 \cdot a, 2 \cdot a, 3 \cdot a, \ldots, b \cdot a</math> są nie większe od <math>n</math> i nie są względnie pierwsze z <math>n</math>, zatem | ||
+ | ::<math>\varphi (n) \leqslant n - b</math> | ||
− | + | Ponieważ <math>b \geqslant a</math>, to <math>b^2 \geqslant a b = n</math> i <math>b \geqslant \sqrt{n}</math>. Wynika stąd, że | |
− | ::<math>n | + | ::<math>\varphi (n) \leqslant n - b \leqslant n - \sqrt{n}</math> |
− | + | <br/><span style="border-bottom-style: double;">Drugi sposób</span><br/> | |
+ | Niech <math>q</math> oznacza najmniejszy dzielnik pierwszy liczby złożonej <math>n</math>, zatem <math>q^2 \leqslant n</math>, czyli <math>q \leqslant \sqrt{n}</math>, a stąd <math>{\small\frac{n}{q}} \geqslant \sqrt{n}</math> i | ||
− | + | ::<math>\varphi (n) = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right) \leqslant n \left( 1 - {\small\frac{1}{q}} \right) = n - {\small\frac{n}{q}} \leqslant n - \sqrt{n}</math> | |
− | + | ||
− | + | Co należało pokazać.<br/> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 1081: | Linia 1060: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="H39" style="font-size: 110%; font-weight: bold;">Twierdzenie H39</span><br/> |
− | Dla <math>n \geqslant 1</math> prawdziwe jest oszacowanie | + | Dla <math>n \geqslant 1</math> prawdziwe jest oszacowanie <math>\varphi (n) > {\small\frac{\sqrt{n}}{2}}</math>. |
− | |||
− | |||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | + | Dla <math>k \geqslant 3</math> jest | |
− | ::<math>( | + | ::<math>\left( 1 - {\small\frac{1}{k}} \right)^2 > {\small\frac{1}{k}}</math> |
− | + | Wynika stąd, że jeżeli <math>m \geqslant 3</math> jest liczbą nieparzystą, to | |
− | + | ::<math>\varphi (m)^2 = m^2 \prod_{p|m} \left( 1 - {\small\frac{1}{p}} \right)^2 > m^2 \prod_{p|m} {\small\frac{1}{p}} \geqslant m</math> | |
− | + | bo | |
− | + | ::<math>\prod_{p|m} p \leqslant m</math> | |
− | + | Czyli dla nieparzystych liczb <math>m \geqslant 3</math> mamy | |
− | + | ::<math>\varphi (m) > \sqrt{m} > {\small\frac{\sqrt{m}}{2}}</math> | |
− | |||
− | |||
+ | Jeżeli <math>d = 2^a</math>, gdzie <math>a \geqslant 1</math>, to | ||
− | < | + | ::<math>\varphi (d) = \varphi (2^a) = 2^{a - 1} > {\small\frac{\sqrt{2^a}}{2}} = {\small\frac{\sqrt{d}}{2}}</math> |
− | |||
− | |||
− | |||
− | + | W przypadku ogólnym, gdy <math>n</math> jest iloczynem liczby nieparzystej <math>m \geqslant 3</math> i potęgi liczby <math>2</math>, dostajemy | |
− | + | ::<math>\varphi (n) = \varphi (2^a m) = \varphi (2^a) \varphi (m) > {\small\frac{\sqrt{2^a}}{2}} \cdot \sqrt{m} = {\small\frac{\sqrt{2^a m}}{2}} = {\small\frac{\sqrt{n}}{2}}</math> | |
− | + | Oczywiście nierówność <math>\varphi (n) > {\small\frac{\sqrt{n}}{2}}</math> jest również prawdziwa dla <math>n = 1</math>. Co należało pokazać.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | + | <span id="H40" style="font-size: 110%; font-weight: bold;">Zadanie H40</span><br/> | |
+ | Pokazać, że dla <math>n \geqslant 7</math> prawdziwe jest oszacowanie <math>\varphi (n) > \sqrt{n}</math>. | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | |
+ | Zauważmy, że | ||
− | ::<math> | + | ::<math>n - 1 > \sqrt{n} \qquad \qquad \;\, \text{dla} \; n \geqslant 3</math> |
− | + | ::<math>n - 1 > \sqrt{2 n} \qquad \qquad \text{dla} \; n \geqslant 4</math> | |
− | |||
− | |||
+ | Zatem dla liczby pierwszej <math>p</math> i <math>k \geqslant 1</math> jest | ||
− | + | ::<math>\varphi (p^k) = (p - 1) p^{k - 1} > \sqrt{p} \cdot p^{k - 1} = p^{k - \tfrac{1}{2}} \geqslant p^{\tfrac{k}{2}} = \sqrt{p^k} \qquad \qquad \qquad \qquad \quad \; \text{dla} \;\: p \geqslant 3</math> | |
− | |||
− | + | ::<math>\varphi (p^k) = (p - 1) p^{k - 1} > \sqrt{2 p} \cdot p^{k - 1} = \sqrt{2} \cdot p^{k - \tfrac{1}{2}} \geqslant \sqrt{2} \cdot p^{\tfrac{k}{2}} = \sqrt{2 p^k} \qquad \qquad \text{dla} \;\, p \geqslant 5</math> | |
− | |||
− | |||
− | + | '''1. Przypadek, gdy <math>\boldsymbol{n \geqslant 3}</math> jest liczbą nieparzystą''' | |
− | + | Liczba <math>n</math> jest iloczynem czynników pierwszych nieparzystych, zatem | |
− | |||
− | |||
+ | ::<math>\varphi (n) = \varphi (p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s) = \varphi (p^{\alpha_1}_1) \cdot \ldots \cdot \varphi (p^{\alpha_s}_s) > \sqrt{p^{\alpha_1}_1} \cdot \ldots \cdot \sqrt{p^{\alpha_s}_s} = \sqrt{n}</math> | ||
− | + | '''2. Przypadek, gdy <math>\boldsymbol{n = 2^a m} \;</math> i <math>\; \boldsymbol{q \mid m ,} \;</math> gdzie <math>\; \boldsymbol{q \geqslant 5}</math>''' | |
+ | Z założenia <math>n = 2^a m = 2^a q^b r</math>, gdzie <math>r \geqslant 1</math> jest liczbą nieparzystą. Zauważmy, że <math>\varphi (r) \geqslant \sqrt{r}</math>, bo może być <math>r = 1</math>. | ||
− | + | ::<math>\varphi (n) = \varphi (2^a q^b r)</math> | |
− | |||
− | |||
− | + | :::<math>\;\;\,\, = \varphi (2^a) \varphi (q^b) \varphi (r)</math> | |
− | |||
− | + | :::<math>\;\;\,\, > 2^{a - 1} \sqrt{2 q^b} \sqrt{r}</math> | |
− | ::<math>\ | + | :::<math>\;\;\,\, = 2^{a - \tfrac{1}{2}} \sqrt{q^b} \sqrt{r}</math> |
− | + | :::<math>\;\;\,\, \geqslant 2^{\tfrac{a}{2}} \sqrt{q^b r}</math> | |
− | + | :::<math>\;\;\,\, = \sqrt{2^a q^b r}</math> | |
− | + | :::<math>\;\;\,\, = \sqrt{n}</math> | |
− | < | + | '''3. Przypadek, gdy <math>\boldsymbol{n = 2^a m} \;</math> i <math>\; \boldsymbol{q \nmid m ,} \;</math> gdzie <math>\; \boldsymbol{q \geqslant 5}</math>''' |
− | |||
− | + | Jeżeli żadna liczba pierwsza <math>q \geqslant 5</math> nie dzieli <math>m</math>, to możliwe są tylko dwie sytuacje: <math>n = 2^a \,</math> i <math>\, n = 2^a 3^b</math>. | |
− | + | '''3a. Przypadek, gdy <math>\boldsymbol{n = 2^a}</math>''' | |
− | + | ::<math>\varphi (n) = \varphi (2^a) = 2^{a - 1} > \sqrt{2^a} = \sqrt{n} \qquad \qquad \;\, \text{dla} \; a \geqslant 3</math> | |
− | |||
− | |||
− | |||
− | + | Twierdzenie nie jest prawdziwe dla <math>n = 2 \,</math> i <math>\, n = 4 \,\,</math> (gdy <math>a = 1 \,</math> lub <math>\, a = 2</math>). | |
− | + | '''3b. Przypadek, gdy <math>\boldsymbol{n = 2^a 3^b}</math>''' | |
− | + | ::<math>\varphi (n) = \varphi (2^a 3^b) = \varphi (2^a) \varphi (3^b) = 2^{a - 1} \cdot 2 \cdot 3^{b - 1} = 2^a 3^{b - 1} = \sqrt{2^a 3^b} \cdot {\small\frac{\sqrt{2^a 3^b}}{3}} > \sqrt{2^a 3^b}</math> | |
− | + | Ostatnia nierówność jest prawdziwa, o ile <math>\sqrt{2^a 3^b} > 3</math>, czyli gdy <math>2^a 3^b > 9</math>, co ma miejsce, gdy <math>a \geqslant 2</math> lub <math>b \geqslant 2</math>. | |
− | + | Twierdzenie nie jest prawdziwe dla <math>n = 6 \;</math> (gdy <math>a = 1 \,</math> i <math>\, b = 1</math>). | |
− | |||
− | : | + | Zbierając uzyskane wyniki, otrzymujemy: oszacowanie <math>\varphi (n) > \sqrt{n}</math> nie jest prawdziwe dla <math>n = 1, 2, 4, 6</math>. Co należało pokazać.<br/> |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
+ | <span id="H41" style="font-size: 110%; font-weight: bold;">Zadanie H41</span><br/> | ||
+ | Pokazać, że dla <math>n \geqslant 2</math> prawdziwe jest oszacowanie <math>\varphi (n) > {\small\frac{n}{3 \log n}}</math>. Korzystając z tego wyniku, pokazać, że <math>\varphi (n) > n^{2 / 3}</math> dla <math>n \geqslant 43</math> oraz że <math>\varphi (n) > n^{3 / 4}</math> dla <math>n \geqslant 211</math>. | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | |
− | + | Niech <math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>, a <math>n' = q_1 \cdot \ldots \cdot q_s</math> oznacza liczbę, będącą iloczynem dokładnie '''tych samych''' czynników pierwszych, jakie występują w liczbie <math>n</math>, natomiast <math>n^{\!\ast} = p_1 \cdot \ldots \cdot p_s</math> oznacza liczbę, będącą iloczynem dokładnie '''tej samej ilości''' czynników pierwszych, przy czym <math>p_i</math> oznacza teraz <math>i</math>-tą liczbę pierwszą. | |
− | + | Ponieważ | |
− | + | ::<math>{\small\frac{\varphi (n)}{n}} = \prod_{p \mid n} \left( 1 - {\small\frac{1}{p}} \right)</math> | |
− | + | to | |
− | + | ::<math>{\small\frac{\varphi (n)}{n}} = {\small\frac{\varphi (n')}{n'}} \geqslant {\small\frac{\varphi (n^{\!\ast})}{n^{\!\ast}}} = \prod^s_{i = 1} \left( 1 - {\small\frac{1}{p_i}} \right) \geqslant \prod^{p_s}_{k = 2} \left( 1 - {\small\frac{1}{k}} \right) = {\small\frac{1}{p_s}}</math> | |
− | + | Ostatnia równość wynika z prostego wzoru | |
− | ::<math>\left\ | + | ::<math>\prod^m_{k = 2} \left( 1 - {\small\frac{1}{k}} \right) = {\small\frac{1}{2}} \cdot {\small\frac{2}{3}} \cdot {\small\frac{3}{4}} \cdot \ldots \cdot {\small\frac{m - 2}{m - 1}} \cdot {\small\frac{m - 1}{m}} = {\small\frac{1}{m}}</math> |
− | |||
− | + | Musimy oszacować wartość liczby <math>p_s</math>. Z twierdzenia B31 wynika, że dla <math>m \geqslant 2</math> jest <math>P(m) \geqslant 2^{m / 2}</math>, gdzie funkcja <math>P(m)</math> jest równa iloczynowi wszystkich liczb pierwszych nie większych od <math>m</math>. Zatem dla <math>p_s \geqslant 2</math> jest | |
+ | ::<math>n^{\!\ast} = p_1 \cdot \ldots \cdot p_s = P (p_s) \geqslant 2^{p_s / 2}</math> | ||
− | + | Logarytmując, otrzymujemy | |
− | ::<math> | + | ::<math>p_s \leqslant {\small\frac{2 \log n^{\!\ast}}{\log 2}}</math> |
− | + | Ponieważ <math>n \geqslant n' \geqslant n^{\!\ast}</math>, to | |
− | ::<math>\ | + | ::<math>{\small\frac{\varphi (n)}{n}} \geqslant {\small\frac{1}{p_s}} \geqslant {\small\frac{\log 2}{2 \log n^{\!\ast}}} \geqslant {\small\frac{\log 2}{2 \log n}} > {\small\frac{1}{3 \log n}}</math> |
− | + | Ostatecznie otrzymujemy | |
− | ::<math>\ | + | ::<math>\varphi (n) > {\small\frac{n}{3 \log n}}</math> |
− | + | Co należało pokazać. | |
− | |||
− | + | Rozwiązując drugą część zadania, wystarczy znaleźć, dla jakich <math>n</math> prawdziwa jest nierówność | |
− | + | ::<math>{\small\frac{n}{3 \log n}} > n^{2 / 3}</math> | |
− | + | Przebieg funkcji <math>{\small\frac{n}{3 \log n}} \,</math> i <math>\, n^{2 / 3}</math> przedstawiliśmy na wykresie | |
− | |||
− | |||
− | |||
+ | ::[[File: Euler1.png|1100px|none]] | ||
+ | Punkt przecięcia tych funkcji znajdujemy, wpisując w PARI/GP polecenie | ||
− | <span style="font-size: | + | <span style="font-size: 90%; color:black;">'''solve'''(n = 10, 10^5, n/(3*'''log'''(n)) - n^(2/3))</span> |
− | |||
− | + | Otrzymujemy | |
− | |||
− | |||
− | ::<math> | + | ::<math>n = 29409.965</math> |
− | + | Zatem <math>{\small\frac{n}{3 \log n}} > n^{2 / 3}</math> dla <math>n > 2.95 \cdot 10^4</math>. | |
− | + | Poleceniem | |
− | |||
− | |||
− | |||
− | + | <span style="font-size: 90%; color:black;">'''for'''(n = 1, 3*10^4, '''if'''( '''eulerphi'''(n) <= n^(2/3), '''print'''(n) ))</span> | |
− | + | sprawdzamy, że oszacowanie <math>\varphi (n) > n^{2 / 3}</math> jest prawdziwe dla <math>n \geqslant 43</math>. | |
− | |||
− | + | Postępując analogicznie jak wyżej, znajdujemy, dla jakich <math>n</math> prawdziwa jest nierówność | |
− | + | ::<math>{\small\frac{n}{3 \log n}} > n^{3 / 4}</math> | |
+ | Wpisując w PARI/GP polecenie | ||
− | <span style=" | + | <span style="font-size: 90%; color:black;">'''solve'''(n = 10, 10^7, n/(3*'''log'''(n)) - n^(3/4))</span> |
− | |||
− | + | otrzymujemy | |
− | + | ::<math>n = 4447862.680</math> | |
− | + | Zatem <math>{\small\frac{n}{3 \log n}} > n^{3 / 4}</math> dla <math>n > 4.45 \cdot 10^6</math> | |
− | + | Poleceniem | |
− | + | <span style="font-size: 90%; color:black;">'''for'''(n = 1, 5*10^6, '''if'''( '''eulerphi'''(n) <= n^(3/4), '''print'''(n) ))</span> | |
− | + | sprawdzamy, że oszacowanie <math>\varphi (n) > n^{3 / 4}</math> jest prawdziwe dla <math>n \geqslant 211</math>. Co należało pokazać.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
+ | <span id="H42" style="font-size: 110%; font-weight: bold;">Twierdzenie H42</span><br/> | ||
+ | Niech <math>n \in \mathbb{Z}_+</math>. Liczba <math>n</math> jest liczbą pierwszą wtedy i tylko wtedy, gdy <math>\varphi (n) = n - 1</math>. | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | |
+ | Dla liczb złożonych <math>n \geqslant 4</math> nigdy nie będzie <math>\varphi (n) = n - 1</math>, bo | ||
− | ::<math | + | ::<math>\varphi (n) \leqslant n - \sqrt{n} \leqslant n - 2</math> |
− | + | Dla <math>n = 1, 2, 3</math> sprawdzamy bezpośrednio: <math>\varphi (1) = 1 \neq 1 - 1</math>, <math>\varphi (2) = 1 = 2 - 1</math>, <math>\varphi (3) = 2 = 3 - 1</math>. Co kończy dowód.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | + | <span id="H43" style="font-size: 110%; font-weight: bold;">Twierdzenie H43</span><br/> | |
− | + | Dla dowolnej liczby całkowitej dodatniej <math>n</math> jest | |
− | |||
+ | ::<math>n = \sum_{d \mid n} \varphi (d) = \sum_{d \mid n} \varphi \left( {\small\frac{n}{d}} \right)</math> | ||
+ | gdzie sumowanie przebiega po wszystkich dzielnikach dodatnich liczby <math>n</math>. | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | |
− | + | Ponieważ <math>\varphi (n)</math> jest funkcją multiplikatywną, to funkcja | |
− | + | ::<math>F(n) = \sum_{d \mid n} \varphi (d)</math> | |
− | |||
− | |||
− | + | też jest funkcją multiplikatywną (zobacz [[#H30|H30]]). Łatwo sprawdzamy, że twierdzenie jest prawdziwe dla <math>n = 1</math>. Niech <math>n > 1</math>. Jeżeli <math>n = | |
+ | p^{\alpha}</math> jest potęgą liczby pierwszej, to otrzymujemy | ||
− | + | ::<math>F (p^{\alpha}) = \sum_{d \mid p^{\alpha}} \varphi (d)</math> | |
− | + | ::::<math>= \varphi (1) + \varphi (p) + \varphi (p^2) + \ldots + \varphi (p^{\alpha}) =</math> | |
− | |||
− | |||
− | |||
+ | ::::<math>= 1 + (p - 1) + p (p - 1) + \ldots + p^{\alpha - 1} (p - 1) =</math> | ||
− | + | ::::<math>= 1 + (p - 1) + (p^2 - p) + \ldots + (p^{\alpha} - p^{\alpha - 1})</math> | |
− | ::<math> | + | ::::<math>= p^{\alpha}</math> |
− | + | Jeżeli <math>n</math> jest postaci <math>n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>, to | |
− | + | ::<math>F(n) = F (p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s) =</math> | |
− | ::<math> | + | :::<math>\;\;\;\, = F (p^{\alpha_1}_1) \cdot \ldots \cdot F (p^{\alpha_s}_s) =</math> |
− | + | :::<math>\;\;\;\, = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math> | |
− | ::<math> | + | :::<math>\;\;\;\, = n</math> |
− | + | Niech <math>1 < d_1 < d_2 < \ldots < n</math> będą dzielnikami liczby <math>n</math>. Zauważmy, że kiedy <math>d</math> przebiega zbiór dzielników <math>\{ 1, d_1, d_2, \ldots, n \}</math>, to <math>e = {\small\frac{n}{d}}</math> przebiega wszystkie te liczby tylko w odwrotnej kolejności. Zatem | |
+ | ::<math>\sum_{d \mid n} \varphi (d) = \sum_{d \mid n} \varphi \left( {\small\frac{n}{d}} \right)</math> | ||
− | + | Co należało pokazać.<br/> | |
− | + | □ | |
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | + | <span id="H44" style="font-size: 110%; font-weight: bold;">Zadanie H44</span><br/> | |
+ | Niech <math>n \geqslant 2</math>. Pokazać, że suma liczb całkowitych dodatnich nie większych od <math>n</math> i względnie pierwszych z <math>n</math> jest równa <math>{\small\frac{1}{2}} n \varphi (n)</math>. | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | |
+ | Łatwo sprawdzamy, że wzór jest prawdziwy dla <math>n = 2</math> i odtąd będziemy przyjmowali, że <math>n \geqslant 3</math>. Zatem wartości <math>\varphi (n)</math> są liczbami parzystymi i niech <math>c = {\small\frac{1}{2}} \varphi (n)</math>. Zauważmy, że jeżeli liczba <math>a</math> jest względnie pierwsza z <math>n</math>, to liczba <math>n - a</math> jest również względnie pierwsza z <math>n</math>, bo <math>\gcd (a, n) = \gcd (n - a, n)</math>. Wypiszmy wszystkie liczby całkowite dodatnie nie większe od <math>n</math> i względnie pierwsze z <math>n</math> w kolejności rosnącej, a pod spodem w kolejności malejącej | ||
− | + | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: center; margin-right: auto;" | |
− | ::<math> | + | |- |
+ | | <math>1</math> || <math>a_2</math> || <math>…</math> || <math>a_c</math> || <math>n - a_c</math> || <math>…</math> || <math>n - a_2</math> || <math>n - 1</math> | ||
+ | |- | ||
+ | | <math>n - 1</math> || <math>n - a_2</math> || <math>…</math> || <math>n - a_c</math> || <math>a_c</math> || <math>…</math> || <math>a_2</math> || <math>1</math> | ||
+ | |} | ||
− | Ponieważ | + | Suma liczb w każdej kolumnie jest równa <math>n</math>. Ponieważ ilość liczb względnie pierwszych z <math>n</math> jest równa <math>\varphi (n)</math>, to podwojona suma liczb całkowitych nie większych od <math>n</math> i pierwszych względem <math>n</math> wynosi <math>n \varphi (n)</math>. Co należało pokazać.<br/> |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | + | <span id="H45" style="font-size: 110%; font-weight: bold;">Zadanie H45</span><br/> | |
+ | Pokazać, że dla liczb naturalnych nieparzystych <math>n \geqslant 5</math> prawdziwe jest oszacowanie <math>\varphi (n) > \pi (n)</math>. | ||
− | ::<math> | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} |
+ | '''1.''' Jeżeli <math>n \geqslant 5</math> jest liczbą pierwszą, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze mniejsze od <math>n</math> oraz liczby <math>1, 4</math>. Zatem | ||
− | ::<math>\ | + | ::<math>\varphi (n) \geqslant \pi (n) - 1 + 2 > \pi (n)</math>. |
− | + | '''2.''' Jeżeli <math>n = p^a</math>, gdzie <math>a \geqslant 2</math>, jest potęgą liczby pierwszej nieparzystej, to <math>n \geqslant 9</math> i liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczby <math>p</math>) oraz liczby <math>1, 4, 8</math>. Zatem | |
− | ::<math>\ | + | ::<math>\varphi (n) \geqslant \pi (n) - 1 + 3 > \pi (n)</math>. |
− | + | '''3.''' Jeżeli <math>n</math> ma więcej niż jeden dzielnik pierwszy nieparzysty, to <math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>, gdzie <math>s \geqslant 2</math>. Zauważmy, że | |
− | + | ::<math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s \geqslant q_1 \cdot \ldots \cdot q_s \geqslant 3 \cdot 5^{s - 1} > 2^{2 s - 1}</math> | |
− | + | Liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczb <math>q_1, \ldots, q_s</math>) oraz liczby <math>1, 2^2, 2^3, \ldots, 2^{2 s - 1}</math>. Zatem | |
− | + | ::<math>\varphi (n) \geqslant \pi (n) - s + 2 s - 1 = \pi (n) + s - 1 > \pi (n)</math> | |
− | + | Co należało pokazać.<br/> | |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 1390: | Linia 1356: | ||
− | <span style="font-size: 110%; font-weight: bold;"> | + | <span id="H46" style="font-size: 110%; font-weight: bold;">Zadanie H46</span><br/> |
− | + | Pokazać, że dla liczb naturalnych <math>n \geqslant 91</math> prawdziwe jest oszacowanie <math>\varphi (n) > \pi (n)</math>. | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show= | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} |
− | < | + | Ponieważ <math>p_{2 s} > 1</math> i <math>p_{2 s} \geqslant p_{s + 1}</math>, to z zadania A40 natychmiast wynika nierówność |
− | |||
− | ::<math> | + | ::<math>p_1 p_2 \cdot \ldots \cdot p_s > p_{s + 1} p_{2 s}</math> |
− | + | która jest prawdziwa dla <math>n \geqslant 4</math>. | |
− | + | Pokażemy najpierw, że dla każdej liczby naturalnej mającej nie mniej niż cztery dzielniki pierwsze nierówność <math>\varphi (n) > \pi (n)</math> jest zawsze prawdziwa. | |
− | |||
− | |||
− | |||
− | + | Przez <math>p_1, p_2, \ldots, p_k, \ldots</math> oznaczymy kolejne liczby pierwsze. Niech <math>n \geqslant 2</math> będzie liczbą naturalną i <math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>, gdzie <math>q_i</math> oznaczają dowolne (nie muszą być kolejne) liczby pierwsze. | |
− | + | Wśród kolejnych <math>2 s</math> liczb pierwszych znajduje się przynajmniej <math>s</math> liczb pierwszych '''różnych''' od każdej z liczb <math>q_1, \ldots, q_s</math>. Jeśli oznaczymy te liczby (w rosnącej kolejności) przez <math>r_1, \ldots, r_s</math>, to łatwo zauważymy, że prawdziwe są dla nich następujące oszacowania | |
− | + | :* dla najmniejszej liczby <math>r_1 \leqslant p_{s + 1}</math> | |
− | + | :* dla wszystkich liczb <math>r_j \leqslant p_{2 s}</math> dla <math>j = 1, \ldots, s</math>. | |
− | + | Korzystając z wypisanej na początku dowodu nierówności, dla <math>s \geqslant 4</math> mamy | |
+ | ::<math>n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s \geqslant q_1 \cdot \ldots \cdot q_s \geqslant p_1 \cdot \ldots \cdot p_s > p_{s + 1} p_{2 s} \geqslant r_1 \cdot r_j</math> | ||
− | < | + | gdzie <math>j = 1, \ldots, s</math>. |
− | |||
− | + | Wynika stąd, że jeśli <math>s \geqslant 4</math>, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczb pierwszych <math>q_1, \ldots, q_s</math>) oraz liczby <math>1</math> i <math>r_1 r_j</math>, gdzie <math>j = 1, \ldots, s</math>. Zatem | |
− | + | ::<math>\varphi (n) \geqslant \pi (n) - s + s + 1> \pi (n)</math> | |
− | + | Co mieliśmy pokazać. | |
− | |||
− | + | Uwzględniając rezultat pokazany w zadaniu [[#H45|H45]], pozostaje sprawdzić przypadki gdy <math>n = 2^a</math>, <math>n = 2^a p^b</math>, <math>n = 2^a p^b q^c</math>, gdzie <math>a, b, c \in \mathbb{Z}_+</math>. | |
− | + | '''1.''' Niech <math>n = 2^a</math>. Jeśli <math>n \geqslant 16</math>, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczby <math>2</math>) oraz liczby <math>1, 9, 15</math>. Zatem | |
− | + | ::<math>\varphi (n) \geqslant \pi (n) - 1 + 3 > \pi (n)</math> | |
− | + | '''2.''' Niech <math>n = 2^a p^b</math>, zaś <math>r</math> będzie najmniejszą liczbą pierwszą nieparzystą różną od <math>p</math>. Oczywiście <math>r \in \{ 3, 5 \}</math> i jeśli tylko <math>n > 5^3 = 125</math>, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczb pierwszych <math>2</math> i <math>p</math>) oraz liczby <math>1, r^2, r^3</math>. Zatem | |
+ | ::<math>\varphi (n) \geqslant \pi (n) - 2 + 3 > \pi (n)</math> | ||
− | + | '''3.''' Niech <math>n = 2^a p^b q^c</math>, zaś <math>r</math> będzie najmniejszą liczbą pierwszą nieparzystą różną od <math>p</math> oraz różną od <math>q</math>. Oczywiście <math>r \in \{ 3, 5, 7 \}</math> i jeśli <math>n > 7^4 = 2401</math>, to liczbami pierwszymi względem <math>n</math> są wszystkie liczby pierwsze nie większe od <math>n</math> (oprócz liczb pierwszych <math>2</math>, <math>p</math> i <math>q</math>) oraz liczby <math>1, r^2, r^3, r^4</math>. Zatem | |
− | ::<math> | + | ::<math>\varphi (n) \geqslant \pi (n) - 3 + 4 > \pi (n)</math> |
− | + | Zbierając: pozostaje sprawdzić bezpośrednio przypadki, gdy <math>n</math> jest liczbą parzystą i <math>n \leqslant 2401</math>. W GP/PARI wystarczy napisać polecenie | |
− | :: | + | <span style="font-size: 90%; color:black;">for(n = 1, 2500, if( eulerphi(n) <= primepi(n), print(n) ))</span> |
− | + | Nierówność <math>\varphi (n) > \pi (n)</math> nie jest prawdziwa dla <math>n \in \{ 2, 3, 4, 6, 8, 10, 12, 14, 18, 20, 24, 30, 42, 60, 90 \}</math>. Co kończy dowód.<br/> | |
− | |||
− | |||
− | |||
− | |||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 1455: | Linia 1413: | ||
− | <span style="font-size: 110%; font-weight: bold;"> | + | <span id="H47" style="font-size: 110%; font-weight: bold;">Zadanie H47</span><br/> |
− | + | Pokazać, że <math>\varphi (n) = 2^a</math> wtedy i tylko wtedy, gdy <math>n = 2^b q_1 \cdot \ldots \cdot q_s</math>, gdzie <math>q_1, \ldots, q_s</math> są liczbami pierwszymi Fermata: <math>3, 5, 17, 257, 65537</math>. | |
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
+ | W przypadku, gdy <math>2 \mid n</math>, łatwo zauważamy, że liczba <math>2</math> może występować w dowolnej potędze, bo <math>\varphi (2^b) = 2^{b - 1}</math>. | ||
+ | |||
+ | W przypadku, gdy <math>p \mid n</math>, gdzie <math>p</math> jest liczbą pierwszą nieparzystą, mamy <math>\varphi (p^k) = (p - 1) p^{k - 1}</math> i równie łatwo zauważmy, że musi być <math>k = 1</math>, a liczba <math>p - 1</math> musi być potęgą liczby <math>2</math>. Zatem liczba pierwsza <math>p</math> musi być postaci <math>p = 2^t + 1</math>, co jest możliwe tylko wtedy, gdy <math>t</math> jest potęgą liczby <math>2</math> (zobacz [[#H48|H48]]), czyli <math>p</math> musi być liczbą pierwszą Fermata. Co należało pokazać.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
+ | == Uzupełnienie == | ||
− | + | <span id="H48" style="font-size: 110%; font-weight: bold;">Twierdzenie H48</span><br/> | |
+ | Niech <math>a, n \in \mathbb{Z}_+</math> i <math>a \geqslant 2</math>. Jeżeli liczba <math>a^n + 1</math> jest liczbą pierwszą, to <math>a</math> jest liczbą parzystą i <math>n = 2^m</math>. | ||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
+ | Gdyby liczba <math>a</math> była nieparzysta, to liczba <math>a^n + 1 \geqslant 4</math> byłaby parzysta i nie mogłaby być liczbą pierwszą. | ||
+ | Niech wykładnik <math>n = x y</math> będzie liczbą złożoną, a <math>x</math> będzie liczbą nieparzystą. Wtedy | ||
− | + | ::<math>a^n + 1 = (a^y)^x + 1</math> | |
− | + | Oznaczając <math>b = a^y</math> oraz <math>x = 2 k + 1</math>, otrzymujemy | |
− | + | ::<math>a^n + 1 = (a^y)^x + 1 = b^x + 1 = b^{2 k + 1} + 1 = (b + 1) \cdot (1 - b + b^2 - b^3 + \ldots + b^{2 k - 2} - b^{2 k - 1} + b^{2 k})</math> | |
− | + | Zatem w takim przypadku <math>a^n + 1</math> jest liczbą złożoną. Wynika stąd, że wykładnik <math>n</math> nie może zawierać czynników nieparzystych, czyli musi być <math>n = 2^m</math>. Co należało pokazać.<br/> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | <br/> | ||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 1645: | Linia 1464: | ||
<references> | <references> | ||
− | <ref name=" | + | <ref name="GCD1">Wikipedia, ''Największy wspólny dzielnik'', ([https://pl.wikipedia.org/wiki/Najwi%C4%99kszy_wsp%C3%B3lny_dzielnik Wiki-pl]), ([https://en.wikipedia.org/wiki/Greatest_common_divisor Wiki-en])</ref> |
− | <ref name=" | + | <ref name="cardinality1">Wikipedia, ''Moc zbioru'', ([https://pl.wikipedia.org/wiki/Moc_zbioru Wiki-pl]), ([https://en.wikipedia.org/wiki/Cardinality Wiki-en])</ref> |
− | <ref name=" | + | <ref name="sumazbiorow">Wikipedia, ''Zasada włączeń i wyłączeń'', ([https://pl.wikipedia.org/wiki/Zasada_w%C5%82%C4%85cze%C5%84_i_wy%C5%82%C4%85cze%C5%84 Wiki-pl]), ([https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle Wiki-en])</ref> |
− | <ref name=" | + | <ref name="Euler1">Wikipedia, ''Funkcja φ'', ([https://pl.wikipedia.org/wiki/Funkcja_%CF%86 Wiki-pl]), ([https://en.wikipedia.org/wiki/Euler%27s_totient_function Wiki-en])</ref> |
− | + | </references> | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Wersja z 13:06, 19 lut 2024
Największy wspólny dzielnik
Definicja H1
Niech będą dane dwie liczby całkowite [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] niebędące jednocześnie zerami. Największym wspólnym dzielnikiem[1] liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] będziemy nazywali liczbę całkowitą [math]\displaystyle{ D }[/math] taką, że
- [math]\displaystyle{ D \mid a \quad \text{i} \quad D \mid b }[/math]
- [math]\displaystyle{ \,\, d \mid a \quad \text{i} \quad \; d \mid b \qquad \Longrightarrow \qquad d \leqslant D }[/math]
gdzie [math]\displaystyle{ d }[/math] jest dowolną liczbą całkowitą.
Uwaga H2
Tak zdefiniowaną liczbę [math]\displaystyle{ D }[/math] będziemy oznaczali przez [math]\displaystyle{ \gcd (a, b) }[/math]. Ponieważ [math]\displaystyle{ 1 \mid a \; }[/math] i [math]\displaystyle{ \; 1 \mid b }[/math], to z definicji wynika natychmiast, że [math]\displaystyle{ \gcd (a, b) \geqslant 1 }[/math].
Zadanie H3
Pokazać, że
- [math]\displaystyle{ d \mid \gcd (a, b) \qquad \Longleftrightarrow \qquad d \mid a \quad \text{i} \quad d \mid b }[/math]
[math]\displaystyle{ \Large{\Longrightarrow} }[/math]
Z założenia [math]\displaystyle{ d \mid \gcd (a, b) }[/math]. Z definicji największego wspólnego dzielnika [math]\displaystyle{ \gcd (a, b) \mid a }[/math], zatem [math]\displaystyle{ d \mid a }[/math]. Analogicznie pokazujemy, że [math]\displaystyle{ d \mid b }[/math].
[math]\displaystyle{ \Large{\Longleftarrow} }[/math]
Z założenia [math]\displaystyle{ a = r d }[/math], [math]\displaystyle{ b = s d }[/math]. Z lematu Bézouta (zobacz C73) istnieją takie liczby całkowite [math]\displaystyle{ x, y }[/math], że
- [math]\displaystyle{ \gcd (a, b) = a x + b y = r d x + s d y = d (r x + s y) }[/math]
Zatem [math]\displaystyle{ d \mid \gcd (a, b) }[/math].
□
Twierdzenie H4
Jeżeli liczby całkowite [math]\displaystyle{ a, b }[/math] nie są jednocześnie równe zero i [math]\displaystyle{ \gcd (a, b) = a x + b y }[/math], to [math]\displaystyle{ \gcd (x, y) = 1 }[/math].
Z lematu Bézouta (zobacz C73) wiemy, że liczby całkowite [math]\displaystyle{ x, y }[/math] zawsze istnieją. Niech [math]\displaystyle{ \gcd (a, b) = d \gt 0 }[/math], zatem [math]\displaystyle{ a = d k }[/math] i [math]\displaystyle{ b = d m }[/math], czyli
- [math]\displaystyle{ (d k) x + (d m) y = d }[/math]
Co oznacza, że [math]\displaystyle{ k x + m y = 1 }[/math], ale [math]\displaystyle{ \gcd (x, y) }[/math] jest dzielnikiem [math]\displaystyle{ k x + m y }[/math] (bo jest dzielnikiem [math]\displaystyle{ x }[/math] i [math]\displaystyle{ y }[/math]), zatem [math]\displaystyle{ \gcd (x, y) \mid 1 }[/math], czyli [math]\displaystyle{ \gcd (x, y) = 1 }[/math]. Co należało pokazać.
□
Twierdzenie H5
Niech [math]\displaystyle{ a, b, k \in \mathbb{Z} }[/math]. Prawdziwy jest wzór
- [math]\displaystyle{ \gcd (a + k b, b) = \gcd (a, b) }[/math]
Niech [math]\displaystyle{ d_1 = \gcd (a + k b, b) \; }[/math] i [math]\displaystyle{ \; d_2 = \gcd (a, b) }[/math].
Z definicji [math]\displaystyle{ d_1 \mid (a + k b) \; }[/math] i [math]\displaystyle{ \; d_1 \mid b }[/math], zatem [math]\displaystyle{ a + k b = x d_1 \; }[/math] i [math]\displaystyle{ \; b = y d_1 }[/math], czyli [math]\displaystyle{ a + k x d_1 = x d_1 }[/math], skąd natychmiast wynika, że [math]\displaystyle{ d_1 \mid a }[/math]. Ponieważ [math]\displaystyle{ d_1 \mid b }[/math], to [math]\displaystyle{ d_1 \mid d_2 }[/math] (zobacz H3).
Z definicji [math]\displaystyle{ d_2 \mid a \; }[/math] i [math]\displaystyle{ \; d_2 \mid b }[/math], zatem [math]\displaystyle{ d_2 \mid (a + k b) \; }[/math] i [math]\displaystyle{ \; d_2 \mid b }[/math], czyli [math]\displaystyle{ d_2 \mid d_1 }[/math].
Ponieważ [math]\displaystyle{ d_1 \mid d_2 \; }[/math] i [math]\displaystyle{ \; d_2 \mid d_1 }[/math], to [math]\displaystyle{ | d_1 | = | d_2 | }[/math]. Co kończy dowód.
□
Twierdzenie H6
Niech [math]\displaystyle{ a, b, m \in \mathbb{Z} }[/math]. Prawdziwa jest następująca równoważność
- [math]\displaystyle{ \gcd (a, m) = 1 \quad \text{i} \quad \gcd (b, m) = 1 \quad \qquad \Longleftrightarrow \quad \qquad \gcd (a b, m) = 1 }[/math]
[math]\displaystyle{ \Large{\Longrightarrow} }[/math]
Niech [math]\displaystyle{ \gcd (a b, m) = d }[/math]. Z definicji [math]\displaystyle{ d \mid a b }[/math] i [math]\displaystyle{ d \mid m }[/math]. Gdyby było [math]\displaystyle{ d \gt 1 }[/math], to istniałaby liczba pierwsza [math]\displaystyle{ p }[/math] taka, że [math]\displaystyle{ p \mid d }[/math] i mielibyśmy [math]\displaystyle{ p \mid a b }[/math] i [math]\displaystyle{ p \mid m }[/math]. Jeżeli [math]\displaystyle{ p \mid a b }[/math], to [math]\displaystyle{ p \mid a }[/math] lub [math]\displaystyle{ p \mid b }[/math] (zobacz C74). W przypadku, gdy [math]\displaystyle{ p \mid a }[/math] dostajemy [math]\displaystyle{ \gcd (a, m) \geqslant p \gt 1 }[/math], wbrew założeniu, że [math]\displaystyle{ \gcd (a, m) = 1 }[/math]. Analogicznie pokazujemy sprzeczność, gdy [math]\displaystyle{ p \mid b }[/math].
[math]\displaystyle{ \Large{\Longleftarrow} }[/math]
Niech [math]\displaystyle{ \gcd (a, m) = d }[/math]. Z definicji [math]\displaystyle{ d \mid a }[/math] i [math]\displaystyle{ d \mid m }[/math], zatem również [math]\displaystyle{ d \mid a b }[/math] i [math]\displaystyle{ d \mid m }[/math]. Mamy stąd
- [math]\displaystyle{ 1 = \gcd (a b, m) \geqslant d \geqslant 1 }[/math]
Czyli musi być [math]\displaystyle{ d = 1 }[/math]. Analogicznie pokazujemy, że [math]\displaystyle{ \gcd (b, m) = 1 }[/math].
□
Twierdzenie H7
Dla [math]\displaystyle{ a, b, m \in \mathbb{Z} }[/math] jest
- [math]\displaystyle{ \gcd (a b, m) \mid \gcd (a, m) \cdot \gcd (b, m) }[/math]
Wprowadźmy oznaczenia
- [math]\displaystyle{ r = \gcd (a b, m) }[/math]
- [math]\displaystyle{ s = \gcd (a, m) }[/math]
- [math]\displaystyle{ t = \gcd (b, m) }[/math]
Z lematu Bézouta (zobacz C73) istnieją takie liczby [math]\displaystyle{ x, y, X, Y }[/math], że
- [math]\displaystyle{ s = a x + m y }[/math]
- [math]\displaystyle{ t = b X + m Y }[/math]
Zatem
- [math]\displaystyle{ s t = (a x + m y) (b X + m Y) = a b x X + a m x Y + m b y X + m^2 y Y }[/math]
ale [math]\displaystyle{ r \mid a b }[/math] i [math]\displaystyle{ r \mid m }[/math], skąd otrzymujemy, że [math]\displaystyle{ r \mid s t }[/math]. Co należało pokazać.
□
Twierdzenie H8
Jeżeli liczby [math]\displaystyle{ a, b }[/math] są względnie pierwsze, to
- [math]\displaystyle{ \gcd (a b, m) = \gcd (a, m) \cdot \gcd (b, m) }[/math]
Wprowadźmy oznaczenia
- [math]\displaystyle{ r = \gcd (a b, m) }[/math]
- [math]\displaystyle{ s = \gcd (a, m) }[/math]
- [math]\displaystyle{ t = \gcd (b, m) }[/math]
Z założenia [math]\displaystyle{ \gcd (a, b) = 1 }[/math]. Ponieważ [math]\displaystyle{ s \mid a }[/math] oraz [math]\displaystyle{ t \mid b }[/math], to [math]\displaystyle{ \gcd (s, t) = 1 }[/math], zatem (zobacz C75)
- [math]\displaystyle{ s \mid a \qquad \,\, \text{i} \qquad t \mid b \qquad \qquad \;\, \Longrightarrow \qquad \qquad s t \mid a b }[/math]
- [math]\displaystyle{ s \mid m \qquad \text{i} \qquad t \mid m \qquad \qquad \Longrightarrow \qquad \qquad s t \mid m }[/math]
Wynika stąd, że [math]\displaystyle{ s t \mid \gcd (a b, m) }[/math], czyli [math]\displaystyle{ s t \mid r }[/math]. Z poprzedniego twierdzenia wiemy, że [math]\displaystyle{ r \mid s t }[/math], zatem [math]\displaystyle{ |r| = |s t| }[/math]. Co kończy dowód.
□
Twierdzenie H9
Jeżeli liczby [math]\displaystyle{ b, m }[/math] są względnie pierwsze, to
- [math]\displaystyle{ \gcd (a b, m) = \gcd (a, m) }[/math]
Wprowadźmy oznaczenia
- [math]\displaystyle{ r = \gcd (a b, m) }[/math]
- [math]\displaystyle{ s = \gcd (a, m) }[/math]
Z lematu Bézouta istnieją takie liczby [math]\displaystyle{ x, y }[/math], że
- [math]\displaystyle{ r = a b x + m y }[/math]
Ale [math]\displaystyle{ s \mid a \; }[/math] i [math]\displaystyle{ \; s \mid m }[/math], zatem [math]\displaystyle{ s \mid r }[/math].
Z założenia [math]\displaystyle{ \gcd (b, m) = 1 }[/math], zatem z twierdzenia H7 wynika natychmiast, że [math]\displaystyle{ r \mid s }[/math]. Ponieważ [math]\displaystyle{ s \mid r \; }[/math] i [math]\displaystyle{ \; r \mid s }[/math], to [math]\displaystyle{ | r | = | s | }[/math]. Co należało pokazać.
□
Twierdzenie H10
Jeżeli liczby [math]\displaystyle{ a, b }[/math] nie są jednocześnie równe zero i [math]\displaystyle{ m \neq 0 }[/math], to
- [math]\displaystyle{ \gcd (a m, b m) = | m | \cdot \gcd (a, b) }[/math]
Oznaczmy [math]\displaystyle{ d = \gcd (a, b) \; }[/math] i [math]\displaystyle{ \; D = \gcd (a m, b m) }[/math]. Pokażemy, że [math]\displaystyle{ d m \mid D }[/math].
- [math]\displaystyle{ \begin{array}{llll} d = \gcd (a, b) & \qquad \Longrightarrow \qquad & d \mid a \quad \text{i} \quad d \mid b & \text{(zobacz H3)} \\ & & & \\ & \qquad \Longrightarrow \qquad & d m \mid a m \quad \text{i} \quad d m \mid b m & \\ & & & \\ & \qquad \Longrightarrow \qquad & d m \mid \gcd (a m, b m) & \text{(zobacz H3)} \\ & & & \\ & \qquad \Longrightarrow \qquad & d m \mid D & \\ \end{array} }[/math]
Pokażemy, że [math]\displaystyle{ D \mid d m }[/math].
- [math]\displaystyle{ \begin{array}{llll} d = \gcd (a, b) & \qquad \Longrightarrow \qquad & d = a x + b y & \text{(lemat Bézouta C73)} \\ & & & \\ & \qquad \Longrightarrow \qquad & d m = a m x + b m y & \\ & & & \\ & \qquad \Longrightarrow \qquad & D \mid d m & \\ \end{array} }[/math]
Ostatnia implikacja korzysta z tego, że [math]\displaystyle{ D \mid a m \; }[/math] i [math]\displaystyle{ \; D \mid b m }[/math] (zobacz H3). Ponieważ [math]\displaystyle{ d m \mid D \; }[/math] i [math]\displaystyle{ \; D \mid d m }[/math], to [math]\displaystyle{ | D | = | d m | }[/math]. Co należało pokazać.
□
Zadanie H11
Pokazać, że [math]\displaystyle{ a \mid b }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ a \mid \gcd (a, b) }[/math].
[math]\displaystyle{ \Large{\Longrightarrow} }[/math]
Zakładając, że [math]\displaystyle{ a \mid b }[/math], dostajemy
- [math]\displaystyle{ \begin{array}{llll} a \mid b & \qquad \Longrightarrow \qquad & b = k a & \\ & & & \\ & \qquad \Longrightarrow \qquad & \gcd (a, b) = \gcd (a, k a) = | a | \cdot \gcd (1, k) = | a | & \qquad \text{(zobacz H10)} \\ & & & \\ & \qquad \Longrightarrow \qquad & a \mid \gcd (a, b) & \\ \end{array} }[/math]
[math]\displaystyle{ \Large{\Longleftarrow} }[/math]
Jeżeli [math]\displaystyle{ a \mid \gcd (a, b) }[/math], to [math]\displaystyle{ a \mid b }[/math] (zobacz H3). Co należało pokazać.
□
Zadanie H12
Niech [math]\displaystyle{ \gcd (a, d) = 1 }[/math]. Pokazać, że [math]\displaystyle{ d \nmid a b }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ d \nmid b }[/math].
Korzystając z rezultatu pokazanego w zadaniu H11, dostajemy
- [math]\displaystyle{ \begin{array}{llll} d \nmid a b & \qquad \Longleftrightarrow \qquad & d \nmid \gcd (d, a b) & \\ & & & \\ & \qquad \Longleftrightarrow \qquad & d \nmid \gcd (d, b) & \text{(zobacz H9)} \\ & & & \\ & \qquad \Longleftrightarrow \qquad & d \nmid b & \\ \end{array} }[/math]
Co należało pokazać.
□
Twierdzenie H13
Jeżeli dodatnie liczby [math]\displaystyle{ a, b }[/math] są względnie pierwsze, to każdy dzielnik [math]\displaystyle{ d }[/math] iloczynu [math]\displaystyle{ a b }[/math] można przedstawić jednoznacznie w postaci [math]\displaystyle{ d = d_1 d_2 }[/math], gdzie [math]\displaystyle{ d_1 \mid a , }[/math] [math]\displaystyle{ \; d_2 \mid b \; }[/math] [math]\displaystyle{ \text{i} \; \gcd (d_1, d_2) = 1 }[/math].
Niech [math]\displaystyle{ d_1 = \gcd (d, a) \; }[/math] i [math]\displaystyle{ \; d_2 = \gcd (d, b) }[/math]. Z twierdzenia H8 mamy
- [math]\displaystyle{ d_1 d_2 = \gcd (d, a) \cdot \gcd (d, b) = \gcd (d, a b) = d }[/math]
Bo z założenia [math]\displaystyle{ d \mid a b }[/math]. Z definicji największego wspólnego dzielnika i zadania H3 dostajemy
- [math]\displaystyle{ \gcd (d_1, d_2) = e \qquad \Longrightarrow \qquad e \mid d_1 \quad \text{i} \quad e \mid d_2 }[/math]
- [math]\displaystyle{ \, \Longrightarrow \qquad e \mid \gcd (d, a) \quad \text{i} \quad e \mid \gcd (d, b) }[/math]
- [math]\displaystyle{ \, \Longrightarrow \qquad e \mid a \quad \text{i} \quad e \mid b }[/math]
- [math]\displaystyle{ \, \Longrightarrow \qquad e \mid \gcd (a, b) }[/math]
- [math]\displaystyle{ \, \Longrightarrow \qquad \gcd (a, b) \geqslant e }[/math]
Gdyby było [math]\displaystyle{ \gcd (d_1, d_2) = e \gt 1 }[/math], to mielibyśmy [math]\displaystyle{ \gcd (a, b) \geqslant e \gt 1 }[/math]. Wbrew założeniu, że [math]\displaystyle{ \gcd (a, b) = 1 }[/math]. Co kończy dowód.
□
Twierdzenie H14
Jeżeli [math]\displaystyle{ a, m, n \in \mathbb{Z}_+ }[/math], to
- [math]\displaystyle{ \gcd (a^m - 1, a^n - 1) = a^{\gcd (m, n)} - 1 }[/math]
Pokażemy najpierw, że jeżeli [math]\displaystyle{ d }[/math] jest dzielnikiem lewej strony dowodzonej równości, to jest również dzielnikiem prawej strony i odwrotnie.
[math]\displaystyle{ \Large{\Longrightarrow} }[/math]
Z założenia [math]\displaystyle{ d }[/math] jest dzielnikiem [math]\displaystyle{ \gcd (a^m - 1, a^n - 1) }[/math], czyli [math]\displaystyle{ d \mid (a^m - 1) \; }[/math] i [math]\displaystyle{ \; d \mid (a^n - 1) }[/math], co możemy zapisać w postaci
- [math]\displaystyle{ a^m \equiv 1 \!\! \pmod{d} \quad \qquad \text{oraz} \quad \qquad a^n \equiv 1 \!\! \pmod{d} }[/math]
Z lematu Bézouta (zobacz C73) wiemy, że istnieją takie liczby [math]\displaystyle{ x, y }[/math], że [math]\displaystyle{ \gcd (m, n) = m x + n y }[/math]. Łatwo znajdujemy, że
- [math]\displaystyle{ a^{\gcd (m, n)} \equiv a^{m x + n y} \equiv (a^m)^x \cdot (a^n)^y \equiv 1^x \cdot 1^y \equiv 1 \!\! \pmod{d} }[/math]
Czyli [math]\displaystyle{ d \, \biggr\rvert \left( a^{\gcd (m, n)} - 1 \right) }[/math].
[math]\displaystyle{ \Large{\Longleftarrow} }[/math]
Z założenia [math]\displaystyle{ d \, \biggr\rvert \left( a^{\gcd (m, n)} - 1 \right) }[/math], czyli
- [math]\displaystyle{ a^{\gcd (m, n)} \equiv 1 \!\! \pmod{d} }[/math]
Zatem
- [math]\displaystyle{ a^m \equiv \left[ a^{\gcd (m, n)} \right]^{\tfrac{m}{\gcd (m, n)}} \equiv 1 \!\! \pmod{d} }[/math]
Podobnie otrzymujemy
- [math]\displaystyle{ a^n \equiv 1 \!\! \pmod{d} }[/math]
Zatem [math]\displaystyle{ d }[/math] dzieli [math]\displaystyle{ a^m - 1 \; }[/math] i [math]\displaystyle{ \; a^n - 1 }[/math], czyli
- [math]\displaystyle{ d \mid \gcd (a^m - 1, a^n - 1) }[/math]
W szczególności wynika stąd, że
- [math]\displaystyle{ \gcd (a^m - 1, a^n - 1) \, \biggr\rvert \left( a^{\gcd (m, n)} - 1 \right) }[/math]
- [math]\displaystyle{ \left( a^{\gcd (m, n)} - 1 \right) \, \biggr\rvert \, \gcd (a^m - 1, a^n - 1) }[/math]
Czyli [math]\displaystyle{ \left| \gcd (a^m - 1, a^n - 1) \right| = \left| a^{\gcd (m, n)} - 1 \right| }[/math]. Co kończy dowód.
□
Uwaga H15
W dowodzie twierdzenia H14 pominęliśmy milczeniem fakt, że jedna z liczb [math]\displaystyle{ x, y }[/math] może być (i często jest) ujemna. Choć rezultat jest prawidłowy, to nie wiemy, co oznacza zapis
- [math]\displaystyle{ a^{- 1000} \equiv 1^{- 10} \equiv 1 \!\! \pmod{d} }[/math]
Omówimy ten problem w następnej sekcji. Zauważmy, wyprzedzając materiał, że z kongruencji
- [math]\displaystyle{ a^m \equiv 1 \!\! \pmod{d} \quad \qquad \text{oraz} \quad \qquad a^n \equiv 1 \!\! \pmod{d} }[/math]
wynika, że [math]\displaystyle{ \gcd (a, d) = 1 }[/math] i liczba [math]\displaystyle{ a }[/math] ma element odwrotny modulo [math]\displaystyle{ d }[/math].
Element odwrotny modulo [math]\displaystyle{ m }[/math]
Twierdzenie H16
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math]. Dla liczby [math]\displaystyle{ a \in \mathbb{Z} }[/math] istnieje taka liczba [math]\displaystyle{ x }[/math], że
- [math]\displaystyle{ a x \equiv 1 \!\! \pmod{m} }[/math]
wtedy i tylko wtedy, gdy [math]\displaystyle{ \gcd (a, m) = 1 }[/math].
[math]\displaystyle{ \Large{\Longrightarrow} }[/math]
Z założenia istnieje taka liczba [math]\displaystyle{ x }[/math], że
- [math]\displaystyle{ a x \equiv 1 \!\! \pmod{m} }[/math]
Zatem dla pewnego [math]\displaystyle{ k \in \mathbb{Z} }[/math] jest
- [math]\displaystyle{ a x = 1 + k m }[/math]
Czyli [math]\displaystyle{ a x - k m = 1 }[/math]. Wynika stąd, że [math]\displaystyle{ \gcd (a, m) }[/math] dzieli [math]\displaystyle{ 1 }[/math], co oznacza, że [math]\displaystyle{ \gcd (a, m) = 1 }[/math].
[math]\displaystyle{ \Large{\Longleftarrow} }[/math]
Z założenia [math]\displaystyle{ \gcd (a, m) = 1 }[/math]. Z lematu Bézouta (zobacz C73) wynika, że istnieją takie liczby całkowite [math]\displaystyle{ x, y }[/math], że
- [math]\displaystyle{ a x + m y = 1 }[/math]
Zatem modulo [math]\displaystyle{ m }[/math] dostajemy
- [math]\displaystyle{ a x \equiv 1 \!\! \pmod{m} }[/math]
Co kończy dowód.
□
Definicja H17
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math]. Liczbę [math]\displaystyle{ x }[/math] taką, że
- [math]\displaystyle{ a \cdot x \equiv 1 \!\! \pmod{m} }[/math]
będziemy nazywali elementem odwrotnym liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] i oznaczali jako [math]\displaystyle{ a^{- 1} }[/math].
Uwaga H18
Oznaczenie elementu odwrotnego ma naturalne uzasadnienie. Zauważmy, że jeżeli [math]\displaystyle{ b \mid a }[/math] oraz [math]\displaystyle{ b }[/math] ma element odwrotny modulo [math]\displaystyle{ m }[/math], to prawdziwa jest kongruencja
- [math]\displaystyle{ {\small\frac{a}{b}} \equiv a b^{- 1} \!\! \pmod{m} }[/math]
Istotnie
- [math]\displaystyle{ {\small\frac{a}{b}} = {\small\frac{a}{b}} \cdot 1 \equiv {\small\frac{a}{b}} \cdot b b^{- 1} \equiv a b^{- 1} \!\! \pmod{m} }[/math]
W PARI/GP odwrotność liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] znajdujemy, wpisując Mod(a, m)^(-1)
.
Twierdzenie H19
Niech [math]\displaystyle{ a, k \in \mathbb{Z} }[/math], [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math]. Poniższa tabelka przedstawia elementy odwrotne do elementu [math]\displaystyle{ a }[/math] w przypadku niektórych modułów [math]\displaystyle{ m }[/math]. W szczególności, jeżeli moduł [math]\displaystyle{ m }[/math] jest liczbą nieparzystą, to [math]\displaystyle{ 2^{- 1} \equiv {\small\frac{m + 1}{2}} \!\! \pmod{m} }[/math].
postać
modułu [math]\displaystyle{ \boldsymbol{m} }[/math]odwrotność
elementu [math]\displaystyle{ \boldsymbol{a} }[/math]uwagi [math]\displaystyle{ 1. }[/math] [math]\displaystyle{ m = 2 }[/math] [math]\displaystyle{ 1 }[/math] liczba [math]\displaystyle{ a }[/math]
jest liczbą
nieparzystą[math]\displaystyle{ 2. }[/math] [math]\displaystyle{ m = 4 }[/math] [math]\displaystyle{ R_4(a) }[/math] [math]\displaystyle{ 3. }[/math] [math]\displaystyle{ m = 8 }[/math] [math]\displaystyle{ R_8(a) }[/math] [math]\displaystyle{ 4. }[/math] [math]\displaystyle{ m = a k - 1 }[/math] [math]\displaystyle{ {\small\frac{m + 1}{a}} }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ 5. }[/math] [math]\displaystyle{ m = a k + 1 }[/math] [math]\displaystyle{ - {\small\frac{m - 1}{a}} }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ 6. }[/math] [math]\displaystyle{ m = a k - 2 }[/math] [math]\displaystyle{ {\small\frac{m + 1}{2}} \cdot {\small\frac{m + 2}{a}} }[/math] liczby [math]\displaystyle{ a , m }[/math]
są liczbami
nieparzystymi[math]\displaystyle{ 7. }[/math] [math]\displaystyle{ m = a k + 2 }[/math] [math]\displaystyle{ {\small\frac{m - 1}{2}} \cdot {\small\frac{m - 2}{2}} }[/math]
Punkty 1. - 3.
Ponieważ dla liczb nieparzystych jest
- [math]\displaystyle{ a^2 \equiv 1 \!\! \pmod{2} }[/math]
- [math]\displaystyle{ a^2 \equiv 1 \!\! \pmod{4} }[/math]
- [math]\displaystyle{ a^2 \equiv 1 \!\! \pmod{8} }[/math]
to liczba nieparzysta [math]\displaystyle{ a }[/math] jest swoją odwrotnością modulo [math]\displaystyle{ 2 }[/math], [math]\displaystyle{ 4 }[/math] i [math]\displaystyle{ 8 }[/math]. Ponieważ element odwrotny jest definiowany modulo, zatem możemy napisać
- [math]\displaystyle{ a^{- 1} \equiv R_2 (a) \!\! \pmod{2} }[/math]
- [math]\displaystyle{ a^{- 1} \equiv R_4 (a) \!\! \pmod{4} }[/math]
- [math]\displaystyle{ a^{- 1} \equiv R_8 (a) \!\! \pmod{8} }[/math]
W pierwszym przypadku wynik jest oczywisty, bo [math]\displaystyle{ R_2 (a) = 1 }[/math].
Punkt 4.
Zauważmy, że
- [math]\displaystyle{ \gcd (a, m) = \gcd (a, a k - 1) = \gcd (a, - 1) = 1 }[/math]
oraz [math]\displaystyle{ a \mid (m + 1) }[/math]. Zatem
- [math]\displaystyle{ a \cdot a^{- 1} = a \cdot {\small\frac{m + 1}{a}} = m + 1 \equiv 1 \!\! \pmod{m} }[/math]
Punkt 5.
Zauważmy, że
- [math]\displaystyle{ \gcd (a, m) = \gcd (a, a k + 1) = \gcd (a, 1) = 1 }[/math]
oraz [math]\displaystyle{ a \mid (m - 1) }[/math]. Zatem
- [math]\displaystyle{ a \cdot a^{- 1} = a \cdot \left[ - \left( {\small\frac{m - 1}{a}} \right) \right] = - m + 1 \equiv 1 \!\! \pmod{m} }[/math]
Punkt 6.
Ponieważ zakładamy, że [math]\displaystyle{ 2 \mid (m + 1) }[/math], to [math]\displaystyle{ m }[/math] musi być liczbą nieparzystą, czyli [math]\displaystyle{ a }[/math] też musi być liczbą nieparzystą. Zauważmy, że
- [math]\displaystyle{ \gcd (a, m) = \gcd (a, a k - 2) = \gcd (a, - 2) = 1 }[/math]
oraz [math]\displaystyle{ a \mid (m + 2) }[/math]. Zatem
- [math]\displaystyle{ a \cdot a^{- 1} = a \cdot \left( {\small\frac{m + 1}{2}} \cdot {\small\frac{m + 2}{a}} \right) = {\small\frac{m + 1}{2}} \cdot (m + 2) \equiv {\small\frac{m + 1}{2}} \cdot 2 \equiv m + 1 \equiv 1 \!\! \pmod{m} }[/math]
Podobnie pokazujemy punkt 7. Co kończy dowód.
□
Twierdzenie H20
Niech [math]\displaystyle{ a, b \in \mathbb{Z} }[/math], [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math] i liczba [math]\displaystyle{ a }[/math] ma element odwrotny modulo [math]\displaystyle{ m }[/math]. Jeżeli liczby [math]\displaystyle{ u_1, u_2, \ldots, u_r }[/math] są liczbami różnymi modulo [math]\displaystyle{ m }[/math], to liczby
- 1. [math]\displaystyle{ a u_1, a u_2, \ldots, a u_r }[/math]
- 2. [math]\displaystyle{ a u_1 + b, a u_2 + b, \ldots, a u_r + b }[/math]
są liczbami różnymi modulo [math]\displaystyle{ m }[/math]. Jeżeli ponadto liczby [math]\displaystyle{ u_1, u_2, \ldots, u_r }[/math] są względnie pierwsze z [math]\displaystyle{ m }[/math], to również liczby
- 3. [math]\displaystyle{ u^{- 1}_1, u^{- 1}_2, \ldots, u^{- 1}_r }[/math]
są liczbami różnymi modulo [math]\displaystyle{ m }[/math].
Punkt 1.
Przypuśćmy dla uzyskania sprzeczności, że istnieją takie różne wskaźniki [math]\displaystyle{ i, j }[/math], że
- [math]\displaystyle{ a u_i \equiv a u_j \!\! \pmod{m} }[/math]
Z założenia liczba [math]\displaystyle{ a }[/math] ma element odwrotny modulo [math]\displaystyle{ m }[/math], zatem mnożąc obie strony kongruencji przez [math]\displaystyle{ a^{- 1} }[/math], otrzymujemy
- [math]\displaystyle{ u_i \equiv u_j \!\! \pmod{m} }[/math]
dla [math]\displaystyle{ i \neq j }[/math], wbrew założeniu, że liczby [math]\displaystyle{ u_1, u_2, \ldots, u_r }[/math] są różne modulo [math]\displaystyle{ m }[/math]. Dowód punktu 2. jest analogiczny.
Punkt 3.
Przypuśćmy dla uzyskania sprzeczności, że istnieją takie różne wskaźniki [math]\displaystyle{ i, j }[/math], że
- [math]\displaystyle{ u^{- 1}_i \equiv u^{- 1}_j \!\! \pmod{m} }[/math]
- [math]\displaystyle{ u_j u^{- 1}_i \equiv 1 \!\! \pmod{m} }[/math]
- [math]\displaystyle{ u_j u^{- 1}_i u_i \equiv u_i \!\! \pmod{m} }[/math]
- [math]\displaystyle{ u_j \equiv u_i \!\! \pmod{m} }[/math]
Ponownie otrzymujemy [math]\displaystyle{ u_i \equiv u_j \!\! \pmod{m} }[/math] dla [math]\displaystyle{ i \neq j }[/math], wbrew założeniu, że liczby [math]\displaystyle{ u_1, u_2, \ldots, u_r }[/math] są różne modulo [math]\displaystyle{ m }[/math]. Co należało pokazać.
□
Zadanie H21
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą. Pokazać, że dla [math]\displaystyle{ k \in [0, p - 1] }[/math] prawdziwa jest kongruencja
- [math]\displaystyle{ \binom{p - 1}{k} \equiv (- 1)^k \pmod{p} }[/math]
Zauważmy, że modulo [math]\displaystyle{ p }[/math] mamy
- [math]\displaystyle{ \binom{p - 1}{k} = {\small\frac{(p - 1) !}{k! \cdot (p - 1 - k) !}} }[/math]
- [math]\displaystyle{ \;\;\;\; = {\small\frac{(p - 1) (p - 2) \cdot \ldots \cdot (p - k)}{k!}} }[/math]
- [math]\displaystyle{ \;\;\;\; \equiv (p - 1) (p - 2) \cdot \ldots \cdot (p - k) \cdot (k!)^{- 1} }[/math]
- [math]\displaystyle{ \;\;\;\; \equiv (- 1)^k \cdot k! \cdot (k!)^{- 1} }[/math]
- [math]\displaystyle{ \;\;\;\; \equiv (- 1)^k \pmod{p} }[/math]
Co należało pokazać.
□
Zadanie H22
Niech [math]\displaystyle{ A }[/math] i [math]\displaystyle{ B }[/math] będą zbiorami skończonymi. Pokazać, że jeżeli [math]\displaystyle{ A \subseteq B \;\; \text{i} \;\; | A | = | B | }[/math], to [math]\displaystyle{ \; A = B }[/math].
Pierwszy sposób
Z definicji zbiory [math]\displaystyle{ A }[/math] i [math]\displaystyle{ B }[/math] są równe wtedy i tylko wtedy, gdy jednocześnie spełnione są warunki
- [math]\displaystyle{ x \in A \qquad \Longrightarrow \qquad x \in B }[/math]
- [math]\displaystyle{ x \in B \qquad \Longrightarrow \qquad x \in A }[/math]
Z założenia [math]\displaystyle{ A \subseteq B }[/math], zatem warunek 1. jest spełniony. Przypuśćmy, że istnieje taki element [math]\displaystyle{ x }[/math], że [math]\displaystyle{ x \in B }[/math], ale [math]\displaystyle{ x \notin A }[/math]. Jeśli tak, to
- [math]\displaystyle{ | B | = | A | + 1 }[/math]
Co jest sprzeczne z założeniem, że [math]\displaystyle{ | A | = | B | }[/math].
Uwaga
Łatwo zauważyć, że wybierając z trzech warunków [math]\displaystyle{ A \subseteq B }[/math], [math]\displaystyle{ B \subseteq A }[/math] i [math]\displaystyle{ | A | = | B | }[/math] dowolne dwa, zawsze otrzymamy z nich trzeci. Oczywiście nie dotyczy to zbiorów nieskończonych. Przykładowo liczby parzyste stanowią podzbiór liczb całkowitych, liczb parzystych jest tyle samo, co liczb całkowitych[2], ale zbiór liczb całkowitych nie jest podzbiorem zbioru liczb parzystych.
Drugi sposób
Ponieważ zbiór [math]\displaystyle{ A }[/math] jest z założenia podzbiorem zbioru [math]\displaystyle{ B }[/math], to zbiór [math]\displaystyle{ B }[/math] można przedstawić w postaci sumy zbioru [math]\displaystyle{ A }[/math] i pewnego zbioru [math]\displaystyle{ C }[/math] takiego, że żaden element zbioru [math]\displaystyle{ C }[/math] nie jest elementem zbioru [math]\displaystyle{ A }[/math]. Zatem
- [math]\displaystyle{ B = A \cup C \qquad \text{i} \qquad A \cap C = \varnothing }[/math]
Ponieważ zbiory [math]\displaystyle{ A }[/math] i [math]\displaystyle{ C }[/math] są rozłączne, to wiemy, że
- [math]\displaystyle{ | A \cup C | = | A | + | C | }[/math]
Czyli
- [math]\displaystyle{ | B | = | A \cup C | = | A | + | C | }[/math]
Skąd wynika, że [math]\displaystyle{ | C | = 0 }[/math], zatem zbiór [math]\displaystyle{ C }[/math] jest zbiorem pustym i otrzymujemy natychmiast [math]\displaystyle{ B = A }[/math]. Co należało pokazać.
Uwaga (przypadek zbiorów skończonych)
Najczęściej prawdziwe jest jedynie oszacowanie [math]\displaystyle{ | A \cup C | \leqslant | A | + | C | }[/math], bo niektóre elementy mogą zostać policzone dwa razy. Elementy liczone dwukrotnie to te, które należą do iloczynu zbiorów [math]\displaystyle{ | A | }[/math] i [math]\displaystyle{ | C | }[/math], zatem od sumy [math]\displaystyle{ | A | + | C | }[/math] musimy odjąć liczbę elementów iloczynu zbiorów [math]\displaystyle{ | A | }[/math] i [math]\displaystyle{ | C | }[/math]. Co daje ogólny wzór[3]
- [math]\displaystyle{ | A \cup C | = | A | + | C | - | A \cap C | }[/math]
- [math]\displaystyle{ | A \cup C | = | A | + | C | - | A \cap C | }[/math]
□
Definicja H23
Niech elementy każdego ze zbiorów [math]\displaystyle{ A = \{ a_1, a_2, \ldots, a_r \} }[/math] oraz [math]\displaystyle{ B = \{ b_1, b_2, \ldots, b_r \} }[/math] będą różne modulo [math]\displaystyle{ m }[/math]. Powiemy, że zbiory [math]\displaystyle{ A, B }[/math] są równe modulo [math]\displaystyle{ m }[/math], jeżeli dla każdego [math]\displaystyle{ k = 1, \ldots, r }[/math] istnieje takie [math]\displaystyle{ j = 1, \ldots, r }[/math], że prawdziwa jest kongruencja [math]\displaystyle{ a_k \equiv b_j \!\! \pmod{m} }[/math].
Twierdzenie H24
Niech elementy każdego ze zbiorów [math]\displaystyle{ A = \{ a_1, a_2, \ldots, a_r \} }[/math] oraz [math]\displaystyle{ B = \{ b_1, b_2, \ldots, b_r \} }[/math] będą różne modulo [math]\displaystyle{ m }[/math]. Zbiory [math]\displaystyle{ A, B }[/math] są równe modulo [math]\displaystyle{ m }[/math] wtedy i tylko wtedy, gdy zbiory [math]\displaystyle{ A' = \{ R_m (a_1), R_m (a_2), \ldots, R_m (a_r) \} }[/math] i [math]\displaystyle{ B' = \{ R_m (b_1), R_m (b_2), \ldots, R_m (b_r) \} }[/math] są równe.
[math]\displaystyle{ \Large{\Longrightarrow} }[/math]
Ponieważ elementy każdego ze zbiorów [math]\displaystyle{ A, B }[/math] są różne modulo [math]\displaystyle{ m }[/math], to elementy zbiorów [math]\displaystyle{ A' }[/math] i [math]\displaystyle{ B' }[/math] są wszystkie różne. Czyli [math]\displaystyle{ | A' | = | B' | = r }[/math]. Ponieważ warunek
- [math]\displaystyle{ a_k \equiv b_j \!\! \pmod{m} }[/math]
oznacza, że reszty z dzielenia liczb [math]\displaystyle{ a_k }[/math] i [math]\displaystyle{ b_j }[/math] przez [math]\displaystyle{ m }[/math] są równe, to z założenia dla każdego [math]\displaystyle{ k = 1, \ldots, r }[/math] istnieje takie [math]\displaystyle{ j = 1, \ldots, r }[/math], że
- [math]\displaystyle{ R_m (a_k) = R_m (b_j) }[/math]
A to oznacza, że każdy element zbioru [math]\displaystyle{ A' }[/math] należy do zbioru [math]\displaystyle{ B' }[/math], czyli [math]\displaystyle{ A' \subseteq B' }[/math]. Wynika stąd, że [math]\displaystyle{ A' = B' }[/math] (zobacz H22). Co należało pokazać.
[math]\displaystyle{ \Large{\Longleftarrow} }[/math]
Ponieważ zbiory [math]\displaystyle{ A', B' }[/math] są równe, to zbiór [math]\displaystyle{ A' }[/math] jest podzbiorem zbioru [math]\displaystyle{ B' }[/math], czyli dla każdego elementu [math]\displaystyle{ R_m (a_k) \in A' }[/math] istnieje taki element [math]\displaystyle{ R_m (b_j) \in B' }[/math], że
- [math]\displaystyle{ R_m (a_k) = R_m (b_j) }[/math]
Ponieważ równość reszt oznacza równość modulo, zatem
- [math]\displaystyle{ a_k \equiv b_j \!\! \pmod{m} }[/math]
Wynika stąd, że dla każdego [math]\displaystyle{ k = 1, \ldots, r }[/math] istnieje takie [math]\displaystyle{ j = 1, \ldots, r }[/math], że prawdziwa jest kongruencja
- [math]\displaystyle{ a_k \equiv b_j \!\! \pmod{m} }[/math]
czyli zbiory [math]\displaystyle{ A, B }[/math] są równe modulo [math]\displaystyle{ m }[/math]. Co kończy dowód.
□
Twierdzenie H25
Niech będą dane zbiory [math]\displaystyle{ A = \{ 1, 2, \ldots, p - 1 \} }[/math], [math]\displaystyle{ B = \{ b_1, b_2, \ldots, b_{p - 1} \} }[/math], gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą. Jeżeli wszystkie elementy zbioru [math]\displaystyle{ B }[/math] są różne modulo [math]\displaystyle{ p }[/math] i żadna z liczb [math]\displaystyle{ b_k \in B }[/math] nie jest podzielna przez [math]\displaystyle{ p }[/math], to zbiory [math]\displaystyle{ A, B, C = \{ b^{- 1}_1, b^{- 1}_2, \ldots, b^{- 1}_{p - 1} \} }[/math] są równe modulo [math]\displaystyle{ p }[/math].
Z definicji zbioru [math]\displaystyle{ A }[/math] wszystkie elementy tego zbioru są różne modulo [math]\displaystyle{ p }[/math]. Łatwo zauważamy, że
- [math]\displaystyle{ A = \{ 1, 2, \ldots, p - 1 \} = \{ R_p (1), R_p (2), \ldots, R_p (p - 1) \} = A' }[/math]
Ponieważ wszystkie liczby [math]\displaystyle{ b_k \in B }[/math], gdzie [math]\displaystyle{ k = 1, \ldots, p - 1 }[/math] są różne modulo [math]\displaystyle{ p }[/math] i nie są podzielne przez [math]\displaystyle{ p }[/math], to reszty [math]\displaystyle{ R_p (b_1), R_p (b_2), \ldots, R_p (b_{p - 1}) }[/math] są wszystkie dodatnie i różne, a ponieważ jest ich [math]\displaystyle{ p - 1 }[/math], czyli dokładnie tyle, ile jest różnych i dodatnich reszt z dzielenia przez liczbę [math]\displaystyle{ p }[/math], to zbiór tych reszt jest identyczny ze zbiorem dodatnich reszt z dzielenia przez [math]\displaystyle{ p }[/math], czyli ze zbiorem [math]\displaystyle{ A }[/math]. Zatem mamy
- [math]\displaystyle{ A = A' = \{ R_p (b_1), R_p (b_2), \ldots, R_p (b_{p - 1}) \} = B' }[/math]
Na mocy twierdzenia H24 zbiory [math]\displaystyle{ A }[/math] i [math]\displaystyle{ B }[/math] są równe modulo [math]\displaystyle{ p }[/math].
Z twierdzenia H20 wiemy, że wszystkie liczby [math]\displaystyle{ b^{- 1}_k \in C }[/math] są różne modulo [math]\displaystyle{ p }[/math]. Zauważmy, że każda z tych liczb jest względnie pierwsza z [math]\displaystyle{ p }[/math], zatem nie może być podzielna przez [math]\displaystyle{ p }[/math]. Wynika stąd, że reszty [math]\displaystyle{ R_p (b^{- 1}_1), R_p (b^{- 1}_2), \ldots, R_p (b^{- 1}_{p - 1}) }[/math] są wszystkie dodatnie i różne, a ponieważ jest ich [math]\displaystyle{ p - 1 }[/math], czyli dokładnie tyle, ile jest różnych i dodatnich reszt z dzielenia przez liczbę [math]\displaystyle{ p }[/math], to zbiór tych reszt jest identyczny ze zbiorem dodatnich reszt z dzielenia przez [math]\displaystyle{ p }[/math], czyli ze zbiorem [math]\displaystyle{ A }[/math]. Zatem mamy
- [math]\displaystyle{ A = A' = \{ R_p (b^{- 1}_1), R_p (b^{- 1}_2), \ldots, R_p (b^{- 1}_{p - 1}) \} = C' }[/math]
Na mocy twierdzenia H24 zbiory [math]\displaystyle{ A }[/math] i [math]\displaystyle{ C }[/math] są równe modulo [math]\displaystyle{ p }[/math]. Ponieważ [math]\displaystyle{ A' = B' }[/math] i [math]\displaystyle{ A' = C' }[/math], to [math]\displaystyle{ B' = C' }[/math] i ponownie na mocy twierdzenia H24 zbiory [math]\displaystyle{ B }[/math] i [math]\displaystyle{ C }[/math] są równe modulo [math]\displaystyle{ p }[/math]. Co należało pokazać.
□
Zadanie H26
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Pokazać, że suma [math]\displaystyle{ \sum_{k = 1}^{p - 1} {\small\frac{(p - 1) !}{k}} }[/math] jest podzielna przez [math]\displaystyle{ p }[/math].
Zauważmy najpierw, że modulo [math]\displaystyle{ p }[/math] następujące sumy są równe
- [math]\displaystyle{ \sum_{k = 1}^{p - 1} k \equiv \sum_{k = 1}^{p - 1} k^{- 1} \!\! \pmod{p} }[/math]
Istotnie, jeśli przyjmiemy w twierdzeniu H25, że zbiór [math]\displaystyle{ B = \{ 1, 2, \ldots, p - 1 \} }[/math], to zbiór [math]\displaystyle{ C }[/math] będzie zbiorem liczb, które są odwrotnościami liczb [math]\displaystyle{ 1, 2, \ldots, p - 1 }[/math] modulo [math]\displaystyle{ p }[/math] i możemy napisać
- [math]\displaystyle{ \sum_{x \in B} x \equiv \sum_{y \in C} y \!\! \pmod{p} }[/math]
bo
- gdy [math]\displaystyle{ x }[/math] przebiega kolejne wartości [math]\displaystyle{ b_k }[/math], to [math]\displaystyle{ x }[/math] przyjmuje kolejno wartości [math]\displaystyle{ 1, 2, \ldots, p - 1 }[/math]
- gdy [math]\displaystyle{ y }[/math] przebiega kolejne wartości [math]\displaystyle{ b_k^{- 1} }[/math], to [math]\displaystyle{ y }[/math] (modulo [math]\displaystyle{ p }[/math]) przyjmuje wszystkie wartości ze zbioru [math]\displaystyle{ A = \{ 1, 2, \ldots, p - 1 \} }[/math], czyli liczba [math]\displaystyle{ y }[/math] (modulo [math]\displaystyle{ p }[/math]) przyjmuje wszystkie wartości [math]\displaystyle{ 1, 2, \ldots, p - 1 }[/math], ale w innej kolejności
Ponieważ kolejność sumowania tych samych składników nie wpływa na wartość sumy, to prawdziwa jest wyżej wypisana równość sum modulo [math]\displaystyle{ p }[/math].
Zatem modulo [math]\displaystyle{ p }[/math] otrzymujemy
- [math]\displaystyle{ \sum_{k = 1}^{p - 1} {\small\frac{(p - 1) !}{k}} \equiv \sum_{k = 1}^{p - 1} (p - 1)! \cdot k^{- 1} }[/math]
- [math]\displaystyle{ \;\;\: \equiv (p - 1) ! \cdot \sum_{k = 1}^{p - 1} k^{- 1} }[/math]
- [math]\displaystyle{ \;\;\: \equiv (p - 1) ! \cdot \sum_{k = 1}^{p - 1} k }[/math]
- [math]\displaystyle{ \;\;\: \equiv (p - 1) ! \cdot {\small\frac{(p - 1) p}{2}} }[/math]
- [math]\displaystyle{ \;\;\: \equiv (p - 1) ! \cdot {\small\frac{p - 1}{2}} \cdot p }[/math]
- [math]\displaystyle{ \;\;\: \equiv 0 \!\! \pmod{p} }[/math]
Należy zauważyć, że dla liczby pierwszej nieparzystej [math]\displaystyle{ p }[/math] liczba [math]\displaystyle{ {\small\frac{p - 1}{2}} }[/math] jest liczbą całkowitą.
□
Funkcje multiplikatywne
Definicja H27
Powiemy, że funkcja [math]\displaystyle{ f(n) }[/math] określona w zbiorze liczb całkowitych dodatnich jest funkcją multiplikatywną, jeżeli [math]\displaystyle{ f(1) = 1 }[/math] i dla względnie pierwszych liczb [math]\displaystyle{ a, b }[/math] spełniony jest warunek [math]\displaystyle{ f(a b) = f (a) f (b) }[/math].
Uwaga H28
Założenie [math]\displaystyle{ f(1) = 1 }[/math] możemy równoważnie zastąpić założeniem, że funkcja [math]\displaystyle{ f(n) }[/math] nie jest tożsamościowo równa zero.
Gdyby [math]\displaystyle{ f(n) }[/math] spełniała jedynie warunek [math]\displaystyle{ f(a b) = f (a) f (b) }[/math] dla względnie pierwszych liczb [math]\displaystyle{ a, b }[/math], to mielibyśmy
- a) [math]\displaystyle{ f(n) }[/math] jest tożsamościowo równa zeru wtedy i tylko wtedy, gdy [math]\displaystyle{ f(1) = 0 }[/math]
- b) [math]\displaystyle{ f(n) }[/math] nie jest tożsamościowo równa zeru wtedy i tylko wtedy, gdy [math]\displaystyle{ f(1) = 1 }[/math]
Ponieważ [math]\displaystyle{ f(1) = f (1 \cdot 1) = f (1) f (1) }[/math], zatem [math]\displaystyle{ f(1) = 0 }[/math] lub [math]\displaystyle{ f (1) = 1 }[/math].
Jeżeli [math]\displaystyle{ f(1) = 0 }[/math], to dla dowolnego [math]\displaystyle{ n }[/math] mamy
- [math]\displaystyle{ f(n) = f (n \cdot 1) = f (n) f (1) = 0 }[/math]
Czyli [math]\displaystyle{ f(n) }[/math] jest funkcją tożsamościowo równą zero.
Jeżeli [math]\displaystyle{ f(n) }[/math] nie jest funkcją tożsamościowo równą zero, to istnieje taka liczba [math]\displaystyle{ a \in \mathbb{Z}_+ }[/math], że [math]\displaystyle{ f(a) \neq 0 }[/math]. Zatem
- [math]\displaystyle{ f(a) = f (a \cdot 1) = f (a) f (1) }[/math]
I dzieląc obie strony przez [math]\displaystyle{ f(a) \neq 0 }[/math], dostajemy [math]\displaystyle{ f(1) = 1 }[/math].
Przykład H29
Ponieważ [math]\displaystyle{ \gcd (1, c) = 1 }[/math], to [math]\displaystyle{ \gcd (n, c) }[/math] rozpatrywana jako funkcja [math]\displaystyle{ n }[/math], gdzie [math]\displaystyle{ c }[/math] jest ustaloną liczbą całkowitą, jest funkcją multiplikatywną (zobacz H8).
Twierdzenie H30
Jeżeli funkcja [math]\displaystyle{ f(n) }[/math] jest funkcją multiplikatywną, to funkcja
- [math]\displaystyle{ F(n) = \sum_{d \mid n} f (d) }[/math]
gdzie sumowanie przebiega po wszystkich dzielnikach dodatnich liczby [math]\displaystyle{ n }[/math], jest również funkcją multiplikatywną.
Ponieważ
- [math]\displaystyle{ F(1) = \sum_{d \mid 1} f (d) = f (1) = 1 }[/math]
to funkcja [math]\displaystyle{ F(n) }[/math] spełnia pierwszy warunek definicji H27.
Niech [math]\displaystyle{ a, b }[/math] będą względnie pierwszymi liczbami dodatnimi. Każdy dzielnik dodatni iloczynu [math]\displaystyle{ a b }[/math] można zapisać w postaci [math]\displaystyle{ d = d_1 d_2 }[/math], gdzie [math]\displaystyle{ d_1 \mid a }[/math], [math]\displaystyle{ \; d_2 \mid b \, }[/math] oraz [math]\displaystyle{ \, \gcd (d_1, d_2) = 1 }[/math] (zobacz H13). Niech zbiory
- [math]\displaystyle{ S_a = \{ d \in \mathbb{Z}_+ : d \mid a \} }[/math]
- [math]\displaystyle{ S_b = \{ d \in \mathbb{Z}_+ : d \mid b \} }[/math]
- [math]\displaystyle{ S_{a b} = \{ d \in \mathbb{Z}_+ : d \mid a b \} }[/math]
będą zbiorami dzielników dodatnich liczb [math]\displaystyle{ a, b }[/math] i [math]\displaystyle{ a b }[/math]. Dla przykładu
- [math]\displaystyle{ S_5 = \{ 1, 5 \} }[/math]
- [math]\displaystyle{ S_7 = \{ 1, 7 \} }[/math]
- [math]\displaystyle{ S_{35} = \{ 1, 5, 7, 35 \} }[/math]
Dla dowolnego [math]\displaystyle{ d_1 \in S_a \, }[/math] i [math]\displaystyle{ \, d_2 \in S_b }[/math] musi być [math]\displaystyle{ \gcd (d_1, d_2) = 1 }[/math], bo gdyby było [math]\displaystyle{ \gcd (d_1, d_2) = g \gt 1 }[/math], to
- [math]\displaystyle{ g \mid d_1 \quad \; \text{i} \quad \; d_1 \mid a \qquad \quad \Longrightarrow \qquad \quad g \mid a }[/math]
- [math]\displaystyle{ g \mid d_2 \quad \; \text{i} \quad \; d_2 \mid b \qquad \quad \Longrightarrow \qquad \quad g \mid b }[/math]
Zatem [math]\displaystyle{ g \mid \gcd (a, b) }[/math] i mielibyśmy [math]\displaystyle{ \gcd (a, b) \geqslant g \gt 1 }[/math], wbrew założeniu.
Przekształcając, otrzymujemy
- [math]\displaystyle{ F(a b) = \sum_{d \mid a b} f (d) }[/math]
- [math]\displaystyle{ \;\;\;\;\: = \sum_{d \in S_{a b}} f (d) }[/math]
- [math]\displaystyle{ \;\;\;\;\: = \underset{d_2 \in S_{b}}{\sum_{d_1 \in S_{a}}} f (d_1 d_2) }[/math]
- [math]\displaystyle{ \;\;\;\;\: = \underset{d_2 \in S_{b}}{\sum_{d_1 \in S_{a}}} f (d_1) f (d_2) }[/math]
- [math]\displaystyle{ \;\;\;\;\: = \sum_{d_1 \in S_{a}} f (d_1) \sum_{d_2 \in S_{b}} f (d_2) }[/math]
- [math]\displaystyle{ \;\;\;\;\: = \sum_{d_1 \mid a} f (d_1) \sum_{d_2 \mid b} f (d_2) }[/math]
- [math]\displaystyle{ \;\;\;\;\: = F (a) F (b) }[/math]
Co należało pokazać.
□
Funkcja Eulera [math]\displaystyle{ \varphi (n) }[/math]
Definicja H31
Funkcja Eulera [math]\displaystyle{ \varphi (n) }[/math][4] jest równa ilości liczb całkowitych dodatnich nie większych od [math]\displaystyle{ n }[/math] i względnie pierwszych z [math]\displaystyle{ n }[/math].
Twierdzenie H32
Funkcja Eulera [math]\displaystyle{ \varphi (n) }[/math] jest multiplikatywna, czyli dla względnie pierwszych liczb [math]\displaystyle{ m, n }[/math] jest [math]\displaystyle{ \varphi (m n) = \varphi (m) \varphi (n) }[/math].
Niech [math]\displaystyle{ m, n }[/math] będą dodatnimi liczbami całkowitymi takimi, że [math]\displaystyle{ \gcd (m, n) = 1 }[/math]. Twierdzenie jest prawdziwe dla [math]\displaystyle{ n = 1 }[/math], zatem nie zmniejszając ogólności, możemy założyć, że [math]\displaystyle{ n \gt 1 }[/math]. Wypiszmy w tabeli wszystkie liczby od [math]\displaystyle{ 1 }[/math] do [math]\displaystyle{ m n }[/math].
[math]\displaystyle{ 1 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ k }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ m }[/math] [math]\displaystyle{ m + 1 }[/math] [math]\displaystyle{ m + 2 }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ m + k }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ 2 m }[/math] [math]\displaystyle{ 2 m + 1 }[/math] [math]\displaystyle{ 2 m + 2 }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ 2 m + k }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ 3 m }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ (n - 1) m + 1 }[/math] [math]\displaystyle{ (n - 1) m + 2 }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ (n - 1) m + k }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ n m }[/math]
1. Natychmiast widzimy, że w pierwszym wierszu mamy [math]\displaystyle{ \varphi (m) }[/math] liczb względnie pierwszych z [math]\displaystyle{ m }[/math]. Tak samo jest w każdym kolejnym wierszu, bo (zobacz H5)
- [math]\displaystyle{ \gcd (r m + k, m) = \gcd (k, m) }[/math]
Zatem mamy dokładnie [math]\displaystyle{ \varphi (m) }[/math] kolumn liczb względnie pierwszych z [math]\displaystyle{ m }[/math].
2. Załóżmy, że liczba [math]\displaystyle{ k }[/math] jest jedną z liczb względnie pierwszych z [math]\displaystyle{ m }[/math], czyli [math]\displaystyle{ \gcd (k, m) = 1 }[/math]. Przy tym założeniu [math]\displaystyle{ k }[/math]-ta kolumna (pokazana w tabeli) jest kolumną liczb względnie pierwszych z [math]\displaystyle{ m }[/math].
3. Zauważmy, że reszty z dzielenia liczb wypisanych w [math]\displaystyle{ k }[/math]-tej kolumnie przez [math]\displaystyle{ n }[/math] są wszystkie różne. Gdyby tak nie było, to dla pewnych [math]\displaystyle{ i, j }[/math], gdzie [math]\displaystyle{ 0 \leqslant i, j \leqslant n - 1 }[/math], różnica liczb [math]\displaystyle{ i m + k }[/math] oraz [math]\displaystyle{ j m + k }[/math] byłaby podzielna przez [math]\displaystyle{ n }[/math]. Mielibyśmy
- [math]\displaystyle{ n \mid ((i m + k) - (j m + k)) }[/math]
Skąd wynika natychmiast
- [math]\displaystyle{ n \mid (i - j) m }[/math]
Ponieważ założyliśmy, że [math]\displaystyle{ \gcd (n, m) = 1 }[/math], to musi być [math]\displaystyle{ n \mid (i - j) }[/math] (zobacz C74), ale
- [math]\displaystyle{ 0 \leqslant | i - j | \leqslant n - 1 }[/math]
Czyli [math]\displaystyle{ n }[/math] może dzielić [math]\displaystyle{ i - j }[/math] tylko w przypadku, gdy [math]\displaystyle{ i = j }[/math]. Wbrew naszemu przypuszczeniu, że istnieją różne liczby dające takie same reszty przy dzieleniu przez [math]\displaystyle{ n }[/math].
4. Ponieważ w [math]\displaystyle{ k }[/math]-tej kolumnie znajduje się dokładnie [math]\displaystyle{ n }[/math] liczb i reszty z dzielenia tych liczb przez [math]\displaystyle{ n }[/math] są wszystkie różne, to reszty te tworzą zbiór [math]\displaystyle{ S = \{ 0, 1, \ldots, n - 1 \} }[/math]. Wynika stąd, że liczby wypisane w [math]\displaystyle{ k }[/math]-tej kolumnie mogą być zapisane w postaci
- [math]\displaystyle{ a_r = b_r \cdot n + r }[/math]
gdzie [math]\displaystyle{ r = 0, 1, \ldots, n - 1 }[/math] i [math]\displaystyle{ b_r \in \mathbb{Z} }[/math].
Zauważmy, że następujące ilości liczb są sobie równe
- ilość liczb w [math]\displaystyle{ k }[/math]-tej kolumnie względnie pierwszych z [math]\displaystyle{ n }[/math]
- ilość liczb [math]\displaystyle{ r }[/math] względnie pierwszych z [math]\displaystyle{ n }[/math], gdzie [math]\displaystyle{ r = 0, \ldots, n - 1 }[/math], bo [math]\displaystyle{ \gcd (b_r \cdot n + r, n) = \gcd (r, n) }[/math]
- ilość liczb [math]\displaystyle{ r }[/math] względnie pierwszych z [math]\displaystyle{ n }[/math], gdzie [math]\displaystyle{ r = 1, \ldots, n }[/math], bo [math]\displaystyle{ \gcd (n, n) = \gcd (0, n) = | n | \gt 1 }[/math]
Ostatnia ilość liczb jest równa [math]\displaystyle{ \varphi (n) }[/math], co wynika wprost z definicji funkcji [math]\displaystyle{ \varphi (n) }[/math].
5. Zbierając: mamy w wypisanej tabeli dokładnie [math]\displaystyle{ \varphi (m) \varphi (n) }[/math] liczb [math]\displaystyle{ u \in [1, m n] }[/math], dla których jednocześnie jest
- [math]\displaystyle{ \gcd (u, m) = 1 \quad \text{i} \quad \gcd (u, n) = 1 }[/math]
Z twierdzenia H6 wynika, że w tabeli jest dokładnie [math]\displaystyle{ \varphi (m) \varphi (n) }[/math] liczb [math]\displaystyle{ u \in [1, m n] }[/math], dla których jest
- [math]\displaystyle{ \gcd (u, m n) = 1 }[/math]
Zatem [math]\displaystyle{ \varphi (m n) = \varphi (m) \varphi (n) }[/math]. Co należało pokazać.
□
Twierdzenie H33
Dla dowolnej liczby całkowitej dodatniej [math]\displaystyle{ n }[/math] jest
- [math]\displaystyle{ \varphi (n) = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right) }[/math]
gdzie iloczyn obliczamy po wszystkich liczbach pierwszych [math]\displaystyle{ p }[/math], będących dzielnikami liczby [math]\displaystyle{ n }[/math].
Ponieważ wszystkie liczby naturalne mniejsze od liczby pierwszej [math]\displaystyle{ p }[/math] są jednocześnie pierwsze względem [math]\displaystyle{ p }[/math], to [math]\displaystyle{ \varphi (p) = p - 1 }[/math].
Równie łatwo znajdujemy wartość funkcji [math]\displaystyle{ \varphi (n) }[/math] w przypadku gdy [math]\displaystyle{ n }[/math] jest potęgą liczby pierwszej [math]\displaystyle{ n = p^k }[/math]. Wystarczy zauważyć, że w ciągu kolejnych liczb
- [math]\displaystyle{ 1, 2, 3, 4, \ldots, p^k - 1, p^k }[/math]
jedynymi liczbami, które nie są pierwsze względem [math]\displaystyle{ p^k }[/math], są te, które dzielą się przez [math]\displaystyle{ p }[/math] i jest ich [math]\displaystyle{ p^{k - 1} }[/math], co widać natychmiast po ich bezpośrednim wypisaniu
- [math]\displaystyle{ 1 \cdot p, 2 \cdot p, 3 \cdot p, \ldots, (p^{k - 1} - 1) \cdot p, p^{k - 1} \cdot p }[/math]
Zatem
- [math]\displaystyle{ \varphi (p^k) = p^k - p^{k - 1} = p^k \left( 1 - {\small\frac{1}{p}} \right) }[/math]
Ponieważ [math]\displaystyle{ \varphi (n) }[/math] jest funkcją multiplikatywną, to dla [math]\displaystyle{ n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math] otrzymujemy
- [math]\displaystyle{ \varphi (n) = \prod^s_{k = 1} \varphi (p^{\alpha_k}_k) }[/math]
- [math]\displaystyle{ \;\;\; = \prod^s_{k = 1} p^{\alpha_k}_k \left( 1 - {\small\frac{1}{p_k}} \right) }[/math]
- [math]\displaystyle{ \;\;\; = \left[ \prod^s_{k = 1} p^{\alpha_k}_k \right] \cdot \left[ \prod^s_{k = 1} \left( 1 - {\small\frac{1}{p_k}} \right) \right] }[/math]
- [math]\displaystyle{ \;\;\; = n \cdot \prod^s_{k = 1} \left( 1 - {\small\frac{1}{p_k}} \right) }[/math]
- [math]\displaystyle{ \;\;\; = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right) }[/math]
Co należało pokazać.
□
Twierdzenie H34
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Jeżeli [math]\displaystyle{ q }[/math] jest liczbą pierwszą, to
- [math]\displaystyle{ \varphi (q n) = \left\{ \begin{array}{rl} (q - 1) \varphi (n) & \quad \text{gdy} \quad q \nmid n \\ q \varphi (n) & \quad \text{gdy} \quad q \mid n \\ \end{array} \right. }[/math]
Jeżeli [math]\displaystyle{ q \nmid m }[/math], to [math]\displaystyle{ \gcd (q, m) = 1 }[/math], zatem [math]\displaystyle{ \varphi (q m) = \varphi (q) \varphi (m) = (q - 1) \varphi (m) }[/math]. Jeżeli [math]\displaystyle{ q \mid m }[/math], to liczby [math]\displaystyle{ m }[/math] oraz [math]\displaystyle{ q m }[/math] mają taki sam zbiór dzielników pierwszych, zatem
- [math]\displaystyle{ \varphi (q m) = q m \prod_{p \mid q m} \left( 1 - {\small\frac{1}{p}} \right) = q \cdot \left[ m \prod_{p \mid m} \left( 1 - {\small\frac{1}{p}} \right) \right] = q \varphi (m) }[/math]
Co należało pokazać.
□
Zadanie H35
Niech [math]\displaystyle{ q \in \mathbb{P} }[/math] i [math]\displaystyle{ a, b, m, n \in \mathbb{Z}_+ }[/math]. Pokazać, że
- [math]\displaystyle{ \varphi (q^{a + b}) = q^a \varphi (q^b) }[/math]
- [math]\displaystyle{ \varphi (n^m) = n^{m - 1} \varphi (n) }[/math]
Punkt 1.
- [math]\displaystyle{ \varphi (q^{a + b}) = (q - 1) q^{a + b - 1} = q^a \cdot (q - 1) q^{b - 1} = q^a \varphi (q^b) }[/math]
Punkt 2.
Niech [math]\displaystyle{ n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math]
- [math]\displaystyle{ \varphi (n^m) = \varphi (p^{m \alpha_1}_1 \cdot \ldots \cdot p^{m \alpha_s}_s) }[/math]
- [math]\displaystyle{ \, = \varphi (p^{m \alpha_1}_1) \cdot \ldots \cdot \varphi (p^{m \alpha_s}_s) }[/math]
- [math]\displaystyle{ \, = \varphi (p^{(m - 1) \alpha_1 + \alpha_1}_1) \cdot \ldots \cdot \varphi (p^{(m - 1) \alpha_s + \alpha_s}_s) }[/math]
- [math]\displaystyle{ \, = p^{(m - 1) \alpha_1}_1 \varphi (p^{\alpha_1}_1) \cdot \ldots \cdot p^{(m - 1) \alpha_s}_s \varphi (p^{\alpha_s}_s) }[/math]
- [math]\displaystyle{ \, = p^{(m - 1) \alpha_1}_1 \cdot \ldots \cdot p^{(m - 1) \alpha_s}_s \cdot \varphi (p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s) }[/math]
- [math]\displaystyle{ \, = n^{m - 1} \varphi (n) }[/math]
Co należało pokazać.
□
Twierdzenie H36
Niech [math]\displaystyle{ m, n \in \mathbb{Z}_+ }[/math]. Jeżeli [math]\displaystyle{ m \mid n }[/math], to [math]\displaystyle{ \varphi (m) \mid \varphi (n) }[/math].
Niech [math]\displaystyle{ n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math]. Ponieważ założyliśmy, że [math]\displaystyle{ m \mid n }[/math], to [math]\displaystyle{ m }[/math] musi być postaci [math]\displaystyle{ m = p^{\beta_1}_1 \cdot \ldots \cdot p^{\beta_s}_s }[/math], gdzie [math]\displaystyle{ 0 \leqslant \beta_i \leqslant \alpha_i }[/math], dla [math]\displaystyle{ i = 1, \ldots, s }[/math]. Łatwo zauważamy, że
- jeżeli [math]\displaystyle{ \beta_i = 0 }[/math], to [math]\displaystyle{ \varphi (p^{\beta_i}_i) = 1 }[/math] i dzieli [math]\displaystyle{ \varphi (p^{\alpha_i}_i) }[/math]
- jeżeli [math]\displaystyle{ 1 \leqslant \beta_i \leqslant \alpha_i }[/math], to [math]\displaystyle{ (p_i - 1) p_i^{\beta_i - 1} \mid (p_i - 1) p_i^{\alpha_i - 1} }[/math], zatem [math]\displaystyle{ \varphi (p^{\beta_i}_i) \mid \varphi (p^{\alpha_i}_i) }[/math]
Skąd natychmiast wynika, że [math]\displaystyle{ \varphi (p^{\beta_1}_1) \cdot \ldots \cdot \varphi (p^{\beta_s}_s) }[/math] dzieli [math]\displaystyle{ \varphi (p^{\alpha_1}_1) \cdot \ldots \cdot \varphi (p^{\alpha_s}_s) }[/math], czyli [math]\displaystyle{ \varphi (m) \mid \varphi (n) }[/math].
Zauważmy, że twierdzenie odwrotne nie jest prawdziwe, bo [math]\displaystyle{ \varphi (7) \mid \varphi (19) }[/math], ale [math]\displaystyle{ 7 \nmid 19 }[/math].
□
Zadanie H37
Dla [math]\displaystyle{ n \geqslant 3 }[/math] wartości [math]\displaystyle{ \varphi (n) }[/math] są liczbami parzystymi.
Jeżeli liczba [math]\displaystyle{ n \geqslant 3 }[/math] jest podzielna przez liczbę pierwszą nieparzystą [math]\displaystyle{ p }[/math], zaś [math]\displaystyle{ k }[/math] jest wykładnikiem, z jakim [math]\displaystyle{ p }[/math] wchodzi do rozwinięcia [math]\displaystyle{ n }[/math] na czynniki pierwsze, to
- [math]\displaystyle{ \varphi (n) = \varphi \left( p^k \cdot {\small\frac{n}{p^k}} \right) = (p - 1) p^{k - 1} \cdot \varphi \left( {\small\frac{n}{p^k}} \right) }[/math]
zatem [math]\displaystyle{ \varphi (n) }[/math] jest liczbą parzystą, ponieważ [math]\displaystyle{ p - 1 }[/math] jest liczbą parzystą.
Jeżeli żadna liczba nieparzysta nie dzieli [math]\displaystyle{ n }[/math], to liczba [math]\displaystyle{ n }[/math] jest postaci [math]\displaystyle{ n = 2^a }[/math] i [math]\displaystyle{ \varphi (n) = 2^{a - 1} }[/math], ale z założenia [math]\displaystyle{ n \geqslant 3 }[/math], zatem [math]\displaystyle{ a \geqslant 2 }[/math] i [math]\displaystyle{ \varphi (n) }[/math] jest liczbą parzystą.
□
Twierdzenie H38
Jeżeli [math]\displaystyle{ n }[/math] jest liczbą złożoną, to [math]\displaystyle{ \varphi (n) \leqslant n - \sqrt{n} }[/math].
Pierwszy sposób
Niech [math]\displaystyle{ n = a b }[/math], gdzie [math]\displaystyle{ 1 \lt a \leqslant b \lt n }[/math]. Liczby [math]\displaystyle{ 1 \cdot a, 2 \cdot a, 3 \cdot a, \ldots, b \cdot a }[/math] są nie większe od [math]\displaystyle{ n }[/math] i nie są względnie pierwsze z [math]\displaystyle{ n }[/math], zatem
- [math]\displaystyle{ \varphi (n) \leqslant n - b }[/math]
Ponieważ [math]\displaystyle{ b \geqslant a }[/math], to [math]\displaystyle{ b^2 \geqslant a b = n }[/math] i [math]\displaystyle{ b \geqslant \sqrt{n} }[/math]. Wynika stąd, że
- [math]\displaystyle{ \varphi (n) \leqslant n - b \leqslant n - \sqrt{n} }[/math]
Drugi sposób
Niech [math]\displaystyle{ q }[/math] oznacza najmniejszy dzielnik pierwszy liczby złożonej [math]\displaystyle{ n }[/math], zatem [math]\displaystyle{ q^2 \leqslant n }[/math], czyli [math]\displaystyle{ q \leqslant \sqrt{n} }[/math], a stąd [math]\displaystyle{ {\small\frac{n}{q}} \geqslant \sqrt{n} }[/math] i
- [math]\displaystyle{ \varphi (n) = n \cdot \prod_{p|n} \left( 1 - {\small\frac{1}{p}} \right) \leqslant n \left( 1 - {\small\frac{1}{q}} \right) = n - {\small\frac{n}{q}} \leqslant n - \sqrt{n} }[/math]
Co należało pokazać.
□
Twierdzenie H39
Dla [math]\displaystyle{ n \geqslant 1 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ \varphi (n) \gt {\small\frac{\sqrt{n}}{2}} }[/math].
Dla [math]\displaystyle{ k \geqslant 3 }[/math] jest
- [math]\displaystyle{ \left( 1 - {\small\frac{1}{k}} \right)^2 \gt {\small\frac{1}{k}} }[/math]
Wynika stąd, że jeżeli [math]\displaystyle{ m \geqslant 3 }[/math] jest liczbą nieparzystą, to
- [math]\displaystyle{ \varphi (m)^2 = m^2 \prod_{p|m} \left( 1 - {\small\frac{1}{p}} \right)^2 \gt m^2 \prod_{p|m} {\small\frac{1}{p}} \geqslant m }[/math]
bo
- [math]\displaystyle{ \prod_{p|m} p \leqslant m }[/math]
Czyli dla nieparzystych liczb [math]\displaystyle{ m \geqslant 3 }[/math] mamy
- [math]\displaystyle{ \varphi (m) \gt \sqrt{m} \gt {\small\frac{\sqrt{m}}{2}} }[/math]
Jeżeli [math]\displaystyle{ d = 2^a }[/math], gdzie [math]\displaystyle{ a \geqslant 1 }[/math], to
- [math]\displaystyle{ \varphi (d) = \varphi (2^a) = 2^{a - 1} \gt {\small\frac{\sqrt{2^a}}{2}} = {\small\frac{\sqrt{d}}{2}} }[/math]
W przypadku ogólnym, gdy [math]\displaystyle{ n }[/math] jest iloczynem liczby nieparzystej [math]\displaystyle{ m \geqslant 3 }[/math] i potęgi liczby [math]\displaystyle{ 2 }[/math], dostajemy
- [math]\displaystyle{ \varphi (n) = \varphi (2^a m) = \varphi (2^a) \varphi (m) \gt {\small\frac{\sqrt{2^a}}{2}} \cdot \sqrt{m} = {\small\frac{\sqrt{2^a m}}{2}} = {\small\frac{\sqrt{n}}{2}} }[/math]
Oczywiście nierówność [math]\displaystyle{ \varphi (n) \gt {\small\frac{\sqrt{n}}{2}} }[/math] jest również prawdziwa dla [math]\displaystyle{ n = 1 }[/math]. Co należało pokazać.
□
Zadanie H40
Pokazać, że dla [math]\displaystyle{ n \geqslant 7 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ \varphi (n) \gt \sqrt{n} }[/math].
Zauważmy, że
- [math]\displaystyle{ n - 1 \gt \sqrt{n} \qquad \qquad \;\, \text{dla} \; n \geqslant 3 }[/math]
- [math]\displaystyle{ n - 1 \gt \sqrt{2 n} \qquad \qquad \text{dla} \; n \geqslant 4 }[/math]
Zatem dla liczby pierwszej [math]\displaystyle{ p }[/math] i [math]\displaystyle{ k \geqslant 1 }[/math] jest
- [math]\displaystyle{ \varphi (p^k) = (p - 1) p^{k - 1} \gt \sqrt{p} \cdot p^{k - 1} = p^{k - \tfrac{1}{2}} \geqslant p^{\tfrac{k}{2}} = \sqrt{p^k} \qquad \qquad \qquad \qquad \quad \; \text{dla} \;\: p \geqslant 3 }[/math]
- [math]\displaystyle{ \varphi (p^k) = (p - 1) p^{k - 1} \gt \sqrt{2 p} \cdot p^{k - 1} = \sqrt{2} \cdot p^{k - \tfrac{1}{2}} \geqslant \sqrt{2} \cdot p^{\tfrac{k}{2}} = \sqrt{2 p^k} \qquad \qquad \text{dla} \;\, p \geqslant 5 }[/math]
1. Przypadek, gdy [math]\displaystyle{ \boldsymbol{n \geqslant 3} }[/math] jest liczbą nieparzystą
Liczba [math]\displaystyle{ n }[/math] jest iloczynem czynników pierwszych nieparzystych, zatem
- [math]\displaystyle{ \varphi (n) = \varphi (p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s) = \varphi (p^{\alpha_1}_1) \cdot \ldots \cdot \varphi (p^{\alpha_s}_s) \gt \sqrt{p^{\alpha_1}_1} \cdot \ldots \cdot \sqrt{p^{\alpha_s}_s} = \sqrt{n} }[/math]
2. Przypadek, gdy [math]\displaystyle{ \boldsymbol{n = 2^a m} \; }[/math] i [math]\displaystyle{ \; \boldsymbol{q \mid m ,} \; }[/math] gdzie [math]\displaystyle{ \; \boldsymbol{q \geqslant 5} }[/math]
Z założenia [math]\displaystyle{ n = 2^a m = 2^a q^b r }[/math], gdzie [math]\displaystyle{ r \geqslant 1 }[/math] jest liczbą nieparzystą. Zauważmy, że [math]\displaystyle{ \varphi (r) \geqslant \sqrt{r} }[/math], bo może być [math]\displaystyle{ r = 1 }[/math].
- [math]\displaystyle{ \varphi (n) = \varphi (2^a q^b r) }[/math]
- [math]\displaystyle{ \;\;\,\, = \varphi (2^a) \varphi (q^b) \varphi (r) }[/math]
- [math]\displaystyle{ \;\;\,\, \gt 2^{a - 1} \sqrt{2 q^b} \sqrt{r} }[/math]
- [math]\displaystyle{ \;\;\,\, = 2^{a - \tfrac{1}{2}} \sqrt{q^b} \sqrt{r} }[/math]
- [math]\displaystyle{ \;\;\,\, \geqslant 2^{\tfrac{a}{2}} \sqrt{q^b r} }[/math]
- [math]\displaystyle{ \;\;\,\, = \sqrt{2^a q^b r} }[/math]
- [math]\displaystyle{ \;\;\,\, = \sqrt{n} }[/math]
3. Przypadek, gdy [math]\displaystyle{ \boldsymbol{n = 2^a m} \; }[/math] i [math]\displaystyle{ \; \boldsymbol{q \nmid m ,} \; }[/math] gdzie [math]\displaystyle{ \; \boldsymbol{q \geqslant 5} }[/math]
Jeżeli żadna liczba pierwsza [math]\displaystyle{ q \geqslant 5 }[/math] nie dzieli [math]\displaystyle{ m }[/math], to możliwe są tylko dwie sytuacje: [math]\displaystyle{ n = 2^a \, }[/math] i [math]\displaystyle{ \, n = 2^a 3^b }[/math].
3a. Przypadek, gdy [math]\displaystyle{ \boldsymbol{n = 2^a} }[/math]
- [math]\displaystyle{ \varphi (n) = \varphi (2^a) = 2^{a - 1} \gt \sqrt{2^a} = \sqrt{n} \qquad \qquad \;\, \text{dla} \; a \geqslant 3 }[/math]
Twierdzenie nie jest prawdziwe dla [math]\displaystyle{ n = 2 \, }[/math] i [math]\displaystyle{ \, n = 4 \,\, }[/math] (gdy [math]\displaystyle{ a = 1 \, }[/math] lub [math]\displaystyle{ \, a = 2 }[/math]).
3b. Przypadek, gdy [math]\displaystyle{ \boldsymbol{n = 2^a 3^b} }[/math]
- [math]\displaystyle{ \varphi (n) = \varphi (2^a 3^b) = \varphi (2^a) \varphi (3^b) = 2^{a - 1} \cdot 2 \cdot 3^{b - 1} = 2^a 3^{b - 1} = \sqrt{2^a 3^b} \cdot {\small\frac{\sqrt{2^a 3^b}}{3}} \gt \sqrt{2^a 3^b} }[/math]
Ostatnia nierówność jest prawdziwa, o ile [math]\displaystyle{ \sqrt{2^a 3^b} \gt 3 }[/math], czyli gdy [math]\displaystyle{ 2^a 3^b \gt 9 }[/math], co ma miejsce, gdy [math]\displaystyle{ a \geqslant 2 }[/math] lub [math]\displaystyle{ b \geqslant 2 }[/math].
Twierdzenie nie jest prawdziwe dla [math]\displaystyle{ n = 6 \; }[/math] (gdy [math]\displaystyle{ a = 1 \, }[/math] i [math]\displaystyle{ \, b = 1 }[/math]).
Zbierając uzyskane wyniki, otrzymujemy: oszacowanie [math]\displaystyle{ \varphi (n) \gt \sqrt{n} }[/math] nie jest prawdziwe dla [math]\displaystyle{ n = 1, 2, 4, 6 }[/math]. Co należało pokazać.
□
Zadanie H41
Pokazać, że dla [math]\displaystyle{ n \geqslant 2 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ \varphi (n) \gt {\small\frac{n}{3 \log n}} }[/math]. Korzystając z tego wyniku, pokazać, że [math]\displaystyle{ \varphi (n) \gt n^{2 / 3} }[/math] dla [math]\displaystyle{ n \geqslant 43 }[/math] oraz że [math]\displaystyle{ \varphi (n) \gt n^{3 / 4} }[/math] dla [math]\displaystyle{ n \geqslant 211 }[/math].
Niech [math]\displaystyle{ n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s }[/math], a [math]\displaystyle{ n' = q_1 \cdot \ldots \cdot q_s }[/math] oznacza liczbę, będącą iloczynem dokładnie tych samych czynników pierwszych, jakie występują w liczbie [math]\displaystyle{ n }[/math], natomiast [math]\displaystyle{ n^{\!\ast} = p_1 \cdot \ldots \cdot p_s }[/math] oznacza liczbę, będącą iloczynem dokładnie tej samej ilości czynników pierwszych, przy czym [math]\displaystyle{ p_i }[/math] oznacza teraz [math]\displaystyle{ i }[/math]-tą liczbę pierwszą.
Ponieważ
- [math]\displaystyle{ {\small\frac{\varphi (n)}{n}} = \prod_{p \mid n} \left( 1 - {\small\frac{1}{p}} \right) }[/math]
to
- [math]\displaystyle{ {\small\frac{\varphi (n)}{n}} = {\small\frac{\varphi (n')}{n'}} \geqslant {\small\frac{\varphi (n^{\!\ast})}{n^{\!\ast}}} = \prod^s_{i = 1} \left( 1 - {\small\frac{1}{p_i}} \right) \geqslant \prod^{p_s}_{k = 2} \left( 1 - {\small\frac{1}{k}} \right) = {\small\frac{1}{p_s}} }[/math]
Ostatnia równość wynika z prostego wzoru
- [math]\displaystyle{ \prod^m_{k = 2} \left( 1 - {\small\frac{1}{k}} \right) = {\small\frac{1}{2}} \cdot {\small\frac{2}{3}} \cdot {\small\frac{3}{4}} \cdot \ldots \cdot {\small\frac{m - 2}{m - 1}} \cdot {\small\frac{m - 1}{m}} = {\small\frac{1}{m}} }[/math]
Musimy oszacować wartość liczby [math]\displaystyle{ p_s }[/math]. Z twierdzenia B31 wynika, że dla [math]\displaystyle{ m \geqslant 2 }[/math] jest [math]\displaystyle{ P(m) \geqslant 2^{m / 2} }[/math], gdzie funkcja [math]\displaystyle{ P(m) }[/math] jest równa iloczynowi wszystkich liczb pierwszych nie większych od [math]\displaystyle{ m }[/math]. Zatem dla [math]\displaystyle{ p_s \geqslant 2 }[/math] jest
- [math]\displaystyle{ n^{\!\ast} = p_1 \cdot \ldots \cdot p_s = P (p_s) \geqslant 2^{p_s / 2} }[/math]
Logarytmując, otrzymujemy
- [math]\displaystyle{ p_s \leqslant {\small\frac{2 \log n^{\!\ast}}{\log 2}} }[/math]
Ponieważ [math]\displaystyle{ n \geqslant n' \geqslant n^{\!\ast} }[/math], to
- [math]\displaystyle{ {\small\frac{\varphi (n)}{n}} \geqslant {\small\frac{1}{p_s}} \geqslant {\small\frac{\log 2}{2 \log n^{\!\ast}}} \geqslant {\small\frac{\log 2}{2 \log n}} \gt {\small\frac{1}{3 \log n}} }[/math]
Ostatecznie otrzymujemy
- [math]\displaystyle{ \varphi (n) \gt {\small\frac{n}{3 \log n}} }[/math]
Co należało pokazać.
Rozwiązując drugą część zadania, wystarczy znaleźć, dla jakich [math]\displaystyle{ n }[/math] prawdziwa jest nierówność
- [math]\displaystyle{ {\small\frac{n}{3 \log n}} \gt n^{2 / 3} }[/math]
Przebieg funkcji [math]\displaystyle{ {\small\frac{n}{3 \log n}} \, }[/math] i [math]\displaystyle{ \, n^{2 / 3} }[/math] przedstawiliśmy na wykresie
Punkt przecięcia tych funkcji znajdujemy, wpisując w PARI/GP polecenie
solve(n = 10, 10^5, n/(3*log(n)) - n^(2/3))
Otrzymujemy
- [math]\displaystyle{ n = 29409.965 }[/math]
Zatem [math]\displaystyle{ {\small\frac{n}{3 \log n}} \gt n^{2 / 3} }[/math] dla [math]\displaystyle{ n \gt 2.95 \cdot 10^4 }[/math].
Poleceniem
for(n = 1, 3*10^4, if( eulerphi(n) <= n^(2/3), print(n) ))
sprawdzamy, że oszacowanie [math]\displaystyle{ \varphi (n) \gt n^{2 / 3} }[/math] jest prawdziwe dla [math]\displaystyle{ n \geqslant 43 }[/math].
Postępując analogicznie jak wyżej, znajdujemy, dla jakich [math]\displaystyle{ n }[/math] prawdziwa jest nierówność
- [math]\displaystyle{ {\small\frac{n}{3 \log n}} \gt n^{3 / 4} }[/math]
Wpisując w PARI/GP polecenie
solve(n = 10, 10^7, n/(3*log(n)) - n^(3/4))
otrzymujemy
- [math]\displaystyle{ n = 4447862.680 }[/math]
Zatem [math]\displaystyle{ {\small\frac{n}{3 \log n}} \gt n^{3 / 4} }[/math] dla [math]\displaystyle{ n \gt 4.45 \cdot 10^6 }[/math]
Poleceniem
for(n = 1, 5*10^6, if( eulerphi(n) <= n^(3/4), print(n) ))
sprawdzamy, że oszacowanie [math]\displaystyle{ \varphi (n) \gt n^{3 / 4} }[/math] jest prawdziwe dla [math]\displaystyle{ n \geqslant 211 }[/math]. Co należało pokazać.
□
Twierdzenie H42
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Liczba [math]\displaystyle{ n }[/math] jest liczbą pierwszą wtedy i tylko wtedy, gdy [math]\displaystyle{ \varphi (n) = n - 1 }[/math].
Dla liczb złożonych [math]\displaystyle{ n \geqslant 4 }[/math] nigdy nie będzie [math]\displaystyle{ \varphi (n) = n - 1 }[/math], bo
- [math]\displaystyle{ \varphi (n) \leqslant n - \sqrt{n} \leqslant n - 2 }[/math]
Dla [math]\displaystyle{ n = 1, 2, 3 }[/math] sprawdzamy bezpośrednio: [math]\displaystyle{ \varphi (1) = 1 \neq 1 - 1 }[/math], [math]\displaystyle{ \varphi (2) = 1 = 2 - 1 }[/math], [math]\displaystyle{ \varphi (3) = 2 = 3 - 1 }[/math]. Co kończy dowód.
□
Twierdzenie H43
Dla dowolnej liczby całkowitej dodatniej [math]\displaystyle{ n }[/math] jest
- [math]\displaystyle{ n = \sum_{d \mid n} \varphi (d) = \sum_{d \mid n} \varphi \left( {\small\frac{n}{d}} \right) }[/math]
gdzie sumowanie przebiega po wszystkich dzielnikach dodatnich liczby [math]\displaystyle{ n }[/math].
Ponieważ [math]\displaystyle{ \varphi (n) }[/math] jest funkcją multiplikatywną, to funkcja
- [math]\displaystyle{ F(n) = \sum_{d \mid n} \varphi (d) }[/math]
też jest funkcją multiplikatywną (zobacz H30). Łatwo sprawdzamy, że twierdzenie jest prawdziwe dla [math]\displaystyle{ n = 1 }[/math]. Niech [math]\displaystyle{ n \gt 1 }[/math]. Jeżeli [math]\displaystyle{ n = p^{\alpha} }[/math] jest potęgą liczby pierwszej, to otrzymujemy
- [math]\displaystyle{ F (p^{\alpha}) = \sum_{d \mid p^{\alpha}} \varphi (d) }[/math]
- [math]\displaystyle{ = \varphi (1) + \varphi (p) + \varphi (p^2) + \ldots + \varphi (p^{\alpha}) = }[/math]
- [math]\displaystyle{ = 1 + (p - 1) + p (p - 1) + \ldots + p^{\alpha - 1} (p - 1) = }[/math]
- [math]\displaystyle{ = 1 + (p - 1) + (p^2 - p) + \ldots + (p^{\alpha} - p^{\alpha - 1}) }[/math]
- [math]\displaystyle{ = p^{\alpha} }[/math]
Jeżeli [math]\displaystyle{ n }[/math] jest postaci [math]\displaystyle{ n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math], to
- [math]\displaystyle{ F(n) = F (p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s) = }[/math]
- [math]\displaystyle{ \;\;\;\, = F (p^{\alpha_1}_1) \cdot \ldots \cdot F (p^{\alpha_s}_s) = }[/math]
- [math]\displaystyle{ \;\;\;\, = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math]
- [math]\displaystyle{ \;\;\;\, = n }[/math]
Niech [math]\displaystyle{ 1 \lt d_1 \lt d_2 \lt \ldots \lt n }[/math] będą dzielnikami liczby [math]\displaystyle{ n }[/math]. Zauważmy, że kiedy [math]\displaystyle{ d }[/math] przebiega zbiór dzielników [math]\displaystyle{ \{ 1, d_1, d_2, \ldots, n \} }[/math], to [math]\displaystyle{ e = {\small\frac{n}{d}} }[/math] przebiega wszystkie te liczby tylko w odwrotnej kolejności. Zatem
- [math]\displaystyle{ \sum_{d \mid n} \varphi (d) = \sum_{d \mid n} \varphi \left( {\small\frac{n}{d}} \right) }[/math]
Co należało pokazać.
□
Zadanie H44
Niech [math]\displaystyle{ n \geqslant 2 }[/math]. Pokazać, że suma liczb całkowitych dodatnich nie większych od [math]\displaystyle{ n }[/math] i względnie pierwszych z [math]\displaystyle{ n }[/math] jest równa [math]\displaystyle{ {\small\frac{1}{2}} n \varphi (n) }[/math].
Łatwo sprawdzamy, że wzór jest prawdziwy dla [math]\displaystyle{ n = 2 }[/math] i odtąd będziemy przyjmowali, że [math]\displaystyle{ n \geqslant 3 }[/math]. Zatem wartości [math]\displaystyle{ \varphi (n) }[/math] są liczbami parzystymi i niech [math]\displaystyle{ c = {\small\frac{1}{2}} \varphi (n) }[/math]. Zauważmy, że jeżeli liczba [math]\displaystyle{ a }[/math] jest względnie pierwsza z [math]\displaystyle{ n }[/math], to liczba [math]\displaystyle{ n - a }[/math] jest również względnie pierwsza z [math]\displaystyle{ n }[/math], bo [math]\displaystyle{ \gcd (a, n) = \gcd (n - a, n) }[/math]. Wypiszmy wszystkie liczby całkowite dodatnie nie większe od [math]\displaystyle{ n }[/math] i względnie pierwsze z [math]\displaystyle{ n }[/math] w kolejności rosnącej, a pod spodem w kolejności malejącej
[math]\displaystyle{ 1 }[/math] [math]\displaystyle{ a_2 }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ a_c }[/math] [math]\displaystyle{ n - a_c }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ n - a_2 }[/math] [math]\displaystyle{ n - 1 }[/math] [math]\displaystyle{ n - 1 }[/math] [math]\displaystyle{ n - a_2 }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ n - a_c }[/math] [math]\displaystyle{ a_c }[/math] [math]\displaystyle{ … }[/math] [math]\displaystyle{ a_2 }[/math] [math]\displaystyle{ 1 }[/math]
Suma liczb w każdej kolumnie jest równa [math]\displaystyle{ n }[/math]. Ponieważ ilość liczb względnie pierwszych z [math]\displaystyle{ n }[/math] jest równa [math]\displaystyle{ \varphi (n) }[/math], to podwojona suma liczb całkowitych nie większych od [math]\displaystyle{ n }[/math] i pierwszych względem [math]\displaystyle{ n }[/math] wynosi [math]\displaystyle{ n \varphi (n) }[/math]. Co należało pokazać.
□
Zadanie H45
Pokazać, że dla liczb naturalnych nieparzystych [math]\displaystyle{ n \geqslant 5 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ \varphi (n) \gt \pi (n) }[/math].
1. Jeżeli [math]\displaystyle{ n \geqslant 5 }[/math] jest liczbą pierwszą, to liczbami pierwszymi względem [math]\displaystyle{ n }[/math] są wszystkie liczby pierwsze mniejsze od [math]\displaystyle{ n }[/math] oraz liczby [math]\displaystyle{ 1, 4 }[/math]. Zatem
- [math]\displaystyle{ \varphi (n) \geqslant \pi (n) - 1 + 2 \gt \pi (n) }[/math].
2. Jeżeli [math]\displaystyle{ n = p^a }[/math], gdzie [math]\displaystyle{ a \geqslant 2 }[/math], jest potęgą liczby pierwszej nieparzystej, to [math]\displaystyle{ n \geqslant 9 }[/math] i liczbami pierwszymi względem [math]\displaystyle{ n }[/math] są wszystkie liczby pierwsze nie większe od [math]\displaystyle{ n }[/math] (oprócz liczby [math]\displaystyle{ p }[/math]) oraz liczby [math]\displaystyle{ 1, 4, 8 }[/math]. Zatem
- [math]\displaystyle{ \varphi (n) \geqslant \pi (n) - 1 + 3 \gt \pi (n) }[/math].
3. Jeżeli [math]\displaystyle{ n }[/math] ma więcej niż jeden dzielnik pierwszy nieparzysty, to [math]\displaystyle{ n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s }[/math], gdzie [math]\displaystyle{ s \geqslant 2 }[/math]. Zauważmy, że
- [math]\displaystyle{ n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s \geqslant q_1 \cdot \ldots \cdot q_s \geqslant 3 \cdot 5^{s - 1} \gt 2^{2 s - 1} }[/math]
Liczbami pierwszymi względem [math]\displaystyle{ n }[/math] są wszystkie liczby pierwsze nie większe od [math]\displaystyle{ n }[/math] (oprócz liczb [math]\displaystyle{ q_1, \ldots, q_s }[/math]) oraz liczby [math]\displaystyle{ 1, 2^2, 2^3, \ldots, 2^{2 s - 1} }[/math]. Zatem
- [math]\displaystyle{ \varphi (n) \geqslant \pi (n) - s + 2 s - 1 = \pi (n) + s - 1 \gt \pi (n) }[/math]
Co należało pokazać.
□
Zadanie H46
Pokazać, że dla liczb naturalnych [math]\displaystyle{ n \geqslant 91 }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ \varphi (n) \gt \pi (n) }[/math].
Ponieważ [math]\displaystyle{ p_{2 s} \gt 1 }[/math] i [math]\displaystyle{ p_{2 s} \geqslant p_{s + 1} }[/math], to z zadania A40 natychmiast wynika nierówność
- [math]\displaystyle{ p_1 p_2 \cdot \ldots \cdot p_s \gt p_{s + 1} p_{2 s} }[/math]
która jest prawdziwa dla [math]\displaystyle{ n \geqslant 4 }[/math].
Pokażemy najpierw, że dla każdej liczby naturalnej mającej nie mniej niż cztery dzielniki pierwsze nierówność [math]\displaystyle{ \varphi (n) \gt \pi (n) }[/math] jest zawsze prawdziwa.
Przez [math]\displaystyle{ p_1, p_2, \ldots, p_k, \ldots }[/math] oznaczymy kolejne liczby pierwsze. Niech [math]\displaystyle{ n \geqslant 2 }[/math] będzie liczbą naturalną i [math]\displaystyle{ n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s }[/math], gdzie [math]\displaystyle{ q_i }[/math] oznaczają dowolne (nie muszą być kolejne) liczby pierwsze.
Wśród kolejnych [math]\displaystyle{ 2 s }[/math] liczb pierwszych znajduje się przynajmniej [math]\displaystyle{ s }[/math] liczb pierwszych różnych od każdej z liczb [math]\displaystyle{ q_1, \ldots, q_s }[/math]. Jeśli oznaczymy te liczby (w rosnącej kolejności) przez [math]\displaystyle{ r_1, \ldots, r_s }[/math], to łatwo zauważymy, że prawdziwe są dla nich następujące oszacowania
- dla najmniejszej liczby [math]\displaystyle{ r_1 \leqslant p_{s + 1} }[/math]
- dla wszystkich liczb [math]\displaystyle{ r_j \leqslant p_{2 s} }[/math] dla [math]\displaystyle{ j = 1, \ldots, s }[/math].
Korzystając z wypisanej na początku dowodu nierówności, dla [math]\displaystyle{ s \geqslant 4 }[/math] mamy
- [math]\displaystyle{ n = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s \geqslant q_1 \cdot \ldots \cdot q_s \geqslant p_1 \cdot \ldots \cdot p_s \gt p_{s + 1} p_{2 s} \geqslant r_1 \cdot r_j }[/math]
gdzie [math]\displaystyle{ j = 1, \ldots, s }[/math].
Wynika stąd, że jeśli [math]\displaystyle{ s \geqslant 4 }[/math], to liczbami pierwszymi względem [math]\displaystyle{ n }[/math] są wszystkie liczby pierwsze nie większe od [math]\displaystyle{ n }[/math] (oprócz liczb pierwszych [math]\displaystyle{ q_1, \ldots, q_s }[/math]) oraz liczby [math]\displaystyle{ 1 }[/math] i [math]\displaystyle{ r_1 r_j }[/math], gdzie [math]\displaystyle{ j = 1, \ldots, s }[/math]. Zatem
- [math]\displaystyle{ \varphi (n) \geqslant \pi (n) - s + s + 1\gt \pi (n) }[/math]
Co mieliśmy pokazać.
Uwzględniając rezultat pokazany w zadaniu H45, pozostaje sprawdzić przypadki gdy [math]\displaystyle{ n = 2^a }[/math], [math]\displaystyle{ n = 2^a p^b }[/math], [math]\displaystyle{ n = 2^a p^b q^c }[/math], gdzie [math]\displaystyle{ a, b, c \in \mathbb{Z}_+ }[/math].
1. Niech [math]\displaystyle{ n = 2^a }[/math]. Jeśli [math]\displaystyle{ n \geqslant 16 }[/math], to liczbami pierwszymi względem [math]\displaystyle{ n }[/math] są wszystkie liczby pierwsze nie większe od [math]\displaystyle{ n }[/math] (oprócz liczby [math]\displaystyle{ 2 }[/math]) oraz liczby [math]\displaystyle{ 1, 9, 15 }[/math]. Zatem
- [math]\displaystyle{ \varphi (n) \geqslant \pi (n) - 1 + 3 \gt \pi (n) }[/math]
2. Niech [math]\displaystyle{ n = 2^a p^b }[/math], zaś [math]\displaystyle{ r }[/math] będzie najmniejszą liczbą pierwszą nieparzystą różną od [math]\displaystyle{ p }[/math]. Oczywiście [math]\displaystyle{ r \in \{ 3, 5 \} }[/math] i jeśli tylko [math]\displaystyle{ n \gt 5^3 = 125 }[/math], to liczbami pierwszymi względem [math]\displaystyle{ n }[/math] są wszystkie liczby pierwsze nie większe od [math]\displaystyle{ n }[/math] (oprócz liczb pierwszych [math]\displaystyle{ 2 }[/math] i [math]\displaystyle{ p }[/math]) oraz liczby [math]\displaystyle{ 1, r^2, r^3 }[/math]. Zatem
- [math]\displaystyle{ \varphi (n) \geqslant \pi (n) - 2 + 3 \gt \pi (n) }[/math]
3. Niech [math]\displaystyle{ n = 2^a p^b q^c }[/math], zaś [math]\displaystyle{ r }[/math] będzie najmniejszą liczbą pierwszą nieparzystą różną od [math]\displaystyle{ p }[/math] oraz różną od [math]\displaystyle{ q }[/math]. Oczywiście [math]\displaystyle{ r \in \{ 3, 5, 7 \} }[/math] i jeśli [math]\displaystyle{ n \gt 7^4 = 2401 }[/math], to liczbami pierwszymi względem [math]\displaystyle{ n }[/math] są wszystkie liczby pierwsze nie większe od [math]\displaystyle{ n }[/math] (oprócz liczb pierwszych [math]\displaystyle{ 2 }[/math], [math]\displaystyle{ p }[/math] i [math]\displaystyle{ q }[/math]) oraz liczby [math]\displaystyle{ 1, r^2, r^3, r^4 }[/math]. Zatem
- [math]\displaystyle{ \varphi (n) \geqslant \pi (n) - 3 + 4 \gt \pi (n) }[/math]
Zbierając: pozostaje sprawdzić bezpośrednio przypadki, gdy [math]\displaystyle{ n }[/math] jest liczbą parzystą i [math]\displaystyle{ n \leqslant 2401 }[/math]. W GP/PARI wystarczy napisać polecenie
for(n = 1, 2500, if( eulerphi(n) <= primepi(n), print(n) ))
Nierówność [math]\displaystyle{ \varphi (n) \gt \pi (n) }[/math] nie jest prawdziwa dla [math]\displaystyle{ n \in \{ 2, 3, 4, 6, 8, 10, 12, 14, 18, 20, 24, 30, 42, 60, 90 \} }[/math]. Co kończy dowód.
□
Zadanie H47
Pokazać, że [math]\displaystyle{ \varphi (n) = 2^a }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ n = 2^b q_1 \cdot \ldots \cdot q_s }[/math], gdzie [math]\displaystyle{ q_1, \ldots, q_s }[/math] są liczbami pierwszymi Fermata: [math]\displaystyle{ 3, 5, 17, 257, 65537 }[/math].
W przypadku, gdy [math]\displaystyle{ 2 \mid n }[/math], łatwo zauważamy, że liczba [math]\displaystyle{ 2 }[/math] może występować w dowolnej potędze, bo [math]\displaystyle{ \varphi (2^b) = 2^{b - 1} }[/math].
W przypadku, gdy [math]\displaystyle{ p \mid n }[/math], gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą, mamy [math]\displaystyle{ \varphi (p^k) = (p - 1) p^{k - 1} }[/math] i równie łatwo zauważmy, że musi być [math]\displaystyle{ k = 1 }[/math], a liczba [math]\displaystyle{ p - 1 }[/math] musi być potęgą liczby [math]\displaystyle{ 2 }[/math]. Zatem liczba pierwsza [math]\displaystyle{ p }[/math] musi być postaci [math]\displaystyle{ p = 2^t + 1 }[/math], co jest możliwe tylko wtedy, gdy [math]\displaystyle{ t }[/math] jest potęgą liczby [math]\displaystyle{ 2 }[/math] (zobacz H48), czyli [math]\displaystyle{ p }[/math] musi być liczbą pierwszą Fermata. Co należało pokazać.
□
Uzupełnienie
Twierdzenie H48
Niech [math]\displaystyle{ a, n \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ a \geqslant 2 }[/math]. Jeżeli liczba [math]\displaystyle{ a^n + 1 }[/math] jest liczbą pierwszą, to [math]\displaystyle{ a }[/math] jest liczbą parzystą i [math]\displaystyle{ n = 2^m }[/math].
Gdyby liczba [math]\displaystyle{ a }[/math] była nieparzysta, to liczba [math]\displaystyle{ a^n + 1 \geqslant 4 }[/math] byłaby parzysta i nie mogłaby być liczbą pierwszą.
Niech wykładnik [math]\displaystyle{ n = x y }[/math] będzie liczbą złożoną, a [math]\displaystyle{ x }[/math] będzie liczbą nieparzystą. Wtedy
- [math]\displaystyle{ a^n + 1 = (a^y)^x + 1 }[/math]
Oznaczając [math]\displaystyle{ b = a^y }[/math] oraz [math]\displaystyle{ x = 2 k + 1 }[/math], otrzymujemy
- [math]\displaystyle{ a^n + 1 = (a^y)^x + 1 = b^x + 1 = b^{2 k + 1} + 1 = (b + 1) \cdot (1 - b + b^2 - b^3 + \ldots + b^{2 k - 2} - b^{2 k - 1} + b^{2 k}) }[/math]
Zatem w takim przypadku [math]\displaystyle{ a^n + 1 }[/math] jest liczbą złożoną. Wynika stąd, że wykładnik [math]\displaystyle{ n }[/math] nie może zawierać czynników nieparzystych, czyli musi być [math]\displaystyle{ n = 2^m }[/math]. Co należało pokazać.
□
Przypisy