Tekst źródłowy strony Liczby kwadratowe i niekwadratowe modulo. Wybrane zagadnienia

<div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">22.04.2023</div>

__FORCETOC__



== Element odwrotny modulo <math>m</math> == 

<span style="font-size: 110%; font-weight: bold;">Twierdzenie K1</span><br/>
Niech <math>m \in \mathbb{Z}_+</math>. Dla liczby <math>k</math> istnieje taka liczba <math>x</math>, że

::<math>x k \equiv 1 \!\! \pmod{m}</math>

wtedy i&nbsp;tylko wtedy, gdy <math>\gcd (k, m) = 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

<math>\Large{\Longrightarrow}</math>

Z założenia istnieje taka liczba <math>x</math>, że

::<math>x k \equiv 1 \!\! \pmod{m}</math>

Zatem dla pewnego <math>r \in \mathbb{Z}</math> jest

::<math>x k = 1 + r m</math>

Czyli <math>x k - r m = 1</math>. Wynika stąd, że <math>\gcd (k, m)</math> dzieli <math>1</math>, co oznacza, że <math>\gcd (k, m) = 1</math>.

<math>\Large{\Longleftarrow}</math>

Z założenia <math>\gcd (k, m) = 1</math>. Z&nbsp;lematu Bézouta (zobacz C71) wynika, że istnieją takie liczby całkowite <math>x, y</math>, że

::<math>k x + m y = 1</math>

Zatem modulo <math>m</math> dostajemy

::<math>k x \equiv 1 \!\! \pmod{m}</math>

Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Definicja K2</span><br/>
Niech <math>m \in \mathbb{Z}_+</math>. Liczbę <math>x</math> taką, że

::<math>x \cdot k \equiv 1 \!\! \pmod{m}</math>

będziemy nazywali elementem odwrotnym liczby <math>k</math> modulo <math>m</math> i&nbsp;oznaczali jako <math>k^{- 1}</math>.



<span style="font-size: 110%; font-weight: bold;">Uwaga K3</span><br/>
Oznaczenie elementu odwrotnego ma naturalne uzasadnienie. Zauważmy, że jeżeli <math>b \mid a</math> oraz <math>b</math> ma element odwrotny modulo <math>m</math>, to prawdziwa jest kongruencja

::<math>{\small\frac{a}{b}} \equiv a b^{- 1} \!\! \pmod{m}</math>

Istotnie

::<math>{\small\frac{a}{b}} = {\small\frac{a}{b}} \cdot 1 \equiv {\small\frac{a}{b}} \cdot b b^{- 1} \equiv a b^{- 1}\!\! \pmod{m}</math>

W PARI/GP odwrotność liczby <math>a</math> modulo <math>m</math> znajdujemy, wpisując <code>Mod(a, m)^(-1)</code>.



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K4</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, a&nbsp;liczby <math>a, b</math> będą względnie pierwsze z <math>p</math>. Jeżeli liczby <math>a, b</math> są różne modulo <math>p</math>, to ich elementy odwrotne <math>a^{-1}, b^{- 1}</math> też są różne modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia <math>a \not\equiv b \!\! \pmod{p}</math>. Gdyby było

::<math>a^{- 1} \equiv b^{- 1} \!\! \pmod{p}</math>

to mielibyśmy

::<math>a^{- 1} a b \equiv b^{- 1} a b \!\! \pmod{p}</math>

Czyli

::<math>b \equiv a \!\! \pmod{p}</math>

Wbrew uczynionemu założeniu. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}




<span style="font-size: 110%; font-weight: bold;">Twierdzenie K5</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, zbiór <math>R = \{ 1, 2, \ldots, p - 1 \}</math>, a&nbsp;zbiór <math>S</math> będzie identyczny ze zbiorem <math>R</math> modulo <math>p</math>. Jeżeli liczby <math>x_k \in S</math> przebiegają cały zbiór <math>S</math>, to liczby <math>x^{- 1}_k</math> przebiegają zbiór <math>T</math> identyczny ze zbiorem <math>R</math> modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia zbiory <math>R</math> i <math>S</math> są identyczne modulo <math>R</math>. Zatem każdej liczbie <math>k \in R</math> odpowiada dokładnie jedna liczba <math>x_k \in S</math> taka, że

::<math>x_k \equiv k \!\! \pmod{p}</math>

Ponieważ <math>\gcd (k, p) = 1</math>, to również <math>\gcd (x_k, p) = 1</math>. Zatem liczba <math>x_k</math> ma element odwrotny <math>x^{- 1}_k</math> modulo <math>p</math>. Ponieważ wszystkie liczby <math>x_k</math> są różne modulo <math>p</math>, to elementy odwrotne <math>x^{- 1}_k</math> też są wszystkie różne modulo <math>p</math>. Ponieważ liczb <math>x^{- 1}_k</math> jest dokładnie <math>p - 1</math>, to tworzą one pewien zbiór <math>T</math> identyczny ze zbiorem <math>R</math> modulo <math>p</math>. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K6</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą.

Jeżeli <math>a</math> jest liczbą kwadratową (odpowiednio niekwadratową) modulo <math>p</math>, to element odwrotny liczby <math>a</math> modulo <math>p</math> istnieje i&nbsp;jest liczbą kwadratową (odpowiednio niekwadratową) modulo <math>p</math>.

Jeżeli <math>a, b</math> są liczbami kwadratowymi (odpowiednio niekwadratowymi) modulo <math>p</math>, to istnieje taka liczba <math>r</math>, że <math>a \equiv b r^2 \!\! \pmod{p}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia <math>a</math> jest liczbą kwadratową (niekwadratową) modulo <math>p</math>, zatem <math>\gcd (a, p) = 1</math>, czyli element odwrotny liczby <math>a</math> modulo <math>p</math> istnieje. Mamy

::<math>1 = \left( {\small\frac{1}{p}} \right)_{\small{\!\! L}}
 = \left( {\small\frac{a a^{- 1}}{p}} \right)_{\small{\!\! L}}
 = \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \cdot \left( {\small\frac{a^{- 1}}{p}} \right)_{\small{\!\! L}}</math>

Zatem musi być 

::<math>\left( {\small\frac{a^{- 1}}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}}</math>

Co należało pokazać.


Niech <math>a, b</math> będą liczbami kwadratowymi (niekwadratowymi). Iloczyn <math>a b^{- 1}</math> jest liczbą kwadratową, bo

::<math>\left( {\small\frac{a b^{- 1}}{p}} \right)_{\small{\!\! L}}
 = \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \cdot \left( {\small\frac{b^{- 1}}{p}} \right)_{\small{\!\! L}}
 = \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \cdot \left( {\small\frac{b}{p}} \right)_{\small{\!\! L}}
 = \left( {\small\frac{\pm 1}{p}} \right)_{\small{\!\! L}} \cdot \left( {\small\frac{\pm 1}{p}} \right)_{\small{\!\! L}}
 = \left( {\small\frac{\pm 1}{p}} \right)_{\small{\!\! L}}^{\! 2}
 = 1</math>

Zatem istnieje taka liczba <math>r</math>, że

::<math>a b^{- 1} \equiv r^2 \!\! \pmod{p}</math>

Czyli

::<math>a \equiv b r^2 \!\! \pmod{p}</math>

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}





== Przykłady sum symboli Legendre'a ==

<span style="font-size: 110%; font-weight: bold;">Twierdzenie K7</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, <math>a, d \in \mathbb{Z}</math> i <math>p \nmid d</math>. Pokazać, że

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

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

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

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

'''Punkt 1.'''

Wystarczy zauważyć, że wśród liczb <math>1, 2, \ldots, p - 1</math> jest <math>{\small\frac{p - 1}{2}}</math> liczb kwadratowych modulo <math>p</math> i <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math>. Zatem

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

'''Punkt 2.'''

Wystarczy zauważyć, że

::<math>\left( {\small\frac{k^2}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}}^{\! 2}</math>

oraz że wśród liczb <math>1, 2, \ldots, p - 1</math> jest <math>{\small\frac{p - 1}{2}}</math> liczb kwadratowych modulo <math>p</math> i <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math>. Zatem

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

'''Punkt 3.'''

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

::<math>x_k = a + k d</math>

przez liczbę <math>p</math> są wszystkie różne i&nbsp;tworzą zbiór <math>S = \{ 0, 1, \ldots, p - 1 \}</math>. Czyli wśród reszt <math>r_1, r_2, \ldots, r_p</math> jest <math>{\small\frac{p - 1}{2}}</math> liczb kwadratowych modulo <math>p</math>, tyle samo liczb niekwadratowych modulo <math>p</math>, a&nbsp;jedna z&nbsp;tych reszt jest podzielna przez <math>p</math>. Z&nbsp;własności symbolu Legendre'a wiemy, że licznik wpływa na wartość symbolu jedynie modulo mianownik (zobacz J29 p. 2). Zatem możemy napisać

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

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K8</span><br/>
Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą i <math>a, b \in \mathbb{Z}</math>, to

::<math>\sum_{k = 0}^{p - 1} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + b}{p}} \right)_{\small{\!\! L}} 
 = \begin{cases}
 \;\;\:\,      - 1 & \text{gdy } \, p \nmid (a - b) \\
    p - 1 & \text{gdy } \, p \mid (a - b) \\
\end{cases}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

'''1. Przypadek, gdy <math>\boldsymbol{p \mid (a - b)}</math>'''

Z założenia <math>b \equiv a \!\! \pmod{p}</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}} 
 = \sum_{k = 0}^{p - 1} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}} 
 = \sum_{k = 0}^{p - 1} \left( {\small\frac{k + a}{p}} \right)_{\small{\!\! L}}^{\! 2}</math>

Z&nbsp;twierdzenia C55 wiemy, że reszty <math>r_1, r_2, \ldots, r_p</math> z&nbsp;dzielenia <math>p</math> kolejnych liczb postaci

::<math>x_k = a + k</math>

przez liczbę <math>p</math> są wszystkie różne i&nbsp;tworzą zbiór <math>S = \{ 0, 1, \ldots, p - 1 \}</math>. Czyli wśród reszt <math>r_1, r_2, \ldots, r_p</math> jest <math>{\small\frac{p - 1}{2}}</math> liczb kwadratowych modulo <math>p</math>, tyle samo liczb niekwadratowych modulo <math>p</math>, a&nbsp;jedna z&nbsp;tych reszt jest podzielna przez <math>p</math>. Z&nbsp;własności symbolu Legendre'a wiemy, że licznik wpływa na wartość symbolu jedynie modulo mianownik (zobacz J29 p. 2). Zatem możemy napisać

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

Co należało pokazać.

'''2. Przypadek, gdy <math>\boldsymbol{p \nmid (a - b)}</math>'''

Kładąc <math>j = k + a</math> i&nbsp;sumując od <math>a</math> do <math>p - 1 + a</math>, otrzymujemy

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

Wśród <math>p</math> kolejnych liczb <math>a, a + 1, \ldots, p - 1 + a</math> istnieje dokładnie jedna liczba podzielna przez <math>p</math>. Możemy ją pominąć, bo nie wnosi ona wkładu do wyliczanej sumy.

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

::::::::<math>\;\;\, = \underset{p \nmid j}{\sum_{j = a}^{p - 1 + a}} \left( {\small\frac{j}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{j + (b - a) j j^{- 1}}{p}} \right)_{\small{\!\! L}}</math>

::::::::<math>\;\;\, = \underset{p \nmid j}{\sum_{j = a}^{p - 1 + a}} \left( {\small\frac{j^2}{p}} \right)_{\small{\!\! L}} \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. Wiemy też, że gdy liczby <math>j</math> przebiegają zbiór identyczny (modulo <math>p</math>) ze zbiorem <math>R = \{ 1, 2, \ldots, p - 1 \}</math>, to liczby <math>j^{- 1}</math> przebiegają pewien zbiór <math>S</math> identyczny (modulo <math>p</math>) ze zbiorem <math>R</math> (zobacz K5). 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}} 
 = \sum_{r = 1}^{p - 1} \left( {\small\frac{1 + (b - a) r}{p}} \right)_{\small{\!\! L}}</math>

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

::::::::<math>\;\;\, = - 1</math>

Ostatnia z&nbsp;wypisanych sum jest równa zero, co wynika z&nbsp;trzeciego wzoru twierdzenia K7 i&nbsp;faktu, że <math>p \nmid (b - a)</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K9</span><br/>
Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą i <math>n \in \mathbb{Z}</math>, to

::<math>\sum_{k = 0}^{p - 1} \left( {\small\frac{k^2 + n}{p}} \right)_{\small{\!\! L}} =
\begin{cases}
 \;\;\:\,      - 1 & \text{gdy } \, p \nmid n \\
    p - 1 & \text{gdy } \, p \mid n \\
\end{cases}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

'''Przypadek, gdy <math>\boldsymbol{p \mid n}</math>

Z drugiego wzoru twierdzenia K7 otrzymujemy

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

'''Przypadek, gdy <math>\boldsymbol{p \nmid n}</math>

Jeżeli liczby <math>a, b</math> są obie liczbami kwadratowymi lub obie liczbami niekwadratowymi modulo <math>p</math>, to istnieje taka liczba <math>r</math>, że

::<math>a \equiv b r^2 \!\! \pmod{p}</math>

(zobacz K6). Zatem 

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

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

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

:::<math>\;\;\; = \left( {\small\frac{r^2}{p}} \right)_{\small{\!\! L}} \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 C55 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>


Wynika stąd, że dla wszystkich liczb kwadratowych (odpowiednio niekwadratowych) modulo <math>p</math> wyrażenie <math>S(n)</math> ma taką samą wartość i&nbsp;jeśli wybierzemy liczby <math>a, b</math> tak, aby jedna była liczbą kwadratową, a&nbsp;druga liczbą niekwadratową modulo <math>p</math>, to możemy napisać

::<math>\sum_{n = 1}^{p - 1} S (n) = {\small\frac{p - 1}{2}} (S (a) + S (b))</math>


Z drugiej strony

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

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

::::<math>\;\;\;\: = \sum_{k = 0}^{p - 1} \left[ - \left( {\small\frac{k^2}{p}} \right)_{\small{\!\! L}} + \sum_{n = 0}^{p - 1} \left( {\small\frac{k^2 + n}{p}} \right)_{\small{\!\! L}} \right]</math>

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

::::<math>\;\;\;\: = - (p - 1)</math>

bo z&nbsp;twierdzenia K7 wiemy, że

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


Łącząc uzyskane rezultaty, dostajemy

::<math>- (p - 1) = {\small\frac{p - 1}{2}} (S (a) + S (b))</math>

Zatem

::<math>S(a) + S (b) = - 2</math>


Z twierdzenia K8 mamy

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

bo <math>p \nmid 2</math>. Dla ustalenia uwagi przyjmijmy, że <math>a</math> jest liczbą kwadratową, a <math>b</math> jest liczbą niekwadratową modulo <math>p</math>. Jeżeli <math>- 1</math> jest liczbą kwadratową modulo <math>p</math>, to <math>S(a) = - 1</math> i&nbsp;natychmiast otrzymujemy, że <math>S(b) = - 1</math>. Jeżeli <math>- 1</math> jest liczbą niekwadratową modulo <math>p</math>, to <math>S(b) = - 1</math> i&nbsp;natychmiast otrzymujemy, że <math>S(a) = - 1</math>. Zatem bez względu na to, czy <math>n</math> jest liczbą kwadratową, czy liczbą niekwadratową modulo <math>p</math>, musi być <math>S(n) = - 1</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie K10</span><br/>
Pokazać, że jeżeli <math>p</math> jest liczbą pierwszą nieparzystą i <math>r , s \in \mathbb{Z}</math>, to

::<math>\sum_{k = 0}^{p - 1} \left( {\small\frac{k^2 + r k + s}{p}} \right)_{\small{\!\! L}} =
\begin{cases}
 \;\;\:\,      - 1 & \text{gdy } \, p \nmid (r^2 - 4 s) \\
    p - 1 & \text{gdy } \, p \mid (r^2 - 4 s) \\
\end{cases}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}

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

:::::::<math>\;\;\;\, = \sum_{k = 0}^{p - 1} \left( {\small\frac{4 k^2 + 4 r k + 4 s}{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 C55 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>

Z twierdzenia K9 wynika natychmiast teza dowodzonego twierdzenia.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K11</span><br/>
Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą i <math>p \nmid n</math>, to dla sumy

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

prawdziwe są następujące wzory

::(a) <math>\;\; S(n) = 0 \qquad \qquad \text{gdy } \; p = 4 k + 3</math>

::(b) <math>\;\; | S (n) | < 2 \sqrt{p} \qquad \text{gdy } \; p = 4 k + 1</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

'''Punkt (a)'''

Zauważmy, że zbiory <math>R = \{ 0, 1, 2, \ldots, p - 1 \}</math> oraz <math>T = \{ - p + 1, - p + 2, \ldots, - p + (p - 1), 0 \}</math> są identyczne modulo <math>p</math>. Z&nbsp;własności symbolu Legendre'a wiemy, że licznik wpływa na wartość symbolu jedynie modulo mianownik (zobacz J29 p.2). Zatem możemy sumowanie po <math>k \in R</math> zastąpić sumowaniem po <math>j \in T .</math> Otrzymujemy

::<math>S(n) = \sum_{j = - p + 1}^{0} \left( {\small\frac{j (j^2 + n)}{p}} \right)_{\small{\!\! L}}</math>

Kładąc <math>j = - r</math> i&nbsp;sumując po <math>r</math> od <math>0</math> do <math>p - 1</math>, dostajemy

::<math>S(n) = \sum_{r = 0}^{p - 1} \left( {\small\frac{- r}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{(- r)^2 + n}{p}} \right)_{\small{\!\! L}} 
 = \sum_{r = 0}^{p - 1} \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{r}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{r^2 + n}{p}} \right)_{\small{\!\! L}}  
 = \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} S (n)</math>

Jeżeli <math>p = 4 k + 3</math>, to <math>S (n) = - S (n)</math>, czyli <math>S(n) = 0</math>.

'''Punkt (b)'''

Pomysł dowodu zaczerpnęliśmy z materiałów szkoleniowych Międzynarodowej Olimpiady Matematycznej<ref name="Dukic1"/>.

Jeżeli liczby <math>a, b</math> są obie liczbami kwadratowymi lub obie liczbami niekwadratowymi modulo <math>p</math>, to istnieje taka liczba <math>r</math>, że

::<math>a \equiv b r^2 \!\! \pmod{p}</math>

(zobacz K6). Zatem

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

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

::::::<math>\;\:\, = \left( {\small\frac{r^3}{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 C55 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>

Czyli <math>S (a)^2 = S (b)^2</math>. Wynika stąd, że dla wszystkich liczb kwadratowych (odpowiednio niekwadratowych) modulo <math>p</math> wyrażenie <math>S (n)^2</math> ma taką samą wartość i&nbsp;jeśli wybierzemy liczby <math>a, b</math> tak, aby jedna była liczbą kwadratową, a&nbsp;druga liczbą niekwadratową modulo <math>p</math>, to prawdziwa jest równość

::<math>\sum_{n = 1}^{p - 1} S (n)^2 = {\small\frac{p - 1}{2}} (S (a)^2 + S (b)^2)</math>

Jak łatwo zauważyć <math>S(0) = 0</math>, zatem możemy napisać

::<math>\sum_{n = 0}^{p - 1} S (n)^2 = {\small\frac{p - 1}{2}} (S (a)^2 + S (b)^2)</math>

Z drugiej strony

::<math>S (n)^2 = \sum_{k = 1}^{p - 1} \left( {\small\frac{k (k^2 + n)}{p}} \right)_{\small{\!\! L}} \sum^{p - 1}_{j = 1} \left( {\small\frac{j (j^2 + n)}{p}} \right)_{\small{\!\! L}}</math>

:::<math>\quad \,\, = \sum_{k = 1}^{p - 1} \sum_{j = 1}^{p - 1} \left( {\small\frac{k (k^2 + n)}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{j (j^2 + n)}{p}} \right)_{\small{\!\! L}}</math>

:::<math>\quad \,\, = \sum_{k = 1}^{p - 1} \sum_{j = 1}^{p - 1} \left( {\small\frac{k j (k^2 + n) (j^2 + n)}{p}} \right)_{\small{\!\! L}}</math>

Zatem

::<math>\sum_{n = 0}^{p - 1} S (n)^2 = \sum_{n = 0}^{p - 1} \sum_{k = 1}^{p - 1} \sum_{j = 1}^{p - 1} \left( {\small\frac{k j (k^2 + n) (j^2 + n)}{p}} \right)_{\small{\!\! L}}</math>

:::::<math>\;\! = \sum_{k = 1}^{p - 1} \sum_{j = 1}^{p - 1} \left( {\small\frac{k j}{p}} \right)_{\small{\!\! L}} \sum_{n = 0}^{p - 1} \left( {\small\frac{(n + k^2) (n + j^2)}{p}} \right)_{\small{\!\! L}}</math>


Z twierdzenia K8 wiemy, że

::<math>\sum_{n = 0}^{p - 1} \left( {\small\frac{(n + k^2) (n + j^2)}{p}} \right)_{\small{\!\! L}} =
\begin{cases}
 \;\;\:\,      - 1 & \text{gdy } \, p \nmid (k^2 - j^2) \\
    p - 1 & \text{gdy } \, p \mid (k^2 - j^2) \\
\end{cases}</math>


Zbadajmy, kiedy <math>p \mid (k^2 - j^2)</math>, czyli kiedy <math>p \mid [(k - j) (k + j)]</math>. Mamy

::* <math>\; 0 \leqslant | k - j | \leqslant p - 2</math>

::* <math>\; 2 \leqslant k + j \leqslant 2 p - 2</math>

Zatem <math>p \mid [(k - j) (k + j)]</math> gdy

::* <math>\; j = k</math>

::* <math>\; j = p - k</math>


Pozwala to zapisać rozpatrywaną sumę w&nbsp;postaci

::<math>\sum_{n = 0}^{p - 1} S (n)^2 = \sum_{k = 1}^{p - 1} \sum_{j = 1}^{p - 1} \left( {\small\frac{k j}{p}} \right)_{\small{\!\! L}} \cdot 
\left\{ \begin{array}{rll}
  - 1   & \text{gdy } \; j \neq k \;\;\;\; \text{ i } \;\;\;\; j \neq p - k \\
  p - 1 & \text{gdy } \; j = k \;\; \text{ lub } \;\; j = p - k \\
\end{array} \right\}</math>

<div style="margin-top: 1em; margin-bottom: 1em;">
:::::<math>\:\! = (p - 1) \underset{j = k \; \text{ lub } \; j = p - k}{\sum^{p - 1}_{k = 1} \sum_{j = 1}^{p - 1}} \left( {\small\frac{k j}{p}} \right)_{\small{\!\! L}} - \underset{j \neq k \; \text{ i } \; j \neq p - k}{\sum_{k = 1}^{p - 1} \sum_{j = 1}^{p - 1}} \left( {\small\frac{k j}{p}} \right)_{\small{\!\! L}}</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
:::::<math>\:\! = (p - 1) \left[ \sum_{k = 1}^{p - 1} \left( {\small\frac{k^2}{p}} \right)_{\small{\!\! L}} + \sum_{k = 1}^{p - 1} \left( {\small\frac{k (p - k)}{p}} \right)_{\small{\!\! L}} \right] - \sum_{k = 1}^{p - 1} \sum_{j = 1}^{p - 1} \left( {\small\frac{k j}{p}} \right)_{\small{\!\! L}} + \underset{j = k \; \text{ lub } \; j = p - k}{\sum_{k = 1}^{p - 1} \sum_{j = 1}^{p - 1}} \left( {\small\frac{k j}{p}} \right)_{\small{\!\! L}}</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
:::::<math>\:\! = (p - 1) \left[ (p - 1) + \sum_{k = 1}^{p - 1} \left( {\small\frac{- k^2}{p}} \right)_{\small{\!\! L}} \right] - \sum_{k = 1}^{p - 1} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \sum^{p - 1}_{j = 1} \left( {\small\frac{j}{p}} \right)_{\small{\!\! L}} + \sum_{k = 1}^{p - 1} \left( {\small\frac{k^2}{p}} \right)_{\small{\!\! L}} + \sum_{k = 1}^{p - 1} \left( {\small\frac{k (p - k)}{p}} \right)_{\small{\!\! L}}</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
:::::<math>\:\! = (p - 1) \left[ (p - 1) + \left( {\small\frac{-1}{p}} \right)_{\small{\!\! L}} \sum_{k = 1}^{p - 1} \left( {\small\frac{k^2}{p}} \right)_{\small{\!\! L}} \right] + (p - 1) + \sum_{k = 1}^{p - 1} \left( {\small\frac{- k^2}{p}} \right)_{\small{\!\! L}}</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
:::::<math>\:\! = (p - 1) \cdot 2 (p - 1) + (p - 1) + (p - 1)</math>
</div>

:::::<math>\:\! = 2 p (p - 1)</math>

Zauważmy, że <math>\left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} = 1</math>, bo <math>p = 4 k + 1</math>.


Ponieważ wcześniej pokazaliśmy, że

::<math>\sum_{n = 0}^{p - 1} S (n)^2 = {\small\frac{p - 1}{2}} (S (a)^2 + S (b)^2)</math>

to otrzymujemy

::<math>{\small\frac{p - 1}{2}} (S (a)^2 + S (b)^2) = 2 p (p - 1)</math>

Czyli

::<math>S (a)^2 + S (b)^2 = 4 p</math>

Wynika stąd, że bez względu na to, czy <math>n</math> jest liczbą kwadratową, czy liczbą niekwadratową modulo <math>p</math>, prawdziwe jest oszacowanie

::<math>| S (n) | \leqslant 2 \sqrt{p}</math>

Równość <math>S (n)^2 = 4 p</math> nie jest możliwa, bo dzielnik pierwszy <math>p</math> występuje po prawej stronie w&nbsp;potędze nieparzystej. Zatem mamy nieco silniejsze oszacowanie

::<math>| S (n) | < 2 \sqrt{p}</math>

Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie K12</span><br/>
Pokazać, że jeżeli <math>p \geqslant 7</math> jest liczbą pierwszą, to wśród liczb <math>1, 2, \ldots, p - 1</math> istnieją:

:* dwie kolejne liczby będące liczbami kwadratowymi modulo <math>p</math>
:* dwie kolejne liczby będące liczbami niekwadratowymi modulo <math>p</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Dla <math>p = 7</math> łatwo sprawdzamy, że twierdzenie jest prawdziwe.

'''Punkt 1.'''

Zauważmy, że przynajmniej jedna z&nbsp;liczb <math>2, 5, 10</math> jest liczbą kwadratową. Zakładając, że tak nie jest, otrzymujemy natychmiast sprzeczność

::<math> -1 = \left( {\small\frac{10}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} \cdot \left( {\small\frac{5}{p}} \right)_{\small{\!\! L}} = (- 1) \cdot (- 1) = 1</math>

W zależności od tego, która z&nbsp;liczb <math>2, 5, 10</math> jest liczbą kwadratową, mamy następujące pary kolejnych liczb kwadratowych

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
| <math>2</math> || <math>1, 2 \; \text{ oraz } \; 8, 9</math>
|-
| <math>5</math> || <math>4, 5</math>
|-
| <math>10</math> || <math>9, 10</math>
|}

'''Punkt 2.'''

Rozważmy wszystkie możliwe wartości <math>\left( {\small\frac{k}{p}} \right)_{\small{\!\! L}}</math> dla <math>k = 1, 2, 3, 4</math> i <math>p \geqslant 11</math>. Zauważmy, że <math>\left( {\small\frac{6}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! L}}</math>.

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{k}</math> || <math>\,\, \boldsymbol{1} \,\,</math> || <math>\boldsymbol{2}</math> || <math>\boldsymbol{3}</math> || <math>\,\, \boldsymbol{4} \,\,</math> || <math>\,\, \boldsymbol{5} \,\,</math> || <math>\boldsymbol{6}</math> || <math>\boldsymbol{(…)}</math> || <math>\boldsymbol{p-1}</math>
|-
! <math>\boldsymbol{A.}</math> 
| <math>1</math> || <math>1</math> || <math>1</math> || <math>1</math> || <math></math> || <math>1</math> || <math></math> || <math></math>
|-
! <math>\boldsymbol{B.}</math> 
| <math>1</math> || <math>1</math> || <math>-1</math> || <math>1</math> || <math></math> || <math>-1</math> || <math></math> || <math></math>
|-
! <math>\boldsymbol{C.}</math> 
| <math>1</math> || <math>-1</math> || <math>1</math> || <math>1</math> || <math></math> || <math>-1</math> || <math></math> || <math></math>
|-
! <math>\boldsymbol{D.}</math> 
| <math>1</math> || <math>-1</math> || <math>-1</math> || <math>1</math> || <math></math> || <math>1</math> || <math></math> || <math></math>
|}

'''A.''' W&nbsp;tym przypadku liczby <math>2, 3</math> są liczbami kwadratowymi modulo <math>p</math>. Gdyby w&nbsp;pozostałych komórkach miało nie być ani jednej pary kolejnych liczb niekwadratowych modulo <math>p</math>, to musielibyśmy <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych umieścić wśród pozostałych <math>p - 5</math> komórek tak, aby między nimi zawsze była liczba kwadratowa modulo <math>p</math>. Wartość <math>\left( {\small\frac{6}{p}} \right)_{\small{\!\! L}}</math> wymusza, aby liczby niekwadratowe modulo <math>p</math> umieszczać w&nbsp;komórkach „nieparzystych”. Po wypełnieniu tych komórek pozostaną nam dwie liczby, które będziemy zmuszeni umieścić w&nbsp;komórkach „parzystych”. Co oznacza, że muszą pojawić się dwie pary kolejnych liczb niekwadratowych modulo <math>p</math>.

'''B. i&nbsp;C.''' W&nbsp;tym przypadku dokładnie jedna z&nbsp;liczb <math>2, 3</math> jest liczbą kwadratową modulo <math>p</math>. Gdyby w&nbsp;pozostałych komórkach miało nie być ani jednej pary kolejnych liczb niekwadratowych modulo <math>p</math>, to musielibyśmy <math>{\small\frac{p - 3}{2}}</math> liczb niekwadratowych umieścić wśród pozostałych <math>p - 5</math> komórek tak, aby między nimi zawsze była liczba kwadratowa modulo <math>p</math>. Wartość <math>\left( {\small\frac{6}{p}} \right)_{\small{\!\! L}}</math> wymusza, aby liczby niekwadratowe modulo <math>p</math> umieszczać w&nbsp;komórkach „parzystych”. Po wypełnieniu tych komórek pozostanie nam jedna liczba, którą będziemy zmuszeni umieścić w&nbsp;komórce „nieparzystej”. Co oznacza, że musi pojawić się jedna para kolejnych liczb niekwadratowych modulo <math>p</math>.

'''D.''' W&nbsp;tym przypadku nie musimy niczego dowodzić, bo liczby <math>2, 3</math> są kolejnymi liczbami niekwadratowymi modulo <math>p</math>.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga K13</span><br/>
Wzmocnimy wynik uzyskany w&nbsp;poprzednim zadaniu. Zauważmy, jak użycie symbolu Legendre'a pozwala sformalizować problem.



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K14</span><br/>
Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą, to

:* istnieje <math>\left\lfloor {\small\frac{p - 3}{4}} \right\rfloor</math> różnych par kolejnych liczb kwadratowych modulo <math>p</math>
:* istnieje <math>\left\lfloor {\small\frac{p - 1}{4}} \right\rfloor</math> różnych par kolejnych liczb niekwadratowych modulo <math>p</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

'''Punkt 1.'''

Chcemy znaleźć ilość takich liczb <math>k \in \{ 1, 2, \ldots, p - 2 \}</math>, dla których

::<math>\left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} = 1</math>

Ilość liczb <math>k</math> spełniających powyższy warunek łatwo zapisać korzystając z&nbsp;symbolu Legendre'a

::<math>N = {\small\frac{1}{4}} \sum_{k = 1}^{p - 2} \left[ 1 + \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \right] \left[ 1 + \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} \right]</math>

Tylko w&nbsp;przypadku, gdy obie liczby <math>k</math> i <math>k + 1</math> są liczbami kwadratowymi modulo <math>p</math>, iloczyn wyrażeń w&nbsp;nawiasach kwadratowych jest różny od zera i&nbsp;równy <math>4</math> (stąd czynnik <math>{\small\frac{1}{4}}</math> przed sumą).

::<math>4 N = \sum_{k = 1}^{p - 2} \left[ 1 + \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} + \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} + \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} \right]</math>

<div style="margin-top: 1em; margin-bottom: 1em;">
:::<math>\: = p - 2 + \sum_{k = 1}^{p - 2} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} + \sum_{k = 1}^{p - 2} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} + \sum_{k = 1}^{p - 2} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}}</math>
</div>

Po kolei wyliczamy sumy po prawej stronie

<div style="margin-top: 0em; margin-bottom: 1em;">
::<math>\sum_{k = 1}^{p - 2} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} 
 = - \left( {\small\frac{p - 1}{p}} \right)_{\small{\!\! L}} + \sum_{k = 1}^{p - 1} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} 
 = - \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}}</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\sum_{k = 1}^{p - 2} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
 = - \left( {\small\frac{1}{p}} \right)_{\small{\!\! L}} + \sum^{p - 1}_{k = 0} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
 = - 1</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\sum_{k = 1}^{p - 2} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
 = \sum_{k = 0}^{p - 1} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
 = - 1</math>
</div>

(zobacz K7 i&nbsp;K8). Zatem

::<math>N = {\small\frac{1}{4}} \left[ p - 4 - \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} \right]</math>

Czyli

::<math>N = 
\begin{cases}
  {\large\frac{p - 5}{4}} & \text{ gdy } \; p = 4 k + 1 \\
  {\large\frac{p - 3}{4}} & \text{ gdy } \; p = 4 k + 3 \\
\end{cases}</math>

Powyższy wynik można zapisać w&nbsp;postaci

::<math>N = \left\lfloor {\small\frac{p - 3}{4}} \right\rfloor</math>

'''Punkt 2.'''

Chcemy znaleźć ilość takich liczb <math>k \in \{ 1, 2, \ldots, p - 2 \}</math>, dla których

::<math>\left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} = - 1</math>

Ilość liczb <math>k</math> spełniających powyższy warunek łatwo zapisać korzystając z&nbsp;symbolu Legendre'a

::<math>N = {\small\frac{1}{4}} \sum_{k = 1}^{p - 2} \left[ - 1 + \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \right] \left[ - 1 + \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} \right]</math>

Tylko w&nbsp;przypadku, gdy obie liczby <math>k</math> i <math>k + 1</math> są liczbami niekwadratowymi modulo <math>p</math>, iloczyn wyrażeń w&nbsp;nawiasach kwadratowych jest różny od zera i&nbsp;równy <math>4</math> (stąd czynnik <math>{\small\frac{1}{4}}</math> przed sumą).

::<math>4 N = \sum_{k = 1}^{p - 2} \left[ 1 - \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} - \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} + \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} \right]</math>

<div style="margin-top: 1em; margin-bottom: 1em;">
:::<math>\: = p - 2 - \sum_{k = 1}^{p - 2} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} - \sum_{k = 1}^{p - 2} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} + \sum_{k = 1}^{p - 2} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}}</math>
</div>

Wartości sum wyliczyliśmy już w&nbsp;punkcie 1. Zatem

::<math>N = {\small\frac{1}{4}} \left[ p - 2 + \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} \right]</math>

Czyli

::<math>N = 
\begin{cases}
  {\large\frac{p - 1}{4}} & \text{ gdy } \; p = 4 k + 1 \\
  {\large\frac{p - 3}{4}} & \text{ gdy } \; p = 4 k + 3 \\
\end{cases}</math>

Powyższy wynik można zapisać w&nbsp;postaci

::<math>N = \left\lfloor {\small\frac{p - 1}{4}} \right\rfloor</math>

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K15</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Słowo „trójka” oznacza tutaj trzy kolejne liczby kwadratowe (niekwadratowe) modulo <math>p</math>.

Jeżeli <math>p = 4 k + 3</math>, to liczba różnych trójek liczb kwadratowych (niekwadratowych) jest równa

::<math>N = \left\lfloor {\small\frac{p - 3}{8}} \right\rfloor</math>

Jeżeli <math>p = 4 k + 1</math>, to liczba różnych trójek liczb niekwadratowych jest równa

::<math>N = {\small\frac{p - 3 - S (- 1)}{8}} > {\small\frac{p - 3 - 2 \sqrt{p}}{8}}</math>

Jeżeli <math>p = 4 k + 1</math>, to liczba różnych trójek liczb kwadratowych jest równa

::<math>N = {\small\frac{p - 15 + S (- 1)}{8}} > {\small\frac{p - 15 - 2 \sqrt{p}}{8}} \qquad \quad \text{ gdy } \; p = 8 k + 1</math>

::<math>N = {\small\frac{p - 7 + S (- 1)}{8}} > {\small\frac{p - 7 - 2 \sqrt{p}}{8}} \qquad \quad \;\;\; \text{ gdy } \; p = 8 k + 5</math>

Gdzie przez <math>S(- 1)</math> oznaczyliśmy sumę

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

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

'''Przypadek pierwszy: trójki liczb kwadratowych modulo''' <math>\boldsymbol{p}</math>

Chcemy znaleźć ilość takich liczb <math>k \in \{ 2, 3, \ldots, p - 2 \}</math>, dla których

::<math>\left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} = + 1</math>

Ilość liczb <math>k</math> spełniających powyższy warunek łatwo zapisać korzystając z&nbsp;symbolu Legendre'a

::<math>N = {\small\frac{1}{8}} \sum_{k = 2}^{p - 2} \left[ 1 + \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} \right] \left[ 1 + \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \right] \left[ 1 + \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} \right]</math>

Tylko w&nbsp;przypadku, gdy wszystkie trzy liczby <math>k - 1, k, k + 1</math> są liczbami kwadratowymi modulo <math>p</math>, iloczyn wyrażeń w&nbsp;nawiasach kwadratowych jest różny od zera i&nbsp;równy <math>8</math> (stąd czynnik <math>{\small\frac{1}{8}}</math> przed sumą).

::<math>8 N = \sum_{k = 2}^{p - 2} \left[ 1 
+ \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} 
+ \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} 
+ \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
+ \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} 
+ \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
+ \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
+ \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}}
\right]</math>

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


Po kolei wyliczamy sumy po prawej stronie 

::<math>\sum_{k = 2}^{p - 2} \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} = - \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} - \left( {\small\frac{- 2}{p}} \right)_{\small{\!\! L}}</math>

::<math>\sum_{k = 2}^{p - 2} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} = - 1 - \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}}</math>

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


::<math>\sum_{k = 2}^{p - 2} \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} = - 1 - \left( {\small\frac{2}{p}} \right)_{\small{\!\! L}}</math>

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

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


::<math>\sum_{k = 2}^{p - 2} \left( {\small\frac{k (k^2 - 1)}{p}} \right)_{\small{\!\! L}} = \sum^{p - 1}_{k = 0} \left( {\small\frac{k (k^2 - 1)}{p}} \right)_{\small{\!\! L}} = S (- 1)</math>


(zobacz K7, K8 i K11). Oznaczenie <math>S(- 1)</math> nawiązuje do oznaczenia wprowadzonego w&nbsp;twierdzeniu K11. Wykorzystamy też znalezione w&nbsp;tym twierdzeniu oszacowanie <math>| S (- 1) |</math>.

Zatem

::<math>8 N = p - 8 - 3 \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} - 3 \left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} - \left( {\small\frac{- 2}{p}} \right)_{\small{\!\! L}} + S (- 1)</math>

Jeżeli <math>p = 8 k + 1</math>

::<math>N = {\small\frac{p - 15 + S (- 1)}{8}} > {\small\frac{p - 15 - 2 \sqrt{p}}{8}}</math>

Jeżeli <math>p = 8 k + 3</math>

::<math>N = {\small\frac{p - 3}{8}}</math>

Jeżeli <math>p = 8 k + 5</math>

::<math>N = {\small\frac{p - 7 + S (- 1)}{8}} > {\small\frac{p - 7 - 2 \sqrt{p}}{8}}</math>

Jeżeli <math>p = 8 k + 7</math>

::<math>N = {\small\frac{p - 7}{8}}</math>


'''Przypadek drugi: trójki liczb niekwadratowych modulo''' <math>\boldsymbol{p}</math>

Chcemy znaleźć ilość takich liczb <math>k \in \{ 2, 3, \ldots, p - 2 \}</math>, dla których

::<math>\left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} = - 1</math>

Ilość liczb <math>k</math> spełniających powyższy warunek łatwo zapisać korzystając z&nbsp;symbolu Legendre'a

::<math>N = - {\small\frac{1}{8}} \sum_{k = 2}^{p - 2} \left[ - 1 + \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} \right] \left[ - 1 + \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \right] \left[ - 1 + \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} \right]</math>

Tylko w&nbsp;przypadku, gdy wszystkie trzy liczby <math>k - 1, k, k + 1</math> są liczbami niekwadratowymi modulo <math>p</math>, iloczyn wyrażeń w&nbsp;nawiasach kwadratowych jest różny od zera i&nbsp;równy <math>- 8</math> (stąd czynnik <math>- {\small\frac{1}{8}}</math> przed sumą).

::<math>8 N = \sum_{k = 2}^{p - 2} \left[ 1 
- \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} 
- \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} 
- \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
+ \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} 
+ \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
+ \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}} 
- \left( {\small\frac{k - 1}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k}{p}} \right)_{\small{\!\! L}} \left( {\small\frac{k + 1}{p}} \right)_{\small{\!\! L}}
\right]</math>

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


Wartości sum już policzyliśmy, rozpatrując przypadek liczb kwadratowych modulo <math>p</math>. Zatem

::<math>8 N = p - 4 + \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} - \left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} + \left( {\small\frac{- 2}{p}} \right)_{\small{\!\! L}} - S (- 1)</math>


Jeżeli <math>p = 8 k + 1</math>

::<math>N = {\small\frac{p - 3 - S (- 1)}{8}} > {\small\frac{p - 3 - 2 \sqrt{p}}{8}}</math>

Jeżeli <math>p = 8 k + 3</math>

::<math>N = {\small\frac{p - 3}{8}}</math>

Jeżeli <math>p = 8 k + 5</math>

::<math>N = {\small\frac{p - 3 - S (- 1)}{8}} > {\small\frac{p - 3 - 2 \sqrt{p}}{8}}</math>

Jeżeli <math>p = 8 k + 7</math>

::<math>N = {\small\frac{p - 7}{8}}</math>

Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga K16</span><br/>
Korzystając z&nbsp;twierdzenia K15, łatwo można pokazać, że każda liczba pierwsza <math>p \geqslant 19</math> ma co najmniej dwie różne trójki kolejnych liczb kwadratowych modulo <math>p</math> i&nbsp;co najmniej dwie różne trójki kolejnych liczb niekwadratowych modulo <math>p</math>.





== Najmniejsze liczby niekwadratowe modulo ==

<span style="font-size: 110%; font-weight: bold;">Uwaga K17</span><br/>
Najmniejsze liczby niekwadratowe modulo przedstawiamy Czytelnikowi jedynie jako pewną ciekawostkę. Jednocześnie jest to nietrudny temat, który pozwala lepiej poznać i&nbsp;zrozumieć liczby kwadratowe modulo, liczby niekwadratowe modulo, symbol Legendre'a i&nbsp;symbol Jacobiego.




{| style="border-spacing: 5px; border: 2px solid black; background: transparent;"
| &nbsp;'''A.''' Najmniejsze liczby niekwadratowe modulo <math>p</math>&nbsp;
|}

<span style="font-size: 110%; font-weight: bold;">Przykład K18</span><br/>
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math>

::{| class="wikitable plainlinks"  style="font-size: 100%; text-align: center; margin-right: auto;"
! <math>\boldsymbol{m}</math> 
| <math>3</math> || <math>5</math> || <math>7</math> || <math>9</math> || <math>11</math> || <math>13</math> || <math>15</math> || <math>17</math> || <math>19</math> || <math>21</math> || <math>23</math> || <math>25</math> || <math>27</math> || <math>29</math> || <math>31</math> || <math>33</math> || <math>35</math> || <math>37</math> || <math>39</math> || <math>41</math> || <math>43</math> || <math>45</math> || <math>47</math> || <math>49</math> || <math>51</math>
|-
!  <math>\boldsymbol{\mathbb{n}( p )}</math> 
| <math>2</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math>
|}



<span style="font-size: 110%; font-weight: bold;">Uwaga K19</span><br/>
Do wyszukiwania liczb <math>\mathbb{n} = \mathbb{n} (p)</math> Czytelnik może wykorzystać prostą funkcję napisaną w&nbsp;PARI/GP

 <span style="font-size: 90%; color:black;">A(p) = 
 {
 '''if'''( p == 2, '''return'''(0) );
 '''if'''( !'''isprime'''(p), '''return'''(0) );
 '''forprime'''(q = 2, p, '''if'''( jacobi(q, p) == -1, '''return'''(q) ));
 }</span>

Zauważmy, że choć wyliczamy symbol Jacobiego, to jest to w&nbsp;rzeczywistości symbol Legendre'a, '''bo wiemy''', że liczba <math>p</math> jest liczbą pierwszą (w przypadku, gdy <math>p</math> jest liczbą złożoną, funkcja zwraca zero).



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K20</span><br/>
Niech <math>\mathbb{n} \in \mathbb{Z}_+</math> i&nbsp;niech <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli <math>\mathbb{n}</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>, to jest liczbą pierwszą.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Przypuśćmy, że <math>\mathbb{n} = a b</math> jest liczbą złożoną, gdzie <math>1 < a, b < \mathbb{n}</math>. Z&nbsp;założenia <math>\mathbb{n}</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>, zatem liczby <math>a, b</math> są liczbami kwadratowymi modulo <math>p</math>. Z&nbsp;definicji liczb kwadratowych muszą istnieć takie liczby <math>r, s</math>, że

::<math>r^2 \equiv a \pmod{p}</math>

::<math>s^2 \equiv b \pmod{p}</math>

Skąd wynika, że

::<math>\mathbb{n} = a b \equiv (r s)^2 \pmod{p}</math>

Wbrew założeniu, że <math>\mathbb{n}</math> jest liczbą niekwadratową modulo <math>p</math>.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie K21</span><br/>
Pokazać, że najmniejszą liczbą niekwadratową modulo <math>p</math> jest

:* &nbsp;liczba <math>2</math> wtedy i&nbsp;tylko wtedy, gdy <math>p = 8 k \pm 3</math>
:* &nbsp;liczba <math>3</math> wtedy i&nbsp;tylko wtedy, gdy <math>p = 24 k \pm 7</math>
:* &nbsp;liczba <math>\geqslant 5</math> wtedy i&nbsp;tylko wtedy, gdy <math>p = 24 k \pm 1</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Z właściwości symbolu Legendre'a (zobacz J29 p.7) wiemy, że 

::<math>\left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} \,\, = 
 \,\, 
  \begin{cases}
 \;\;\: 1 & \text{gdy } p \equiv 1, 7 \pmod{8} \\
      - 1 & \text{gdy } p \equiv 3, 5 \pmod{8} 
  \end{cases}</math>

Wynika stąd natychmiast, dla liczb pierwszych <math>p</math> postaci <math>8 k \pm 3</math> (i tylko dla takich liczb) liczba <math>2</math> jest liczbą niekwadratową, czyli również najmniejszą liczbą niekwadratową modulo <math>p</math>.

Z zadania J41 wynika, że liczba <math>3</math> jest liczbą niekwadratową jedynie dla liczb pierwszych postaci <math>12 k \pm 5</math>. Zatem dla liczb pierwszych, które są jednocześnie postaci <math>p = 8 k \pm 1</math> i <math>p = 12 j \pm 5</math>, liczba <math>3</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>. Z&nbsp;czterech warunków

::<math>p = 8 k + 1 \quad \text{i} \quad p = 12 j + 5</math>

::<math>p = 8 k + 1 \quad \text{i} \quad p = 12 j + 7</math>

::<math>p = 8 k + 7 \quad \text{i} \quad p = 12 j + 5</math>

::<math>p = 8 k + 7 \quad \text{i} \quad p = 12 j + 7</math>

Drugi i&nbsp;trzeci nie są możliwe, bo modulo <math>4</math> otrzymujemy

::<math>p \equiv 1 \pmod{4} \quad \text{i} \quad p \equiv 3 \pmod{4}</math>

::<math>p \equiv 3 \pmod{4} \quad \text{i} \quad p \equiv 1 \pmod{4}</math>

a z&nbsp;pierwszego i&nbsp;czwartego mamy

::<math>3 p = 24 k + 3 \quad \text{i} \quad 2 p = 24 j + 10 \qquad \;\: \Longrightarrow \qquad p = 24 (k - j) - 7 \qquad \Longrightarrow \qquad p \equiv - 7 \pmod{24}</math>

::<math>3 p = 24 k + 21 \quad \text{i} \quad 2 p = 24 j + 14 \qquad \Longrightarrow \qquad p = 24 (k - j) + 7 \qquad \Longrightarrow \qquad p \equiv 7 \pmod{24}</math>

Zauważmy, że problem mogliśmy zapisać w&nbsp;postaci układu kongruencji

::<math>p \equiv \pm 1 \pmod{8}</math>

::<math>p \equiv \pm 5 \pmod{12}</math>

Gdyby moduły tych kongruencji były względnie pierwsze, to każdemu wyborowi znaków odpowiadałaby pewna kongruencja równoważna (zobacz J3). Widzimy, że w&nbsp;przypadku, gdy moduły nie są względnie pierwsze, kongruencja równoważna może istnieć, ale nie musi. Rozwiązując taki problem, wygodnie jest skorzystać z&nbsp;programu PARI/GP. Wystarczy wpisać

 chinese(Mod(1, 8), Mod(5, 12)) = Mod(17, 24)
 chinese(Mod(1, 8), Mod(-5, 12)) - błąd 
 chinese(Mod(-1, 8), Mod(5, 12)) - błąd 
 chinese(Mod(-1, 8), Mod(-5, 12)) = Mod(7, 24)

Ostatni punkt zadania rozwiążemy tą metodą. Liczba większa lub równa <math>5</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math> wtedy i&nbsp;tylko wtedy, gdy liczby <math>2</math> i <math>3</math> są liczbami kwadratowymi modulo <math>p</math>, co oznacza, że liczba pierwsza <math>p</math> spełnia kongruencje

::<math>p \equiv \pm 1 \pmod{8}</math>

::<math>p \equiv \pm 1 \pmod{12}</math>

Postępując jak wyżej, otrzymujemy

 chinese(Mod(1, 8), Mod(1, 12)) = Mod(1, 24)
 chinese(Mod(1, 8), Mod(-1, 12)) - błąd 
 chinese(Mod(-1, 8), Mod(1, 12)) - błąd 
 chinese(Mod(-1, 8), Mod(-1, 12)) = Mod(23, 24)

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K22</span><br/>
Dla każdej liczby pierwszej <math>p_n</math> istnieje nieskończenie wiele takich liczb pierwszych <math>q</math>, że <math>p_n</math> jest najmniejszą liczbą niekwadratową modulo <math>q</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>2, p_2, \ldots, p_{n - 1}, p_n</math> będą kolejnymi liczbami pierwszymi. Wybierzmy liczbę <math>u</math> tak, aby spełniała układ kongruencji

::<math>\begin{align}
 u & \equiv 1 \pmod{8 p_2 \cdot \ldots \cdot p_{n - 1}} \\
 u & \equiv a \pmod{p_n}
\end{align}</math>

gdzie <math>a</math> oznacza dowolną liczbą niekwadratową modulo <math>p_n</math>. Na podstawie chińskiego twierdzenia o&nbsp;resztach (zobacz J3) powyższy układ kongruencji może być zapisany w&nbsp;postaci kongruencji równoważnej

::<math>u \equiv c \pmod{8 p_2 \cdot \ldots \cdot p_n}</math>


Zauważmy, że żadna z&nbsp;liczb pierwszych <math>p_k</math>, gdzie <math>1 \leqslant k \leqslant n</math> nie dzieli liczby <math>c</math>, bo mielibyśmy

::<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&nbsp;z&nbsp;twierdzenia Dirichleta 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&nbsp;tych liczb pierwszych.


Ponieważ <math>q \equiv 1 \!\! \pmod{8}</math>, to <math>\left( {\small\frac{2}{q}} \right)_{\small{\!\! L}} = 1</math> (zobacz J29), a&nbsp;dla wszystkich liczb pierwszych nieparzystych <math>p_k < p_n</math> mamy

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left( {\small\frac{p_k}{q}} \right)_{\small{\!\! L}} = \left( {\small\frac{q}{p_k}} \right)_{\small{\!\! L}} \cdot (- 1)^{\tfrac{q - 1}{2} \cdot \tfrac{p_k - 1}{2}} = \left( {\small\frac{q}{p_k}} \right)_{\small{\!\! L}} = \left( {\small\frac{c}{p_k}} \right)_{\small{\!\! L}} = \left( {\small\frac{1}{p_k}} \right)_{\small{\!\! L}} = 1</math>
</div>

bo <math>8 \mid (q - 1)</math>. Dla liczby pierwszej <math>p_n</math> jest

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left( {\small\frac{p_n}{q}} \right)_{\small{\!\! L}} = \left( {\small\frac{q}{p_n}} \right)_{\small{\!\! L}} \cdot (- 1)^{\tfrac{q - 1}{2} \cdot \tfrac{p_n - 1}{2}} = \left( {\small\frac{q}{p_n}} \right)_{\small{\!\! L}} = \left( {\small\frac{c}{p_n}} \right)_{\small{\!\! L}} = \left( {\small\frac{a}{p_n}} \right)_{\small{\!\! L}} = - 1</math>
</div>

Zatem wszystkie liczby pierwsze mniejsze od <math>p_n</math> są liczbami kwadratowymi modulo <math>q</math>, a&nbsp;liczba pierwsza <math>p_n</math> jest najmniejszą liczbą niekwadratową modulo <math>q</math>. Zauważmy, że <math>q</math> była dowolnie wybraną liczbą pierwszą z&nbsp;nieskończenie wielu liczb pierwszych występujących w&nbsp;ciągu arytmetycznym <math>8 p_2 \cdot \ldots \cdot p_n \cdot k + c</math>, gdzie <math>k \in \mathbb{Z}_+</math>. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K23 (Sarvadaman Chowla)</span><br/>
Istnieje niekończenie wiele liczb pierwszych <math>p</math> takich, że najmniejsza liczba niekwadratowa modulo <math>p</math> jest większa od <math>{\small\frac{\log p}{2 L \log 2}}</math>, gdzie <math>L</math> jest stałą Linnika.

{{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&nbsp;twierdzenia Dirichleta wiemy, że w&nbsp;ciągu arytmetycznym <math>u_k = a k + 1</math> występuje nieskończenie wiele liczb pierwszych. Niech <math>p</math> oznacza dowolną z&nbsp;nich.

Ponieważ <math>p \equiv 1 \!\! \pmod{8}</math>, to

::<math>\left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} = 1</math>

(zobacz J29 p.7). Oczywiście <math>p \equiv 1 \!\! \pmod{4}</math>, zatem dla dowolnej liczby pierwszej nieparzystej <math>q_i \leqslant m</math> z&nbsp;twierdzenia J29 p.9 otrzymujemy

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left( {\small\frac{q_i}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{p}{q_i}} \right)_{\small{\!\! L}} = \left( {\small\frac{a k + 1}{q_i}} \right)_{\small{\!\! L}} = \left( {\small\frac{1}{q_i}} \right)_{\small{\!\! L}} = 1</math>
</div>

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

::<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&nbsp;ciągu arytmetycznym <math>u_k = a k + 1</math>, a&nbsp;liczba <math>m</math> została wybrana tak, że liczba <math>a = 4 P (m)</math> jest dostatecznie duża i&nbsp;możliwe jest skorzystanie z&nbsp;twierdzenia Linnika (zobacz C30). Dostajemy natychmiast oszacowanie

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

gdzie <math>L</math> jest stałą Linnika (możemy przyjąć <math>L = 5</math>). Łącząc powyższe oszacowania, łatwo otrzymujemy oszacowanie najmniejszej liczby niekwadratowej modulo <math>p</math>

::<math>\mathbb{n}(p) \geqslant m + 1 > \log_4 a = {\small\frac{\log a}{\log 4}} = {\small\frac{\log a^L}{2 L \log 2}} > {\small\frac{\log p}{2 L \log 2}}</math>

Każdemu wyborowi innej liczby <math>m' > m</math> takiej, że <math>P(m') > P (m)</math> odpowiada inna liczba pierwsza <math>p'</math> taka, że <math>\mathbb{n}(p') > {\small\frac{\log p'}{2 L \log 2}}</math>, zatem liczb pierwszych <math>p</math> dla których najmniejsza liczba niekwadratowa modulo <math>p</math> jest większa od <math>{\small\frac{\log p}{2 L \log 2}}</math> jest nieskończenie wiele.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga K24</span><br/>
W twierdzeniu K22 pokazaliśmy, że dla każdej liczby pierwszej <math>\mathbb{n}</math> istnieją takie liczby pierwsze <math>p</math>, że <math>\mathbb{n}</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>. Zatem zbiór <math>S_\mathbb{n}</math> liczb pierwszych takich, że dla każdej liczby <math>p \in S_\mathbb{n}</math> liczba <math>\mathbb{n}</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math> jest zbiorem niepustym. Wynika stąd, że zbiór <math>S_\mathbb{n}</math> ma element najmniejszy i&nbsp;możemy te najmniejsze liczby pierwsze łatwo znaleźć – wystarczy w&nbsp;PARI/GP napisać proste polecenie

 <span style="font-size: 90%; color:black;">'''forprime'''(n = 2, 50, '''forprime'''(p = 2, 10^10, '''if'''( A(p) == n, '''print'''(n, "   ", p); '''break'''() )))</span>

W tabeli przedstawiamy uzyskane rezultaty (zobacz też [https://oeis.org/A000229 A000229]).

::{| class="wikitable plainlinks"  style="font-size: 100%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{\mathbb{n}}</math> 
| <math>2</math> || <math>3</math> || <math>5</math> || <math>7</math> || <math>11</math> || <math>13</math> || <math>17</math> || <math>19</math> || <math>23</math> || <math>29</math> || <math>31</math> || <math>37</math> || <math>41</math> || <math>43</math> || <math>47</math>
|-
! <math>\boldsymbol{p}</math> 
| <math>3</math> || <math>7</math> || <math>23</math> || <math>71</math> || <math>311</math> || <math>479</math> || <math>1559</math> || <math>5711</math> || <math>10559</math> || <math>18191</math> || <math>31391</math> || <math>422231</math> || <math>701399</math> || <math>366791</math> || <math>3818929</math>
|}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K25</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, a <math>\mathbb{n}</math> będzie najmniejszą liczbą niekwadratową modulo <math>p</math>. Prawdziwe jest oszacowanie

::<math>\mathbb{n} (p) < \sqrt{p} + {\small\frac{1}{2}}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Ponieważ <math>\mathbb{n} \nmid p</math>, to z&nbsp;oszacowania <math>x - 1 < \lfloor x \rfloor \leqslant x</math> wynika, że

::<math>{\small\frac{p}{\mathbb{n}}} - 1 < \left\lfloor {\small\frac{p}{\mathbb{n}}} \right\rfloor < {\small\frac{p}{\mathbb{n}}}</math>

::<math>p < \mathbb{n} \left\lfloor {\small\frac{p}{\mathbb{n}}} \right\rfloor + \mathbb{n} < p + \mathbb{n}</math>

Niech <math>u = \left\lfloor {\small\frac{p}{\mathbb{n}}} \right\rfloor + 1</math>, mamy

::<math>0 < \mathbb{n} u - p < \mathbb{n}</math>

Liczba <math>\mathbb{n} u - p</math> musi być liczbą kwadratową modulo <math>p</math>, zatem

::<math>1 = \left( {\small\frac{\mathbb{n} u - p}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{\mathbb{n}}{p}} \right)_{\small{\!\! L}} \cdot \left( {\small\frac{u}{p}} \right)_{\small{\!\! L}} = - \left( {\small\frac{u}{p}} \right)_{\small{\!\! L}}</math>

Ale z&nbsp;założenia <math>\mathbb{n}</math> jest najmniejszą liczbą taką, że <math>\left( {\small\frac{\mathbb{n}}{p}} \right)_{\small{\!\! L}} = - 1</math>. Wynika stąd, że musi być <math>\mathbb{n} \leqslant u</math> i&nbsp;łatwo znajdujemy, że

::<math>\mathbb{n} \leqslant \left\lfloor {\small\frac{p}{\mathbb{n}}} \right\rfloor + 1 < {\small\frac{p}{\mathbb{n}}} + 1</math>

::<math>\mathbb{n}^2 < p + \mathbb{n}</math>

Ponieważ wypisane liczby są liczbami całkowitymi, to ostatnią nierówność możemy zapisać w&nbsp;postaci

::<math>\mathbb{n}^2 \leqslant p + \mathbb{n} - 1</math>

Skąd otrzymujemy

::<math>\left( \mathbb{n} - {\small\frac{1}{2}} \right)^2 \leqslant p - {\small\frac{3}{4}}</math>

::<math>\mathbb{n} \leqslant {\small\frac{1}{2}} + \sqrt{p - {\small\frac{3}{4}}} < {\small\frac{1}{2}} + \sqrt{p}</math>

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K26*</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, a <math>\mathbb{n}</math> będzie najmniejszą liczbą niekwadratową modulo <math>p</math>. Dla <math>p \geqslant 5</math> prawdziwe jest oszacowanie<ref name="Norton1"/><ref name="Trevino1"/><ref name="Trevino2"/>

::<math>\mathbb{n} (p) \leqslant 1.1 \cdot p^{1 / 4} \log p</math>



<span style="font-size: 110%; font-weight: bold;">Uwaga K27</span><br/>
Liczby <math>\mathbb{n} = \mathbb{n} (p)</math> są zaskakująco małe. Średnia wartość <math>\mathbb{n} = \mathbb{n} (p)</math>, gdzie <math>p</math> są nieparzystymi liczbami pierwszymi, jest równa<ref name="Erdos1"/>

::<math>\lim_{x \to \infty} {\small\frac{1}{\pi (x)}} \sum_{p \leqslant x} \mathbb{n} (p) = \sum_{k = 1}^{\infty} {\small\frac{p_k}{2^k}} = 3.674643966 \ldots</math>



<span style="font-size: 110%; font-weight: bold;">Uwaga K28</span><br/>
Możemy też badać najmniejsze '''nieparzyste''' liczby niekwadratowe modulo <math>p</math>. Pokażemy, że są one również liczbami pierwszymi. W tabeli przedstawiliśmy najmniejsze '''nieparzyste''' liczby niekwadratowe modulo <math>p</math>.

::{| class="wikitable plainlinks"  style="font-size: 100%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{m}</math> 
| <math>5</math> || <math>7</math> || <math>9</math> || <math>11</math> || <math>13</math> || <math>15</math> || <math>17</math> || <math>19</math> || <math>21</math> || <math>23</math> || <math>25</math> || <math>27</math> || <math>29</math> || <math>31</math> || <math>33</math> || <math>35</math> || <math>37</math> || <math>39</math> || <math>41</math> || <math>43</math> || <math>45</math> || <math>47</math> || <math>49</math> || <math>51</math>
|-
! <math>\boldsymbol{\mathbb{n}_1( p )}</math> 
| <math>3</math> || <math>3</math> || <math>-</math> || <math>7</math> || <math>5</math> || <math>-</math> || <math>3</math> || <math>3</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math> || <math>3</math> || <math>3</math> || <math>-</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>3</math> || <math>3</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math>
|}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K29</span><br/>
Dla każdej liczby pierwszej <math>p \geqslant 5</math> najmniejsza '''nieparzysta''' liczba niekwadratowa modulo <math>p</math> jest liczbą pierwszą mniejszą od <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>S \subset \{ 1, 2, \ldots, p - 1 \}</math> będzie zbiorem wszystkich '''nieparzystych''' liczb niekwadratowych modulo <math>p</math>. Z&nbsp;twierdzenia J24 wiemy, że jeżeli <math>p</math> jest liczbą pierwszą nieparzystą, to w&nbsp;zbiorze <math>\{ 1, 2, \ldots, p - 1 \}</math> jest dokładnie <math>{\small\frac{p - 1}{2}}</math> liczb kwadratowych modulo <math>p</math> i&nbsp;tyle samo liczb niekwadratowych modulo <math>p</math>. W&nbsp;zbiorze <math>\{ 1, 2, \ldots, p - 1 \}</math> mamy też dokładnie <math>{\small\frac{p - 1}{2}}</math> liczb parzystych i&nbsp;tyle samo liczb nieparzystych.

Wszystkie liczby parzyste nie mogą być liczbami niekwadratowymi modulo <math>p</math>, bo <math>4 = 2^2 < 5 \leqslant p</math> jest parzystą liczbą kwadratową modulo <math>p</math>, czyli wśród liczb nieparzystych musi istnieć przynajmniej jedna liczba niekwadratowa modulo <math>p</math>. Wynika stąd, że zbiór <math>S</math> nie jest zbiorem pustym, zatem ma element najmniejszy. Pokażemy, że najmniejszy element zbioru <math>S</math> jest liczbą pierwszą.

Niech <math>3 \leqslant \mathbb{n}_\boldsymbol{1} \leqslant p - 2</math> będzie najmniejszą '''nieparzystą''' liczbą niekwadratową modulo <math>p</math>. Wynika stąd, że każda liczba <math>a < \mathbb{n}_\boldsymbol{1}</math> musi być liczbą parzystą lub liczbą kwadratową modulo <math>p</math>. Przypuśćmy, że <math>\mathbb{n}_\boldsymbol{1}</math> jest liczbą złożoną, czyli <math>\mathbb{n}_\boldsymbol{1} = a b</math>, gdzie <math>1 < a, b < \mathbb{n}_\boldsymbol{1}</math>. Zauważmy, że żadna z&nbsp;liczb <math>a, b</math> nie może być liczbą parzystą, bo wtedy liczba <math>\mathbb{n}_\boldsymbol{1}</math> również byłaby liczbą parzystą wbrew określeniu liczby <math>\mathbb{n}_\boldsymbol{1}</math>. Zatem obie liczby <math>a, b</math> muszą być nieparzystymi liczbami kwadratowymi, co jest niemożliwe, bo

::<math>- 1 = \left( {\small\frac{\mathbb{n}_\boldsymbol{1}}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{a b}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{a}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{b}{p}} \right)_{\small{\!\! J}}</math>

i jeden z&nbsp;czynników po prawej stronie musi być ujemny. Co oznacza, że jedna z&nbsp;liczb <math>a, b</math> jest nieparzystą liczbą niekwadratową modulo <math>p</math> mniejszą od <math>\mathbb{n}_\boldsymbol{1}</math> wbrew określeniu liczby <math>\mathbb{n}_\boldsymbol{1}</math>. Uzyskana sprzeczność pokazuje, że liczba <math>\mathbb{n}_\boldsymbol{1}</math> jest liczbą pierwszą. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}





{| style="border-spacing: 5px; border: 2px solid black; background: transparent;"
| &nbsp;'''B.''' Najmniejsze liczby niekwadratowe modulo <math>m</math>
|}

<span style="font-size: 110%; font-weight: bold;">Uwaga K30</span><br/>
Najmniejsze liczby niekwadratowe modulo <math>m</math> są naturalnym uogólnieniem najmniejszych liczb niekwadratowych modulo <math>p .</math> W&nbsp;jednym i&nbsp;drugim przypadku liczba <math>\mathbb{n}</math> jest najmniejszą liczbą niekwadratową w&nbsp;zbiorze wszystkich liczb niekwadratowych dodatnich nie większych od <math>p</math> lub <math>m .</math> Dlatego będziemy je oznaczali również jako <math>\mathbb{n}(m) .</math>



<span style="font-size: 110%; font-weight: bold;">Definicja K31</span><br/>
Niech <math>m \in \mathbb{Z} \,</math> i <math>\, m \geqslant 3 .</math> Powiemy, że <math>\mathbb{n} (m)</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>, gdy <math>\mathbb{n}</math> jest najmniejszą liczbą dodatnią względnie pierwszą z <math>m</math> taką, że kongruencja

::<math>x^2 \equiv \mathbb{n} \pmod{m}</math>

nie ma rozwiązania.



<span style="font-size: 110%; font-weight: bold;">Przykład K32</span><br/>
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math> i&nbsp;najmniejsze liczby niekwadratowe modulo <math>m .</math>

::{| class="wikitable plainlinks"  style="font-size: 100%; text-align: center; margin-right: auto;"
! <math>\boldsymbol{m}</math> 
| <math>3</math> || <math>5</math> || <math>7</math> || <math>9</math> || <math>11</math> || <math>13</math> || <math>15</math> || <math>17</math> || <math>19</math> || <math>21</math> || <math>23</math> || <math>25</math> || <math>27</math> || <math>29</math> || <math>31</math> || <math>33</math> || <math>35</math> || <math>37</math> || <math>39</math> || <math>41</math> || <math>43</math> || <math>45</math> || <math>47</math> || <math>49</math> || <math>51</math>
|-
! <math>\boldsymbol{\mathbb{n}( p )}</math> 
| <math>2</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math>
|-
! <math>\boldsymbol{\mathbb{n}( m )}</math> 
| <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>3</math> || <math>2</math>
|}

::{| class="wikitable plainlinks"  style="font-size: 100%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{m}</math> 
| <math>4</math> || <math>6</math> || <math>8</math> || <math>10</math> || <math>12</math> || <math>14</math> || <math>16</math> || <math>18</math> || <math>20</math> || <math>22</math> || <math>24</math> || <math>26</math> || <math>28</math> || <math>30</math> || <math>32</math> || <math>34</math> || <math>36</math> || <math>38</math> || <math>40</math> || <math>42</math> || <math>44</math> || <math>46</math> || <math>48</math> || <math>50</math> || <math>52</math>
|-
! <math>\boldsymbol{\mathbb{n}( m )}</math> 
| <math>3</math> || <math>5</math> || <math>3</math> || <math>3</math> || <math>5</math> || <math>3</math> || <math>3</math> || <math>5</math> || <math>3</math> || <math>7</math> || <math>5</math> || <math>5</math> || <math>3</math> || <math>7</math> || <math>3</math> || <math>3</math> || <math>5</math> || <math>3</math> || <math>3</math> || <math>5</math> || <math>3</math> || <math>5</math> || <math>5</math> || <math>3</math> || <math>3</math>
|}



<span style="font-size: 110%; font-weight: bold;">Uwaga K33</span><br/>
Do wyszukiwania liczb <math>\mathbb{n} (m)</math> Czytelnik może wykorzystać prostą funkcję napisaną w&nbsp;PARI/GP

 <span style="font-size: 90%; color:black;">B(m) = 
 {
 '''local'''(p, res);
 p = 1;
 '''while'''( p < m,
        p = '''nextprime'''(p + 1);
        '''if'''( m%p == 0, '''next'''() );
        res = -1;
        '''for'''( k = 2, '''floor'''(m/2), '''if'''( k^2%m == p, res = 1; '''break'''() ) );
        '''if'''( res == -1, '''return'''(p) );
      );
 }</span>

Obliczenia można wielokrotnie przyspieszyć, modyfikując kod funkcji tak, aby uwzględniał pokazane niżej właściwości oraz parzystość liczby <math>m .</math> Tutaj przedstawiamy tylko przykład, który wykorzystuje część tych możliwości.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
 <span style="font-size: 90%; color:black;">B(m) = 
 {
 '''local'''(p, res, t);
 t = m%8;
 '''if'''( t == 3 || t == 5, '''return'''(2) );
 t = m%12;
 '''if'''( t == 4 || t == 8, '''return'''(3) );
 t = m%24;
 '''if'''( t == 9 || t == 15, '''return'''(2) );
 '''if'''( t == 10 || t == 14, '''return'''(3) );
 t = m%30;
 '''if'''( t == 6 || t == 12 || t == 18 || t == 24, '''return'''(5) );
 p = 1;
 '''while'''( p < m,
        p = '''nextprime'''(p + 1);
        '''if'''( m%p == 0, '''next'''() );
        res = -1;
        '''for'''( k = 2, '''floor'''(m/2), '''if'''( k^2%m == p, res = 1; '''break'''() ) );
        '''if'''( res == -1, '''return'''(p) );
      );
 }</span>
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K34</span><br/>
Niech <math>m \in \mathbb{Z} \,</math> i <math>\, m \geqslant 3 .</math> Jeżeli <math>\mathbb{n}</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>, to <math>\mathbb{n}</math> jest liczbą pierwszą.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Przypuśćmy, że <math>\mathbb{n} = a b</math> jest liczbą złożoną, gdzie <math>1 < a, b < \mathbb{n} .</math> Z&nbsp;założenia <math>\mathbb{n}</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>, zatem liczby <math>a, b</math> są liczbami kwadratowymi modulo <math>m .</math> Z&nbsp;definicji liczb kwadratowych muszą istnieć takie liczby <math>r, s</math>, że

::<math>r^2 \equiv a \pmod{m}</math>

::<math>s^2 \equiv b \pmod{m}</math>

Skąd wynika, że

::<math>\mathbb{n} = a b \equiv (r s)^2 \pmod{m}</math>

Wbrew założeniu, że <math>\mathbb{n}</math> jest liczbą niekwadratową modulo <math>m .</math><br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie K35</span><br/>
Niech <math>m \in \mathbb{Z}_+ \,</math> i <math>\, \mathbb{n} (m)</math> będzie najmniejszą liczbą niekwadratową modulo <math>m .</math> Pokazać, że jeżeli <math>m = 8 k \pm 3</math>, to <math>\mathbb{n} (m) = 2 .</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Z twierdzenia J36 wiemy, że <math>\left( {\small\frac{2}{m}} \right)_{\small{\!\! J}} = - 1</math>, gdy <math>m = 8 k \pm 3 .</math> Wynika stąd, że <math>2</math> jest liczbą niekwadratową modulo <math>m</math>, a&nbsp;jeśli tak, to musi być najmniejszą liczbą niekwadratową modulo <math>m .</math> Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie K36</span><br/>
Niech <math>m \in \mathbb{Z}_+ \,</math> i <math>\, \mathbb{n} (m)</math> będzie najmniejszą liczbą niekwadratową modulo <math>m .</math> Pokazać, że jeżeli spełniony jest jeden z&nbsp;warunków

:*&nbsp;&nbsp;<math>4 \mid m \;</math> i <math>\; \gcd (3, m) = 1</math>
:*&nbsp;&nbsp;<math>m = 12 k \pm 4</math>

to <math>\mathbb{n} (m) = 3 .</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zauważmy, że <math>2</math> nie może być najmniejszą liczbą niekwadratową modulo <math>m</math>, bo <math>2 \mid m .</math> Rozważmy kongruencję

::<math>x^2 \equiv 3 \pmod{m}</math>

Z założenia <math>4 \mid m</math>, co nie wyklucza możliwości, że również <math>8 \mid m .</math> Ponieważ <math>4 \nmid (3 - 1)</math> i <math>8 \nmid (3 - 1)</math>, to z&nbsp;twierdzenia J50 wynika, że kongruencja <math>x^2 \equiv 3 \!\! \pmod{m}</math> nie ma rozwiązania. Jeśli tylko <math>3 \nmid m</math>, to <math>\mathbb{n} (m) = 3 .</math> W&nbsp;pierwszym punkcie jest to założone wprost, w&nbsp;drugim łatwo widzimy, że <math>3 \nmid (12 k \pm 4) .</math>

Można też zauważyć, że żądanie, aby <math>\gcd (3, m) = 1</math>, prowadzi do dwóch układów kongruencji

::<math>\begin{align}
 m &\equiv 0 \pmod{4} \\
 m &\equiv 1 \pmod{3}
\end{align}</math>

oraz

::<math>\begin{align}
 m &\equiv 0 \pmod{4} \\
 m &\equiv 2 \pmod{3}
\end{align}</math>

którym, na mocy chińskiego twierdzenia o&nbsp;resztach, odpowiadają dwie kongruencje równoważne

::<math>m \equiv \pm 4 \pmod{12}</math>

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie K37</span><br/>
Niech <math>m = 24 k \pm 10 .</math> Pokazać, że <math>\mathbb{n} (m) = 3 .</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zapiszmy <math>m</math> w&nbsp;postaci <math>m = 2 m'</math>, gdzie <math>m' = 12 k \pm 5 .</math> Gdyby kongruencja

::<math>x^2 \equiv 3 \pmod{2 m'}</math>

miała rozwiązanie, to również kongruencja

::<math>x^2 \equiv 3 \pmod{m'}</math>

miałaby rozwiązanie, ale jest to niemożliwe, bo <math>\left( {\small\frac{3}{m'}} \right)_{\small{\!\! J}} = - 1</math> (zobacz J41), czyli <math>3</math> jest liczbą niekwadratową modulo <math>m' .</math> Ponieważ <math>2 \mid m</math>, to <math>2</math> nie może być najmniejszą liczbą niekwadratową modulo <math>m .</math> Wynika stąd, że <math>\mathbb{n} (m) = 3 .</math><br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K38</span><br/>
Niech <math>m \in \mathbb{Z}_+ \;</math> i <math>\; S_2 = \{ 3, 5, 11, 13, 19, 29, 37, 43, \ldots \}</math> będzie zbiorem liczb pierwszych <math>p</math> takich, że <math>\left( {\small\frac{2}{p}} \right)_{\small{\!\! J}} = - 1 .</math> Jeżeli <math>m</math> jest liczbą nieparzystą podzielną przez <math>p \in S_2</math>, to <math>\mathbb{n} (m) = 2 .</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia <math>p \mid m \;</math> i <math>\; \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}} = - 1 .</math> Zatem kongruencja

::<math>x^2 \equiv 2 \pmod{m}</math>

nie ma rozwiązania (zobacz J50). Ponieważ <math>2 \nmid m</math>, to <math>\mathbb{n} (m) = 2 .</math>

Uwaga: zbiór <math>S_2</math> tworzą liczby pierwsze postaci <math>8 k \pm 3</math> (zobacz J36).<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K39</span><br/>
Niech <math>m \in \mathbb{Z}_+ \;</math> i <math>\; S_3 = \{ 5, 7, 17, 19, 29, 31, 41, 43, \ldots \}</math> będzie zbiorem liczb pierwszych <math>p</math> takich, że <math>\left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = - 1 .</math> Jeżeli <math>m</math> jest liczbą parzystą niepodzielną przez <math>3</math> i&nbsp;podzielną przez <math>p \in S_3</math>, to <math>\mathbb{n} (m) = 3 .</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia <math>p \mid m \;</math> i <math>\; \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = - 1 .</math> Zatem kongruencja

::<math>x^2 \equiv 3 \pmod{m}</math>

nie ma rozwiązania (zobacz J50). Ponieważ <math>2 \mid m</math> i <math>3 \nmid m</math>, to <math>\mathbb{n} (m) = 3 .</math>

Uwaga: zbiór <math>S_3</math> tworzą liczby pierwsze postaci <math>12 k \pm 5</math> (zobacz J41).<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K40</span><br/>
Jeżeli <math>m</math> jest liczbą dodatnią podzielną przez <math>6</math> i&nbsp;niepodzielną przez <math>5</math>, to <math>\mathbb{n} (m) = 5 .</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia <math>3 \mid m \;</math> i <math>\; \left( {\small\frac{5}{3}} \right)_{\small{\!\! J}} = \left( {\small\frac{2}{3}} \right)_{\small{\!\! J}} = - 1 .</math> Zatem kongruencja

::<math>x^2 \equiv 5 \pmod{m}</math>

nie ma rozwiązania (zobacz J50). Ponieważ <math>2 \mid m</math>, <math>3 \mid m</math> i <math>5 \nmid m</math>, to <math>\mathbb{n} (m) = 5 .</math><br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K41</span><br/>
Niech <math>m \in \mathbb{Z}_+</math> i <math>p \geqslant 5</math> będzie liczbą pierwszą. Jeżeli iloczyn wszystkich liczb pierwszych mniejszych od <math>p</math> dzieli <math>m</math> i <math>p \nmid m</math>, to <math>\mathbb{n} (m) = p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z twierdzenia K73 wiemy, że istnieje liczba pierwsza nieparzysta <math>q < p</math> taka, że <math>\left( {\small\frac{p}{q}} \right)_{\small{\!\! J}} = - 1 .</math> Z&nbsp;założenia <math>q \mid m</math>, zatem kongruencja

::<math>x^2 \equiv p \pmod{m}</math>

nie ma rozwiązania (zobacz J50). Ponieważ wszystkie liczby pierwsze mniejsze od <math>p</math> dzielą <math>m</math>, to <math>\mathbb{n} (m) = p</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie K42</span><br/>
Pokazać, że podanym w&nbsp;pierwszej kolumnie postaciom liczby <math>m</math> odpowiadają wymienione w&nbsp;drugiej kolumnie wartości <math>\mathbb{n} (m) .</math>

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: left; margin-right: auto;"
|-
! Postać liczby <math>\boldsymbol{m}</math> || <math>\boldsymbol{𝕟(m)}</math> || Uwagi
|-
| <math>m=24k \pm 9</math> || style="text-align:center;" | <math>2</math> || rowspan="3" style="text-align:center;" | K38
|-
| <math>m=120k \pm 25</math> || style="text-align:center;" | <math>2</math>
|-
| <math>m=120k \pm 55</math> || style="text-align:center;" | <math>2</math>
|-
| <math>m=120k \pm 50</math> || style="text-align:center;" | <math>3</math> || style="text-align:center;" | K39
|-
| <math>m=30k \pm 6</math> || style="text-align:center;" | <math>5</math> || rowspan="2" style="text-align:center;" | K40, K41
|-
| <math>m=30k \pm 12</math> || style="text-align:center;" | <math>5</math>
|-
| <math>m=210k \pm 30</math> || style="text-align:center;" | <math>7</math> || rowspan="3" style="text-align:center;" | K41
|-
| <math>m=210k \pm 60</math> || style="text-align:center;" | <math>7</math> 
|-
| <math>m=210k \pm 90</math> || style="text-align:center;" | <math>7</math> 
|}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K43</span><br/>
Niech <math>m</math> będzie liczbą nieparzystą, a <math>\mathbb{n} (m)</math> będzie najmniejszą liczbą niekwadratową modulo <math>m .</math> Mamy

::<math>\begin{array}{lll}
  \mathbb{n} (2 m) >\mathbb{n} (m) &  & \text{gdy} \;\; \mathbb{n} (m) = 2 \\
  \mathbb{n} (2 m) =\mathbb{n} (m) &  & \text{gdy} \;\; \mathbb{n} (m) > 2
\end{array}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

'''Punkt 1.'''

W przypadku, gdy <math>\mathbb{n} (m) = 2</math>, mamy <math>\mathbb{n} (2 m) > 2 = \mathbb{n} (m)</math>, bo <math>\mathbb{n} (2 m)</math> musi być liczbą względnie pierwszą z <math>2 m .</math>

'''Punkt 2.'''

Z definicji najmniejszej liczby niekwadratowej modulo <math>m</math> wiemy, że kongruencja

::<math>x^2 \equiv \mathbb{n} (m) \pmod{m}</math>

nie ma rozwiązania. Oznacza to, że istnieje liczba pierwsza nieparzysta <math>p</math> taka, że <math>p \mid m \;</math> i <math>\; \left( {\small\frac{\mathbb{n} (m)}{p}} \right)_{\small{\!\! J}} = - 1 .</math> Ponieważ <math>p \mid 2 m</math>, to wynika stąd natychmiast, że kongruencja

::<math>x^2 \equiv \mathbb{n} (m) \pmod{2 m}</math>

również nie ma rozwiązania (zobacz J50).

Zatem <math>\mathbb{n} (2 m) \leqslant \mathbb{n} (m) .</math> Niech <math>q</math> będzie liczbą pierwszą taką, że <math>2 < q <\mathbb{n} (m) .</math> Kongruencję

::<math>x^2 \equiv q \pmod{2 m} \qquad \qquad (1)</math>

możemy zapisać w&nbsp;postaci układu kongruencji równoważnych (zobacz J1)

::<math>\begin{align}
 x^2 & \equiv q \pmod{m} \qquad \qquad \;\: (2) \\
 x^2 & \equiv q \pmod{2} \qquad \qquad \;\;\,\, (3) \\
\end{align}</math>

Z definicji <math>q</math> jest liczbą kwadratową modulo <math>m</math>, zatem kongruencja <math>(2)</math> ma rozwiązanie – oznaczmy to rozwiązanie przez <math>x_0 .</math> Łatwo zauważamy, że liczba

::<math>x'_0 = 
  \begin{cases}
  \;\;\;\; x_0 & \text{gdy} \quad x_0 \equiv 1 \pmod{2} \\
  x_0 + m & \text{gdy} \quad x_0 \equiv 0 \pmod{2} \\
  \end{cases}</math>

jest rozwiązaniem układu kongruencji <math>(2)</math> i <math>(3)</math>, a&nbsp;tym samym kongruencja <math>(1)</math> ma rozwiązanie dla każdego <math>2 < q <\mathbb{n} (m) .</math> Wynika stąd, że <math>\mathbb{n} (2 m) =\mathbb{n} (m) .</math><br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K44</span><br/>
Niech <math>m</math> będzie liczbą nieparzystą, a <math>\mathbb{n} (m)</math> będzie najmniejszą liczbą niekwadratową modulo <math>m .</math> Mamy

::<math>\begin{array}{lllll}
  \mathbb{n} (4 m) \geqslant 5 & & \mathbb{n} (m) = 2         & & \text{gdy } \;\; 3 \mid m \\
  \mathbb{n} (4 m) = 3         & & \mathbb{n} (m) \geqslant 2 & & \text{gdy } \;\; 3 \nmid m \\
\end{array}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

'''Punkt 1.'''

Z twierdzenia K38 wynika, że w&nbsp;przypadku, gdy <math>3 \mid m</math>, to <math>\mathbb{n} (m) = 2 .</math> Ponieważ <math>2 \mid 4 m</math> i <math>3 \mid 4 m</math>, to <math>\mathbb{n} (4 m) \geqslant 5 .</math>

'''Punkt 2.'''

Ponieważ <math>m</math> jest liczbą nieparzystą, to <math>8 \nmid 4 m</math>, ale <math>4 \mid 4 m \;</math> i <math>\; 4 \nmid (3 - 1)</math>, zatem z&nbsp;twierdzenia J50 wynika, że kongruencja

::<math>x^2 \equiv 3 \pmod{4 m}</math>

nie ma rozwiązania. Ponieważ <math>2 \mid 4 m \;</math> i <math>\; 3 \nmid 4 m</math>, to <math>\mathbb{n} (4 m) = 3 .</math><br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K45</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli <math>a</math> jest liczbą niekwadratową modulo <math>p \,</math> i <math>\, p \mid m</math>, to <math>a</math> jest liczbą niekwadratową modulo <math>m .</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Wiemy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>m</math> wtedy i&nbsp;tylko wtedy, gdy kongruencja

::<math>x^2 \equiv a \pmod{m}</math>

ma rozwiązanie. Przypuśćmy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>m .</math> Zatem istnieje taka liczba <math>k \in \mathbb{Z}</math>, że

::<math>k^2 \equiv a \pmod{m}</math>

Ponieważ z&nbsp;założenia <math>p \mid m</math>, to prawdziwa jest też kongruencja

::<math>k^2 \equiv a \pmod{p}</math>

co przeczy założeniu, że liczba <math>a</math> jest liczbą niekwadratową modulo <math>p .</math><br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K46</span><br/>
Niech <math>m \geqslant 3</math> będzie liczbą nieparzystą. Jeżeli liczba <math>\mathbb{n} = \mathbb{n} (m)</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>, to istnieje taki dzielnik pierwszy <math>p</math> liczby <math>m</math>, że <math>\mathbb{n}</math> jest najmniejszą liczbą niekwadratową modulo <math>p .</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Przypuśćmy, że taki dzielnik pierwszy nie istnieje. Zatem mamy zbiór dzielników pierwszych liczby <math>m</math>: <math>\{ p_1, \ldots, p_s \}</math> i&nbsp;powiązany z&nbsp;dzielnikami pierwszymi <math>p_k</math> zbiór najmniejszych liczb niekwadratowych modulo <math>p_k</math>: <math>\{ \mathbb{n}_1, \ldots, \mathbb{n}_s \}</math>, z&nbsp;których każda jest liczbą niekwadratową modulo <math>m</math> (zobacz K45). Wynika stąd, że liczba <math>\mathbb{n} = \mathbb{n} (m)</math> musi być mniejsza od każdej z&nbsp;liczb <math>\mathbb{n}_k .</math>

Z definicji liczba <math>\mathbb{n} = \mathbb{n} (m)</math> jest liczbą niekwadratową modulo <math>m</math>, co oznacza, że kongruencja

::<math>x^2 \equiv \mathbb{n} \pmod{m}</math>

nie ma rozwiązania. Niech <math>m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s .</math> Zatem przynajmniej jedna z&nbsp;kongruencji

::<math>x^2 \equiv \mathbb{n} \pmod{p^{\alpha_k}_k}</math>

musi nie mieć rozwiązania (zobacz J11). Z&nbsp;twierdzenia J44 wiemy, że wtedy kongruencja

::<math>x^2 \equiv \mathbb{n} \pmod{p_k}</math>

również nie ma rozwiązania. Zatem <math>\mathbb{n}</math> jest liczbą niekwadratową modulo <math>p_k \,</math> i <math>\, \mathbb{n} < \mathbb{n}_k</math>, co przeczy definicji liczby <math>\mathbb{n}_k .</math><br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K47</span><br/>
Niech <math>m \geqslant 3</math> będzie liczbą nieparzystą. Jeżeli <math>m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>, to

::<math>\mathbb{n}(m) = \min ( \mathbb{n} (p_1), \ldots, \mathbb{n} (p_s) )</math>

gdzie <math>\mathbb{n}(m)</math> jest najmniejszą liczbą kwadratową modulo <math>m</math>, a <math>\mathbb{n}(p_k)</math> są najmniejszymi liczbami kwadratowymi modulo <math>p_k .</math>

{{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&nbsp;twierdzenia K46, 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

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

Otrzymana sprzeczność dowodzi, że <math>\mathbb{n} (m)</math> jest względnie pierwsza z&nbsp;każdą z&nbsp;liczb pierwszych <math>p_i</math>, gdzie <math>1 \leqslant i \leqslant s .</math> Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K48</span><br/>
Niech <math>m \geqslant 3</math> będzie liczbą nieparzystą, a <math>\mathbb{n}(m)</math> jest najmniejszą liczbą niekwadratową modulo <math>m .</math> Prawdziwe są oszacowania

::<math>\mathbb{n}(m) < \sqrt{m} + {\small\frac{1}{2}} \qquad \qquad \qquad \;\;\, \text{dla } m \geqslant 3</math>

::<math>\mathbb{n}(m) \leqslant 1.1 \cdot m^{1 / 4} \log m \qquad \qquad \text{dla } m \geqslant 5</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>p</math> będzie dzielnikiem pierwszym liczby <math>m</math> takim, że <math>\mathbb{n}(m) = \mathbb{n} (p)</math> (z twierdzenia K46 wiemy, że taki dzielnik istnieje). Jeżeli prawdziwe jest oszacowanie <math>\mathbb{n}(p) < F (p)</math>, gdzie <math>F(x)</math> jest funkcją rosnącą, to

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

Podane w&nbsp;twierdzeniu oszacowania wynikają natychmiast z&nbsp;twierdzeń K25 i&nbsp;K26.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga K49</span><br/>
Liczby <math>\mathbb{n} (m)</math> są zaskakująco małe. Średnia wartość <math>\mathbb{n} = \mathbb{n} (m)</math> wynosi<ref name="Pollack1"/>

::<math>\lim_{x \to \infty} {\small\frac{1}{x}} \sum_{m \leqslant x} \mathbb{n} (m) = 2 + \sum_{k = 3}^{\infty} {\small\frac{p_k - 1}{p_1 \cdot \ldots \cdot p_{k - 1}}} = 2.920050977 \ldots</math>





{| style="border-spacing: 5px; border: 2px solid black; background: transparent;"
| &nbsp;'''C.''' Najmniejsze dodatnie liczby niekwadratowe <math>a</math> takie, że <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math>&nbsp;
|}

<span style="font-size: 110%; font-weight: bold;">Przykład K50</span><br/>
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math>, najmniejsze liczby niekwadratowe modulo <math>m</math> i&nbsp;najmniejsze dodatnie liczby niekwadratowe <math>a</math> takie, że <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math>.

::{| class="wikitable plainlinks"  style="font-size: 100%; text-align: center; margin-right: auto;"
! <math>\boldsymbol{m}</math> 
| <math>3</math> || <math>5</math> || <math>7</math> || <math>9</math> || <math>11</math> || <math>13</math> || <math>15</math> || <math>17</math> || <math>19</math> || <math>21</math> || <math>23</math> || <math>25</math> || <math>27</math> || <math>29</math> || <math>31</math> || <math>33</math> || <math>35</math> || <math>37</math> || <math>39</math> || <math>41</math> || <math>43</math> || <math>45</math> || <math>47</math> || <math>49</math> || <math>51</math>
|-
!  <math>\boldsymbol{\mathbb{n}( p )}</math> 
| <math>2</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math>
|-
!  <math>\boldsymbol{\mathbb{n}( m )}</math> 
| <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>3</math> || <math>2</math>
|-
!  <math>\boldsymbol{c( m )}</math> 
| <math>2</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>7</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>5</math> || <math>2</math> || <math>2</math> || <math>7</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>-</math> || <math>2</math>
|}



<span style="font-size: 110%; font-weight: bold;">Uwaga K51</span><br/>
Do wyszukiwania liczb <math>c = c (m)</math> Czytelnik może wykorzystać prostą funkcję napisaną w&nbsp;PARI/GP

 <span style="font-size: 90%; color:black;">C(m) = 
 {
 '''if'''( m%2 == 0, '''return'''(0) );
 '''if'''( '''issquare'''(m), '''return'''(0) );
 '''forprime'''(p = 2, m, '''if'''( jacobi(p, m) == -1, '''return'''(p) ));
 }</span>



<span style="font-size: 110%; font-weight: bold;">Uwaga K52</span><br/>
Najmniejsze dodatnie liczby niekwadratowe <math>a</math> takie, że <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math> oznaczyliśmy jako <math>c(m)</math>. Zauważmy, że są to liczby inne od <math>\mathbb{n}(p)</math> i <math>\mathbb{n}(m)</math>. Wystarczy zwrócić uwagę na występujące w&nbsp;tabeli liczby <math>\mathbb{n}(p)</math>, <math>\mathbb{n}(m)</math> i <math>c(m)</math> dla <math>m = 15, 33, 39</math>. Różnice wynikają z&nbsp;innej definicji liczb <math>c(m)</math> – jeżeli liczba <math>a</math> jest liczbą niekwadratową modulo <math>m</math>, to symbol Jacobiego <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}</math> nie musi być równy <math>- 1</math>. I&nbsp;tak czasami bywa, co bardzo dobrze pokazuje powyższa tabela.

Ponieważ <math>c(m)</math> nie zawsze będzie najmniejszą liczbą kwadratową modulo <math>m</math>, to mamy natychmiast oszacowanie: <math>c(m) \geqslant \mathbb{n} (m)</math> (poza przypadkami, gdy <math>m = n^2</math>).

Dla <math>c(m)</math> nie są prawdziwe oszacowania podane w&nbsp;twierdzeniu K25. Łatwo zauważamy, że

::<math>c = c (15) = 7 > \sqrt{15} + {\small\frac{1}{2}} \approx 4.37</math>

::<math>c = c (39) = 7 > \sqrt{39} + {\small\frac{1}{2}} \approx 6.74</math>

::<math>c = c (105) = 11 > \sqrt{105} + {\small\frac{1}{2}} \approx 10.75</math>

::<math>c = c (231) = 17 > \sqrt{231} + {\small\frac{1}{2}} \approx 15.7</math>

Nie ma więcej takich przypadków dla <math>m < 10^9</math>.



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K53</span><br/>
Niech <math>c, m \in \mathbb{Z}_+</math> i&nbsp;niech <math>m \geqslant 3</math> będzie liczbą nieparzystą, a <math>c</math> będzie najmniejszą liczbą taką, że <math>\left( {\small\frac{c}{m}} \right)_{\small{\!\! J}} = - 1</math>. Liczba <math>c</math> musi być liczbą pierwszą.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Przypuśćmy, że <math>c = a b</math> jest liczbą złożoną, gdzie <math>1 < a, b < c</math>. Mamy

::<math>- 1 = \left( {\small\frac{c}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{a b}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}</math><math>\left( {\small\frac{b}{m}} \right)_{\small{\!\! J}}</math>

Zatem jeden z&nbsp;czynników po prawej stronie musi być równy <math>- 1</math> wbrew definicji liczby <math>c</math>.<br/>
&#9633;
{{\Spoiler}}





== Liczby pierwsze postaci <math>x^2 + n y^2</math> ==

<span style="font-size: 110%; font-weight: bold;">Przykład K54</span><br/>
Przedstawiamy wszystkie rozkłady liczb naturalnych nie większych od <math>85</math> na sumę postaci <math>x^2 + y^2</math>, gdzie <math>x, y \in \mathbb{N}_0</math>. Rozkłady różniące się jedynie kolejnością liczb <math>x , y</math> nie zostały uwzględnione.

{| class="wikitable plainlinks"  style="font-size: 70%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{n}</math> 
| <math>1</math> || style="background-color: #99cc66" | <math>2</math> || <math>4</math> || style="background-color: #99cc66" | <math>5</math> || <math>8</math> || <math>9</math> || <math>10</math> || style="background-color: #99cc66" | <math>13</math> || <math>16</math> || style="background-color: #99cc66" | <math>17</math> || <math>18</math> || <math>20</math> || <math>25</math> || <math>26</math> || style="background-color: #99cc66" | <math>29</math> || <math>32</math> || <math>34</math> || <math>36</math> || style="background-color: #99cc66" | <math>37</math> || <math>40</math> || style="background-color: #99cc66" | <math>41</math> || <math>45</math> || <math>49</math> || <math>50</math> || <math>52</math> || style="background-color: #99cc66" | <math>53</math> || <math>58</math> ||style="background-color: #99cc66" | <math>61</math> || <math>64</math> || <math>65</math> || <math>68</math> || <math>72</math> || style="background-color: #99cc66" | <math>73</math> || <math>74</math> || <math>80</math> || <math>81</math> || <math>82</math> || <math>85</math>
|-
! <math>\boldsymbol{x,y}</math> 
| <math>1,0</math> || <math>1,1</math> || <math>2,0</math> || <math>2,1</math> || <math>2,2</math> || <math>3,0</math> || <math>3,1</math> || <math>3,2</math> || <math>4,0</math> || <math>4,1</math> || <math>3,3</math> || <math>4,2</math> || <math>5,0</math> || <math>5,1</math> || <math>5,2</math> || <math>4,4</math> || <math>5,3</math> || <math>6,0</math> || <math>6,1</math> || <math>6,2</math> || <math>5,4</math> || <math>6,3</math> || <math>7,0</math> || <math>7,1</math> || <math>6,4</math> || <math>7,2</math> || <math>7,3</math> || <math>6,5</math> || <math>8,0</math> || <math>8,1</math> || <math>8,2</math> || <math>6,6</math> || <math>8,3</math> || <math>7,5</math> || <math>8,4</math> || <math>9,0</math> || <math>9,1</math> || <math>9,2</math>
|-
! <math>\boldsymbol{x,y}</math> 
| <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>4,3</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>5,5</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>7,4</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>7,6</math>
|}

Zauważmy, że liczba złożona <math>21</math> nie ma rozkładu na sumę kwadratów, a&nbsp;liczba złożona <math>65</math> ma dwa takie rozkłady. Obie liczby są postaci <math>4 k + 1</math>.



<span style="font-size: 110%; font-weight: bold;">Przykład K55</span><br/>
Przedstawiamy wszystkie rozkłady liczb naturalnych nie większych od <math>73</math> na sumę postaci <math>x^2 + 2 y^2</math>, gdzie <math>x, y \in \mathbb{N}_0</math>.

{| class="wikitable plainlinks"  style="font-size: 70%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{n}</math> 
| <math>1</math> || style="background-color: #99cc66" | <math>2</math> || style="background-color: #99cc66" | <math>3</math> || <math>4</math> || <math>6</math> || <math>8</math> || <math>9</math> || style="background-color: #99cc66" | <math>11</math> || <math>12</math> || <math>16</math> || style="background-color: #99cc66" | <math>17</math> || <math>18</math> || style="background-color: #99cc66" | <math>19</math> || <math>22</math> || <math>24</math> || <math>25</math> || <math>27</math> || <math>32</math> || <math>33</math> || <math>34</math> || <math>36</math> || <math>38</math> || style="background-color: #99cc66" | <math>41</math> || style="background-color: #99cc66" | <math>43</math> || <math>44</math> || <math>48</math> || <math>49</math> || <math>50</math> || <math>51</math> || <math>54</math> || <math>57</math> || style="background-color: #99cc66" | <math>59</math> || <math>64</math> || <math>66</math> || style="background-color: #99cc66" | <math>67</math> || <math>68</math> || <math>72</math> || style="background-color: #99cc66" | <math>73</math>
|-
! <math>\boldsymbol{x,y}</math> 
| <math>1,0</math> || <math>0,1</math> || <math>1,1</math> || <math>2,0</math> || <math>2,1</math> || <math>0,2</math> || <math>3,0</math> || <math>3,1</math> || <math>2,2</math> || <math>4,0</math> || <math>3,2</math> || <math>4,1</math> || <math>1,3</math> || <math>2,3</math> || <math>4,2</math> || <math>5,0</math> || <math>5,1</math> || <math>0,4</math> || <math>5,2</math> || <math>4,3</math> || <math>6,0</math> || <math>6,1</math> || <math>3,4</math> || <math>5,3</math> || <math>6,2</math> || <math>4,4</math> || <math>7,0</math> || <math>0,5</math> || <math>7,1</math> || <math>6,3</math> || <math>7,2</math> || <math>3,5</math> || <math>8,0</math> || <math>8,1</math> || <math>7,3</math> || <math>6,4</math> || <math>8,2</math> || <math>1,6</math>
|-
! <math>\boldsymbol{x,y}</math> 
| <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>1,2</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>0,3</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>3,3</math> || <math></math> || <math>1,4</math> || <math></math> || <math>2,4</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>1,5</math> || <math>2,5</math> || <math>5,4</math> || <math></math> || <math></math> || <math>4,5</math> || <math></math> || <math></math> || <math>0,6</math> || <math></math>
|}

Zauważmy, że liczba złożona <math>65</math> nie ma rozkładu na sumę postaci <math>x^2 + 2 y^2</math>, a&nbsp;liczba złożona <math>33</math> ma dwa takie rozkłady. Obie liczby są postaci <math>8 k + 1</math>.

Zauważmy też, że liczba złożona <math>35</math> nie ma rozkładu na sumę postaci <math>x^2 + 2 y^2</math>, a&nbsp;liczba złożona <math>27</math> ma dwa takie rozkłady. Obie liczby są postaci <math>8 k + 3</math>.



<span style="font-size: 110%; font-weight: bold;">Przykład K56</span><br/>
Przedstawiamy wszystkie rozkłady liczb naturalnych nie większych od <math>103</math> na sumę postaci <math>x^2 + 3 y^2</math>, gdzie <math>x, y \in \mathbb{N}_0</math>.

{| class="wikitable plainlinks"  style="font-size: 70%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{n}</math> 
| <math>1</math> || style="background-color: #99cc66" | <math>3</math> || <math>4</math> || style="background-color: #99cc66" | <math>7</math> || <math>9</math> || <math>12</math> || style="background-color: #99cc66" | <math>13</math> || <math>16</math> || style="background-color: #99cc66" | <math>19</math> || <math>21</math> || <math>25</math> || <math>27</math> || <math>28</math> || style="background-color: #99cc66" | <math>31</math> || <math>36</math> || style="background-color: #99cc66" | <math>37</math> || <math>39</math> || style="background-color: #99cc66" | <math>43</math> || <math>48</math> || <math>49</math> || <math>52</math> || <math>57</math> || style="background-color: #99cc66" | <math>61</math> || <math>63</math> || <math>64</math> || style="background-color: #99cc66" | <math>67</math> || style="background-color: #99cc66" | <math>73</math> || <math>75</math> || <math>76</math> || style="background-color: #99cc66" | <math>79</math> || <math>81</math> || <math>84</math> || <math>91</math> || <math>93</math> || style="background-color: #99cc66" | <math>97</math> || <math>100</math> || style="background-color: #99cc66" | <math>103</math>
|-
! <math>\boldsymbol{x,y}</math> 
| <math>1,0</math> || <math>0,1</math> || <math>2,0</math> || <math>2,1</math> || <math>3,0</math> || <math>3,1</math> || <math>1,2</math> || <math>4,0</math> || <math>4,1</math> || <math>3,2</math> || <math>5,0</math> || <math>0,3</math> || <math>5,1</math> || <math>2,3</math> || <math>6,0</math> || <math>5,2</math> || <math>6,1</math> || <math>4,3</math> || <math>6,2</math> || <math>7,0</math> || <math>7,1</math> || <math>3,4</math> || <math>7,2</math> || <math>6,3</math> || <math>8,0</math> || <math>8,1</math> || <math>5,4</math> || <math>0,5</math> || <math>8,2</math> || <math>2,5</math> || <math>9,0</math> || <math>9,1</math> || <math>8,3</math> || <math>9,2</math> || <math>7,4</math> || <math>10,0</math> || <math>10,1</math>
|-
! <math>\boldsymbol{x,y}</math> 
| <math></math> || <math></math> || <math>1,1</math> || <math></math> || <math></math> || <math>0,2</math> || <math></math> || <math>2,2</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>4,2</math> || <math></math> || <math>3,3</math> || <math></math> || <math></math> || <math></math> || <math>0,4</math> || <math>1,4</math> || <math>5,3</math> || <math></math> || <math></math> || <math></math> || <math>4,4</math> || <math></math> || <math></math> || <math></math> || <math>7,3</math> || <math></math> || <math></math> || <math>6,4</math> || <math>4,5</math> || <math></math> || <math></math> || <math>5,5</math> || <math></math>
|-
! <math>\boldsymbol{x,y}</math> 
| <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>1,3</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>2,4</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math> || <math>1,5</math> || <math></math> || <math></math> || <math>3,5</math> || <math></math> || <math></math> || <math></math> || <math></math> || <math></math>
|}

Zauważmy, że liczba złożona <math>55</math> nie ma rozkładu na sumę postaci <math>x^2 + 3 y^2</math>, a&nbsp;liczba złożona <math>91</math> ma dwa takie rozkłady. Obie liczby są postaci <math>6 k + 1</math>.



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K57</span><br/>
Jeżeli liczba nieparzysta postaci <math>Q = x^2 + n y^2</math>, gdzie <math>n \in \{ 1, 2, 3 \}</math>, ma dwa różne takie przedstawienia w&nbsp;liczbach całkowitych dodatnich, to jest liczbą złożoną.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
W dowodzie wyróżniliśmy miejsca, które wymagają oddzielnej analizy ze względu na wartość liczby <math>n</math>.

Niech

::<math>Q = x^2 + n y^2 = a^2 + n b^2</math>

<div style="border: thin solid black; padding-top: 0em; margin-top: 0.5em; padding-bottom: 0em; margin-bottom: 0.5em;">
<math>\boldsymbol{n = 1}</math>

Z założenia <math>Q</math> jest liczbą nieparzystą, zatem liczby występujące w&nbsp;rozkładach <math>x^2 + y^2 = a^2 + b^2</math> muszą mieć przeciwną parzystość. Nie zmniejszając ogólności, możemy założyć, że liczby <math>x, a</math> są parzyste, a&nbsp;liczby <math>y, b</math> nieparzyste.

<math>\boldsymbol{n = 2}</math>

Z założenia <math>Q</math> jest liczbą nieparzystą, zatem liczby <math>x, a</math> występująca w&nbsp;rozkładach <math>x^2 + 2 y^2 = a^2 + 2 b^2</math> muszą być nieparzyste. Pokażemy, że liczby <math>y, b</math> muszą mieć taką samą parzystość. Przypuśćmy, że <math>y</math> jest parzysta, a <math>b</math> nieparzysta, wtedy modulo <math>4</math> dostajemy

::<math>1 + 2 \cdot 0 \equiv 1 + 2 \cdot 1 \!\! \pmod{4}</math>

Co jest niemożliwe.

<math>\boldsymbol{n = 3}</math>

Z założenia <math>Q</math> jest liczbą nieparzystą, zatem liczby występujące w&nbsp;rozkładach <math>x^2 + 3 y^2 = a^2 + 3 b^2</math> muszą mieć przeciwną parzystość. Pokażemy, że liczby <math>x, a</math> muszą mieć taką samą parzystość. Gdyby liczba <math>x</math> była nieparzysta, a&nbsp;liczba <math>a</math> parzysta, to modulo <math>4</math> mielibyśmy

::<math>1 + 3 \cdot 0 \equiv 0 + 3 \cdot 1 \!\! \pmod{4}</math>

Co jest niemożliwe.
</div>
Mamy

::<math>x^2 - a^2 = n (b^2 - y^2)</math>

::<math>(x - a) (x + a) = n (b - y) (b + y)</math>

Niech <math>f = \gcd (x - a, b - y)</math>, zatem <math>f</math> jest liczbą parzystą i

::<math>x - a = f r , \qquad \qquad b - y = f s , \qquad \qquad \gcd (r, s) = 1</math>

Czyli

::<math>r(x + a) = n s (y + b)</math>

ale liczby <math>r, s</math> są względnie pierwsze, zatem <math>s \mid (x + a)</math> i&nbsp;musi być

::<math>x + a = k s \qquad \qquad \Longrightarrow \qquad \qquad n (y + b) = k r</math>

Gdyby <math>k</math> było liczbą nieparzystą, to liczby <math>r, s</math> musiałyby być parzyste, co jest niemożliwe, bo <math>\gcd (r, s) = 1</math>. Zatem <math>k</math> jest liczbą parzystą i <math>2 s \mid (x + a)</math>, czyli możemy pokazać więcej. Musi być

::<math>x + a = 2 l s \qquad \qquad \Longrightarrow \qquad \qquad n (y + b) = 2 l r</math>

W przypadku gdy <math>n = 2</math> lub <math>n = 3</math>, zauważmy, że <math>n \mid l</math> lub <math>n \mid r</math>.

Łatwo otrzymujemy

::<math>x = {\small\frac{1}{2}} (2 l s + f r)</math>

::<math>y = {\small\frac{1}{2 n}} (2 l r - n f s)</math>

Ostatecznie

::<math>Q = x^2 + n y^2</math>

::<math>\;\;\;\: = \left[ {\small\frac{1}{2}} (2 l s + f r) \right]^2 + n \left[ {\small\frac{1}{2 n}} (2 l r - n f s) \right]^2</math>

::<math>\;\;\;\: = {\small\frac{1}{4 n}} [n (2 l s + f r)^2 + (2 l r - n f s)^2]</math>

::<math>\;\;\;\: = {\small\frac{1}{4 n}} [n (2 l s)^2 + n (f r)^2 + (2 l r)^2 + (n f s)^2]</math>

::<math>\;\;\;\: = {\small\frac{1}{4 n}} [(2 l)^2 + n f^2] (r^2 + n s^2)</math>

<div style="border: thin solid black; padding-top: 0em; margin-top: 0.5em; padding-bottom: 0em; margin-bottom: 0.5em;">
<math>\boldsymbol{n = 1}</math>

::<math>Q = {\small\frac{1}{4}} [(2 l)^2 + f^2] (r^2 + s^2) = \left[ l^2 + \left( {\small\frac{f}{2}} \right)^2 \right] (r^2 + s^2)</math>

<math>\boldsymbol{n = 2 , 3}</math>

W zależności od tego, która z&nbsp;liczb <math>l, r</math> jest podzielna przez <math>n</math>, możemy napisać

::<math>Q = {\small\frac{1}{4 n}} [(2 l)^2 + n f^2] (r^2 + n s^2) = \left[ {\small\frac{(2 l)^2 + n f^2}{4 n}} \right] (r^2 + n s^2) = \left[ {\small\frac{(2 l)^2 + n f^2}{4}} \right] \left( {\small\frac{r^2 + n s^2}{n}} \right)</math>
</div>

Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga K58</span><br/>
Zauważmy, że iloczyn liczb postaci <math>x^2 + n y^2</math> jest liczbą tej samej postaci.

::<math>(a^2 + n b^2) (x^2 + n y^2) = (a x + n b y)^2 + n (a y - b x)^2</math>

::::::::<math>\;\;\;\:\, = (a x - n b y)^2 + n (a y + b x)^2</math>



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K59</span><br/>
Niech <math>x, y, a, b \in \mathbb{Z}</math> i <math>n \in \{ 1, 2, 3 \}</math>. Jeżeli liczba parzysta <math>Q = x^2 + n y^2</math>, to <math>Q = 2^{\alpha} R</math>, gdzie <math>R = a^2 + n b^2</math> jest liczbą nieparzystą.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
W szczególnym przypadku, gdy <math>R = 1</math>, mamy <math>R = 1^2 + n \cdot 0^2</math>.

Dowód sprowadza się do podania wzorów, które pozwalają obniżyć wykładnik, z&nbsp;jakim liczba <math>2</math> występuje w&nbsp;rozwinięciu na czynniki pierwsze liczby <math>Q</math>. Zauważmy, że wynik jest zawsze liczbą, której postać jest taka sama, jak postać liczby <math>Q</math>. Stosując te wzory odpowiednią ilość razy, otrzymujmy rozkład <math>Q = 2^{\alpha} R</math>, gdzie <math>R</math> jest liczbą nieparzystą postaci <math>a^2 + n b^2</math>.

'''1.''' <math>\boldsymbol{Q = x^2 + y^2}</math>

a) jeżeli liczby <math>x, y</math> są parzyste, to <math>{\small\frac{Q}{4}} = \left( {\small\frac{x}{2}} \right)^2 + \left( {\small\frac{y}{2}} \right)^2</math>

b) jeżeli liczby <math>x, y</math> są nieparzyste, to <math>{\small\frac{Q}{2}} = \left( {\small\frac{x + y}{2}} \right)^2 + \left( {\small\frac{x - y}{2}} \right)^2</math>

'''2.''' <math>\boldsymbol{Q = x^2 + 2 y^2}</math>

a) jeżeli liczby <math>x, y</math> są parzyste, to <math>{\small\frac{Q}{4}} = \left( {\small\frac{x}{2}} \right)^2 + 2 \left( {\small\frac{y}{2}} \right)^2</math>

b) jeżeli liczba <math>x</math> jest parzysta, a <math>y</math> nieparzysta, to <math>{\small\frac{Q}{2}} = y^2 + 2 \left( {\small\frac{x}{2}} \right)^2</math>

'''3.''' <math>\boldsymbol{Q = x^2 + 3 y^2}</math>

a) jeżeli liczby <math>x, y</math> są parzyste, to <math>{\small\frac{Q}{4}} = \left( {\small\frac{x}{2}} \right)^2 + 3 \left( {\small\frac{y}{2}} \right)^2</math>

b) jeżeli liczby <math>x, y</math> są nieparzyste i <math>4 \mid (x + y)</math>, to <math>{\small\frac{Q}{4}} = \left( {\small\frac{x - 3 y}{4}} \right)^2 + 3 \left( {\small\frac{x + y}{4}} \right)^2</math>

c) jeżeli liczby <math>x, y</math> są nieparzyste i <math>4 \mid (x - y)</math>, to <math>{\small\frac{Q}{4}} = \left( {\small\frac{x + 3 y}{4}} \right)^2 + 3 \left( {\small\frac{x - y}{4}} \right)^2</math>

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K60</span><br/>
Liczba pierwsza <math>p \geqslant 3</math> jest postaci

:(a)&nbsp;&nbsp;<math>4 k + 1</math>

:(b)&nbsp;&nbsp;<math>8 k + 1 \,</math> lub <math>\: 8 k + 3</math>

:(c)&nbsp;&nbsp;<math>6 k + 1</math>

wtedy i&nbsp;tylko wtedy, gdy istnieje dokładnie jedna para liczb całkowitych dodatnich <math>x, y</math>, że 

:(a)&nbsp;&nbsp;<math>p = x^2 + y^2</math>

:(b)&nbsp;&nbsp;<math>p = x^2 + 2 y^2</math>

:(c)&nbsp;&nbsp;<math>p = x^2 + 3 y^2</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

<math>\Large{\Longleftarrow}</math>

Niech <math>n = 1, 2, 3</math>. Z&nbsp;założenia liczba pierwsza <math>p \geqslant 3</math> może być przedstawiona w&nbsp;postaci <math>p = x_0^2 + n y_0^2</math>, gdzie <math>x_0, y_0</math> są liczbami takimi, że <math>1 \leqslant x_0, y_0 < p</math>. Zatem <math>p \nmid x_0</math> i <math>p \nmid y_0</math>, a&nbsp;rozpatrując równanie <math>p = x_0^2 + n y_0^2</math> modulo <math>p</math> dostajemy

::<math>x_0^2 + n y_0^2 \equiv 0 \!\! \pmod{p}</math>

Zauważmy, że liczba <math>x_0</math> jest rozwiązaniem kongruencji

::<math>x^2 \equiv - n y_0^2 \!\! \pmod{p}</math>

Wynika stąd, że liczba <math>- n y_0^2</math> jest liczbą kwadratową modulo <math>p</math>. Zatem

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left( {\small\frac{- n y_0^2}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- n}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{y_0^2}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{- n}{p}} \right)_{\small{\!\! J}} = 1</math>
</div>

Z twierdzenia J36 i&nbsp;zadania J40 otrzymujemy natychmiast

:(a) jeżeli <math>\left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} = 1</math>, to liczba pierwsza <math>p</math> musi być postaci <math>4 k + 1</math>

:(b) jeżeli <math>\left( {\small\frac{- 2}{p}} \right)_{\small{\!\! J}} = 1</math>, to liczba pierwsza <math>p</math> musi być postaci <math>8 k + 1</math> lub <math>8 k + 3</math>

:(c) jeżeli <math>\left( {\small\frac{- 3}{p}} \right)_{\small{\!\! J}} = 1</math>, to liczba pierwsza <math>p</math> musi być postaci <math>6 k + 1</math>

Co należało pokazać.


<math>\Large{\Longrightarrow}</math>

'''A. Istnienie rozwiązania kongruencji''' <math>\boldsymbol{x^2 + n y^2 \equiv 0 \!\! \pmod{p}}</math>

Z założenia liczba pierwsza <math>p \geqslant 3</math> jest postaci

:(a)&nbsp;&nbsp;<math>4 k + 1</math>

:(b)&nbsp;&nbsp;<math>8 k + 1 \,</math> lub <math>\: 8 k + 3</math>

:(c)&nbsp;&nbsp;<math>6 k + 1</math>

Wynika stąd, że dla (a) <math>n = 1</math>, (b) <math>n = 2</math>, (c) <math>n = 3</math> mamy

::<math>\left( {\small\frac{- n}{p}} \right)_{\small{\!\! J}} = 1</math>

(zobacz J36 i&nbsp;J40) i&nbsp;liczba <math>- n</math> jest liczbą kwadratową modulo <math>p</math>. Zatem kongruencja

::<math>x^2 \equiv - n \!\! \pmod{p}</math>

ma rozwiązanie, czyli istnieje taka liczba <math>k</math>, że

::<math>k^2 + n \equiv 0 \!\! \pmod{p}</math>

Zauważmy, że liczby <math>x_0 = k</math> i <math>y_0 = 1</math> są szczególnymi przypadkami rozwiązania kongruencji

::<math>x^2 + n y^2 \equiv 0 \!\! \pmod{p}</math>

W przypadku (a), korzystając z&nbsp;twierdzenia Wilsona (zobacz J18), liczbę <math>x_0</math> możemy jawnie wypisać: <math>x_0 = \left( {\small\frac{p - 1}{2}} \right) !</math>


'''B. Zmniejszenie rozwiązania początkowego'''

Niech liczby <math>x_0, y_0</math> takie, że <math>p \nmid x_0 \,</math> i <math>\, p \nmid y_0</math> spełniają kongruencję

::<math>x_0^2 + n y_0^2 \equiv 0 \!\! \pmod{p}</math>

Wybierzmy liczby <math>r, s</math> tak, aby były najbliższymi liczbami całkowitymi odpowiednio dla liczb <math>{\small\frac{x_0}{p}} \,</math> i <math>\, {\small\frac{y_0}{p}}</math>. Z&nbsp;definicji mamy

::<math>\left| {\small\frac{x_0}{p}} - r \right| \leqslant {\small\frac{1}{2}} \qquad \qquad \text{i} \qquad \qquad \left| {\small\frac{y_0}{p}} - s \right| \leqslant {\small\frac{1}{2}}</math>

Zatem

::<math>| x_0 - r p | \leqslant {\small\frac{p}{2}} \qquad \qquad \text{i} \qquad \qquad | y_0 - s p | \leqslant {\small\frac{p}{2}}</math>

Ponieważ liczby po lewej stronie nierówności są liczbami całkowitymi, to nigdy nie będą równe liczbie <math>{\small\frac{p}{2}}</math>, gdzie <math>p</math> jest liczbą nieparzystą. Pozwala to wzmocnić wypisane nierówności.

::<math>| x_0 - r p | < {\small\frac{p}{2}} \qquad \qquad \text{i} \qquad \qquad | y_0 - s p | < {\small\frac{p}{2}}</math>

Wynika stąd, że dla dowolnego rozwiązania początkowego <math>x_0, y_0</math> możemy wybrać liczby 

::<math>x = x_0 - r p \qquad \qquad \text{i} \qquad \qquad y = y_0 - s p</math>

takie, że <math>p \nmid x</math> oraz <math>p \nmid y</math> i&nbsp;dla których

::<math>0 < x^2 + n y^2 < \left( {\small\frac{p}{2}} \right)^2 + n \left( {\small\frac{p}{2}} \right)^2 = {\small\frac{(n + 1) p}{4}} \cdot p</math>

Ponieważ modulo <math>p</math> jest <math>x \equiv x_0 \,</math> i <math>\, y \equiv y_0</math>, to liczby <math>x, y</math> spełniają kongruencję

::<math>x^2 + n y^2 \equiv 0 \!\! \pmod{p}</math>

Zatem wynikające z&nbsp;powyższej kongruencji równanie

::<math>x^2 + n y^2 = m p</math>

ma rozwiązanie dla liczb

::<math>| x | < {\small\frac{p}{2}} , \qquad \qquad | y | < {\small\frac{p}{2}}, \qquad \qquad 1 \leqslant m < {\small\frac{(n + 1) p}{4}}</math>

Pomysł ze zmniejszaniem liczb stanowiących rozwiązanie za chwilę wykorzystamy ponownie i&nbsp;będzie to istotny element dowodu.


'''C. Metoda nieskończonego schodzenia Fermata'''<ref name="InfiniteDescent1"/><ref name="Bussey1"/>

Pomysł dowodu został zaczerpnięty z&nbsp;książki Hardy'ego i&nbsp;Wrighta<ref name="HardyWright1"/>.

Jeżeli w&nbsp;rozwiązaniu <math>m = 1</math>, to <math>p = x^2 + n y^2</math> i&nbsp;twierdzenie jest udowodnione. W&nbsp;przypadku gdy <math>m > 1</math> wskażemy sposób postępowania, który pozwoli nam z&nbsp;istniejącego rozwiązania równania

::<math>x^2 + n y^2 = m p</math>

otrzymać nowe rozwiązanie tej samej postaci

::<math>x_1^2 + n y_1^2 = m_1 p</math>

takie, że <math>1 \leqslant m_1 < m</math>. Powtarzając tę procedurę odpowiednią ilość razy, otrzymamy rozwiązanie <math>x_k, y_k, m_k</math>, gdzie <math>m_k = 1</math>. Istnienie takiej procedury stanowi dowód prawdziwości twierdzenia.

Zauważmy, że podział na parzyste i&nbsp;nieparzyste liczby <math>m</math> jest konieczny tylko w&nbsp;przypadku gdy <math>n = 3</math>. W&nbsp;pozostałych przypadkach nie musimy wzmacniać nierówności, aby prawdziwe było oszacowanie <math>1 \leqslant m_1 < m</math>.

'''Przypadek, gdy''' <math>\boldsymbol{m > 1}</math> '''jest liczbą parzystą'''

Jeżeli <math>m > 1</math> jest liczbą parzystą, to z&nbsp;twierdzenia K59 wiemy, że liczba <math>x^2 + n y^2</math> może być zapisana w&nbsp;postaci

::<math>x^2 + n y^2 = 2^{\alpha} (x^2_1 + n y^2_1)</math>

gdzie <math>x^2_1 + n y^2_1</math> jest liczbą nieparzystą. Wystarczy położyć <math>m_1 = {\small\frac{m}{2^{\alpha}}}</math>, aby z&nbsp;istniejącego rozwiązania otrzymać nowe rozwiązanie tej samej postaci

::<math>x_1^2 + n y_1^2 = m_1 p</math>

gdzie <math>m_1</math> jest liczbą nieparzystą i <math>1 \leqslant m_1 < m</math>.

'''Przypadek, gdy''' <math>\boldsymbol{m > 1}</math> '''jest liczbą nieparzystą'''

Niech liczby <math>r, s</math> będą liczbami całkowitymi najbliższymi liczbom <math>{\small\frac{x}{m}} \,</math> i <math>\, {\small\frac{y}{m}}</math>. Z&nbsp;definicji mamy

::<math>\left| {\small\frac{x}{m}} - r \right| \leqslant {\small\frac{1}{2}} \qquad \qquad \text{i} \qquad \qquad \left| {\small\frac{y}{m}} - s \right| \leqslant {\small\frac{1}{2}}</math>

Zatem

::<math>| x - r m | \leqslant {\small\frac{m}{2}} \qquad \qquad \text{i} \qquad \qquad | y - s m | \leqslant {\small\frac{m}{2}}</math>

Ponieważ liczby po lewej stronie nierówności są liczbami całkowitymi, to nigdy nie będą równe liczbie <math>{\small\frac{m}{2}}</math>, gdzie <math>m</math> jest liczbą nieparzystą. Pozwala to wzmocnić wypisane nierówności.

::<math>| x - r m | < {\small\frac{m}{2}} \qquad \qquad \text{i} \qquad \qquad | y - s m | < {\small\frac{m}{2}}</math>

Połóżmy

::<math>a = x - r m \qquad \qquad \text{i} \qquad \qquad b = y - s m</math>

Zauważmy, że liczba <math>m</math> nie może jednocześnie dzielić liczb <math>x</math> i <math>y</math>, bo mielibyśmy <math>m^2 \mid (x^2 + n y^2)</math>, czyli <math>m \mid p</math>, co jest niemożliwe. Zatem przynajmniej jedna z&nbsp;liczb <math>a, b</math> musi być różna od <math>0</math>.

Rozpatrując równanie <math>x^2 + n y^2 = m p</math> modulo <math>m</math> i&nbsp;uwzględniając, że

::<math>x \equiv a \!\! \pmod{m}</math>

::<math>y \equiv b \!\! \pmod{m}</math>

otrzymujemy 

::<math>a^2 + n b^2 \equiv 0 \pmod{m}</math>

Mamy też oszacowanie

::<math>0 < a^2 + n b^2 < \left( {\small\frac{m}{2}} \right)^2 + n \cdot \left( {\small\frac{m}{2}} \right)^2 = {\small\frac{(n + 1) m^2}{4}} = {\small\frac{(n + 1) m}{4}} \cdot m</math>

Wynika stąd, że istnieje taka liczba <math>m_1</math> spełniająca warunek <math>1 \leqslant m_1 < {\small\frac{(n + 1) m}{4}}</math>, że

::<math>a^2 + n b^2 = m_1 m</math>

Mnożąc stronami powyższe równanie i&nbsp;równanie <math>x^2 + n y^2 = m p</math>, otrzymujemy

::<math>m_1 m^2 p = (a^2 + n b^2) (x^2 + n y^2)</math>

::::<math>\;\; = (a x + n b y)^2 + n (a y - b x)^2</math>

(zobacz K58). Zauważmy teraz, że

::<math>a x + n b y = (x - r m) x + n (y - s m) y</math>

::::<math>\quad \; = x^2 - r m x + n y^2 - n s m y</math>

::::<math>\quad \; = m (p - r x - n s y)</math>

::::<math>\quad \; = m x_1</math>


::<math>a y - b x = (x - r m) y - (y - s m) x</math>

::::<math>\;\;\, = x y - r m y - y x + s m x</math>

::::<math>\;\;\, = m (s x - r y)</math>

::::<math>\;\;\, = m y_1</math>

Gdzie oznaczyliśmy

::<math>x_1 = p - r x - n s y</math>

::<math>y_1 = s x - r y</math>

Wynika stąd, że

::<math>m_1 m^2 p = (m x_1)^2 + n (m y_1)^2</math>

Zatem

::<math>x^2_1 + n y^2_1 = m_1 p</math>

gdzie

::<math>1 \leqslant m_1 < {\small\frac{(n + 1) m}{4}}</math>

Czyli powtarzając odpowiednią ilość razy opisaną powyżej procedurę, otrzymamy <math>m_k = 1</math>.


'''D. Jednoznaczność rozkładu'''

Z założenia <math>p</math> jest liczbą pierwszą, zatem jednoznaczność rozkładu wynika z&nbsp;twierdzenia K57. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga K61</span><br/>
Udowodnione wyżej twierdzenie można wykorzystać do znalezienia rozkładu liczby pierwszej <math>p</math> postaci <math>4 k + 1</math> na sumę dwóch kwadratów. Dla dużych liczb pierwszych funkcja działa wolno, bo dużo czasu zajmuje obliczanie silni.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
 <span style="font-size: 90%; color:black;">SumOfTwoSquares(p) = 
 {
 '''local'''(m, r, s, x, y, x1, y1);
 '''if'''( p%4 <> 1 || !'''isprime'''(p), '''return'''("Error") );
 x = 1;
 '''for'''(k = 2, (p-1)/2, x = (x*k)%p); \\ x = { [(p-1)/2]! } % p
 x = x - '''round'''(x/p)*p;
 y = 1;
 m = (x^2 + y^2)/p;
 '''while'''( m > 1,
        r = '''round'''(x/m);
        s = '''round'''(y/m);
        x1 = p - r*x - s*y;
        y1 = r*y - s*x;
        x = x1;
        y = y1;
        m = (x^2 + y^2)/p;
      );
 '''return'''([ '''abs'''(x), '''abs'''(y), p ]);
 }</span>
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie K62</span><br/>
Niech liczby pierwsze <math>p, q</math> będą postaci <math>4 k + 1</math>, a&nbsp;liczba pierwsza <math>r</math>
będzie postaci <math>4 k + 3</math>. Pokazać, że 
:*&nbsp;&nbsp;liczby <math>r, p r \,</math> i <math>\, r^2</math> nie rozkładają się na sumę dwóch kwadratów liczb całkowitych dodatnich
:*&nbsp;&nbsp;liczby <math>p</math>, <math>2 p</math>, <math>p^2 \,</math> i <math>\, p r^2</math> mają jeden rozkład na sumę dwóch kwadratów liczb całkowitych dodatnich 
:*&nbsp;&nbsp;liczba <math>p q</math>, <math>p \neq q</math> ma dwa rozkłady na sumę dwóch kwadratów liczb całkowitych dodatnich

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}

'''Punkt 1.'''

Ponieważ liczby <math>r \,</math> i <math>\, p r</math> są postaci <math>4 k + 3</math>, to modulo <math>4</math> mamy

::<math>r, p r \equiv 3 \!\! \pmod{4}</math>

Suma <math>x^2 + y^2</math> musi być liczbą nieparzystą, zatem liczby <math>x, y</math> muszą mieć przeciwną parzystość i&nbsp;modulo <math>4</math> mamy

::<math>x^2 + y^2 \equiv 1 \!\! \pmod{4}</math>

Przypuśćmy, że

::<math>r^2 = x^2 + y^2</math>

gdzie <math>x, y \in \mathbb{Z}_+</math>. Liczby <math>x, y</math> muszą mieć przeciwną parzystość, zatem <math>x \neq y</math>. Z&nbsp;twierdzenia J22 wynika, że liczba <math>x^2 + y^2</math> musi mieć dzielnik pierwszy postaci <math>4 k + 1</math>, co w&nbsp;sposób oczywisty jest niemożliwe.

'''Punkt 2.'''

W przypadku liczby pierwszej <math>p</math> odpowiedzi udziela twierdzenie K60. Niech <math>p = x^2 + y^2</math>, mamy

::<math>2 p = (x + y)^2 + (x - y)^2</math>

::<math>p^2 = (x^2 - y^2)^2 + (2 x y)^2</math>

::<math>p r^2 = (r x)^2 + (r y)^2</math>

'''Punkt 3.'''

Niech <math>p = x^2 + y^2</math> i <math>q = a^2 + b^2</math>. Ze wzorów podanych w&nbsp;uwadze K58 mamy

::<math>p q = (a^2 + b^2) (x^2 + y^2) = (a x + b y)^2 + (a y - b x)^2</math>

:::::::::<math>\:\, = (a x - b y)^2 + (a y + b x)^2</math>

Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}





== Twierdzenia o&nbsp;istnieniu liczb pierwszych kwadratowych i&nbsp;niekwadratowych modulo ==

<span style="font-size: 110%; font-weight: bold;">Zadanie K63</span><br/>
Niech <math>s = \pm 1</math>. Zbadać podzielność liczby <math>p - s a^2</math>

:* przez <math>4</math>, gdy <math>p = 4 k + r</math>, gdzie <math>r = 1, 3</math>
:* przez <math>8</math>, gdy <math>p = 8 k + r</math>, gdzie <math>r = 1, 3, 5, 7</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Problem sprowadza się do uzyskania odpowiedzi, kiedy kongruencja

::<math>p - s a^2 \equiv 0 \pmod{2^n}</math>

gdzie <math>n = 2, 3</math>, ma rozwiązanie. Podstawiając, dostajemy

::<math>2^n k + r \equiv s a^2 \pmod{2^n}</math>

::<math>s a^2 \equiv r \pmod{2^n}</math>

::<math>a^2 \equiv s r \pmod{2^n}</math>

Z twierdzenia J49 wiemy, że aby powyższa kongruencja miała rozwiązanie, musi być <math>2^n \mid (s r - 1)</math>, co jest możliwe tylko, gdy

::<math>s = 
\begin{cases}
 \;\;\: 1 & \text{gdy } r = 1 \\
      - 1 & \text{gdy } r = 3 \\
\end{cases}</math>

dla <math>2^n = 4</math> i&nbsp;gdy

::<math>s = 
\begin{cases}
 \;\;\: 1 & \text{gdy } r = 1 \\
      - 1 & \text{gdy } r = 7 \\
\end{cases}</math>

dla <math>2^n = 8</math>. Dla <math>2^n = 8</math> i <math>r = 3, 5</math> rozpatrywana kongruencja nie ma rozwiązania.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga K64</span><br/>
Poniżej udowodnimy trzy twierdzenia dotyczące istnienia liczb pierwszych, które są liczbami kwadratowymi modulo <math>p</math>. Pomysł ujęcia problemu zaczerpnęliśmy z&nbsp;pracy Alexandru Gicy<ref name="Gica1"/>. Zadanie K63 należy traktować jako uzupełnienie do dowodu twierdzenia K65. Z&nbsp;zadania łatwo widzimy, że powiązanie liczby <math>s</math> z&nbsp;postacią liczby pierwszej <math>p</math> nie jest przypadkowe.

Zauważmy, że twierdzenia ograniczają się do liczb pierwszych <math>p</math>, ponieważ dla liczb złożonych nieparzystych <math>m > 0</math> wynik <math>\left( {\small\frac{q}{m}} \right)_{\small{\!\! J}} = 1</math> nie oznacza, że liczba pierwsza <math>q</math> jest liczbą kwadratową modulo <math>m</math>.

W tabeli przedstawiamy najmniejsze liczby pierwsze <math>q</math> postaci <math>4 k + 1</math> kwadratowe modulo <math>p</math>.

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{p}</math> 
| <math>3</math> || <math>5</math> || <math>7</math> || <math>11</math> || <math>13</math> || <math>17</math> || <math>19</math> || <math>23</math> || <math>29</math> || <math>31</math> || <math>37</math> || <math>41</math> || <math>43</math> || <math>47</math> || <math>53</math> || <math>59</math> || <math>61</math> || <math>67</math> || <math>71</math> || <math>73</math> || <math>79</math> || <math>83</math> || <math>89</math> || <math>97</math>
|-
! <math>\boldsymbol{q}</math> 
| style="background-color: red" | <math>13</math> || style="background-color: red" | <math>29</math> || style="background-color: red" | <math>29</math> || <math>5</math> || style="background-color: red" | <math>17</math> || <math>13</math> || <math>5</math> || <math>13</math> || <math>5</math> || <math>5</math> || style="background-color: red" | <math>41</math> || <math>5</math> || <math>13</math> || <math>17</math> || <math>13</math> || <math>5</math> || <math>5</math> || <math>17</math> || <math>5</math> || <math>37</math> || <math>5</math> || <math>17</math> || <math>5</math> || <math>53</math>
|}


W kolejnej tabeli przedstawiamy najmniejsze liczby pierwsze <math>q</math> postaci <math>4 k + 3</math> kwadratowe modulo <math>p</math>.

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{p}</math> 
| <math>3</math> || <math>5</math> || <math>7</math> || <math>11</math> || <math>13</math> || <math>17</math> || <math>19</math> || <math>23</math> || <math>29</math> || <math>31</math> || <math>37</math> || <math>41</math> || <math>43</math> || <math>47</math> || <math>53</math> || <math>59</math> || <math>61</math> || <math>67</math> || <math>71</math> || <math>73</math> || <math>79</math> || <math>83</math> || <math>89</math> || <math>97</math>
|-
! <math>\boldsymbol{q}</math> 
| style="background-color: red" | <math>7</math> || style="background-color: red" | <math>11</math> || style="background-color: red" | <math>11</math> || <math>3</math> || <math>3</math> || style="background-color: red" | <math>19</math> || <math>7</math> || <math>3</math> || <math>7</math> || <math>7</math> || <math>3</math> || <math>23</math> || <math>11</math> || <math>3</math> || <math>7</math> || <math>3</math> || <math>3</math> || <math>19</math> || <math>3</math> || <math>3</math> || <math>11</math> || <math>3</math> || <math>11</math> || <math>3</math>
|}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K65</span><br/>
Jeżeli <math>p \geqslant 11</math> jest liczbą pierwszą i <math>p \neq 17</math>, to istnieje liczba pierwsza <math>q < p</math> postaci <math>4 k + 3</math> kwadratowa modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech 
::<math>s = 
\begin{cases}
 \;\;\: 1 & \text{gdy } \, p \, \text{ jest postaci } \, 4 k + 1 \\
      - 1 & \text{gdy } \, p \, \text{ jest postaci } \, 4 k + 3 \\
\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

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

Czyli

::<math>p \equiv s a^2 \pmod{q}</math>

i otrzymujemy

::<math>\left( {\small\frac{q}{p}} \right)_{\small{\!\! J}} = s \cdot \left( {\small\frac{p}{q}} \right)_{\small{\!\! J}} = s \cdot \left( {\small\frac{s a^2}{q}} \right)_{\small{\!\! J}} = s \cdot \left( {\small\frac{s}{q}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{a^2}{q}} \right)_{\small{\!\! J}} =s \cdot \left( {\small\frac{s}{q}} \right)_{\small{\!\! J}} = 1</math>

Zatem liczba <math>q < p</math> jest liczbą kwadratową modulo <math>p</math>.

Pomysł dowodu polega na wskazaniu kilku liczb <math>u(a_1), \ldots, u(a_r)</math> takich, że

::<math>3 \leqslant u(a_1) < \ldots < u(a_r) < p</math>

z których jedna musi być postaci <math>4 k + 3</math>.

'''Przypadek pierwszy:''' <math>\boldsymbol{p \equiv 3 \!\! \pmod{8}}</math>

Mamy <math>s = - 1</math> i&nbsp;przyjmujemy <math>n = 2</math>. Rozważmy liczby

::<math>3 \leqslant {\small\frac{p + 1}{4}} < {\small\frac{p + 9}{4}} < p</math>

Oszacowania są jednocześnie spełnione dla <math>p \geqslant 11</math>. Z&nbsp;założenia <math>p = 8 k + 3</math>, zatem rozpatrywane liczby to <math>\{ 2 k + 1, 2 k + 3 \}</math>. Ponieważ są to dwie kolejne liczby nieparzyste, to jedna z&nbsp;nich jest postaci <math>4 k + 3</math>.

'''Przypadek drugi:''' <math>\boldsymbol{p \equiv 5 \!\! \pmod{8}}</math>

Mamy <math>s = + 1</math> i&nbsp;przyjmujemy <math>n = 2</math>. Rozważmy liczby

::<math>3 \leqslant {\small\frac{p - 9}{4}} < {\small\frac{p - 1}{4}} < p</math>

Oszacowania są jednocześnie spełnione dla <math>p \geqslant 21</math>. Z&nbsp;założenia <math>p = 8 k + 5</math>, zatem rozpatrywane liczby to <math>\{ 2 k - 1, 2 k + 1 \}</math>. Ponieważ są to dwie kolejne liczby nieparzyste, to jedna z&nbsp;nich jest postaci <math>4 k + 3</math>.

'''Przypadek trzeci:''' <math>\boldsymbol{p \equiv 7 \!\! \pmod{8}}</math>

Mamy <math>s = - 1</math> i&nbsp;przyjmujemy <math>n = 3</math>. Rozważmy liczby

::<math>3 \leqslant {\small\frac{p + 1}{8}} < {\small\frac{p + 9}{8}} < {\small\frac{p + 25}{8}} < {\small\frac{p + 49}{8}} < p</math>

Oszacowania są jednocześnie spełnione dla <math>p \geqslant 23</math>. Z&nbsp;założenia <math>p = 8 k + 7</math>, zatem rozpatrywane liczby to <math>\{ k + 1, k + 2, k + 4, k + 7 \}</math>. Jeżeli <math>k \equiv r \!\! \pmod{4}</math>, to modulo <math>4</math> mamy zbiór <math>\{ r + 1, r + 2, r, r + 3 \}</math>. Zatem jedna z&nbsp;liczb w&nbsp;tym zbiorze jest postaci <math>4 k + 3</math>.

'''Przypadek czwarty:''' <math>\boldsymbol{p \equiv 1 \!\! \pmod{8}}</math>

Mamy <math>s = + 1</math> i&nbsp;przyjmujemy <math>n = 3</math>. Rozważmy liczby

::<math>3 \leqslant {\small\frac{p - 49}{8}} < {\small\frac{p - 25}{8}} < {\small\frac{p - 9}{8}} < {\small\frac{p - 1}{8}} < p</math>

Oszacowania są jednocześnie spełnione dla <math>p \geqslant 73</math>. Z&nbsp;założenia <math>p = 8 k + 1</math>, zatem rozpatrywane liczby to <math>\{ k - 6, k - 3, k - 1, k \}</math>. Jeżeli <math>k \equiv r \!\! \pmod{4}</math>, to modulo <math>4</math> mamy zbiór <math>\{ r + 2, r + 1, r + 3, r \}</math>. Zatem jedna z&nbsp;liczb w&nbsp;tym zbiorze jest postaci <math>4 k + 3</math>.

Pozostaje sprawdzić twierdzenie dla liczb pierwszych <math>p < 73</math>. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K66</span><br/>
Jeżeli <math>p \geqslant 11</math> jest liczbą pierwszą postaci <math>8 k + 1</math> lub <math>8 k + 3</math>, to istnieje liczba pierwsza <math>q < p</math> postaci <math>4 k + 1</math> kwadratowa modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
W przypadku, gdy liczba pierwsza <math>p</math> jest postaci <math>8 k + 1</math> lub <math>8 k + 3</math>, to istnieją takie liczby całkowite dodatnie <math>x, y</math>, że <math>p = x^2 + 2 y^2</math> (zobacz K60). Ponieważ z&nbsp;założenia <math>p \geqslant 11</math>, to musi być <math>x \neq y</math>. Z&nbsp;twierdzenia J22 wynika, że liczba <math>x^2 + y^2</math> ma dzielnik pierwszy <math>q</math> postaci <math>4 k + 1</math>. Łatwo widzimy, że <math>q \leqslant x^2 + y^2 < x^2 + 2 y^2 = p</math>.

Modulo <math>q</math> możemy napisać

::<math>x^2 + y^2 \equiv 0 \!\! \pmod{q}</math>

Liczba pierwsza <math>q < p</math> nie może dzielić <math>y</math>, bo mielibyśmy <math>q \mid x</math>, czyli <math>q \mid p</math>, co jest niemożliwe. Rozpatrując równość <math>p = x^2 + 2 y^2</math> modulo <math>q</math>, dostajemy

::<math>p \equiv y^2 \!\! \pmod{q}</math>

Wynika stąd natychmiast (zobacz J36 p.9)

::<math>\left( {\small\frac{q}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{p}{q}} \right)_{\small{\!\! J}} = \left( {\small\frac{y^2}{q}} \right)_{\small{\!\! J}} = 1</math>

Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K67</span><br/>
Jeżeli <math>p \geqslant 19</math> jest liczbą pierwszą postaci <math>12 k + 7</math>, to istnieje liczba pierwsza <math>q < p</math> postaci <math>4 k + 1</math> kwadratowa modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia <math>p \equiv 1 \!\! \pmod{6}</math>, zatem istnieją takie liczby <math>x, y \in \mathbb{Z}_+</math>, że <math>p = x^2 + 3 y^2</math> (zobacz K60). 
Liczby <math>x, y</math> muszą mieć przeciwną parzystość i&nbsp;być względnie pierwsze. Gdyby liczba <math>x</math> była nieparzysta, to modulo <math>4</math> mielibyśmy

::<math>1 + 3 \cdot 0 \equiv 3 \!\! \pmod{4}</math>

Co jest niemożliwe. Zatem <math>x = 2 k</math>, a&nbsp;liczba <math>y</math> musi być nieparzysta. Otrzymujemy

::<math>p = 4 k^2 + 3 y^2 = 4 (k^2 + y^2) - y^2</math>

Ponieważ <math>p</math> jest liczbą pierwszą, to jedynie w&nbsp;przypadku gdy <math>k = y = 1</math> możliwa jest sytuacja, że <math>k = y</math>. Mielibyśmy wtedy <math>p = 7</math>, ale z&nbsp;założenia musi być <math>p \geqslant 19</math>. Wynika stąd, że <math>k \neq y</math>, zatem liczba <math>k^2 + y^2</math> ma dzielnik pierwszy <math>q</math> postaci <math>4 k + 1</math> (zobacz J22). Oczywiście <math>q \leqslant k^2 + y^2 < 4 k^2 + 3 y^2 = p</math>.

Modulo <math>q</math> możemy napisać

::<math>k^2 + y^2 \equiv 0 \!\! \pmod{q}</math>

Liczba pierwsza <math>q</math> nie może dzielić <math>y</math>, bo mielibyśmy <math>q \mid k</math>, czyli <math>q \mid p</math>, co jest niemożliwe. Rozpatrując równość <math>p = 4 (k^2 + y^2) - y^2</math> modulo <math>q</math>, dostajemy

::<math>p \equiv - y^2 \!\! \pmod{q}</math>

Wynika stąd natychmiast (zobacz J36 p.9 i&nbsp;p.6)

::<math>\left( {\small\frac{q}{p}} \right)_{\small{\!\! J}} 
= \left( {\small\frac{p}{q}} \right)_{\small{\!\! J}} 
= \left( {\small\frac{- y^2}{q}} \right)_{\small{\!\! J}} 
= \left( {\small\frac{- 1}{q}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{y^2}{q}} \right)_{\small{\!\! J}} 
= \left( {\small\frac{- 1}{q}} \right)_{\small{\!\! J}} = 1</math>

Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



Twierdzenia K66 i&nbsp;K67 można uogólnić na wszystkie liczby pierwsze.<ref name="Gica1"/><br/>
<span style="font-size: 110%; font-weight: bold;">Twierdzenie K68*</span><br/>
Jeżeli <math>p \geqslant 11</math> jest liczbą pierwszą i <math>p \neq 13, 37</math>, to istnieje liczba pierwsza <math>q < p</math> postaci <math>4 k + 1</math> kwadratowa modulo <math>p</math>.



<span style="font-size: 110%; font-weight: bold;">Uwaga K69</span><br/>
W tabeli przedstawiamy najmniejsze liczby pierwsze <math>q</math> postaci <math>4 k + 1</math> niekwadratowe modulo <math>m</math>.

:{| class="wikitable plainlinks"  style="font-size: 80%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{m}</math> 
| <math>2</math> || <math>3</math> || <math>4</math> || <math>5</math> || <math>6</math> || <math>7</math> || <math>8</math> || <math>9</math> || <math>10</math> || <math>11</math> || <math>12</math> || <math>13</math> || <math>14</math> || <math>15</math> || <math>16</math> || <math>17</math> || <math>18</math> || <math>19</math> || <math>20</math> || <math>21</math> || <math>22</math> || <math>23</math> || <math>24</math> || <math>25</math> || <math>26</math> || <math>27</math> || <math>28</math> || <math>29</math> || <math>30</math> || <math>31</math> || <math>32</math> || <math>33</math> || <math>34</math> || <math>35</math> || <math>36</math> || <math>37</math> || <math>38</math> || <math>39</math> || <math>40</math>
|-
! <math>\boldsymbol{q}</math> 
| style="background-color: red" | <math>-</math> || style="background-color: red" | <math>5</math> || style="background-color: red" | <math>-</math> || style="background-color: red" | <math>13</math> || <math>5</math> || <math>5</math> || <math>5</math> || <math>5</math> || style="background-color: red" | <math>13</math> || style="background-color: red" | <math>13</math> || <math>5</math> || <math>5</math> || <math>5</math> || <math>13</math> || <math>5</math> || <math>5</math> || <math>5</math> || <math>13</math> || <math>13</math> || <math>5</math> || <math>13</math> || <math>5</math> || <math>5</math> || <math>13</math> || <math>5</math> || <math>5</math> || <math>5</math> || <math>17</math> || <math>13</math> || <math>13</math> || <math>5</math> || <math>5</math> || <math>5</math> || <math>13</math> || <math>5</math> || <math>5</math> || <math>13</math> || <math>5</math> || <math>13</math>
|}


W kolejnej tabeli przedstawiamy najmniejsze liczby pierwsze <math>q</math> postaci <math>4 k + 3</math> niekwadratowe modulo <math>m</math>.

:{| class="wikitable plainlinks"  style="font-size: 80%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{m}</math> 
| <math>2</math> || <math>3</math> || <math>4</math> || <math>5</math> || <math>6</math> || <math>7</math> || <math>8</math> || <math>9</math> || <math>10</math> || <math>11</math> || <math>12</math> || <math>13</math> || <math>14</math> || <math>15</math> || <math>16</math> || <math>17</math> || <math>18</math> || <math>19</math> || <math>20</math> || <math>21</math> || <math>22</math> || <math>23</math> || <math>24</math> || <math>25</math> || <math>26</math> || <math>27</math> || <math>28</math> || <math>29</math> || <math>30</math> || <math>31</math> || <math>32</math> || <math>33</math> || <math>34</math> || <math>35</math> || <math>36</math> || <math>37</math> || <math>38</math> || <math>39</math> || <math>40</math>
|-
! <math>\boldsymbol{q}</math> 
| style="background-color: red" | <math>-</math> || style="background-color: red" | <math>11</math> || <math>3</math> || <math>3</math> || style="background-color: red" | <math>11</math> || <math>3</math> || <math>3</math> || style="background-color: red" | <math>11</math> || <math>3</math> || <math>7</math> || <math>7</math> || <math>7</math> || <math>3</math> || <math>7</math> || <math>3</math> || <math>3</math> || <math>11</math> || <math>3</math> || <math>3</math> || <math>11</math> || <math>7</math> || <math>7</math> || <math>7</math> || <math>3</math> || <math>7</math> || <math>11</math> || <math>3</math> || <math>3</math> || <math>7</math> || <math>3</math> || <math>3</math> || <math>7</math> || <math>3</math> || <math>3</math> || <math>7</math> || <math>19</math> || <math>3</math> || <math>7</math> || <math>3</math>
|}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K70</span><br/>
Jeżeli <math>m \geqslant 7</math> jest liczbą całkowitą postaci <math>4 k + 3</math>, to istnieje liczba pierwsza <math>q < m</math> postaci <math>4 k + 3</math> niekwadratowa modulo <math>m</math>.

{{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&nbsp;z&nbsp;twierdzenia J36 p.9 dostajemy

::<math>\left( {\small\frac{q}{m}} \right)_{\small{\!\! J}} =
 - \left( {\small\frac{m}{q}} \right)_{\small{\!\! J}} =
 - \left( {\small\frac{k q + 4}{q}} \right)_{\small{\!\! J}} =
 - \left( {\small\frac{4}{q}} \right)_{\small{\!\! J}} = - 1</math>

Zatem <math>q</math> jest liczbą niekwadratową modulo <math>m</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



Można też pokazać, że<ref name="Pollack2"/><br/>
<span style="font-size: 110%; font-weight: bold;">Twierdzenie K71*</span><br/>
'''A.''' Jeżeli <math>p \geqslant 13</math> jest liczbą pierwszą, to istnieje liczba pierwsza <math>q < p</math> postaci <math>4 k + 1</math> niekwadratowa modulo <math>p</math>.

'''B.''' Jeżeli <math>p \geqslant 5</math> jest liczbą pierwszą, to istnieje liczba pierwsza <math>q < p</math> postaci <math>4 k + 3</math> niekwadratowa modulo <math>p</math>.



Zauważmy, że twierdzenie K71 można łatwo uogólnić na liczby całkowite dodatnie.<br/>
<span style="font-size: 110%; font-weight: bold;">Twierdzenie K72</span><br/>
'''A.''' Jeżeli <math>m \geqslant 6</math> jest liczbą całkowitą i <math>m \neq 10 , 11</math>, to istnieje liczba pierwsza <math>q < m</math> postaci <math>4 k + 1</math> niekwadratowa modulo <math>m</math>.

'''B.''' Jeżeli <math>m \geqslant 4</math> jest liczbą całkowitą i <math>m \neq 6 , 9</math>, to istnieje liczba pierwsza <math>q < m</math> postaci <math>4 k + 3</math> niekwadratowa modulo <math>m</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}

'''Punkt B'''

Rozważmy liczby <math>m</math> postaci <math>m = 2^a 3^b</math>.

Jeżeli <math>3 \mid m</math>, to <math>11</math> jest liczbą niekwadratową modulo <math>m</math>, bo <math>\left( {\small\frac{11}{3}} \right)_{\small{\!\! J}} = - 1</math> (zobacz J50 i&nbsp;K45).

Jeżeli <math>3 \nmid m</math>, ale <math>8 \mid m</math>, to <math>8 \nmid (11 - 1)</math>, zatem liczba <math>11</math> jest liczbą niekwadratową modulo <math>m</math> (zobacz J50).

Jeżeli <math>3 \nmid m</math> i <math>8 \nmid m</math>, ale <math>4 \mid m</math>, to <math>4 \nmid (11 - 1)</math>, zatem liczba <math>11</math> jest liczbą niekwadratową modulo <math>m</math> (zobacz J50).

Jeżeli <math>m = 2</math>, to łatwo zauważamy, że nie istnieją liczby niekwadratowe modulo <math>2</math>.


Zbierając:

:* jeśli liczba <math>m \geqslant 12</math> nie ma dzielnika pierwszego <math>p \geqslant 5</math>, czyli jest postaci <math>m = 2^a 3^b</math>, to liczba pierwsza <math>q = 11</math> jest mniejsza od <math>m</math>, jest postaci <math>4 k + 3</math> i&nbsp;jest liczbą niekwadratową modulo <math>m</math>.
:* jeśli liczba <math>m \geqslant 12</math> ma dzielnik pierwszy <math>p \geqslant 5</math>, to istnieje liczba pierwsza <math>q < p \leqslant m</math> taka, że <math>q</math> jest postaci <math>4 k + 3</math> i&nbsp;jest liczbą niekwadratową modulo <math>m</math> (zobacz K71 i&nbsp;K45).


Pozostaje wypisać dla liczb <math>3 \leqslant m \leqslant 11</math> najmniejsze liczby niekwadratowe, które są liczbami pierwszymi postaci <math>4 k + 3</math>.

 <span style="font-size: 90%; color:black;">'''for'''(m = 3, 15, '''forprimestep'''(q = 3, 100, 4, '''if'''( isQR(q,m) == -1, '''print'''(m, "  ", q); '''break'''() )))</span>

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{m}</math> 
| <math>3</math> || <math>4</math> || <math>5</math> || <math>6</math> || <math>7</math> || <math>8</math> || <math>9</math> || <math>10</math> || <math>11</math> || <math>12</math> || <math>13</math> || <math>14</math> || <math>15</math>
|-
! <math>\boldsymbol{q}</math> 
| style="background-color: red" | <math>11</math> || <math>3</math> || <math>3</math> || style="background-color: red" | <math>11</math> || <math>3</math> || <math>3</math> || style="background-color: red" | <math>11</math> || <math>3</math> || <math>7</math> || <math>7</math> || <math>7</math> || <math>3</math> || <math>7</math>
|}

Widzimy, że twierdzenie jest prawdziwe dla <math>m \geqslant 4</math>, o ile <math>m \neq 6 , 9</math>.

'''Punkt A'''

Rozważmy liczby <math>m</math> postaci <math>m = 2^a 3^b 5^c 7^d 11^e</math>.

Jeżeli jedna z&nbsp;liczb <math>3, 5, 7, 11</math> dzieli <math>m</math>, to <math>17</math> jest liczbą niekwadratową modulo <math>m</math>, bo
<math>\left( {\small\frac{17}{3}} \right)_{\small{\!\! J}} 
= \left( {\small\frac{17}{5}} \right)_{\small{\!\! J}} 
= \left( {\small\frac{17}{7}} \right)_{\small{\!\! J}} 
= \left( {\small\frac{17}{11}} \right)_{\small{\!\! J}} 
= - 1</math>.

Jeżeli żadna z&nbsp;liczb <math>3, 5, 7, 11</math> nie dzieli <math>m</math>, ale <math>8 \mid m</math>, to <math>8 \nmid (5 - 1)</math>, zatem liczba <math>5</math> jest liczbą niekwadratową modulo <math>m</math>.

Jeżeli żadna z&nbsp;liczb <math>3, 5, 7, 11</math> nie dzieli <math>m</math> i <math>8 \nmid m</math>, ale <math>4 \mid m</math>, to nie istnieją liczby pierwsze postaci <math>4 k + 1</math> niekwadratowe modulo <math>m</math>, bo <math>4 \mid [(4 k + 1) - 1]</math>

Jeżeli <math>m = 2</math>, to łatwo zauważamy, że nie istnieją liczby niekwadratowe modulo <math>2</math>.

Zbierając:

:* jeśli liczba <math>m \geqslant 18</math> nie ma dzielnika pierwszego <math>p \geqslant 13</math>, czyli jest postaci <math>m = 2^a 3^b 5^c 7^d 11^e</math>, to liczba pierwsza <math>q = 5</math> lub <math>q = 17</math> jest mniejsza od <math>m</math>, jest postaci <math>4 k + 1</math> i&nbsp;jest liczbą niekwadratową modulo <math>m</math>.
:* jeśli liczba <math>m \geqslant 18</math> ma dzielnik pierwszy <math>p \geqslant 13</math>, to istnieje liczba pierwsza <math>q < p \leqslant m</math> taka, że <math>q</math> jest postaci <math>4 k + 1</math> i&nbsp;jest liczbą niekwadratową modulo <math>m</math> (zobacz K71 i&nbsp;K45).

Pozostaje wypisać dla liczb <math>3 \leqslant m \leqslant 17</math> najmniejsze liczby niekwadratowe, które są liczbami pierwszymi postaci <math>4 k + 1</math>.

 <span style="font-size: 90%; color:black;">'''for'''(m = 3, 20, '''forprimestep'''(q = 1, 100, 4, '''if'''( isQR(q,m) == -1, '''print'''(m, "  ", q); '''break'''() )))</span>

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{m}</math> 
| <math>3</math> || <math>4</math> || <math>5</math> || <math>6</math> || <math>7</math> || <math>8</math> || <math>9</math> || <math>10</math> || <math>11</math> || <math>12</math> || <math>13</math> || <math>14</math> || <math>15</math> || <math>16</math> || <math>17</math> || <math>18</math> || <math>19</math> || <math>20</math>
|-
! <math>\boldsymbol{q}</math> 
| style="background-color: red" | <math>5</math> || style="background-color: red" | <math>-</math> || style="background-color: red" | <math>13</math> || <math>5</math> || <math>5</math> || <math>5</math> || <math>5</math> || style="background-color: red" | <math>13</math> || style="background-color: red" | <math>13</math> || <math>5</math> || <math>5</math> || <math>5</math> || <math>13</math> || <math>5</math> || <math>5</math> || <math>5</math> || <math>13</math> || <math>13</math>
|}

Widzimy, że twierdzenie jest prawdziwe dla <math>m \geqslant 6</math>, o ile <math>m \neq 10 , 11</math>.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie K73</span><br/>
Jeżeli <math>p \geqslant 5</math> jest liczbą pierwszą, to istnieje liczba pierwsza nieparzysta <math>q < p</math> taka, że <math>\left( {\small\frac{p}{q}} \right)_{\small{\!\! J}} = - 1 .</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Łatwo sprawdzamy, że

::<math>\left( {\small\frac{5}{3}} \right)_{\small{\!\! J}} = \left( {\small\frac{7}{5}} \right)_{\small{\!\! J}} = \left( {\small\frac{11}{3}} \right)_{\small{\!\! J}} = - 1</math>

(zobacz J36&nbsp;p.7). Zatem dowód wystarczy przeprowadzić dla <math>p \geqslant 13</math>.

'''A. Liczba pierwsza''' <math>\, \boldsymbol{p} \,</math> '''jest postaci''' <math>\, \boldsymbol{4 k + 1}</math>

Niech liczba <math>q</math> będzie najmniejszą '''nieparzystą''' liczbą niekwadratową modulo <math>p</math>. Z&nbsp;twierdzenia K29 wiemy, że dla <math>p \geqslant 5</math> liczba <math>q</math> jest liczbą pierwszą i&nbsp;jest mniejsza od <math>p</math>. Ponieważ <math>p \equiv 1 \!\! \pmod{4}</math>, to z&nbsp;twierdzenia J36&nbsp;p.9 otrzymujemy natychmiast

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left( {\small\frac{p}{q}} \right)_{\small{\!\! J}} = \left( {\small\frac{q}{p}} \right)_{\small{\!\! J}} = - 1</math>
</div>

'''B. Liczba pierwsza''' <math>\, \boldsymbol{p} \,</math> '''jest postaci''' <math>\, \boldsymbol{4 k + 3}</math>

Z twierdzenia K65 wynika, że dla każdej liczby pierwszej <math>p \geqslant 11</math> postaci <math>4 k + 3</math> istnieje liczba pierwsza <math>q < p</math> taka, że <math>q</math> jest postaci <math>4 k + 3</math> i&nbsp;jest liczbą kwadratową modulo <math>p</math>. Ponieważ <math>p \equiv q \equiv 3 \!\! \pmod{4}</math>, to z&nbsp;twierdzenia J36 p.9 otrzymujemy natychmiast 

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left( {\small\frac{p}{q}} \right)_{\small{\!\! J}} = - \left( {\small\frac{q}{p}} \right)_{\small{\!\! J}} = - 1</math>
</div>

Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie K74</span><br/>
Udowodnić twierdzenie K73 w&nbsp;przypadku, gdy liczba pierwsza <math>p \geqslant 19</math> jest postaci <math>4 k + 3</math>, nie korzystając z&nbsp;twierdzenia K65.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Z założenia <math>p = 4 k + 3</math>. Liczba <math>k</math> może być postaci <math>k = 3 j</math>, <math>k = 3 j + 1</math> i <math>k = 3 j + 2</math>. Odpowiada to liczbom pierwszym postaci <math>p = 12 j + 3</math>, <math>p = 12 j + 7</math> i <math>p = 12 j + 11</math>.

Ponieważ nie ma liczb pierwszych <math>p \geqslant 19</math> i&nbsp;będących postaci <math>p = 12 j + 3</math>, to pozostaje rozważyć przypadki <math>p = 12 j + 7</math> i <math>p = 12 j + 11</math>.

'''A. Liczba pierwsza''' <math>\, \boldsymbol{p} \,</math> '''jest postaci''' <math>\, \boldsymbol{12 j + 11}</math>

Wiemy, że w&nbsp;tym przypadku <math>\left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = + 1</math> (zobacz J41). Mamy

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left( {\small\frac{p}{3}} \right)_{\small{\!\! J}} = - \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = - 1</math>
</div>

Czyli wystarczy przyjąć <math>q = 3</math>.

'''B. Liczba pierwsza''' <math>\, \boldsymbol{p} \,</math> '''jest postaci''' <math>\, \boldsymbol{12 j + 7}</math>

Wiemy, że w&nbsp;tym przypadku <math>\left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = - 1</math> (zobacz J36&nbsp;p.6 oraz J41). Otrzymujemy

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left( {\small\frac{p}{p - 12}} \right)_{\small{\!\! J}} = - \left( {\small\frac{p - 12}{p}} \right)_{\small{\!\! J}} = - \left( {\small\frac{- 12}{p}} \right)_{\small{\!\! J}} = \left[ - \left( {\small\frac{- 1}{p}} \right)_{\small{\!\! J}} \right] \cdot \left( {\small\frac{2^2}{p}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{3}{p}} \right)_{\small{\!\! J}} = -1</math>
</div>

Ponieważ liczba <math>p - 12 \geqslant 7</math> jest nieparzysta, to musi istnieć nieparzysty dzielnik pierwszy <math>q < p</math> liczby <math>p - 12</math> taki, że <math>\left( {\small\frac{p}{q}} \right)_{\small{\!\! J}} = - 1</math>. W&nbsp;przeciwnym razie z&nbsp;twierdzenia J36&nbsp;p.4 mielibyśmy <math>\left( {\small\frac{p}{p - 12}} \right)_{\small{\!\! J}} = 1</math>. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}














== Przypisy ==

<references>

<ref name="Dukic1">Dušan Đukić, ''Quadratic Congruences'', International Mathematical Olympiad training materials, ([https://imomath.com/index.cgi?page=quadraticCongruencesSumsLegendreSymbols IMOmath.com])</ref>

<ref name="Norton1">Karl K. Norton, ''Numbers with Small Prime Factors, and the Least ''k''th Power Non-Residue'', Memoirs of the American Mathematical Society, No. 106 (1971)</ref>

<ref name="Trevino1">Enrique Treviño, ''The least k-th power non-residue'', Journal of Number Theory, Volume 149 (2015)</ref>

<ref name="Trevino2">Kevin J. McGown and Enrique Treviño, ''The least quadratic non-residue'', Mexican Mathematicians in the World (2021)</ref>

<ref name="Erdos1">Paul Erdős, ''Számelméleti megjegyzések I'', Afar. Lapok, v. 12 (1961)</ref>

<ref name="Pollack1">Paul Pollack, ''The average least quadratic nonresidue modulo <math>m</math> and other variations on a&nbsp;theme of Erdős'', Journal of Number Theory, Vol. 132 (2012), No. 6, pp. 1185-1202.</ref>

<ref name="InfiniteDescent1">Wikipedia, ''Proof by infinite descent'', ([https://en.wikipedia.org/wiki/Proof_by_infinite_descent Wiki-en])</ref>

<ref name="Bussey1">W. H. Bussey, ''Fermat's Method of Infinite Descent'', The American Mathematical Monthly, Vol. 25, No. 8 (1918)</ref>

<ref name="HardyWright1">G. H. Hardy and Edward M. Wright, ''An Introduction to the Theory of Numbers'', New York: Oxford University Press, 5th Edition, zobacz dowód Twierdzenia 366 w&nbsp;sekcji 20.4 na stronie 301.</ref>

<ref name="Gica1">Alexandru Gica, ''Quadratic Residues of Certain Types'', Rocky Mountain J. Math. 36 (2006), no. 6, 1867-1871.</ref>

<ref name="Pollack2">Paul Pollack, ''The least prime quadratic nonresidue in a&nbsp;prescribed residue class mod 4'', Journal of Number Theory 187 (2018), 403-414</ref>

</references>












&nbsp;