Tekst źródłowy strony CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego

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

__FORCETOC__



== Chińskie twierdzenie o&nbsp;resztach ==

<span style="font-size: 110%; font-weight: bold;">Twierdzenie J1</span><br/>
Niech <math>a, u \in \mathbb{Z}</math> i <math>m, n \in \mathbb{Z}_+</math> i <math>\gcd (m, n) = 1</math>. Kongruencja

::<math>u \equiv a \pmod{m n}</math>

jest równoważna układowi kongruencji

::<math>\begin{align}
 u &\equiv a \pmod{m} \\
 u &\equiv a \pmod{n} \\
\end{align}</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>

Jeżeli liczba <math>u - a</math> jest podzielna przez iloczyn <math>m n</math>, to tym bardziej jest podzielna przez dowolny czynnik tego iloczynu, skąd wynika natychmiast wypisany układ kongruencji.

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

Z kongruencji

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

wynika, że <math>u - a = k m</math>, zaś z&nbsp;kongruencji

::<math>u \equiv a \pmod{n}</math>

otrzymujemy <math>n \mid (u - a)</math>, czyli <math>n \mid k m</math>. Ponieważ <math>\gcd (m, n) = 1</math>, zatem <math>n \mid k</math> (zobacz C74) i&nbsp;istnieje taka liczba całkowita <math>s</math>, że <math>k = s n</math>, czyli <math>u - a = s n m</math>, a&nbsp;stąd <math>u \equiv a \!\! \pmod{m n}</math>. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J2</span><br/>
Dla dowolnych liczb <math>a, b \in \mathbb{Z}</math> i&nbsp;względnie pierwszych liczb <math>m, n \in \mathbb{Z}_+</math> istnieje dokładnie jedna taka liczba <math>c</math> (określona modulo <math>m n</math>), że prawdziwy jest układ kongruencji

::<math>\begin{align}
 c & \equiv a \pmod{m} \\
 c & \equiv b \pmod{n} \\
\end{align}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z&nbsp;założenia liczby <math>m</math> i <math>n</math> są względnie pierwsze, zatem na mocy lematu Bézouta (C.71) istnieją takie liczby <math>x, y \in \mathbb{Z}</math>, że

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

Niech <math>c = a n y + b m x</math>. Modulo <math>m</math> dostajemy

::<math>c \equiv a n y \pmod{m}</math>

::<math>c \equiv a (1 - m x) \pmod{m}</math>

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

Natomiast modulo <math>n</math> mamy

::<math>c \equiv b m x \pmod{n}</math>

::<math>c \equiv b (1 - n y) \pmod{n}</math>

::<math>c \equiv b \pmod{n}</math>

Pokazaliśmy tym samym istnienie szukanej liczby <math>c</math>. Przypuśćmy, że istnieją dwie takie liczby <math>c \;</math> i <math>\; d</math>. Z&nbsp;założenia <math>m \mid (d - a) \;</math> i <math>\; m \mid (c - a)</math>, zatem <math>m</math> dzieli różnicę tych liczb, czyli <math>m \mid (d - c)</math>. Podobnie pokazujemy, że <math>n \mid (d - c)</math>. Ponieważ liczby <math>m \;</math> i <math>\; n</math> są względnie pierwsze, to <math>m n \mid (d - c)</math> (zobacz C75), co oznacza, że

::<math>d \equiv c \pmod{m n}</math>.

Czyli możemy powiedzieć, że wybrana przez nas liczba <math>c</math> jest określona modulo <math>m n</math> i&nbsp;tak rozumiana jest dokładnie jedna. W&nbsp;szczególności istnieje tylko jedna liczba <math>c</math> taka, że <math>1 \leqslant c \leqslant m n</math>.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J3 (chińskie twierdzenie o&nbsp;resztach)</span><br/>
Niech <math>a, b, c, u \in \mathbb{Z}</math> i <math>m, n \in \mathbb{Z}_+</math> oraz niech <math>\gcd (m, n) = 1</math>. Istnieje dokładnie jedna liczba <math>c</math> (określona modulo <math>m n</math>) taka, że kongruencja

::<math>u \equiv c \pmod{m n}</math>

jest równoważna układowi kongruencji

::<math>\begin{align}
 u & \equiv a \pmod{m} \\
 u & \equiv b \pmod{n} \\
\end{align}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z&nbsp;twierdzenia J2 wiemy, że istnieje dokładnie jedna liczba <math>c</math> (określona modulo <math>m n</math>) taka, że prawdziwy jest układ kongruencji

::<math>\begin{align}
 c & \equiv a \pmod{m} \\
 c & \equiv b \pmod{n} \\
\end{align}</math>

Korzystając z&nbsp;tego rezultatu i&nbsp;twierdzenia J1, otrzymujemy

::<math>u \equiv c \pmod{m n} \qquad \Longleftrightarrow \qquad 
\begin{array}{l}
  u \equiv c \; \pmod{m} \\
  u \equiv c \; \pmod{n} \\
\end{array} \qquad \Longleftrightarrow \qquad
\begin{array}{l}
  u \equiv a \; \pmod{m} \\
  u \equiv b \:\, \pmod{n} \\
\end{array} </math>

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



<span style="font-size: 110%; font-weight: bold;">Uwaga J4</span><br/>
Chińskie twierdzenie o&nbsp;resztach<ref name="CRT1"/> (CRT<ref name="CRT2"/>) pozostaje prawdziwe w&nbsp;przypadku układu skończonej liczby kongruencji. Założenie, że moduły <math>m</math> i <math>n</math> są względnie pierwsze, jest istotne. Przykładowo układ kongruencji

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

nie może być zapisany w&nbsp;postaci jednej równoważnej kongruencji, bo nie istnieją liczby, które spełniałyby powyższy układ jednocześnie. Łatwo zauważamy, że rozwiązaniem pierwszego równania jest <math>u = 4 k + 1</math>, które dla liczb <math>k</math> parzystych i&nbsp;nieparzystych ma postać

::<math>u = 8 j + 1, \qquad u = 8 j + 5</math>

i nie może być <math>u \equiv 3 \!\! \pmod{8}</math>.



<span style="font-size: 110%; font-weight: bold;">Zadanie J5</span><br/>
Niech <math>u, a_1, \ldots, a_k \in \mathbb{Z}</math> i <math>m_1, \ldots, m_k \in \mathbb{Z}_+</math>. Pokazać, że jeżeli liczby <math>m_1, \ldots, m_k</math> są parami względnie pierwsze (czyli <math>\gcd (m_i, m_j) = 1</math> dla <math>i \neq j</math>), to istnieje dokładnie jedna liczba <math>c</math> (określona modulo <math>m_1 \cdot \ldots \cdot m_k</math>) taka, że układ kongruencji

::<math>\begin{align}
 u & \equiv a_1 \pmod{m_1} \\
   & \cdots \\
 u & \equiv a_k \pmod{m_k} \\
\end{align}</math>

można zapisać w&nbsp;sposób równoważny w&nbsp;postaci kongruencji

::<math>u \equiv c \;\; \pmod{m_1 \cdot \ldots \cdot m_k}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Indukcja matematyczna. Twierdzenie jest prawdziwe dla liczby <math>k = 2</math> (zobacz J3). Zakładając prawdziwość twierdzenia dla liczby naturalnej <math>k \geqslant 2</math>, dla liczby <math>k + 1</math> otrzymujemy układ kongruencji

::<math>\begin{align}
 u & \equiv c \quad \;\, \pmod{m_1 \cdot \ldots \cdot m_k} \\
 u & \equiv a_{k + 1} \pmod{m_{k + 1}} \\
\end{align}</math>

gdzie skorzystaliśmy z&nbsp;założenia indukcyjnego. Z&nbsp;twierdzenia J3 wynika, że układ ten można zapisać w&nbsp;sposób równoważny w&nbsp;postaci kongruencji

::<math>u \equiv c' \pmod{m_1 \cdot \ldots \cdot m_k m_{k + 1}}</math>

gdzie liczba <math>c'</math> jest dokładnie jedna i&nbsp;jest określona modulo <math>m_1 \cdot \ldots \cdot m_k m_{k + 1}</math>. Zatem twierdzenie jest prawdziwe dla <math>k + 1</math>. Co kończy dowód indukcyjny.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Przykład J6</span><br/>
Dysponujemy pewną ilością kulek. Grupując je po <math>5</math>, zostają nam <math>3</math>, a&nbsp;kiedy próbujemy ustawić je po <math>7</math>, zostają nam <math>4</math>. Jaka najmniejsza ilość kulek spełnia te warunki? Rozważmy układ kongruencji

::<math>\begin{align}
 n &\equiv 3 \pmod{5} \\
 n &\equiv 4 \pmod{7} \\
\end{align}</math>

Z chińskiego twierdzenia o&nbsp;resztach wiemy, że powyższy układ możemy zapisać w&nbsp;postaci równoważnej kongruencji modulo <math>35</math>. Jeśli chcemy zaoszczędzić sobie trudu, to wystarczy skorzystać z&nbsp;PARI/GP. Wpisując proste polecenie

 <span style="font-size: 90%; color:black;">chinese( Mod(3,5), Mod(4,7) )</span>

uzyskujemy wynik <code>Mod(18, 35)</code>, zatem równoważna kongruencja ma postać

::<math>n \equiv 18 \pmod{35}</math>

Jest to zarazem odpowiedź na postawione pytanie: najmniejsza liczba kulek wynosi <math>18</math>.

Gdybyśmy chcieli rozważać bardziej rozbudowany układ kongruencji, przykładowo

::<math>\begin{align}
 n &\equiv 1 \pmod{2} \\
 n &\equiv 2 \pmod{3} \\
 n &\equiv 3 \pmod{5} \\
 n &\equiv 4 \pmod{7} \\
 n &\equiv 5 \pmod{11} \\
\end{align}</math>

to argumenty należy zapisać w&nbsp;postaci wektora

 <span style="font-size: 90%; color:black;">chinese( [Mod(1,2), Mod(2,3), Mod(3,5), Mod(4,7), Mod(5,11)] )</span>

Otrzymujemy <code>Mod(1523, 2310)</code>.





== Wielomiany ==

<span style="font-size: 110%; font-weight: bold;">Twierdzenie J7</span><br/>
Niech <math>n \in \mathbb{Z}_+</math>. Dla dowolnych liczb całkowitych <math>x, s</math> prawdziwy jest wzór

::<math>x^n = s^n + (x - s) \cdot R_{n - 1} (x)</math>

gdzie <math>R_{n - 1} (x)</math> jest pewnym wielomianem całkowitym stopnia <math>n - 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Indukcja matematyczna. Dla <math>n = 1, 2, 3</math> mamy

::<math>x = s + (x - s) \cdot 1</math>

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

::<math>x^3 = s^3 + (x - s) (x^2 + x s + s^2)</math>

Zakładając, że twierdzenie jest prawdziwe dla liczb całkowitych dodatnich należących do przedziału <math>[1, n]</math> otrzymujemy dla <math>n + 1</math>

::<math>x^{n + 1} = x \cdot x^n</math>

:::<math>\;\;\; = x \cdot [s^n + (x - s) \cdot R_{n - 1} (x)]</math>

:::<math>\;\;\; = x s^n + x (x - s) R_{n - 1} (x)</math>

:::<math>\;\;\; = [s + (x - s)] s^n + x (x - s) R_{n - 1} (x)</math>

:::<math>\;\;\; = s^{n + 1} + (x - s) s^n + x (x - s) R_{n - 1} (x)</math>

:::<math>\;\;\; = s^{n + 1} + (x - s) [s^n + x R_{n - 1} (x)]</math>

:::<math>\;\;\; = s^{n + 1} + (x - s) R_n (x)</math>

gdzie oznaczyliśmy <math>R_n (x) = s^n + x R_{n - 1} (x)</math>. Na mocy zasady indukcji matematycznej twierdzenie jest prawdziwe dla wszystkich liczb całkowitych dodatnich.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J8</span><br/>
Niech <math>W_n (x)</math> będzie dowolnym wielomianem stopnia <math>n \geqslant 1</math>. Wielomian <math>W_n (x)</math> można przedstawić w postaci

::<math>W_n (x) = W_n (s) + (x - s) V_{n - 1} (x)</math>

gdzie <math>V_{n - 1} (x)</math> jest wielomianem stopnia <math>n - 1</math>, a współczynniki wiodące wielomianów <math>W_n (x)</math> i <math>V_{n - 1} (x)</math> są sobie równe.

{{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>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math>, gdzie <math>a_n \neq 0</math>. Korzystając z twierdzenia J7, dostajemy

::<math>W_n (x) - W_n (s) = \sum_{k = 0}^{n} a_k x^k - \sum_{k = 0}^{n} a_k s^k</math>

::::::<math>\quad \,\, = \sum_{k = 1}^{n} a_k (x^k - s^k)</math>

::::::<math>\quad \,\, = \sum_{k = 1}^{n} a_k (x - s) R_{k - 1} (x)</math>

::::::<math>\quad \,\, = (x - s) \cdot \sum_{k = 1}^{n} a_k R_{k - 1} (x)</math>

::::::<math>\quad \,\, = (x - s) \cdot V_{n - 1} (x)</math>

gdzie oznaczyliśmy <math>V_{n - 1} (x) = \sum_{k = 1}^{n} a_k R_{k - 1} (x)</math>. Ponieważ wielomian <math>a_n R_{n - 1} (x)</math> ma najwyższy stopnień równy <math>n - 1</math>, to stopień wielomianu <math>V_{n - 1} (x)</math> jest równy <math>n - 1</math>.

Niech <math>V_{n - 1} (x) = \sum_{k = 0}^{n - 1} b_k x^k</math>. Mamy

::<math>\sum_{k = 0}^{n} a_k x^k - W_n (s) = \sum_{k = 0}^{n - 1} b_k x^{k + 1} - s \sum_{k = 0}^{n - 1} b_k x^k</math>

Porównując wyrazy o najwyższym stopniu, łatwo zauważamy, że <math>a_n = b_{n - 1}</math>. Czyli współczynnik wiodący wielomianu <math>V_{n - 1} (x)</math> jest równy <math>a_n</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Definicja J9</span><br/>
Wielomian <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math>, gdzie <math>a_0, \ldots, a_n \in \mathbb{Z}</math> oraz <math>a_n \neq 0</math>, będziemy nazywali wielomianem całkowitym stopnia <math>n</math>.



<span style="font-size: 110%; font-weight: bold;">Definicja J10</span><br/>
Powiemy, że wielomian całkowity <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math> jest stopnia <math>n</math> modulo <math>p</math>, gdzie <math>p</math> jest liczbą pierwszą, jeżeli <math>p \nmid a_n</math>. Jeżeli każdy współczynnik <math>a_k</math>, gdzie <math>k = 0, 1, \ldots, n</math>, jest podzielny przez <math>p</math>, to stopień wielomianu <math>W_n (x)</math> modulo <math>p</math> jest nieokreślony.



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J11</span><br/>
Niech <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math> będzie wielomianem całkowitym i <math>m \in \mathbb{Z}_+</math>. Jeżeli prawdziwa jest kongruencja <math>x \equiv y \!\! \pmod{m}</math>, to

::<math>W_n (x) \equiv W_n (y) \pmod{m}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Dla <math>k \geqslant 1</math> wyrażenie <math>x^k - y^k</math> jest podzielne przez <math>x - y</math>, co łatwo pokazać stosując indukcję matematyczną lub zauważając, że

::<math>x^k - y^k = (x - y) \sum_{j = 1}^{k} x^{k - j} y^{j - 1}</math>

Z założenia <math>m \mid (x - y)</math>, zatem dla <math>k \geqslant 1</math> mamy <math>m \mid (x^k - y^k)</math>. Wynika stąd, że prawdziwe są kongruencje

::<math>\begin{align}
  a_0 & \equiv a_0 \;\;\:\, \pmod{m}\\
  a_1 x & \equiv a_1 y \;\, \pmod{m}\\
  a_2 x^2 & \equiv a_2 y^2 \pmod{m}\\
   & \cdots \\
  a_n x^n & \equiv a_n y^n \pmod{m} \\
\end{align}</math>

Dodając wypisane kongruencje stronami, otrzymujemy

::<math>W_n (x) \equiv W_n (y) \pmod{m}</math>

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



<span style="font-size: 110%; font-weight: bold;">Uwaga J12</span><br/>
Niech <math>W(x)</math> będzie wielomianem całkowitym. Rozważmy kongruencję

::<math>W(x) \equiv 0 \pmod{m n} \qquad \qquad \qquad (1)</math>

gdzie liczby <math>m</math> i <math>n</math> są względnie pierwsze.

Kongruencja ta jest równoważna układowi kongruencji

::<math>\begin{align}
  W (x) &\equiv 0 \pmod{m} \\
  W (x) &\equiv 0 \pmod{n} \\
\end{align} \qquad \qquad \qquad \; (2)</math>

Zatem problem szukania rozwiązań kongruencji <math>(1)</math> możemy sprowadzić do szukania rozwiązań układu kongruencji <math>(2)</math>. W&nbsp;szczególności wynika stąd, że jeżeli któraś z&nbsp;kongruencji <math>(2)</math> nie ma rozwiązania, to kongruencja <math>W(x) \equiv 0 \!\! \pmod{m n}</math> również nie ma rozwiązania.

Załóżmy, że każda z&nbsp;kongruencji <math>(2)</math> ma przynajmniej jedno rozwiązanie i&nbsp;niech

:*&nbsp;&nbsp;&nbsp;<math>x \equiv a \!\! \pmod{m}</math> będzie pierwiastkiem kongruencji <math>W (x) \equiv 0 \!\! \pmod{m}</math>
:*&nbsp;&nbsp;&nbsp;<math>x \equiv b \!\! \pmod{n}</math> będzie pierwiastkiem kongruencji <math>W (x) \equiv 0 \!\! \pmod{n}</math>

Pierwiastki te tworzą układ kongruencji

::<math>\begin{align}
 x &\equiv a \pmod{m} \\
 x &\equiv b \pmod{n} \\
\end{align} \qquad \qquad \qquad \qquad (3)</math>

Z chińskiego twierdzenia o&nbsp;resztach wiemy, że układ ten możemy zapisać w&nbsp;postaci równoważnej

::<math>x \equiv c \pmod{m n}</math>

Zauważmy, że liczba <math>c</math> określona modulo <math>m n</math> jest rozwiązaniem kongruencji <math>(1)</math>. Istotnie z&nbsp;twierdzenia J11 mamy

::<math>\begin{align}
  W (c) &\equiv W (a) \equiv 0 \pmod{m} \\
  W (c) &\equiv W (b) \equiv 0 \pmod{n} \\
\end{align}</math>

ale liczby <math>m, n</math> są względnie pierwsze, zatem otrzymujemy, że

::<math>W (c) \equiv 0 \pmod{m n}</math>

Wynika stąd, że każdemu układowi rozwiązań <math>(3)</math> odpowiada dokładnie jedno rozwiązanie kongruencji <math>(1)</math>.

Podsumujmy: jeżeli kongruencje

::<math>\begin{align}
  W (x) &\equiv 0 \pmod{m} \\
  W (x) &\equiv 0 \pmod{n} \\
\end{align}</math>

mają odpowiednio <math>r</math> i <math>s</math> pierwiastków, to liczba różnych układów kongruencji <math>(3)</math> jest równa iloczynowi <math>r s</math> i&nbsp;istnieje <math>r s</math> różnych rozwiązań kongruencji

::<math>W(x) \equiv 0 \pmod{m n}</math>





== Twierdzenie Lagrange'a ==

<span style="font-size: 110%; font-weight: bold;">Twierdzenie J13</span><br/>
Kongruencja

::<math>a_1 x + a_0 \equiv 0 \pmod{p}</math>

gdzie <math>p \nmid a_1</math>, ma dokładnie jedno rozwiązanie modulo <math>p</math>.

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

'''A. Istnienie rozwiązania'''

Ponieważ rozpatrywaną kongruencję możemy zapisać w&nbsp;postaci <math>a_1 x + a_0 = k p</math>, to istnienie liczb <math>x</math> i <math>k</math>, dla których ta równość jest prawdziwa, wynika z&nbsp;twierdzenia C76. Poniżej przedstawimy jeszcze jeden sposób znalezienia rozwiązania.

Ponieważ <math>\gcd (a_1, p) = 1</math>, to istnieją takie liczby <math>r, s</math>, że <math>a_1 r + p s = 1</math> (zobacz C73 - lemat Bézouta). Zauważmy, że <math>p \nmid r</math>, bo gdyby tak było, to liczba pierwsza <math>p</math> dzieliłaby wyrażenie <math>a_1 r + p s</math>, ale jest to niemożliwe, bo <math>a_1 r + p s = 1</math>. Czyli modulo <math>p</math> mamy

::<math>a_1 r \equiv 1 \pmod{p}</math>

Mnożąc rozpatrywaną kongruencję przez <math>r</math>, otrzymujemy

::<math>a_1 r x + a_0 r \equiv 0 \pmod{p}</math>

Zatem

::<math>x \equiv - a_0 r \pmod{p}</math>

'''B. Brak innych rozwiązań'''

Przypuśćmy, że istnieją dwa różne rozwiązania kongruencji

::<math>a_1 x + a_0 \equiv 0 \pmod{p}</math>

Jeśli oznaczymy je przez <math>x_1</math> i <math>x_2</math>, to otrzymamy

::<math>a_1 x_1 + a_0 \equiv 0 \equiv a_1 x_2 + a_0 \pmod{p}</math>

Czyli

::<math>a_1 x_1 \equiv a_1 x_2 \pmod{p}</math>

::<math>p \mid a_1 (x_1 - x_2)</math>

Ponieważ <math>p \nmid a_1</math>, to z&nbsp;lematu Euklidesa (C74) otrzymujemy natychmiast <math>p \mid (x_1 - x_2)</math>. Skąd wynika, że <math>x_1 \equiv x_2 \!\! \pmod{p}</math>, wbrew założeniu, że <math>x_1</math> i <math>x_2</math> są dwoma różnymi rozwiązaniami. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J14 (Joseph Louis Lagrange, 1768)</span><br/>
Jeżeli wielomian <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math> ma stopień <math>n</math> modulo <math>p</math>, gdzie <math>n \geqslant 1</math>, to kongruencja

::<math>W_n (x) \equiv 0 \pmod{p}</math>

ma co najwyżej <math>n</math> rozwiązań.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Indukcja matematyczna. Z&nbsp;J13 wiemy, że dowodzone twierdzenie jest prawdziwe dla <math>n = 1</math>. Załóżmy, że twierdzenie jest prawdziwe dla wszystkich liczb całkowitych dodatnich nie większych od <math>n - 1</math>. Niech wielomian <math>W_n (x)</math> ma stopień <math>n</math> modulo <math>p</math>. Jeżeli kongruencja

::<math>W_n (x) \equiv 0 \pmod{p}</math>

nie ma żadnego rozwiązania, to dowodzone twierdzenie jest prawdziwe dla <math>n</math>. Przypuśćmy teraz, że wypisana wyżej kongruencja ma przynajmniej jeden pierwiastek <math>x \equiv s \!\! \pmod{p}</math>. Korzystając z&nbsp;twierdzenia J8, możemy napisać

::<math>W_n (x) - W_n (s) = (x - s) V_{n - 1} (x)</math>

gdzie wielomian <math>V_{n - 1} (x)</math> ma stopień <math>n - 1</math> modulo <math>p</math>, bo wielomiany <math>W_n (x)</math> oraz <math>V_{n - 1} (x)</math> mają jednakowe współczynniki wiodące.


Z założenia <math>x \equiv s \!\! \pmod{p}</math> jest jednym z&nbsp;pierwiastków kongruencji <math>W_n (x) \equiv 0 \!\! \pmod{p}</math>, zatem modulo <math>p</math> otrzymujemy

::<math>W_n (x) \equiv (x - s) V_{n - 1} (x) \pmod{p}</math>

Ponieważ <math>p</math> jest liczbą pierwszą, to z&nbsp;rozpatrywanej kongruencji

::<math>W_n (x) \equiv 0 \pmod{p}</math>

wynika, że musi być (zobacz C74)

::<math>x \equiv s \pmod{p} \qquad \qquad \text{lub} \qquad \qquad V_{n - 1} (x) \equiv 0 \pmod{p}</math>


Z założenia indukcyjnego kongruencja

::<math>V_{n - 1} (x) \pmod{p}</math>

ma co najwyżej <math>n - 1</math> rozwiązań, zatem kongruencja

::<math>W_n (x) \equiv 0 \pmod{p}</math>

ma nie więcej niż <math>n</math> rozwiązań. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J15</span><br/>
Jeżeli kongruencja

::<math>a_n x^n + a_{n - 1} x^{n - 1} + \ldots + a_1 x + a_0 \equiv 0 \pmod{p}</math>

ma więcej niż <math>n</math> rozwiązań, to wszystkie współczynniki <math>a_k</math>, gdzie <math>k = 0, \ldots, n</math>, muszą być podzielne przez <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 \{ 0, 1, \ldots, n \}</math> będzie zbiorem takim, że dla każdego <math>k \in S</math> jest <math>p \nmid a_k</math>. Przypuśćmy, że <math>S</math> jest zbiorem niepustym. Niech <math>j</math> oznacza największy element zbioru <math>S</math>. Jeżeli <math>j = 0</math>, to wielomian <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math> jest stopnia <math>0</math> modulo <math>p</math> i

::<math>a_0 \not\equiv 0 \pmod{p}</math>

Konsekwentnie, dla dowolnego <math>x \in \mathbb{Z}</math> jest

::<math>a_n x^n + a_{n - 1} x^{n - 1} + \ldots + a_1 x + a_0 \not\equiv 0 \pmod{p}</math>

bo dla każdego <math>1 \leqslant k \leqslant n</math> mamy <math>a_k \equiv 0 \!\! \pmod{p}</math>. Zatem rozpatrywana kongruencja nie ma ani jednego rozwiązania, czyli rozwiązań nie może być więcej niż <math>n</math>.

W przypadku gdy <math>j \neq 0</math>, z&nbsp;twierdzenia Lagrange'a wynika, że rozpatrywana kongruencja ma nie więcej niż <math>j \leqslant n</math> rozwiązań, ponownie wbrew założeniu, że kongruencja ta ma więcej niż <math>n</math> rozwiązań. Uczynione przypuszczenie, że <math>S</math> jest zbiorem niepustym, okazało się fałszywe, zatem zbiór <math>S</math> musi być zbiorem pustym. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Przykład J16</span><br/>
Z twierdzenia Lagrange'a wynika, że kongruencja

::<math>x^p - x - 1 \equiv 0 \pmod{p}</math>

ma co najwyżej <math>p</math> rozwiązań. W&nbsp;rzeczywistości nie ma ani jednego rozwiązania, bo z&nbsp;twierdzenia Fermata wiemy, że dla dowolnej liczby pierwszej <math>p</math> jest

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



<span style="font-size: 110%; font-weight: bold;">Przykład J17</span><br/>
Zauważmy, że w&nbsp;przypadku, gdy <math>n \geqslant p</math>, możemy zawsze wielomian przekształcić do postaci takiej, że <math>n < p</math>. Niech <math>p = 5</math> i 

::<math>W(x) = x^{15} + 11 x^{11} + 5 x^5 + 2 x^2 + x + 1</math>

Ponieważ <math>x^5 \equiv x \!\! \pmod{5}</math>, to

::<math>W(x) \equiv x^3 + 11 x^3 + 5 x + 2 x^2 + x + 1 \equiv 12 x^3 + 2 x^2 + 6 x + 1 \pmod{5}</math>

Co wynika również z&nbsp;faktu, że <math>W(x)</math> można zapisać w&nbsp;postaci

::<math>W(x) = x^{15} + 11 x^{11} + 5 x^5 + 2 x^2 + x + 1 = (x^5 - x) (x^{10} + 12 x^6 + 12 x^2 + 5) + 12 x^3 + 2 x^2 + 6 x + 1</math>

ale <math>x^5 - x \equiv 0 \!\! \pmod{5}</math> na mocy twierdzenia Fermata.

W PARI/GP polecenie

 <span style="font-size: 90%; color:black;">Mod(x^15 + 11*x^11 + 5*x^5 + 2*x^2 + x + 1, x^5 - x)</span>

znajduje resztę z dzielenia wielomianu <math>x^{15} + 11 x^{11} + 5 x^5 + 2 x^2 + x + 1</math> przez wielomian <math>x^5 - x</math>. Tutaj otrzymujemy

 <span style="font-size: 90%; color:black;">Mod(12*x^3 + 2*x^2 + 6*x + 1, x^5 - x)</span>





== Twierdzenie Wilsona ==

<span style="font-size: 110%; font-weight: bold;">Twierdzenie J18 (John Wilson, 1770)</span><br/>
Liczba całkowita <math>p \geqslant 2</math> jest liczbą pierwszą wtedy i&nbsp;tylko wtedy, gdy

::<math>(p - 1) ! \equiv - 1 \pmod{p}</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>

Przypuśćmy, że prawdziwa jest kongruencja <math>(p - 1) ! \equiv - 1 \!\! \pmod{p}</math> oraz <math>p</math> jest liczbą złożoną. Zatem liczba <math>p</math> ma dzielnik <math>d</math> taki, że <math>2 \leqslant d \leqslant p - 1</math>. Ponieważ <math>d \mid p ,</math> to prawdziwa jest kongruencja

::<math>(p - 1) ! \equiv - 1 \pmod{d}</math>

czyli

::<math>0 \equiv - 1 \pmod{d}</math>

co jest niemożliwe.

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

Łatwo sprawdzamy, że twierdzenie jest prawdziwe dla <math>p = 2</math>. Niech teraz <math>p</math> będzie liczbą pierwszą nieparzystą. Rozważmy wielomiany

::<math>W(x) = (x - 1) (x - 2) \cdot \ldots \cdot (x - (p - 1))</math>

oraz

::<math>V(x) = x^{p - 1} - 1</math>

Zauważmy, że

:* stopnie tych wielomianów są równe <math>p - 1</math>
:* współczynniki wiodące są równe <math>1</math>
:* wyrazy wolne są równe odpowiednio <math>(p - 1) !</math> oraz <math>- 1</math>
:* wielomiany mają <math>p - 1</math> rozwiązań modulo <math>p</math>

Niech

::<math>U(x) = W (x) - V (x)</math>

Zauważmy, że

:* stopień wielomianu <math>U(x)</math> jest równy <math>p - 2 \geqslant 1</math>, ponieważ wyrazy o&nbsp;najwyższym stopniu uległy redukcji 
:* wielomian <math>U(x)</math> ma <math>p - 1</math> rozwiązań modulo <math>p</math>, bo dla każdego <math>k \in \{ 1, 2, \ldots, p - 1 \}</math> mamy <math>U(k) = W (k) - V (k) \equiv 0 \!\! \pmod{p}</math>

Z twierdzenia Lagrange'a wiemy, że wielomian <math>U(x)</math> nie może mieć więcej niż <math>p - 2</math> rozwiązań modulo <math>p</math>. Zatem z&nbsp;twierdzenia J15 wynika natychmiast, że liczba pierwsza <math>p</math> musi dzielić każdy współczynnik <math>a_k</math> wielomianu <math>U(x)</math> i&nbsp;w&nbsp;szczególności musi dzielić wyraz wolny, który jest równy <math>(p - 1) ! + 1</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J19</span><br/>
Liczba całkowita nieparzysta <math>p \geqslant 3</math> jest liczbą pierwszą wtedy i&nbsp;tylko wtedy, gdy

::<math>\left[ \left( {\small\frac{p - 1}{2}} \right) ! \right]^2 \equiv (- 1)^{\tfrac{p + 1}{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 twierdzenia Wilsona wiemy, że liczba całkowita <math>p \geqslant 2</math> jest liczbą pierwszą wtedy i&nbsp;tylko wtedy, gdy

::<math>(p - 1) ! \equiv - 1 \pmod{p}</math>

W przypadku, gdy liczba <math>p</math> jest liczbą nieparzystą możemy powyższy wzór łatwo przekształcić. Ponieważ czynniki w <math>(p - 1) !</math> są określone modulo <math>p</math>, to odejmując od każdego czynnika większego od <math>{\small\frac{p - 1}{2}}</math> liczbę <math>p</math>, otrzymujemy

::<math>1 \cdot 2 \cdot \ldots \cdot {\small\frac{p - 3}{2}} \cdot {\small\frac{p - 1}{2}} \cdot \left( {\small\frac{p + 1}{2}} - p \right) \left( {\small\frac{p + 3}{2}} - p \right) \cdot \ldots \cdot (- 2) \cdot (- 1) \equiv - 1 \!\! \pmod{p}</math>

::<math>(- 1)^{\tfrac{p - 1}{2}} \cdot \left[ \left( {\small\frac{p - 1}{2}} \right) ! \right]^2 \equiv - 1 \!\! \pmod{p}</math>

::<math>\left[ \left( {\small\frac{p - 1}{2}} \right) ! \right]^2 \equiv (- 1)^{\tfrac{p + 1}{2}} \!\! \pmod{p}</math>

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



<span style="font-size: 110%; font-weight: bold;">Zadanie J20</span><br/>
Pokazać, że jeżeli <math>p</math> jest liczbą pierwszą nieparzystą, to <math>(p - 2) ! \equiv 1 \!\! \pmod{p}</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Niech <math>S</math> będzie zbiorem liczb całkowitych dodatnich mniejszych od <math>p</math>, czyli <math>S = \{ 1, 2, \ldots, p - 1 \}</math>. Podstawą dowodu jest spostrzeżenie, że tylko dwie liczby należące do <math>S</math> są swoimi odwrotnościami modulo <math>p</math>.
Pozostałe liczby są wzajemnie swoimi odwrotnościami modulo <math>p</math>.

Jeżeli liczba <math>x</math> jest swoją odwrotnością modulo <math>p</math>, to musi być

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

Łatwo zauważamy, że istnieją dwa rozwiązania <math>x \equiv 1 \!\! \pmod{p} \,</math> i <math>\, x \equiv - 1 \!\! \pmod{p} ,</math> a z twierdzenia Lagrange'a (J14) wiemy, że są to wszystkie rozwiązania. Wynika stąd, że w zbiorze <math>S</math> liczby <math>1 \,</math> i <math>\, p - 1</math> są swoimi odwrotnościami modulo <math>p ,</math> a pozostałe liczby <math>2, \ldots, p - 2</math> są wzajemnie swoimi odwrotnościami modulo <math>p ,</math> czyli można połączyć je w pary <math>a, b</math> takie, że <math>a \neq b \,</math> i <math>\, a \cdot b \equiv 1 \!\! \pmod{p} .</math> Tworząc iloczyn wszystkich takich par, otrzymujemy

::<math>(a \cdot b) \cdot (c \cdot d) \cdot \ldots \cdot (x \cdot y) \equiv 1 \!\! \pmod{p}</math>

Oczywiście iloczyn po lewej stronie wyczerpuje wszystkie liczby <math>2, 3, \ldots, p - 2 ,</math> zatem

::<math>2 \cdot 3 \cdot \ldots \cdot (p - 2) \equiv 1 \!\! \pmod{p}</math>

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



<span style="font-size: 110%; font-weight: bold;">Zadanie J21</span><br/>
Pokazać, że jeżeli <math>m \geqslant 6</math> jest liczbą złożoną, to <math>(m - 1) ! \equiv 0 \!\! \pmod{m}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Ponieważ <math>m</math> jest liczbą złożoną, to możemy zapisać <math>m</math> w postaci <math>m = a b ,</math> gdzie liczby <math>a, b</math> spełniają warunek <math>1 < a, b < m .</math> Rozpatrzmy najpierw przypadek kiedy <math>a \neq b ,</math> wtedy w iloczynie <math>1 \cdot 2 \cdot \ldots \cdot (m - 1)</math> występują obydwa czynniki <math>a \,</math> i <math>\, b</math>, zatem <math>a b \mid (m - 1) !</math>

Rozważmy teraz przypadek gdy <math>m = a^2</math>. Jeśli <math>m - 1 \geqslant 2 a ,</math> to w iloczynie <math>1 \cdot 2 \cdot \ldots \cdot (m - 1)</math> pojawi się czynnik <math>a</math> oraz <math>2 a ,</math> wobec tego <math>a^2 \mid (m - 1) !</math> Ponieważ z warunków <math>m = a^2</math> oraz <math>m - 1 \geqslant 2 a</math> wynika, że <math>a \geqslant 3 ,</math> to jedynie dla <math>m = 2^2 = 4</math> twierdzenie nie jest prawdziwe. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}





== Twierdzenie Fermata ==
<span style="font-size: 110%; font-weight: bold;">Twierdzenie J22 (Pierre de Fermat, 1640)</span><br/>
Niech <math>a \in \mathbb{Z}</math>. Jeżeli <math>p</math> jest liczbą pierwszą

:* to liczba <math>a^p - a</math> jest podzielna przez <math>p</math>, czyli <math>a^p \equiv a \!\! \pmod p</math>
:* i&nbsp;jeśli dodatkowo <math>p \nmid a</math>, to liczba <math>a^{p - 1} - 1</math> jest podzielna przez <math>p</math>, czyli <math>a^{p - 1} \equiv 1 \!\! \pmod p</math>

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

Zauważmy, że<br/>
a) twierdzenie jest prawdziwe dla <math>a = 0</math><br/>
b) w&nbsp;przypadku, gdy <math>p = 2</math> wyrażenie <math>a^p - a = a^2 - a = a (a - 1)</math> jest podzielne przez <math>2</math>, bo jedna z&nbsp;liczb <math>a - 1</math> i <math>a</math> jest liczbą parzystą<br/>
c) w&nbsp;przypadku, gdy <math>p</math> jest liczbą pierwszą nieparzystą i&nbsp;twierdzenie jest prawdziwe dla <math>a \geqslant 1</math>, to jest też prawdziwe dla <math>- a</math>, bo
::<math>(- a)^p - (- a) = (- 1)^p a^p + a = - a^p + a = - (a^p - a)</math><br/>


Zatem wystarczy pokazać, że dla ustalonej liczby pierwszej nieparzystej <math>p</math> twierdzenie jest prawdziwe dla każdego <math>a \in \mathbb{Z}_+</math>.

Indukcja matematyczna. Dla <math>a = 1</math> mamy <math>1^p - 1 = 0</math> zatem liczba pierwsza <math>p</math> jest dzielnikiem rozważanego wyrażenia. Zakładając, że twierdzenie jest prawdziwe dla <math>a</math>, czyli <math>p \mid a^p - a</math>, otrzymujmy dla <math>a + 1</math>

::<math>(a + 1)^p - (a + 1) = \sum_{k = 0}^{p} \binom{p}{k} \cdot a^k - a - 1</math>

:::::::<math>\;\;\,\, = 1 + \sum_{k = 1}^{p - 1} \binom{p}{k} \cdot a^k + a^p - a - 1</math>

:::::::<math>\;\;\,\, = a^p - a + \sum^{p - 1}_{k = 1} \binom{p}{k} \cdot a^k</math>


Z założenia indukcyjnego <math>p \mid a^p - a</math>, zaś <math>\binom{p}{k} = {\small\frac{p!}{k! \cdot (p - k) !}}</math> dla <math>k = 1, 2, \ldots, p - 1</math> jest podzielne przez <math>p</math> (ponieważ <math>p</math> dzieli licznik, ale nie dzieli mianownika). Zatem <math>(a + 1)^p - (a + 1)</math> jest podzielne przez liczbę pierwszą <math>p</math>.

'''Punkt 2.'''

Z punktu 1. wiemy, że liczba pierwsza <math>p</math> dzieli <math>a^p - a = a (a^{p - 1} - 1)</math>. Jeżeli <math>p \nmid a</math>, to z&nbsp;lematu Euklidesa (zobacz twierdzenie C74) wynika natychmiast, że <math>p</math> dzieli <math>a^{p - 1} - 1</math>.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J23</span><br/>
Niech <math>x, y \in \mathbb{Z}</math>. Jeżeli <math>\gcd (x, y) = 1</math> i&nbsp;liczba pierwsza nieparzysta <math>p</math> dzieli <math>x^2 + y^2</math>, to <math>p</math> jest postaci <math>4 k + 1</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>x^2 \equiv - y^2 \!\! \pmod{p}</math>

Przypuśćmy, że <math>p \mid y</math>. Wtedy z&nbsp;powyższej kongruencji mamy natychmiast, że <math>p \mid x</math>, wbrew założeniu, że <math>\gcd (x, y) = 1</math>. Zatem <math>p \nmid y</math> i&nbsp;z&nbsp;twierdzenia Fermata dostajemy

::<math>1 \equiv x^{p - 1} \equiv (x^2)^{\tfrac{p - 1}{2}} \equiv (- y^2)^{\tfrac{p - 1}{2}} \equiv y^{p - 1} \cdot (- 1)^{\tfrac{p - 1}{2}} \equiv (- 1)^{\tfrac{p - 1}{2}} \!\! \pmod{p}</math>

Wynika stąd, że <math>{\small\frac{p - 1}{2}}</math> musi być liczbą parzystą, czyli <math>p = 4 k + 1</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie J24</span><br/>
Niech <math>x, y, n \geqslant 0</math>. Pokazać, że jedynymi rozwiązaniami równania

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

są liczby

:* <math>x = 2^{n / 2} \,</math> i <math>\, y = 0 \,</math> lub <math>\, x = 0 \,</math> i <math>\, y = 2^{n / 2}</math>, gdy <math>2 \mid n</math>
:* <math>x = y = 2^{(n - 1) / 2}</math>, gdy <math>2 \nmid n</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
'''A.''' Gdy jedna z&nbsp;liczb <math>x, y</math> jest równa <math>0</math> (powiedzmy <math>y</math>), to mamy <math>x = 2^{n / 2}</math>, gdy <math>n</math> jest parzyste. Gdy <math>n</math> jest nieparzyste, to rozwiązanie nie istnieje. Od tej pory będziemy zakładali, że <math>x, y \geqslant 1</math>

'''B.''' Wiemy, że kwadrat liczby nieparzystej przystaje do <math>1</math> modulo <math>4</math>. Gdy obie liczby <math>x, y</math> są nieparzyste, to modulo <math>4</math> mamy

::<math>2 \equiv 2^n \!\! \pmod{4}</math>

Kongruencja ta jest prawdziwa tylko dla <math>n = 1</math> i&nbsp;w&nbsp;tym przypadku mamy <math>(x, y) = (1, 1)</math>.

'''C.''' W&nbsp;przypadku, gdy obie liczby są parzyste, możemy napisać <math>x = 2^a u</math>, <math>y = 2^b w</math>, gdzie liczby <math>u, w</math> są nieparzyste. Nie zmniejszając ogólności możemy założyć, że <math>1 \leqslant a \leqslant b < {\small\frac{n}{2}}</math>. Dostajemy

::<math>u^2 + 2^{2 b - 2 a} w^2 = 2^{n - 2 a}</math>

Widzimy, że nie może być <math>a < b</math>, bo suma liczby nieparzystej i&nbsp;parzystej nie jest liczbą parzystą. Zatem <math>a = b</math> i&nbsp;otrzymujemy równanie

::<math>u^2 + w^2 = 2^{n - 2 a}</math>

które ma rozwiązanie w&nbsp;liczbach nieparzystych tylko dla wykładnika <math>n - 2 a = 1</math>. Mamy <math>u = w = 1</math>, zatem <math>x = y = 2^{(n - 1) / 2}</math> i <math>n</math> musi być liczbą nieparzystą.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J25</span><br/>
Niech <math>x, y \in \mathbb{Z}_+</math>. Jeżeli <math>x \neq y</math>, to liczba <math>x^2 + y^2</math> ma dzielnik pierwszy postaci <math>4 k + 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
W&nbsp;przypadku, gdy <math>x = y</math> mamy <math>x^2 + y^2 = 2 y^2</math> i&nbsp;jeśli liczba <math>y</math> nie ma dzielnika pierwszego postaci <math>4 k + 1</math>, to nie ma go również liczba <math>2 y^2</math>. Przykładowo <math>x^2 + y^2 = 2 y^2 = 2^{2 r + 1}, 2 \cdot 3^{2 r}, 2 \cdot 7^{2 r}</math>. Dlatego zakładamy, że <math>x \neq y</math>. Analogiczna sytuacja ma miejsce, gdy jedna z&nbsp;liczb <math>x, y</math> jest równa zero. Dlatego zakładamy, że <math>x, y \in \mathbb{Z}_+</math>.

Niech <math>\gcd (x, y) = d</math>, zatem mamy <math>x = a d</math>, <math>y = b d</math>. Wynika stąd, że <math>x^2 + y^2 = d^2 (a^2 + b^2)</math>, gdzie <math>\gcd (a, b) = 1 \,</math> i <math>\, a \neq b</math>. Ponieważ <math>\, a \neq b</math>, to liczba <math>a^2 + b^2</math> musi mieć dzielnik pierwszy nieparzysty (zobacz J24). Z&nbsp;twierdzenia J23 zastosowanego do liczby <math>a^2 + b^2</math> wynika, że <math>a^2 + b^2</math> musi mieć dzielnik pierwszy postaci <math>4 k + 1</math>.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie J26</span><br/>
Pokazać, że jeżeli <math>m \in \mathbb{Z}_+</math>, to <math>m \geqslant 2</math> nie jest dzielnikiem liczby <math>2^m - 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Ponieważ liczby parzyste nie mogą dzielić liczby nieparzystej <math>2^m - 1</math>, to możemy założyć, że <math>m</math> jest liczbą nieparzystą. Zatem <math>\gcd (m, 2) = 1</math> i liczba <math>2</math> ma element odwrotny modulo <math>m</math>.

Niech <math>p</math> będzie najmniejszym dzielnikiem pierwszym liczby nieparzystej <math>m</math>, wtedy <math>\gcd (m, p - 1) = 1</math> i z lematu Bezout'a (zobacz C73) istnieją takie liczby całkowite <math>x, y</math>, że

::<math>m x + (p - 1) y = 1</math>

Załóżmy, dla uzyskania sprzeczności, że <math>m \mid (2^m - 1)</math>. Zatem

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

i dostajemy

::<math>2 = 2^1 = 2^{m x + (p - 1) y} \equiv (2^m)^x \cdot (2^{p - 1})^y \equiv 1 \!\! \pmod{p}</math>

Co jest niemożliwe.<br/>
&#9633;
{{\Spoiler}}





== Twierdzenie Eulera ==

Twierdzenie Eulera jest uogólnieniem twierdzenia Fermata.<br/>
<span style="font-size: 110%; font-weight: bold;">Twierdzenie J27 (Leonhard Euler, 1763)</span><br/>
Niech <math>a \in \mathbb{Z}</math>, <math>m \in \mathbb{Z}_+</math> oraz <math>\gcd (a, m) = 1</math>, wtedy

::<math>a^{\varphi (m)} \equiv 1 \!\! \pmod{m}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Łatwo zauważyć, że twierdzenie jest prawdziwe dla <math>m = 1, 2</math>, zatem będziemy rozpatrywali przypadek, gdy <math>m \geqslant 3</math>.

Niech <math>R = \{ r_1, r_2, \ldots, r_{\varphi (m)} \}</math> będzie zbiorem wszystkich liczb całkowitych dodatnich nie większych od <math>m</math> i względnie pierwszych z <math>m</math>. Niech <math>S = \{ a r_1, a r_2, \ldots, a r_{\varphi (m)} \}</math>. Prosta analiza właściwości zbiorów <math>R</math> i <math>S</math> stanowi podstawę dowodu twierdzenia.

'''1. Wszystkie elementy w <math>\boldsymbol{R}</math> są różne modulo <math>\boldsymbol{m}</math>'''

Nie może być <math>r_i \equiv r_j \!\! \pmod{m}</math> dla różnych <math>i, j</math>, bo dla <math>m \geqslant 3</math> mamy oszacowanie <math>1 \leqslant r_i, r_j \leqslant m - 1</math>, skąd otrzymujemy <math>0 \leqslant | r_i - r_j | \leqslant m - 2</math>. Wynika stąd, że <math>m \mid (r_i - r_j)</math> tylko w przypadku, gdy <math>r_i = r_j</math>, czyli gdy <math>i = j</math>.

'''2. Wszystkie elementy w <math>\boldsymbol{S}</math> są względnie pierwsze z <math>\boldsymbol{m}</math>'''

Z definicji dowolna liczba <math>r_i \in R</math> jest względnie pierwsza z <math>m</math> oraz z założenia <math>\gcd (a, m) = 1</math>. Z twierdzenia H6 otrzymujemy natychmiast, że <math>\gcd (a r_i, m) = 1</math>.

'''3. Wszystkie elementy w <math>\boldsymbol{S}</math> są różne modulo <math>m</math>'''

Załóżmy, dla uzyskania sprzeczności, że dla różnych wskaźników <math>i, j</math> jest <math>a r_i \equiv a r_j \!\! \pmod{m}</math>. Ponieważ <math>\gcd (a, m) = 1</math>, to liczba <math>a</math> ma element odwrotny modulo <math>m</math>. Mnożąc obie strony kongruencji przez <math>a^{- 1}</math> otrzymujemy <math>r_i \equiv r_j \!\! \pmod{m}</math> dla różnych <math>i, j</math>, co jest niemożliwe (zobacz punkt 1).

'''4. Każdy element w <math>\boldsymbol{S}</math> jest równy modulo <math>\boldsymbol{m}</math> pewnemu elementowi w <math>\boldsymbol{R}</math>'''

Dla każdego <math>i = 1, \ldots, \varphi (m)</math> liczba <math>a r_i \in S</math> może być zapisana w postaci <math>a r_i = k m + r</math>, gdzie <math>k \in \mathbb{Z} \;</math> i <math>\; 0 \leqslant r < m</math>. Ponieważ

::<math>\gcd (a r_i, m) = 1 = \gcd (k m + r, m) = \gcd (r, m)</math>

to <math>r \in R</math> i musi być <math>a r_i \equiv r_j \!\! \pmod{m}</math> dla pewnego <math>r_j \in R</math>.


Z punktów 1., 2. i 4. wynika natychmiast, że zbiory <math>R</math> i <math>S</math> są równe modulo <math>m</math> (zobacz H24), zatem

::<math>a r_1 \cdot a r_2 \cdot \ldots \cdot a r_{\varphi (m)} \equiv r_1 \cdot r_2 \cdot \ldots \cdot r_{\varphi (m)} \!\! \pmod{m}</math>

::<math>r_1 \cdot r_2 \cdot \ldots \cdot r_{\varphi (m)} \cdot a^{\varphi (m)} \equiv r_1 \cdot r_2 \cdot \ldots \cdot r_{\varphi (m)} \!\! \pmod{m}</math>

Ale <math>\gcd (r_1 r_2 \cdot \ldots \cdot r_{\varphi (m)}, m) = 1</math> i mnożąc obie strony powyższej kongruencji przez element odwrotny do <math>r_1 r_2 \cdot \ldots \cdot r_{\varphi (m)}</math> modulo <math>m</math>, otrzymujemy

::<math>a^{\varphi (m)} \equiv 1 \!\! \pmod{m}</math>

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



<span style="font-size: 110%; font-weight: bold;">Zadanie J28</span><br/>
Niech <math>m \in \mathbb{Z}_+</math>, zaś <math>a, b \in \mathbb{Z}</math>. Pokazać, że jeżeli <math>\gcd (a, m) = 1</math>, to kongruencja <math>a x \equiv b \!\! \pmod{m}</math> ma jednoznaczne rozwiązanie równe

::<math>x \equiv a^{\varphi (m) - 1} \cdot b \!\! \pmod{m}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Z twierdzenia Eulera wynika, że jeżeli <math>\gcd (a, m) = 1</math>, to elementem odwrotnym do <math>a</math> modulo <math>m</math> jest <math>a^{\varphi (m) - 1}</math>. Istotnie

::<math>a^{\varphi (m) - 1} \cdot a = a^{\varphi (m)} \equiv 1 \!\! \pmod{m}</math>

Zatem mnożąc obie strony kongruencji <math>a x \equiv b \!\! \pmod{m}</math> przez <math>a^{\varphi (m) - 1}</math>, otrzymujemy

::<math>a^{\varphi (m) - 1} \cdot a x = a^{\varphi (m)} \cdot x \equiv x \equiv a^{\varphi (m) - 1} \cdot b \!\! \pmod{m}</math>

::<math>x \equiv a^{\varphi (m) - 1} \cdot b \!\! \pmod{m}</math>

Co było do pokazania.<br/>
&#9633;
{{\Spoiler}}





== Kryterium Eulera ==

<span style="font-size: 110%; font-weight: bold;">Definicja J29</span><br/>
Niech <math>p</math> będzie liczbą pierwszą i <math>a \in \mathbb{Z}</math>. Powiemy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>p</math>, jeżeli kongruencja

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

ma rozwiązanie, czyli istnieje taka liczba <math>k \in \mathbb{Z}</math>, że <math>p \mid (k^2 - a)</math>.

Powiemy, że liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math>, jeżeli kongruencja

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

nie ma rozwiązania.



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J30</span><br/>
Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą, to wśród liczb <math>1, 2, \ldots, p - 1</math> istnieje 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>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Zauważmy, że w&nbsp;rozważanym zbiorze liczb <math>\{ 1, 2, \ldots, p - 1 \}</math>, kwadraty liczb <math>k</math> i <math>p - k</math> są takimi samymi liczbami modulo <math>p</math>, co wynika z&nbsp;oczywistej kongruencji

::<math>k^2 \equiv (p - k)^2 \pmod{p}</math>

Pozwala to wypisać pary liczb, których kwadraty są identyczne modulo <math>p</math>

::<math>(1, p - 1), (2, p - 2), \ldots, \left( {\small\frac{p - 1}{2}}, p - {\small\frac{p - 1}{2}} \right)</math>

Ponieważ

::<math>p - {\small\frac{p - 1}{2}} = {\small\frac{p + 1}{2}} = {\small\frac{p - 1}{2}} + 1</math>

to wypisane pary wyczerpują cały zbiór <math>\{ 1, 2, \ldots, p - 1 \}</math>. Co więcej, liczby <math>1^2, 2^2, \ldots, \left( {\small\frac{p - 1}{2}} \right)^2</math> są wszystkie różne modulo <math>p</math>. Istotnie, przypuśćmy, że <math>1 \leqslant i, j \leqslant {\small\frac{p - 1}{2}}</math> oraz <math>i \neq j</math>, a&nbsp;jednocześnie <math>i^2 \equiv j^2 \!\! \pmod{p}</math>. Gdyby tak było, to mielibyśmy

::<math>(i - j) (i + j) \equiv 0 \pmod{p}</math>

Łatwo zauważamy, że jest to niemożliwe, bo żaden z&nbsp;czynników nie jest podzielny przez <math>p</math>, co wynika z&nbsp;prostych oszacowań

::<math>1 \leqslant | i - j | \leqslant i + j < p - 1</math>

::<math>2 < i + j < p - 1</math>


Ponieważ (z definicji) liczba <math>a</math> jest liczbą kwadratową modulo <math>p</math>, jeżeli kongruencja

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

ma rozwiązanie, to liczba kwadratowa modulo <math>p</math> musi przystawać do pewnego kwadratu modulo <math>p</math>.

Wynika stąd, że różnych liczb kwadratowych modulo <math>p</math> jest tyle samo, co kwadratów <math>1^2, 2^2, \ldots, \left( {\small\frac{p - 1}{2}} \right)^2</math>. Czyli jest ich dokładnie <math>{\small\frac{p - 1}{2}}</math>. Pozostałe liczby w&nbsp;zbiorze <math>\{ 1, 2, \ldots, p - 1 \}</math> to liczby niekwadratowe modulo <math>p</math> i&nbsp;jest ich również <math>{\small\frac{p - 1}{2}}</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J31 (kryterium Eulera, 1748)</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą i <math>p \nmid a</math>. Modulo <math>p</math> mamy

::{| border="0" 
|-style=height:2.5em
| &#9679;&nbsp;&nbsp;&nbsp; || liczba <math>a</math> jest liczbą kwadratową modulo <math>p</math> wtedy i&nbsp;tylko wtedy, gdy <math>a^{(p - 1) / 2} \equiv 1 \pmod{p}</math>
|-style=height:2.5em
| &#9679;&nbsp;&nbsp;&nbsp; || liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math> wtedy i&nbsp;tylko wtedy, gdy <math>a^{(p - 1) / 2} \equiv - 1 \pmod{p}</math>
|}

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

'''Punkt 1.'''

Niech <math>Q \subset \{ 1, 2, \ldots, p - 1 \}</math> będzie zbiorem wszystkich liczb kwadratowych modulo <math>p</math>, a <math>S \subset \{ 1, 2, \ldots, p - 1 \}</math> będzie zbiorem wszystkich rozwiązań kongruencji

::<math>x^{(p - 1) / 2} \equiv 1 \pmod{p}</math>

Zauważmy, że

::{| border=1 style="border-collapse: collapse;"
|-style=height:2.5em
| &nbsp;&nbsp;&nbsp;'''A'''&nbsp;&nbsp;&nbsp; || &nbsp;&nbsp;&nbsp;<math>| Q | = {\small\frac{p - 1}{2}}</math> || &nbsp;&nbsp;&nbsp;zobacz J30
|-style=height:2.5em
| &nbsp;&nbsp;&nbsp;'''B'''&nbsp;&nbsp;&nbsp; || &nbsp;&nbsp;&nbsp;<math>| S | \leqslant {\small\frac{p - 1}{2}}</math> || &nbsp;&nbsp;&nbsp;zobacz twierdzenie Lagrange'a J14
|-style=height:2.5em
| &nbsp;&nbsp;&nbsp;'''C'''&nbsp;&nbsp;&nbsp; || &nbsp;&nbsp;&nbsp;jeżeli <math>a \in Q</math>, to <math>a \in S \qquad </math> || &nbsp;&nbsp;&nbsp;wynika z&nbsp;ciągu implikacji:<br/> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>a \in Q \qquad \Longrightarrow \qquad a \equiv k^2 \pmod{p}</math><br/> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>a \equiv k^2 \pmod{p} \qquad \Longrightarrow \qquad a^{(p - 1) / 2} \equiv (k^2)^{(p - 1) / 2} \equiv k^{p - 1} \equiv 1 \pmod{p}</math>&nbsp;&nbsp;&nbsp;<br/> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<math>a^{(p - 1) / 2} \equiv 1 \pmod{p} \qquad \Longrightarrow \qquad a \in S</math>
|-style=height:2.5em
| &nbsp;&nbsp;&nbsp;'''D'''&nbsp;&nbsp;&nbsp; || &nbsp;&nbsp;&nbsp;<math>Q \subseteq S</math> || &nbsp;&nbsp;&nbsp;z punktu '''C''' wynika, że '''każdy''' element zbioru <math>Q</math> należy do zbioru <math>S</math>
|}


Łącząc rezultaty z&nbsp;tabeli, otrzymujemy

::<math>{\small\frac{p - 1}{2}} = | Q | \leqslant | S | \leqslant {\small\frac{p - 1}{2}}</math>

Skąd łatwo widzimy, że

::<math>| Q | = | S | = {\small\frac{p - 1}{2}}</math>

Ponieważ <math>Q \subseteq S</math>, a&nbsp;zbiory <math>Q</math> i <math>S</math> są równoliczne, to zbiory te są równe (zobacz H23). Prostą konsekwencją równości zbiorów <math>Q</math> i <math>S</math> jest stwierdzenie

::{| border=0 style="background: #EEEEEE;"
|-style=height:2.0em
|&nbsp;&nbsp;&nbsp;liczba <math>a</math> jest liczbą kwadratową modulo <math>p</math> wtedy i&nbsp;tylko wtedy, gdy <math>a^{(p - 1) / 2} \equiv 1 \pmod{p}</math>&nbsp;&nbsp;&nbsp;
|}

Co kończy dowód punktu pierwszego.

'''Punkt 2.'''

Z udowodnionego już punktu pierwszego wynika<ref name="logic1"/>, że

::{| border=0 style="background: #EEEEEE;"
|-style=height:2.0em
|&nbsp;&nbsp;&nbsp;liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math> wtedy i&nbsp;tylko wtedy, gdy <math>a^{(p - 1) / 2} \not\equiv 1 \pmod{p}</math>&nbsp;&nbsp;&nbsp;
|}

Z twierdzenia Fermata

::<math>a^{p - 1} - 1 = (a^{(p - 1) / 2} - 1) \cdot (a^{(p - 1) / 2} + 1) \equiv 0 \pmod{p}</math>

wynika natychmiast, że jeżeli <math>a^{(p - 1) / 2} - 1 \not\equiv 0 \pmod{p}</math>, to musi być

::<math>a^{(p - 1) / 2} + 1 \equiv 0 \pmod{p}</math>

Fakt ten pozwala sformułować uzyskaną równoważność bardziej precyzyjnie

::{| border=0 style="background: #EEEEEE;"
|-style=height:2.0em
|&nbsp;&nbsp;&nbsp;liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math> wtedy i&nbsp;tylko wtedy, gdy <math>a^{(p - 1) / 2} \equiv - 1 \pmod{p}</math>&nbsp;&nbsp;&nbsp;
|}

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





== Symbol Legendre'a ==

<span style="font-size: 110%; font-weight: bold;">Definicja J32</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą i <math>a \in \mathbb{Z}</math>. Symbolem Legendre'a<ref name="legendre1"/> nazywamy funkcję <math>a</math> i <math>p</math> zdefiniowaną następująco

::<math>\left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} = \left\{ \begin{array}{rl}
   1 & \text{gdy } \, a \, \text{ jest liczbą kwadratową modulo } \, p \,  \text{ oraz } \, p \nmid a \\
 - 1 & \text{gdy } \, a \, \text{ jest liczbą niekwadratową modulo } \, p \\
   0 & \text{gdy } \, p \mid a \\
\end{array} \right.</math>



<span style="font-size: 110%; font-weight: bold;">Uwaga J33</span><br/>
Powyższa definicja pozwala nam zapisać kryterium Eulera w&nbsp;zwartej formie, która obejmuje również przypadek, gdy <math>p \mid a</math>

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



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J34*</span><br/>
Niech <math>a, b \in \mathbb{Z}</math> oraz <math>p, q</math> będą nieparzystymi liczbami pierwszymi. Symbol Legendre'a ma następujące właściwości

::{| class="wikitable plainlinks"  style="font-size: 100%; text-align: left; margin-right: auto;"
|-
| &nbsp;&nbsp;1.&nbsp;&nbsp; || <math>\left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \,\, = \,\, 0 \quad \Longleftrightarrow \quad \gcd (a, p) > 1</math>
|-
| &nbsp;&nbsp;2.&nbsp;&nbsp; || <math>a \equiv b \pmod p \quad \Longrightarrow \quad \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{b}{p}} \right)_{\small{\!\! L}}</math>
|-
| &nbsp;&nbsp;3.&nbsp;&nbsp; || <math>\left( {\small\frac{a b}{p}} \right)_{\small{\!\! L}} \,\, = \,\, \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \cdot   \left( {\small\frac{b}{p}} \right)_{\small{\!\! L}}</math>
|-
| &nbsp;&nbsp;4.&nbsp;&nbsp; || <math>a^{(p - 1) / 2} \equiv \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \pmod{p}</math>
|-
| &nbsp;&nbsp;5.&nbsp;&nbsp; || <math>\left( {\small\frac{1}{p}} \right)_{\small{\!\! L}} \,\, = \,\, 1</math>
|-
| &nbsp;&nbsp;6.&nbsp;&nbsp; || <math>\left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} \,\, = \,\, (- 1)^{\tfrac{p - 1}{2}} \,\, = \,\, 
  \begin{cases}
 \;\;\: 1 & \text{gdy } p \equiv 1 \pmod{4} \\
      - 1 & \text{gdy } p \equiv 3 \pmod{4} \\
  \end{cases}</math>
|-
| &nbsp;&nbsp;7.&nbsp;&nbsp; || <math>\left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} \,\, = \,\, (- 1)^{\tfrac{p^2 - 1}{8}} \,\, = \,\, 
  \begin{cases}
 \;\;\: 1 & \text{gdy } p \equiv 1, 7 \pmod{8} \\
      - 1 & \text{gdy } p \equiv 3, 5 \pmod{8} \\
  \end{cases}</math>
|-
| &nbsp;&nbsp;8.&nbsp;&nbsp; || <math>\left( {\small\frac{- 2}{p}} \right)_{\small{\!\! L}} \,\, = \,\, (- 1)^{\tfrac{(p - 1)(p - 3)}{8}} \,\, = \,\, 
  \begin{cases}
 \;\;\: 1 & \text{gdy } p \equiv 1, 3 \pmod{8} \\
      - 1 & \text{gdy } p \equiv 5, 7 \pmod{8} \\
  \end{cases}</math>
|-
| &nbsp;&nbsp;9.&nbsp;&nbsp; || <math>\left( {\small\frac{p}{q}} \right)_{\small{\!\! L}} \,\, = \,\, \left( {\small\frac{q}{p}} \right)_{\small{\!\! L}} \cdot (-1)^{\tfrac{q - 1}{2} \cdot \tfrac{p - 1}{2}} \,\, = \,\, \left( {\small\frac{q}{p}} \right)_{\small{\!\! L}} \cdot 
\begin{cases}
 \;\;\: 1 & \text{gdy } p \equiv 1 \pmod{4} \;\;\; \text{lub} \;\;\; q \equiv 1 \pmod{4} \\
      - 1 & \text{gdy } p \equiv q \equiv 3 \pmod{4} \\
  \end{cases}</math>
|}



<span style="font-size: 110%; font-weight: bold;">Zadanie J35</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Pokazać, że

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

:*&nbsp;&nbsp;jeżeli <math>a, b</math> są liczbami kwadratowymi (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=Rozwiązanie|Hide=Ukryj rozwiązanie}}
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 (zobacz H18) 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( \pm 1 \right) \cdot \left( \pm 1 \right)
 = \left( \pm 1 \right)^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}}





== Symbol Jacobiego ==

<span style="font-size: 110%; font-weight: bold;">Definicja J36</span><br/>
Niech liczby <math>a \in \mathbb{Z}</math> i <math>m \in \mathbb{Z}_+</math> będą względnie pierwsze. Powiemy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>m</math>, jeżeli kongruencja

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

ma rozwiązanie, czyli istnieje taka liczba <math>k \in \mathbb{Z}</math>, że <math>m \mid (k^2 - a)</math>.

Powiemy, że liczba <math>a</math> jest liczbą niekwadratową modulo <math>m</math>, jeżeli kongruencja

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

nie ma rozwiązania.



<span style="font-size: 110%; font-weight: bold;">Uwaga J37</span><br/>
Prosta funkcja pozwala łatwo sprawdzić, czy liczba <math>a</math> jest liczbą kwadratową modulo <math>m</math>.

 <span style="font-size: 90%; color:black;">isQR(a, m) = 
 \\ funkcja zwraca 1, gdy a jest liczbą kwadratową modulo m,
 \\ -1, gdy a jest liczbą niekwadratową i 0, gdy gcd(a, m) > 1
 {
 '''local'''(w);
 '''if'''( '''gcd'''(a, m) > 1, '''return'''(0) ); \\ liczba nie jest ani QR, ani QNR
 w = -1;
 '''for'''(k = 1, '''floor'''(m/2), '''if'''( (k^2 - a)%m == 0, w = 1; '''break'''() ));
 '''return'''(w);
 }</span>



<span style="font-size: 110%; font-weight: bold;">Uwaga J38</span><br/>
Ponieważ często można spotkać definicję liczb kwadratowych i&nbsp;niekwadratowych modulo <math>m</math>, w&nbsp;której warunek <math>\gcd (a, m) = 1</math> zostaje pominięty, to Czytelnik powinien zawsze upewnić się, jaka definicja jest stosowana. Najczęściej w&nbsp;takim przypadku liczba <math>0</math> nie jest uznawana za liczbę kwadratową modulo <math>m</math>.

Przykładowo:

::<math>\left\{ 0^2, 1^2, 2^2, 3^2, 4^2, 5^2, 6^2, 7^2, 8^2, 9^2 \right\} \equiv \left\{ 0, 1, 4, 9, 6, 5, 6, 9, 4, 1 \right\} \pmod{10}</math>

Liczby kwadratowe modulo <math>10</math> to <math>\left\{ 1, 9 \right\}</math>, a&nbsp;niekwadratowe to <math>\left\{ 3, 7 \right\}</math>. Liczby <math>\left\{ 0, 2, 4, 5, 6, 8 \right\}</math> nie są ani liczbami kwadratowymi, ani liczbami niekwadratowymi modulo <math>10</math>.

Jeśli odrzucimy warunek <math>\gcd (a, m) = 1</math>, to liczbami kwadratowymi modulo <math>10</math> będą <math>\left\{ 0, 1, 4, 5, 6, 9 \right\}</math>, a&nbsp;niekwadratowymi <math>\left\{ 2, 3, 7, 8 \right\}</math>.

Inny przykład. Niech <math>m = 210 = 2 \cdot 3 \cdot 5 \cdot 7</math>. W&nbsp;zależności od przyjętej definicji najmniejszą dodatnią liczbą niekwadratową modulo <math>m</math> będzie albo <math>11</math>, albo <math>2</math>.



<span style="font-size: 110%; font-weight: bold;">Zadanie J39</span><br/>
Niech liczby <math>m, n \in \mathbb{Z}_+</math> i <math>\gcd (m, n) = 1</math>. Pokazać, że liczba <math>a \in \mathbb{Z}</math> jest liczbą kwadratową modulo <math>m n</math> wtedy i&nbsp;tylko wtedy, gdy jest liczbą kwadratową modulo <math>m</math> i&nbsp;modulo <math>n</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Niech <math>W(x) = x^2 - a</math>. Zauważmy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>m</math> wtedy i&nbsp;tylko wtedy, gdy kongruencja <math>W(x) \equiv 0 \!\! \pmod{m}</math> ma rozwiązanie. Dalsza analiza problemu przebiega dokładnie tak, jak to zostało przedstawione w&nbsp;uwadze J12.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Definicja J40</span><br/>
Symbol Jacobiego<ref name="jacobi1"/> <math>\left( {\small\frac{a}{n}} \right)_{\small{\!\! J}}</math> jest uogólnieniem symbolu Legendre'a <math>\left( {\small\frac{a}{p}} \right)_{\small{\!\! L}}</math> dla dodatnich liczb nieparzystych. 
Niech <math>n = \prod_i p_i^{\alpha_i}</math> będzie rozkładem liczby <math>n</math> na czynniki pierwsze, wtedy

::<math>\left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} = \prod_i \left( {\small\frac{a}{p_i}} \right)_{\small{\!\! L}}^{\!\! \alpha_i}</math>



<span style="font-size: 110%; font-weight: bold;">Uwaga J41</span><br/>
Zauważmy, że w&nbsp;przypadku gdy <math>n = 1</math>, po prawej stronie mamy „pusty” iloczyn (bez jakiegokolwiek czynnika). Podobnie jak „pustej” sumie przypisujemy wartość zero, tak „pustemu” iloczynowi przypisujemy wartość jeden. Zatem dla dowolnego <math>a \in \mathbb{Z}</math> jest <math>\left( {\small\frac{a}{1}} \right)_{\small{\!\! J}} = 1</math>.



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J42*</span><br/>
Niech <math>a, b \in \mathbb{Z}</math> oraz <math>m, n \in \mathbb{Z}_+</math> i <math>m, n</math> będą liczbami nieparzystymi. Symbol Jacobiego ma następujące właściwości

::{| class="wikitable plainlinks"  style="font-size: 100%; text-align: left; margin-right: auto;"
|-
| &nbsp;&nbsp;1.&nbsp;&nbsp; || <math>\left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} \,\, = \,\, 0 \quad \Longleftrightarrow \quad \gcd (a, n) > 1</math>
|-
| &nbsp;&nbsp;2.&nbsp;&nbsp; || <math>a \equiv b \pmod n \quad \Longrightarrow \quad \left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} = \left( {\small\frac{b}{n}} \right)_{\small{\!\! J}}</math>
|-
| &nbsp;&nbsp;3.&nbsp;&nbsp; || <math>\left( {\small\frac{a b}{n}} \right)_{\small{\!\! J}} \,\, = \,\, \left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} \cdot   \left( {\small\frac{b}{n}} \right)_{\small{\!\! J}}</math>
|-
| &nbsp;&nbsp;4.&nbsp;&nbsp; || <math>\left( {\small\frac{a}{m n}} \right)_{\small{\!\! J}} \,\, = \,\, \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} \cdot   \left( {\small\frac{a}{n}} \right)_{\small{\!\! J}}</math>
|-
| &nbsp;&nbsp;5.&nbsp;&nbsp; || <math>\left( {\small\frac{1}{n}} \right)_{\small{\!\! J}} \,\, = \,\, 1</math>
|-
| &nbsp;&nbsp;6.&nbsp;&nbsp; || <math>\left( {\small\frac{- 1}{n}} \right)_{\small{\!\! J}} \,\, = \,\, (- 1)^{\tfrac{n - 1}{2}} \,\, = \,\, 
  \begin{cases}
 \;\;\: 1 & \text{gdy } n \equiv 1 \pmod{4} \\
      - 1 & \text{gdy } n \equiv 3 \pmod{4} \\
  \end{cases}</math>
|-
| &nbsp;&nbsp;7.&nbsp;&nbsp; || <math>\left( {\small\frac{2}{n}} \right)_{\small{\!\! J}} \,\, = \,\, (- 1)^{\tfrac{n^2 - 1}{8}} \,\, = \,\, 
  \begin{cases}
 \;\;\: 1 & \text{gdy } n \equiv 1, 7 \pmod{8} \\
      - 1 & \text{gdy } n \equiv 3, 5 \pmod{8} \\
  \end{cases}</math>
|-
| &nbsp;&nbsp;8.&nbsp;&nbsp; || <math>\left( {\small\frac{- 2}{n}} \right)_{\small{\!\! J}} \,\, = \,\, (- 1)^{\tfrac{(n - 1)(n - 3)}{8}} \,\, = \,\, 
  \begin{cases}
 \;\;\: 1 & \text{gdy } n \equiv 1, 3 \pmod{8} \\
      - 1 & \text{gdy } n \equiv 5, 7 \pmod{8} \\
  \end{cases}</math>
|-
| &nbsp;&nbsp;9.&nbsp;&nbsp; || <math>\left( {\small\frac{m}{n}} \right)_{\small{\!\! J}} \,\, = \,\, \left( {\small\frac{n}{m}} \right)_{\small{\!\! J}} \cdot (-1)^{\tfrac{n - 1}{2} \cdot \tfrac{m - 1}{2}} \,\, = \,\, \left( {\small\frac{n}{m}} \right)_{\small{\!\! J}} \cdot 
\begin{cases}
 \;\;\: 1 & \text{gdy } m \equiv 1 \pmod{4} \;\;\; \text{lub} \;\;\; n \equiv 1 \pmod{4} \\
      - 1 & \text{gdy } m \equiv n \equiv 3 \pmod{4} \\
  \end{cases}</math>
|}



<span style="font-size: 110%; font-weight: bold;">Uwaga J43</span><br/>
Zauważmy, że poza zmienionym założeniem tabela z&nbsp;powyższego twierdzenia i&nbsp;tabela z&nbsp;twierdzenia J34 różnią się jedynie punktem czwartym. Oczywiście jest to tylko podobieństwo formalne – symbol Legendre'a i&nbsp;symbol Jacobiego są różnymi funkcjami.



<span style="font-size: 110%; font-weight: bold;">Uwaga J44</span><br/>
Zauważmy, że w&nbsp;przypadku, gdy <math>m</math> jest liczbą nieparzystą

:* jeżeli <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math>, to <math>a</math> jest liczbą niekwadratową modulo <math>m</math>
:* jeżeli <math>a</math> jest liczbą niekwadratową modulo <math>m</math>, to '''nie musi być''' <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math>
:* jeżeli <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = + 1</math>, to <math>a</math> '''nie musi być''' liczbą kwadratową modulo <math>m</math>
:* jeżeli <math>a</math> jest liczbą kwadratową modulo <math>m</math>, to jest <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = + 1</math>

Przykład: jeżeli <math>\gcd (a, m) = 1</math>, to <math>\left( {\small\frac{a}{m^2}} \right)_{\small{\!\! J}} = \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}^2 = + 1</math>, ale <math>a</math> może być liczbą niekwadratową modulo <math>m^2</math>.

Modulo <math>9</math> liczbami niekwadratowymi są: <math>2, 5, 8</math>. Modulo <math>25</math> liczbami niekwadratowymi są: <math>2, 3, 7, 8, 12, 13, 17, 18, 22, 23</math>.



<span style="font-size: 110%; font-weight: bold;">Uwaga J45</span><br/>
Wszystkie liczby kwadratowe i&nbsp;niekwadratowe modulo <math>m</math> można łatwo znaleźć, wykorzystując prosty program:

{{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;">QRandQNR(m) = 
 {
 '''local'''(k, S, V);
 S = [];
 V = [];
 '''for'''(k = 1,  m - 1, '''if'''( '''gcd'''(k, m) > 1, '''next'''() ); S = '''concat'''(S, k));
 S = '''Set'''(S); \\ zbiór liczb względnie pierwszych z m
 '''for'''(k = 1,  m - 1, '''if'''( '''gcd'''(k, m) > 1, '''next'''() ); V = '''concat'''(V, k^2 % m));
 V = '''Set'''(V); \\ zbiór liczb kwadratowych modulo m
 '''print'''("QR: ", V);
 '''print'''("QNR: ", '''setminus'''(S, V)); \\ różnica zbiorów S i V
 }</span>
<br/>
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie J46</span><br/>
Pokazać, że

::<math>\left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 12}{m}} \right)_{\small{\!\! J}} =
\begin{cases}
 \;\;\: 1 & \text{gdy } m = 6 k + 1 \\
 \;\;\: 0 & \text{gdy } m = 6 k + 3 \\
      - 1 & \text{gdy } m = 6 k + 5 \\
\end{cases}</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>\left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{m}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{m}} \right)_{\small{\!\! J}}</math>

::::<math>\; = (- 1)^{\tfrac{m - 1}{2}} \cdot (- 1)^{\tfrac{m - 1}{2} \cdot \tfrac{3 - 1}{2}} \cdot \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}}</math>

::::<math>\; = (- 1)^{m - 1} \cdot \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}}</math>

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

bo <math>m</math> jest liczbą nieparzystą.

Rozważmy liczby nieparzyste <math>m</math> postaci <math>6 k + r</math>, gdzie <math>r = 1, 3, 5</math>. Mamy

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

::::<math>\; = \left( {\small\frac{6 k + r}{3}} \right)_{\small{\!\! J}}</math>

::::<math>\; = \left( {\small\frac{r}{3}} \right)_{\small{\!\! J}}</math>

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

bo odpowiednio dla <math>r = 1, 3, 5</math> jest

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

::<math>\left( {\small\frac{3}{3}} \right)_{\small{\!\! J}} = 0</math>

::<math>\left( {\small\frac{5}{3}} \right)_{\small{\!\! J}} = \left( {\small\frac{2}{3}} \right)_{\small{\!\! J}} = (- 1)^{\tfrac{9 - 1}{8}} = - 1</math>

Łatwo zauważamy, że

::<math>\left( {\small\frac{- 12}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 3 \cdot 2^2}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{m}} \right)_{\small{\!\! J}}^{\! 2} = \left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}}</math>

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



<span style="font-size: 110%; font-weight: bold;">Zadanie J47</span><br/>
Pokazać, że

::<math>\left( {\small\frac{3}{m}} \right)_{\small{\!\! J}} = 
\begin{cases}
 \;\;\: 1 & \text{gdy } m = 12 k \pm 1 \\
 \;\;\: 0 & \text{gdy } m = 12 k \pm 3 \\
      - 1 & \text{gdy } m = 12 k \pm 5 \\
\end{cases}</math>


::<math>\left( {\small\frac{5}{m}} \right)_{\small{\!\! J}} =
\begin{cases}
 \;\;\: 1 & \text{gdy } m = 10 k \pm 1 \\
 \;\;\: 0 & \text{gdy } m = 10 k + 5 \\
      - 1 & \text{gdy } m = 10 k \pm 3 \\
\end{cases}</math>

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

'''Punkt 1.'''

Przy wyliczaniu symboli Legendre'a i&nbsp;Jacobiego, zawsze warto sprawdzić, czy da się ustalić przystawanie liczb modulo <math>4</math>. W&nbsp;tym przypadku mamy

::<math>3 \equiv 3 \pmod{4}</math>

i odpowiednio dla różnych postaci liczby <math>m</math> jest

::<math>m = 12 k + 1 \equiv 1 \pmod{4}</math>

::<math>m = 12 k + 5 \equiv 1 \pmod{4}</math>

::<math>m = 12 k + 7 \equiv 3 \pmod{4}</math>

::<math>m = 12 k + 11 \equiv 3 \pmod{4}</math>

Ułatwi nam to znacznie wykonywanie przekształceń (zobacz J42 p.9)

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

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

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

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

'''Punkt 2.'''

Ponieważ <math>5 \equiv 1 \!\! \pmod{4}</math>, to nie ma już znaczenia, czy <math>m \equiv 1 \!\! \pmod{4}</math>, czy też <math>m \equiv 3 \!\! \pmod{4}</math>. Otrzymujemy natychmiast (zobacz J42 p.9)

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

Rozważmy liczby nieparzyste <math>m</math> postaci <math>10 k + r</math>, gdzie <math>r = 1, 3, 5, 7, 9</math>. Mamy

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

:::<math>\:\, \quad = \left( {\small\frac{10 k + r}{5}} \right)_{\small{\!\! J}}</math>

:::<math>\:\, \quad = \left( {\small\frac{r}{5}} \right)_{\small{\!\! J}}</math>

:::<math>\:\, \quad =
\begin{cases}
 \;\;\: 1 & \text{gdy } r = 1 \\
      - 1 & \text{gdy } r = 3 \\
 \;\;\: 0 & \text{gdy } r = 5 \\
      - 1 & \text{gdy } r = 7 \\
 \;\;\: 1 & \text{gdy } r = 9 \\
\end{cases}</math>

bo odpowiednio dla <math>r = 1, 3, 5, 7, 9</math> jest

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

::<math>\left( {\small\frac{3}{5}} \right)_{\small{\!\! J}} = \left( {\small\frac{-2}{5}} \right)_{\small{\!\! J}} = (- 1)^{\tfrac{(5 - 1)(5 - 3)}{8}} = -1</math>

::<math>\left( {\small\frac{5}{5}} \right)_{\small{\!\! J}} = 0</math>

::<math>\left( {\small\frac{7}{5}} \right)_{\small{\!\! J}} = \left( {\small\frac{2}{5}} \right)_{\small{\!\! J}} = (- 1)^{\tfrac{25 - 1}{8}} = - 1</math>

::<math>\left( {\small\frac{9}{5}} \right)_{\small{\!\! J}} = \left( {\small\frac{3}{5}} \right)_{\small{\!\! J}}^{\! 2} = 1</math>

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



<span style="font-size: 110%; font-weight: bold;">Uwaga J48</span><br/>
Wykorzystując podane w&nbsp;twierdzeniu J42 właściwości symbolu Jacobiego, możemy napisać prostą funkcję w&nbsp;PARI/GP znajdującą jego wartość. Zauważmy, że nie potrzebujemy znać rozkładu liczby <math>n</math> na czynniki pierwsze.

 <span style="font-size: 90%; color:black;">jacobi(a, n) = 
 {
 '''local'''(r, w);
 '''if'''( n <= 0 || n % 2 == 0, '''return'''("Error") );
 a = a % n; \\ korzystamy ze wzoru (a|n) = (b|n), gdy a &equiv; b (mod n)
 w = 1;
 '''while'''( a <> 0,
        '''while'''( a % 2 == 0, a = a/2; r = n % 8; '''if'''( r == 3 || r == 5, w = -w ) );
        \\ usunęliśmy czynnik 2 ze zmiennej a, uwzględniając, że (2|n) = -1, gdy n &equiv; 3,5 (mod 8)
        \\ teraz zmienne a oraz n są nieparzyste
        r = a; \\ zmienna r tylko przechowuje wartość a
        a = n;
        n = r;
        '''if'''( a % 4 == 3 && n % 4 == 3, w = -w );
        \\ zamieniliśmy zmienne, uwzględniając, że (a|n) = - (n|a), gdy a &equiv; n &equiv; 3 (mod 4)
        a = a % n;
      );
 '''if'''( n == 1, '''return'''(w), '''return'''(0) ); \\ n jest teraz równe gcd(a, n)
 }</span>

Zauważmy, że PARI/GP ma zaimplementowaną funkcję, która pozwala obliczać symbol Jacobiego. Jeżeli <math>a</math> jest liczbą całkowitą, a <math>n</math>
dodatnią liczbą nieparzystą, to wystarczy napisać

 <span style="font-size: 90%; color:black;">kronecker(a, n)</span>

aby otrzymać wartość symbolu Jacobiego <math>\left( {\small\frac{a}{n}} \right)_{\small{\!\! J}}</math>.

Kod funkcji podaliśmy dlatego, że jest to ważna funkcja i Czytelnik powinien wiedzieć, jak jest realizowana. Znajomość kodu pozwala łatwo zapisać program w innych językach i obliczać wartości tej funkcji bez korzystania z programu PARI/GP.



<span style="font-size: 110%; font-weight: bold;">Uwaga J49</span><br/>
Jeżeli <math>m</math> jest liczbą pierwszą, to symbol Jacobiego jest symbolem Legendre'a, czyli <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{a}{m}} \right)_{\small{\!\! L}}</math>. Jeżeli <math>m</math> jest liczbą złożoną, to symbol Legendre'a <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! L}}</math> nie istnieje, a&nbsp;symbol Jacobiego <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}</math> dostarcza jedynie ograniczonych informacji.

W przyszłości symbol Legendre'a / Jacobiego będziemy zapisywali w&nbsp;formie uproszczonej <math>(a \mid m)</math> i&nbsp;nie będziemy rozróżniali tych symboli. Interpretacja zapisu jest prosta:

:* jeżeli '''wiemy''', że <math>m</math> jest liczbą pierwszą, to symbol <math>(a \mid m)</math> jest symbolem Legendre'a
:* jeżeli '''wiemy''', że <math>m</math> jest liczbą złożoną, to symbol <math>(a \mid m)</math> jest symbolem Jacobiego
:* jeżeli '''nie wiemy''', czy <math>m</math> jest liczbą pierwszą, czy złożoną, to symbol <math>(a \mid m)</math> jest symbolem Jacobiego





== Rozwiązywanie kongruencji <math>x^2 \equiv a \!\! \pmod{m}</math> ==

<span style="font-size: 110%; font-weight: bold;">Twierdzenie J50</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, zaś <math>a</math> liczbą całkowitą taką, że <math>\gcd (a, p) = 1</math>. Kongruencja

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

ma rozwiązanie wtedy i&nbsp;tylko wtedy, gdy kongruencja

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

ma rozwiązanie.

{{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 kongruencja <math>x^2 \equiv a \!\! \pmod{p^n}</math> ma rozwiązanie. Zatem istnieje taka liczba <math>r \in \mathbb{Z}</math>, że

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

Ponieważ <math>p^n \mid (r^2 - a)</math>, to tym bardziej <math>p \mid (r^2 - a)</math>, co oznacza, że prawdziwa jest kongruencja

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

Skąd wynika natychmiast, że kongruencja <math>x^2 \equiv a \!\! \pmod{p}</math> ma rozwiązanie.

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

Indukcja matematyczna. Z&nbsp;uczynionego w&nbsp;twierdzeniu założenia wiemy, że kongruencja <math>x^2 \equiv a \!\! \pmod{p}</math> ma rozwiązanie. Zatem twierdzenie jest prawdziwe dla <math>n = 1</math>. Załóżmy teraz (założenie indukcyjne), że kongruencja

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

ma rozwiązanie <math>x \equiv u_n \!\! \pmod{p^n}</math> i&nbsp;pokażmy, że twierdzenie jest prawdziwe dla <math>n + 1</math>, czyli że rozwiązanie ma kongruencja

::<math>x^2 \equiv a \pmod{p^{n + 1}}</math>

Wiemy, że liczba <math>u_n</math> jest określona modulo <math>p^n</math>. Nie tracąc ogólności, możemy założyć, że <math>1 \leqslant u_n < p^n</math>. Wartość <math>u_n</math> może zostać wybrana dowolnie (modulo <math>p^n</math>), ale musi zostać ustalona — wymaga tego precyzja i&nbsp;czytelność dowodu. Zatem

::<math>u^2_n - a = k p^n</math>

Zauważmy, że liczba <math>k</math> jest jednoznacznie określona, bo wartość <math>u_n</math> została ustalona. Ponieważ <math>\gcd (2 u_n, p) = 1</math>, to równanie

::<math>2 u_n \cdot s - p \cdot l = - k</math>

ma rozwiązanie (zobacz C76). Niech liczby <math>s_0</math> i <math>l_0</math> będą rozwiązaniem tego równania. Zatem

::<math>2 u_n \cdot s_0 - p \cdot l_0 = - k</math>

::<math>2 u_n \cdot s_0 p^n - l_0 \cdot p^{n + 1} = - k p^n</math>

::<math>2 u_n \cdot s_0 p^n - l_0 \cdot p^{n + 1} = - ( u^2_n - a )</math>

::<math>u^2_n + 2 u_n \cdot s_0 p^n = a + l_0 \cdot p^{n + 1}</math>

Modulo <math>p^{n + 1}</math> dostajemy

::<math>u^2_n + 2 u_n \cdot s_0 p^n \equiv a \pmod{p^{n + 1}}</math>

::<math>(u_n + s_0 p^n)^2 \equiv a \pmod{p^{n + 1}}</math>

bo <math>p^{n + 1} \mid p^{2 n}</math>. Zatem liczba <math>u_{n + 1} = u_n + s_0 p^n</math> jest rozwiązaniem kongruencji

::<math>x^2 \equiv a \pmod{p^{n + 1}}</math>

Pokazaliśmy tym samym prawdziwość tezy indukcyjnej, co kończy dowód indukcyjny.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Uwaga J51</span><br/>
Dla niewielkich modułów rozwiązania dowolnej kongruencji możemy znaleźć przez bezpośrednie sprawdzenie. Omówimy teraz rozwiązania kongruencji <math>x^2 \equiv a \!\! \pmod{2^n}</math> dla <math>n = 1, 2, 3</math>. Ponieważ zakładamy, że <math>\gcd (a, m) = \gcd (a, 2^n) = 1</math>, to <math>a</math> musi być liczbą nieparzystą, zaś <math>x</math> nie może być liczbą parzystą. Istotnie, gdyby tak było, to mielibyśmy <math>0 \equiv 1 \!\! \pmod{2}</math>, bo <math>2 \mid 2^n</math>.

Kongruencja

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

ma dokładnie jedno rozwiązanie <math>x \equiv 1 \!\! \pmod{2}</math>.

Kongruencja

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

ma dwa rozwiązania, gdy <math>a \equiv 1 \!\! \pmod{4}</math>. Rozwiązaniami są: <math>x \equiv 1, 3 \!\! \pmod{4}</math>. W&nbsp;przypadku, gdy <math>a \equiv 3 \!\! \pmod{4}</math> kongruencja nie ma rozwiązań.

Kongruencja

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

ma cztery rozwiązania, gdy <math>a \equiv 1 \!\! \pmod{8}</math>. Rozwiązaniami są: <math>x \equiv 1, 3, 5, 7 \!\! \pmod{8}</math>. W&nbsp;przypadku, gdy <math>a \equiv 3, 5, 7 \!\! \pmod{8}</math> kongruencja nie ma rozwiązań.



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J52</span><br/>
Niech <math>n \geqslant 3</math> i <math>a</math> będzie liczbą nieparzystą. Kongruencja

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

ma rozwiązanie wtedy i&nbsp;tylko wtedy, gdy kongruencja

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

ma rozwiązanie.

{{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 kongruencja <math>x^2 \equiv a \!\! \pmod{2^n}</math> ma rozwiązanie, zatem istnieje taka liczba <math>r \in \mathbb{Z}</math>, że

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

Ponieważ <math>2^n \mid (r^2 - a)</math>, gdzie <math>n \geqslant 3</math>, to tym bardziej <math>2^3 \mid (r^2 - a)</math>. Co oznacza, że prawdziwa jest kongruencja

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

Skąd wynika natychmiast, że kongruencja <math>x^2 \equiv a \!\! \pmod{8}</math> ma rozwiązanie.

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

Indukcja matematyczna. Z&nbsp;uczynionego w&nbsp;twierdzeniu założenia wiemy, że kongruencja <math>x^2 \equiv a \pmod{8}</math> ma rozwiązanie. Zatem twierdzenie jest prawdziwe dla <math>n = 3</math>. Załóżmy teraz (założenie indukcyjne), że kongruencja

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

ma rozwiązanie <math>x \equiv u_n \!\! \pmod{2^n}</math> i&nbsp;pokażemy, że twierdzenie jest prawdziwe dla <math>n + 1</math>, czyli że rozwiązanie ma kongruencja

::<math>x^2 \equiv a \pmod{2^{n + 1}}</math>

Z założenia istnieje taka liczba <math>k</math>, że <math>u^2_n - a = k \cdot 2^n</math>. Niech

::<math>r = 
  \begin{cases}
  0 & \text{gdy } k \text{ jest liczbą parzystą} \\
  1 & \text{gdy } k \text{ jest liczbą nieparzystą} \\
  \end{cases}</math>

Zauważmy, że

::<math>(u_n + r \cdot 2^{n - 1})^2 - a = u^2_n - a + 2^n r + r^2 \cdot 2^{2 n - 2}</math>

::::::::<math>\;\! = k \cdot 2^n + 2^n r + r^2 \cdot 2^{2 n - 2}</math>

::::::::<math>\;\! = 2^n (k + r) + r^2 \cdot 2^{2 n - 2}</math>

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

bo <math>k + r</math> jest liczbą parzystą, a&nbsp;dla <math>n \geqslant 3</math> mamy <math>2 n - 2 \geqslant n + 1</math>. Zatem liczba <math>u_{n + 1} = u_n + r \cdot 2^{n - 1}</math> jest rozwiązaniem kongruencji

::<math>x^2 \equiv a \pmod{2^{n + 1}}</math>

Pokazaliśmy tym samym prawdziwość tezy indukcyjnej, co kończy dowód indukcyjny.<br/>
&#9633;
{{\Spoiler}}


<span style="font-size: 110%; font-weight: bold;">Wniosek J53</span><br/>
Jeżeli <math>a</math> jest liczbą nieparzystą, to kongruencja <math>x^2 \equiv a \!\! \pmod{2^n}</math> ma rozwiązanie wtedy i&nbsp;tylko wtedy, gdy <math>a</math> jest postaci <math>2 k + 1</math>, <math>4 k + 1</math> lub <math>8 k + 1</math> w&nbsp;zależności od tego, czy <math>n = 1</math>, czy <math>n = 2</math>, czy <math>n \geqslant 3</math>.



<span style="font-size: 110%; font-weight: bold;">Uwaga J54</span><br/>
Niech <math>m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math> i <math>\gcd (a, m) = 1</math>. Z&nbsp;chińskiego twierdzenia o&nbsp;resztach (zobacz J3 i&nbsp;J12) wynika, że kongruencja <math>x^2 \equiv a \!\! \pmod{m}</math> ma rozwiązanie wtedy i&nbsp;tylko wtedy, gdy ma rozwiązanie każda z&nbsp;kongruencji

::<math>\begin{align}
 x^2 & \equiv a \pmod{p^{\alpha_1}_1} \\
     & \,\,\,\cdots \\
 x^2 & \equiv a \pmod{p^{\alpha_s}_s} \\
\end{align}</math>

Z definicji J32, twierdzeń J50 i&nbsp;J52, uwagi J51 i&nbsp;wniosku J53 otrzymujemy



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J55</span><br/>
Niech <math>m \in \mathbb{Z}_+</math> i <math>\gcd (a, m) = 1</math>. Kongruencja

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

ma rozwiązanie wtedy i&nbsp;tylko wtedy, gdy

::{| border="0" 
|-style=height:1em
| &#9679;&nbsp;&nbsp;&nbsp; dla każdego nieparzystego dzielnika pierwszego <math>p</math> liczby <math>m</math> jest&nbsp; <math>\left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} = 1</math>
|-style=height:1em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli&nbsp; <math>8 \mid m</math>, &nbsp;to&nbsp; <math>8 \mid ( a - 1 )</math>
|-style=height:2.5em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli&nbsp; <math>8 \nmid m</math>, &nbsp;ale&nbsp; <math>4 \mid m</math>, &nbsp;to&nbsp; <math>4 \mid ( a - 1 )</math>
|}



<span style="font-size: 110%; font-weight: bold;">Twierdzenie J56</span><br/>
Niech <math>m \in \mathbb{Z}_+</math> i <math>\gcd (a, m) = 1</math>. Kongruencja

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

nie ma rozwiązania wtedy i&nbsp;tylko wtedy, gdy spełniony jest co najmniej jeden z&nbsp;warunków

::{| border="0" 
|-style=height:1em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli dla dowolnego nieparzystego dzielnika <math>d</math> liczby <math>m</math> jest <math>\left( {\small\frac{a}{d}} \right)_{\small{\!\! J}} = - 1</math>
|-style=height:1em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli&nbsp; <math>8 \mid m</math> &nbsp;i&nbsp; <math>8 \nmid ( a - 1 )</math>
|-style=height:2.5em
| &#9679;&nbsp;&nbsp;&nbsp; jeżeli&nbsp; <math>8 \nmid m</math>, &nbsp;ale&nbsp; <math>4 \mid m</math> &nbsp;i&nbsp; <math>4 \nmid ( a - 1 )</math>
|}

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

'''Punkt 1.'''

Z założenia <math>d \mid m</math>. Gdyby kongruencja

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

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

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

miałaby rozwiązanie, ale jest to niemożliwe, bo założyliśmy, że <math>\left( {\small\frac{a}{d}} \right)_{\small{\!\! J}} = - 1</math>, co oznacza, że <math>a</math> jest liczbą niekwadratową modulo <math>d</math>.

Punkty 2. i 3. wynikają wprost z&nbsp;twierdzenia J55.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Przykład J57</span><br/>
Zauważmy, że <math>\left( {\small\frac{17}{19}} \right)_{\small{\!\! J}} = \left( {\small\frac{5}{19}} \right)_{\small{\!\! J}} = 1</math> oraz <math>\left( {\small\frac{17}{23}} \right)_{\small{\!\! J}} = \left( {\small\frac{5}{23}} \right)_{\small{\!\! J}} = - 1</math>. W&nbsp;tabelach zestawiliśmy kongruencje i&nbsp;ich rozwiązania.

{| class="wikitable plainlinks"  style="display: inline-table; margin-left: 60px; margin-right: 50px; font-size: 90%; text-align: left;"
|-
! Kongruencje || Rozwiązania
|-
| <math>x^2 \equiv 17 \pmod{16 \cdot 19}</math> || <math>25, 63, 89, 127, 177, 215, 241, 279</math>
|-
| <math>x^2 \equiv 17 \pmod{8 \cdot 19}</math> || <math>13, 25, 51, 63, 89, 101, 127, 139</math>
|-
| <math>x^2 \equiv 5 \;\, \pmod{8 \cdot 19}</math> || <math>\text{brak}</math>
|-
| <math>x^2 \equiv 5 \;\, \pmod{4 \cdot 19}</math> || <math>9, 29, 47, 67</math>
|}
{| class="wikitable plainlinks"  style="display: inline-table; margin-left: 5px; margin-right: 5px; font-size: 90%; text-align: left;"
|-
! Kongruencje || Rozwiązania
|-
| <math>x^2 \equiv 17 \pmod{16 \cdot 23}</math> || <math>\text{brak}</math>
|-
| <math>x^2 \equiv 17 \pmod{8 \cdot 23}</math> || <math>\text{brak}</math>
|-
| <math>x^2 \equiv 5 \;\, \pmod{8 \cdot 23}</math> || <math>\text{brak}</math>
|-
| <math>x^2 \equiv 5 \;\, \pmod{4 \cdot 23}</math> || <math>\text{brak}</math>
|}



<span style="font-size: 110%; font-weight: bold;">Zadanie J58</span><br/>
Rozwiązać kongruencję, gdzie <math>p</math> jest liczbą pierwszą nieparzystą

::<math>x^2 + rx + s \equiv 0 \pmod{p}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Ponieważ <math>\gcd (2, p) = 1</math>, to nie zmniejszając ogólności kongruencję powyższą możemy zapisać w&nbsp;postaci

::<math>4 x^2 + 4 rx + 4 s \equiv 0 \pmod{p}</math>

::<math>(2 x + r)^2 - r^2 + 4 s \equiv 0 \pmod{p}</math>

::<math>(2 x + r)^2 \equiv r^2 - 4 s \pmod{p}</math>

Widzimy, że rozpatrywana kongruencja ma rozwiązanie wtedy i&nbsp;tylko wtedy, gdy liczba <math>r^2 - 4 s</math> jest liczbą kwadratową modulo <math>p</math>. Istotnie, jeśli jest liczbą kwadratową, to istnieje taka liczba <math>b</math>, że <math>b^2 \equiv r^2 - 4 s \!\! \pmod{p}</math>, zatem otrzymujemy

::<math>(2 x + r)^2 \equiv b^2 \pmod{p}</math>

::<math>2 x + r \equiv \pm b \pmod{p}</math>

::<math>x \equiv {\small\frac{p + 1}{2}} \cdot (- r \pm b) \pmod{p}</math>

Jeśli <math>r^2 - 4 s</math> nie jest liczbą kwadratową modulo <math>p</math>, to kongruencja

::<math>(2 x + r)^2 \equiv r^2 - 4 s \pmod{p}</math>

nie ma rozwiązania. Wynika stąd, że równoważna jej kongruencja

::<math>x^2 + rx + s \equiv 0 \pmod{p}</math>

również nie ma rozwiązania.<br/>
&#9633;
{{\Spoiler}}



<span style="font-size: 110%; font-weight: bold;">Zadanie J59</span><br/>
Rozwiązać kongruencję

::<math>5 x^2 + 6 x + 8 \equiv 0 \pmod{19}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Rozwiązywanie kongruencji w&nbsp;przypadku konkretnych wartości liczb <math>r, s</math> jest łatwiejsze niż w&nbsp;przypadku ogólnym. Mnożąc obie strony kongruencji przez <math>4</math>, otrzymujemy

::<math>x^2 + 24 x + 32 \equiv 0 \pmod{19}</math>

::<math>x^2 + 24 x + 13 \equiv 0 \pmod{19}</math>

Celowo zostawiliśmy parzysty współczynnik przy <math>x</math>. Gdyby był nieparzysty, to zawsze możemy dodać do niego nieparzysty moduł.

::<math>(x + 12)^2 - 144 + 13 \equiv 0 \pmod{19}</math>

::<math>(x + 12)^2 + 2 \equiv 0 \pmod{19}</math>

::<math>(x + 12)^2 \equiv - 2 \pmod{19}</math>

::<math>(x + 12)^2 \equiv 6^2 \pmod{19}</math>

::<math>x + 12 \equiv \pm 6 \pmod{19}</math>

Otrzymujemy: <math>x \equiv 1 \!\! \pmod{19}</math> lub <math>x \equiv 13 \!\! \pmod{19}</math>.


Nieco spostrzegawczości pozwala znaleźć rozwiązanie kongruencji natychmiast. W&nbsp;naszym przypadku wystarczyło zauważyć, że

::<math>x^2 + 24 x + 13 \equiv x^2 - 14 x + 13 \equiv (x - 1) (x - 13) \equiv 0 \pmod{19}</math><br/>
&#9633;
{{\Spoiler}}














== Przypisy ==

<references>

<ref name="CRT1">Wikipedia, ''Chińskie twierdzenie o&nbsp;resztach'', ([https://pl.wikipedia.org/wiki/Chi%C5%84skie_twierdzenie_o_resztach Wiki-pl]), ([https://en.wikipedia.org/wiki/Chinese_remainder_theorem Wiki-en])</ref>

<ref name="CRT2">CRT to często używany skrót od angielskiej nazwy twierdzenia: ''Chinese remainder theorem''</ref>

<ref name="logic1">Wikipedia, ''Logical equivalence'', ([https://en.wikipedia.org/wiki/Logical_equivalence Wiki-en])</ref>

<ref name="jacobi1">Wikipedia, ''Symbol Jacobiego'', ([https://pl.wikipedia.org/wiki/Symbol_Jacobiego Wiki-pl]), ([https://en.wikipedia.org/wiki/Jacobi_symbol Wiki-en])</ref>

<ref name="legendre1">Wikipedia, ''Symbol Legendre’a'', ([https://pl.wikipedia.org/wiki/Symbol_Legendre%E2%80%99a Wiki-pl]), ([https://en.wikipedia.org/wiki/Legendre_symbol Wiki-en])</ref>

</references>











&nbsp;