Ciągi liczbowe

Z Henryk Dąbrowski
Przejdź do nawigacji Przejdź do wyszukiwania
12.03.2022



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]
Dowód

Punkt 1.
Prawdziwość twierdzenia wynika ze względu na identyczność warunków, które muszą spełniać prawie wszystkie wyrazy ciągu

[math]\displaystyle{ | a_n - a | \lt \varepsilon \qquad \iff \qquad | (a_n - a) - 0 | \lt \varepsilon \qquad \iff \qquad \big|| a_n - a | - 0 \big| \lt \varepsilon }[/math]

Punkt 2.
Jest to jedynie szczególny przypadek punktu 1. dla [math]\displaystyle{ a = 0 }[/math].

Punkt 3.
Dla dowolnych liczb [math]\displaystyle{ x, y \in \mathbb{R} }[/math] prawdziwa jest nierówność

[math]\displaystyle{ \big|| x | - | y | \big| \leqslant |x - y| }[/math]

Wynika stąd, że jeżeli dla prawie wszystkich wyrazów ciągu [math]\displaystyle{ (a_n) }[/math] spełniona jest nierówność [math]\displaystyle{ |a_n - a| \lt \varepsilon }[/math], to tym bardziej prawdą jest, że [math]\displaystyle{ \big|| a_n | - | a |\big| \lt \varepsilon }[/math]


Twierdzenie C9 (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].

Dowód

Niech [math]\displaystyle{ \varepsilon }[/math] będzie dowolną, ustaloną liczbą większą od [math]\displaystyle{ 0 }[/math]. Z założenia prawie wszystkie wyrazy ciągu [math]\displaystyle{ (a_n) }[/math] spełniają warunek [math]\displaystyle{ |a_n - g| \lt \varepsilon }[/math]. Możemy założyć, że są to wszystkie wyrazy, poczynając od wyrazu [math]\displaystyle{ N_a }[/math]. Podobnie prawie wszystkie wyrazy ciągu [math]\displaystyle{ (b_n) }[/math] spełniają warunek [math]\displaystyle{ |b_n - g| \lt \varepsilon }[/math] i podobnie możemy założyć, że są to wszystkie wyrazy, poczynając od wyrazu [math]\displaystyle{ N_b }[/math]

Nierówność [math]\displaystyle{ a_n \leqslant x_n \leqslant b_n }[/math] jest spełniona dla wszystkich wyrazów, poczynając od [math]\displaystyle{ N_0 }[/math], zatem oznaczając przez [math]\displaystyle{ M }[/math] największą z liczb [math]\displaystyle{ N_a }[/math], [math]\displaystyle{ N_b }[/math], [math]\displaystyle{ N_0 }[/math], możemy napisać, że o ile [math]\displaystyle{ n \gt M }[/math], to spełnione są jednocześnie nierówności

  • [math]\displaystyle{ \quad g - \varepsilon \lt a_n \lt g + \varepsilon\ }[/math]
  • [math]\displaystyle{ \quad g - \varepsilon \lt b_n \lt g + \varepsilon\ }[/math]
  • [math]\displaystyle{ \quad a_n \leqslant x_n \leqslant b_n }[/math]

Z powyższych nierówności wynika natychmiast następujący ciąg nierówności

[math]\displaystyle{ g - \varepsilon \lt a_n \leqslant x_n \leqslant b_n \lt g + \varepsilon }[/math]

Co oznacza, że dla [math]\displaystyle{ n \gt M }[/math] zachodzi

[math]\displaystyle{ g - \varepsilon \lt x_n \lt g + \varepsilon }[/math]

Czyli prawie wszystkie wyrazy ciągu [math]\displaystyle{ (x_n) }[/math] spełniają warunek [math]\displaystyle{ |x_n - g| \lt \varepsilon }[/math]. Co kończy dowód.


Bez dowodu podamy kilka ważnych twierdzeń.
Twierdzenie C10*
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 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} \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 C12*
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

  1. [math]\displaystyle{ \quad \lim_{n \to \infty} (a_n \pm b_n) = a \pm b }[/math]
  2. [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} \frac{a_n}{b_n} = \frac{a}{b} }[/math]


Twierdzenie C13
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]
Dowód

Wystarczy pokazać, że (zobacz twierdzenie C8 p.2)

[math]\displaystyle{ \lim_{n \to \infty} |x_n \cdot a_n| = 0 }[/math]

Z założenia prawdziwe jest oszacowanie

[math]\displaystyle{ 0 \leqslant |x_n \cdot a_n| \leqslant |a_n| \cdot M }[/math]

Zatem z twierdzenia o trzech ciągach otrzymujemy natychmiast, że

[math]\displaystyle{ \lim_{n \to \infty} |x_n \cdot a_n| = 0 }[/math]

Co kończy dowód.


Twierdzenie C14
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 + \frac{a}{n} }[/math]
Dowód

Wzór jest prawdziwy dla [math]\displaystyle{ a = 0 }[/math]. Zakładając, że [math]\displaystyle{ a \gt 0 }[/math] i korzystając ze wzoru dwumianowego, mamy dla [math]\displaystyle{ n \geqslant 1 }[/math]

[math]\displaystyle{ \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]\displaystyle{ \;\; \geqslant \sum_{k=0}^{1}\left [\binom{n}{k} \cdot \left ( \frac{a}{n} \right )^k \right ] = }[/math]
[math]\displaystyle{ \;\; = 1 + n \cdot \frac{a}{n} = }[/math]
[math]\displaystyle{ \;\; = 1 + a }[/math]

Co należało pokazać.


Twierdzenie C15
Jeżeli [math]\displaystyle{ A \gt 0 }[/math], to [math]\displaystyle{ \lim_{n \to \infty} \sqrt[n]{A} = 1 }[/math].

Dowód

Dla [math]\displaystyle{ A \gt 1 }[/math] możemy napisać [math]\displaystyle{ A = 1 + a }[/math], gdzie [math]\displaystyle{ a \gt 0 }[/math], wtedy z twierdzenia C14 otrzymujemy

[math]\displaystyle{ 1 \lt \sqrt[n]{A} = (1 + a)^{1 / n} \leqslant 1 + \frac{a}{n} }[/math]

Z twierdzenia o trzech ciągach dostajemy natychmiast (dla [math]\displaystyle{ A \gt 1 }[/math])

[math]\displaystyle{ \lim_{n \to \infty} \sqrt[n]{A} = 1 }[/math]

W przypadku gdy [math]\displaystyle{ 0 \lt A \lt 1 }[/math], możemy napisać [math]\displaystyle{ A = \frac{1}{B} }[/math], gdzie [math]\displaystyle{ B \gt 1 }[/math], wtedy ze względu na udowodniony wyżej rezultat [math]\displaystyle{ \lim_{n \to \infty} \sqrt[n]{B} = 1 }[/math]

[math]\displaystyle{ \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]

Jeżeli [math]\displaystyle{ A = 1 }[/math], to [math]\displaystyle{ \sqrt[n]{A} = 1 }[/math] dla każdego [math]\displaystyle{ n \geqslant 1 }[/math]. Co kończy dowód.


Twierdzenie C16
Jeżeli prawie wszystkie wyrazy ciągu 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]

Dowód

Z założenia dla prawie wszystkich wyrazów ciągu [math]\displaystyle{ (a_n) }[/math] jest

[math]\displaystyle{ 0 \lt m \leqslant a_n \leqslant M }[/math]

Zatem dla prawie wszystkich wyrazów ciągu [math]\displaystyle{ a_n }[/math] mamy

[math]\displaystyle{ \sqrt[n]{m} \leqslant \sqrt[n]{a_n} \leqslant \sqrt[n]{M} }[/math]

Z twierdzenia C15 wiemy, że [math]\displaystyle{ \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]\displaystyle{ \lim_{n \to \infty} \sqrt[n]{a_n} = 1 }[/math]


Twierdzenie C17
Następujące ciągi są silnie rosnące i zbieżne

Dowód

Punkt 1
W twierdzeniu A6 pokazaliśmy, że ciąg

[math]\displaystyle{ a_n = \left( 1 + \frac{1}{n} \right)^n }[/math]

jest silnie rosnący i ograniczony od góry. Zatem z twierdzenia C10 wynika, że jest zbieżny. Liczbę będącą granicą tego ciągu oznaczamy literą [math]\displaystyle{ e }[/math], jest ona podstawą logarytmu naturalnego.

Punkt 2
Pokażemy najpierw, że ciąg [math]\displaystyle{ \left( 1 - \frac{1}{n} \right)^n }[/math] jest silnie rosnący. Musimy pokazać, że prawdziwa jest nierówność

[math]\displaystyle{ \left( 1 - \frac{1}{n + 1} \right)^{n + 1} \gt \left( 1 - \frac{1}{n} \right)^n }[/math]

Łatwo sprawdzamy prawdziwość nierówności dla [math]\displaystyle{ n = 1 }[/math]. Załóżmy teraz, że [math]\displaystyle{ n \geqslant 2 }[/math]. Przekształcając,

[math]\displaystyle{ \left( \frac{n}{n + 1} \right)^{n + 1} \gt \left( \frac{n - 1}{n} \right)^n }[/math]
[math]\displaystyle{ \frac{n}{n + 1} \cdot \left( \frac{n}{n + 1} \right)^n \cdot \left( \frac{n}{n - 1} \right)^n \gt 1 }[/math]
[math]\displaystyle{ \left( \frac{n^2}{n^2 - 1} \right)^n \gt \frac{n + 1}{n} }[/math]

otrzymujemy nierówność równoważną,

[math]\displaystyle{ \left( 1 + \frac{1}{n^2 - 1} \right)^n \gt 1 + \frac{1}{n} }[/math]

którą już łatwo udowodnić, bo

[math]\displaystyle{ \left( 1 + \frac{1}{n^2 - 1} \right)^n \gt \left( 1 + \frac{1}{n^2} \right)^n = \sum_{k = 0}^{n} \binom{n}{k} \cdot \left( \frac{1}{n^2} \right)^k \gt \sum_{k = 0}^{1} \binom{n}{k} \cdot \frac{1}{n^{2k}} = 1 + \frac{1}{n} }[/math]

Ponieważ dla każdego [math]\displaystyle{ n \geqslant 1 }[/math] jest [math]\displaystyle{ \left( 1 - \frac{1}{n} \right)^n \leqslant 1 }[/math] (bo iloczyn liczb mniejszych od [math]\displaystyle{ 1 }[/math] nie może być liczbą większą do jedności), to z twierdzenia C10 wynika, że ciąg ten jest zbieżny. Zatem możemy napisać

[math]\displaystyle{ \underset{n \rightarrow \infty}{\lim} \left( 1 - \frac{1}{n} \right)^n = g }[/math]

Rozważmy teraz iloczyn wypisanych w twierdzeniu ciągów

[math]\displaystyle{ \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]

Łatwo widzimy, że ciąg [math]\displaystyle{ \left( 1 - \frac{1}{n^2} \right)^{n^2} }[/math] jest podciągiem ciągu [math]\displaystyle{ \left( 1 - \frac{1}{n} \right)^n }[/math], zatem jest ograniczony i dla [math]\displaystyle{ n \geqslant 2 }[/math] spełniony jest układ nierówności

[math]\displaystyle{ 0 \lt \left( \frac{3}{4} \right)^4 \leqslant \left( 1 - \frac{1}{n^2} \right)^{n^2} \leqslant 1 }[/math]

Z twierdzenia C16 dostajemy

[math]\displaystyle{ \lim_{n \to \infty} \left[ \left( 1 - \frac{1}{n^2} \right)^{n^2} \right]^{1 / n} = 1 }[/math]

Z twierdzenia C12 p. 2 wynika natychmiast, że

[math]\displaystyle{ 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]

Zatem [math]\displaystyle{ g = \frac{1}{e} }[/math].


Twierdzenie C18
Dla [math]\displaystyle{ n \geqslant 2 }[/math] prawdziwe są następujące nierówności

Dowód

Ponieważ ciąg [math]\displaystyle{ \left( 1 + \frac{1}{n} \right)^n }[/math] jest silnie rosnący, to

[math]\displaystyle{ \left( 1 + \frac{1}{n} \right)^n \lt e }[/math]

Logarytmując powyższą nierówność, mamy

[math]\displaystyle{ n \cdot \log \left( 1 + \frac{1}{n} \right) \lt 1 }[/math]

Stąd wynika natychmiast, że

[math]\displaystyle{ \log \left( 1 + \frac{1}{n} \right) \lt \frac{1}{n} }[/math]


Ponieważ ciąg [math]\displaystyle{ \left( 1 - \frac{1}{n} \right)^n }[/math] również jest silnie rosnący, to postępując analogicznie, dostajemy

[math]\displaystyle{ \left( 1 - \frac{1}{n} \right)^n \lt \frac{1}{e} }[/math]
[math]\displaystyle{ n \cdot \log \left( 1 - \frac{1}{n} \right) \lt - 1 }[/math]
[math]\displaystyle{ \log \left( 1 - \frac{1}{n} \right) \lt - \frac{1}{n} }[/math]


Przekształcając otrzymane wzory, otrzymujemy

[math]\displaystyle{ - \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) \lt - \frac{1}{n + 1} }[/math]

oraz

[math]\displaystyle{ - \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) \lt \frac{1}{n - 1} }[/math]



Liczby pierwsze w ciągach arytmetycznych

Twierdzenie C19
Każda liczba naturalna [math]\displaystyle{ n \geqslant 2 }[/math] jest liczbą pierwszą lub iloczynem liczb pierwszych.

Dowód

Pierwszy sposób

Przypuśćmy, że istnieją liczby naturalne większe od [math]\displaystyle{ 1 }[/math], które nie są liczbami pierwszymi ani nie są iloczynami liczb pierwszych. Niech [math]\displaystyle{ m }[/math] oznacza najmniejszą[1] z takich liczb. Z założenia [math]\displaystyle{ m }[/math] nie jest liczbą pierwszą, zatem [math]\displaystyle{ m }[/math] może być zapisana w postaci [math]\displaystyle{ m = a \cdot b }[/math], gdzie liczby [math]\displaystyle{ a, b }[/math] są liczbami naturalnymi mniejszymi od [math]\displaystyle{ m }[/math].

Ponieważ [math]\displaystyle{ m }[/math] jest najmniejszą liczbą naturalną, która nie jest liczbą pierwszą ani nie jest iloczynem liczb pierwszych, to liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] muszą być liczbami złożonymi, ale jako mniejsze od [math]\displaystyle{ m }[/math] są one iloczynami liczb pierwszych, zatem i liczba [math]\displaystyle{ m }[/math] musi być iloczynem liczb pierwszych.

Uzyskana sprzeczność dowodzi, że nasze przypuszczenie jest fałszywe.


Drugi sposób

Indukcja matematyczna. Twierdzenie jest oczywiście prawdziwe dla [math]\displaystyle{ n = 2 }[/math]. Zakładając, że twierdzenie jest prawdziwe dla wszystkich liczb naturalnych [math]\displaystyle{ k \in [2, n] }[/math], dla liczby [math]\displaystyle{ n + 1 }[/math] mamy dwie możliwości

  • [math]\displaystyle{ n + 1 }[/math] jest liczbą pierwszą (wtedy twierdzenie jest prawdziwe w sposób oczywisty)
  • [math]\displaystyle{ n + 1 }[/math] jest liczbą złożoną wtedy, [math]\displaystyle{ n + 1 = a b }[/math], gdzie [math]\displaystyle{ 1 \lt a, b \lt n + 1 }[/math]; zatem na podstawie założenia indukcyjnego liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] są liczbami pierwszymi lub iloczynami liczb pierwszych, czyli [math]\displaystyle{ n + 1 = a b }[/math] jest iloczynem liczb pierwszych.

Co należało pokazać.


Twierdzenie C20 (Euklides, IV w. p.n.e.)
Istnieje nieskończenie wiele liczb pierwszych.

Dowód

Przypuśćmy, że istnieje jedynie skończona ilość liczb pierwszych [math]\displaystyle{ p_1, p_2, \ldots, p_n }[/math] . Wtedy liczba [math]\displaystyle{ a = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1 }[/math] jest większa od jedności i z twierdzenia C19 wynika, że posiada dzielnik będący liczbą pierwszą, ale jak łatwo zauważyć żadna z liczb pierwszych [math]\displaystyle{ p_1, p_2, \ldots, p_n }[/math] nie jest dzielnikiem liczby [math]\displaystyle{ a }[/math]. Zatem istnieje liczba pierwsza [math]\displaystyle{ p }[/math] będąca dzielnikiem pierwszym liczby [math]\displaystyle{ a }[/math] i różna od każdej z liczb [math]\displaystyle{ p_1, p_2, \ldots, p_n }[/math]. Co kończy dowód.


Twierdzenie C21
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ą.

Dowód

Jeżeli [math]\displaystyle{ n }[/math] jest liczbą pierwszą, to twierdzenie jest dowiedzione. Zbadajmy zatem sytuację gdy [math]\displaystyle{ n }[/math] jest liczbą złożoną. Z założenia [math]\displaystyle{ n }[/math] jest liczbą nieparzystą, zatem możliwe są trzy typy iloczynów

[math]\displaystyle{ (4 a + 1) (4 b + 1) = 16 a b + 4 a + 4 b + 1 = 4 (4 a b + a + b) + 1 }[/math]
[math]\displaystyle{ (4 a + 1) (4 b + 3) = 16 a b + 12 a + 4 b + 3 = 4 (4 a b + 3 a + b) + 3 }[/math]
[math]\displaystyle{ (4 a + 3) (4 b + 3) = 16 a b + 12 a + 12 b + 9 = 4 (4 a b + 3 a + 3 b + 2) + 1 }[/math]

Widzimy, że liczba złożona postaci [math]\displaystyle{ 4 k + 3 }[/math] jest iloczynem liczb postaci [math]\displaystyle{ 4 k + 1 }[/math] i [math]\displaystyle{ 4 k + 3 }[/math]. Wynika stąd natychmiast, że liczba złożona postaci [math]\displaystyle{ 4 k + 3 }[/math] posiada dzielnik postaci [math]\displaystyle{ 4 k + 3 }[/math]. Niech [math]\displaystyle{ q }[/math] oznacza najmniejszy dzielnik liczby [math]\displaystyle{ n }[/math] postaci [math]\displaystyle{ 4 k + 3 }[/math]. Pokażemy, że [math]\displaystyle{ q }[/math] jest liczbą pierwszą. Istotnie, gdyby [math]\displaystyle{ q }[/math] była liczbą złożoną, to miałaby dzielnik [math]\displaystyle{ d }[/math] postaci [math]\displaystyle{ 4 k + 3 }[/math] i byłoby [math]\displaystyle{ d \lt q }[/math], wbrew założeniu, że [math]\displaystyle{ q }[/math] jest najmniejszym dzielnikiem liczby [math]\displaystyle{ n }[/math] postaci [math]\displaystyle{ 4 k + 3 }[/math]. Co kończy dowód.


Twierdzenie C22
Istnieje nieskończenie wiele liczb pierwszych postaci [math]\displaystyle{ 4 k + 3 }[/math].

Dowód

Przypuśćmy, że istnieje tylko skończona ilość liczb pierwszych postaci [math]\displaystyle{ 4 k + 3 }[/math]. Niech będą to liczby [math]\displaystyle{ p_1, \ldots, p_s }[/math]. Liczba

[math]\displaystyle{ M = 4 p_1 \cdot \ldots \cdot p_s - 1 = 4 (p_1 \cdot \ldots \cdot p_s - 1) + 3 }[/math]

jest postaci [math]\displaystyle{ 4 k + 3 }[/math] i jak wiemy z twierdzenia C21, ma dzielnik pierwszy [math]\displaystyle{ q }[/math] postaci [math]\displaystyle{ 4 k + 3 }[/math]. Ale jak łatwo zauważyć, żadna z liczb [math]\displaystyle{ p_1, \ldots, p_s }[/math] nie dzieli liczby [math]\displaystyle{ M }[/math]. Zatem istnieje liczba pierwsza [math]\displaystyle{ q }[/math] postaci [math]\displaystyle{ 4 k + 3 }[/math] różna od każdej z liczb [math]\displaystyle{ p_1, p_2, \ldots, p_s }[/math]. Otrzymana sprzeczność kończy dowód.


Twierdzenie C23
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ą.

Dowód

Jeżeli [math]\displaystyle{ n }[/math] jest liczbą pierwszą, to twierdzenie jest dowiedzione. Zbadajmy sytuację gdy [math]\displaystyle{ n }[/math] jest liczbą złożoną. Z twierdzenia C19 wiemy, że w tym przypadku liczba [math]\displaystyle{ n }[/math] będzie iloczynem liczb pierwszych. Zauważmy, że nieparzyste liczby pierwsze mogą być jedynie postaci [math]\displaystyle{ 6 k + 1 }[/math] lub [math]\displaystyle{ 6 k + 5 }[/math] (liczba [math]\displaystyle{ 6 k + 3 }[/math] jest liczbą złożoną). Ponieważ iloczyn liczb postaci [math]\displaystyle{ 6 k + 1 }[/math]

[math]\displaystyle{ (6 a + 1) (6 b + 1) = 36 a b + 6 a + 6 b + 1 = 6 (6 a b + a + b) + 1 }[/math]

jest liczbą postaci [math]\displaystyle{ 6 k + 1 }[/math], to w rozkładzie liczby [math]\displaystyle{ n }[/math] na czynniki pierwsze musi pojawić się przynajmniej jeden czynnik postaci [math]\displaystyle{ 6 k + 5 }[/math]. Co kończy dowód.


Twierdzenie C24
Istnieje nieskończenie wiele liczb pierwszych postaci [math]\displaystyle{ 6 k + 5 }[/math].

Dowód

Przypuśćmy, że istnieje tylko skończona ilość liczb pierwszych postaci [math]\displaystyle{ 6 k + 5 }[/math]. Niech będą to liczby [math]\displaystyle{ p_1, \ldots, p_s }[/math]. Liczba

[math]\displaystyle{ M = 6 p_1 \cdot \ldots \cdot p_s - 1 = 6 (p_1 \cdot \ldots \cdot p_s - 1) + 5 }[/math]

jest postaci [math]\displaystyle{ 6 k + 5 }[/math] i jak wiemy z twierdzenia C23 ma dzielnik pierwszy [math]\displaystyle{ q }[/math] postaci [math]\displaystyle{ 6 k + 5 }[/math]. Ale jak łatwo zauważyć żadna z liczb [math]\displaystyle{ p_1, \ldots, p_s }[/math] nie dzieli liczby [math]\displaystyle{ M }[/math]. Zatem istnieje liczba pierwsza [math]\displaystyle{ q }[/math] postaci [math]\displaystyle{ 6 k + 5 }[/math] różna od każdej z liczb [math]\displaystyle{ p_1, p_2, \ldots, p_s }[/math]. Otrzymana sprzeczność kończy dowód.


Twierdzenie C25
Istnieje nieskończenie wiele liczb pierwszych postaci [math]\displaystyle{ 3 k + 2 }[/math].

Dowód

Jeżeli [math]\displaystyle{ k = 2 j }[/math] jest liczbą parzystą, to otrzymujemy ciąg liczb parzystych

[math]\displaystyle{ 3 k + 2 = 6 j + 2 }[/math]

w którym jedynie liczba [math]\displaystyle{ 2 }[/math] jest liczbą pierwszą (dla [math]\displaystyle{ j = 0 }[/math]).

Jeżeli [math]\displaystyle{ k = 2 j + 1 }[/math] jest liczbą nieparzystą, to otrzymujemy ciąg liczb nieparzystych

[math]\displaystyle{ 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 C24). Zatem w ciągu arytmetycznym postaci [math]\displaystyle{ 3 k + 2 }[/math] występuje nieskończenie wiele liczb pierwszych.


Uwaga C26
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 C27* (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 C28
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 C29
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 C30* (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 C31
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]
Rozwiązanie

Oszacowanie podane w twierdzeniu Linnika

[math]\displaystyle{ p_{\min} (a, b) \lt a^L }[/math]

jest prawdziwe dla dowolnej liczby [math]\displaystyle{ b \in [1, a - 1] }[/math] względnie pierwszej z [math]\displaystyle{ a }[/math]. Jeżeli zdefiniujemy funkcję

[math]\displaystyle{ p(a) = \underset{\gcd (a, b) = 1}{\max_{1 \leqslant b \lt a}} p_{\min} (a, b) }[/math]

to możemy zapisać twierdzenie Linnika tak, aby po lewej stronie nie występowała liczba [math]\displaystyle{ b }[/math], co czyni zapis bardziej przejrzystym. Mamy

[math]\displaystyle{ p(a) \lt a^L }[/math]

dla wszystkich [math]\displaystyle{ a \gt a_0 }[/math]. Ponieważ dla [math]\displaystyle{ a \in [2, a_0] }[/math] funkcja [math]\displaystyle{ p(a) }[/math] przyjmuje wartości skończone, a dla [math]\displaystyle{ a \gt a_0 }[/math] jest [math]\displaystyle{ p(a) \lt a^L }[/math], to funkcja [math]\displaystyle{ {\small\frac{p (a)}{a^L}} }[/math] jest ograniczona od góry, czyli istnieje taka stała [math]\displaystyle{ c }[/math], że

[math]\displaystyle{ {\small\frac{p (a)}{a^L}} \lt c }[/math]

dla dowolnego [math]\displaystyle{ a \geqslant 2 }[/math]. Co należało pokazać.


Przykład C32
Pokazaliśmy (zobacz C31), ż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].

Linnik-22.png
Pokaż kod i dane do wykresu

W tabeli przedstawiamy dane, na podstawie których sporządziliśmy zamieszczony wyżej wykres. Mamy kolejno

  • przedział [math]\displaystyle{ U }[/math]
  • minimalną wartość [math]\displaystyle{ {\small\frac{\log p(a)}{\log a}} }[/math] w przedziale [math]\displaystyle{ U }[/math]
  • liczbę [math]\displaystyle{ a }[/math], która odpowiada minimalnej wartości [math]\displaystyle{ {\small\frac{\log p(a)}{\log a}} }[/math]
  • wartość [math]\displaystyle{ p(a) = \underset{\gcd (a, b) = 1}{\max_{1 \leqslant b \lt a}} p_{\min} (a, b) }[/math]
  • liczbę [math]\displaystyle{ b }[/math] taką, że najmniejsza liczba pierwsza w ciągu [math]\displaystyle{ a k + b }[/math] jest równa [math]\displaystyle{ p ( a ) }[/math]

Następnie podajemy analogiczne wartości dla maksymalnej wartości [math]\displaystyle{ {\small\frac{\log p(a)}{\log a}} }[/math] w przedziale [math]\displaystyle{ U }[/math]. Pominęliśmy dane dla początkowych przedziałów [math]\displaystyle{ [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ą.

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);
}
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);
}
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);
}

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]


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.


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 C33
Pokazać, że istnieje nieskończenie wiele liczb pierwszych zakończonych cyframi 99, przykładowo 199, 499, 599, 1399, 1499, ...

Rozwiązanie

Wszystkie liczby naturalne zakończone cyframi [math]\displaystyle{ 99 }[/math] możemy zapisać w postaci [math]\displaystyle{ a_n = 100 k + 99 }[/math], gdzie [math]\displaystyle{ k \in \mathbb{N} }[/math]. Ponieważ ciąg [math]\displaystyle{ (a_n) }[/math] jest ciągiem arytmetycznym, a liczby [math]\displaystyle{ 99 }[/math] i [math]\displaystyle{ 100 }[/math] są względnie pierwsze, to na podstawie twierdzenia Dirichleta stwierdzamy, że istnieje nieskończenie wiele liczb pierwszych zakończonych cyframi [math]\displaystyle{ 99 }[/math].


Definicja C34
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 C35
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 C36
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
Rozwiązanie

Punkt 1.
W przypadku liczb naturalnych, łatwo widzimy, że kolejne liczby

[math]\displaystyle{ (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]\displaystyle{ m }[/math] zawsze możemy wskazać taką liczbę [math]\displaystyle{ n }[/math], że [math]\displaystyle{ p_{n + 1} - p_n \gt m }[/math].

Punkt 2.
W przypadku ciągu arytmetycznego [math]\displaystyle{ u_k = a k + b }[/math] rozważmy kolejne wyrazy ciągu począwszy od wskaźnika

[math]\displaystyle{ k_0 = \prod^{m - 1}_{j = 0} (a j + b) }[/math]

Łatwo zauważamy, że dla [math]\displaystyle{ k = k_0, k_0 + 1, \ldots, k_0 + (m - 1) }[/math] wyrazy ciągu arytmetycznego [math]\displaystyle{ u_k = a k + b }[/math] są liczbami złożonymi. Istotnie, niech [math]\displaystyle{ t = 0, 1, \ldots, m - 1 }[/math] wtedy

[math]\displaystyle{ u_k = a k + b = }[/math]
[math]\displaystyle{ \! = a (k_0 + t) + b = }[/math]
[math]\displaystyle{ \! = a k_0 + (a t + b) = }[/math]
[math]\displaystyle{ \! = a \prod^{m - 1}_{j = 0} (a j + b) + (a t + b) }[/math]

i liczba [math]\displaystyle{ a t + b }[/math] dzieli iloczyn [math]\displaystyle{ \prod^{m - 1}_{j = 0} (a j + b) }[/math] dla [math]\displaystyle{ t = 0, \ldots, m - 1 }[/math]. Co należało pokazać.

Wiemy, że jeżeli liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] są względnie pierwsze, to w ciągu [math]\displaystyle{ a k + b }[/math] występuje nieskończenie wiele liczb pierwszych. Niech będą to liczby [math]\displaystyle{ q_1, q_2, \ldots, q_r, \ldots }[/math]. Uzyskany rezultat oznacza, że dla dowolnej liczby naturalnej [math]\displaystyle{ m }[/math] zawsze możemy wskazać taką liczbę [math]\displaystyle{ n }[/math], że [math]\displaystyle{ q_{n + 1} - q_n \geqslant a (m + 1) }[/math]


Przykład C37
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 C38
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.

Dowód

Warunek [math]\displaystyle{ 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]\displaystyle{ k \in \mathbb{N} }[/math]. Wartość funkcji

[math]\displaystyle{ Q(k, n) = \pi (k + n) - \pi (k) }[/math]

jest równa ilości liczb pierwszych wśród [math]\displaystyle{ n }[/math] kolejnych liczb naturalnych od liczby [math]\displaystyle{ k + 1 }[/math] do liczby [math]\displaystyle{ k + n }[/math].

Uwzględniając, że wypisane niżej wyrażenia w nawiasach kwadratowych mogą przyjmować jedynie dwie wartości [math]\displaystyle{ 0 }[/math] lub [math]\displaystyle{ 1 }[/math], dostajemy

  • [math]\displaystyle{ \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]\displaystyle{ Q(0, n) = \pi (n) \qquad }[/math] bo [math]\displaystyle{ \pi (0) = 0 }[/math]
  • [math]\displaystyle{ Q((n + 1) ! + 1, n) = 0 \qquad }[/math] bo liczby [math]\displaystyle{ (n + 1) ! + 2, \ldots, (n + 1) ! + (n + 1) }[/math] są liczbami złożonymi

Ponieważ wartości funkcji [math]\displaystyle{ Q(k, n) }[/math] mogą zmieniać się tylko o [math]\displaystyle{ - 1 }[/math], [math]\displaystyle{ 0 }[/math] lub [math]\displaystyle{ 1 }[/math], to [math]\displaystyle{ Q(k, n) }[/math] musi przyjmować wszystkie wartości całkowite od [math]\displaystyle{ 0 }[/math] do [math]\displaystyle{ \pi (n) }[/math]. Wynika stąd, że istnieje taka liczba [math]\displaystyle{ k_r }[/math], że [math]\displaystyle{ Q(k_r, n) = r }[/math], gdzie [math]\displaystyle{ 0 \leqslant r \leqslant \pi (n) }[/math].


C Q10.png

Fragment wykresu funkcji [math]\displaystyle{ Q(k, 10) }[/math]. Widzimy, że dla [math]\displaystyle{ k = 113 }[/math] po raz pierwszy mamy [math]\displaystyle{ Q(k, 10) = 0 }[/math], a funkcja [math]\displaystyle{ Q(k, 10) }[/math] przyjmuje wszystkie wartości całkowite od [math]\displaystyle{ 0 }[/math] do [math]\displaystyle{ 5 }[/math].


Przykład C39
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 C40
Pokazać, nie korzystając z twierdzenia C38, że istnieje [math]\displaystyle{ 1000 }[/math] kolejnych liczb naturalnych, wśród których jest dokładnie jedna liczba pierwsza.

Rozwiązanie

Zauważmy, że [math]\displaystyle{ 1000 }[/math] kolejnych liczb naturalnych

[math]\displaystyle{ 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]\displaystyle{ 1000 }[/math] kolejnych liczb naturalnych, wśród których jest dokładnie jedna liczba pierwsza.

Uwaga: dopiero liczba [math]\displaystyle{ 1001! - 1733 }[/math] jest pierwsza.


Zadanie C41
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.

Rozwiązanie

Rozwiązywanie zadania rozpoczniemy od dwóch spostrzeżeń

  • wśród pierwszych [math]\displaystyle{ 20 }[/math] liczb naturalnych postaci [math]\displaystyle{ 6 k + 1 }[/math] jest [math]\displaystyle{ 13 }[/math] liczb pierwszych
  • w ciągu [math]\displaystyle{ 6 k + 1 }[/math] istnieją dowolnie długie przedziały pozbawione liczb pierwszych (zobacz zadanie C36), zatem istnieje [math]\displaystyle{ 20 }[/math] kolejnych liczb naturalnych postaci [math]\displaystyle{ 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]\displaystyle{ 20 }[/math] liczb naturalnych postaci [math]\displaystyle{ 6 k + 1 }[/math] wśród których jest, powiedzmy, [math]\displaystyle{ 15 }[/math] liczb pierwszych.

Drugie spostrzeżenie mówi nam, że ilość liczb pierwszych wśród kolejnych [math]\displaystyle{ 20 }[/math] liczb naturalnych postaci [math]\displaystyle{ 6 k + 1 }[/math] zmienia się od [math]\displaystyle{ 13 }[/math] do [math]\displaystyle{ 0 }[/math]. Analiza przebiegu tych zmian jest kluczem do dowodu twierdzenia.


Zbadajmy zatem, jak zmienia się ilość liczb pierwszych wśród kolejnych [math]\displaystyle{ 20 }[/math] liczb naturalnych postaci [math]\displaystyle{ 6 k + 1 }[/math]. Rozważmy ciąg [math]\displaystyle{ a_k = 6 k + 1 }[/math], gdzie [math]\displaystyle{ k = 0, 1, 2, \ldots }[/math]

[math]\displaystyle{ (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.


Niech [math]\displaystyle{ (B^n) }[/math] będzie fragmentem ciągu [math]\displaystyle{ (a_k) }[/math] rozpoczynającym się od [math]\displaystyle{ n }[/math]-tego wyrazu ciągu i złożonym z [math]\displaystyle{ 20 }[/math] kolejnych wyrazów ciągu [math]\displaystyle{ (a_k) }[/math]. Przykładowo mamy

[math]\displaystyle{ (B^1) = (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 ) }[/math]

[math]\displaystyle{ (B^2) = ( \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 ) }[/math]

[math]\displaystyle{ (B^3) = ( \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} ) }[/math]


Musimy zrozumieć, jak przejście od ciągu [math]\displaystyle{ (B^n) }[/math] do ciągu [math]\displaystyle{ (B^{n + 1}) }[/math] wpływa na ilość liczb pierwszych w tych ciągach.

  • jeżeli najmniejszy wyraz ciągu [math]\displaystyle{ (B^n) }[/math] jest liczbą złożoną, to po przejściu do ciągu [math]\displaystyle{ (B^{n + 1}) }[/math] ilość liczb pierwszych w tym ciągu w stosunku do ilości liczb pierwszych w ciągu [math]\displaystyle{ (B^n) }[/math] może
    • pozostać bez zmian (w przypadku, gdy największy wyraz ciągu [math]\displaystyle{ (B^{n + 1}) }[/math] jest liczbą złożoną)
    • zwiększyć się o jeden (w przypadku, gdy największy wyraz ciągu [math]\displaystyle{ (B^{n + 1}) }[/math] jest liczbą pierwszą)
  • jeżeli najmniejszy wyraz ciągu [math]\displaystyle{ (B^n) }[/math] jest liczbą pierwszą, to po przejściu do ciągu [math]\displaystyle{ (B^{n + 1}) }[/math] ilość liczb pierwszych w tym ciągu w stosunku do ilości liczb pierwszych w ciągu [math]\displaystyle{ (B^n) }[/math] może
    • zmniejszyć się o jeden (w przypadku, gdy największy wyraz ciągu [math]\displaystyle{ (B^{n + 1}) }[/math] jest liczbą złożoną)
    • pozostać bez zmian (w przypadku, gdy największy wyraz ciągu [math]\displaystyle{ (B^{n + 1}) }[/math] jest liczbą pierwszą)


Wynika stąd, że przechodząc od ciągu [math]\displaystyle{ (B^n) }[/math] do ciągu [math]\displaystyle{ (B^{n + 1}) }[/math] ilość liczb pierwszych może się zmienić o [math]\displaystyle{ - 1 }[/math], [math]\displaystyle{ 0 }[/math] lub [math]\displaystyle{ 1 }[/math]. Z drugiego ze spostrzeżeń uczynionych na początku dowodu wynika istnienie takiej liczby [math]\displaystyle{ r }[/math], że wśród ciągów

[math]\displaystyle{ (B^1), (B^2), \ldots, (B^r) }[/math]

ilość liczb pierwszych będzie przyjmowała wszystkie możliwe wartości od liczby [math]\displaystyle{ 13 }[/math] do liczby [math]\displaystyle{ 0 }[/math]. Co zapewnia istnienie takich [math]\displaystyle{ 20 }[/math] kolejnych liczb naturalnych postaci [math]\displaystyle{ 6 k + 1 }[/math], że wśród nich jest dokładnie [math]\displaystyle{ 5 }[/math] liczb pierwszych.


Twierdzenie C42
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.

Dowód

Twierdzenie można udowodnić uogólniając dowód twierdzenia C38 lub wykorzystując metodę zastosowaną w rozwiązaniu zadania C41.


Zadanie C43
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].

Rozwiązanie

Wiemy, że liczby pierwsze nieparzyste [math]\displaystyle{ p \geqslant 5 }[/math] mogą być postaci [math]\displaystyle{ 6 k + 1 }[/math] lub [math]\displaystyle{ 6 k + 5 }[/math]. Ponieważ

[math]\displaystyle{ (6 k + 1)^2 = 6 (6 k^2 + 2 k) + 1 }[/math]
[math]\displaystyle{ (6 k + 5)^2 = 6 (6 k^2 + 10 k + 4) + 1 }[/math]

zatem kwadraty liczb pierwszych są postaci [math]\displaystyle{ 6 k + 1 }[/math] i nie mogą występować w ciągu postaci [math]\displaystyle{ 6 k + 5 }[/math].


Zadanie C44
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]
Rozwiązanie

Punkt 1.
Zauważmy, że liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] są względnie pierwsze, zatem liczba pierwsza [math]\displaystyle{ p }[/math] nie może jednocześnie dzielić liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math]. Ponieważ z założenia [math]\displaystyle{ p \mid a }[/math], to wynika stąd, że [math]\displaystyle{ p }[/math] nie dzieli [math]\displaystyle{ b }[/math]. Jeśli tak, to

[math]\displaystyle{ a k + b = (n p) k + b }[/math]

i [math]\displaystyle{ p }[/math] nie dzieli żadnej liczby postaci [math]\displaystyle{ a k + b }[/math].

Punkt 2.
Pierwszy sposób

Niech [math]\displaystyle{ k_0 \in \mathbb{N} }[/math]. Przypuśćmy, że dla pewnych różnych liczb naturalnych [math]\displaystyle{ i, j }[/math] takich, że [math]\displaystyle{ 1 \leqslant i \lt j \leqslant p }[/math] liczby [math]\displaystyle{ a(k_0 + i) + b }[/math] oraz [math]\displaystyle{ a(k_0 + j) + b }[/math] dają tę samą resztę przy dzieleniu przez liczbę pierwszą [math]\displaystyle{ p }[/math]. Zatem różnica tych liczb jest podzielna przez [math]\displaystyle{ p }[/math]

[math]\displaystyle{ p \mid [a (k_0 + j) + b] - [a (k_0 + i) + b] }[/math]

czyli

[math]\displaystyle{ p \mid a (j - i) }[/math]

Ponieważ [math]\displaystyle{ p \nmid a }[/math] to na mocy lematu Euklidesa (twierdzenie C74), mamy

[math]\displaystyle{ p \mid (j - i) }[/math]

co jest niemożliwe, bo [math]\displaystyle{ 1 \leqslant j - i \leqslant p - 1 \lt p }[/math].

Zatem reszty [math]\displaystyle{ r_1, r_2, \ldots, r_p }[/math] są wszystkie różne, a ponieważ jest ich [math]\displaystyle{ p }[/math], czyli tyle ile jest różnych reszt z dzielenia przez liczbę [math]\displaystyle{ p }[/math], to zbiór tych reszt jest identyczny ze zbiorem reszt z dzielenia przez [math]\displaystyle{ p }[/math], czyli ze zbiorem [math]\displaystyle{ S = \{ 0, 1, 2, \ldots, p - 1 \} }[/math]. W szczególności wynika stąd, że wśród [math]\displaystyle{ p }[/math] kolejnych wyrazów ciągu arytmetycznego [math]\displaystyle{ a k + b }[/math] jeden z tych wyrazów jest podzielny przez [math]\displaystyle{ p }[/math]. Zatem istnieje nieskończenie wiele wyrazów ciągu [math]\displaystyle{ a k + b }[/math], które są podzielne przez [math]\displaystyle{ p }[/math].


Drugi sposób

Problem sprowadza się do wykazania istnienia nieskończenie wielu par liczb naturalnych [math]\displaystyle{ (k, n) }[/math], takich że

[math]\displaystyle{ a k + b = n p }[/math]

Co z kolei sprowadza się do badania rozwiązań całkowitych równania

[math]\displaystyle{ n p - a k = b }[/math]

Zauważmy, że ponieważ [math]\displaystyle{ p \nmid a }[/math], to liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ p }[/math] są względnie pierwsze. Zatem ich największym wspólnym dzielnikiem jest liczba [math]\displaystyle{ 1 }[/math]. Na mocy twierdzenia C78 równanie to ma nieskończenie wiele rozwiązań w liczbach całkowitych

[math]\displaystyle{ n = n_0 + p t }[/math]
[math]\displaystyle{ k = k_0 + a t }[/math]

gdzie [math]\displaystyle{ t }[/math] jest dowolną liczbą całkowitą, a para liczb [math]\displaystyle{ (n_0, k_0) }[/math] jest dowolnym rozwiązaniem tego równania. Widzimy, że dla dostatecznie dużych liczb [math]\displaystyle{ t }[/math] zawsze możemy uzyskać takie [math]\displaystyle{ n }[/math] i [math]\displaystyle{ k }[/math], że [math]\displaystyle{ n, k \in \mathbb{Z}_+ }[/math]. Pokazaliśmy w ten sposób, że w ciągu arytmetycznym [math]\displaystyle{ a k + b }[/math] istnieje nieskończenie wiele wyrazów podzielnych przez liczbę pierwszą [math]\displaystyle{ p }[/math].


Trzeci sposób

Zauważmy, że ponieważ [math]\displaystyle{ p \nmid a }[/math], to liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ p }[/math] są względnie pierwsze. Zatem ich największym wspólnym dzielnikiem jest liczba [math]\displaystyle{ 1 }[/math]. Lemat Bézouta zapewnia istnienie takich liczb całkowitych [math]\displaystyle{ x }[/math] i [math]\displaystyle{ y }[/math], że

[math]\displaystyle{ a x + p y = 1 }[/math]

Niech [math]\displaystyle{ k_0 = r p - b x }[/math], gdzie [math]\displaystyle{ r }[/math] jest dowolną liczbą całkowitą dodatnią, ale na tyle dużą, aby [math]\displaystyle{ k_0 }[/math] była liczbą dodatnią bez względu na znak iloczynu [math]\displaystyle{ b x }[/math]. Łatwo sprawdzamy, że liczba [math]\displaystyle{ a k_0 + b }[/math] jest podzielna przez [math]\displaystyle{ p }[/math]

[math]\displaystyle{ a k_0 + b = a (r p - b x) + b = }[/math]
[math]\displaystyle{ \;\; = a r p - a b x + b = }[/math]
[math]\displaystyle{ \;\; = a r p + b (1 - a x) = }[/math]
[math]\displaystyle{ \;\; = a r p + b p y = }[/math]
[math]\displaystyle{ \;\; = p (a r + b y) }[/math]

Zatem w ciągu [math]\displaystyle{ a k + b }[/math] istnieje przynajmniej jeden wyraz podzielny przez liczbę pierwszą [math]\displaystyle{ p }[/math]. Jeśli tak, to w ciągu arytmetycznym [math]\displaystyle{ a k + b }[/math] istnieje nieskończenie wiele liczb podzielnych przez [math]\displaystyle{ p }[/math], bo dla [math]\displaystyle{ k = k_0 + s p }[/math], gdzie [math]\displaystyle{ s \in \mathbb{N} }[/math], mamy

[math]\displaystyle{ a k + b = a (k_0 + s p) + b = a s p + (a k_0 + b) }[/math]

Czyli [math]\displaystyle{ p \mid a k + b }[/math].


Uwaga C45
Ł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 C46
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

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 C47
Ł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 C48
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].

Dowód

Gdyby liczba [math]\displaystyle{ a }[/math] była nieparzysta, to liczba [math]\displaystyle{ a^n + 1 \geqslant 4 }[/math] byłaby parzysta i nie mogłaby być liczbą pierwszą.

Niech wykładnik [math]\displaystyle{ n = x y }[/math] będzie liczbą złożoną, a [math]\displaystyle{ x }[/math] będzie liczbą nieparzystą. Wtedy

[math]\displaystyle{ a^n + 1 = (a^y)^x + 1 }[/math]

Oznaczając [math]\displaystyle{ b = a^y }[/math] oraz [math]\displaystyle{ x = 2 k + 1 }[/math], otrzymujemy

[math]\displaystyle{ a^n + 1 = (a^y)^x + 1 }[/math]
[math]\displaystyle{ \: = b^x + 1 }[/math]
[math]\displaystyle{ \: = b^{2 k + 1} + 1 }[/math]
[math]\displaystyle{ \: = (b + 1) \cdot (1 - b + b^2 - b^3 + \ldots + b^{2 k - 2} - b^{2 k - 1} + b^{2 k}) }[/math]

Czyli [math]\displaystyle{ a^n + 1 }[/math] jest liczbą złożoną. Wynika stąd, że wykładnik [math]\displaystyle{ n }[/math] nie może zawierać czynników nieparzystych, czyli musi być [math]\displaystyle{ n = 2^m }[/math]. Co należało pokazać.


Twierdzenie C49
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].

Dowód

Indukcja matematyczna. Twierdzenie jest prawdziwe dla [math]\displaystyle{ n = 1 }[/math], bo [math]\displaystyle{ x - y }[/math] dzieli [math]\displaystyle{ x^1 - y^1 }[/math]. Załóżmy, że [math]\displaystyle{ x - y }[/math] jest dzielnikiem wyrażenia [math]\displaystyle{ x^n - y^n }[/math], czyli [math]\displaystyle{ x^n - y^n = (x - y) \cdot k }[/math], otrzymujemy dla [math]\displaystyle{ n + 1 }[/math]

[math]\displaystyle{ x^{n + 1} - y^{n + 1} = x x^n - y x^n + y x^n - y y^n = }[/math]
[math]\displaystyle{ \quad \, = (x - y) x^n + y (x^n - y^n) = }[/math]
[math]\displaystyle{ \quad \, = (x - y) x^n + y (x - y) \cdot k = }[/math]
[math]\displaystyle{ \quad \, = (x - y) (x^n + y \cdot k) }[/math]

Czyli [math]\displaystyle{ x - y }[/math] jest dzielnikiem [math]\displaystyle{ x^{n + 1} - y^{n + 1} }[/math]. Co kończy dowód indukcyjny.


Twierdzenie C50
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ą.

Dowód

Z twierdzenia C49 wiemy, że [math]\displaystyle{ x - y \mid x^n - y^n }[/math]. W przypadku gdy [math]\displaystyle{ a \gt 2 }[/math] mamy

[math]\displaystyle{ a - 1 \mid a^n - 1 }[/math]

Czyli musi być [math]\displaystyle{ a = 2 }[/math]. Z tego samego twierdzenia wynika też, że jeżeli [math]\displaystyle{ n }[/math] jest liczbą złożoną [math]\displaystyle{ n = r s }[/math], to

[math]\displaystyle{ 2^r - 1 \mid 2^{r s} - 1 }[/math]

bo [math]\displaystyle{ a^r - b^r \mid (a^r)^s - (b^r)^s }[/math]. Zatem [math]\displaystyle{ n }[/math] musi być liczbą pierwszą. Co kończy dowód.




Ciągi arytmetyczne liczb pierwszych

Uwaga C51
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 C52* (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 C53
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości [math]\displaystyle{ n = 3 }[/math] i [math]\displaystyle{ n = 4 }[/math].

Pokaż tabele

W przypadku [math]\displaystyle{ n = 3 }[/math] wyszukiwanie ciągów zostało przeprowadzone dla [math]\displaystyle{ d = 2 k }[/math], gdzie [math]\displaystyle{ 1 \leqslant k \leqslant 100 }[/math] i (przy ustalonym [math]\displaystyle{ d }[/math]) dla kolejnych liczb pierwszych [math]\displaystyle{ p_0 \leqslant 10^8 }[/math].

W przypadku [math]\displaystyle{ n = 4 }[/math] wyszukiwanie ciągów zostało przeprowadzone dla [math]\displaystyle{ d = 6 k }[/math], gdzie [math]\displaystyle{ 1 \leqslant k \leqslant 100 }[/math] i (przy ustalonym [math]\displaystyle{ d }[/math]) dla kolejnych liczb pierwszych [math]\displaystyle{ p_0 \leqslant 10^8 }[/math].

Jeżeli w tabeli jest wypisanych sześć wartości [math]\displaystyle{ p_0 }[/math], to oznacza to, że zostało znalezionych co najmniej sześć wartości [math]\displaystyle{ p_0 }[/math].



Przykład C54
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości [math]\displaystyle{ n = 5 }[/math] i [math]\displaystyle{ n = 6 }[/math].

Pokaż tabele

W przypadku [math]\displaystyle{ n = 5 }[/math] wyszukiwanie ciągów zostało przeprowadzone dla [math]\displaystyle{ d = 6 k }[/math], gdzie [math]\displaystyle{ 1 \leqslant k \leqslant 100 }[/math] i (przy ustalonym [math]\displaystyle{ d }[/math]) dla kolejnych liczb pierwszych [math]\displaystyle{ p_0 \leqslant 10^8 }[/math].

W przypadku [math]\displaystyle{ n = 6 }[/math] wyszukiwanie ciągów zostało przeprowadzone dla [math]\displaystyle{ d = 30 k }[/math], gdzie [math]\displaystyle{ 1 \leqslant k \leqslant 100 }[/math] i (przy ustalonym [math]\displaystyle{ d }[/math]) dla kolejnych liczb pierwszych [math]\displaystyle{ p_0 \leqslant 10^8 }[/math].

Jeżeli w tabeli jest wypisanych sześć wartości [math]\displaystyle{ p_0 }[/math], to oznacza to, że zostało znalezionych co najmniej sześć wartości [math]\displaystyle{ p_0 }[/math].



Przykład C55
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości [math]\displaystyle{ n = 7 }[/math] i [math]\displaystyle{ n = 8 }[/math].

Pokaż tabele

W przypadku [math]\displaystyle{ n = 7 }[/math] wyszukiwanie ciągów zostało przeprowadzone dla [math]\displaystyle{ d = 30 k }[/math], gdzie [math]\displaystyle{ 1 \leqslant k \leqslant 100 }[/math] i (przy ustalonym [math]\displaystyle{ d }[/math]) dla kolejnych liczb pierwszych [math]\displaystyle{ p_0 \leqslant 10^8 }[/math].

W przypadku [math]\displaystyle{ n = 8 }[/math] wyszukiwanie ciągów zostało przeprowadzone dla [math]\displaystyle{ d = 210 k }[/math], gdzie [math]\displaystyle{ 1 \leqslant k \leqslant 100 }[/math] i (przy ustalonym [math]\displaystyle{ d }[/math]) dla kolejnych liczb pierwszych [math]\displaystyle{ p_0 \leqslant 10^8 }[/math].

Jeżeli w tabeli jest wypisanych sześć wartości [math]\displaystyle{ p_0 }[/math], to oznacza to, że zostało znalezionych co najmniej sześć wartości [math]\displaystyle{ p_0 }[/math].



Przykład C56
Tabela zawiera przykładowe ciągi arytmetyczne liczb pierwszych o długości [math]\displaystyle{ n = 9 }[/math] i [math]\displaystyle{ n = 10 }[/math].

Pokaż tabele

W przypadku [math]\displaystyle{ n = 9 }[/math] wyszukiwanie ciągów zostało przeprowadzone dla [math]\displaystyle{ d = 210 k }[/math], gdzie [math]\displaystyle{ 1 \leqslant k \leqslant 100 }[/math] i (przy ustalonym [math]\displaystyle{ d }[/math]) dla kolejnych liczb pierwszych [math]\displaystyle{ p_0 \leqslant 10^9 }[/math].

W przypadku [math]\displaystyle{ n = 10 }[/math] wyszukiwanie ciągów zostało przeprowadzone dla [math]\displaystyle{ d = 210 k }[/math], gdzie [math]\displaystyle{ 1 \leqslant k \leqslant 100 }[/math] i (przy ustalonym [math]\displaystyle{ d }[/math]) dla kolejnych liczb pierwszych [math]\displaystyle{ p_0 \leqslant 10^{10} }[/math].

Jeżeli w tabeli jest wypisanych sześć wartości [math]\displaystyle{ p_0 }[/math], to oznacza to, że zostało znalezionych co najmniej sześć wartości [math]\displaystyle{ p_0 }[/math].



Twierdzenie C57
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].

Dowód

Przypuśćmy, że dla pewnych różnych liczb naturalnych [math]\displaystyle{ i, j }[/math] takich, że [math]\displaystyle{ 1 \leqslant i \lt j \leqslant n }[/math] liczby [math]\displaystyle{ a + (k_0 + i) d }[/math] oraz [math]\displaystyle{ a + (k_0 + j) d }[/math] dają tę samą resztę przy dzieleniu przez [math]\displaystyle{ n }[/math]. Zatem różnica tych liczb jest podzielna przez [math]\displaystyle{ n }[/math]

[math]\displaystyle{ n \mid [a + (k_0 + j) d] - [a + (k_0 + i) d] }[/math]

Czyli

[math]\displaystyle{ n \mid d (j - i) }[/math]

Ponieważ liczby [math]\displaystyle{ d }[/math] i [math]\displaystyle{ n }[/math] są względnie pierwsze, to na mocy lematu Euklidesa (twierdzenie C74), mamy

[math]\displaystyle{ n \mid (j - i) }[/math]

Co jest niemożliwe, bo [math]\displaystyle{ 1 \leqslant j - i \leqslant n - 1 \lt n }[/math].

Zatem reszty [math]\displaystyle{ r_1, r_2, \ldots, r_n }[/math] są wszystkie różne, a ponieważ jest ich [math]\displaystyle{ n }[/math], czyli tyle ile jest różnych reszt z dzielenia przez liczbę [math]\displaystyle{ n }[/math], to zbiór tych reszt jest identyczny ze zbiorem reszt z dzielenia przez [math]\displaystyle{ n }[/math], czyli ze zbiorem [math]\displaystyle{ S = \{ 0, 1, 2, \ldots, n - 1 \} }[/math].


Twierdzenie C58
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].

Dowód

Punkt 1.
Gdyby [math]\displaystyle{ p_0 \mid d }[/math], to dla [math]\displaystyle{ k \geqslant 1 }[/math] mielibyśmy [math]\displaystyle{ p_k = p_0 \left( 1 + k \cdot \frac{d}{p_0} \right) }[/math] i wszystkie te liczby byłyby złożone.

Punkt 2.
Ponieważ [math]\displaystyle{ p_0 }[/math] dzieli [math]\displaystyle{ p_0 + p_0 d }[/math], więc musi być [math]\displaystyle{ n - 1 \lt p_0 }[/math], czyli [math]\displaystyle{ n \leqslant p_0 }[/math].

Punkt 3.
Niech [math]\displaystyle{ q }[/math] będzie liczbą pierwszą mniejszą od [math]\displaystyle{ n }[/math], a liczby [math]\displaystyle{ r_k }[/math] będą resztami uzyskanymi z dzielenia liczb [math]\displaystyle{ p_k = p_0 + k d }[/math] przez [math]\displaystyle{ q }[/math], dla [math]\displaystyle{ k = 0, 1, \ldots, q - 1 }[/math]. Ponieważ z założenia liczby [math]\displaystyle{ p_0, \ldots, p_{n - 1} }[/math] są liczbami pierwszymi większymi od [math]\displaystyle{ q }[/math] (zauważmy, że [math]\displaystyle{ p_0 \geqslant n }[/math]), to żadna z reszt [math]\displaystyle{ r_k }[/math] nie może być równa zeru. Czyli mamy [math]\displaystyle{ q }[/math] reszt mogących przyjmować jedynie [math]\displaystyle{ q - 1 }[/math] różnych wartości. Zatem istnieją różne liczby [math]\displaystyle{ i, j }[/math], takie że [math]\displaystyle{ 0 \leqslant i \lt j \leqslant q - 1 }[/math], dla których [math]\displaystyle{ r_i = r_j }[/math]. Wynika stąd, że różnica liczb

[math]\displaystyle{ p_j - p_i = (p_0 + j d) - (p_0 + i d) = d (j - i) }[/math]

musi być podzielna przez [math]\displaystyle{ q }[/math]. Ponieważ [math]\displaystyle{ q \nmid (j - i) }[/math], bo [math]\displaystyle{ 1 \leqslant j - i \leqslant q - 1 \lt q }[/math], zatem z lematu Euklidesa [math]\displaystyle{ q \mid d }[/math].

Z uwagi na fakt, że jest tak dla każdej liczby pierwszej [math]\displaystyle{ q \lt n }[/math], liczba [math]\displaystyle{ d }[/math] musi być podzielna przez

[math]\displaystyle{ P(n - 1) = \prod_{q \lt n} q }[/math]

Punkt 4.
Ponieważ [math]\displaystyle{ P(n - 1)|d }[/math], to wszystkie liczby pierwsze mniejsze od [math]\displaystyle{ n }[/math] muszą być dzielnikami [math]\displaystyle{ d }[/math]. Wynika stąd, że jeśli liczba pierwsza [math]\displaystyle{ q }[/math] nie dzieli [math]\displaystyle{ d }[/math], to musi być [math]\displaystyle{ q \geqslant n }[/math]. Co należało pokazać.


Uwaga C59
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 C60
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 C58, 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 C61
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 C58 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 C62
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.

Rozwiązanie

Ponieważ [math]\displaystyle{ p_0 = 3 }[/math], a rozpatrywany PAP jest rosnący, to kolejne wyrazy ciągu są większe od liczby [math]\displaystyle{ 3 }[/math] i mogą być przedstawione w jednej z postaci [math]\displaystyle{ 6 k - 1 }[/math] lub [math]\displaystyle{ 6 k + 1 }[/math]. Z twierdzenia C58 wiemy, że musi być [math]\displaystyle{ n \leqslant p_0 = 3 }[/math], czyli długość rozpatrywanego ciągu arytmetycznego liczb pierwszych wynosi dokładnie [math]\displaystyle{ 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]\displaystyle{ p, q, r }[/math] takich, że [math]\displaystyle{ p = 3 }[/math]. Mamy

[math]\displaystyle{ r = q + d = q + (q - p) = 2 q - p }[/math]

Zatem

[math]\displaystyle{ r + q = 3 q - 3 }[/math]

Widzimy, że prawa strona powyższej równości jest podzielna przez [math]\displaystyle{ 3 }[/math]. Zatem liczby po lewej stronie wypisanych wyżej równości muszą być różnych postaci, bo tylko w takim przypadku lewa strona równości będzie również podzielna przez [math]\displaystyle{ 3 }[/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 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.

Rozwiązanie

Niech liczby [math]\displaystyle{ p, q, r }[/math] będą trzema kolejnymi (dowolnie wybranymi) wyrazami rozpatrywanego ciągu. Łatwo zauważmy, że

[math]\displaystyle{ r = q + d = q + (q - p) = 2 q - p }[/math]

Zatem

[math]\displaystyle{ p + q = 3 q - r }[/math]
[math]\displaystyle{ q + r = 3 q - p }[/math]
[math]\displaystyle{ p + r = 2 q }[/math]

Zauważmy, że prawa strona wypisanych wyżej równości nie jest podzielna przez [math]\displaystyle{ 3 }[/math], bo liczby [math]\displaystyle{ p, q, r }[/math] są liczbami pierwszymi większymi od liczby [math]\displaystyle{ 3 }[/math]. Zatem liczby po lewej stronie wypisanych wyżej równości muszą być tej samej postaci, bo gdyby było inaczej, to lewa strona tych równości byłaby podzielna przez [math]\displaystyle{ 3 }[/math], a prawa nie. Czyli każda para liczb z trójki [math]\displaystyle{ p, q, r }[/math] musi być tej samej postaci i wynika stąd, że wszystkie trzy liczby muszą być tej samej postaci. Ponieważ trzy kolejne wyrazy ciągu [math]\displaystyle{ p_0, p_1, \ldots, p_{n - 1} }[/math] były wybrane dowolnie, to wszystkie wyrazy tego ciągu muszą być tej samej postaci.


Zadanie C64
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 C58, że jeżeli liczba pierwsza [math]\displaystyle{ q }[/math] nie dzieli [math]\displaystyle{ d }[/math], to [math]\displaystyle{ n \leqslant q }[/math].

Rozwiązanie

Przypuśćmy, że [math]\displaystyle{ n \gt q }[/math] tak, że [math]\displaystyle{ q \lt n \leqslant p_0 }[/math], zatem

[math]\displaystyle{ q \lt p_k = p_0 + k d \qquad }[/math] dla [math]\displaystyle{ \; k = 0, 1, \ldots, n - 1 }[/math]

Ponieważ [math]\displaystyle{ q \nmid d }[/math], to na mocy twierdzenia C57 wśród [math]\displaystyle{ q }[/math] kolejnych wyrazów [math]\displaystyle{ p_0, p_1, \ldots, p_{q - 1} }[/math] (zauważmy, że [math]\displaystyle{ q - 1 \lt n - 1 }[/math]) jedna liczba pierwsza [math]\displaystyle{ p_k }[/math] musi być podzielna przez [math]\displaystyle{ q }[/math], zatem musi być równa [math]\displaystyle{ q }[/math]. Jednak jest to niemożliwe, bo [math]\displaystyle{ q \lt p_k }[/math] dla wszystkich [math]\displaystyle{ k = 0, 1, \ldots, n - 1 }[/math]. Zatem nie może być [math]\displaystyle{ n \gt q }[/math].


Twierdzenie C65
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].

Dowód

[math]\displaystyle{ \Longrightarrow }[/math]
Jeżeli [math]\displaystyle{ p_0 = q }[/math], to [math]\displaystyle{ q }[/math]-wyrazowy ciąg arytmetyczny liczb pierwszych ma postać

[math]\displaystyle{ p_k = q + k d \qquad }[/math] dla [math]\displaystyle{ \; k = 0, 1, \ldots, q - 1 }[/math]

Gdyby [math]\displaystyle{ q \mid d }[/math], to mielibyśmy

[math]\displaystyle{ p_k = q \left( 1 + k \cdot \frac{d}{q} \right) }[/math]

i wszystkie liczby [math]\displaystyle{ p_k }[/math] dla [math]\displaystyle{ k \geqslant 1 }[/math] byłyby złożone, wbrew założeniu, że [math]\displaystyle{ p_k }[/math] tworzą [math]\displaystyle{ q }[/math]-wyrazowy ciąg arytmetyczny liczb pierwszych.

[math]\displaystyle{ \Longleftarrow }[/math]
Ponieważ [math]\displaystyle{ q }[/math] jest długością rozpatrywanego ciągu arytmetycznego liczb pierwszych, to z twierdzenia C58 wynika, że musi być [math]\displaystyle{ q \leqslant p_0 }[/math].

Z założenia liczba pierwsza [math]\displaystyle{ q }[/math] nie dzieli [math]\displaystyle{ d }[/math], zatem z twierdzenia C57 wiemy, że [math]\displaystyle{ q }[/math] musi dzielić jedną z liczb [math]\displaystyle{ p_0, p_1, \ldots, p_{q - 1} }[/math].

Jeżeli [math]\displaystyle{ q \mid p_k }[/math], to [math]\displaystyle{ p_k = q }[/math]. Ponieważ [math]\displaystyle{ q \leqslant p_0 }[/math], to możliwe jest jedynie [math]\displaystyle{ q \mid p_0 }[/math] i musi być [math]\displaystyle{ p_0 = q }[/math].


Uwaga C66
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ń C58 i C65 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 C67
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 C68
Znaleźć wszystkie PAP[math]\displaystyle{ (n, d, p) }[/math] dla [math]\displaystyle{ d = 2, 4, 8, 10, 14, 16 }[/math].

Rozwiązanie

Zauważmy, że dla każdej z podanych różnic [math]\displaystyle{ d }[/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].

Ponieważ [math]\displaystyle{ n = 3 }[/math] jest liczbą pierwszą i dla wypisanych [math]\displaystyle{ d }[/math] liczba [math]\displaystyle{ n \nmid d }[/math], to w każdym przypadku może istnieć tylko jeden ciąg, którego pierwszym wyrazem jest liczba pierwsza [math]\displaystyle{ p_0 = n = 3 }[/math]. Dla [math]\displaystyle{ d = 2, 4, 8, 10, 14 }[/math] łatwo znajdujemy odpowiednie ciągi

[math]\displaystyle{ (3, 5, 7) }[/math], [math]\displaystyle{ \qquad (3, 7, 11) }[/math], [math]\displaystyle{ \qquad (3, 11, 19) }[/math], [math]\displaystyle{ \qquad (3, 13, 23) }[/math], [math]\displaystyle{ \qquad (3, 17, 31) }[/math]

Dla [math]\displaystyle{ d = 16 }[/math] szukany ciąg nie istnieje, bo [math]\displaystyle{ 35 = 5 \cdot 7 }[/math].


Zadanie C69
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].

Rozwiązanie

Z założenia PAP ma długość [math]\displaystyle{ n }[/math], liczba [math]\displaystyle{ n }[/math] jest liczbą pierwszą i [math]\displaystyle{ n \nmid d }[/math]. Zatem może istnieć tylko jeden PAP taki, że [math]\displaystyle{ p_0 = n }[/math]. Dla [math]\displaystyle{ n = 3, 5 }[/math] i odpowiednio [math]\displaystyle{ d = 2, 6 }[/math] otrzymujemy ciągi arytmetyczne liczb pierwszych

[math]\displaystyle{ (3, 5, 7) }[/math], [math]\displaystyle{ \qquad (5, 11, 17, 23, 29) }[/math]

Ale dla [math]\displaystyle{ n = 7, 11 }[/math] i odpowiednio [math]\displaystyle{ d = 30, 210 }[/math] szukane ciągi nie istnieją, bo

[math]\displaystyle{ (7, 37, 67, 97, 127, 157, {\color{Red} 187 = 11 \cdot 17}) }[/math]
[math]\displaystyle{ (11, {\color{Red} 221 = 13 \cdot 17}, 431, 641, {\color{Red} 851 = 23 \cdot 37}, 1061, {\color{Red} 1271 = 31 \cdot 41}, 1481, {\color{Red} 1691 = 19 \cdot 89}, 1901, 2111) }[/math]


Przykład C70
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].

Pokaż tabelę


Przykłady takich ciągów dla jeszcze większych liczb pierwszych Czytelnik znajdzie na stronie A088430.


Przykład C71
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]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].

Pokaż tabele



Zadanie C72
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].

Rozwiązanie

Zauważmy, że ilość liczb pierwszych nie większych od [math]\displaystyle{ x }[/math] w dobrym przybliżeniu jest określona funkcją [math]\displaystyle{ \frac{x}{\log x} }[/math]. Ponieważ funkcja [math]\displaystyle{ \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]\displaystyle{ x }[/math], ilość liczb pierwszych w przedziale [math]\displaystyle{ (x, 2 x) }[/math] jest tego samego rzędu, co ilość liczb pierwszych w przedziale [math]\displaystyle{ (1, x) }[/math][17].


Zatem liczbę [math]\displaystyle{ \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]\displaystyle{ x }[/math]. Zakładając, że liczby pierwsze są rozłożone przypadkowo, możemy wyliczyć prawdopodobieństwo tego, że [math]\displaystyle{ n }[/math] kolejnych liczb pierwszych, położonych w pobliżu liczby [math]\displaystyle{ x }[/math], utworzy ciąg arytmetyczny

[math]\displaystyle{ \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]

gdzie [math]\displaystyle{ d = P (n) }[/math]. Jest tak, ponieważ w ciągu kolejnych liczb całkowitych musimy trafić na liczbę pierwszą, następnie na [math]\displaystyle{ d - 1 }[/math] liczb złożonych, taka sytuacja musi się powtórzyć dokładnie [math]\displaystyle{ n - 1 }[/math] razy, a na koniec znowu musimy trafić na liczbę pierwszą. Czyli potrzebujemy [math]\displaystyle{ n }[/math] liczb pierwszych, na które trafiamy z prawdopodobieństwem [math]\displaystyle{ \frac{1}{\log x} }[/math] oraz [math]\displaystyle{ (n - 1) (d - 1) }[/math] liczb złożonych, na które trafiamy z prawdopodobieństwem [math]\displaystyle{ 1 - \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]\displaystyle{ n }[/math] kolejnych liczb pierwszych należących do przedziału [math]\displaystyle{ (x, 2 x) }[/math] możemy zatem oszacować na równą około

[math]\displaystyle{ 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]


Porównując powyższe oszacowanie z rzeczywistą ilością [math]\displaystyle{ \# \text{CPAP}(n, x) }[/math] ciągów arytmetycznych kolejnych liczb pierwszych w przedziale [math]\displaystyle{ (x, 2x) }[/math] dostajemy

[math]\displaystyle{ \frac{\# \text{CPAP}(n, x)}{Q_{\text{cpap}} (n, x)} = f (n, x) }[/math]

gdzie w możliwym do zbadania zakresie, czyli dla [math]\displaystyle{ x \lt 2^{42} \approx 4.4 \cdot 10^{12} }[/math] mamy

[math]\displaystyle{ f(n, x) \approx a_n \cdot \log x + b_n }[/math]

Stałe [math]\displaystyle{ a_n }[/math] i [math]\displaystyle{ b_n }[/math] wyznaczamy metodą regresji liniowej. Musimy pamiętać, że uzyskanych w ten sposób wyników nie możemy ekstrapolować dla dowolnie dużych [math]\displaystyle{ x }[/math].

W przypadku [math]\displaystyle{ n = 5 }[/math] oraz [math]\displaystyle{ n = 6 }[/math] dysponowaliśmy zbyt małą liczbą danych, aby wyznaczyć stałe [math]\displaystyle{ a_n }[/math] i [math]\displaystyle{ b_n }[/math] z wystarczającą dokładnością. Dlatego w tych przypadkach ograniczyliśmy się do podania oszacowania funkcji [math]\displaystyle{ f(n, x) }[/math].

Uzyskany wyżej rezultaty są istotne, bo z wyliczonych postaci funkcji [math]\displaystyle{ f(n, x) }[/math] wynika, że są to funkcje bardzo wolno zmienne, a ich ekstrapolacja jest w pełni uprawniona.


W zamieszczonej niżej tabeli mamy kolejno

  • [math]\displaystyle{ n }[/math], czyli długość CPAP
  • wartość iloczynu [math]\displaystyle{ n \cdot P (n) }[/math]
  • znalezioną postać funkcji [math]\displaystyle{ f(n, x) }[/math] lub oszacowanie wartości tej funkcji [math]\displaystyle{ C_n }[/math] na podstawie uzyskanych danych; w przypadku [math]\displaystyle{ n = 7 }[/math] jest to oszacowanie wynikające z obserwacji, że wartości funkcji [math]\displaystyle{ f(n, x) }[/math] są rzędu [math]\displaystyle{ n \cdot P (n) }[/math]
  • wyliczoną wartość [math]\displaystyle{ \frac{\# \text{CPAP}(n, 2^{40})}{Q_{\text{cpap}}(n, 2^{40})} }[/math], czyli [math]\displaystyle{ f(n, 2^{40}) }[/math]
  • wartość funkcji [math]\displaystyle{ f(n, 2^{70}) }[/math] wynikające z ekstrapolacji wzoru [math]\displaystyle{ f(n, x) = a_n \cdot \log x + b_n \qquad }[/math] (dla [math]\displaystyle{ n = 3, 4 }[/math])
  • wartość [math]\displaystyle{ x }[/math] wynikającą z rozwiązania równania
[math]\displaystyle{ \qquad (a_n \cdot \log x + b_n) \cdot Q_{\text{cpap}} (n, x) = 1 \qquad }[/math] (dla [math]\displaystyle{ n = 3, 4 }[/math])
[math]\displaystyle{ \qquad C_n \cdot Q_{\text{cpap}} (n, x) = 1 \qquad }[/math] (dla [math]\displaystyle{ n = 5, 6, 7 }[/math])
  • dla porównania w kolejnych kolumnach zostały podane dwie najmniejsze wartości [math]\displaystyle{ p_0 }[/math] dla CPAP-n

Zauważając, że funkcje [math]\displaystyle{ f(n, x) }[/math] są rzędu [math]\displaystyle{ n \cdot P (n) }[/math] i przyjmując, że podobnie będzie dla [math]\displaystyle{ f(7, x) }[/math], możemy wyliczyć wartość [math]\displaystyle{ x }[/math], dla której może pojawić się pierwszy CPAP-7. Wartość ta jest równa w przybliżeniu [math]\displaystyle{ 2 \cdot 10^{20} }[/math] i wynika z rozwiązania równania

[math]\displaystyle{ f(7, x) \cdot Q_{\text{cpap}}(7, x) = 1 }[/math]

Możemy ją łatwo wyliczyć w PARI/GP. Oczywiście funkcję [math]\displaystyle{ f(7, x) }[/math] zastąpiliśmy jej oszacowaniem [math]\displaystyle{ C_7 = 2500 }[/math]

P(n) = prod(k = 2, n, if( isprime(k), k, 1 ))
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 )



Uzupełnienie

Twierdzenie C73 (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]
Dowód

Niech [math]\displaystyle{ S }[/math] będzie zbiorem wszystkich liczb całkowitych dodatnich postaci [math]\displaystyle{ a n + b m }[/math], gdzie [math]\displaystyle{ n, m }[/math] są dowolnymi liczbami całkowitymi. Zbiór [math]\displaystyle{ S }[/math] nie jest zbiorem pustym, bo przykładowo liczba [math]\displaystyle{ a^2 + b^2 \in S }[/math]. Z zasady dobrego uporządkowania liczb naturalnych wynika, że zbiór [math]\displaystyle{ S }[/math] ma element najmniejszy, oznaczmy go literą [math]\displaystyle{ d }[/math].

Pokażemy, że [math]\displaystyle{ d \mid a }[/math] i [math]\displaystyle{ d \mid b }[/math]. Z twierdzenia o dzieleniu z resztą możemy napisać [math]\displaystyle{ a = k d + r }[/math], gdzie [math]\displaystyle{ 0 \leqslant r \lt d }[/math].

Przypuśćmy, że [math]\displaystyle{ d \nmid a }[/math], czyli że [math]\displaystyle{ r \gt 0 }[/math]. Ponieważ [math]\displaystyle{ d \in S }[/math], to mamy [math]\displaystyle{ d = a u + b v }[/math] dla pewnych liczb całkowitych [math]\displaystyle{ u }[/math] i [math]\displaystyle{ v }[/math]. Zatem

[math]\displaystyle{ r = a - k d = }[/math]
[math]\displaystyle{ \;\;\, = a - k (a u + b v) = }[/math]
[math]\displaystyle{ \;\;\, = a \cdot (1 - k u) + b \cdot (- k v) }[/math]

Wynika stąd, że dodatnia liczba [math]\displaystyle{ r }[/math] należy do zbioru [math]\displaystyle{ S }[/math] oraz [math]\displaystyle{ r \lt d }[/math], wbrew określeniu liczby [math]\displaystyle{ d }[/math], czyli musi być [math]\displaystyle{ r = 0 }[/math] i [math]\displaystyle{ d \mid a }[/math]. Podobnie pokazujemy, że [math]\displaystyle{ d \mid b }[/math].

Jeżeli [math]\displaystyle{ d' }[/math] jest innym dzielnikiem liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math], to [math]\displaystyle{ d' \mid d }[/math], bo [math]\displaystyle{ d' \mid (a u + b v) }[/math]. Zatem [math]\displaystyle{ d' \leqslant d }[/math], skąd wynika natychmiast, że liczba [math]\displaystyle{ d }[/math] jest największym z dzielników, które jednocześnie dzielą liczby [math]\displaystyle{ a }[/math] oraz [math]\displaystyle{ b }[/math]. Czyli [math]\displaystyle{ d = D }[/math].


Twierdzenie C74 (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]
Dowód

Punkt 1.

Z założenia liczby [math]\displaystyle{ d }[/math] i [math]\displaystyle{ a }[/math] są względnie pierwsze, zatem na mocy lematu Bézouta (twierdzenie C73) istnieją takie liczby całkowite [math]\displaystyle{ x }[/math] i [math]\displaystyle{ y }[/math], że

[math]\displaystyle{ d x + a y = 1 }[/math]

Mnożąc obie strony równania przez [math]\displaystyle{ b }[/math], dostajemy

[math]\displaystyle{ d b x + a b y = b }[/math]

Obydwa wyrazy po lewej stronie są podzielne przez [math]\displaystyle{ d }[/math], bo z założenia [math]\displaystyle{ d \mid a b }[/math]. Zatem prawa strona również jest podzielna przez [math]\displaystyle{ d }[/math], czyli [math]\displaystyle{ d \mid b }[/math]. Co kończy dowód punktu pierwszego.

Punkt 2.

Jeżeli [math]\displaystyle{ p \nmid a }[/math], to [math]\displaystyle{ \gcd (p, a) = 1 }[/math], zatem z punktu pierwszego wynika, że [math]\displaystyle{ p \mid b }[/math].

Jeżeli [math]\displaystyle{ p \nmid b }[/math], to [math]\displaystyle{ \gcd (p, b) = 1 }[/math], zatem z punktu pierwszego wynika, że [math]\displaystyle{ p \mid a }[/math].

Czyli [math]\displaystyle{ p }[/math] musi dzielić przynajmniej jedną z liczb [math]\displaystyle{ a, b }[/math]. Co należało pokazać.


Twierdzenie C75
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].

Dowód

Z założenia istnieją takie liczby [math]\displaystyle{ r, s, x, y \in \mathbb{Z} }[/math], że [math]\displaystyle{ m = a r }[/math] i [math]\displaystyle{ m = b s }[/math] oraz

[math]\displaystyle{ a x + b y = 1 }[/math]

(zobacz C73). Zatem

[math]\displaystyle{ m = m (a x + b y) }[/math]
[math]\displaystyle{ \quad \, = m a x + m b y }[/math]
[math]\displaystyle{ \quad \, = b s a x + a r b y }[/math]
[math]\displaystyle{ \quad \, = a b (s x + r y) }[/math]

Czyli [math]\displaystyle{ a b \mid m }[/math]. Co należało pokazać.


Twierdzenie C76
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].

Dowód

Niech [math]\displaystyle{ D }[/math] oznacza największy wspólny dzielnik liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math].

[math]\displaystyle{ \Longrightarrow }[/math]

Jeżeli liczby całkowite [math]\displaystyle{ x_0 }[/math] i [math]\displaystyle{ y_0 }[/math] są rozwiązaniem rozpatrywanego równania, to

[math]\displaystyle{ a x_0 + b y_0 = c }[/math]

Ponieważ [math]\displaystyle{ D }[/math] dzieli lewą stronę równania, to musi również dzielić prawą, zatem musi być [math]\displaystyle{ D \mid c }[/math].

[math]\displaystyle{ \Longleftarrow }[/math]

Jeżeli [math]\displaystyle{ D \mid c }[/math], to możemy napisać [math]\displaystyle{ c = k D }[/math] i równanie przyjmuje postać

[math]\displaystyle{ a x + b y = k D }[/math]

Lemat Bézouta (twierdzenie C73) zapewnia istnienie liczb całkowitych [math]\displaystyle{ x_0 }[/math] i [math]\displaystyle{ y_0 }[/math] takich, że

[math]\displaystyle{ a x_0 + b y_0 = D }[/math]

Czyli z lematu Bézouta wynika, że równanie [math]\displaystyle{ a x + b y = D }[/math] ma rozwiązanie w liczbach całkowitych. Przekształcając, dostajemy

[math]\displaystyle{ a(k x_0) + b (k y_0) = k D }[/math]

Zatem liczby [math]\displaystyle{ k x_0 }[/math] i [math]\displaystyle{ k y_0 }[/math] są rozwiązaniem równania

[math]\displaystyle{ a x + b y = k D }[/math]

Co oznacza, że równianie [math]\displaystyle{ a x + b y = c }[/math] ma rozwiązanie.


Uwaga C77
Z twierdzenia C76 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 = \frac{A}{D} }[/math], [math]\displaystyle{ b = \frac{B}{D} }[/math], [math]\displaystyle{ c = \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 C78
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ą.

Dowód

Z założenia liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] są względnie pierwsze, zatem największy wspólny dzielnik tych liczb jest równy [math]\displaystyle{ 1 }[/math] i dzieli liczbę [math]\displaystyle{ c }[/math]. Na mocy twierdzenia C76 równanie

[math]\displaystyle{ a x + b y = c }[/math]

ma rozwiązanie w liczbach całkowitych.

Zauważmy, że jeżeli para liczb całkowitych [math]\displaystyle{ (x_0, y_0) }[/math] jest rozwiązaniem równania [math]\displaystyle{ a x + b y = c }[/math], to para liczb [math]\displaystyle{ (x_0 + b t, y_0 - a t) }[/math] również jest rozwiązaniem. Istotnie

[math]\displaystyle{ a(x_0 + b t) + b (y_0 - a t) = a x_0 + a b t + b y_0 - b a t = }[/math]
[math]\displaystyle{ \, = a x_0 + b y_0 = }[/math]
[math]\displaystyle{ \, = c }[/math]

Pokażmy teraz, że nie istnieją inne rozwiązania niż określone wzorami

[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ą.

Przypuśćmy, że pary liczb całkowitych [math]\displaystyle{ (x, y) }[/math] oraz [math]\displaystyle{ (x_0, y_0) }[/math] są rozwiązaniami rozpatrywanego równania, zatem

[math]\displaystyle{ a x + b y = c = a x_0 + b y_0 }[/math]

Wynika stąd, że musi być spełniony warunek

[math]\displaystyle{ a (x - x_0) = b (y_0 - y) }[/math]

Ponieważ liczby [math]\displaystyle{ a \, }[/math] i [math]\displaystyle{ \, b }[/math] są względnie pierwsze, to na mocy lematu Euklidesa (twierdzenie C74) [math]\displaystyle{ b \mid (x - x_0) }[/math]. Skąd mamy

[math]\displaystyle{ x - x_0 = b t }[/math]

gdzie [math]\displaystyle{ t }[/math] jest dowolną liczbą całkowitą. Po podstawieniu dostajemy natychmiast

[math]\displaystyle{ y - y_0 = - a t }[/math]

Co kończy dowód.


Przykład C79
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

  1. 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)
  2. 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].
  3. Wikipedia, Linnik's theorem, (Wiki-en)
  4. MathWorld, Linnik's Theorem. (MathWorld)
  5. Yuri Linnik, On the least prime in an arithmetic progression. I. The basic theorem, Mat. Sb. (N.S.) 15 (1944) 139–178.
  6. Yuri Linnik, On the least prime in an arithmetic progression. II. The Deuring-Heilbronn phenomenon, Mat. Sb. (N.S.) 15 (1944) 347–368.
  7. 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.
  8. 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
  9. Paul Turán, Über die Primzahlen der arithmetischen Progression, Acta Sci. Szeged 8 (1937), 226-235
  10. 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
  11. Wikipedia, Primes in arithmetic progression, (Wiki-en)
  12. MathWorld, Prime Arithmetic Progression, (LINK)
  13. J. G. van der Corput, Über Summen von Primzahlen und Primzahlquadraten, Mathematische Annalen, 116 (1939) 1-50, (LINK)
  14. Wikipedia, Largest known primes in AP, (Wiki-en)
  15. 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)
  16. Wikipedia, Primes in arithmetic progression - Largest known consecutive primes in AP, (Wiki-en)
  17. Henryk Dąbrowski, Twierdzenie Czebyszewa o liczbie pierwszej między n i 2n - Uwagi do twierdzenia, (LINK)