Ciągi liczbowe: Różnice pomiędzy wersjami
(Nie pokazano 21 pośrednich wersji utworzonych przez tego samego użytkownika) | |||
Linia 7: | Linia 7: | ||
== Ciągi nieskończone == | == Ciągi nieskończone == | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja C1</span><br/> | + | <span id="C1" style="font-size: 110%; font-weight: bold;">Definicja C1</span><br/> |
Niech <math>n \in \mathbb{Z}_+</math>. Jeżeli każdej liczbie <math>n</math> przypiszemy pewną liczbę rzeczywistą <math>a_n</math>, to powiemy, że liczby <math>a_1, a_2, \ldots, a_n, \ldots</math> tworzą ciąg nieskończony. | Niech <math>n \in \mathbb{Z}_+</math>. Jeżeli każdej liczbie <math>n</math> przypiszemy pewną liczbę rzeczywistą <math>a_n</math>, to powiemy, że liczby <math>a_1, a_2, \ldots, a_n, \ldots</math> tworzą ciąg nieskończony. | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga C2</span><br/> | + | <span id="C2" style="font-size: 110%; font-weight: bold;">Uwaga C2</span><br/> |
Ciąg nieskończony <math>a_1, a_2, \ldots, a_n, \ldots</math> będziemy oznaczać <math>(a_n)</math>. Często, o ile nie będzie prowadziło to do nieporozumień, ciąg nieskończony będziemy nazywać po prostu ciągiem. | Ciąg nieskończony <math>a_1, a_2, \ldots, a_n, \ldots</math> będziemy oznaczać <math>(a_n)</math>. Często, o ile nie będzie prowadziło to do nieporozumień, ciąg nieskończony będziemy nazywać po prostu ciągiem. | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja C3</span><br/> | + | <span id="C3" style="font-size: 110%; font-weight: bold;">Definicja C3</span><br/> |
Niech <math>n \in \mathbb{Z}_+</math>. Ciąg <math>(a_n)</math> będziemy nazywali | Niech <math>n \in \mathbb{Z}_+</math>. Ciąg <math>(a_n)</math> będziemy nazywali | ||
::* ciągiem rosnącym, jeżeli dla każdego <math>n</math> jest <math>a_{n + 1} \geqslant a_n</math> | ::* ciągiem rosnącym, jeżeli dla każdego <math>n</math> jest <math>a_{n + 1} \geqslant a_n</math> | ||
Linia 32: | Linia 32: | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja C4</span><br/> | + | <span id="C4" style="font-size: 110%; font-weight: bold;">Definicja C4</span><br/> |
Niech <math>\varepsilon \in \mathbb{R}_+</math>. Liczbę <math>a</math> będziemy nazywali granicą ciągu <math>(a_n)</math>, jeżeli dla dowolnego <math>\varepsilon</math> w przedziale <math>(a - \varepsilon, a + \varepsilon)</math> znajdują się '''prawie wszystkie wyrazy ciągu''' <math>(a_n)</math> (to znaczy wszystkie poza co najwyżej skończoną ilością). | Niech <math>\varepsilon \in \mathbb{R}_+</math>. Liczbę <math>a</math> będziemy nazywali granicą ciągu <math>(a_n)</math>, jeżeli dla dowolnego <math>\varepsilon</math> w przedziale <math>(a - \varepsilon, a + \varepsilon)</math> znajdują się '''prawie wszystkie wyrazy ciągu''' <math>(a_n)</math> (to znaczy wszystkie poza co najwyżej skończoną ilością). | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga C5</span><br/> | + | <span id="C5" style="font-size: 110%; font-weight: bold;">Uwaga C5</span><br/> |
1) sens definicji jest taki: jeżeli liczba <math>a</math> jest granicą ciągu <math>(a_n)</math>, to dla dowolnie małego <math>\varepsilon > 0</math>, poza przedziałem <math>(a - \varepsilon, a + \varepsilon)</math> może się znaleźć co najwyżej skończona ilość wyrazów ciągu <math>(a_n)</math> | 1) sens definicji jest taki: jeżeli liczba <math>a</math> jest granicą ciągu <math>(a_n)</math>, to dla dowolnie małego <math>\varepsilon > 0</math>, poza przedziałem <math>(a - \varepsilon, a + \varepsilon)</math> może się znaleźć co najwyżej skończona ilość wyrazów ciągu <math>(a_n)</math> | ||
− | 2) słabsze żądanie, aby w przedziale <math>(a - \varepsilon, a + \varepsilon)</math> znajdowała się nieskończona ilość wyrazów ciągu nie prowadzi do poprawnej definicji granicy. Przykładowo, w przedziale <math>(1 - \varepsilon, 1 + \varepsilon)</math> znajduje się nieskończenie wiele wyrazów ciągu <math>a_n = (-1)^n</math>, ale ani liczba <math>1</math>, ani liczba <math>- 1</math> nie są granicami tego ciągu. O ciągu <math>a_n = (- 1)^n</math> mówimy, że nie ma granicy. | + | 2) słabsze żądanie, aby w przedziale <math>(a - \varepsilon, a + \varepsilon)</math> znajdowała się nieskończona ilość wyrazów ciągu, nie prowadzi do poprawnej definicji granicy. Przykładowo, w przedziale <math>(1 - \varepsilon, 1 + \varepsilon)</math> znajduje się nieskończenie wiele wyrazów ciągu <math>a_n = (-1)^n</math>, ale ani liczba <math>1</math>, ani liczba <math>- 1</math> nie są granicami tego ciągu. O ciągu <math>a_n = (- 1)^n</math> mówimy, że nie ma granicy. |
3) ze względu na równoważność warunków | 3) ze względu na równoważność warunków | ||
Linia 49: | Linia 49: | ||
::* <math>\quad | a_n - a | < \varepsilon</math> | ::* <math>\quad | a_n - a | < \varepsilon</math> | ||
− | definicja C4 może być wypowiedziana następująco | + | definicja [[#C4|C4]] może być wypowiedziana następująco |
− | <span style="font-size: 110%; font-weight: bold;">Definicja C6</span><br/> | + | <span id="C6" style="font-size: 110%; font-weight: bold;">Definicja C6</span><br/> |
Liczbę <math>a</math> będziemy nazywali granicą ciągu <math>(a_n)</math>, jeżeli dla dowolnego <math>\varepsilon > 0</math> '''prawie wszystkie wyrazy ciągu''' <math>(a_n)</math> spełniają warunek <math>|a_n - a| < \varepsilon</math>. | Liczbę <math>a</math> będziemy nazywali granicą ciągu <math>(a_n)</math>, jeżeli dla dowolnego <math>\varepsilon > 0</math> '''prawie wszystkie wyrazy ciągu''' <math>(a_n)</math> spełniają warunek <math>|a_n - a| < \varepsilon</math>. | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja C7</span><br/> | + | <span id="C7" style="font-size: 110%; font-weight: bold;">Definicja C7</span><br/> |
− | Ciąg <math>(a_n)</math> mający granicę (w rozumieniu definicji C4 lub C6) będziemy nazywali ciągiem zbieżnym, a fakt ten zapisujemy symbolicznie następująco | + | Ciąg <math>(a_n)</math> mający granicę (w rozumieniu definicji [[#C4|C4]] lub [[#C6|C6]]) będziemy nazywali ciągiem zbieżnym, a fakt ten zapisujemy symbolicznie następująco |
::<math>\lim_{n \to \infty} a_n = a</math> lub <math>a_n \longrightarrow a</math> | ::<math>\lim_{n \to \infty} a_n = a</math> lub <math>a_n \longrightarrow a</math> | ||
Linia 68: | Linia 68: | ||
Zauważmy jeszcze, że wprost z definicji granicy wynika</br> | Zauważmy jeszcze, że wprost z definicji granicy wynika</br> | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie C8</span><br/ | + | <span id="C8" style="font-size: 110%; font-weight: bold;">Twierdzenie C8</span><br/> |
− | |||
− | :: | + | ::1. <math>\quad \lim_{n \to \infty} a_n = a \qquad \iff \qquad \lim_{n \to \infty} (a_n - a) = 0 \qquad \iff \qquad \lim_{n \to \infty} | a_n - a | = 0</math> |
− | ::3. <math>\quad \lim_{n \to \infty} a_n = a \ | + | ::2. <math>\quad \lim_{n \to \infty} a_n = 0 \qquad \iff \qquad \lim_{n \to \infty} | a_n | = 0</math> |
+ | |||
+ | ::3. <math>\quad \lim_{n \to \infty} a_n = a \qquad \implies \qquad \lim_{n \to \infty} | a_n | = | a |</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}} | ||
Linia 79: | Linia 80: | ||
Prawdziwość twierdzenia wynika ze względu na identyczność warunków, które muszą spełniać prawie wszystkie wyrazy ciągu | Prawdziwość twierdzenia wynika ze względu na identyczność warunków, które muszą spełniać prawie wszystkie wyrazy ciągu | ||
− | ::<math>| a_n - a | < \varepsilon \ | + | ::<math>| a_n - a | < \varepsilon \qquad \iff \qquad | (a_n - a) - 0 | < \varepsilon \qquad \iff \qquad \big|| a_n - a | - 0 \big| < \varepsilon</math> |
'''Punkt 2.'''<br/> | '''Punkt 2.'''<br/> | ||
Linia 95: | Linia 96: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie C9 (twierdzenie o trzech ciągach)</span><br/> | + | <span id="C9" style="font-size: 110%; font-weight: bold;">Twierdzenie C9</span><br/> |
+ | Jeżeli ciąg <math>(a_n)</math> jest zbieżny, to jest ograniczony. | ||
+ | |||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
+ | Z założenia ciąg <math>(a_n)</math> jest zbieżny, zatem możemy napisać, że <math>\lim_{n \rightarrow \infty} a_n = a</math>. Z definicji granicy (zobacz [[#C4|C4]], [[#C6|C6]]) dla dowolnego <math>\varepsilon > 0</math> prawie wszystkie wyrazy ciągu <math>(a_n)</math> spełniają warunek <math>| a_n - a | < \varepsilon</math>. Możemy przyjąć, że są to wszystkie wyrazy, poczynając od pewnego <math>N = N (\varepsilon)</math>. Zatem dla <math>n > N</math> jest | ||
+ | |||
+ | ::<math>a - \varepsilon < a_n < a + \varepsilon</math> | ||
+ | |||
+ | Wynika stąd, że dla każdego <math>n \geqslant 1</math> jest | ||
+ | |||
+ | ::<math>m \leqslant a_n \leqslant M</math> | ||
+ | |||
+ | gdzie | ||
+ | |||
+ | ::<math>M = \max (a_1, \ldots, a_N, a + \varepsilon)</math> | ||
+ | |||
+ | ::<math>m = \min (a_1, \ldots, a_N, a - \varepsilon)</math> | ||
+ | |||
+ | Ponieważ <math>- | m | \leqslant m \;</math> i <math>\; M \leqslant | M |</math>, to | ||
+ | |||
+ | ::<math>- | m | \leqslant a_n \leqslant | M |</math> | ||
+ | |||
+ | Jeżeli oznaczymy <math>U = \max (| m |, | M |)</math>, to możemy napisać | ||
+ | |||
+ | ::<math>- U \leqslant a_n \leqslant U</math> | ||
+ | |||
+ | Czyli dla każdego <math>n \geqslant 1</math> jest <math>| a_n | \leqslant U</math>. Co kończy dowód.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C10" style="font-size: 110%; font-weight: bold;">Twierdzenie C10 (twierdzenie o trzech ciągach)</span><br/> | ||
Jeżeli istnieje taka liczba całkowita <math>N_0</math>, że dla każdego <math>n > N_0</math> jest spełniony warunek | Jeżeli istnieje taka liczba całkowita <math>N_0</math>, że dla każdego <math>n > N_0</math> jest spełniony warunek | ||
Linia 107: | Linia 140: | ||
{{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>\varepsilon</math> będzie dowolną, ustaloną liczbą większą od <math>0</math>. Z założenia prawie wszystkie wyrazy ciągu <math>(a_n)</math> spełniają warunek <math>|a_n - g| < \varepsilon</math>. Możemy | + | Niech <math>\varepsilon</math> będzie dowolną, ustaloną liczbą większą od <math>0</math>. Z założenia prawie wszystkie wyrazy ciągu <math>(a_n)</math> spełniają warunek <math>|a_n - g| < \varepsilon</math>. Możemy przyjąć, że są to wszystkie wyrazy, poczynając od wyrazu <math>N_a</math>. Podobnie prawie wszystkie wyrazy ciągu <math>(b_n)</math> spełniają warunek <math>|b_n - g| < \varepsilon</math> i podobnie możemy przyjąć, że są to wszystkie wyrazy, poczynając od wyrazu <math>N_b</math> |
Nierówność <math>a_n \leqslant x_n \leqslant b_n</math> jest spełniona dla wszystkich wyrazów, poczynając od <math>N_0</math>, zatem oznaczając przez <math>M</math> największą z liczb <math>N_a</math>, <math>N_b</math>, <math>N_0</math>, możemy napisać, że o ile <math>n > M</math>, to spełnione są jednocześnie nierówności | Nierówność <math>a_n \leqslant x_n \leqslant b_n</math> jest spełniona dla wszystkich wyrazów, poczynając od <math>N_0</math>, zatem oznaczając przez <math>M</math> największą z liczb <math>N_a</math>, <math>N_b</math>, <math>N_0</math>, możemy napisać, że o ile <math>n > M</math>, to spełnione są jednocześnie nierówności | ||
Linia 130: | Linia 163: | ||
Bez dowodu podamy kilka ważnych twierdzeń.<br> | Bez dowodu podamy kilka ważnych twierdzeń.<br> | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C11" style="font-size: 110%; font-weight: bold;">Twierdzenie C11*</span><br/> |
Jeżeli istnieje taka liczba całkowita <math>n</math> i rzeczywista <math>M</math>, że dla każdego <math>k > n</math> jest | Jeżeli istnieje taka liczba całkowita <math>n</math> i rzeczywista <math>M</math>, że dla każdego <math>k > n</math> jest | ||
Linia 140: | Linia 173: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C12" style="font-size: 110%; font-weight: bold;">Twierdzenie C12*</span><br/> |
Jeżeli istnieje taka liczba całkowita <math>n</math> i rzeczywista <math>M</math>, że dla każdego <math>k > n</math> jest | Jeżeli istnieje taka liczba całkowita <math>n</math> i rzeczywista <math>M</math>, że dla każdego <math>k > n</math> jest | ||
Linia 150: | Linia 183: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C13" style="font-size: 110%; font-weight: bold;">Twierdzenie C13*</span><br/> |
Jeżeli <math>\lim_{n \to \infty} a_n = a</math> oraz <math>\lim_{n \to \infty} b_n = b</math>, gdzie <math>a, b</math> są dowolnymi liczbami rzeczywistymi, to | Jeżeli <math>\lim_{n \to \infty} a_n = a</math> oraz <math>\lim_{n \to \infty} b_n = b</math>, gdzie <math>a, b</math> są dowolnymi liczbami rzeczywistymi, to | ||
Linia 158: | Linia 191: | ||
Jeżeli dodatkowo dla każdego <math>n</math> jest <math>b_n \neq 0</math> i <math>b \neq 0</math>, to | Jeżeli dodatkowo dla każdego <math>n</math> jest <math>b_n \neq 0</math> i <math>b \neq 0</math>, to | ||
− | : 3. <math>\quad \lim_{n \to \infty} \frac{a_n}{b_n} = \frac{a}{b}</math> | + | : 3. <math>\quad \lim_{n \to \infty} {\small\frac{a_n}{b_n}} = {\small\frac{a}{b}}</math> |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C14" style="font-size: 110%; font-weight: bold;">Twierdzenie C14</span><br/> |
Jeżeli <math>\lim_{n \to \infty} a_n = 0</math>, zaś ciąg <math>(x_n)</math> jest ograniczony, czyli istnieje taka liczba <math>M > 0</math>, że dla każdej wartości <math>n</math> prawdziwa jest nierówność <math>| x_n | < M</math>, to | Jeżeli <math>\lim_{n \to \infty} a_n = 0</math>, zaś ciąg <math>(x_n)</math> jest ograniczony, czyli istnieje taka liczba <math>M > 0</math>, że dla każdej wartości <math>n</math> prawdziwa jest nierówność <math>| x_n | < M</math>, to | ||
Linia 168: | Linia 201: | ||
{{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}} | ||
− | Wystarczy pokazać, że (zobacz twierdzenie C8 p.2) | + | Wystarczy pokazać, że (zobacz twierdzenie [[#C8|C8]] p.2) |
::<math>\lim_{n \to \infty} |x_n \cdot a_n| = 0</math> | ::<math>\lim_{n \to \infty} |x_n \cdot a_n| = 0</math> | ||
Linia 176: | Linia 209: | ||
::<math>0 \leqslant |x_n \cdot a_n| \leqslant |a_n| \cdot M</math> | ::<math>0 \leqslant |x_n \cdot a_n| \leqslant |a_n| \cdot M</math> | ||
− | Zatem z twierdzenia o trzech ciągach otrzymujemy natychmiast, że | + | Zatem z twierdzenia o trzech ciągach otrzymujemy natychmiast, że |
::<math>\lim_{n \to \infty} |x_n \cdot a_n| = 0</math> | ::<math>\lim_{n \to \infty} |x_n \cdot a_n| = 0</math> | ||
Linia 186: | Linia 219: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C15" style="font-size: 110%; font-weight: bold;">Twierdzenie C15</span><br/> |
Dla <math>a \geqslant 0</math> i <math>n \geqslant 1</math> prawdziwa jest nierówność | Dla <math>a \geqslant 0</math> i <math>n \geqslant 1</math> prawdziwa jest nierówność | ||
− | ::<math>(1 + a)^{1 / n} \leqslant 1 + \frac{a}{n}</math> | + | ::<math>(1 + a)^{1 / n} \leqslant 1 + {\small\frac{a}{n}}</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}} | ||
Wzór jest prawdziwy dla <math>a = 0</math>. Zakładając, że <math>a > 0</math> i korzystając ze wzoru dwumianowego, mamy dla <math>n \geqslant 1</math> | Wzór jest prawdziwy dla <math>a = 0</math>. Zakładając, że <math>a > 0</math> i korzystając ze wzoru dwumianowego, mamy dla <math>n \geqslant 1</math> | ||
− | ::<math>\left( 1 + \frac{a}{n} \right)^n = \sum_{k=0}^{n}\left [\binom{n}{k} \cdot \left ( \frac{a}{n} \right )^k \right ] \geqslant</math> | + | ::<math>\left( 1 + {\small\frac{a}{n}} \right)^n = \sum_{k=0}^{n} \left [ {\small\binom{n}{k}} \cdot \left ( {\small\frac{a}{n}} \right )^k \right ] \geqslant</math> |
− | :::::<math>\;\; \geqslant \sum_{k=0}^{1}\left [\binom{n}{k} \cdot \left ( \frac{a}{n} \right )^k \right ] =</math> | + | :::::<math>\;\; \geqslant \sum_{k=0}^{1} \left [ {\small\binom{n}{k}} \cdot \left ( {\small\frac{a}{n}} \right )^k \right ] =</math> |
− | :::::<math>\;\; = 1 + n \cdot \frac{a}{n} =</math> | + | :::::<math>\;\; = 1 + n \cdot {\small\frac{a}{n}} =</math> |
:::::<math>\;\; = 1 + a</math> | :::::<math>\;\; = 1 + a</math> | ||
Linia 205: | Linia 238: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C16" style="font-size: 110%; font-weight: bold;">Twierdzenie C16</span><br/> |
Jeżeli <math>A > 0</math>, to <math>\lim_{n \to \infty} \sqrt[n]{A} = 1</math>. | Jeżeli <math>A > 0</math>, to <math>\lim_{n \to \infty} \sqrt[n]{A} = 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}} | ||
− | Dla <math>A > 1</math> możemy napisać <math>A = 1 + a</math>, gdzie <math>a > 0</math>, wtedy z twierdzenia | + | Dla <math>A > 1</math> możemy napisać <math>A = 1 + a</math>, gdzie <math>a > 0</math>, wtedy z twierdzenia [[#C15|C15]] otrzymujemy |
− | ::<math>1 < \sqrt[n]{A} = (1 + a)^{1 / n} \leqslant 1 + \frac{a}{n}</math> | + | ::<math>1 < \sqrt[n]{A} = (1 + a)^{1 / n} \leqslant 1 + {\small\frac{a}{n}}</math> |
Z twierdzenia o trzech ciągach dostajemy natychmiast (dla <math>A > 1</math>) | Z twierdzenia o trzech ciągach dostajemy natychmiast (dla <math>A > 1</math>) | ||
Linia 217: | Linia 250: | ||
::<math>\lim_{n \to \infty} \sqrt[n]{A} = 1</math> | ::<math>\lim_{n \to \infty} \sqrt[n]{A} = 1</math> | ||
− | W przypadku gdy <math>0 < A < 1</math>, możemy napisać <math>A = \frac{1}{B}</math>, gdzie <math>B > 1</math>, wtedy ze względu na udowodniony wyżej rezultat <math>\lim_{n \to \infty} \sqrt[n]{B} = 1</math> | + | W przypadku gdy <math>0 < A < 1</math>, możemy napisać <math>A = {\small\frac{1}{B}}</math>, gdzie <math>B > 1</math>, wtedy ze względu na udowodniony wyżej rezultat <math>\lim_{n \to \infty} \sqrt[n]{B} = 1</math> |
− | ::<math>\lim_{n \to \infty} \sqrt[n]{A} = \lim_{n \to \infty} \frac{1}{\sqrt[n]{B}} = \frac{1}{\underset{n \rightarrow \infty}{\lim} \sqrt[n]{B}} = 1</math> | + | ::<math>\lim_{n \to \infty} \sqrt[n]{A} = \lim_{n \to \infty} {\small\frac{1}{\sqrt[n]{B}}} = \frac{1}{\underset{n \rightarrow \infty}{\lim} \sqrt[n]{B}} = 1</math> |
Jeżeli <math>A = 1</math>, to <math>\sqrt[n]{A} = 1</math> dla każdego <math>n \geqslant 1</math>. Co kończy dowód.<br/> | Jeżeli <math>A = 1</math>, to <math>\sqrt[n]{A} = 1</math> dla każdego <math>n \geqslant 1</math>. Co kończy dowód.<br/> | ||
Linia 227: | Linia 260: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C17" style="font-size: 110%; font-weight: bold;">Twierdzenie C17</span><br/> |
− | Jeżeli prawie wszystkie wyrazy | + | Jeżeli prawie wszystkie wyrazy ciągu <math>(a_n)</math> spełniają warunek <math>0 < m < a_n < M</math>, to <math>\lim_{n \to \infty} \sqrt[n]{a_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}} | ||
Linia 239: | Linia 272: | ||
::<math>\sqrt[n]{m} \leqslant \sqrt[n]{a_n} \leqslant \sqrt[n]{M}</math> | ::<math>\sqrt[n]{m} \leqslant \sqrt[n]{a_n} \leqslant \sqrt[n]{M}</math> | ||
− | Z twierdzenia | + | Z twierdzenia [[#C16|C16]] wiemy, że <math>\lim_{n \to \infty} \sqrt[n]{m} = \lim_{n \to \infty} \sqrt[n]{M} = 1</math>, zatem na podstawie twierdzenia o trzech ciągach otrzymujemy natychmiast <math>\lim_{n \to \infty} \sqrt[n]{a_n} = 1</math><br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 245: | Linia 278: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C18" style="font-size: 110%; font-weight: bold;">Twierdzenie C18</span><br/> |
Następujące ciągi są silnie rosnące i zbieżne | Następujące ciągi są silnie rosnące i zbieżne | ||
::{| class="wikitable plainlinks" style="font-size: 100%; text-align: center; margin-right: auto;" | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: center; margin-right: auto;" | ||
|- style=height:4em | |- style=height:4em | ||
− | | <math>\quad 1. \quad</math> || <math>\lim_{n \to \infty} \left( 1 + \frac{1}{n} \right)^n = e = 2.718281828 \ldots</math> | + | | <math>\quad 1. \quad</math> || <math>\lim_{n \to \infty} \left( 1 + {\small\frac{1}{n}} \right)^n = e = 2.718281828 \ldots</math> |
|- style=height:4em | |- style=height:4em | ||
− | | <math>\quad 2. \quad</math> || <math>\lim_{n \to \infty} \left( 1 - \frac{1}{n} \right)^n = \frac{1}{e} = 0.367879441 \ldots</math> | + | | <math>\quad 2. \quad</math> || <math>\lim_{n \to \infty} \left( 1 - {\small\frac{1}{n}} \right)^n = {\small\frac{1}{e}} = 0.367879441 \ldots</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'''<br/> | '''Punkt 1'''<br/> | ||
− | W twierdzeniu A6 pokazaliśmy, że ciąg | + | W twierdzeniu [[Twierdzenie Czebyszewa o funkcji π(n)#A6|A6]] pokazaliśmy, że ciąg |
− | ::<math>a_n = \left( 1 + \frac{1}{n} \right)^n</math> | + | ::<math>a_n = \left( 1 + {\small\frac{1}{n}} \right)^n</math> |
− | jest silnie rosnący i ograniczony od góry. Zatem z twierdzenia | + | jest silnie rosnący i ograniczony od góry. Zatem z twierdzenia [[#C11|C11]] wynika, że jest zbieżny. Liczbę będącą granicą tego ciągu oznaczamy literą <math>e</math>, jest ona podstawą logarytmu naturalnego. |
'''Punkt 2'''<br/> | '''Punkt 2'''<br/> | ||
− | Pokażemy najpierw, że ciąg <math>\left( 1 - \frac{1}{n} \right)^n</math> jest silnie rosnący. Musimy pokazać, że prawdziwa jest nierówność | + | Pokażemy najpierw, że ciąg <math>\left( 1 - {\small\frac{1}{n}} \right)^n</math> jest silnie rosnący. Musimy pokazać, że prawdziwa jest nierówność |
− | ::<math>\left( 1 - \frac{1}{n + 1} \right)^{n + 1} > \left( 1 - \frac{1}{n} \right)^n</math> | + | ::<math>\left( 1 - {\small\frac{1}{n + 1}} \right)^{n + 1} > \left( 1 - {\small\frac{1}{n}} \right)^n</math> |
Łatwo sprawdzamy prawdziwość nierówności dla <math>n = 1</math>. Załóżmy teraz, że <math>n \geqslant 2</math>. Przekształcając, | Łatwo sprawdzamy prawdziwość nierówności dla <math>n = 1</math>. Załóżmy teraz, że <math>n \geqslant 2</math>. Przekształcając, | ||
− | ::<math>\left( \frac{n}{n + 1} \right)^{n + 1} > \left( \frac{n - 1}{n} \right)^n</math> | + | ::<math>\left( {\small\frac{n}{n + 1}} \right)^{n + 1} > \left( {\small\frac{n - 1}{n}} \right)^n</math> |
− | ::<math>\frac{n}{n + 1} \cdot \left( \frac{n}{n + 1} \right)^n \cdot \left( \frac{n}{n - 1} \right)^n > 1</math> | + | ::<math>{\small\frac{n}{n + 1}} \cdot \left( {\small\frac{n}{n + 1}} \right)^n \cdot \left( {\small\frac{n}{n - 1}} \right)^n > 1</math> |
− | ::<math>\left( \frac{n^2}{n^2 - 1} \right)^n > \frac{n + 1}{n}</math> | + | ::<math>\left( {\small\frac{n^2}{n^2 - 1}} \right)^n > {\small\frac{n + 1}{n}}</math> |
otrzymujemy nierówność równoważną, | otrzymujemy nierówność równoważną, | ||
− | ::<math>\left( 1 + \frac{1}{n^2 - 1} \right)^n > 1 + \frac{1}{n}</math> | + | ::<math>\left( 1 + {\small\frac{1}{n^2 - 1}} \right)^n > 1 + {\small\frac{1}{n}}</math> |
którą już łatwo udowodnić, bo | którą już łatwo udowodnić, bo | ||
− | ::<math>\left( 1 + \frac{1}{n^2 - 1} \right)^n > \left( 1 + \frac{1}{n^2} \right)^n = \sum_{k = 0}^{n} \binom{n}{k} \cdot \left( \frac{1}{n^2} \right)^k > \sum_{k = 0}^{1} \binom{n}{k} \cdot \frac{1}{n^{2k}} = 1 + \frac{1}{n}</math> | + | ::<math>\left( 1 + {\small\frac{1}{n^2 - 1}} \right)^n > \left( 1 + {\small\frac{1}{n^2}} \right)^n = \sum_{k = 0}^{n} {\small\binom{n}{k}} \cdot \left( {\small\frac{1}{n^2}} \right)^k > \sum_{k = 0}^{1} {\small\binom{n}{k}} \cdot {\small\frac{1}{n^{2k}}} = 1 + {\small\frac{1}{n}}</math> |
− | Ponieważ dla każdego <math>n \geqslant 1</math> jest <math>\left( 1 - \frac{1}{n} \right)^n \leqslant 1</math> (bo iloczyn liczb mniejszych od <math>1</math> nie może być liczbą większą do jedności), to z twierdzenia | + | Ponieważ dla każdego <math>n \geqslant 1</math> jest <math>\left( 1 - {\small\frac{1}{n}} \right)^n \leqslant 1</math> (bo iloczyn liczb mniejszych od <math>1</math> nie może być liczbą większą do jedności), to z twierdzenia [[#C11|C11]] wynika, że ciąg ten jest zbieżny. Zatem możemy napisać |
− | ::<math>\underset{n \rightarrow \infty}{\lim} \left( 1 - \frac{1}{n} \right)^n = g</math> | + | ::<math>\underset{n \rightarrow \infty}{\lim} \left( 1 - {\small\frac{1}{n}} \right)^n = g</math> |
Rozważmy teraz iloczyn wypisanych w twierdzeniu ciągów | Rozważmy teraz iloczyn wypisanych w twierdzeniu ciągów | ||
− | ::<math>\left( 1 + \frac{1}{n} \right)^n \cdot \left( 1 - \frac{1}{n} \right)^n = \left( 1 - \frac{1}{n^2} \right)^n = \left[ \left( 1 - \frac{1}{n^2} \right)^{n^2} \right]^{1 / n}</math> | + | ::<math>\left( 1 + {\small\frac{1}{n}} \right)^n \cdot \left( 1 - {\small\frac{1}{n}} \right)^n = \left( 1 - {\small\frac{1}{n^2}} \right)^n = \left[ \left( 1 - {\small\frac{1}{n^2}} \right)^{n^2} \right]^{1 / n}</math> |
− | Łatwo widzimy, że ciąg <math>\left( 1 - \frac{1}{n^2} \right)^{n^2}</math> jest podciągiem ciągu <math>\left( 1 - \frac{1}{n} \right)^n</math>, zatem jest ograniczony i dla <math>n \geqslant 2</math> spełniony jest układ nierówności | + | Łatwo widzimy, że ciąg <math>\left( 1 - {\small\frac{1}{n^2}} \right)^{n^2}</math> jest podciągiem ciągu <math>\left( 1 - {\small\frac{1}{n}} \right)^n</math>, zatem jest ograniczony i dla <math>n \geqslant 2</math> spełniony jest układ nierówności |
− | ::<math>0 < \left( \frac{3}{4} \right)^4 \leqslant \left( 1 - \frac{1}{n^2} \right)^{n^2} \leqslant 1</math> | + | ::<math>0 < \left( {\small\frac{3}{4}} \right)^4 \leqslant \left( 1 - {\small\frac{1}{n^2}} \right)^{n^2} \leqslant 1</math> |
− | Z twierdzenia | + | Z twierdzenia [[#C17|C17]] dostajemy |
− | ::<math>\lim_{n \to \infty} \left[ \left( 1 - \frac{1}{n^2} \right)^{n^2} \right]^{1 / n} = 1</math> | + | ::<math>\lim_{n \to \infty} \left[ \left( 1 - {\small\frac{1}{n^2}} \right)^{n^2} \right]^{1 / n} = 1</math> |
− | Z twierdzenia | + | Z twierdzenia [[#C13|C13]] p. 2 wynika natychmiast, że |
− | ::<math>e \cdot g = \lim_{n \to \infty} \left[ \left( 1 + \frac{1}{n} \right)^n \cdot \left( 1 - \frac{1}{n} \right)^n \right] = \lim_{n \to \infty} \left[ \left( 1 - \frac{1}{n^2} \right)^{n^2} \right]^{1 / n} = 1</math> | + | ::<math>e \cdot g = \lim_{n \to \infty} \left[ \left( 1 + {\small\frac{1}{n}} \right)^n \cdot \left( 1 - {\small\frac{1}{n}} \right)^n \right] = \lim_{n \to \infty} \left[ \left( 1 - {\small\frac{1}{n^2}} \right)^{n^2} \right]^{1 / n} = 1</math> |
− | Zatem <math>g = \frac{1}{e}</math>.<br/> | + | Zatem <math>g = {\small\frac{1}{e}}</math>.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 310: | Linia 343: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C19" style="font-size: 110%; font-weight: bold;">Twierdzenie C19</span><br/> |
Dla <math>n \geqslant 2</math> prawdziwe są następujące nierówności | Dla <math>n \geqslant 2</math> prawdziwe są następujące nierówności | ||
::{| class="wikitable plainlinks" style="font-size: 100%; text-align: center; margin-right: auto;" | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: center; margin-right: auto;" | ||
|- style=height:4em | |- style=height:4em | ||
− | | <math>\quad 1. \quad</math> || <math> \frac{1}{n + 1} < \log \left( 1 + \frac{1}{n} \right) < \frac{1}{n}</math> | + | | <math>\quad 1. \quad</math> || <math> {\small\frac{1}{n + 1}} < \log \left( 1 + {\small\frac{1}{n}} \right) < {\small\frac{1}{n}}</math> |
|- style=height:4em | |- style=height:4em | ||
− | | <math>\quad 2. \quad</math> || <math>- \frac{1}{n - 1} < \log \left( 1 - \frac{1}{n} \right) < - \frac{1}{n}</math> | + | | <math>\quad 2. \quad</math> || <math>- {\small\frac{1}{n - 1}} < \log \left( 1 - {\small\frac{1}{n}} \right) < - {\small\frac{1}{n}}</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}} | ||
− | Ponieważ ciąg <math>\left( 1 + \frac{1}{n} \right)^n</math> jest silnie rosnący, to | + | Ponieważ ciąg <math>\left( 1 + {\small\frac{1}{n}} \right)^n</math> jest silnie rosnący, to |
− | ::<math>\left( 1 + \frac{1}{n} \right)^n < e</math> | + | ::<math>\left( 1 + {\small\frac{1}{n}} \right)^n < e</math> |
Logarytmując powyższą nierówność, mamy | Logarytmując powyższą nierówność, mamy | ||
− | ::<math>n \cdot \log \left( 1 + \frac{1}{n} \right) < 1</math> | + | ::<math>n \cdot \log \left( 1 + {\small\frac{1}{n}} \right) < 1</math> |
Stąd wynika natychmiast, że | Stąd wynika natychmiast, że | ||
− | ::<math>\log \left( 1 + \frac{1}{n} \right) < \frac{1}{n}</math> | + | ::<math>\log \left( 1 + {\small\frac{1}{n}} \right) < {\small\frac{1}{n}}</math> |
− | Ponieważ ciąg <math>\left( 1 - \frac{1}{n} \right)^n</math> również jest silnie rosnący, to postępując analogicznie, dostajemy | + | Ponieważ ciąg <math>\left( 1 - {\small\frac{1}{n}} \right)^n</math> również jest silnie rosnący, to postępując analogicznie, dostajemy |
− | ::<math>\left( 1 - \frac{1}{n} \right)^n < \frac{1}{e}</math> | + | ::<math>\left( 1 - {\small\frac{1}{n}} \right)^n < {\small\frac{1}{e}}</math> |
− | ::<math>n \cdot \log \left( 1 - \frac{1}{n} \right) < - 1</math> | + | ::<math>n \cdot \log \left( 1 - {\small\frac{1}{n}} \right) < - 1</math> |
− | ::<math>\log \left( 1 - \frac{1}{n} \right) < - \frac{1}{n}</math> | + | ::<math>\log \left( 1 - {\small\frac{1}{n}} \right) < - {\small\frac{1}{n}}</math> |
Przekształcając otrzymane wzory, otrzymujemy | Przekształcając otrzymane wzory, otrzymujemy | ||
− | ::<math>- \log \left( 1 + \frac{1}{n} \right) = - \log \left( \frac{n + 1}{n} \right) = \log \left( \frac{n}{n + 1} \right) = \log \left( 1 - \frac{1}{n + 1} \right) < - \frac{1}{n + 1}</math> | + | ::<math>- \log \left( 1 + {\small\frac{1}{n}} \right) = - \log \left( {\small\frac{n + 1}{n}} \right) = \log \left( {\small\frac{n}{n + 1}} \right) = \log \left( 1 - {\small\frac{1}{n + 1}} \right) < - {\small\frac{1}{n + 1}}</math> |
oraz | oraz | ||
− | ::<math>- \log \left( 1 - \frac{1}{n} \right) = - \log \left( \frac{n - 1}{n} \right) = \log \left( \frac{n}{n - 1} \right) = \log \left( 1 + \frac{1}{n - 1} \right) < \frac{1}{n - 1}</math><br/> | + | ::<math>- \log \left( 1 - {\small\frac{1}{n}} \right) = - \log \left( {\small\frac{n - 1}{n}} \right) = \log \left( {\small\frac{n}{n - 1}} \right) = \log \left( 1 + {\small\frac{1}{n - 1}} \right) < {\small\frac{1}{n - 1}}</math><br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 359: | Linia 392: | ||
== Liczby pierwsze w ciągach arytmetycznych == | == Liczby pierwsze w ciągach arytmetycznych == | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C20" style="font-size: 110%; font-weight: bold;">Twierdzenie C20</span><br/> |
Każda liczba naturalna <math>n \geqslant 2</math> jest liczbą pierwszą lub iloczynem liczb pierwszych. | Każda liczba naturalna <math>n \geqslant 2</math> jest liczbą pierwszą lub iloczynem liczb pierwszych. | ||
Linia 384: | Linia 417: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C21" style="font-size: 110%; font-weight: bold;">Twierdzenie C21 (Euklides, IV w. p.n.e.)</span><br/> |
Istnieje nieskończenie wiele liczb pierwszych. | Istnieje nieskończenie wiele liczb pierwszych. | ||
{{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}} | ||
− | Przypuśćmy, że istnieje jedynie skończona ilość liczb pierwszych <math>p_1, p_2, \ldots, p_n</math> . Wtedy liczba <math>a = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1</math> jest większa od jedności i z twierdzenia | + | Przypuśćmy, że istnieje jedynie skończona ilość liczb pierwszych <math>p_1, p_2, \ldots, p_n</math> . Wtedy liczba <math>a = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1</math> jest większa od jedności i z twierdzenia [[#C20|C20]] wynika, że posiada dzielnik będący liczbą pierwszą, ale jak łatwo zauważyć żadna z liczb pierwszych <math>p_1, p_2, \ldots, p_n</math> nie jest dzielnikiem liczby <math>a</math>. Zatem istnieje liczba pierwsza <math>p</math> będąca dzielnikiem pierwszym liczby <math>a</math> i różna od każdej z liczb <math>p_1, p_2, \ldots, p_n</math>. Co kończy dowód.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 394: | Linia 427: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C22" style="font-size: 110%; font-weight: bold;">Twierdzenie C22</span><br/> |
Jeżeli liczba naturalna <math>n</math> jest postaci <math>4 k + 3</math><ref name="LiczbaJestPostaci"/>, to ma dzielnik postaci <math>4 k + 3</math> będący liczbą pierwszą. | Jeżeli liczba naturalna <math>n</math> jest postaci <math>4 k + 3</math><ref name="LiczbaJestPostaci"/>, to ma dzielnik postaci <math>4 k + 3</math> będący liczbą pierwszą. | ||
{{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>n</math> jest liczbą pierwszą, to twierdzenie jest dowiedzione. Zbadajmy zatem sytuację gdy <math>n</math> jest liczbą złożoną. Z założenia <math>n</math> jest liczbą nieparzystą, zatem możliwe są trzy typy iloczynów | + | Jeżeli <math>n</math> jest liczbą pierwszą, to twierdzenie jest dowiedzione. Zbadajmy zatem sytuację, gdy <math>n</math> jest liczbą złożoną. Z założenia <math>n</math> jest liczbą nieparzystą, zatem możliwe są trzy typy iloczynów |
::<math>(4 a + 1) (4 b + 1) = 16 a b + 4 a + 4 b + 1 = 4 (4 a b + a + b) + 1</math> | ::<math>(4 a + 1) (4 b + 1) = 16 a b + 4 a + 4 b + 1 = 4 (4 a b + a + b) + 1</math> | ||
Linia 412: | Linia 445: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C23" style="font-size: 110%; font-weight: bold;">Twierdzenie C23</span><br/> |
Istnieje nieskończenie wiele liczb pierwszych postaci <math>4 k + 3</math>. | Istnieje nieskończenie wiele liczb pierwszych postaci <math>4 k + 3</math>. | ||
Linia 420: | Linia 453: | ||
::<math>M = 4 p_1 \cdot \ldots \cdot p_s - 1 = 4 (p_1 \cdot \ldots \cdot p_s - 1) + 3</math> | ::<math>M = 4 p_1 \cdot \ldots \cdot p_s - 1 = 4 (p_1 \cdot \ldots \cdot p_s - 1) + 3</math> | ||
− | jest postaci <math>4 k + 3</math> i jak wiemy z twierdzenia | + | jest postaci <math>4 k + 3</math> i jak wiemy z twierdzenia [[#C22|C22]], ma dzielnik pierwszy <math>q</math> postaci <math>4 k + 3</math>. Ale jak łatwo zauważyć, żadna z liczb <math>p_1, \ldots, p_s</math> nie dzieli liczby <math>M</math>. Zatem istnieje liczba pierwsza <math>q</math> postaci <math>4 k + 3</math> różna od każdej z liczb <math>p_1, p_2, \ldots, p_s</math>. Otrzymana sprzeczność kończy dowód.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 426: | Linia 459: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C24" style="font-size: 110%; font-weight: bold;">Twierdzenie C24</span><br/> |
Jeżeli liczba naturalna <math>n</math> jest postaci <math>6 k + 5</math>, to ma dzielnik postaci <math>6 k + 5</math> będący liczbą pierwszą. | Jeżeli liczba naturalna <math>n</math> jest postaci <math>6 k + 5</math>, to ma dzielnik postaci <math>6 k + 5</math> będący liczbą pierwszą. | ||
{{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>n</math> jest liczbą pierwszą, to twierdzenie jest dowiedzione. Zbadajmy sytuację gdy <math>n</math> jest liczbą złożoną. Z twierdzenia | + | Jeżeli <math>n</math> jest liczbą pierwszą, to twierdzenie jest dowiedzione. Zbadajmy sytuację, gdy <math>n</math> jest liczbą złożoną. Z twierdzenia [[#C20|C20]] wiemy, że w tym przypadku liczba <math>n</math> będzie iloczynem liczb pierwszych. Zauważmy, że nieparzyste liczby pierwsze mogą być jedynie postaci <math>6 k + 1</math> lub <math>6 k + 5</math> (liczba <math>6 k + 3</math> jest liczbą złożoną). Ponieważ iloczyn liczb postaci <math>6 k + 1</math> |
::<math>(6 a + 1) (6 b + 1) = 36 a b + 6 a + 6 b + 1 = 6 (6 a b + a + b) + 1</math> | ::<math>(6 a + 1) (6 b + 1) = 36 a b + 6 a + 6 b + 1 = 6 (6 a b + a + b) + 1</math> | ||
Linia 440: | Linia 473: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C25" style="font-size: 110%; font-weight: bold;">Twierdzenie C25</span><br/> |
Istnieje nieskończenie wiele liczb pierwszych postaci <math>6 k + 5</math>. | Istnieje nieskończenie wiele liczb pierwszych postaci <math>6 k + 5</math>. | ||
Linia 448: | Linia 481: | ||
::<math>M = 6 p_1 \cdot \ldots \cdot p_s - 1 = 6 (p_1 \cdot \ldots \cdot p_s - 1) + 5</math> | ::<math>M = 6 p_1 \cdot \ldots \cdot p_s - 1 = 6 (p_1 \cdot \ldots \cdot p_s - 1) + 5</math> | ||
− | jest postaci <math>6 k + 5</math> i | + | jest postaci <math>6 k + 5</math> i ma dzielnik pierwszy <math>q</math> postaci <math>6 k + 5</math> (zobacz [[#C24|C24]]). Ale jak łatwo zauważyć żadna z liczb <math>p_1, \ldots, p_s</math> nie dzieli liczby <math>M</math>. Zatem istnieje liczba pierwsza <math>q</math> postaci <math>6 k + 5</math> różna od każdej z liczb <math>p_1, p_2, \ldots, p_s</math>. Otrzymana sprzeczność kończy dowód.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 454: | Linia 487: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C26" style="font-size: 110%; font-weight: bold;">Twierdzenie C26</span><br/> |
Istnieje nieskończenie wiele liczb pierwszych postaci <math>3 k + 2</math>. | Istnieje nieskończenie wiele liczb pierwszych postaci <math>3 k + 2</math>. | ||
Linia 468: | Linia 501: | ||
::<math>3 k + 2 = 3 (2 j + 1) + 2 = 6 j + 5</math> | ::<math>3 k + 2 = 3 (2 j + 1) + 2 = 6 j + 5</math> | ||
− | o którym wiemy, że zawiera nieskończenie wiele liczb pierwszych (zobacz twierdzenie | + | o którym wiemy, że zawiera nieskończenie wiele liczb pierwszych (zobacz twierdzenie [[#C25|C25]]). Zatem w ciągu arytmetycznym postaci <math>3 k + 2</math> występuje nieskończenie wiele liczb pierwszych.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 474: | Linia 507: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C27" style="font-size: 110%; font-weight: bold;">Uwaga C27</span><br/> |
Zauważmy, że liczby postaci <math>2 k + 1</math> to wszystkie liczby nieparzyste dodatnie. Ponieważ wszystkie liczby pierwsze (poza liczbą <math>2</math>) są liczbami nieparzystymi, to wśród liczb postaci <math>2 k + 1</math> występuje nieskończenie wiele liczb pierwszych. | Zauważmy, że liczby postaci <math>2 k + 1</math> to wszystkie liczby nieparzyste dodatnie. Ponieważ wszystkie liczby pierwsze (poza liczbą <math>2</math>) są liczbami nieparzystymi, to wśród liczb postaci <math>2 k + 1</math> występuje nieskończenie wiele liczb pierwszych. | ||
Linia 481: | Linia 514: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C28" style="font-size: 110%; font-weight: bold;">Twierdzenie C28* (Peter Gustav Lejeune Dirichlet, 1837)</span><br/> |
Niech <math>a \in \mathbb{Z}_+</math> i <math>b \in \mathbb{Z}</math>. Jeżeli liczby <math>a</math> i <math>b</math> są względnie pierwsze, to w ciągu arytmetycznym <math>a k + b</math> występuje nieskończenie wiele liczb pierwszych. | Niech <math>a \in \mathbb{Z}_+</math> i <math>b \in \mathbb{Z}</math>. Jeżeli liczby <math>a</math> i <math>b</math> są względnie pierwsze, to w ciągu arytmetycznym <math>a k + b</math> występuje nieskończenie wiele liczb pierwszych. | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C29" style="font-size: 110%; font-weight: bold;">Uwaga C29</span><br/> |
Dowód twierdzenia Dirichleta jest bardzo trudny. Natomiast bardzo łatwo można pokazać, że dowolny ciąg arytmetyczny <math>a k + b</math> zawiera nieskończenie wiele liczb złożonych. Istotnie, jeżeli liczby <math>a, b</math> nie są względnie pierwsze, to wszystkie wyrazy ciągu są liczbami złożonymi. Jeżeli <math>a, b</math> są względnie pierwsze i <math>b > 1 ,</math> to wystarczy przyjąć <math>k = b t</math>. Jeżeli są względnie pierwsze i <math>b = 1</math>, to wystarczy przyjąć <math>k = a t^2 + 2 t</math>, wtedy | Dowód twierdzenia Dirichleta jest bardzo trudny. Natomiast bardzo łatwo można pokazać, że dowolny ciąg arytmetyczny <math>a k + b</math> zawiera nieskończenie wiele liczb złożonych. Istotnie, jeżeli liczby <math>a, b</math> nie są względnie pierwsze, to wszystkie wyrazy ciągu są liczbami złożonymi. Jeżeli <math>a, b</math> są względnie pierwsze i <math>b > 1 ,</math> to wystarczy przyjąć <math>k = b t</math>. Jeżeli są względnie pierwsze i <math>b = 1</math>, to wystarczy przyjąć <math>k = a t^2 + 2 t</math>, wtedy | ||
Linia 493: | Linia 526: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C30" style="font-size: 110%; font-weight: bold;">Uwaga C30</span><br/> |
− | Wiemy już, że w przypadku gdy liczby <math>a</math> i <math>b</math> są względnie pierwsze, to w ciągu arytmetycznym <math>a k + b</math> występuje nieskończenie wiele liczb pierwszych. Pojawia się pytanie o to, czy możliwe jest oszacowanie najmniejszej liczby pierwszej <math>p</math> w takim ciągu. Jakkolwiek przypuszczamy, że prawdziwe jest oszacowanie <math>p < a^2</math>, to stan naszej obecnej wiedzy ujmuje twierdzenie Linnika<ref name="Linnik1"/><ref name="Linnik2"/><ref name="Linnik3"/><ref name="Linnik4"/>, które podajemy niżej. Trzeba było ponad pół wieku wysiłku wielu matematyków, aby pokazać, że w twierdzeniu Linnika możemy przyjąć <math>L = 5</math><ref name="Xylouris1"/>. | + | Wiemy już, że w przypadku gdy liczby <math>a</math> i <math>b</math> są względnie pierwsze, to w ciągu arytmetycznym <math>a k + b</math> występuje nieskończenie wiele liczb pierwszych. Pojawia się pytanie o to, czy możliwe jest oszacowanie najmniejszej liczby pierwszej <math>p</math> w takim ciągu. Jakkolwiek przypuszczamy, że prawdziwe jest oszacowanie <math>p < a^2</math>, to stan naszej obecnej wiedzy ujmuje twierdzenie Linnika<ref name="Linnik1"/><ref name="Linnik2"/><ref name="Linnik3"/><ref name="Linnik4"/>, które podajemy niżej. Trzeba było ponad pół wieku wysiłku wielu matematyków, aby pokazać, że w twierdzeniu Linnika możemy przyjąć <math>L = 5</math><ref name="Xylouris1"/>. Bombieri, Friedlander i Iwaniec udowodnili<ref name="Bombieri1"/>, że dla prawie wszystkich liczb <math>a</math> prawdziwe jest oszacowanie <math>L \leqslant 2</math>. |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C31" style="font-size: 110%; font-weight: bold;">Twierdzenie C31* (Jurij Linnik, 1944)</span><br/> Niech <math>a, b \in \mathbb{Z}_+</math> i <math>p_{\min} (a, b)</math> oznacza najmniejszą liczbę pierwszą w ciągu arytmetycznym <math>a k + b</math>, gdzie <math>k \in \mathbb{Z}_+</math>. Jeżeli <math>\gcd (a, b) = 1</math> i <math>b \in [1, a - 1]</math>, to istnieją takie stałe <math>L > 0</math> i <math>a_0 \geqslant 2</math>, że dla wszystkich <math>a > a_0</math> prawdziwe jest oszacowanie |
::<math>p_{\min} (a, b) < a^L</math> | ::<math>p_{\min} (a, b) < a^L</math> | ||
Linia 504: | Linia 537: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span id="C32" style="font-size: 110%; font-weight: bold;">Zadanie C32</span><br/> |
− | Pokazać, że | + | Pokazać, że z twierdzenia Linnika wynika istnienie takich stałych <math>c, L > 0</math>, że dla każdego <math>a \geqslant 2</math> prawdziwe jest oszacowanie |
− | + | ::<math>p(a) < c a^L</math> | |
− | |||
− | |||
− | |||
+ | gdzie | ||
+ | ::<math>p(a) = \underset{\gcd (a, b) = 1}{\max_{1 \leqslant b < a}} p_{\min} (a, b)</math> | ||
− | + | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | |
− | + | Oszacowanie podane w twierdzeniu Linnika | |
+ | ::<math>p_{\min} (a, b) < a^L</math> | ||
+ | jest prawdziwe dla dowolnej liczby <math>b \in [1, a - 1]</math> względnie pierwszej z <math>a</math>. Jeżeli zdefiniujemy funkcję | ||
− | + | ::<math>p(a) = \underset{\gcd (a, b) = 1}{\max_{1 \leqslant b < a}} p_{\min} (a, b)</math> | |
− | |||
− | |||
− | + | to możemy zapisać twierdzenie Linnika tak, aby po lewej stronie nie występowała liczba <math>b</math>, co czyni zapis bardziej przejrzystym. Mamy | |
− | + | ::<math>p(a) < a^L</math> | |
− | + | dla wszystkich <math>a > a_0</math>. Ponieważ dla <math>a \in [2, a_0]</math> funkcja <math>p(a)</math> przyjmuje wartości skończone, a dla <math>a > a_0</math> jest <math>p(a) < a^L</math>, to funkcja <math>{\small\frac{p (a)}{a^L}}</math> jest ograniczona od góry, czyli istnieje taka stała <math>c</math>, że | |
− | + | ::<math>{\small\frac{p (a)}{a^L}} < c</math> | |
− | + | dla dowolnego <math>a \geqslant 2</math>. Co należało pokazać.<br/> | |
+ | □ | ||
+ | {{\Spoiler}} | ||
− | <span style="font-size: 110%; font-weight: bold;"> | + | <span id="C33" style="font-size: 110%; font-weight: bold;">Przykład C33</span><br/> |
− | + | Pokazaliśmy (zobacz [[#C32|C32]]), że istnieją takie stałe <math>c, L > 0</math>, że dla każdego <math>a \geqslant 2</math> prawdziwe jest oszacowanie | |
− | + | ::<math>p(a) < c a^L</math> | |
− | |||
− | + | gdzie | |
− | |||
− | |||
− | ::<math>( | + | ::<math>p(a) = \underset{\gcd (a, b) = 1}{\max_{1 \leqslant b < a}} p_{\min} (a, b)</math> |
− | |||
− | + | Ponieważ <math>p(a) > a</math>, to prawdziwy jest ciąg nierówności | |
− | |||
− | ::<math> | + | ::<math>1 < {\small\frac{\log p (a)}{\log a}} < {\small\frac{\log c}{\log a}} + L \leqslant \left| {\small\frac{\log c}{\log a}} \right| + |
− | + | L \leqslant {\small\frac{\left| \log c \right|}{\log 2}} + L</math> | |
− | + | Wynika stąd, że dla <math>a \geqslant 2</math> funkcja <math>{\small\frac{\log p (a)}{\log a}}</math> jest ograniczona. | |
− | |||
− | + | Na zamieszczonym niżej obrazku przedstawiono pierwszych czternaście punktów funkcji <math>{\small\frac{\log p (a)}{\log a}}</math>. Ze względu na skokowy charakter zmian tej funkcji najwygodniej będzie przedstawić jej wykres, pokazując jedynie jej maksymalne i minimalne wartości w wybranych podprzedziałach <math>\mathbb{Z}_+</math>. Mówiąc precyzyjnie, zamieszczone zostały wykresy funkcji | |
− | + | ::<math>f(t) = \max_{2^t \leqslant a < 2^{t + 1}} {\small\frac{\log p (a)}{\log a}} \qquad \qquad \qquad \qquad g(t) = \min_{2^t \leqslant a < 2^{t + 1}} {\small\frac{\log p (a)}{\log a}} \qquad \qquad \qquad \qquad h(a) = 1 + {\small\frac{2 \log \log a}{\log a}}</math> | |
− | + | gdzie <math>t \in \mathbb{Z}_+</math>. | |
− | + | ::[[File: Linnik-22.png|950px|none]] | |
− | |||
− | |||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod i dane do wykresu|Hide=Ukryj kod i dane do wykresu}} | ||
+ | W tabeli przedstawiamy dane, na podstawie których sporządziliśmy zamieszczony wyżej wykres. Mamy kolejno | ||
+ | :* przedział <math>U</math> | ||
+ | :* minimalną wartość <math>{\small\frac{\log p(a)}{\log a}}</math> w przedziale <math>U</math> | ||
+ | :* liczbę <math>a</math>, która odpowiada minimalnej wartości <math>{\small\frac{\log p(a)}{\log a}}</math> | ||
+ | :* wartość <math>p(a) = \underset{\gcd (a, b) = 1}{\max_{1 \leqslant b < a}} p_{\min} (a, b)</math> | ||
+ | :* liczbę <math>b</math> taką, że najmniejsza liczba pierwsza w ciągu <math>a k + b</math> jest równa <math>p ( a )</math> | ||
+ | Następnie podajemy analogiczne wartości dla maksymalnej wartości <math>{\small\frac{\log p(a)}{\log a}}</math> w przedziale <math>U</math>. Pominęliśmy dane dla początkowych przedziałów <math>[2^{n},2^{n + 1})</math>, ponieważ Czytelnik z łatwością policzy je samodzielnie. Prosty kod do obliczeń w PARI/GP zamieściliśmy pod tabelą. | ||
− | + | ::{| class="wikitable plainlinks" style="font-size: 85%; text-align: right; margin-right: auto;" | |
− | + | |- | |
+ | ! <math>\boldsymbol{U}</math> || <math>\boldsymbol{\min_{a \in U} {\small\frac{\log p(a)}{\log a}}}</math> || <math>\boldsymbol{a}</math> || <math>\boldsymbol{p(a)}</math> || <math>\boldsymbol{b}</math> || <math>\boldsymbol{\max_{a \in U} {\small\frac{\log p(a)}{\log a}}}</math> || <math>\boldsymbol{a}</math> || <math>\boldsymbol{p(a)}</math> || <math>\boldsymbol{b}</math> | ||
+ | |- | ||
+ | | <math>[2^{12},2^{13})</math> || <math>1.273691</math> || <math>6840</math> || <math>76679</math> || <math>1439</math> || <math>1.574826</math> || <math>4177</math> || <math>503771</math> || <math>2531</math> | ||
+ | |- | ||
+ | | <math>[2^{13},2^{14})</math> || <math>1.265227</math> || <math>14490</math> || <math>183949</math> || <math>10069</math> || <math>1.551307</math> || <math>8941</math> || <math>1348387</math> || <math>7237</math> | ||
+ | |- | ||
+ | | <math>[2^{14},2^{15})</math> || <math>1.257880</math> || <math>20790</math> || <math>269987</math> || <math>20507</math> || <math>1.519764</math> || <math>22133</math> || <math>4012709</math> || <math>6636</math> | ||
+ | |- | ||
+ | | <math>[2^{15},2^{16})</math> || <math>1.247285</math> || <math>39270</math> || <math>537157</math> || <math>26647</math> || <math>1.500736</math> || <math>40951</math> || <math>8352037</math> || <math>38984</math> | ||
+ | |- | ||
+ | | <math>[2^{16},2^{17})</math> || <math>1.244884</math> || <math>106260</math> || <math>1808207</math> || <math>1787</math> || <math>1.477806</math> || <math>84229</math> || <math>19005359</math> || <math>53834</math> | ||
+ | |- | ||
+ | | <math>[2^{17},2^{18})</math> || <math>1.243658</math> || <math>150150</math> || <math>2740469</math> || <math>37769</math> || <math>1.474387</math> || <math>132331</math> || <math>35588503</math> || <math>123795</math> | ||
+ | |- | ||
+ | | <math>[2^{18},2^{19})</math> || <math>1.233771</math> || <math>510510</math> || <math>11024723</math> || <math>304013</math> || <math>1.457138</math> || <math>297491</math> || <math>94537921</math> || <math>233274</math> | ||
+ | |- | ||
+ | | <math>[2^{19},2^{20})</math> || <math>1.233150</math> || <math>1021020</math> || <math>25706531</math> || <math>181031</math> || <math>1.437418</math> || <math>596081</math> || <math>200230391</math> || <math>543256</math> | ||
+ | |- | ||
+ | | <math>[2^{20},2^{21})</math> || <math>1.231259</math> || <math>2072070</math> || <math>59859383</math> || <math>1841423</math> || <math>1.419752</math> || <math>1181311</math> || <math>418069567</math> || <math>1066784</math> | ||
+ | |- | ||
+ | | <math>[2^{21},2^{22})</math> || <math>1.224444</math> || <math>3543540</math> || <math>104573173</math> || <math>1810513</math> || <math>1.405843</math> || <math>2753747</math> || <math>1131160207</math> || <math>2123937</math> | ||
+ | |} | ||
− | :: | + | <span style="font-size: 90%; color:black;">pmin(a, b) = |
+ | \\ zwraca najmniejszą liczbę pierwszą w ciągu a*k + b, gdzie k >= 1 i gcd(a, b) = 1 | ||
+ | { | ||
+ | '''local'''(k, p); | ||
+ | k = 1; | ||
+ | p = a*k + b; | ||
+ | '''while'''( !'''isprime'''(p), p = a*(k++) + b ); | ||
+ | '''return'''(p); | ||
+ | }</span> | ||
− | + | <span style="font-size: 90%; color:black;">PMAX(a) = | |
+ | \\ zwraca największą ze wszystkich najmniejszych liczb pierwszych | ||
+ | \\ w ciągach a*k + b, gdzie k >= 1, 0 < b < a i gcd(a, b) = 1 | ||
+ | { | ||
+ | '''local'''(b, p, w); | ||
+ | w = [0, 0]; | ||
+ | b = 0; | ||
+ | '''while'''( b++ < a, | ||
+ | '''if'''( '''gcd'''(a, b) > 1, '''next'''() ); | ||
+ | p = pmin(a, b); | ||
+ | '''if'''( w[1] < p, w = [p, b] ); | ||
+ | ); | ||
+ | '''return'''(w); | ||
+ | }</span> | ||
− | + | <span style="font-size: 90%; color:black;">Linnik(n) = | |
+ | \\ n >= 1, sprawdzamy przedział U = [ 2^n , 2^(n + 1) ), czyli 2^n <= a < 2^(n+1) | ||
+ | { | ||
+ | '''local'''(a, b, p4a, sep, txt, w, y, Ymin, Ymax); | ||
+ | sep = ", "; \\ separator | ||
+ | Ymin = [100, 1, 0, 0]; \\ najmniejsza wartość funkcji log( p(a) ) / log(a) w przedziale U | ||
+ | Ymax = [0, 1, 0, 0]; \\ największa wartość funkcji log( p(a) ) / log(a) w przedziale U | ||
+ | a = 2^n - 1; | ||
+ | '''while'''( a++ < 2^(n+1), | ||
+ | w = PMAX(a); | ||
+ | p4a = w[1]; | ||
+ | b = w[2]; | ||
+ | y = '''log'''(p4a) / '''log'''(a); | ||
+ | if( y < Ymin[1], Ymin = [y, a, p4a, b] ); | ||
+ | if( y > Ymax[1], Ymax = [y, a, p4a, b] ); | ||
+ | ); | ||
+ | txt = '''Str'''(n, sep, Ymin[1], sep, Ymin[2], sep, Ymin[3], sep, Ymin[4], sep, Ymax[1], sep, Ymax[2], sep, Ymax[3], sep, Ymax[4]); | ||
+ | '''print'''(txt); | ||
+ | }</span> | ||
+ | {{\Spoiler}} | ||
+ | Przypuszczamy, że prawdziwe jest znacznie silniejsze oszacowanie najmniejszej liczby pierwszej w ciągu arytmetycznym<ref name="Turan1"/><ref name="Wagstaff1"/> | ||
+ | ::<math>p(a) \sim a \log^2 \! a</math> | ||
− | + | W takim przypadku mielibyśmy | |
− | |||
− | + | ::<math>{\small\frac{\log p (a)}{\log a}} \sim 1 + {\small\frac{2 \log \log a}{\log a}}</math> | |
− | |||
− | + | Rzeczywiście, porównanie wykresów funkcji <math>f(t)</math> i <math>h(a)</math> wydaje się potwierdzać to przypuszczenie dla <math>a \in [2, 2^{22}]</math>. | |
− | |||
− | |||
− | + | W tabeli zestawiliśmy wszystkie wartości funkcji <math>{\small\frac{\log p (a)}{\log a}}</math> większe od <math>1.75</math> dla <math>a \in [2, 2^{22}]</math> | |
− | : | + | ::{| class="wikitable plainlinks" style="font-size: 80%; text-align: center; margin-right: auto;" |
+ | |- | ||
+ | ! <math>\boldsymbol{a}</math> || <math>\boldsymbol{\log_2 \! a}</math> || <math>\boldsymbol{p(a)}</math> || <math>\boldsymbol{{\small\frac{\log p(a)}{\log a}}}</math> | ||
+ | |- | ||
+ | | <math>31</math> || <math>4.95</math> || <math>577</math> || <math>1.851446</math> | ||
+ | |- | ||
+ | | <math>5</math> || <math>2.32</math> || <math>19</math> || <math>1.829482</math> | ||
+ | |- | ||
+ | | <math>13</math> || <math>3.70</math> || <math>103</math> || <math>1.806947</math> | ||
+ | |- | ||
+ | | <math>47</math> || <math>5.55</math> || <math>967</math> || <math>1.785437</math> | ||
+ | |- | ||
+ | | <math>19</math> || <math>4.24</math> || <math>191</math> || <math>1.783794</math> | ||
+ | |- | ||
+ | | <math>61</math> || <math>5.93</math> || <math>1511</math> || <math>1.780771</math> | ||
+ | |- | ||
+ | | <math>11</math> || <math>3.46</math> || <math>71</math> || <math>1.777675</math> | ||
+ | |- | ||
+ | | <math>3</math> || <math>1.58</math> || <math>7</math> || <math>1.771243</math> | ||
+ | |} | ||
− | |||
− | |||
− | |||
− | + | Rozważmy zbiór <math>S</math> takich liczb <math>a</math>, że prawdziwe jest oszacowanie <math>p (a) < a \log^2 \! a</math>. Bez trudu możemy podać przykłady takich liczb, ale nie wiemy, czy jest ich nieskończenie wiele. | |
+ | ::{| class="wikitable plainlinks" style="font-size: 80%; text-align: center; margin-right: auto;" | ||
+ | |- | ||
+ | ! <math>\boldsymbol{n}</math> || <math>\boldsymbol{a=p_1 \cdot \ldots \cdot p_n}</math> || <math>\boldsymbol{\log_2 \! a}</math> || <math>\boldsymbol{p(a)}</math> || <math>\boldsymbol{{\small\frac{a \log^2 \! a}{p(a)}}}</math> || <math>\boldsymbol{{\small\frac{\log p(a)}{\log a}}}</math> | ||
+ | |- | ||
+ | | <math>2</math> || <math>6</math> || <math>2.584</math> || <math>11</math> || <math>1.751</math> || <math>1.338290</math> | ||
+ | |- | ||
+ | | <math>3</math> || <math>30</math> || <math>4.906</math> || <math>79</math> || <math>4.392</math> || <math>1.284679</math> | ||
+ | |- | ||
+ | | <math>4</math> || <math>210</math> || <math>7.714</math> || <math>761</math> || <math>7.889</math> || <math>1.240789</math> | ||
+ | |- | ||
+ | | <math>5</math> || <math>2310</math> || <math>11.173</math> || <math>20477</math> || <math>6.766</math> || <math>1.281737</math> | ||
+ | |- | ||
+ | | <math>6</math> || <math>30030</math> || <math>14.874</math> || <math>520547</math> || <math>6.132</math> || <math>1.276692</math> | ||
+ | |- | ||
+ | | <math>7</math> || <math>510510</math> || <math>18.961</math> || <math>11024723</math> || <math>7.999</math> || <math>1.233770</math> | ||
+ | |- | ||
+ | | <math>8</math> || <math>9699690</math> || <math>23.209</math> || <math>375095881</math> || <math>6.692</math> || <math>1.227199</math> | ||
+ | |- | ||
+ | | <math>9</math> || <math>223092870</math> || <math>27.733</math> || <math>11799966613</math> || <math>6.986</math> || <math>1.206432</math> | ||
+ | |- | ||
+ | | <math>10</math> || <math>6469693230</math> || <math>32.591</math> || <math>451404994867</math> || <math>7.314</math> || <math>1.187922</math> | ||
+ | |- | ||
+ | | <math>11</math> || <math>200560490130</math> || <math>37.545</math> || <math>19822720510961</math> || <math>6.852</math> || <math>1.176506</math> | ||
+ | |- | ||
+ | | <math>12</math> || <math>7420738134810</math> || <math>42.754</math> || <math></math> || <math></math> || <math></math> | ||
+ | |} | ||
+ | |||
+ | |||
+ | Ponieważ <math>p(a) > a</math>, to prawdziwy jest układ nierówności | ||
+ | |||
+ | ::<math>1 < {\small\frac{\log p (a)}{\log a}} < 1 + {\small\frac{2 \log \log a}{\log a}}</math> | ||
+ | |||
+ | Jeżeli zbiór <math>S</math> jest nieskończony, to z twierdzenia o trzech ciągach otrzymujemy | ||
+ | |||
+ | ::<math>\underset{a \in S}{\lim_{a \rightarrow \infty}} {\small\frac{\log p (a)}{\log a}} = 1</math> | ||
+ | |||
+ | W konsekwencji wykres funkcji | ||
+ | |||
+ | ::<math>g(t) = \underset{2^t \leqslant a < 2^{t + 1}}{\min} {\small\frac{\log p (a)}{\log a}}</math> | ||
+ | |||
+ | będzie opadał ku prostej <math>y = 1</math>. | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C34" style="font-size: 110%; font-weight: bold;">Zadanie C34</span><br/> | ||
+ | Pokazać, że istnieje nieskończenie wiele liczb pierwszych zakończonych cyframi 99, przykładowo 199, 499, 599, 1399, 1499, ... | ||
+ | |||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
+ | Wszystkie liczby naturalne zakończone cyframi <math>99</math> możemy zapisać w postaci <math>a_n = 100 k + 99</math>, gdzie <math>k \in \mathbb{N}</math>. Ponieważ ciąg <math>(a_n)</math> jest ciągiem arytmetycznym, a liczby <math>99</math> i <math>100</math> są względnie pierwsze, to na podstawie twierdzenia Dirichleta stwierdzamy, że istnieje nieskończenie wiele liczb pierwszych zakończonych cyframi <math>99</math>.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C35" style="font-size: 110%; font-weight: bold;">Definicja C35</span><br/> | ||
+ | Niech <math>a \geqslant 2</math> będzie liczbą całkowitą. Wartość funkcji <math>\pi(n; a, b)</math> jest równa ilości liczb pierwszych nie większych od <math>n</math>, które przy dzieleniu przez <math>a</math> dają resztę <math>b</math>. | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C36" style="font-size: 110%; font-weight: bold;">Uwaga C36</span><br/> | ||
+ | Zauważmy, że w twierdzeniu Dirichleta na liczby <math>a</math> oraz <math>b</math> nałożone są minimalne warunki: <math>a \in \mathbb{Z}_+</math> i <math>b \in \mathbb{Z}</math>. Sytuacja w przypadku funkcji <math>\pi (n ; a, b)</math> jest odmienna – tutaj mamy <math>a \geqslant 2</math> oraz <math>0 \leqslant b \leqslant a - 1</math>. Jest tak dlatego, że podział liczb pierwszych, który odzwierciedla funkcja <math>\pi (n ; a, b)</math>, jest podziałem pierwotnym, a twierdzenie Dirichleta jest tylko jego uzasadnieniem. Podział | ||
+ | liczb pierwszych musi być też precyzyjnie określony, tak aby zachodził naturalny związek | ||
+ | |||
+ | ::<math>\sum_{b = 0}^{a - 1} \pi (n ; a, b) = \pi (n)</math> | ||
+ | |||
+ | Oczywiście nie przeszkadza to w liczeniu liczb pierwszych w dowolnym ciągu arytmetycznym. Niech na przykład | ||
+ | |||
+ | ::<math>u_k = 7 k + 101 = 7 (k + 14) + 3 \qquad</math> gdzie <math>k = 0, 1, \ldots</math> | ||
+ | |||
+ | Ilość liczb pierwszych w ciagu <math>(u_k)</math> jest równa | ||
+ | |||
+ | ::<math>\pi (n ; 7, 3) - \pi (7 \cdot 13 + 3 ; 7, 3) = \pi (n ; 7, 3) - 5</math> | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C37" style="font-size: 110%; font-weight: bold;">Zadanie C37</span><br/> | ||
+ | Pokazać, że dla dowolnej liczby całkowitej <math>m \geqslant 1</math> | ||
+ | |||
+ | * wśród liczb naturalnych zawsze można wskazać <math>m</math> kolejnych liczb, które są złożone | ||
+ | * w ciągu arytmetycznym <math>a k + b</math>, gdzie liczby <math>a</math> i <math>b</math> są względnie pierwsze, zawsze można wskazać <math>m</math> kolejnych wyrazów, które są złożone | ||
+ | |||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
+ | '''Punkt 1.'''<br/> | ||
+ | W przypadku liczb naturalnych łatwo widzimy, że kolejne liczby | ||
+ | |||
+ | ::<math>(m + 1) ! + 2, \quad (m + 1) ! + 3, \quad \ldots, \quad (m + 1) ! + (m + 1)</math> | ||
+ | |||
+ | są liczbami złożonymi. Co oznacza, że dla dowolnej liczby naturalnej <math>m</math> zawsze możemy wskazać taką liczbę <math>n</math>, że <math>p_{n + 1} - p_n > m</math>. | ||
+ | |||
+ | '''Punkt 2.'''<br/> | ||
+ | W przypadku ciągu arytmetycznego <math>u_k = a k + b</math> rozważmy kolejne wyrazy ciągu począwszy od wskaźnika | ||
+ | |||
+ | ::<math>k_0 = \prod^{m - 1}_{j = 0} (a j + b)</math> | ||
+ | |||
+ | Łatwo zauważamy, że dla <math>k = k_0, k_0 + 1, \ldots, k_0 + (m - 1)</math> wyrazy ciągu arytmetycznego <math>u_k = a k + b</math> są liczbami złożonymi. Istotnie, niech <math>t = 0, 1, \ldots, m - 1</math> wtedy | ||
+ | |||
+ | ::<math>u_k = a k + b =</math> | ||
+ | |||
+ | :::<math>\! = a (k_0 + t) + b =</math> | ||
+ | |||
+ | :::<math>\! = a k_0 + (a t + b) =</math> | ||
+ | |||
+ | :::<math>\! = a \prod^{m - 1}_{j = 0} (a j + b) + (a t + b)</math> | ||
+ | |||
+ | i liczba <math>a t + b</math> dzieli iloczyn <math>\prod^{m - 1}_{j = 0} (a j + b)</math> dla <math>t = 0, \ldots, m - 1</math>. Co należało pokazać. | ||
+ | |||
+ | Wiemy, że jeżeli liczby <math>a</math> i <math>b</math> są względnie pierwsze, to w ciągu <math>a k + b</math> występuje nieskończenie wiele liczb pierwszych. Niech będą to liczby <math>q_1, q_2, \ldots, q_r, \ldots</math>. Uzyskany rezultat oznacza, że dla dowolnej liczby naturalnej <math>m</math> zawsze możemy wskazać taką liczbę <math>n</math>, że <math>q_{n + 1} - q_n \geqslant a (m + 1)</math><br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C38" style="font-size: 110%; font-weight: bold;">Przykład C38</span><br/> | ||
+ | Rozważmy ciąg arytmetyczny <math>u_k = 3 k + 2</math> i wskaźnik | ||
+ | |||
+ | ::<math>k_0 = \prod^{12}_{j = 0} (3 j + 2) = 3091650738176000</math> | ||
+ | |||
+ | Trzynaście wyrazów tego szeregu dla <math>k = k_0 + t</math>, gdzie <math>t = 0, 1, \ldots, 12</math> to oczywiście liczby złożone, ale wyrazy dla <math>k = k_0 - 1</math> i <math>k = k_0 + 13</math> są liczbami pierwszymi. | ||
+ | |||
+ | Przeszukując ciąg <math>u_k = 3 k + 2</math>, możemy łatwo znaleźć, że pierwsze trzynaście kolejnych wyrazów złożonych pojawia się już dla <math>k = 370, 371, \ldots, 382</math>. | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C39" style="font-size: 110%; font-weight: bold;">Twierdzenie C39</span><br/> | ||
+ | Jeżeli <math>n \geqslant 3</math>, to istnieje <math>n</math> kolejnych liczb naturalnych, wśród których znajduje się dokładnie <math>r \leqslant \pi (n)</math> liczb pierwszych. | ||
+ | |||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
+ | Warunek <math>n \geqslant 3</math> nie wynika z potrzeb dowodu, a jedynie pomija sytuacje nietypowe, których twierdzenie nie obejmuje. Zawsze istnieje jedna liczba naturalna, która jest liczbą pierwszą i łatwo możemy wskazać dwie kolejne liczby naturalne będące liczbami pierwszymi. | ||
+ | |||
+ | Niech <math>k \in \mathbb{N}</math>. Wartość funkcji | ||
+ | |||
+ | ::<math>Q(k, n) = \pi (k + n) - \pi (k)</math> | ||
+ | |||
+ | jest równa ilości liczb pierwszych wśród <math>n</math> kolejnych liczb naturalnych od liczby <math>k + 1</math> do liczby <math>k + n</math>. | ||
+ | |||
+ | Uwzględniając, że wypisane niżej wyrażenia w nawiasach kwadratowych mogą przyjmować jedynie dwie wartości <math>0</math> lub <math>1</math>, dostajemy | ||
+ | |||
+ | :* <math>\biggl| Q (k + 1, n) - Q (k, n) \biggr| = \biggl| \bigl[\pi (k + n + 1) - \pi (k + n) \bigr] - \bigl[\pi (k + 1) - \pi (k) \bigr] \biggr| \leqslant 1</math> | ||
+ | |||
+ | Ponadto mamy | ||
+ | |||
+ | :* <math>Q(0, n) = \pi (n) \qquad</math> bo <math>\pi (0) = 0</math> | ||
+ | :* <math>Q((n + 1) ! + 1, n) = 0 \qquad</math> bo liczby <math>(n + 1) ! + 2, \ldots, (n + 1) ! + (n + 1)</math> są liczbami złożonymi | ||
+ | |||
+ | Ponieważ wartości funkcji <math>Q(k, n)</math> mogą zmieniać się tylko o <math>- 1</math>, <math>0</math> lub <math>1</math>, to <math>Q(k, n)</math> musi przyjmować '''wszystkie''' wartości całkowite od <math>0</math> do <math>\pi (n)</math>. Wynika stąd, że istnieje taka liczba <math>k_r</math>, że <math>Q(k_r, n) = r</math>, gdzie <math>0 \leqslant r \leqslant \pi (n)</math>. | ||
+ | |||
+ | |||
+ | ::[[File: C_Q10.png|none]] | ||
+ | |||
+ | Fragment wykresu funkcji <math>Q(k, 10)</math>. Widzimy, że dla <math>k = 113</math> po raz pierwszy mamy <math>Q(k, 10) = 0</math>, a funkcja <math>Q(k, 10)</math> przyjmuje wszystkie wartości całkowite od <math>0</math> do <math>5</math>.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C40" style="font-size: 110%; font-weight: bold;">Przykład C40</span><br/> | ||
+ | Czytelnik może łatwo sprawdzić, że ciąg <math>( 1308, \ldots, 1407 )</math> stu kolejnych liczb całkowitych zawiera dokładnie <math>8</math> liczb pierwszych. | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C41" style="font-size: 110%; font-weight: bold;">Zadanie C41</span><br/> | ||
+ | Pokazać, nie korzystając z twierdzenia [[#C39|C39]], że istnieje <math>1000</math> kolejnych liczb naturalnych, wśród których jest dokładnie jedna liczba pierwsza. | ||
+ | |||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
+ | Zauważmy, że <math>1000</math> kolejnych liczb naturalnych | ||
+ | |||
+ | ::<math>1001! + 2, 1001! + 3, \ldots, 1001! + 1001</math> | ||
+ | |||
+ | nie zawiera żadnej liczby pierwszej. Wielokrotnie zmniejszając wszystkie wypisane wyżej liczby o jeden, aż do chwili, gdy pierwsza z wypisanych liczb będzie liczbą pierwszą, uzyskamy <math>1000</math> kolejnych liczb naturalnych, wśród których jest dokładnie jedna liczba pierwsza. | ||
+ | |||
+ | Uwaga: dopiero liczba <math>1001! - 1733</math> jest pierwsza.<br/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
+ | |||
+ | |||
+ | |||
+ | <span id="C42" style="font-size: 110%; font-weight: bold;">Zadanie C42</span><br/> | ||
+ | Pokazać, że istnieje <math>20</math> kolejnych liczb naturalnych postaci <math>6 k + 1</math>, wśród których jest dokładnie <math>5</math> liczb pierwszych. | ||
+ | |||
+ | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
+ | Rozwiązywanie zadania rozpoczniemy od dwóch spostrzeżeń | ||
+ | |||
+ | :* wśród pierwszych <math>20</math> liczb naturalnych postaci <math>6 k + 1</math> jest <math>13</math> liczb pierwszych | ||
+ | :* w ciągu <math>6 k + 1</math> istnieją dowolnie długie przedziały pozbawione liczb pierwszych (zobacz zadanie [[#C37|C37]]), zatem istnieje <math>20</math> kolejnych liczb naturalnych postaci <math>6 k + 1</math>, wśród których nie ma ani jednej liczby pierwszej | ||
+ | |||
+ | Pierwsze spostrzeżenie pokazuje, że rozwiązanie problemu jest potencjalnie możliwe. Rozwiązanie mogłoby nie istnieć, gdybyśmy szukali <math>20</math> liczb naturalnych postaci <math>6 k + 1</math>, wśród których jest, powiedzmy, <math>15</math> liczb pierwszych. | ||
+ | |||
+ | Drugie spostrzeżenie mówi nam, że ilość liczb pierwszych wśród kolejnych <math>20</math> liczb naturalnych postaci <math>6 k + 1</math> zmienia się od <math>13</math> do <math>0</math>. Analiza przebiegu tych zmian jest kluczem do dowodu twierdzenia. | ||
+ | |||
+ | |||
+ | Zbadajmy zatem, jak zmienia się ilość liczb pierwszych wśród kolejnych <math>20</math> liczb naturalnych postaci <math>6 k + 1</math>. Rozważmy ciąg <math>a_k = 6 k + 1</math>, gdzie <math>k = 0, 1, 2, \ldots</math> | ||
+ | |||
+ | <math>(a_k) = (1, \mathbf{7}, \mathbf{13}, \mathbf{19}, 25, \mathbf{31}, \mathbf{37}, \mathbf{43}, 49, 55, \mathbf{61}, \mathbf{67}, \mathbf{73}, \mathbf{79}, 85, 91, \mathbf{97}, \mathbf{103}, \mathbf{109}, 115, 121, \mathbf{127}, 133, \mathbf{139}, 145, \mathbf{151}, \mathbf{157}, \mathbf{163}, 169, 175, \mathbf{181}, 187, \mathbf{193}, \mathbf{199}, 205, \mathbf{211}, \ldots)</math> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Liczby pierwsze zostały pogrubione. | Liczby pierwsze zostały pogrubione. | ||
Linia 678: | Linia 934: | ||
− | Wynika stąd, że przechodząc od ciągu <math>(B^n)</math> do ciągu <math>(B^{n + 1})</math> ilość liczb pierwszych może się zmienić o <math>- 1</math>, <math>0</math> lub <math>1</math>. Z drugiego ze spostrzeżeń uczynionych na początku dowodu wynika istnienie takiej liczby <math>r</math>, że wśród ciągów | + | Wynika stąd, że przechodząc od ciągu <math>(B^n)</math> do ciągu <math>(B^{n + 1})</math>, ilość liczb pierwszych może się zmienić o <math>- 1</math>, <math>0</math> lub <math>1</math>. Z drugiego ze spostrzeżeń uczynionych na początku dowodu wynika istnienie takiej liczby <math>r</math>, że wśród ciągów |
::<math>(B^1), (B^2), \ldots, (B^r)</math> | ::<math>(B^1), (B^2), \ldots, (B^r)</math> | ||
Linia 688: | Linia 944: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C43" style="font-size: 110%; font-weight: bold;">Twierdzenie C43</span><br/> |
Niech <math>a, b \in \mathbb{Z}</math> oraz <math>a \geqslant 2</math> i <math>0 \leqslant b \leqslant a - 1</math>. Jeżeli liczby <math>a</math> oraz <math>b</math> są względnie pierwsze, to istnieje <math>n</math> kolejnych liczb postaci <math>a k + b</math>, wśród których znajduje się dokładnie <math>r \leqslant \pi (a (n - 1) + b ; a, b)</math> liczb pierwszych. | Niech <math>a, b \in \mathbb{Z}</math> oraz <math>a \geqslant 2</math> i <math>0 \leqslant b \leqslant a - 1</math>. Jeżeli liczby <math>a</math> oraz <math>b</math> są względnie pierwsze, to istnieje <math>n</math> kolejnych liczb postaci <math>a k + b</math>, wśród których znajduje się dokładnie <math>r \leqslant \pi (a (n - 1) + b ; a, b)</math> liczb pierwszych. | ||
{{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}} | ||
− | Twierdzenie można udowodnić uogólniając dowód twierdzenia | + | Twierdzenie można udowodnić, uogólniając dowód twierdzenia [[#C39|C39]] lub wykorzystując metodę zastosowaną w rozwiązaniu zadania [[#C42|C42]].<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 698: | Linia 954: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span id="C44" style="font-size: 110%; font-weight: bold;">Zadanie C44</span><br/> |
Niech <math>p \geqslant 5</math> będzie liczbą pierwszą. Pokazać, że w ciągu <math>6 k + 1</math> występują kwadraty wszystkich liczb pierwszych <math>p</math>. | Niech <math>p \geqslant 5</math> będzie liczbą pierwszą. Pokazać, że w ciągu <math>6 k + 1</math> występują kwadraty wszystkich liczb pierwszych <math>p</math>. | ||
Linia 714: | Linia 970: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span id="C45" style="font-size: 110%; font-weight: bold;">Zadanie C45</span><br/> |
Dany jest ciąg arytmetyczny <math>a k + b</math>, gdzie liczby <math>a</math> i <math>b</math> są względnie pierwsze. Pokazać, że | Dany jest ciąg arytmetyczny <math>a k + b</math>, gdzie liczby <math>a</math> i <math>b</math> są względnie pierwsze. Pokazać, że | ||
Linia 722: | Linia 978: | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
'''Punkt 1.'''<br/> | '''Punkt 1.'''<br/> | ||
− | Zauważmy, że liczby <math>a</math> i <math>b</math> są względnie pierwsze, zatem liczba pierwsza <math>p</math> nie może jednocześnie dzielić liczb <math>a</math> i <math>b</math>. Ponieważ z założenia <math>p | + | Zauważmy, że liczby <math>a</math> i <math>b</math> są względnie pierwsze, zatem liczba pierwsza <math>p</math> nie może jednocześnie dzielić liczb <math>a</math> i <math>b</math>. Ponieważ z założenia <math>p \mid a</math>, to wynika stąd, że <math>p</math> nie dzieli <math>b</math>. Jeśli tak, to |
::<math>a k + b = (n p) k + b</math> | ::<math>a k + b = (n p) k + b</math> | ||
Linia 732: | Linia 988: | ||
Niech <math>k_0 \in \mathbb{N}</math>. Przypuśćmy, że dla pewnych różnych liczb naturalnych <math>i, j</math> takich, że <math>1 \leqslant i < j \leqslant p</math> liczby <math>a(k_0 + i) + b</math> oraz <math>a(k_0 + j) + b</math> dają tę samą resztę przy dzieleniu przez liczbę pierwszą <math>p</math>. Zatem różnica tych liczb jest podzielna przez <math>p</math> | Niech <math>k_0 \in \mathbb{N}</math>. Przypuśćmy, że dla pewnych różnych liczb naturalnych <math>i, j</math> takich, że <math>1 \leqslant i < j \leqslant p</math> liczby <math>a(k_0 + i) + b</math> oraz <math>a(k_0 + j) + b</math> dają tę samą resztę przy dzieleniu przez liczbę pierwszą <math>p</math>. Zatem różnica tych liczb jest podzielna przez <math>p</math> | ||
− | ::<math>p | + | ::<math>p \mid [a (k_0 + j) + b] - [a (k_0 + i) + b]</math> |
czyli | czyli | ||
− | ::<math>p | + | ::<math>p \mid a (j - i)</math> |
− | Ponieważ <math>p \nmid a</math> to na mocy lematu Euklidesa (twierdzenie | + | Ponieważ <math>p \nmid a</math> to na mocy lematu Euklidesa (twierdzenie [[#C75|C75]]), mamy |
− | ::<math>p | + | ::<math>p \mid (j - i)</math> |
co jest niemożliwe, bo <math>1 \leqslant j - i \leqslant p - 1 < p</math>. | co jest niemożliwe, bo <math>1 \leqslant j - i \leqslant p - 1 < p</math>. | ||
Linia 756: | Linia 1012: | ||
::<math>n p - a k = b</math> | ::<math>n p - a k = b</math> | ||
− | Zauważmy, że ponieważ <math>p \nmid a</math>, to liczby <math>a</math> i <math>p</math> są względnie pierwsze. Zatem ich największym wspólnym dzielnikiem jest liczba <math>1</math>. Na mocy twierdzenia | + | Zauważmy, że ponieważ <math>p \nmid a</math>, to liczby <math>a</math> i <math>p</math> są względnie pierwsze. Zatem ich największym wspólnym dzielnikiem jest liczba <math>1</math>. Na mocy twierdzenia [[#C79|C79]] równanie to ma nieskończenie wiele rozwiązań w liczbach całkowitych |
::<math>n = n_0 + p t</math> | ::<math>n = n_0 + p t</math> | ||
Linia 785: | Linia 1041: | ||
::<math>a k + b = a (k_0 + s p) + b = a s p + (a k_0 + b)</math> | ::<math>a k + b = a (k_0 + s p) + b = a s p + (a k_0 + b)</math> | ||
− | Czyli <math>p | + | Czyli <math>p \mid a k + b</math>.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 791: | Linia 1047: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C46" style="font-size: 110%; font-weight: bold;">Uwaga C46</span><br/> |
Łatwo możemy napisać w PARI/GP funkcję, która zwraca najmniejszą liczbę naturalną <math>k_0</math>, dla której wyraz ciągu arytmetycznego <math>a k + b</math> jest podzielny przez <math>p</math> (przy założeniu, że liczby <math>a</math> i <math>p</math> są względnie pierwsze). | Łatwo możemy napisać w PARI/GP funkcję, która zwraca najmniejszą liczbę naturalną <math>k_0</math>, dla której wyraz ciągu arytmetycznego <math>a k + b</math> jest podzielny przez <math>p</math> (przy założeniu, że liczby <math>a</math> i <math>p</math> są względnie pierwsze). | ||
Linia 802: | Linia 1058: | ||
== Ciągi nieskończone i liczby pierwsze == | == Ciągi nieskończone i liczby pierwsze == | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C47" style="font-size: 110%; font-weight: bold;">Uwaga C47</span><br/> |
Choć wiele ciągów jest dobrze znanych i równie dobrze zbadanych, to nie wiemy, czy zawierają one nieskończenie wiele liczb pierwszych. Przykładowo | Choć wiele ciągów jest dobrze znanych i równie dobrze zbadanych, to nie wiemy, czy zawierają one nieskończenie wiele liczb pierwszych. Przykładowo | ||
Linia 848: | Linia 1104: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C48" style="font-size: 110%; font-weight: bold;">Przykład C48</span><br/> |
− | Łatwo sprawdzić, że wartości wielomianu <math>W(n) = n^2 + n + 41</math> są liczbami pierwszymi dla <math>1 \leqslant n \leqslant 39</math>. Oczywiście <math>41 | + | Łatwo sprawdzić, że wartości wielomianu <math>W(n) = n^2 + n + 41</math> są liczbami pierwszymi dla <math>1 \leqslant n \leqslant 39</math>. Oczywiście <math>41 \mid W(41)</math>. |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C49" style="font-size: 110%; font-weight: bold;">Twierdzenie C49</span><br/> |
− | Niech <math>a, n</math> | + | 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}} | {{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 <math>a^n + 1 \geqslant 4</math> | + | 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 | + | 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> | ::<math>a^n + 1 = (a^y)^x + 1</math> | ||
− | Oznaczając <math>b = a^y</math> oraz <math>x = 2 k + 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 | + | ::<math>a^n + 1 = (a^y)^x + 1</math> |
− | ::::<math>\: = b^x + 1 | + | ::::<math>\: = b^x + 1</math> |
− | ::::<math>\: = b^{2 k + 1} + 1 | + | ::::<math>\: = b^{2 k + 1} + 1</math> |
− | ::::<math>\: = (b + 1) \cdot (b^{2 k} - b^{2 k - 1} | + | ::::<math>\: = (b + 1) \cdot (1 - b + b^2 - b^3 + \ldots + b^{2 k - 2} - b^{2 k - 1} + b^{2 k})</math> |
− | + | Czyli <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/> | |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 879: | Linia 1135: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C50" style="font-size: 110%; font-weight: bold;">Twierdzenie C50</span><br/> |
Dla dowolnej liczby naturalnej <math>n \geqslant 1</math> liczba <math>x - y</math> jest dzielnikiem wyrażenia <math>x^n - y^n</math>. | Dla dowolnej liczby naturalnej <math>n \geqslant 1</math> liczba <math>x - y</math> jest dzielnikiem wyrażenia <math>x^n - y^n</math>. | ||
Linia 899: | Linia 1155: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C51" style="font-size: 110%; font-weight: bold;">Twierdzenie C51</span><br/> |
Jeżeli <math>n \geqslant 2</math> oraz <math>a^n - 1</math> jest liczbą pierwszą, to <math>a = 2</math> i <math>n</math> jest liczbą pierwszą. | Jeżeli <math>n \geqslant 2</math> oraz <math>a^n - 1</math> jest liczbą pierwszą, to <math>a = 2</math> i <math>n</math> jest liczbą pierwszą. | ||
{{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 twierdzenia | + | Z twierdzenia [[#C50|C50]] wiemy, że <math>x - y \mid x^n - y^n</math>. W przypadku gdy <math>a > 2</math> mamy |
− | ::<math>a - 1 | + | ::<math>a - 1 \mid a^n - 1</math> |
Czyli musi być <math>a = 2</math>. Z tego samego twierdzenia wynika też, że jeżeli <math>n</math> jest liczbą złożoną <math>n = r s</math>, to | Czyli musi być <math>a = 2</math>. Z tego samego twierdzenia wynika też, że jeżeli <math>n</math> jest liczbą złożoną <math>n = r s</math>, to | ||
− | ::<math>2^r - 1 | + | ::<math>2^r - 1 \mid 2^{r s} - 1</math> |
− | bo <math>a^r - b^r | + | bo <math>a^r - b^r \mid (a^r)^s - (b^r)^s</math>. Zatem <math>n</math> musi być liczbą pierwszą. Co kończy dowód.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 922: | Linia 1178: | ||
== Ciągi arytmetyczne liczb pierwszych == | == Ciągi arytmetyczne liczb pierwszych == | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C52" style="font-size: 110%; font-weight: bold;">Uwaga C52</span><br/> |
Ciągi arytmetyczne liczb pierwszych<ref name="PAPWiki"/><ref name="PAPMathWorld"/> zbudowane z dwóch liczb pierwszych nie są interesujące, bo dowolne dwie liczby tworzą ciąg arytmetyczny. Dlatego będziemy się zajmowali ciągami arytmetycznymi liczb pierwszych o długości <math>n \geqslant 3</math>. | Ciągi arytmetyczne liczb pierwszych<ref name="PAPWiki"/><ref name="PAPMathWorld"/> zbudowane z dwóch liczb pierwszych nie są interesujące, bo dowolne dwie liczby tworzą ciąg arytmetyczny. Dlatego będziemy się zajmowali ciągami arytmetycznymi liczb pierwszych o długości <math>n \geqslant 3</math>. | ||
Linia 933: | Linia 1189: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C53" style="font-size: 110%; font-weight: bold;">Twierdzenie C53* (Ben Green i Terence Tao, 2004)</span><br/> |
Dla dowolnej liczby naturalnej <math>n \geqslant 2</math> istnieje nieskończenie wiele <math>n</math>-wyrazowych ciągów arytmetycznych liczb pierwszych. | Dla dowolnej liczby naturalnej <math>n \geqslant 2</math> istnieje nieskończenie wiele <math>n</math>-wyrazowych ciągów arytmetycznych liczb pierwszych. | ||
Linia 939: | Linia 1195: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C54" style="font-size: 110%; font-weight: bold;">Przykład C54</span><br/> |
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości <math>n = 3</math> i <math>n = 4</math>. | Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości <math>n = 3</math> i <math>n = 4</math>. | ||
Linia 1287: | Linia 1543: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C55" style="font-size: 110%; font-weight: bold;">Przykład C55</span><br/> |
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości <math>n = 5</math> i <math>n = 6</math>. | Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości <math>n = 5</math> i <math>n = 6</math>. | ||
Linia 1579: | Linia 1835: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C56" style="font-size: 110%; font-weight: bold;">Przykład C56</span><br/> |
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości <math>n = 7</math> i <math>n = 8</math>. | Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości <math>n = 7</math> i <math>n = 8</math>. | ||
Linia 1843: | Linia 2099: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C57" style="font-size: 110%; font-weight: bold;">Przykład C57</span><br/> |
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości <math>n = 9</math> i <math>n = 10</math>. | Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości <math>n = 9</math> i <math>n = 10</math>. | ||
Linia 2275: | Linia 2531: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C58" style="font-size: 110%; font-weight: bold;">Twierdzenie C58</span><br/> |
− | Niech <math> | + | Niech <math>n \in \mathbb{Z}_+</math> oraz <math>a, d, k, k_0 \in \mathbb{Z}</math>. Jeżeli liczby <math>d</math> i <math>n</math> są względnie pierwsze, to reszty <math>r_1, r_2, \ldots, r_n</math> z dzielenia <math>n</math> liczb <math>x_k</math> postaci |
::<math>x_k = a + k d \qquad</math> dla <math>\; k = k_0 + 1, \ldots, k_0 + n</math> | ::<math>x_k = a + k d \qquad</math> dla <math>\; k = k_0 + 1, \ldots, k_0 + n</math> | ||
− | przez liczbę <math>n</math> są wszystkie różne i tworzą zbiór <math>S = \{ 0, 1, \ldots, n - 1 \}</math>. W szczególności wynika stąd, że wśród <math> | + | przez liczbę <math>n</math> są wszystkie różne i tworzą zbiór <math>S = \{ 0, 1, \ldots, n - 1 \}</math>. W szczególności wynika stąd, że wśród liczb <math>x_k</math> jedna jest podzielna przez <math>n</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}} | ||
Przypuśćmy, że dla pewnych różnych liczb naturalnych <math>i, j</math> takich, że <math>1 \leqslant i < j \leqslant n</math> liczby <math>a + (k_0 + i) d</math> oraz <math>a + (k_0 + j) d</math> dają tę samą resztę przy dzieleniu przez <math>n</math>. Zatem różnica tych liczb jest podzielna przez <math>n</math> | Przypuśćmy, że dla pewnych różnych liczb naturalnych <math>i, j</math> takich, że <math>1 \leqslant i < j \leqslant n</math> liczby <math>a + (k_0 + i) d</math> oraz <math>a + (k_0 + j) d</math> dają tę samą resztę przy dzieleniu przez <math>n</math>. Zatem różnica tych liczb jest podzielna przez <math>n</math> | ||
− | ::<math>n | + | ::<math>n \mid [a + (k_0 + j) d] - [a + (k_0 + i) d]</math> |
Czyli | Czyli | ||
− | ::<math>n | + | ::<math>n \mid d (j - i)</math> |
− | Ponieważ liczby <math>d</math> i <math>n</math> są względnie pierwsze, to na mocy lematu Euklidesa (twierdzenie | + | Ponieważ liczby <math>d</math> i <math>n</math> są względnie pierwsze, to na mocy lematu Euklidesa (twierdzenie [[#C75|C75]]), mamy |
− | ::<math>n | + | ::<math>n \mid (j - i)</math> |
Co jest niemożliwe, bo <math>1 \leqslant j - i \leqslant n - 1 < n</math>. | Co jest niemożliwe, bo <math>1 \leqslant j - i \leqslant n - 1 < n</math>. | ||
Linia 2303: | Linia 2559: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C59" style="font-size: 110%; font-weight: bold;">Twierdzenie C59</span><br/> |
Niech <math>d \in \mathbb{Z}_+</math> i niech będzie dany ciąg arytmetyczny liczb pierwszych o długości <math>n</math> | Niech <math>d \in \mathbb{Z}_+</math> i niech będzie dany ciąg arytmetyczny liczb pierwszych o długości <math>n</math> | ||
Linia 2312: | Linia 2568: | ||
:* <math>p_0 \nmid d</math> | :* <math>p_0 \nmid d</math> | ||
:* <math>n \leqslant p_0</math> | :* <math>n \leqslant p_0</math> | ||
− | :* <math>P(n - 1) | + | :* <math>P(n - 1) \mid d</math> |
:* jeżeli liczba pierwsza <math>q</math> nie dzieli <math>d</math>, to <math>n \leqslant q</math> | :* jeżeli liczba pierwsza <math>q</math> nie dzieli <math>d</math>, to <math>n \leqslant q</math> | ||
Linia 2319: | Linia 2575: | ||
{{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.'''<br/> | '''Punkt 1.'''<br/> | ||
− | Gdyby <math>p_0 | + | Gdyby <math>p_0 \mid d</math>, to dla <math>k \geqslant 1</math> mielibyśmy <math>p_k = p_0 \left( 1 + k \cdot {\small\frac{d}{p_0}} \right)</math> i wszystkie te liczby byłyby złożone. |
'''Punkt 2.'''<br/> | '''Punkt 2.'''<br/> | ||
Linia 2325: | Linia 2581: | ||
'''Punkt 3.'''<br/> | '''Punkt 3.'''<br/> | ||
− | Niech <math>q</math> będzie liczbą pierwszą mniejszą od <math>n</math>, a liczby <math>r_k</math> będą resztami uzyskanymi z dzielenia liczb <math>p_k = p_0 + k d</math> przez <math>q</math>, dla <math>k = 0, 1, \ldots, q - 1</math>. Ponieważ z założenia liczby <math>p_0, \ldots, p_{n - 1}</math> są liczbami pierwszymi większymi od <math>q</math> (zauważmy, że <math>p_0 \geqslant n</math>), to żadna z reszt <math>r_k</math> nie może być równa zeru. Czyli mamy <math>q</math> reszt mogących przyjmować jedynie <math>q - 1</math> różnych wartości. Zatem istnieją różne liczby <math>i, j</math>, | + | Niech <math>q</math> będzie liczbą pierwszą mniejszą od <math>n</math>, a liczby <math>r_k</math> będą resztami uzyskanymi z dzielenia liczb <math>p_k = p_0 + k d</math> przez <math>q</math>, dla <math>k = 0, 1, \ldots, q - 1</math>. Ponieważ z założenia liczby <math>p_0, \ldots, p_{n - 1}</math> są liczbami pierwszymi większymi od <math>q</math> (zauważmy, że <math>p_0 \geqslant n</math>), to żadna z reszt <math>r_k</math> nie może być równa zeru. Czyli mamy <math>q</math> reszt mogących przyjmować jedynie <math>q - 1</math> różnych wartości. Zatem istnieją różne liczby <math>i, j</math> takie, że <math>0 \leqslant i < j \leqslant q - 1</math>, dla których <math>r_i = r_j</math>. Wynika stąd, że różnica liczb |
::<math>p_j - p_i = (p_0 + j d) - (p_0 + i d) = d (j - i)</math> | ::<math>p_j - p_i = (p_0 + j d) - (p_0 + i d) = d (j - i)</math> | ||
− | musi być podzielna przez <math>q</math>. Ponieważ <math>q \nmid (j - i)</math>, bo <math>1 \leqslant j - i \leqslant q - 1 < q</math>, zatem z lematu Euklidesa <math>q | + | musi być podzielna przez <math>q</math>. Ponieważ <math>q \nmid (j - i)</math>, bo <math>1 \leqslant j - i \leqslant q - 1 < q</math>, zatem z lematu Euklidesa <math>q \mid d</math>. |
Z uwagi na fakt, że jest tak dla każdej liczby pierwszej <math>q < n</math>, liczba <math>d</math> musi być podzielna przez | Z uwagi na fakt, że jest tak dla każdej liczby pierwszej <math>q < n</math>, liczba <math>d</math> musi być podzielna przez | ||
Linia 2342: | Linia 2598: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C60" style="font-size: 110%; font-weight: bold;">Uwaga C60</span><br/> |
Czasami, zamiast pisać „ciąg arytmetyczny liczb pierwszych”, będziemy posługiwali się skrótem PAP od angielskiej nazwy „''prime arithmetic progression''”. Konsekwentnie zapis PAP-<math>n</math> będzie oznaczał ciąg arytmetyczny liczb pierwszych o długości <math>n</math>, a zapis PAP<math>(n, d, q)</math> ciąg arytmetyczny liczb pierwszych o długości <math>n</math>, pierwszym wyrazie <math>q</math> i różnicy <math>d</math>. | Czasami, zamiast pisać „ciąg arytmetyczny liczb pierwszych”, będziemy posługiwali się skrótem PAP od angielskiej nazwy „''prime arithmetic progression''”. Konsekwentnie zapis PAP-<math>n</math> będzie oznaczał ciąg arytmetyczny liczb pierwszych o długości <math>n</math>, a zapis PAP<math>(n, d, q)</math> ciąg arytmetyczny liczb pierwszych o długości <math>n</math>, pierwszym wyrazie <math>q</math> i różnicy <math>d</math>. | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C61" style="font-size: 110%; font-weight: bold;">Uwaga C61</span><br/> |
Jakkolwiek sądzimy, że istnieje nieskończenie wiele ciągów arytmetycznych liczb pierwszych rozpoczynających się od dowolnej liczby pierwszej <math>q</math> i o dowolnej długości <math>3 \leqslant n \leqslant q</math>, to obecnie jest to tylko nieudowodnione przypuszczenie. | Jakkolwiek sądzimy, że istnieje nieskończenie wiele ciągów arytmetycznych liczb pierwszych rozpoczynających się od dowolnej liczby pierwszej <math>q</math> i o dowolnej długości <math>3 \leqslant n \leqslant q</math>, to obecnie jest to tylko nieudowodnione przypuszczenie. | ||
− | Dlatego '''nawet dla najmniejszej''' liczby pierwszej <math>q</math> takiej, że <math>q \nmid d</math> nierówność <math>n \leqslant q</math>, pokazana w twierdzeniu | + | Dlatego '''nawet dla najmniejszej''' liczby pierwszej <math>q</math> takiej, że <math>q \nmid d</math> nierówność <math>n \leqslant q</math>, pokazana w twierdzeniu [[#C59|C59]], pozostaje nadal tylko oszacowaniem. W szczególności nie możemy z góry przyjmować, że dla liczby <math>n = q</math> znajdziemy taką liczbę <math>d</math> będącą wielokrotnością liczby <math>P(q - 1)</math> i niepodzielną przez <math>q</math>, że będzie istniał PAP<math>(q, d, q)</math>. |
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C62" style="font-size: 110%; font-weight: bold;">Przykład C62</span><br/> |
Rozważmy dwie różnice <math>d_1 = 6 = 2 \cdot 3</math> oraz <math>d_2 = 42 = 2 \cdot 3 \cdot 7</math>. Zauważmy, że liczba pierwsza <math>5</math> nie dzieli ani <math>d_1</math>, ani <math>d_2</math>. Co więcej, liczba pierwsza <math>5</math> jest '''najmniejszą''' liczbą pierwszą, która nie dzieli rozpatrywanych różnic, zatem nierówność <math>n \leqslant 5</math> zapewnia najmocniejsze oszacowanie długości ciągu <math>n</math>. Łatwo sprawdzamy w zamieszczonych tabelach, że dla <math>d = 6</math> oraz dla <math>d = 42</math> są ciągi o długości <math>3, 4, 5</math>, ale nie ma ciągów o długości <math>6, 7, \ldots</math> | Rozważmy dwie różnice <math>d_1 = 6 = 2 \cdot 3</math> oraz <math>d_2 = 42 = 2 \cdot 3 \cdot 7</math>. Zauważmy, że liczba pierwsza <math>5</math> nie dzieli ani <math>d_1</math>, ani <math>d_2</math>. Co więcej, liczba pierwsza <math>5</math> jest '''najmniejszą''' liczbą pierwszą, która nie dzieli rozpatrywanych różnic, zatem nierówność <math>n \leqslant 5</math> zapewnia najmocniejsze oszacowanie długości ciągu <math>n</math>. Łatwo sprawdzamy w zamieszczonych tabelach, że dla <math>d = 6</math> oraz dla <math>d = 42</math> są ciągi o długości <math>3, 4, 5</math>, ale nie ma ciągów o długości <math>6, 7, \ldots</math> | ||
− | W szczególności z twierdzenia | + | W szczególności z twierdzenia [[#C59|C59]] wynika, że szukając ciągów arytmetycznych liczb pierwszych o określonej długości <math>n</math>, należy szukać ich tylko dla różnic <math>d</math> będących wielokrotnością liczby <math>P(n - 1)</math>. |
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span id="C63" style="font-size: 110%; font-weight: bold;">Zadanie C63</span><br/> |
Wiemy, że liczby pierwsze <math>p > 3</math> można przedstawić w jednej z postaci <math>6 k - 1</math> lub <math>6 k + 1</math>. Pokazać, że jeżeli <math>p_0 = 3</math>, to dwa następne wyrazu rosnącego ciągu arytmetycznego liczb pierwszych są różnych postaci. | Wiemy, że liczby pierwsze <math>p > 3</math> można przedstawić w jednej z postaci <math>6 k - 1</math> lub <math>6 k + 1</math>. Pokazać, że jeżeli <math>p_0 = 3</math>, to dwa następne wyrazu rosnącego ciągu arytmetycznego liczb pierwszych są różnych postaci. | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
− | Ponieważ <math>p_0 = 3</math>, a rozpatrywany PAP jest rosnący, to kolejne wyrazy ciągu są większe od liczby <math>3</math> i mogą być przedstawione w jednej z postaci <math>6 k - 1</math> lub <math>6 k + 1</math>. Z twierdzenia | + | Ponieważ <math>p_0 = 3</math>, a rozpatrywany PAP jest rosnący, to kolejne wyrazy ciągu są większe od liczby <math>3</math> i mogą być przedstawione w jednej z postaci <math>6 k - 1</math> lub <math>6 k + 1</math>. Z twierdzenia [[#C59|C59]] wiemy, że musi być <math>n \leqslant p_0 = 3</math>, czyli długość rozpatrywanego ciągu arytmetycznego liczb pierwszych wynosi dokładnie <math>3</math> i istnieją tylko dwa następne wyrazy. |
Rozważmy ciąg arytmetyczny liczb pierwszych składający się z trzech wyrazów <math>p, q, r</math> takich, że <math>p = 3</math>. Mamy | Rozważmy ciąg arytmetyczny liczb pierwszych składający się z trzech wyrazów <math>p, q, r</math> takich, że <math>p = 3</math>. Mamy | ||
Linia 2381: | Linia 2637: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span id="C64" style="font-size: 110%; font-weight: bold;">Zadanie C64</span><br/> |
Wiemy, że liczby pierwsze <math>p > 3</math> można przedstawić w jednej z postaci <math>6 k - 1</math> lub <math>6 k + 1</math>. Pokazać, że wszystkie wyrazy rosnącego ciągu arytmetycznego liczb pierwszych <math>p_0, p_1, \ldots, p_{n - 1}</math>, gdzie <math>p_0 \geqslant 5</math> i <math>n \geqslant 3</math> muszą być jednakowej postaci. | Wiemy, że liczby pierwsze <math>p > 3</math> można przedstawić w jednej z postaci <math>6 k - 1</math> lub <math>6 k + 1</math>. Pokazać, że wszystkie wyrazy rosnącego ciągu arytmetycznego liczb pierwszych <math>p_0, p_1, \ldots, p_{n - 1}</math>, gdzie <math>p_0 \geqslant 5</math> i <math>n \geqslant 3</math> muszą być jednakowej postaci. | ||
Linia 2403: | Linia 2659: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span id="C65" style="font-size: 110%; font-weight: bold;">Zadanie C65</span><br/> |
Niech <math>d > 0</math> będzie różnicą ciągu arytmetycznego liczb pierwszych o długości <math>n</math> | Niech <math>d > 0</math> będzie różnicą ciągu arytmetycznego liczb pierwszych o długości <math>n</math> | ||
::<math>p_k = p_0 + k d \qquad</math> dla <math>\; k = 0, 1, \ldots, n - 1</math> | ::<math>p_k = p_0 + k d \qquad</math> dla <math>\; k = 0, 1, \ldots, n - 1</math> | ||
− | Pokazać, nie korzystając z twierdzenia | + | Pokazać, nie korzystając z twierdzenia [[#C59|C59]], że jeżeli liczba pierwsza <math>q</math> nie dzieli <math>d</math>, to <math>n \leqslant q</math>. |
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
Linia 2415: | Linia 2671: | ||
::<math>q < p_k = p_0 + k d \qquad</math> dla <math>\; k = 0, 1, \ldots, n - 1</math> | ::<math>q < p_k = p_0 + k d \qquad</math> dla <math>\; k = 0, 1, \ldots, n - 1</math> | ||
− | Ponieważ <math>q \nmid d</math>, to na mocy twierdzenia | + | Ponieważ <math>q \nmid d</math>, to na mocy twierdzenia [[#C58|C58]] wśród <math>q</math> kolejnych wyrazów <math>p_0, p_1, \ldots, p_{q - 1}</math> (zauważmy, że <math>q - 1 < n - 1</math>) jedna liczba pierwsza <math>p_k</math> musi być podzielna przez <math>q</math>, zatem musi być równa <math>q</math>. Jednak jest to niemożliwe, bo <math>q < p_k</math> dla wszystkich <math>k = 0, 1, \ldots, n - 1</math>. Zatem nie może być <math>n > q</math>.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 2421: | Linia 2677: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C66" style="font-size: 110%; font-weight: bold;">Twierdzenie C66</span><br/> |
Niech <math>q</math> będzie liczbą pierwszą, a liczby pierwsze | Niech <math>q</math> będzie liczbą pierwszą, a liczby pierwsze | ||
Linia 2436: | Linia 2692: | ||
::<math>p_k = q + k d \qquad</math> dla <math>\; k = 0, 1, \ldots, q - 1</math> | ::<math>p_k = q + k d \qquad</math> dla <math>\; k = 0, 1, \ldots, q - 1</math> | ||
− | Gdyby <math>q | + | Gdyby <math>q \mid d</math>, to mielibyśmy |
− | ::<math>p_k = q \left( 1 + k \cdot \frac{d}{q} \right)</math> | + | ::<math>p_k = q \left( 1 + k \cdot {\small\frac{d}{q}} \right)</math> |
i wszystkie liczby <math>p_k</math> dla <math>k \geqslant 1</math> byłyby złożone, wbrew założeniu, że <math>p_k</math> tworzą <math>q</math>-wyrazowy ciąg arytmetyczny liczb pierwszych. | i wszystkie liczby <math>p_k</math> dla <math>k \geqslant 1</math> byłyby złożone, wbrew założeniu, że <math>p_k</math> tworzą <math>q</math>-wyrazowy ciąg arytmetyczny liczb pierwszych. | ||
<math>\Longleftarrow</math><br/> | <math>\Longleftarrow</math><br/> | ||
− | Ponieważ <math>q</math> jest długością rozpatrywanego ciągu arytmetycznego liczb pierwszych, to z twierdzenia | + | Ponieważ <math>q</math> jest długością rozpatrywanego ciągu arytmetycznego liczb pierwszych, to z twierdzenia [[#C59|C59]] wynika, że musi być <math>q \leqslant p_0</math>. |
− | Z założenia liczba pierwsza <math>q</math> nie dzieli <math>d</math>, zatem z twierdzenia | + | Z założenia liczba pierwsza <math>q</math> nie dzieli <math>d</math>, zatem z twierdzenia [[#C58|C58]] wiemy, że <math>q</math> musi dzielić jedną z liczb <math>p_0, p_1, \ldots, p_{q - 1}</math>. |
− | Jeżeli <math>q | + | Jeżeli <math>q \mid p_k</math>, to <math>p_k = q</math>. Ponieważ <math>q \leqslant p_0</math>, to możliwe jest jedynie <math>q \mid p_0</math> i musi być <math>p_0 = q</math>.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 2453: | Linia 2709: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C67" style="font-size: 110%; font-weight: bold;">Uwaga C67</span><br/> |
Niech ciąg arytmetyczny liczb pierwszych o długości <math>n</math> ma postać | Niech ciąg arytmetyczny liczb pierwszych o długości <math>n</math> ma postać | ||
::<math>p_k = p_0 + k d \qquad</math> dla <math>\; k = 0, 1, \ldots, n - 1</math> | ::<math>p_k = p_0 + k d \qquad</math> dla <math>\; k = 0, 1, \ldots, n - 1</math> | ||
− | Z udowodnionych wyżej twierdzeń | + | Z udowodnionych wyżej twierdzeń [[#C59|C59]] i [[#C66|C66]] wynika, że ciągi arytmetyczne liczb pierwszych o długości <math>n</math> można podzielić na dwie grupy |
− | :* jeżeli <math>n</math> jest liczbą pierwszą i <math>n \nmid d</math>, to <math>P(n - 1) | + | :* jeżeli <math>n</math> jest liczbą pierwszą i <math>n \nmid d</math>, to <math>P(n - 1) \mid d</math> oraz <math>p_0 = n</math> (dla ustalonego <math>d</math> może istnieć tylko jeden ciąg) |
− | :* jeżeli <math>n</math> jest liczbą złożoną lub <math>n | + | :* jeżeli <math>n</math> jest liczbą złożoną lub <math>n \mid d</math>, to <math>P(n) \mid d</math> oraz <math>p_0 > n</math> |
Funkcja <math>P(t)</math> jest iloczynem wszystkich liczb pierwszych nie większych od <math>t</math>. | Funkcja <math>P(t)</math> jest iloczynem wszystkich liczb pierwszych nie większych od <math>t</math>. | ||
Linia 2467: | Linia 2723: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C68" style="font-size: 110%; font-weight: bold;">Przykład C68</span><br/> |
Niech różnica ciągu arytmetycznego liczb pierwszych wynosi <math>d = 10^t</math>, gdzie <math>t \geqslant 1</math>. Zauważmy, że dla dowolnego <math>t</math> liczba <math>3</math> jest najmniejszą liczbą pierwszą, która nie dzieli <math>d</math>. Z oszacowania <math>n \leqslant 3</math> wynika, że musi być <math>n = 3</math>. | Niech różnica ciągu arytmetycznego liczb pierwszych wynosi <math>d = 10^t</math>, gdzie <math>t \geqslant 1</math>. Zauważmy, że dla dowolnego <math>t</math> liczba <math>3</math> jest najmniejszą liczbą pierwszą, która nie dzieli <math>d</math>. Z oszacowania <math>n \leqslant 3</math> wynika, że musi być <math>n = 3</math>. | ||
Linia 2474: | Linia 2730: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span id="C69" style="font-size: 110%; font-weight: bold;">Zadanie C69</span><br/> |
Znaleźć wszystkie PAP<math>(n, d, p)</math> dla <math>d = 2, 4, 8, 10, 14, 16</math>. | Znaleźć wszystkie PAP<math>(n, d, p)</math> dla <math>d = 2, 4, 8, 10, 14, 16</math>. | ||
Linia 2490: | Linia 2746: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span id="C70" style="font-size: 110%; font-weight: bold;">Zadanie C70</span><br/> |
Znaleźć wszystkie PAP<math>(n, d, p)</math> dla <math>n = 3, 5, 7, 11</math> i <math>d = P (n - 1)</math>. | Znaleźć wszystkie PAP<math>(n, d, p)</math> dla <math>n = 3, 5, 7, 11</math> i <math>d = P (n - 1)</math>. | ||
Linia 2508: | Linia 2764: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C71" style="font-size: 110%; font-weight: bold;">Przykład C71</span><br/> |
− | Przedstawiamy przykładowe ciągi arytmetyczne liczb pierwszych, | + | Przedstawiamy przykładowe ciągi arytmetyczne liczb pierwszych takie, że <math>n = p_0</math> dla <math>n = 3, 5, 7, 11, 13</math>. Zauważmy, że wypisane w tabeli wartości <math>d</math> są wielokrotnościami liczby <math>P(n - 1)</math>. |
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż tabelę|Hide=Ukryj tabelę}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż tabelę|Hide=Ukryj tabelę}} | ||
Linia 2536: | Linia 2792: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C72" style="font-size: 110%; font-weight: bold;">Przykład C72</span><br/> |
Liczby <math>3, 5, 7</math> są najprostszym przykładem ciągu arytmetycznego '''kolejnych''' liczb pierwszych. Zauważmy, że tylko w przypadku <math>n = 3</math> możliwa jest sytuacja, że <math>n = p_0 = 3</math>. Istotnie, łatwo stwierdzamy, że | Liczby <math>3, 5, 7</math> są najprostszym przykładem ciągu arytmetycznego '''kolejnych''' liczb pierwszych. Zauważmy, że tylko w przypadku <math>n = 3</math> możliwa jest sytuacja, że <math>n = p_0 = 3</math>. Istotnie, łatwo stwierdzamy, że | ||
− | :* ponieważ <math>p_0</math> i <math>p_1</math> są '''kolejnymi''' liczbami pierwszymi, to <math>p_1 - p_0 < p_0</math> (zobacz zadanie B22) | + | :* ponieważ <math>p_0</math> i <math>p_1</math> są '''kolejnymi''' liczbami pierwszymi, to <math>p_1 - p_0 < p_0</math> (zobacz zadanie [[Twierdzenie Czebyszewa o liczbie pierwszej między n i 2n#B22|B22]]) |
− | :* dla dowolnej liczby pierwszej <math>q \geqslant 5</math> jest <math>q < P (q - 1)</math> (zobacz zadanie B26) | + | :* dla dowolnej liczby pierwszej <math>q \geqslant 5</math> jest <math>q < P (q - 1)</math> (zobacz zadanie [[Twierdzenie Czebyszewa o liczbie pierwszej między n i 2n#B26|B26]]) |
− | Przypuśćmy teraz, że istnieje ciąg arytmetyczny '''kolejnych''' liczb pierwszych, | + | Przypuśćmy teraz, że istnieje ciąg arytmetyczny '''kolejnych''' liczb pierwszych taki, że <math>n = p_0 \geqslant 5</math>. Mamy |
::<math>d = p_1 - p_0 < p_0 < P (p_0 - 1) = P (n - 1)</math> | ::<math>d = p_1 - p_0 < p_0 < P (p_0 - 1) = P (n - 1)</math> | ||
Linia 2548: | Linia 2804: | ||
Zatem <math>P(n - 1) \nmid d</math>, co jest niemożliwe. | Zatem <math>P(n - 1) \nmid d</math>, co jest niemożliwe. | ||
− | Wynika stąd, że poza przypadkiem <math>n = p_0 = 3</math> ciąg arytmetyczny kolejnych liczb pierwszych musi spełniać warunek <math>P(n) | + | Wynika stąd, że poza przypadkiem <math>n = p_0 = 3</math> ciąg arytmetyczny kolejnych liczb pierwszych musi spełniać warunek <math>P(n) \mid d</math>, czyli <math>P(n) \mid (p_1 - p_0)</math>. |
Poniższe tabele przedstawiają przykładowe ciągi arytmetyczne kolejnych liczb pierwszych o długościach <math>n = 3, 4, 5, 6</math> dla rosnących wartości <math>p_0</math>. Nie istnieje ciąg arytmetyczny kolejnych liczb pierwszych o długości <math>n = 7</math> dla <math>p_0 < 10^{13}</math>. Prawdopodobnie CPAP-7 pojawią się dopiero dla <math>p_0 \sim 10^{20}</math>. | Poniższe tabele przedstawiają przykładowe ciągi arytmetyczne kolejnych liczb pierwszych o długościach <math>n = 3, 4, 5, 6</math> dla rosnących wartości <math>p_0</math>. Nie istnieje ciąg arytmetyczny kolejnych liczb pierwszych o długości <math>n = 7</math> dla <math>p_0 < 10^{13}</math>. Prawdopodobnie CPAP-7 pojawią się dopiero dla <math>p_0 \sim 10^{20}</math>. | ||
Linia 2688: | Linia 2944: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span id="C73" style="font-size: 110%; font-weight: bold;">Zadanie C73</span><br/> |
Uzasadnij przypuszczenie, że ciągów arytmetycznych '''kolejnych''' liczb pierwszych o długości <math>n = 7</math> możemy oczekiwać dopiero dla <math>p_0 \sim 10^{20}</math>. | Uzasadnij przypuszczenie, że ciągów arytmetycznych '''kolejnych''' liczb pierwszych o długości <math>n = 7</math> możemy oczekiwać dopiero dla <math>p_0 \sim 10^{20}</math>. | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
− | Zauważmy, że ilość liczb pierwszych nie większych od <math>x</math> w dobrym przybliżeniu jest określona funkcją <math>\frac{x}{\log x}</math>. Ponieważ funkcja <math>\log x</math> zmienia się bardzo wolno, to odcinki liczb naturalnych o tej samej długości położone w niewielkiej odległości od siebie będą zawierały podobne ilości liczb pierwszych. Przykładowo, dla dużych wartości <math>x</math>, ilość liczb pierwszych w przedziale <math>(x, 2 x)</math> jest tego samego rzędu, co ilość liczb pierwszych w przedziale <math>(1, x)</math><ref name="PrimesInInterval"/>. | + | Zauważmy, że ilość liczb pierwszych nie większych od <math>x</math> w dobrym przybliżeniu jest określona funkcją <math>{\small\frac{x}{\log x}}</math>. Ponieważ funkcja <math>\log x</math> zmienia się bardzo wolno, to odcinki liczb naturalnych o tej samej długości położone w niewielkiej odległości od siebie będą zawierały podobne ilości liczb pierwszych. Przykładowo, dla dużych wartości <math>x</math>, ilość liczb pierwszych w przedziale <math>(x, 2 x)</math> jest tego samego rzędu, co ilość liczb pierwszych w przedziale <math>(1, x)</math><ref name="PrimesInInterval"/>. |
− | Zatem liczbę <math>\frac{1}{\log x}</math> możemy traktować jako prawdopodobieństwo trafienia na liczbę pierwszą wśród liczb znajdujących się w pobliżu liczby <math>x</math>. Zakładając, że liczby pierwsze są rozłożone przypadkowo, możemy wyliczyć prawdopodobieństwo tego, że <math>n</math> kolejnych liczb pierwszych, położonych w pobliżu liczby <math>x</math>, utworzy ciąg arytmetyczny | + | Zatem liczbę <math>{\small\frac{1}{\log x}}</math> możemy traktować jako prawdopodobieństwo trafienia na liczbę pierwszą wśród liczb znajdujących się w pobliżu liczby <math>x</math>. Zakładając, że liczby pierwsze są rozłożone przypadkowo, możemy wyliczyć prawdopodobieństwo tego, że <math>n</math> kolejnych liczb pierwszych, położonych w pobliżu liczby <math>x</math>, utworzy ciąg arytmetyczny |
− | ::<math>\text{prob}_{\text{cpap}} (n, x) = \left( \frac{1}{\log x} \right)^n \left( 1 - \frac{1}{\log x} \right)^{(n - 1) (d - 1)}</math> | + | ::<math>\text{prob}_{\text{cpap}} (n, x) = \left( {\small\frac{1}{\log x}} \right)^n \left( 1 - {\small\frac{1}{\log x}} \right)^{(n - 1) (d - 1)}</math> |
− | gdzie <math>d = P (n)</math>. Jest tak, ponieważ w ciągu kolejnych liczb całkowitych musimy trafić na liczbę pierwszą, następnie na <math>d - 1</math> liczb złożonych, taka sytuacja musi się powtórzyć dokładnie <math>n - 1</math> razy, a na koniec znowu musimy trafić na liczbę pierwszą. Czyli potrzebujemy <math>n</math> liczb pierwszych, na które trafiamy z prawdopodobieństwem <math>\frac{1}{\log x}</math> oraz <math>(n - 1) (d - 1)</math> liczb złożonych, na które trafiamy z prawdopodobieństwem <math>1 - \frac{1}{\log x}</math>, a liczby te muszą pojawiać się w ściśle określonej kolejności. | + | gdzie <math>d = P (n)</math>. Jest tak, ponieważ w ciągu kolejnych liczb całkowitych musimy trafić na liczbę pierwszą, następnie na <math>d - 1</math> liczb złożonych, taka sytuacja musi się powtórzyć dokładnie <math>n - 1</math> razy, a na koniec znowu musimy trafić na liczbę pierwszą. Czyli potrzebujemy <math>n</math> liczb pierwszych, na które trafiamy z prawdopodobieństwem <math>{\small\frac{1}{\log x}}</math> oraz <math>(n - 1) (d - 1)</math> liczb złożonych, na które trafiamy z prawdopodobieństwem <math>1 - {\small\frac{1}{\log x}}</math>, a liczby te muszą pojawiać się w ściśle określonej kolejności. |
Ilość ciągów arytmetycznych utworzonych przez <math>n</math> kolejnych liczb pierwszych należących do przedziału <math>(x, 2 x)</math> możemy zatem oszacować na równą około | Ilość ciągów arytmetycznych utworzonych przez <math>n</math> kolejnych liczb pierwszych należących do przedziału <math>(x, 2 x)</math> możemy zatem oszacować na równą około | ||
− | ::<math>Q_{\text{cpap}}(n, x) = x \cdot \left( \frac{1}{\log x} \right)^n \left( 1 - \frac{1}{\log x} \right)^{(n - 1) (d - 1)}</math> | + | ::<math>Q_{\text{cpap}}(n, x) = x \cdot \left( {\small\frac{1}{\log x}} \right)^n \left( 1 - {\small\frac{1}{\log x}} \right)^{(n - 1) (d - 1)}</math> |
Linia 2755: | Linia 3011: | ||
Możemy ją łatwo wyliczyć w PARI/GP. Oczywiście funkcję <math>f(7, x)</math> zastąpiliśmy jej oszacowaniem <math>C_7 = 2500</math> | Możemy ją łatwo wyliczyć w PARI/GP. Oczywiście funkcję <math>f(7, x)</math> zastąpiliśmy jej oszacowaniem <math>C_7 = 2500</math> | ||
− | P(n) = prod(k=2, n, if( isprime(k), k, 1 )) | + | <span style="font-size: 90%; color:black;">P(n) = '''prod'''(k = 2, n, '''if'''( '''isprime'''(k), k, 1 ))</span> |
− | Q(x) = 2500 * x * ( 1/log(x) )^7 * ( 1 - 1/log(x) )^( (7-1)*(P(7)-1) ) | + | |
− | solve(x=10^10, 10^23, Q(x) - 1 ) | + | <span style="font-size: 90%; color:black;">Q(x) = 2500 * x * ( 1/'''log'''(x) )^7 * ( 1 - 1/'''log'''(x) )^( (7 - 1)*(P(7) - 1) )</span> |
− | < | + | |
+ | <span style="font-size: 90%; color:black;">'''solve'''(x = 10^10, 10^23, Q(x) - 1 )</span> | ||
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 2768: | Linia 3025: | ||
== Uzupełnienie == | == Uzupełnienie == | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C74" style="font-size: 110%; font-weight: bold;">Twierdzenie C74 (lemat Bézouta)</span><br/> |
Jeżeli liczby całkowite <math>a</math> i <math>b</math> nie są jednocześnie równe zeru, a największy wspólny dzielnik tych liczb jest równy <math>D</math>, to istnieją takie liczby całkowite <math>x, y</math>, że | Jeżeli liczby całkowite <math>a</math> i <math>b</math> nie są jednocześnie równe zeru, a największy wspólny dzielnik tych liczb jest równy <math>D</math>, to istnieją takie liczby całkowite <math>x, y</math>, że | ||
Linia 2795: | Linia 3052: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C75" style="font-size: 110%; font-weight: bold;">Twierdzenie C75 (lemat Euklidesa)</span><br/> |
Niech <math>p</math> będzie liczbą pierwszą oraz <math>a, b, d \in \mathbb{Z}</math>. | Niech <math>p</math> będzie liczbą pierwszą oraz <math>a, b, d \in \mathbb{Z}</math>. | ||
− | :* jeżeli <math>d \mid a b</math> i liczba <math>d</math> jest względnie pierwsza z <math>a</math>, to <math>d \mid b</math> | + | :* jeżeli <math>d \mid a b</math> i liczba <math>d</math> jest względnie pierwsza z <math>a</math>, to <math>d \mid b</math> |
:* jeżeli <math>p \mid a b</math>, to <math>p \mid a</math> lub <math>p \mid b</math> | :* jeżeli <math>p \mid a b</math>, to <math>p \mid a</math> lub <math>p \mid b</math> | ||
Linia 2806: | Linia 3063: | ||
'''Punkt 1.''' | '''Punkt 1.''' | ||
− | Z założenia liczby <math>d</math> i <math>a</math> są względnie pierwsze, zatem na mocy lematu Bézouta (twierdzenie | + | Z założenia liczby <math>d</math> i <math>a</math> są względnie pierwsze, zatem na mocy lematu Bézouta (twierdzenie [[#C74|C74]]) istnieją takie liczby całkowite <math>x</math> i <math>y</math>, że |
::<math>d x + a y = 1</math> | ::<math>d x + a y = 1</math> | ||
Linia 2814: | Linia 3071: | ||
::<math>d b x + a b y = b</math> | ::<math>d b x + a b y = b</math> | ||
− | Obydwa wyrazy po | + | Obydwa wyrazy po lewej stronie są podzielne przez <math>d</math>, bo z założenia <math>d \mid a b</math>. Zatem prawa strona również jest podzielna przez <math>d</math>, czyli <math>d \mid b</math>. Co kończy dowód punktu pierwszego. |
'''Punkt 2.''' | '''Punkt 2.''' | ||
− | Jeżeli <math>p \nmid a</math>, to <math>\gcd (p, a) = 1</math>, zatem z punktu pierwszego wynika, że <math>p \mid b</math>. | + | Jeżeli <math>p \nmid a</math>, to <math>\gcd (p, a) = 1</math>, zatem z punktu pierwszego wynika, że <math>p \mid b</math>. |
− | Jeżeli <math>p \nmid b</math>, to <math>\gcd (p, b) = 1</math>, zatem z punktu pierwszego wynika, że <math>p \mid a</math>. | + | Jeżeli <math>p \nmid b</math>, to <math>\gcd (p, b) = 1</math>, zatem z punktu pierwszego wynika, że <math>p \mid a</math>. |
− | Czyli <math>p</math> musi dzielić przynajmniej jedną z liczb <math>a, b</math>. Co należało pokazać.<br/> | + | Czyli <math>p</math> musi dzielić przynajmniej jedną z liczb <math>a, b</math>. Co należało pokazać.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 2828: | Linia 3085: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C76" style="font-size: 110%; font-weight: bold;">Twierdzenie C76</span><br/> |
− | Niech <math>a, b, m \in \mathbb{Z}</math>. Jeżeli <math>a \mid m</math> i <math>b \mid m</math> oraz <math>\gcd (a, b) = 1</math>, to <math>a b \mid m</math>. | + | Niech <math>a, b, m \in \mathbb{Z}</math>. Jeżeli <math>a \mid m \;</math> i <math>\; b \mid m</math> oraz <math>\gcd (a, b) = 1</math>, to <math>a b \mid 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}} | ||
Linia 2837: | Linia 3094: | ||
::<math>a x + b y = 1</math> | ::<math>a x + b y = 1</math> | ||
− | (zobacz | + | (zobacz [[#C74|C74]]). Zatem |
::<math>m = m (a x + b y)</math> | ::<math>m = m (a x + b y)</math> | ||
Linia 2853: | Linia 3110: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C77" style="font-size: 110%; font-weight: bold;">Twierdzenie C77</span><br/> |
Niech <math>a, b, c \in \mathbb{Z}</math>. Równanie <math>a x + b y = c</math> ma rozwiązanie wtedy i tylko wtedy, gdy największy wspólny dzielnik liczb <math>a</math> i <math>b</math> jest dzielnikiem liczby <math>c</math>. | Niech <math>a, b, c \in \mathbb{Z}</math>. Równanie <math>a x + b y = c</math> ma rozwiązanie wtedy i tylko wtedy, gdy największy wspólny dzielnik liczb <math>a</math> i <math>b</math> jest dzielnikiem liczby <math>c</math>. | ||
Linia 2865: | Linia 3122: | ||
::<math>a x_0 + b y_0 = c</math> | ::<math>a x_0 + b y_0 = c</math> | ||
− | Ponieważ <math>D</math> dzieli lewą stronę równania, to musi również dzielić prawą, zatem musi być <math>D | + | Ponieważ <math>D</math> dzieli lewą stronę równania, to musi również dzielić prawą, zatem musi być <math>D \mid c</math>. |
<math>\Longleftarrow</math> | <math>\Longleftarrow</math> | ||
− | Jeżeli <math>D | + | Jeżeli <math>D \mid c</math>, to możemy napisać <math>c = k D</math> i równanie przyjmuje postać |
::<math>a x + b y = k D</math> | ::<math>a x + b y = k D</math> | ||
− | Lemat Bézouta (twierdzenie | + | Lemat Bézouta (twierdzenie [[#C74|C74]]) zapewnia istnienie liczb całkowitych <math>x_0</math> i <math>y_0</math> takich, że |
::<math>a x_0 + b y_0 = D</math> | ::<math>a x_0 + b y_0 = D</math> | ||
Linia 2891: | Linia 3148: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span id="C78" style="font-size: 110%; font-weight: bold;">Uwaga C78</span><br/> |
− | Z twierdzenia | + | Z twierdzenia [[#C77|C77]] wynika, że szukając rozwiązań równania <math>A x + B y = C</math> w liczbach całkowitych, powinniśmy |
:* obliczyć największy wspólny dzielnik <math>D</math> liczb <math>A</math> i <math>B</math> | :* obliczyć największy wspólny dzielnik <math>D</math> liczb <math>A</math> i <math>B</math> | ||
− | :* jeżeli <math>D > 1</math>, należy sprawdzić, czy <math>D | + | :* jeżeli <math>D > 1</math>, należy sprawdzić, czy <math>D \mid C</math> |
:* jeżeli <math>D \nmid C</math>, to równanie <math>A x + B y = C</math> nie ma rozwiązań w liczbach całkowitych | :* jeżeli <math>D \nmid C</math>, to równanie <math>A x + B y = C</math> nie ma rozwiązań w liczbach całkowitych | ||
− | :* jeżeli <math>D | + | :* jeżeli <math>D \mid C</math>, należy podzielić obie strony równania <math>A x + B y = C</math> przez <math>D</math> i przejść do rozwiązywania równania równoważnego <math>a x + b y = c</math>, gdzie <math>a = {\small\frac{A}{D}}</math>, <math>b = {\small\frac{B}{D}}</math>, <math>c = {\small\frac{C}{D}}</math>, zaś największy wspólny dzielnik liczb <math>a</math> i <math>b</math> jest równy <math>1</math>. |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span id="C79" style="font-size: 110%; font-weight: bold;">Twierdzenie C79</span><br/> |
Niech <math>a, b, c \in \mathbb{Z}</math>. Jeżeli liczby <math>a</math> i <math>b</math> są względnie pierwsze, to równanie | Niech <math>a, b, c \in \mathbb{Z}</math>. Jeżeli liczby <math>a</math> i <math>b</math> są względnie pierwsze, to równanie | ||
Linia 2916: | Linia 3173: | ||
{{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 założenia liczby <math>a</math> i <math>b</math> są względnie pierwsze, zatem największy wspólny dzielnik tych liczb jest równy <math>1</math> i dzieli liczbę <math>c</math>. Na mocy twierdzenia | + | Z założenia liczby <math>a</math> i <math>b</math> są względnie pierwsze, zatem największy wspólny dzielnik tych liczb jest równy <math>1</math> i dzieli liczbę <math>c</math>. Na mocy twierdzenia [[#C77|C77]] równanie |
::<math>a x + b y = c</math> | ::<math>a x + b y = c</math> | ||
Linia 2944: | Linia 3201: | ||
Wynika stąd, że musi być spełniony warunek | Wynika stąd, że musi być spełniony warunek | ||
− | ::<math>a(x - x_0) = b (y_0 - y)</math> | + | ::<math>a (x - x_0) = b (y_0 - y)</math> |
− | Ponieważ liczby <math>a</math> i <math>b</math> są względnie pierwsze, to na mocy lematu Euklidesa (twierdzenie | + | Ponieważ liczby <math>a \,</math> i <math>\, b</math> są względnie pierwsze, to na mocy lematu Euklidesa (twierdzenie [[#C75|C75]]) <math>b \mid (x - x_0)</math>. Skąd mamy |
::<math>x - x_0 = b t</math> | ::<math>x - x_0 = b t</math> | ||
Linia 2960: | Linia 3217: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span id="C80" style="font-size: 110%; font-weight: bold;">Przykład C80</span><br/> |
Rozwiązania równania | Rozwiązania równania | ||
::<math>a x + b y = c</math> | ::<math>a x + b y = c</math> | ||
− | gdzie <math>\gcd (a, b) = 1</math>, które omówiliśmy w poprzednim twierdzeniu, najłatwiej znaleźć korzystając w PARI/GP z funkcji <code>gcdext(a, b)</code>. Funkcja ta zwraca wektor liczb <code>[x<sub>0</sub>, y<sub>0</sub>, d]</code>, gdzie <math>d = \gcd (a, b)</math>, a liczby <math>x_0</math> i <math>y_0</math> są rozwiązaniami równania | + | gdzie <math>\gcd (a, b) = 1</math>, które omówiliśmy w poprzednim twierdzeniu, najłatwiej znaleźć korzystając w PARI/GP z funkcji <span style="font-size: 90%; color:black;"><code>gcdext(a, b)</code></span>. Funkcja ta zwraca wektor liczb <span style="font-size: 90%; color:black;"><code>[x<sub>0</sub>, y<sub>0</sub>, d]</code></span>, gdzie <math>d = \gcd (a, b)</math>, a liczby <math>x_0</math> i <math>y_0</math> są rozwiązaniami równania |
::<math>a x_0 + b y_0 = \gcd (a, b)</math> | ::<math>a x_0 + b y_0 = \gcd (a, b)</math> | ||
Linia 2973: | Linia 3230: | ||
::<math>a(c x_0) + b (c y_0) = c</math> | ::<math>a(c x_0) + b (c y_0) = c</math> | ||
− | Zatem para liczb całkowitych <math>(c x_0, c y_0)</math> jest jednym z rozwiązań równania | + | Zatem para liczb całkowitych <math>(c x_0, c y_0)</math> jest jednym z rozwiązań równania |
::<math>a x + b y = c</math> | ::<math>a x + b y = c</math> | ||
Linia 2983: | Linia 3240: | ||
::<math>y = c y_0 - a t</math> | ::<math>y = c y_0 - a t</math> | ||
− | Niech <math>a = 7</math> i <math>b = 17</math>. Funkcja <code>gcdext(7,17)</code> zwraca wektor <code>[5, -2, 1]</code>, zatem rozwiązaniami równania <math>7 x + 17 y = 1</math> są liczby | + | Niech <math>a = 7 \;</math> i <math>\; b = 17</math>. Funkcja <span style="font-size: 90%; color:black;"><code>gcdext(7,17)</code></span> zwraca wektor <span style="font-size: 90%; color:black;"><code>[5, -2, 1]</code></span>, zatem rozwiązaniami równania <math>7 x + 17 y = 1</math> są liczby |
::<math>x = 5 + 17 t</math> | ::<math>x = 5 + 17 t</math> | ||
Linia 3024: | Linia 3281: | ||
<ref name="Xylouris1">Triantafyllos Xylouris, ''Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression'', Bonner Mathematische Schriften, vol. 404, Univ. Bonn, 2011, Diss.</ref> | <ref name="Xylouris1">Triantafyllos Xylouris, ''Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression'', Bonner Mathematische Schriften, vol. 404, Univ. Bonn, 2011, Diss.</ref> | ||
+ | |||
+ | <ref name="Bombieri1">Enrico Bombieri, John B. Friedlander and Henryk Iwaniec, ''Primes in Arithmetic Progressions to Large Moduli. III'', Journal of the American Mathematical Society 2 (1989) 215-224</ref> | ||
+ | |||
+ | <ref name="Turan1">Paul Turán, ''Über die Primzahlen der arithmetischen Progression'', Acta Sci. Szeged 8 (1937), 226-235</ref> | ||
+ | |||
+ | <ref name="Wagstaff1">Samuel S. Wagstaff, Jr., ''Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus'', Mathematics of Computation Vol. 33, No. 147 (1979), 1073-1080</ref> | ||
<ref name="PAPWiki">Wikipedia, ''Primes in arithmetic progression'', ([https://en.wikipedia.org/wiki/Primes_in_arithmetic_progression Wiki-en])</ref> | <ref name="PAPWiki">Wikipedia, ''Primes in arithmetic progression'', ([https://en.wikipedia.org/wiki/Primes_in_arithmetic_progression Wiki-en])</ref> |
Aktualna wersja na dzień 11:05, 9 cze 2024
Ciągi nieskończone
Definicja C1
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Jeżeli każdej liczbie [math]\displaystyle{ n }[/math] przypiszemy pewną liczbę rzeczywistą [math]\displaystyle{ a_n }[/math], to powiemy, że liczby [math]\displaystyle{ a_1, a_2, \ldots, a_n, \ldots }[/math] tworzą ciąg nieskończony.
Uwaga C2
Ciąg nieskończony [math]\displaystyle{ a_1, a_2, \ldots, a_n, \ldots }[/math] będziemy oznaczać [math]\displaystyle{ (a_n) }[/math]. Często, o ile nie będzie prowadziło to do nieporozumień, ciąg nieskończony będziemy nazywać po prostu ciągiem.
Definicja C3
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Ciąg [math]\displaystyle{ (a_n) }[/math] będziemy nazywali
- ciągiem rosnącym, jeżeli dla każdego [math]\displaystyle{ n }[/math] jest [math]\displaystyle{ a_{n + 1} \geqslant a_n }[/math]
- ciągiem malejącym, jeżeli dla każdego [math]\displaystyle{ n }[/math] jest [math]\displaystyle{ a_{n + 1} \leqslant a_n }[/math]
Ciągi rosnące dzielimy na
- ciągi silnie rosnące, jeżeli dla każdego [math]\displaystyle{ n }[/math] jest [math]\displaystyle{ a_{n + 1} \gt a_n }[/math]
- ciągi słabo rosnące, jeżeli istnieją takie [math]\displaystyle{ n }[/math], że [math]\displaystyle{ a_{n + 1} = a_n }[/math]
Ciągi malejące dzielimy na
- ciągi silnie malejące, jeżeli dla każdego [math]\displaystyle{ n }[/math] jest [math]\displaystyle{ a_{n + 1} \lt a_n }[/math]
- ciągi słabo malejące, jeżeli istnieją takie [math]\displaystyle{ n }[/math], że [math]\displaystyle{ a_{n + 1} = a_n }[/math]
Definicja C4
Niech [math]\displaystyle{ \varepsilon \in \mathbb{R}_+ }[/math]. Liczbę [math]\displaystyle{ a }[/math] będziemy nazywali granicą ciągu [math]\displaystyle{ (a_n) }[/math], jeżeli dla dowolnego [math]\displaystyle{ \varepsilon }[/math] w przedziale [math]\displaystyle{ (a - \varepsilon, a + \varepsilon) }[/math] znajdują się prawie wszystkie wyrazy ciągu [math]\displaystyle{ (a_n) }[/math] (to znaczy wszystkie poza co najwyżej skończoną ilością).
Uwaga C5
1) sens definicji jest taki: jeżeli liczba [math]\displaystyle{ a }[/math] jest granicą ciągu [math]\displaystyle{ (a_n) }[/math], to dla dowolnie małego [math]\displaystyle{ \varepsilon \gt 0 }[/math], poza przedziałem [math]\displaystyle{ (a - \varepsilon, a + \varepsilon) }[/math] może się znaleźć co najwyżej skończona ilość wyrazów ciągu [math]\displaystyle{ (a_n) }[/math]
2) słabsze żądanie, aby w przedziale [math]\displaystyle{ (a - \varepsilon, a + \varepsilon) }[/math] znajdowała się nieskończona ilość wyrazów ciągu, nie prowadzi do poprawnej definicji granicy. Przykładowo, w przedziale [math]\displaystyle{ (1 - \varepsilon, 1 + \varepsilon) }[/math] znajduje się nieskończenie wiele wyrazów ciągu [math]\displaystyle{ a_n = (-1)^n }[/math], ale ani liczba [math]\displaystyle{ 1 }[/math], ani liczba [math]\displaystyle{ - 1 }[/math] nie są granicami tego ciągu. O ciągu [math]\displaystyle{ a_n = (- 1)^n }[/math] mówimy, że nie ma granicy.
3) ze względu na równoważność warunków
- [math]\displaystyle{ \quad a_n \in (a - \varepsilon, a + \varepsilon) }[/math]
- [math]\displaystyle{ \quad a - \varepsilon \lt a_n \lt a + \varepsilon }[/math]
- [math]\displaystyle{ \quad - \varepsilon \lt a_n - a \lt \varepsilon }[/math]
- [math]\displaystyle{ \quad | a_n - a | \lt \varepsilon }[/math]
definicja C4 może być wypowiedziana następująco
Definicja C6
Liczbę [math]\displaystyle{ a }[/math] będziemy nazywali granicą ciągu [math]\displaystyle{ (a_n) }[/math], jeżeli dla dowolnego [math]\displaystyle{ \varepsilon \gt 0 }[/math] prawie wszystkie wyrazy ciągu [math]\displaystyle{ (a_n) }[/math] spełniają warunek [math]\displaystyle{ |a_n - a| \lt \varepsilon }[/math].
Definicja C7
Ciąg [math]\displaystyle{ (a_n) }[/math] mający granicę (w rozumieniu definicji C4 lub C6) będziemy nazywali ciągiem zbieżnym, a fakt ten zapisujemy symbolicznie następująco
- [math]\displaystyle{ \lim_{n \to \infty} a_n = a }[/math] lub [math]\displaystyle{ a_n \longrightarrow a }[/math]
(od łacińskiego słowa limes oznaczającego granicę).
Zauważmy jeszcze, że wprost z definicji granicy wynika
Twierdzenie C8
- 1. [math]\displaystyle{ \quad \lim_{n \to \infty} a_n = a \qquad \iff \qquad \lim_{n \to \infty} (a_n - a) = 0 \qquad \iff \qquad \lim_{n \to \infty} | a_n - a | = 0 }[/math]
- 2. [math]\displaystyle{ \quad \lim_{n \to \infty} a_n = 0 \qquad \iff \qquad \lim_{n \to \infty} | a_n | = 0 }[/math]
- 3. [math]\displaystyle{ \quad \lim_{n \to \infty} a_n = a \qquad \implies \qquad \lim_{n \to \infty} | a_n | = | a | }[/math]
Twierdzenie C9
Jeżeli ciąg [math]\displaystyle{ (a_n) }[/math] jest zbieżny, to jest ograniczony.
Twierdzenie C10 (twierdzenie o trzech ciągach)
Jeżeli istnieje taka liczba całkowita [math]\displaystyle{ N_0 }[/math], że dla każdego [math]\displaystyle{ n \gt N_0 }[/math] jest spełniony warunek
- [math]\displaystyle{ a_n \leqslant x_n \leqslant b_n }[/math]
oraz
- [math]\displaystyle{ \lim_{n \to \infty} a_n = \lim_{n \to \infty} b_n = g }[/math]
to [math]\displaystyle{ \lim_{n \to \infty} x_n = g }[/math].
Bez dowodu podamy kilka ważnych twierdzeń.
Twierdzenie C11*
Jeżeli istnieje taka liczba całkowita [math]\displaystyle{ n }[/math] i rzeczywista [math]\displaystyle{ M }[/math], że dla każdego [math]\displaystyle{ k \gt n }[/math] jest
- [math]\displaystyle{ a_{k + 1}\geqslant a_k \qquad }[/math] oraz [math]\displaystyle{ \qquad a_k \leqslant M }[/math]
to ciąg [math]\displaystyle{ (a_k) }[/math] jest zbieżny.
Inaczej mówiąc: ciąg rosnący i ograniczony od góry jest zbieżny.
Twierdzenie C12*
Jeżeli istnieje taka liczba całkowita [math]\displaystyle{ n }[/math] i rzeczywista [math]\displaystyle{ M }[/math], że dla każdego [math]\displaystyle{ k \gt n }[/math] jest
- [math]\displaystyle{ a_{k + 1} \leqslant a_k \qquad }[/math] oraz [math]\displaystyle{ \qquad a_k \geqslant M }[/math]
to ciąg [math]\displaystyle{ (a_k) }[/math] jest zbieżny.
Inaczej mówiąc: ciąg malejący i ograniczony od dołu jest zbieżny.
Twierdzenie C13*
Jeżeli [math]\displaystyle{ \lim_{n \to \infty} a_n = a }[/math] oraz [math]\displaystyle{ \lim_{n \to \infty} b_n = b }[/math], gdzie [math]\displaystyle{ a, b }[/math] są dowolnymi liczbami rzeczywistymi, to
- [math]\displaystyle{ \quad \lim_{n \to \infty} (a_n \pm b_n) = a \pm b }[/math]
- [math]\displaystyle{ \quad \lim_{n \to \infty} (a_n \cdot b_n) = a \cdot b }[/math]
Jeżeli dodatkowo dla każdego [math]\displaystyle{ n }[/math] jest [math]\displaystyle{ b_n \neq 0 }[/math] i [math]\displaystyle{ b \neq 0 }[/math], to
- 3. [math]\displaystyle{ \quad \lim_{n \to \infty} {\small\frac{a_n}{b_n}} = {\small\frac{a}{b}} }[/math]
Twierdzenie C14
Jeżeli [math]\displaystyle{ \lim_{n \to \infty} a_n = 0 }[/math], zaś ciąg [math]\displaystyle{ (x_n) }[/math] jest ograniczony, czyli istnieje taka liczba [math]\displaystyle{ M \gt 0 }[/math], że dla każdej wartości [math]\displaystyle{ n }[/math] prawdziwa jest nierówność [math]\displaystyle{ | x_n | \lt M }[/math], to
- [math]\displaystyle{ \lim_{n \to \infty} (x_n \cdot a_n) = 0 }[/math]
Twierdzenie C15
Dla [math]\displaystyle{ a \geqslant 0 }[/math] i [math]\displaystyle{ n \geqslant 1 }[/math] prawdziwa jest nierówność
- [math]\displaystyle{ (1 + a)^{1 / n} \leqslant 1 + {\small\frac{a}{n}} }[/math]
Twierdzenie C16
Jeżeli [math]\displaystyle{ A \gt 0 }[/math], to [math]\displaystyle{ \lim_{n \to \infty} \sqrt[n]{A} = 1 }[/math].
Twierdzenie C17
Jeżeli prawie wszystkie wyrazy ciągu [math]\displaystyle{ (a_n) }[/math] spełniają warunek [math]\displaystyle{ 0 \lt m \lt a_n \lt M }[/math], to [math]\displaystyle{ \lim_{n \to \infty} \sqrt[n]{a_n} = 1 }[/math]
Twierdzenie C18
Następujące ciągi są silnie rosnące i zbieżne
[math]\displaystyle{ \quad 1. \quad }[/math] [math]\displaystyle{ \lim_{n \to \infty} \left( 1 + {\small\frac{1}{n}} \right)^n = e = 2.718281828 \ldots }[/math] [math]\displaystyle{ \quad 2. \quad }[/math] [math]\displaystyle{ \lim_{n \to \infty} \left( 1 - {\small\frac{1}{n}} \right)^n = {\small\frac{1}{e}} = 0.367879441 \ldots }[/math]
Twierdzenie C19
Dla [math]\displaystyle{ n \geqslant 2 }[/math] prawdziwe są następujące nierówności
[math]\displaystyle{ \quad 1. \quad }[/math] [math]\displaystyle{ {\small\frac{1}{n + 1}} \lt \log \left( 1 + {\small\frac{1}{n}} \right) \lt {\small\frac{1}{n}} }[/math] [math]\displaystyle{ \quad 2. \quad }[/math] [math]\displaystyle{ - {\small\frac{1}{n - 1}} \lt \log \left( 1 - {\small\frac{1}{n}} \right) \lt - {\small\frac{1}{n}} }[/math]
Liczby pierwsze w ciągach arytmetycznych
Twierdzenie C20
Każda liczba naturalna [math]\displaystyle{ n \geqslant 2 }[/math] jest liczbą pierwszą lub iloczynem liczb pierwszych.
Twierdzenie C21 (Euklides, IV w. p.n.e.)
Istnieje nieskończenie wiele liczb pierwszych.
Twierdzenie C22
Jeżeli liczba naturalna [math]\displaystyle{ n }[/math] jest postaci [math]\displaystyle{ 4 k + 3 }[/math][2], to ma dzielnik postaci [math]\displaystyle{ 4 k + 3 }[/math] będący liczbą pierwszą.
Twierdzenie C23
Istnieje nieskończenie wiele liczb pierwszych postaci [math]\displaystyle{ 4 k + 3 }[/math].
Twierdzenie C24
Jeżeli liczba naturalna [math]\displaystyle{ n }[/math] jest postaci [math]\displaystyle{ 6 k + 5 }[/math], to ma dzielnik postaci [math]\displaystyle{ 6 k + 5 }[/math] będący liczbą pierwszą.
Twierdzenie C25
Istnieje nieskończenie wiele liczb pierwszych postaci [math]\displaystyle{ 6 k + 5 }[/math].
Twierdzenie C26
Istnieje nieskończenie wiele liczb pierwszych postaci [math]\displaystyle{ 3 k + 2 }[/math].
Uwaga C27
Zauważmy, że liczby postaci [math]\displaystyle{ 2 k + 1 }[/math] to wszystkie liczby nieparzyste dodatnie. Ponieważ wszystkie liczby pierwsze (poza liczbą [math]\displaystyle{ 2 }[/math]) są liczbami nieparzystymi, to wśród liczb postaci [math]\displaystyle{ 2 k + 1 }[/math] występuje nieskończenie wiele liczb pierwszych.
Wszystkie omówione wyżej przypadki ciągów arytmetycznych: [math]\displaystyle{ 2 k + 1 }[/math], [math]\displaystyle{ 3 k + 2 }[/math], [math]\displaystyle{ 4 k + 3 }[/math] i [math]\displaystyle{ 6 k + 5 }[/math], w których występuje nieskończona ilość liczb pierwszych są szczególnymi przypadkami udowodnionego w 1837 roku twierdzenia
Twierdzenie C28* (Peter Gustav Lejeune Dirichlet, 1837)
Niech [math]\displaystyle{ a \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ b \in \mathbb{Z} }[/math]. Jeżeli liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] są względnie pierwsze, to w ciągu arytmetycznym [math]\displaystyle{ a k + b }[/math] występuje nieskończenie wiele liczb pierwszych.
Uwaga C29
Dowód twierdzenia Dirichleta jest bardzo trudny. Natomiast bardzo łatwo można pokazać, że dowolny ciąg arytmetyczny [math]\displaystyle{ a k + b }[/math] zawiera nieskończenie wiele liczb złożonych. Istotnie, jeżeli liczby [math]\displaystyle{ a, b }[/math] nie są względnie pierwsze, to wszystkie wyrazy ciągu są liczbami złożonymi. Jeżeli [math]\displaystyle{ a, b }[/math] są względnie pierwsze i [math]\displaystyle{ b \gt 1 , }[/math] to wystarczy przyjąć [math]\displaystyle{ k = b t }[/math]. Jeżeli są względnie pierwsze i [math]\displaystyle{ b = 1 }[/math], to wystarczy przyjąć [math]\displaystyle{ k = a t^2 + 2 t }[/math], wtedy
- [math]\displaystyle{ a k + 1 = a^2 t^2 + 2 a t + 1 = (a t + 1)^2 }[/math]
Uwaga C30
Wiemy już, że w przypadku gdy liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] są względnie pierwsze, to w ciągu arytmetycznym [math]\displaystyle{ a k + b }[/math] występuje nieskończenie wiele liczb pierwszych. Pojawia się pytanie o to, czy możliwe jest oszacowanie najmniejszej liczby pierwszej [math]\displaystyle{ p }[/math] w takim ciągu. Jakkolwiek przypuszczamy, że prawdziwe jest oszacowanie [math]\displaystyle{ p \lt a^2 }[/math], to stan naszej obecnej wiedzy ujmuje twierdzenie Linnika[3][4][5][6], które podajemy niżej. Trzeba było ponad pół wieku wysiłku wielu matematyków, aby pokazać, że w twierdzeniu Linnika możemy przyjąć [math]\displaystyle{ L = 5 }[/math][7]. Bombieri, Friedlander i Iwaniec udowodnili[8], że dla prawie wszystkich liczb [math]\displaystyle{ a }[/math] prawdziwe jest oszacowanie [math]\displaystyle{ L \leqslant 2 }[/math].
Twierdzenie C31* (Jurij Linnik, 1944)
Niech [math]\displaystyle{ a, b \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ p_{\min} (a, b) }[/math] oznacza najmniejszą liczbę pierwszą w ciągu arytmetycznym [math]\displaystyle{ a k + b }[/math], gdzie [math]\displaystyle{ k \in \mathbb{Z}_+ }[/math]. Jeżeli [math]\displaystyle{ \gcd (a, b) = 1 }[/math] i [math]\displaystyle{ b \in [1, a - 1] }[/math], to istnieją takie stałe [math]\displaystyle{ L \gt 0 }[/math] i [math]\displaystyle{ a_0 \geqslant 2 }[/math], że dla wszystkich [math]\displaystyle{ a \gt a_0 }[/math] prawdziwe jest oszacowanie
- [math]\displaystyle{ p_{\min} (a, b) \lt a^L }[/math]
Zadanie C32
Pokazać, że z twierdzenia Linnika wynika istnienie takich stałych [math]\displaystyle{ c, L \gt 0 }[/math], że dla każdego [math]\displaystyle{ a \geqslant 2 }[/math] prawdziwe jest oszacowanie
- [math]\displaystyle{ p(a) \lt c a^L }[/math]
gdzie
- [math]\displaystyle{ p(a) = \underset{\gcd (a, b) = 1}{\max_{1 \leqslant b \lt a}} p_{\min} (a, b) }[/math]
Przykład C33
Pokazaliśmy (zobacz C32), że istnieją takie stałe [math]\displaystyle{ c, L \gt 0 }[/math], że dla każdego [math]\displaystyle{ a \geqslant 2 }[/math] prawdziwe jest oszacowanie
- [math]\displaystyle{ p(a) \lt c a^L }[/math]
gdzie
- [math]\displaystyle{ p(a) = \underset{\gcd (a, b) = 1}{\max_{1 \leqslant b \lt a}} p_{\min} (a, b) }[/math]
Ponieważ [math]\displaystyle{ p(a) \gt a }[/math], to prawdziwy jest ciąg nierówności
- [math]\displaystyle{ 1 \lt {\small\frac{\log p (a)}{\log a}} \lt {\small\frac{\log c}{\log a}} + L \leqslant \left| {\small\frac{\log c}{\log a}} \right| + L \leqslant {\small\frac{\left| \log c \right|}{\log 2}} + L }[/math]
Wynika stąd, że dla [math]\displaystyle{ a \geqslant 2 }[/math] funkcja [math]\displaystyle{ {\small\frac{\log p (a)}{\log a}} }[/math] jest ograniczona.
Na zamieszczonym niżej obrazku przedstawiono pierwszych czternaście punktów funkcji [math]\displaystyle{ {\small\frac{\log p (a)}{\log a}} }[/math]. Ze względu na skokowy charakter zmian tej funkcji najwygodniej będzie przedstawić jej wykres, pokazując jedynie jej maksymalne i minimalne wartości w wybranych podprzedziałach [math]\displaystyle{ \mathbb{Z}_+ }[/math]. Mówiąc precyzyjnie, zamieszczone zostały wykresy funkcji
- [math]\displaystyle{ f(t) = \max_{2^t \leqslant a \lt 2^{t + 1}} {\small\frac{\log p (a)}{\log a}} \qquad \qquad \qquad \qquad g(t) = \min_{2^t \leqslant a \lt 2^{t + 1}} {\small\frac{\log p (a)}{\log a}} \qquad \qquad \qquad \qquad h(a) = 1 + {\small\frac{2 \log \log a}{\log a}} }[/math]
gdzie [math]\displaystyle{ t \in \mathbb{Z}_+ }[/math].
Przypuszczamy, że prawdziwe jest znacznie silniejsze oszacowanie najmniejszej liczby pierwszej w ciągu arytmetycznym[9][10]
- [math]\displaystyle{ p(a) \sim a \log^2 \! a }[/math]
W takim przypadku mielibyśmy
- [math]\displaystyle{ {\small\frac{\log p (a)}{\log a}} \sim 1 + {\small\frac{2 \log \log a}{\log a}} }[/math]
Rzeczywiście, porównanie wykresów funkcji [math]\displaystyle{ f(t) }[/math] i [math]\displaystyle{ h(a) }[/math] wydaje się potwierdzać to przypuszczenie dla [math]\displaystyle{ a \in [2, 2^{22}] }[/math].
W tabeli zestawiliśmy wszystkie wartości funkcji [math]\displaystyle{ {\small\frac{\log p (a)}{\log a}} }[/math] większe od [math]\displaystyle{ 1.75 }[/math] dla [math]\displaystyle{ a \in [2, 2^{22}] }[/math]
[math]\displaystyle{ \boldsymbol{a} }[/math] [math]\displaystyle{ \boldsymbol{\log_2 \! a} }[/math] [math]\displaystyle{ \boldsymbol{p(a)} }[/math] [math]\displaystyle{ \boldsymbol{{\small\frac{\log p(a)}{\log a}}} }[/math] [math]\displaystyle{ 31 }[/math] [math]\displaystyle{ 4.95 }[/math] [math]\displaystyle{ 577 }[/math] [math]\displaystyle{ 1.851446 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 2.32 }[/math] [math]\displaystyle{ 19 }[/math] [math]\displaystyle{ 1.829482 }[/math] [math]\displaystyle{ 13 }[/math] [math]\displaystyle{ 3.70 }[/math] [math]\displaystyle{ 103 }[/math] [math]\displaystyle{ 1.806947 }[/math] [math]\displaystyle{ 47 }[/math] [math]\displaystyle{ 5.55 }[/math] [math]\displaystyle{ 967 }[/math] [math]\displaystyle{ 1.785437 }[/math] [math]\displaystyle{ 19 }[/math] [math]\displaystyle{ 4.24 }[/math] [math]\displaystyle{ 191 }[/math] [math]\displaystyle{ 1.783794 }[/math] [math]\displaystyle{ 61 }[/math] [math]\displaystyle{ 5.93 }[/math] [math]\displaystyle{ 1511 }[/math] [math]\displaystyle{ 1.780771 }[/math] [math]\displaystyle{ 11 }[/math] [math]\displaystyle{ 3.46 }[/math] [math]\displaystyle{ 71 }[/math] [math]\displaystyle{ 1.777675 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 1.58 }[/math] [math]\displaystyle{ 7 }[/math] [math]\displaystyle{ 1.771243 }[/math]
Rozważmy zbiór [math]\displaystyle{ S }[/math] takich liczb [math]\displaystyle{ a }[/math], że prawdziwe jest oszacowanie [math]\displaystyle{ p (a) \lt a \log^2 \! a }[/math]. Bez trudu możemy podać przykłady takich liczb, ale nie wiemy, czy jest ich nieskończenie wiele.
[math]\displaystyle{ \boldsymbol{n} }[/math] [math]\displaystyle{ \boldsymbol{a=p_1 \cdot \ldots \cdot p_n} }[/math] [math]\displaystyle{ \boldsymbol{\log_2 \! a} }[/math] [math]\displaystyle{ \boldsymbol{p(a)} }[/math] [math]\displaystyle{ \boldsymbol{{\small\frac{a \log^2 \! a}{p(a)}}} }[/math] [math]\displaystyle{ \boldsymbol{{\small\frac{\log p(a)}{\log a}}} }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 6 }[/math] [math]\displaystyle{ 2.584 }[/math] [math]\displaystyle{ 11 }[/math] [math]\displaystyle{ 1.751 }[/math] [math]\displaystyle{ 1.338290 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 30 }[/math] [math]\displaystyle{ 4.906 }[/math] [math]\displaystyle{ 79 }[/math] [math]\displaystyle{ 4.392 }[/math] [math]\displaystyle{ 1.284679 }[/math] [math]\displaystyle{ 4 }[/math] [math]\displaystyle{ 210 }[/math] [math]\displaystyle{ 7.714 }[/math] [math]\displaystyle{ 761 }[/math] [math]\displaystyle{ 7.889 }[/math] [math]\displaystyle{ 1.240789 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 2310 }[/math] [math]\displaystyle{ 11.173 }[/math] [math]\displaystyle{ 20477 }[/math] [math]\displaystyle{ 6.766 }[/math] [math]\displaystyle{ 1.281737 }[/math] [math]\displaystyle{ 6 }[/math] [math]\displaystyle{ 30030 }[/math] [math]\displaystyle{ 14.874 }[/math] [math]\displaystyle{ 520547 }[/math] [math]\displaystyle{ 6.132 }[/math] [math]\displaystyle{ 1.276692 }[/math] [math]\displaystyle{ 7 }[/math] [math]\displaystyle{ 510510 }[/math] [math]\displaystyle{ 18.961 }[/math] [math]\displaystyle{ 11024723 }[/math] [math]\displaystyle{ 7.999 }[/math] [math]\displaystyle{ 1.233770 }[/math] [math]\displaystyle{ 8 }[/math] [math]\displaystyle{ 9699690 }[/math] [math]\displaystyle{ 23.209 }[/math] [math]\displaystyle{ 375095881 }[/math] [math]\displaystyle{ 6.692 }[/math] [math]\displaystyle{ 1.227199 }[/math] [math]\displaystyle{ 9 }[/math] [math]\displaystyle{ 223092870 }[/math] [math]\displaystyle{ 27.733 }[/math] [math]\displaystyle{ 11799966613 }[/math] [math]\displaystyle{ 6.986 }[/math] [math]\displaystyle{ 1.206432 }[/math] [math]\displaystyle{ 10 }[/math] [math]\displaystyle{ 6469693230 }[/math] [math]\displaystyle{ 32.591 }[/math] [math]\displaystyle{ 451404994867 }[/math] [math]\displaystyle{ 7.314 }[/math] [math]\displaystyle{ 1.187922 }[/math] [math]\displaystyle{ 11 }[/math] [math]\displaystyle{ 200560490130 }[/math] [math]\displaystyle{ 37.545 }[/math] [math]\displaystyle{ 19822720510961 }[/math] [math]\displaystyle{ 6.852 }[/math] [math]\displaystyle{ 1.176506 }[/math] [math]\displaystyle{ 12 }[/math] [math]\displaystyle{ 7420738134810 }[/math] [math]\displaystyle{ 42.754 }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math]
Ponieważ [math]\displaystyle{ p(a) \gt a }[/math], to prawdziwy jest układ nierówności
- [math]\displaystyle{ 1 \lt {\small\frac{\log p (a)}{\log a}} \lt 1 + {\small\frac{2 \log \log a}{\log a}} }[/math]
Jeżeli zbiór [math]\displaystyle{ S }[/math] jest nieskończony, to z twierdzenia o trzech ciągach otrzymujemy
- [math]\displaystyle{ \underset{a \in S}{\lim_{a \rightarrow \infty}} {\small\frac{\log p (a)}{\log a}} = 1 }[/math]
W konsekwencji wykres funkcji
- [math]\displaystyle{ g(t) = \underset{2^t \leqslant a \lt 2^{t + 1}}{\min} {\small\frac{\log p (a)}{\log a}} }[/math]
będzie opadał ku prostej [math]\displaystyle{ y = 1 }[/math].
Zadanie C34
Pokazać, że istnieje nieskończenie wiele liczb pierwszych zakończonych cyframi 99, przykładowo 199, 499, 599, 1399, 1499, ...
Definicja C35
Niech [math]\displaystyle{ a \geqslant 2 }[/math] będzie liczbą całkowitą. Wartość funkcji [math]\displaystyle{ \pi(n; a, b) }[/math] jest równa ilości liczb pierwszych nie większych od [math]\displaystyle{ n }[/math], które przy dzieleniu przez [math]\displaystyle{ a }[/math] dają resztę [math]\displaystyle{ b }[/math].
Uwaga C36
Zauważmy, że w twierdzeniu Dirichleta na liczby [math]\displaystyle{ a }[/math] oraz [math]\displaystyle{ b }[/math] nałożone są minimalne warunki: [math]\displaystyle{ a \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ b \in \mathbb{Z} }[/math]. Sytuacja w przypadku funkcji [math]\displaystyle{ \pi (n ; a, b) }[/math] jest odmienna – tutaj mamy [math]\displaystyle{ a \geqslant 2 }[/math] oraz [math]\displaystyle{ 0 \leqslant b \leqslant a - 1 }[/math]. Jest tak dlatego, że podział liczb pierwszych, który odzwierciedla funkcja [math]\displaystyle{ \pi (n ; a, b) }[/math], jest podziałem pierwotnym, a twierdzenie Dirichleta jest tylko jego uzasadnieniem. Podział
liczb pierwszych musi być też precyzyjnie określony, tak aby zachodził naturalny związek
- [math]\displaystyle{ \sum_{b = 0}^{a - 1} \pi (n ; a, b) = \pi (n) }[/math]
Oczywiście nie przeszkadza to w liczeniu liczb pierwszych w dowolnym ciągu arytmetycznym. Niech na przykład
- [math]\displaystyle{ u_k = 7 k + 101 = 7 (k + 14) + 3 \qquad }[/math] gdzie [math]\displaystyle{ k = 0, 1, \ldots }[/math]
Ilość liczb pierwszych w ciagu [math]\displaystyle{ (u_k) }[/math] jest równa
- [math]\displaystyle{ \pi (n ; 7, 3) - \pi (7 \cdot 13 + 3 ; 7, 3) = \pi (n ; 7, 3) - 5 }[/math]
Zadanie C37
Pokazać, że dla dowolnej liczby całkowitej [math]\displaystyle{ m \geqslant 1 }[/math]
- wśród liczb naturalnych zawsze można wskazać [math]\displaystyle{ m }[/math] kolejnych liczb, które są złożone
- w ciągu arytmetycznym [math]\displaystyle{ a k + b }[/math], gdzie liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] są względnie pierwsze, zawsze można wskazać [math]\displaystyle{ m }[/math] kolejnych wyrazów, które są złożone
Przykład C38
Rozważmy ciąg arytmetyczny [math]\displaystyle{ u_k = 3 k + 2 }[/math] i wskaźnik
- [math]\displaystyle{ k_0 = \prod^{12}_{j = 0} (3 j + 2) = 3091650738176000 }[/math]
Trzynaście wyrazów tego szeregu dla [math]\displaystyle{ k = k_0 + t }[/math], gdzie [math]\displaystyle{ t = 0, 1, \ldots, 12 }[/math] to oczywiście liczby złożone, ale wyrazy dla [math]\displaystyle{ k = k_0 - 1 }[/math] i [math]\displaystyle{ k = k_0 + 13 }[/math] są liczbami pierwszymi.
Przeszukując ciąg [math]\displaystyle{ u_k = 3 k + 2 }[/math], możemy łatwo znaleźć, że pierwsze trzynaście kolejnych wyrazów złożonych pojawia się już dla [math]\displaystyle{ k = 370, 371, \ldots, 382 }[/math].
Twierdzenie C39
Jeżeli [math]\displaystyle{ n \geqslant 3 }[/math], to istnieje [math]\displaystyle{ n }[/math] kolejnych liczb naturalnych, wśród których znajduje się dokładnie [math]\displaystyle{ r \leqslant \pi (n) }[/math] liczb pierwszych.
Przykład C40
Czytelnik może łatwo sprawdzić, że ciąg [math]\displaystyle{ ( 1308, \ldots, 1407 ) }[/math] stu kolejnych liczb całkowitych zawiera dokładnie [math]\displaystyle{ 8 }[/math] liczb pierwszych.
Zadanie C41
Pokazać, nie korzystając z twierdzenia C39, że istnieje [math]\displaystyle{ 1000 }[/math] kolejnych liczb naturalnych, wśród których jest dokładnie jedna liczba pierwsza.
Zadanie C42
Pokazać, że istnieje [math]\displaystyle{ 20 }[/math] kolejnych liczb naturalnych postaci [math]\displaystyle{ 6 k + 1 }[/math], wśród których jest dokładnie [math]\displaystyle{ 5 }[/math] liczb pierwszych.
Twierdzenie C43
Niech [math]\displaystyle{ a, b \in \mathbb{Z} }[/math] oraz [math]\displaystyle{ a \geqslant 2 }[/math] i [math]\displaystyle{ 0 \leqslant b \leqslant a - 1 }[/math]. Jeżeli liczby [math]\displaystyle{ a }[/math] oraz [math]\displaystyle{ b }[/math] są względnie pierwsze, to istnieje [math]\displaystyle{ n }[/math] kolejnych liczb postaci [math]\displaystyle{ a k + b }[/math], wśród których znajduje się dokładnie [math]\displaystyle{ r \leqslant \pi (a (n - 1) + b ; a, b) }[/math] liczb pierwszych.
Zadanie C44
Niech [math]\displaystyle{ p \geqslant 5 }[/math] będzie liczbą pierwszą. Pokazać, że w ciągu [math]\displaystyle{ 6 k + 1 }[/math] występują kwadraty wszystkich liczb pierwszych [math]\displaystyle{ p }[/math].
Zadanie C45
Dany jest ciąg arytmetyczny [math]\displaystyle{ a k + b }[/math], gdzie liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] są względnie pierwsze. Pokazać, że
- jeżeli liczba pierwsza [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ a }[/math], to żaden wyraz ciągu [math]\displaystyle{ a k + b }[/math] nie jest podzielny przez [math]\displaystyle{ p }[/math]
- jeżeli liczba pierwsza [math]\displaystyle{ p }[/math] nie dzieli [math]\displaystyle{ a }[/math], to istnieje nieskończenie wiele wyrazów ciągu [math]\displaystyle{ a k + b }[/math], które są podzielne przez [math]\displaystyle{ p }[/math]
Uwaga C46
Łatwo możemy napisać w PARI/GP funkcję, która zwraca najmniejszą liczbę naturalną [math]\displaystyle{ k_0 }[/math], dla której wyraz ciągu arytmetycznego [math]\displaystyle{ a k + b }[/math] jest podzielny przez [math]\displaystyle{ p }[/math] (przy założeniu, że liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ p }[/math] są względnie pierwsze).
f(a,b,p) = lift( Mod(-b,p)*Mod(a,p)^(-1) )
Ciągi nieskończone i liczby pierwsze
Uwaga C47
Choć wiele ciągów jest dobrze znanych i równie dobrze zbadanych, to nie wiemy, czy zawierają one nieskończenie wiele liczb pierwszych. Przykładowo
[math]\displaystyle{ \quad 1. \quad }[/math] [math]\displaystyle{ a_n = n^2 + 1 }[/math] A002496 [math]\displaystyle{ \quad 2. \quad }[/math] [math]\displaystyle{ b_n = n^2 - n - 1 }[/math] A002327 [math]\displaystyle{ \quad 3. \quad }[/math] [math]\displaystyle{ c_n = n^2 + n + 1 }[/math] A002383 [math]\displaystyle{ \quad 4. \quad }[/math] [math]\displaystyle{ d_n = n^4 + 1 }[/math] A000068 [math]\displaystyle{ \quad 5. \quad }[/math] [math]\displaystyle{ u_n = n! + 1 }[/math] A002981 [math]\displaystyle{ \quad 6. \quad }[/math] [math]\displaystyle{ v_n = n! - 1 }[/math] A002982 [math]\displaystyle{ \quad 7. \quad }[/math] [math]\displaystyle{ M_n = 2^n - 1 }[/math] (liczby Mersenne'a) A000043 [math]\displaystyle{ \quad 8. \quad }[/math] [math]\displaystyle{ F_n = 2^{2^n} + 1 }[/math] (liczby Fermata) A019434 [math]\displaystyle{ \quad 9. \quad }[/math] [math]\displaystyle{ F_n (a) = a^{2^n} + 1 }[/math] (uogólnione liczby Fermata, [math]\displaystyle{ a }[/math] parzyste) MathWorld
Nie wiemy, czy istnieje wielomian całkowity [math]\displaystyle{ W(n) }[/math] stopnia większego niż jeden taki, że [math]\displaystyle{ W(n) }[/math] jest liczbą pierwszą dla nieskończenie wielu liczb [math]\displaystyle{ n }[/math].
Przykład C48
Łatwo sprawdzić, że wartości wielomianu [math]\displaystyle{ W(n) = n^2 + n + 41 }[/math] są liczbami pierwszymi dla [math]\displaystyle{ 1 \leqslant n \leqslant 39 }[/math]. Oczywiście [math]\displaystyle{ 41 \mid W(41) }[/math].
Twierdzenie C49
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].
Twierdzenie C50
Dla dowolnej liczby naturalnej [math]\displaystyle{ n \geqslant 1 }[/math] liczba [math]\displaystyle{ x - y }[/math] jest dzielnikiem wyrażenia [math]\displaystyle{ x^n - y^n }[/math].
Twierdzenie C51
Jeżeli [math]\displaystyle{ n \geqslant 2 }[/math] oraz [math]\displaystyle{ a^n - 1 }[/math] jest liczbą pierwszą, to [math]\displaystyle{ a = 2 }[/math] i [math]\displaystyle{ n }[/math] jest liczbą pierwszą.
Ciągi arytmetyczne liczb pierwszych
Uwaga C52
Ciągi arytmetyczne liczb pierwszych[11][12] zbudowane z dwóch liczb pierwszych nie są interesujące, bo dowolne dwie liczby tworzą ciąg arytmetyczny. Dlatego będziemy się zajmowali ciągami arytmetycznymi liczb pierwszych o długości [math]\displaystyle{ n \geqslant 3 }[/math].
Ponieważ nie da się zbudować ciągu arytmetycznego liczb pierwszych o długości [math]\displaystyle{ n \geqslant 3 }[/math], w którym pierwszym wyrazem jest liczba [math]\displaystyle{ p_0 = 2 }[/math], to będą nas interesowały ciągi rozpoczynające się od liczby pierwszej [math]\displaystyle{ p_0 \geqslant 3 }[/math]
Jeżeli do liczby pierwszej nieparzystej dodamy dodatnią liczbę nieparzystą, to otrzymamy liczbę parzystą złożoną, zatem różnica ciągu arytmetycznego [math]\displaystyle{ d }[/math] musi być liczbą parzystą, aby zbudowanie jakiegokolwiek ciągu arytmetycznego liczb pierwszych o długości [math]\displaystyle{ n \geqslant 3 }[/math] było możliwe.
Istnienie nieskończenie wiele ciągów arytmetycznych liczb pierwszych o długości [math]\displaystyle{ n = 3 }[/math] pokazano już wiele lat temu[13]. Temat ciągów arytmetycznych liczb pierwszych zyskał na popularności[14] po udowodnieniu przez Bena Greena i Terence'a Tao twierdzenia o istnieniu dowolnie długich (ale skończonych) ciągów arytmetycznych liczb pierwszych[15].
Twierdzenie C53* (Ben Green i Terence Tao, 2004)
Dla dowolnej liczby naturalnej [math]\displaystyle{ n \geqslant 2 }[/math] istnieje nieskończenie wiele [math]\displaystyle{ n }[/math]-wyrazowych ciągów arytmetycznych liczb pierwszych.
Przykład C54
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości [math]\displaystyle{ n = 3 }[/math] i [math]\displaystyle{ n = 4 }[/math].
Przykład C55
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości [math]\displaystyle{ n = 5 }[/math] i [math]\displaystyle{ n = 6 }[/math].
Przykład C56
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości [math]\displaystyle{ n = 7 }[/math] i [math]\displaystyle{ n = 8 }[/math].
Przykład C57
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości [math]\displaystyle{ n = 9 }[/math] i [math]\displaystyle{ n = 10 }[/math].
Twierdzenie C58
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math] oraz [math]\displaystyle{ a, d, k, k_0 \in \mathbb{Z} }[/math]. Jeżeli liczby [math]\displaystyle{ d }[/math] i [math]\displaystyle{ n }[/math] są względnie pierwsze, to reszty [math]\displaystyle{ r_1, r_2, \ldots, r_n }[/math] z dzielenia [math]\displaystyle{ n }[/math] liczb [math]\displaystyle{ x_k }[/math] postaci
- [math]\displaystyle{ x_k = a + k d \qquad }[/math] dla [math]\displaystyle{ \; k = k_0 + 1, \ldots, k_0 + n }[/math]
przez liczbę [math]\displaystyle{ n }[/math] są wszystkie różne i tworzą zbiór [math]\displaystyle{ S = \{ 0, 1, \ldots, n - 1 \} }[/math]. W szczególności wynika stąd, że wśród liczb [math]\displaystyle{ x_k }[/math] jedna jest podzielna przez [math]\displaystyle{ n }[/math].
Twierdzenie C59
Niech [math]\displaystyle{ d \in \mathbb{Z}_+ }[/math] i niech będzie dany ciąg arytmetyczny liczb pierwszych o długości [math]\displaystyle{ n }[/math]
- [math]\displaystyle{ p_k = p_0 + k d \qquad }[/math] dla [math]\displaystyle{ \; k = 0, 1, \ldots, n - 1 }[/math]
Z żądania, aby dany ciąg arytmetyczny był ciągiem arytmetycznym liczb pierwszych, wynika, że muszą być spełnione następujące warunki
- [math]\displaystyle{ p_0 \nmid d }[/math]
- [math]\displaystyle{ n \leqslant p_0 }[/math]
- [math]\displaystyle{ P(n - 1) \mid d }[/math]
- jeżeli liczba pierwsza [math]\displaystyle{ q }[/math] nie dzieli [math]\displaystyle{ d }[/math], to [math]\displaystyle{ n \leqslant q }[/math]
gdzie [math]\displaystyle{ P(t) }[/math] jest iloczynem wszystkich liczb pierwszych nie większych od [math]\displaystyle{ t }[/math].
Uwaga C60
Czasami, zamiast pisać „ciąg arytmetyczny liczb pierwszych”, będziemy posługiwali się skrótem PAP od angielskiej nazwy „prime arithmetic progression”. Konsekwentnie zapis PAP-[math]\displaystyle{ n }[/math] będzie oznaczał ciąg arytmetyczny liczb pierwszych o długości [math]\displaystyle{ n }[/math], a zapis PAP[math]\displaystyle{ (n, d, q) }[/math] ciąg arytmetyczny liczb pierwszych o długości [math]\displaystyle{ n }[/math], pierwszym wyrazie [math]\displaystyle{ q }[/math] i różnicy [math]\displaystyle{ d }[/math].
Uwaga C61
Jakkolwiek sądzimy, że istnieje nieskończenie wiele ciągów arytmetycznych liczb pierwszych rozpoczynających się od dowolnej liczby pierwszej [math]\displaystyle{ q }[/math] i o dowolnej długości [math]\displaystyle{ 3 \leqslant n \leqslant q }[/math], to obecnie jest to tylko nieudowodnione przypuszczenie.
Dlatego nawet dla najmniejszej liczby pierwszej [math]\displaystyle{ q }[/math] takiej, że [math]\displaystyle{ q \nmid d }[/math] nierówność [math]\displaystyle{ n \leqslant q }[/math], pokazana w twierdzeniu C59, pozostaje nadal tylko oszacowaniem. W szczególności nie możemy z góry przyjmować, że dla liczby [math]\displaystyle{ n = q }[/math] znajdziemy taką liczbę [math]\displaystyle{ d }[/math] będącą wielokrotnością liczby [math]\displaystyle{ P(q - 1) }[/math] i niepodzielną przez [math]\displaystyle{ q }[/math], że będzie istniał PAP[math]\displaystyle{ (q, d, q) }[/math].
Przykład C62
Rozważmy dwie różnice [math]\displaystyle{ d_1 = 6 = 2 \cdot 3 }[/math] oraz [math]\displaystyle{ d_2 = 42 = 2 \cdot 3 \cdot 7 }[/math]. Zauważmy, że liczba pierwsza [math]\displaystyle{ 5 }[/math] nie dzieli ani [math]\displaystyle{ d_1 }[/math], ani [math]\displaystyle{ d_2 }[/math]. Co więcej, liczba pierwsza [math]\displaystyle{ 5 }[/math] jest najmniejszą liczbą pierwszą, która nie dzieli rozpatrywanych różnic, zatem nierówność [math]\displaystyle{ n \leqslant 5 }[/math] zapewnia najmocniejsze oszacowanie długości ciągu [math]\displaystyle{ n }[/math]. Łatwo sprawdzamy w zamieszczonych tabelach, że dla [math]\displaystyle{ d = 6 }[/math] oraz dla [math]\displaystyle{ d = 42 }[/math] są ciągi o długości [math]\displaystyle{ 3, 4, 5 }[/math], ale nie ma ciągów o długości [math]\displaystyle{ 6, 7, \ldots }[/math]
W szczególności z twierdzenia C59 wynika, że szukając ciągów arytmetycznych liczb pierwszych o określonej długości [math]\displaystyle{ n }[/math], należy szukać ich tylko dla różnic [math]\displaystyle{ d }[/math] będących wielokrotnością liczby [math]\displaystyle{ P(n - 1) }[/math].
Zadanie C63
Wiemy, że liczby pierwsze [math]\displaystyle{ p \gt 3 }[/math] można przedstawić w jednej z postaci [math]\displaystyle{ 6 k - 1 }[/math] lub [math]\displaystyle{ 6 k + 1 }[/math]. Pokazać, że jeżeli [math]\displaystyle{ p_0 = 3 }[/math], to dwa następne wyrazu rosnącego ciągu arytmetycznego liczb pierwszych są różnych postaci.
Zadanie C64
Wiemy, że liczby pierwsze [math]\displaystyle{ p \gt 3 }[/math] można przedstawić w jednej z postaci [math]\displaystyle{ 6 k - 1 }[/math] lub [math]\displaystyle{ 6 k + 1 }[/math]. Pokazać, że wszystkie wyrazy rosnącego ciągu arytmetycznego liczb pierwszych [math]\displaystyle{ p_0, p_1, \ldots, p_{n - 1} }[/math], gdzie [math]\displaystyle{ p_0 \geqslant 5 }[/math] i [math]\displaystyle{ n \geqslant 3 }[/math] muszą być jednakowej postaci.
Zadanie C65
Niech [math]\displaystyle{ d \gt 0 }[/math] będzie różnicą ciągu arytmetycznego liczb pierwszych o długości [math]\displaystyle{ n }[/math]
- [math]\displaystyle{ p_k = p_0 + k d \qquad }[/math] dla [math]\displaystyle{ \; k = 0, 1, \ldots, n - 1 }[/math]
Pokazać, nie korzystając z twierdzenia C59, że jeżeli liczba pierwsza [math]\displaystyle{ q }[/math] nie dzieli [math]\displaystyle{ d }[/math], to [math]\displaystyle{ n \leqslant q }[/math].
Twierdzenie C66
Niech [math]\displaystyle{ q }[/math] będzie liczbą pierwszą, a liczby pierwsze
- [math]\displaystyle{ p_k = p_0 + k d \qquad }[/math] gdzie [math]\displaystyle{ \; k = 0, 1, \ldots, q - 1 }[/math]
tworzą ciąg arytmetyczny o długości [math]\displaystyle{ q }[/math] i różnicy [math]\displaystyle{ d \gt 0 }[/math].
Równość [math]\displaystyle{ p_0 = q }[/math] zachodzi wtedy i tylko wtedy, gdy [math]\displaystyle{ q \nmid d }[/math].
Uwaga C67
Niech ciąg arytmetyczny liczb pierwszych o długości [math]\displaystyle{ n }[/math] ma postać
- [math]\displaystyle{ p_k = p_0 + k d \qquad }[/math] dla [math]\displaystyle{ \; k = 0, 1, \ldots, n - 1 }[/math]
Z udowodnionych wyżej twierdzeń C59 i C66 wynika, że ciągi arytmetyczne liczb pierwszych o długości [math]\displaystyle{ n }[/math] można podzielić na dwie grupy
- jeżeli [math]\displaystyle{ n }[/math] jest liczbą pierwszą i [math]\displaystyle{ n \nmid d }[/math], to [math]\displaystyle{ P(n - 1) \mid d }[/math] oraz [math]\displaystyle{ p_0 = n }[/math] (dla ustalonego [math]\displaystyle{ d }[/math] może istnieć tylko jeden ciąg)
- jeżeli [math]\displaystyle{ n }[/math] jest liczbą złożoną lub [math]\displaystyle{ n \mid d }[/math], to [math]\displaystyle{ P(n) \mid d }[/math] oraz [math]\displaystyle{ p_0 \gt n }[/math]
Funkcja [math]\displaystyle{ P(t) }[/math] jest iloczynem wszystkich liczb pierwszych nie większych od [math]\displaystyle{ t }[/math].
Przykład C68
Niech różnica ciągu arytmetycznego liczb pierwszych wynosi [math]\displaystyle{ d = 10^t }[/math], gdzie [math]\displaystyle{ t \geqslant 1 }[/math]. Zauważmy, że dla dowolnego [math]\displaystyle{ t }[/math] liczba [math]\displaystyle{ 3 }[/math] jest najmniejszą liczbą pierwszą, która nie dzieli [math]\displaystyle{ d }[/math]. Z oszacowania [math]\displaystyle{ n \leqslant 3 }[/math] wynika, że musi być [math]\displaystyle{ n = 3 }[/math].
Jeżeli długość ciągu [math]\displaystyle{ n = 3 }[/math] i [math]\displaystyle{ n \nmid d }[/math], to musi być [math]\displaystyle{ p_0 = n = 3 }[/math] i może istnieć tylko jeden PAP dla każdego [math]\displaystyle{ d }[/math]. W przypadku [math]\displaystyle{ t \leqslant 10000 }[/math] jedynie dla [math]\displaystyle{ t = 1, 5, 6, 17 }[/math] wszystkie liczby ciągu arytmetycznego [math]\displaystyle{ (3, 3 + 10^t, 3 + 2 \cdot 10^t) }[/math] są pierwsze.
Zadanie C69
Znaleźć wszystkie PAP[math]\displaystyle{ (n, d, p) }[/math] dla [math]\displaystyle{ d = 2, 4, 8, 10, 14, 16 }[/math].
Zadanie C70
Znaleźć wszystkie PAP[math]\displaystyle{ (n, d, p) }[/math] dla [math]\displaystyle{ n = 3, 5, 7, 11 }[/math] i [math]\displaystyle{ d = P (n - 1) }[/math].
Przykład C71
Przedstawiamy przykładowe ciągi arytmetyczne liczb pierwszych takie, że [math]\displaystyle{ n = p_0 }[/math] dla [math]\displaystyle{ n = 3, 5, 7, 11, 13 }[/math]. Zauważmy, że wypisane w tabeli wartości [math]\displaystyle{ d }[/math] są wielokrotnościami liczby [math]\displaystyle{ P(n - 1) }[/math].
Przykład C72
Liczby [math]\displaystyle{ 3, 5, 7 }[/math] są najprostszym przykładem ciągu arytmetycznego kolejnych liczb pierwszych. Zauważmy, że tylko w przypadku [math]\displaystyle{ n = 3 }[/math] możliwa jest sytuacja, że [math]\displaystyle{ n = p_0 = 3 }[/math]. Istotnie, łatwo stwierdzamy, że
- ponieważ [math]\displaystyle{ p_0 }[/math] i [math]\displaystyle{ p_1 }[/math] są kolejnymi liczbami pierwszymi, to [math]\displaystyle{ p_1 - p_0 \lt p_0 }[/math] (zobacz zadanie B22)
- dla dowolnej liczby pierwszej [math]\displaystyle{ q \geqslant 5 }[/math] jest [math]\displaystyle{ q \lt P (q - 1) }[/math] (zobacz zadanie B26)
Przypuśćmy teraz, że istnieje ciąg arytmetyczny kolejnych liczb pierwszych taki, że [math]\displaystyle{ n = p_0 \geqslant 5 }[/math]. Mamy
- [math]\displaystyle{ d = p_1 - p_0 \lt p_0 \lt P (p_0 - 1) = P (n - 1) }[/math]
Zatem [math]\displaystyle{ P(n - 1) \nmid d }[/math], co jest niemożliwe.
Wynika stąd, że poza przypadkiem [math]\displaystyle{ n = p_0 = 3 }[/math] ciąg arytmetyczny kolejnych liczb pierwszych musi spełniać warunek [math]\displaystyle{ P(n) \mid d }[/math], czyli [math]\displaystyle{ P(n) \mid (p_1 - p_0) }[/math].
Poniższe tabele przedstawiają przykładowe ciągi arytmetyczne kolejnych liczb pierwszych o długościach [math]\displaystyle{ n = 3, 4, 5, 6 }[/math] dla rosnących wartości [math]\displaystyle{ p_0 }[/math]. Nie istnieje ciąg arytmetyczny kolejnych liczb pierwszych o długości [math]\displaystyle{ n = 7 }[/math] dla [math]\displaystyle{ p_0 \lt 10^{13} }[/math]. Prawdopodobnie CPAP-7 pojawią się dopiero dla [math]\displaystyle{ p_0 \sim 10^{20} }[/math].
Znane są ciągi arytmetyczne kolejnych liczb pierwszych o długościach [math]\displaystyle{ n \leqslant 10 }[/math][16].
Zadanie C73
Uzasadnij przypuszczenie, że ciągów arytmetycznych kolejnych liczb pierwszych o długości [math]\displaystyle{ n = 7 }[/math] możemy oczekiwać dopiero dla [math]\displaystyle{ p_0 \sim 10^{20} }[/math].
Uzupełnienie
Twierdzenie C74 (lemat Bézouta)
Jeżeli liczby całkowite [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] nie są jednocześnie równe zeru, a największy wspólny dzielnik tych liczb jest równy [math]\displaystyle{ D }[/math], to istnieją takie liczby całkowite [math]\displaystyle{ x, y }[/math], że
- [math]\displaystyle{ a x + b y = D }[/math]
Twierdzenie C75 (lemat Euklidesa)
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą oraz [math]\displaystyle{ a, b, d \in \mathbb{Z} }[/math].
- jeżeli [math]\displaystyle{ d \mid a b }[/math] i liczba [math]\displaystyle{ d }[/math] jest względnie pierwsza z [math]\displaystyle{ a }[/math], to [math]\displaystyle{ d \mid b }[/math]
- jeżeli [math]\displaystyle{ p \mid a b }[/math], to [math]\displaystyle{ p \mid a }[/math] lub [math]\displaystyle{ p \mid b }[/math]
Twierdzenie C76
Niech [math]\displaystyle{ a, b, m \in \mathbb{Z} }[/math]. Jeżeli [math]\displaystyle{ a \mid m \; }[/math] i [math]\displaystyle{ \; b \mid m }[/math] oraz [math]\displaystyle{ \gcd (a, b) = 1 }[/math], to [math]\displaystyle{ a b \mid m }[/math].
Twierdzenie C77
Niech [math]\displaystyle{ a, b, c \in \mathbb{Z} }[/math]. Równanie [math]\displaystyle{ a x + b y = c }[/math] ma rozwiązanie wtedy i tylko wtedy, gdy największy wspólny dzielnik liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] jest dzielnikiem liczby [math]\displaystyle{ c }[/math].
Uwaga C78
Z twierdzenia C77 wynika, że szukając rozwiązań równania [math]\displaystyle{ A x + B y = C }[/math] w liczbach całkowitych, powinniśmy
- obliczyć największy wspólny dzielnik [math]\displaystyle{ D }[/math] liczb [math]\displaystyle{ A }[/math] i [math]\displaystyle{ B }[/math]
- jeżeli [math]\displaystyle{ D \gt 1 }[/math], należy sprawdzić, czy [math]\displaystyle{ D \mid C }[/math]
- jeżeli [math]\displaystyle{ D \nmid C }[/math], to równanie [math]\displaystyle{ A x + B y = C }[/math] nie ma rozwiązań w liczbach całkowitych
- jeżeli [math]\displaystyle{ D \mid C }[/math], należy podzielić obie strony równania [math]\displaystyle{ A x + B y = C }[/math] przez [math]\displaystyle{ D }[/math] i przejść do rozwiązywania równania równoważnego [math]\displaystyle{ a x + b y = c }[/math], gdzie [math]\displaystyle{ a = {\small\frac{A}{D}} }[/math], [math]\displaystyle{ b = {\small\frac{B}{D}} }[/math], [math]\displaystyle{ c = {\small\frac{C}{D}} }[/math], zaś największy wspólny dzielnik liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] jest równy [math]\displaystyle{ 1 }[/math].
Twierdzenie C79
Niech [math]\displaystyle{ a, b, c \in \mathbb{Z} }[/math]. Jeżeli liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] są względnie pierwsze, to równanie
- [math]\displaystyle{ a x + b y = c }[/math]
ma nieskończenie wiele rozwiązań w liczbach całkowitych.
Jeżeli para liczb całkowitych [math]\displaystyle{ (x_0, y_0) }[/math] jest jednym z tych rozwiązań, to wszystkie pozostałe rozwiązania całkowite można otrzymać ze wzorów
- [math]\displaystyle{ x = x_0 + b t }[/math]
- [math]\displaystyle{ y = y_0 - a t }[/math]
gdzie [math]\displaystyle{ t }[/math] jest dowolną liczbą całkowitą.
Przykład C80
Rozwiązania równania
- [math]\displaystyle{ a x + b y = c }[/math]
gdzie [math]\displaystyle{ \gcd (a, b) = 1 }[/math], które omówiliśmy w poprzednim twierdzeniu, najłatwiej znaleźć korzystając w PARI/GP z funkcji gcdext(a, b)
. Funkcja ta zwraca wektor liczb [x0, y0, d]
, gdzie [math]\displaystyle{ d = \gcd (a, b) }[/math], a liczby [math]\displaystyle{ x_0 }[/math] i [math]\displaystyle{ y_0 }[/math] są rozwiązaniami równania
- [math]\displaystyle{ a x_0 + b y_0 = \gcd (a, b) }[/math]
Ponieważ założyliśmy, że [math]\displaystyle{ \gcd (a, b) = 1 }[/math], to łatwo zauważmy, że
- [math]\displaystyle{ a(c x_0) + b (c y_0) = c }[/math]
Zatem para liczb całkowitych [math]\displaystyle{ (c x_0, c y_0) }[/math] jest jednym z rozwiązań równania
- [math]\displaystyle{ a x + b y = c }[/math]
i wszystkie pozostałe rozwiązania uzyskujemy ze wzorów
- [math]\displaystyle{ x = c x_0 + b t }[/math]
- [math]\displaystyle{ y = c y_0 - a t }[/math]
Niech [math]\displaystyle{ a = 7 \; }[/math] i [math]\displaystyle{ \; b = 17 }[/math]. Funkcja gcdext(7,17)
zwraca wektor [5, -2, 1]
, zatem rozwiązaniami równania [math]\displaystyle{ 7 x + 17 y = 1 }[/math] są liczby
- [math]\displaystyle{ x = 5 + 17 t }[/math]
- [math]\displaystyle{ y = - 2 - 7 t }[/math]
A rozwiązaniami równania [math]\displaystyle{ 7 x + 17 y = 10 }[/math] są liczby
- [math]\displaystyle{ x = 50 + 17 t }[/math]
- [math]\displaystyle{ y = - 20 - 7 t }[/math]
Przypisy
- ↑ Korzystamy w tym momencie z zasady dobrego uporządkowania zbioru liczb naturalnych, która stwierdza, że każdy niepusty podzbiór zbioru liczb naturalnych zawiera element najmniejszy. (Wiki-pl), (Wiki-en)
- ↑ Określenie, że „liczba [math]\displaystyle{ n }[/math] jest postaci [math]\displaystyle{ a k + b }[/math]”, jest jedynie bardziej czytelnym (obrazowym) zapisem stwierdzenia, że reszta z dzielenia liczby [math]\displaystyle{ n }[/math] przez [math]\displaystyle{ a }[/math] wynosi [math]\displaystyle{ b }[/math]. Zapis „liczba [math]\displaystyle{ n }[/math] jest postaci [math]\displaystyle{ a k - 1 }[/math]” oznacza, że reszta z dzielenia liczby [math]\displaystyle{ n }[/math] przez [math]\displaystyle{ a }[/math] wynosi [math]\displaystyle{ a - 1 }[/math].
- ↑ Wikipedia, Linnik's theorem, (Wiki-en)
- ↑ MathWorld, Linnik's Theorem. (MathWorld)
- ↑ Yuri Linnik, On the least prime in an arithmetic progression. I. The basic theorem, Mat. Sb. (N.S.) 15 (1944) 139–178.
- ↑ Yuri Linnik, On the least prime in an arithmetic progression. II. The Deuring-Heilbronn phenomenon, Mat. Sb. (N.S.) 15 (1944) 347–368.
- ↑ Triantafyllos Xylouris, Über die Nullstellen der Dirichletschen L-Funktionen und die kleinste Primzahl in einer arithmetischen Progression, Bonner Mathematische Schriften, vol. 404, Univ. Bonn, 2011, Diss.
- ↑ Enrico Bombieri, John B. Friedlander and Henryk Iwaniec, Primes in Arithmetic Progressions to Large Moduli. III, Journal of the American Mathematical Society 2 (1989) 215-224
- ↑ Paul Turán, Über die Primzahlen der arithmetischen Progression, Acta Sci. Szeged 8 (1937), 226-235
- ↑ Samuel S. Wagstaff, Jr., Greatest of the Least Primes in Arithmetic Progressions Having a Given Modulus, Mathematics of Computation Vol. 33, No. 147 (1979), 1073-1080
- ↑ Wikipedia, Primes in arithmetic progression, (Wiki-en)
- ↑ MathWorld, Prime Arithmetic Progression, (LINK)
- ↑ J. G. van der Corput, Über Summen von Primzahlen und Primzahlquadraten, Mathematische Annalen, 116 (1939) 1-50, (LINK)
- ↑ Wikipedia, Largest known primes in AP, (Wiki-en)
- ↑ Ben Green and Terence Tao, The Primes Contain Arbitrarily Long Arithmetic Progressions., Ann. of Math. (2) 167 (2008), 481-547, (LINK1), Preprint. 8 Apr 2004, (LINK2)
- ↑ Wikipedia, Primes in arithmetic progression - Largest known consecutive primes in AP, (Wiki-en)
- ↑ Henryk Dąbrowski, Twierdzenie Czebyszewa o liczbie pierwszej między n i 2n - Uwagi do twierdzenia, (LINK)