Liczby kwadratowe i niekwadratowe modulo. Wybrane zagadnienia - Historia wersji

HenrykDabrowski o 18:04, 6 sty 2026

2026-01-06T18:04:18Z

HenrykDabrowski o 11:57, 18 lis 2025

2025-11-18T11:57:49Z

HenrykDabrowski o 18:50, 7 lis 2025

2025-11-07T18:50:17Z

← poprzednia wersja		Wersja z 20:50, 7 lis 2025
Linia 1045:		Linia 1045:
	</div>		</div>

	Wynika stąd, że najmniejsza liczba niekwadratowa modulo <math>p</math> jest większa od <math>m</math>. Wiemy też, że (zobacz A9)		Wynika stąd, że najmniejsza liczba niekwadratowa modulo <math>p</math> jest większa od <math>m</math>. Wiemy też, że (zobacz A10)

	::<math>a = 4 P (m) < 4 \cdot 4^m = 4^{m + 1}</math>		::<math>a = 4 P (m) < 4 \cdot 4^m = 4^{m + 1}</math>

HenrykDabrowski o 11:29, 31 maj 2024

2024-05-31T11:29:35Z

HenrykDabrowski o 16:33, 17 mar 2024

2024-03-17T16:33:12Z

Podgląd zmian

HenrykDabrowski o 11:34, 5 mar 2024

2024-03-05T11:34:44Z

← poprzednia wersja		Wersja z 13:34, 5 mar 2024
Linia 109:		Linia 109:
	::::::::<math>\;\;\, = \underset{p \nmid j}{\sum_{j = a}^{p - 1 + a}} \left( {\small\frac{1 + (b - a) j^{- 1}}{p}} \right)_{\small{\!\! L}}</math>		::::::::<math>\;\;\, = \underset{p \nmid j}{\sum_{j = a}^{p - 1 + a}} \left( {\small\frac{1 + (b - a) j^{- 1}}{p}} \right)_{\small{\!\! L}}</math>

	Z własności symbolu Legendre'a wiemy, że licznik wpływa na wartość symbolu jedynie modulo mianownik. Liczby <math>j = k + a</math>, gdzie <math>k = 0, 1, \ldots, p - 1</math>, są wszystkie różne modulo <math>p</math> (zobacz ~~H20~~). Niech zbiór <math>S</math> będzie zbiorem wszystkich liczb <math>j = k + a</math>, które nie są podzielne przez <math>p</math>. Na mocy twierdzenia ~~H25~~ zbiory <math>R = \{ 1, \ldots, p - 1 \}</math>, <math>S</math> oraz <math>T = \{ s^{- 1}_1, \ldots, s^{- 1}_{p - 1} \}</math>, gdzie <math>s_k \in S</math>, są równe modulo <math>p</math>. Zatem od sumowania po <math>j</math> możemy przejść do sumowania po <math>r \in R</math>.		Z własności symbolu Legendre'a wiemy, że licznik wpływa na wartość symbolu jedynie modulo mianownik. Liczby <math>j = k + a</math>, gdzie <math>k = 0, 1, \ldots, p - 1</math>, są wszystkie różne modulo <math>p</math> (zobacz H21). Niech zbiór <math>S</math> będzie zbiorem wszystkich liczb <math>j = k + a</math>, które nie są podzielne przez <math>p</math>. Na mocy twierdzenia H26 zbiory <math>R = \{ 1, \ldots, p - 1 \}</math>, <math>S</math> oraz <math>T = \{ s^{- 1}_1, \ldots, s^{- 1}_{p - 1} \}</math>, gdzie <math>s_k \in S</math>, są równe modulo <math>p</math>. Zatem od sumowania po <math>j</math> możemy przejść do sumowania po <math>r \in R</math>.

	::<math>\sum_{k = 0}^{p - 1} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + b}{p}} \right)_{\small{\!\! L}}		::<math>\sum_{k = 0}^{p - 1} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + b}{p}} \right)_{\small{\!\! L}}

HenrykDabrowski o 11:20, 24 lut 2024

2024-02-24T11:20:01Z

← poprzednia wersja		Wersja z 13:20, 24 lut 2024
Linia 1573:		Linia 1573:

	{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}		{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}
	Twierdzenie to jest prostym wnioskiem z twierdzenia K42, ale musimy jeszcze pokazać, że <math>\gcd (\mathbb{n} (m), m) = 1 .</math> Przypuśćmy, że <math>p_k \|\mathbb{n} (m)</math> dla pewnego <math>1 \leqslant k \leqslant s .</math> Ponieważ <math>\mathbb{n} (m)</math> jest liczbą pierwszą, to musi być <math>\mathbb{n} (m) = p_k</math>, ale wtedy		Twierdzenie to jest prostym wnioskiem z twierdzenia K42, ale musimy jeszcze pokazać, że <math>\gcd (\mathbb{n} (m), m) = 1 .</math> Przypuśćmy, że <math>p_k \mid \mathbb{n} (m)</math> dla pewnego <math>1 \leqslant k \leqslant s .</math> Ponieważ <math>\mathbb{n} (m)</math> jest liczbą pierwszą, to musi być <math>\mathbb{n} (m) = p_k</math>, ale wtedy

	::<math>\mathbb{n} (p_k) < p_k =\mathbb{n} (m) \leqslant \mathbb{n} (p_k)</math>		::<math>\mathbb{n} (p_k) < p_k =\mathbb{n} (m) \leqslant \mathbb{n} (p_k)</math>

HenrykDabrowski o 15:41, 23 lut 2024

2024-02-23T15:41:31Z

← poprzednia wersja		Wersja z 17:41, 23 lut 2024
Linia 1429:		Linia 1429:
	\| <math>m=120k \pm 50</math> \|\| style="text-align:center;" \| <math>3</math> \|\| style="text-align:center;" \| K35		\| <math>m=120k \pm 50</math> \|\| style="text-align:center;" \| <math>3</math> \|\| style="text-align:center;" \| K35
	\|-		\|-
	\| <math>m=30k \pm 6</math> \|\| style="text-align:center;" \| <math>5</math> \|\| rowspan="2" style="text-align:center;" \| K36, K37		\| <math>m=30k \pm 6</math> \|\| style="text-align:center;" \| <math>5</math> \|\| rowspan="2" style="text-align:center;" \| K36, K37
	\|-		\|-
	\| <math>m=30k \pm 12</math> \|\| style="text-align:center;" \| <math>5</math>		\| <math>m=30k \pm 12</math> \|\| style="text-align:center;" \| <math>5</math>

HenrykDabrowski o 12:17, 23 lut 2024

2024-02-23T12:17:55Z

← poprzednia wersja		Wersja z 14:17, 23 lut 2024
Linia 1429:		Linia 1429:
	\| <math>m=120k \pm 50</math> \|\| style="text-align:center;" \| <math>3</math> \|\| style="text-align:center;" \| K35		\| <math>m=120k \pm 50</math> \|\| style="text-align:center;" \| <math>3</math> \|\| style="text-align:center;" \| K35
	\|-		\|-
	\| <math>m=30k \pm 6</math> \|\| style="text-align:center;" \| <math>5</math> \|\| rowspan="2" style="text-align:center;" \| K36,~~<math>\;</math>~~K37		\| <math>m=30k \pm 6</math> \|\| style="text-align:center;" \| <math>5</math> \|\| rowspan="2" style="text-align:center;" \| K36, K37
	\|-		\|-
	\| <math>m=30k \pm 12</math> \|\| style="text-align:center;" \| <math>5</math>		\| <math>m=30k \pm 12</math> \|\| style="text-align:center;" \| <math>5</math>

HenrykDabrowski o 17:51, 22 lut 2024

2024-02-22T17:51:18Z

← poprzednia wersja		Wersja z 19:51, 22 lut 2024
Linia 1429:		Linia 1429:
	\| <math>m=120k \pm 50</math> \|\| style="text-align:center;" \| <math>3</math> \|\| style="text-align:center;" \| K35		\| <math>m=120k \pm 50</math> \|\| style="text-align:center;" \| <math>3</math> \|\| style="text-align:center;" \| K35
	\|-		\|-
	\| <math>m=30k \pm 6</math> \|\| style="text-align:center;" \| <math>5</math> \|\| rowspan="2" style="text-align:center;" \| K36, K37		\| <math>m=30k \pm 6</math> \|\| style="text-align:center;" \| <math>5</math> \|\| rowspan="2" style="text-align:center;" \| K36,<math>\;</math>K37
	\|-		\|-
	\| <math>m=30k \pm 12</math> \|\| style="text-align:center;" \| <math>5</math>		\| <math>m=30k \pm 12</math> \|\| style="text-align:center;" \| <math>5</math>

← poprzednia wersja		Wersja z 13:57, 18 lis 2025
Linia 36:		Linia 36:
	'''Punkt 3.'''		'''Punkt 3.'''

	Z założenia liczby <math>p</math> i <math>d</math> są względnie pierwsze. Z twierdzenia ~~C58~~ wiemy, że reszty <math>r_1, r_2, \ldots, r_p</math> z dzielenia <math>p</math> kolejnych liczb postaci		Z założenia liczby <math>p</math> i <math>d</math> są względnie pierwsze. Z twierdzenia C59 wiemy, że reszty <math>r_1, r_2, \ldots, r_p</math> z dzielenia <math>p</math> kolejnych liczb postaci

	::<math>x_k = a + k d</math>		::<math>x_k = a + k d</math>
Linia 79:		Linia 79:
	= \sum_{k = 0}^{p - 1} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}}^{\! 2}</math>		= \sum_{k = 0}^{p - 1} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}}^{\! 2}</math>

	Z twierdzenia ~~C58~~ wiemy, że reszty <math>r_1, r_2, \ldots, r_p</math> z dzielenia <math>p</math> kolejnych liczb postaci		Z twierdzenia C59 wiemy, że reszty <math>r_1, r_2, \ldots, r_p</math> z dzielenia <math>p</math> kolejnych liczb postaci

	::<math>x_k = a + k</math>		::<math>x_k = a + k</math>
Linia 159:		Linia 159:
	:::<math>\;\;\; = \sum_{k = 0}^{p - 1} \left( {\small\frac{(k r^{- 1})^2 + b}{p}} \right)_{\small{\!\! L}}</math>		:::<math>\;\;\; = \sum_{k = 0}^{p - 1} \left( {\small\frac{(k r^{- 1})^2 + b}{p}} \right)_{\small{\!\! L}}</math>

	Z twierdzenia ~~C58~~ wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>k r^{- 1}</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem		Z twierdzenia C59 wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>k r^{- 1}</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem

	::<math>S(a) = \sum_{x = 0}^{p - 1} \left( {\small\frac{x^2 + b}{p}} \right)_{\small{\!\! L}} = S (b)</math>		::<math>S(a) = \sum_{x = 0}^{p - 1} \left( {\small\frac{x^2 + b}{p}} \right)_{\small{\!\! L}} = S (b)</math>
Linia 224:		Linia 224:
	:::::::<math>\;\;\;\, = \sum^{p - 1}_{k = 0} \left( {\small\frac{(2 k + r)^2 + 4 s - r^2}{p}} \right)_{\small{\!\! L}}</math>		:::::::<math>\;\;\;\, = \sum^{p - 1}_{k = 0} \left( {\small\frac{(2 k + r)^2 + 4 s - r^2}{p}} \right)_{\small{\!\! L}}</math>

	Z twierdzenia ~~C58~~ wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>2 k + r</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem		Z twierdzenia C59 wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>2 k + r</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem

	::<math>\sum_{k = 0}^{p - 1} \left( {\small\frac{k^2 + r k + s}{p}} \right)_{\small{\!\! L}} = \sum_{x = 0}^{p - 1} \left( {\small\frac{x^2 + 4 s - r^2}{p}} \right)_{\small{\!\! L}}</math>		::<math>\sum_{k = 0}^{p - 1} \left( {\small\frac{k^2 + r k + s}{p}} \right)_{\small{\!\! L}} = \sum_{x = 0}^{p - 1} \left( {\small\frac{x^2 + 4 s - r^2}{p}} \right)_{\small{\!\! L}}</math>
Linia 279:		Linia 279:
	::::::<math>\;\:\, = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} \sum_{k = 0}^{p - 1} \left( {\small\frac{(k r^{- 1}) \left[ (k r^{- 1})^2 + b \right] }{p}} \right)_{\small{\!\! L}}</math>		::::::<math>\;\:\, = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} \sum_{k = 0}^{p - 1} \left( {\small\frac{(k r^{- 1}) \left[ (k r^{- 1})^2 + b \right] }{p}} \right)_{\small{\!\! L}}</math>

	Z twierdzenia ~~C58~~ wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>k r^{- 1}</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem		Z twierdzenia C59 wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>k r^{- 1}</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem

	::<math>S(a) = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} \sum_{x = 0}^{p - 1} \left( {\small\frac{x (x^2 + b)}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} S (b)</math>		::<math>S(a) = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} \sum_{x = 0}^{p - 1} \left( {\small\frac{x (x^2 + b)}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} S (b)</math>
Linia 415:		Linia 415:
	::<math>\sum_{x = 0}^{p - 1} \left( {\small\frac{x^3 + x^2 (b - 3 r) + x [a c - r (2 b - 3 r)] + [a^2 d - a c r + r^2 (b - r)]}{p}} \right)_{\small{\!\! L}}</math>		::<math>\sum_{x = 0}^{p - 1} \left( {\small\frac{x^3 + x^2 (b - 3 r) + x [a c - r (2 b - 3 r)] + [a^2 d - a c r + r^2 (b - r)]}{p}} \right)_{\small{\!\! L}}</math>

	bo, gdy <math>t</math> przebiega zbiór <math>\{ 0, 1, \ldots, p - 1 \}</math>, to (modulo <math>p</math>) liczby <math>a t + r</math> przebiegają taki sam zbiór (zobacz ~~C58~~). Ponieważ <math>p \geqslant 5</math>, to liczbę <math>r</math> możemy wybrać tak, aby było		bo, gdy <math>t</math> przebiega zbiór <math>\{ 0, 1, \ldots, p - 1 \}</math>, to (modulo <math>p</math>) liczby <math>a t + r</math> przebiegają taki sam zbiór (zobacz C59). Ponieważ <math>p \geqslant 5</math>, to liczbę <math>r</math> możemy wybrać tak, aby było

	::<math>3 r \equiv b \!\! \pmod{p}</math>		::<math>3 r \equiv b \!\! \pmod{p}</math>
Linia 465:		Linia 465:
	::<math>S(a, b) = \sum_{x = 0}^{p - 1} \left( {\small\frac{x - x_2}{p}} \right)_{\small{\!\! L}}^{\! 2} \left( {\small\frac{x - x_1}{p}} \right)_{\small{\!\! L}}</math>		::<math>S(a, b) = \sum_{x = 0}^{p - 1} \left( {\small\frac{x - x_2}{p}} \right)_{\small{\!\! L}}^{\! 2} \left( {\small\frac{x - x_1}{p}} \right)_{\small{\!\! L}}</math>

	Niech <math>t = x - x_2</math>. Jeżeli <math>x</math> przebiega zbiór <math>\{ 0, 1, \ldots, p - 1 \}</math>, to (modulo <math>p</math>) <math>t</math> przebiega taki sam zbiór (zobacz ~~C58~~). Zatem		Niech <math>t = x - x_2</math>. Jeżeli <math>x</math> przebiega zbiór <math>\{ 0, 1, \ldots, p - 1 \}</math>, to (modulo <math>p</math>) <math>t</math> przebiega taki sam zbiór (zobacz C59). Zatem

	::<math>S(a, b) = \sum_{t = 0}^{p - 1} \left( {\small\frac{t}{p}} \right)_{\small{\!\! L}}^{\! 2} \left( {\small\frac{t + x_2 - x_1}{p}} \right)_{\small{\!\! L}}		::<math>S(a, b) = \sum_{t = 0}^{p - 1} \left( {\small\frac{t}{p}} \right)_{\small{\!\! L}}^{\! 2} \left( {\small\frac{t + x_2 - x_1}{p}} \right)_{\small{\!\! L}}
Linia 1008:		Linia 1008:
	::<math>u \equiv 0 \pmod{p_k}</math>		::<math>u \equiv 0 \pmod{p_k}</math>

	wbrew wypisanemu wyżej układowi kongruencji. Zatem <math>\gcd (c, 8 p_2 \cdot \ldots \cdot p_n) = 1</math> i z twierdzenia Dirichleta (zobacz ~~C28~~) wiemy, że wśród liczb <math>u</math> spełniających kongruencję <math>u \equiv c \!\! \pmod{8 p_2 \cdot \ldots \cdot p_n}</math> występuje nieskończenie wiele liczb pierwszych (bo wśród tych liczb są liczby postaci <math>8 p_2 \cdot \ldots \cdot p_n \cdot k + c</math>, gdzie <math>k \in \mathbb{Z}_+</math>). Oznaczmy przez <math>q</math> dowolną z tych liczb pierwszych.		wbrew wypisanemu wyżej układowi kongruencji. Zatem <math>\gcd (c, 8 p_2 \cdot \ldots \cdot p_n) = 1</math> i z twierdzenia Dirichleta (zobacz C29) wiemy, że wśród liczb <math>u</math> spełniających kongruencję <math>u \equiv c \!\! \pmod{8 p_2 \cdot \ldots \cdot p_n}</math> występuje nieskończenie wiele liczb pierwszych (bo wśród tych liczb są liczby postaci <math>8 p_2 \cdot \ldots \cdot p_n \cdot k + c</math>, gdzie <math>k \in \mathbb{Z}_+</math>). Oznaczmy przez <math>q</math> dowolną z tych liczb pierwszych.


Linia 1033:		Linia 1033:

	{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}		{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}
	Niech <math>a = 4 P (m)</math>, gdzie <math>P(m)</math> jest iloczynem wszystkich liczb pierwszych nie większych od <math>m</math>. Z twierdzenia Dirichleta (zobacz ~~C28~~) wiemy, że w ciągu arytmetycznym <math>u_k = a k + 1</math> występuje nieskończenie wiele liczb pierwszych. Niech <math>p</math> oznacza dowolną z nich.		Niech <math>a = 4 P (m)</math>, gdzie <math>P(m)</math> jest iloczynem wszystkich liczb pierwszych nie większych od <math>m</math>. Z twierdzenia Dirichleta (zobacz C29) wiemy, że w ciągu arytmetycznym <math>u_k = a k + 1</math> występuje nieskończenie wiele liczb pierwszych. Niech <math>p</math> oznacza dowolną z nich.

	Ponieważ <math>p \equiv 1 \!\! \pmod{8}</math>, to		Ponieważ <math>p \equiv 1 \!\! \pmod{8}</math>, to
Linia 1049:		Linia 1049:
	::<math>a = 4 P (m) < 4 \cdot 4^m = 4^{m + 1}</math>		::<math>a = 4 P (m) < 4 \cdot 4^m = 4^{m + 1}</math>

	Załóżmy teraz, że <math>p</math> jest najmniejszą liczbą pierwszą w ciągu arytmetycznym <math>u_k = a k + 1</math>, a liczba <math>m</math> została wybrana tak, że liczba <math>a = 4 P (m)</math> jest dostatecznie duża i możliwe jest skorzystanie z twierdzenia Linnika (zobacz ~~C31~~). Dostajemy natychmiast oszacowanie		Załóżmy teraz, że <math>p</math> jest najmniejszą liczbą pierwszą w ciągu arytmetycznym <math>u_k = a k + 1</math>, a liczba <math>m</math> została wybrana tak, że liczba <math>a = 4 P (m)</math> jest dostatecznie duża i możliwe jest skorzystanie z twierdzenia Linnika (zobacz C32). Dostajemy natychmiast oszacowanie

	::<math>p = p_{\min} (a, 1) < a^L</math>		::<math>p = p_{\min} (a, 1) < a^L</math>
Linia 2279:		Linia 2279:
	\end{cases}</math>		\end{cases}</math>

	Dla ustalonych liczb <math>n</math> i <math>s</math> rozważmy liczbę <math>u(a) = {\small\frac{p - s a^2}{2^n}}</math> taką, że <math>3 \leqslant u (a) < p</math>. Jeżeli liczba ta jest postaci <math>4 k + 3</math>, to ma dzielnik pierwszy <math>q < p</math> postaci <math>4 k + 3</math> (zobacz ~~C22~~). Zatem możemy napisać <math>u (a) = t q</math>, co oznacza, że		Dla ustalonych liczb <math>n</math> i <math>s</math> rozważmy liczbę <math>u(a) = {\small\frac{p - s a^2}{2^n}}</math> taką, że <math>3 \leqslant u (a) < p</math>. Jeżeli liczba ta jest postaci <math>4 k + 3</math>, to ma dzielnik pierwszy <math>q < p</math> postaci <math>4 k + 3</math> (zobacz C23). Zatem możemy napisać <math>u (a) = t q</math>, co oznacza, że

	::<math>p - s a^2 = 2^n u (a) = 2^n t q</math>		::<math>p - s a^2 = 2^n u (a) = 2^n t q</math>
Linia 2434:		Linia 2434:

	{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}		{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}
	Ponieważ liczba <math>m - 4 \geqslant 3</math> jest postaci <math>4 k + 3</math>, to ma dzielnik pierwszy <math>q < m</math> postaci <math>4 k + 3</math> (zobacz ~~C22~~). Czyli <math>m - 4 = k q</math> i z twierdzenia J42 p.9 dostajemy		Ponieważ liczba <math>m - 4 \geqslant 3</math> jest postaci <math>4 k + 3</math>, to ma dzielnik pierwszy <math>q < m</math> postaci <math>4 k + 3</math> (zobacz C23). Czyli <math>m - 4 = k q</math> i z twierdzenia J42 p.9 dostajemy

	::<math>\left( {\small\frac{q}{m}} \right)_{\small{\!\! J}} =		::<math>\left( {\small\frac{q}{m}} \right)_{\small{\!\! J}} =

← poprzednia wersja		Wersja z 13:29, 31 maj 2024
Linia 36:		Linia 36:
	'''Punkt 3.'''		'''Punkt 3.'''

	Z założenia liczby <math>p</math> i <math>d</math> są względnie pierwsze. Z twierdzenia ~~C57~~ wiemy, że reszty <math>r_1, r_2, \ldots, r_p</math> z dzielenia <math>p</math> kolejnych liczb postaci		Z założenia liczby <math>p</math> i <math>d</math> są względnie pierwsze. Z twierdzenia C58 wiemy, że reszty <math>r_1, r_2, \ldots, r_p</math> z dzielenia <math>p</math> kolejnych liczb postaci

	::<math>x_k = a + k d</math>		::<math>x_k = a + k d</math>
Linia 79:		Linia 79:
	= \sum_{k = 0}^{p - 1} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}}^{\! 2}</math>		= \sum_{k = 0}^{p - 1} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}}^{\! 2}</math>

	Z twierdzenia ~~C57~~ wiemy, że reszty <math>r_1, r_2, \ldots, r_p</math> z dzielenia <math>p</math> kolejnych liczb postaci		Z twierdzenia C58 wiemy, że reszty <math>r_1, r_2, \ldots, r_p</math> z dzielenia <math>p</math> kolejnych liczb postaci

	::<math>x_k = a + k</math>		::<math>x_k = a + k</math>
Linia 159:		Linia 159:
	:::<math>\;\;\; = \sum_{k = 0}^{p - 1} \left( {\small\frac{(k r^{- 1})^2 + b}{p}} \right)_{\small{\!\! L}}</math>		:::<math>\;\;\; = \sum_{k = 0}^{p - 1} \left( {\small\frac{(k r^{- 1})^2 + b}{p}} \right)_{\small{\!\! L}}</math>

	Z twierdzenia ~~C57~~ wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>k r^{- 1}</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem		Z twierdzenia C58 wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>k r^{- 1}</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem

	::<math>S(a) = \sum_{x = 0}^{p - 1} \left( {\small\frac{x^2 + b}{p}} \right)_{\small{\!\! L}} = S (b)</math>		::<math>S(a) = \sum_{x = 0}^{p - 1} \left( {\small\frac{x^2 + b}{p}} \right)_{\small{\!\! L}} = S (b)</math>
Linia 224:		Linia 224:
	:::::::<math>\;\;\;\, = \sum^{p - 1}_{k = 0} \left( {\small\frac{(2 k + r)^2 + 4 s - r^2}{p}} \right)_{\small{\!\! L}}</math>		:::::::<math>\;\;\;\, = \sum^{p - 1}_{k = 0} \left( {\small\frac{(2 k + r)^2 + 4 s - r^2}{p}} \right)_{\small{\!\! L}}</math>

	Z twierdzenia ~~C57~~ wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>2 k + r</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem		Z twierdzenia C58 wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>2 k + r</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem

	::<math>\sum_{k = 0}^{p - 1} \left( {\small\frac{k^2 + r k + s}{p}} \right)_{\small{\!\! L}} = \sum_{x = 0}^{p - 1} \left( {\small\frac{x^2 + 4 s - r^2}{p}} \right)_{\small{\!\! L}}</math>		::<math>\sum_{k = 0}^{p - 1} \left( {\small\frac{k^2 + r k + s}{p}} \right)_{\small{\!\! L}} = \sum_{x = 0}^{p - 1} \left( {\small\frac{x^2 + 4 s - r^2}{p}} \right)_{\small{\!\! L}}</math>
Linia 279:		Linia 279:
	::::::<math>\;\:\, = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} \sum_{k = 0}^{p - 1} \left( {\small\frac{(k r^{- 1}) \left[ (k r^{- 1})^2 + b \right] }{p}} \right)_{\small{\!\! L}}</math>		::::::<math>\;\:\, = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} \sum_{k = 0}^{p - 1} \left( {\small\frac{(k r^{- 1}) \left[ (k r^{- 1})^2 + b \right] }{p}} \right)_{\small{\!\! L}}</math>

	Z twierdzenia ~~C57~~ wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>k r^{- 1}</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem		Z twierdzenia C58 wiemy, że gdy <math>k</math> przebiega zbiór <math>T = \{ 0, 1, \ldots, p - 1 \}</math>, to <math>k r^{- 1}</math> przebiega zbiór <math>T'</math> identyczny ze zbiorem <math>T</math> modulo <math>p</math>. Zatem

	::<math>S(a) = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} \sum_{x = 0}^{p - 1} \left( {\small\frac{x (x^2 + b)}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} S (b)</math>		::<math>S(a) = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} \sum_{x = 0}^{p - 1} \left( {\small\frac{x (x^2 + b)}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} S (b)</math>
Linia 415:		Linia 415:
	::<math>\sum_{x = 0}^{p - 1} \left( {\small\frac{x^3 + x^2 (b - 3 r) + x [a c - r (2 b - 3 r)] + [a^2 d - a c r + r^2 (b - r)]}{p}} \right)_{\small{\!\! L}}</math>		::<math>\sum_{x = 0}^{p - 1} \left( {\small\frac{x^3 + x^2 (b - 3 r) + x [a c - r (2 b - 3 r)] + [a^2 d - a c r + r^2 (b - r)]}{p}} \right)_{\small{\!\! L}}</math>

	bo, gdy <math>t</math> przebiega zbiór <math>\{ 0, 1, \ldots, p - 1 \}</math>, to (modulo <math>p</math>) liczby <math>a t + r</math> przebiegają taki sam zbiór (zobacz ~~C57~~). Ponieważ <math>p \geqslant 5</math>, to liczbę <math>r</math> możemy wybrać tak, aby było		bo, gdy <math>t</math> przebiega zbiór <math>\{ 0, 1, \ldots, p - 1 \}</math>, to (modulo <math>p</math>) liczby <math>a t + r</math> przebiegają taki sam zbiór (zobacz C58). Ponieważ <math>p \geqslant 5</math>, to liczbę <math>r</math> możemy wybrać tak, aby było

	::<math>3 r \equiv b \!\! \pmod{p}</math>		::<math>3 r \equiv b \!\! \pmod{p}</math>
Linia 465:		Linia 465:
	::<math>S(a, b) = \sum_{x = 0}^{p - 1} \left( {\small\frac{x - x_2}{p}} \right)_{\small{\!\! L}}^{\! 2} \left( {\small\frac{x - x_1}{p}} \right)_{\small{\!\! L}}</math>		::<math>S(a, b) = \sum_{x = 0}^{p - 1} \left( {\small\frac{x - x_2}{p}} \right)_{\small{\!\! L}}^{\! 2} \left( {\small\frac{x - x_1}{p}} \right)_{\small{\!\! L}}</math>

	Niech <math>t = x - x_2</math>. Jeżeli <math>x</math> przebiega zbiór <math>\{ 0, 1, \ldots, p - 1 \}</math>, to (modulo <math>p</math>) <math>t</math> przebiega taki sam zbiór (zobacz ~~C57~~). Zatem		Niech <math>t = x - x_2</math>. Jeżeli <math>x</math> przebiega zbiór <math>\{ 0, 1, \ldots, p - 1 \}</math>, to (modulo <math>p</math>) <math>t</math> przebiega taki sam zbiór (zobacz C58). Zatem

	::<math>S(a, b) = \sum_{t = 0}^{p - 1} \left( {\small\frac{t}{p}} \right)_{\small{\!\! L}}^{\! 2} \left( {\small\frac{t + x_2 - x_1}{p}} \right)_{\small{\!\! L}}		::<math>S(a, b) = \sum_{t = 0}^{p - 1} \left( {\small\frac{t}{p}} \right)_{\small{\!\! L}}^{\! 2} \left( {\small\frac{t + x_2 - x_1}{p}} \right)_{\small{\!\! L}}
Linia 1008:		Linia 1008:
	::<math>u \equiv 0 \pmod{p_k}</math>		::<math>u \equiv 0 \pmod{p_k}</math>

	wbrew wypisanemu wyżej układowi kongruencji. Zatem <math>\gcd (c, 8 p_2 \cdot \ldots \cdot p_n) = 1</math> i z twierdzenia Dirichleta (zobacz ~~C27~~) wiemy, że wśród liczb <math>u</math> spełniających kongruencję <math>u \equiv c \!\! \pmod{8 p_2 \cdot \ldots \cdot p_n}</math> występuje nieskończenie wiele liczb pierwszych (bo wśród tych liczb są liczby postaci <math>8 p_2 \cdot \ldots \cdot p_n \cdot k + c</math>, gdzie <math>k \in \mathbb{Z}_+</math>). Oznaczmy przez <math>q</math> dowolną z tych liczb pierwszych.		wbrew wypisanemu wyżej układowi kongruencji. Zatem <math>\gcd (c, 8 p_2 \cdot \ldots \cdot p_n) = 1</math> i z twierdzenia Dirichleta (zobacz C28) wiemy, że wśród liczb <math>u</math> spełniających kongruencję <math>u \equiv c \!\! \pmod{8 p_2 \cdot \ldots \cdot p_n}</math> występuje nieskończenie wiele liczb pierwszych (bo wśród tych liczb są liczby postaci <math>8 p_2 \cdot \ldots \cdot p_n \cdot k + c</math>, gdzie <math>k \in \mathbb{Z}_+</math>). Oznaczmy przez <math>q</math> dowolną z tych liczb pierwszych.


Linia 1033:		Linia 1033:

	{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}		{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}
	Niech <math>a = 4 P (m)</math>, gdzie <math>P(m)</math> jest iloczynem wszystkich liczb pierwszych nie większych od <math>m</math>. Z twierdzenia Dirichleta (zobacz ~~C27~~) wiemy, że w ciągu arytmetycznym <math>u_k = a k + 1</math> występuje nieskończenie wiele liczb pierwszych. Niech <math>p</math> oznacza dowolną z nich.		Niech <math>a = 4 P (m)</math>, gdzie <math>P(m)</math> jest iloczynem wszystkich liczb pierwszych nie większych od <math>m</math>. Z twierdzenia Dirichleta (zobacz C28) wiemy, że w ciągu arytmetycznym <math>u_k = a k + 1</math> występuje nieskończenie wiele liczb pierwszych. Niech <math>p</math> oznacza dowolną z nich.

	Ponieważ <math>p \equiv 1 \!\! \pmod{8}</math>, to		Ponieważ <math>p \equiv 1 \!\! \pmod{8}</math>, to
Linia 1049:		Linia 1049:
	::<math>a = 4 P (m) < 4 \cdot 4^m = 4^{m + 1}</math>		::<math>a = 4 P (m) < 4 \cdot 4^m = 4^{m + 1}</math>

	Załóżmy teraz, że <math>p</math> jest najmniejszą liczbą pierwszą w ciągu arytmetycznym <math>u_k = a k + 1</math>, a liczba <math>m</math> została wybrana tak, że liczba <math>a = 4 P (m)</math> jest dostatecznie duża i możliwe jest skorzystanie z twierdzenia Linnika (zobacz ~~C30~~). Dostajemy natychmiast oszacowanie		Załóżmy teraz, że <math>p</math> jest najmniejszą liczbą pierwszą w ciągu arytmetycznym <math>u_k = a k + 1</math>, a liczba <math>m</math> została wybrana tak, że liczba <math>a = 4 P (m)</math> jest dostatecznie duża i możliwe jest skorzystanie z twierdzenia Linnika (zobacz C31). Dostajemy natychmiast oszacowanie

	::<math>p = p_{\min} (a, 1) < a^L</math>		::<math>p = p_{\min} (a, 1) < a^L</math>
Linia 2279:		Linia 2279:
	\end{cases}</math>		\end{cases}</math>

	Dla ustalonych liczb <math>n</math> i <math>s</math> rozważmy liczbę <math>u(a) = {\small\frac{p - s a^2}{2^n}}</math> taką, że <math>3 \leqslant u (a) < p</math>. Jeżeli liczba ta jest postaci <math>4 k + 3</math>, to ma dzielnik pierwszy <math>q < p</math> postaci <math>4 k + 3</math> (zobacz ~~C21~~). Zatem możemy napisać <math>u (a) = t q</math>, co oznacza, że		Dla ustalonych liczb <math>n</math> i <math>s</math> rozważmy liczbę <math>u(a) = {\small\frac{p - s a^2}{2^n}}</math> taką, że <math>3 \leqslant u (a) < p</math>. Jeżeli liczba ta jest postaci <math>4 k + 3</math>, to ma dzielnik pierwszy <math>q < p</math> postaci <math>4 k + 3</math> (zobacz C22). Zatem możemy napisać <math>u (a) = t q</math>, co oznacza, że

	::<math>p - s a^2 = 2^n u (a) = 2^n t q</math>		::<math>p - s a^2 = 2^n u (a) = 2^n t q</math>
Linia 2434:		Linia 2434:

	{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}		{{Spoiler\|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;\|Show=Dowód\|Hide=Ukryj dowód}}
	Ponieważ liczba <math>m - 4 \geqslant 3</math> jest postaci <math>4 k + 3</math>, to ma dzielnik pierwszy <math>q < m</math> postaci <math>4 k + 3</math> (zobacz ~~C21~~). Czyli <math>m - 4 = k q</math> i z twierdzenia J42 p.9 dostajemy		Ponieważ liczba <math>m - 4 \geqslant 3</math> jest postaci <math>4 k + 3</math>, to ma dzielnik pierwszy <math>q < m</math> postaci <math>4 k + 3</math> (zobacz C22). Czyli <math>m - 4 = k q</math> i z twierdzenia J42 p.9 dostajemy

	::<math>\left( {\small\frac{q}{m}} \right)_{\small{\!\! J}} =		::<math>\left( {\small\frac{q}{m}} \right)_{\small{\!\! J}} =