Testy pierwszości. Liczby pseudopierwsze Lucasa i liczby silnie pseudopierwsze Lucasa. Test BPSW

22.03.2023

Chińskie twierdzenie o resztach

Twierdzenie J1
Niech [math]\displaystyle{ a, u \in \mathbb{Z} }[/math] i [math]\displaystyle{ m, n \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ \gcd (m, n) = 1 }[/math]. Kongruencja

[math]\displaystyle{ u \equiv a \pmod{m n} }[/math]

jest równoważna układowi kongruencji

[math]\displaystyle{ \begin{align} u &\equiv a \pmod{m} \\ u &\equiv a \pmod{n} \end{align} }[/math]

Dowód

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

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

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

Z kongruencji

[math]\displaystyle{ u \equiv a \pmod{m} }[/math]

wynika, że [math]\displaystyle{ u - a = k m }[/math], zaś z kongruencji

[math]\displaystyle{ u \equiv a \pmod{n} }[/math]

otrzymujemy [math]\displaystyle{ n \mid (u - a) }[/math], czyli [math]\displaystyle{ n \mid k m }[/math]. Ponieważ [math]\displaystyle{ \gcd (m, n) = 1 }[/math], zatem [math]\displaystyle{ n \mid k }[/math] (zobacz C74) i istnieje taka liczba całkowita [math]\displaystyle{ s }[/math], że [math]\displaystyle{ k = s n }[/math], czyli [math]\displaystyle{ u - a = s n m }[/math], a stąd [math]\displaystyle{ u \equiv a \!\! \pmod{m n} }[/math]. Co kończy dowód.
□

Twierdzenie J2
Dla dowolnych liczb [math]\displaystyle{ a, b \in \mathbb{Z} }[/math] i względnie pierwszych liczb [math]\displaystyle{ m, n \in \mathbb{Z}_+ }[/math] istnieje dokładnie jedna taka liczba [math]\displaystyle{ c }[/math] (określona modulo [math]\displaystyle{ m n }[/math]), że prawdziwy jest układ kongruencji

[math]\displaystyle{ \begin{align} c & \equiv a \pmod{m} \\ c & \equiv b \pmod{n} \end{align} }[/math]

Dowód

Z założenia liczby [math]\displaystyle{ m }[/math] i [math]\displaystyle{ n }[/math] są względnie pierwsze, zatem na mocy lematu Bézouta (C.71) istnieją takie liczby [math]\displaystyle{ x, y \in \mathbb{Z} }[/math], że

[math]\displaystyle{ m x + n y = 1 }[/math]

Niech [math]\displaystyle{ c = a n y + b m x }[/math]. Modulo [math]\displaystyle{ m }[/math] dostajemy

[math]\displaystyle{ c \equiv a n y \pmod{m} }[/math]

[math]\displaystyle{ c \equiv a (1 - m x) \pmod{m} }[/math]

[math]\displaystyle{ c \equiv a \pmod{m} }[/math]

Natomiast modulo [math]\displaystyle{ n }[/math] mamy

[math]\displaystyle{ c \equiv b m x \pmod{n} }[/math]

[math]\displaystyle{ c \equiv b (1 - n y) \pmod{n} }[/math]

[math]\displaystyle{ c \equiv b \pmod{n} }[/math]

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

[math]\displaystyle{ d \equiv c \pmod{m n} }[/math].

Czyli możemy powiedzieć, że wybrana przez nas liczba [math]\displaystyle{ c }[/math] jest określona modulo [math]\displaystyle{ m n }[/math] i tak rozumiana jest dokładnie jedna. W szczególności istnieje tylko jedna liczba [math]\displaystyle{ c }[/math] taka, że [math]\displaystyle{ 1 \leqslant c \leqslant m n }[/math].
□

Twierdzenie J3 (chińskie twierdzenie o resztach)
Niech [math]\displaystyle{ a, b, c, u \in \mathbb{Z} }[/math] i [math]\displaystyle{ m, n \in \mathbb{Z}_+ }[/math] oraz niech [math]\displaystyle{ \gcd (m, n) = 1 }[/math]. Istnieje dokładnie jedna liczba [math]\displaystyle{ c }[/math] (określona modulo [math]\displaystyle{ m n }[/math]) taka, że kongruencja

[math]\displaystyle{ u \equiv c \pmod{m n} }[/math]

jest równoważna układowi kongruencji

[math]\displaystyle{ \begin{align} u & \equiv a \pmod{m} \\ u & \equiv b \pmod{n} \end{align} }[/math]

Dowód

Z twierdzenia J2 wiemy, że istnieje dokładnie jedna liczba [math]\displaystyle{ c }[/math] (określona modulo [math]\displaystyle{ m n }[/math]) taka, że prawdziwy jest układ kongruencji

[math]\displaystyle{ \begin{align} c & \equiv a \pmod{m} \\ c & \equiv b \pmod{n} \end{align} }[/math]

Korzystając z tego rezultatu i twierdzenia J1, otrzymujemy

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

Uwaga J4
Chińskie twierdzenie o resztach (CRT) pozostaje prawdziwe w przypadku układu skończonej liczby kongruencji. Założenie, że moduły [math]\displaystyle{ m }[/math] i [math]\displaystyle{ n }[/math] są względnie pierwsze, jest istotne. Przykładowo układ kongruencji

[math]\displaystyle{ \begin{align} u &\equiv 1 \pmod{4} \\ u &\equiv 3 \pmod{8} \end{align} }[/math]

nie może być zapisany w 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]\displaystyle{ u = 4 k + 1 }[/math], które dla liczb [math]\displaystyle{ k }[/math] parzystych i nieparzystych ma postać

[math]\displaystyle{ u = 8 j + 1, \qquad u = 8 j + 5 }[/math]

i nie może być [math]\displaystyle{ u \equiv 3 \!\! \pmod{8} }[/math].

Zadanie J5
Niech [math]\displaystyle{ u, a_1, \ldots, a_k \in \mathbb{Z} }[/math] i [math]\displaystyle{ m_1, \ldots, m_k \in \mathbb{Z}_+ }[/math]. Pokazać, że jeżeli liczby [math]\displaystyle{ m_1, \ldots, m_k }[/math] są parami względnie pierwsze (czyli [math]\displaystyle{ \gcd (m_i, m_j) = 1 }[/math] dla [math]\displaystyle{ i \neq j }[/math]), to istnieje dokładnie jedna liczba [math]\displaystyle{ c }[/math] (określona modulo [math]\displaystyle{ m_1 \cdot \ldots \cdot m_k }[/math]) taka, że układ kongruencji

[math]\displaystyle{ \begin{align} u & \equiv a_1 \pmod{m_1} \\ & \cdots \\ u & \equiv a_k \pmod{m_k} \end{align} }[/math]

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

[math]\displaystyle{ u \equiv c \;\; \pmod{m_1 \cdot \ldots \cdot m_k} }[/math]

Rozwiązanie

Indukcja matematyczna. Twierdzenie jest prawdziwe dla liczby [math]\displaystyle{ k = 2 }[/math] (zobacz J3). Zakładając prawdziwość twierdzenia dla liczby naturalnej [math]\displaystyle{ k \geqslant 2 }[/math], dla liczby [math]\displaystyle{ k + 1 }[/math] otrzymujemy układ kongruencji

[math]\displaystyle{ \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 założenia indukcyjnego. Z twierdzenia J3 wynika, że układ ten można zapisać w sposób równoważny w postaci kongruencji

[math]\displaystyle{ u \equiv c' \pmod{m_1 \cdot \ldots \cdot m_k m_{k + 1}} }[/math]

gdzie liczba [math]\displaystyle{ c' }[/math] jest dokładnie jedna i jest określona modulo [math]\displaystyle{ m_1 \cdot \ldots \cdot m_k m_{k + 1} }[/math]. Zatem twierdzenie jest prawdziwe dla [math]\displaystyle{ k + 1 }[/math]. Co kończy dowód indukcyjny.
□

Przykład J6
Dysponujemy pewną ilością kulek. Grupując je po [math]\displaystyle{ 5 }[/math], zostają nam [math]\displaystyle{ 3 }[/math], a kiedy próbujemy ustawić je po [math]\displaystyle{ 7 }[/math], zostają nam [math]\displaystyle{ 4 }[/math]. Jaka najmniejsza ilość kulek spełnia te warunki? Rozważmy układ kongruencji

[math]\displaystyle{ \begin{align} n &\equiv 3 \pmod{5} \\ n &\equiv 4 \pmod{7} \end{align} }[/math]

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

chinese( Mod(3,5), Mod(4,7) )

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

[math]\displaystyle{ n \equiv 18 \pmod{35} }[/math]

Jest to zarazem odpowiedź na postawione pytanie: najmniejsza liczba kulek wynosi [math]\displaystyle{ 18 }[/math].

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

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

chinese( [Mod(1,2), Mod(2,3), Mod(3,5), Mod(4,7), Mod(5,11)] )

Otrzymujemy Mod(1523, 2310).

Wielomiany

Twierdzenie J7
Niech [math]\displaystyle{ W_n (x) }[/math] będzie dowolnym wielomianem stopnia [math]\displaystyle{ n }[/math]. Wielomian [math]\displaystyle{ W_n (x) }[/math] można przedstawić w postaci

[math]\displaystyle{ W_n (x) = W_n (s) + (x - s) V_{n - 1} (x) }[/math]

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

Dowód

Z założenia [math]\displaystyle{ W_n (x) = \sum_{k = 0}^{n} a_k x^k }[/math], gdzie [math]\displaystyle{ a_n \neq 0 }[/math]. Zauważmy, że

[math]\displaystyle{ W_n (x) - W_n (s) = \sum_{k = 0}^{n} a_k x^k - \sum_{k = 0}^{n} a_k s^k }[/math]

[math]\displaystyle{ \quad \; = \sum_{k = 1}^{n} a_k (x^k - s^k) }[/math]

Dla [math]\displaystyle{ k \geqslant 1 }[/math] prawdziwy jest wzór

[math]\displaystyle{ x^k - s^k = (x - s) \sum_{j = 1}^{k} x^{k - j} s^{j - 1} }[/math]

[math]\displaystyle{ \;\,\, = (x - s) (x^{k - 1} + s x^{k - 2} + \ldots + s^{k - 2} x + s^{k - 1}) }[/math]

[math]\displaystyle{ \;\,\, = (x - s) U^{(k)} (x) }[/math]

Gdzie przez [math]\displaystyle{ U^{(k)} (x) = \sum_{j = 1}^{k} x^{k - j} s^{j - 1} }[/math] oznaczyliśmy wielomian, którego stopień jest równy [math]\displaystyle{ k - 1 }[/math]. Zatem możemy napisać

[math]\displaystyle{ W_n (x) - W_n (s) = (x - s) \sum_{k = 1}^{n} a_k U^{(k)} (x) }[/math]

Suma wypisana po prawej stronie jest pewnym wielomianem [math]\displaystyle{ V_{n - 1} (x) }[/math]. Ponieważ ze wszystkich wielomianów [math]\displaystyle{ a_k U^{(k)} (x) }[/math], wielomian [math]\displaystyle{ a_n U^{(n)} (x) }[/math] ma największy stopień równy [math]\displaystyle{ n - 1 }[/math], to stopień wielomianu [math]\displaystyle{ V_{n - 1} (x) }[/math] jest równy [math]\displaystyle{ n - 1 }[/math]. Czyli

[math]\displaystyle{ W_n (x) - W_n (s) = (x - s) V_{n - 1} (x) }[/math]

Niech [math]\displaystyle{ V_n (x) = \sum_{k = 0}^{n - 1} b_k x^k }[/math]. Mamy

[math]\displaystyle{ \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 największym stopniu, łatwo zauważamy, że [math]\displaystyle{ a_n = b_{n - 1} }[/math]. Czyli współczynnik wiodący wielomianu [math]\displaystyle{ V_{n - 1} (x) }[/math] jest równy [math]\displaystyle{ a_n }[/math]. Co należało pokazać.
□

Definicja J8
Wielomian [math]\displaystyle{ W_n (x) = \sum_{k = 0}^{n} a_k x^k }[/math], gdzie [math]\displaystyle{ a_0, \ldots, a_n \in \mathbb{Z} }[/math] oraz [math]\displaystyle{ a_n \neq 0 }[/math], będziemy nazywali wielomianem całkowitym stopnia [math]\displaystyle{ n }[/math].

Definicja J9
Powiemy, że wielomian całkowity [math]\displaystyle{ W_n (x) = \sum_{k = 0}^{n} a_k x^k }[/math] jest stopnia [math]\displaystyle{ n }[/math] modulo [math]\displaystyle{ p }[/math], gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą, jeżeli [math]\displaystyle{ p \nmid a_n }[/math]. Jeżeli każdy współczynnik [math]\displaystyle{ a_k }[/math], gdzie [math]\displaystyle{ k = 0, 1, \ldots, n }[/math], jest podzielny przez [math]\displaystyle{ p }[/math], to stopień wielomianu [math]\displaystyle{ W_n (x) }[/math] modulo [math]\displaystyle{ p }[/math] jest nieokreślony.

Twierdzenie J10
Niech [math]\displaystyle{ W_n (x) = \sum_{k = 0}^{n} a_k x^k }[/math] będzie wielomianem całkowitym i [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math]. Jeżeli prawdziwa jest kongruencja [math]\displaystyle{ x \equiv y \!\! \pmod{m} }[/math], to

[math]\displaystyle{ W_n (x) \equiv W_n (y) \pmod{m} }[/math]

Dowód

Dla [math]\displaystyle{ k \geqslant 1 }[/math] wyrażenie [math]\displaystyle{ x^k - y^k }[/math] jest podzielne przez [math]\displaystyle{ x - y }[/math], co łatwo pokazać stosując indukcję matematyczną lub zauważając, że

[math]\displaystyle{ x^k - y^k = (x - y) \sum_{j = 1}^{k} x^{k - j} y^{j - 1} }[/math]

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

[math]\displaystyle{ \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]\displaystyle{ W_n (x) \equiv W_n (y) \pmod{m} }[/math]

Co należało pokazać.
□

Uwaga J11
Niech [math]\displaystyle{ W(x) }[/math] będzie wielomianem całkowitym. Rozważmy kongruencję

[math]\displaystyle{ W(x) \equiv 0 \pmod{m n} \qquad \qquad \qquad (1) }[/math]

gdzie liczby [math]\displaystyle{ m }[/math] i [math]\displaystyle{ n }[/math] są względnie pierwsze.

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

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

Załóżmy, że każda z kongruencji [math]\displaystyle{ (2) }[/math] ma przynajmniej jedno rozwiązanie i niech

• [math]\displaystyle{ x \equiv a \!\! \pmod{m} }[/math] będzie pierwiastkiem kongruencji [math]\displaystyle{ W (x) \equiv 0 \!\! \pmod{m} }[/math]
• [math]\displaystyle{ x \equiv b \!\! \pmod{n} }[/math] będzie pierwiastkiem kongruencji [math]\displaystyle{ W (x) \equiv 0 \!\! \pmod{n} }[/math]

Pierwiastki te tworzą układ kongruencji

[math]\displaystyle{ \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 resztach wiemy, że układ ten możemy zapisać w postaci równoważnej

[math]\displaystyle{ x \equiv c \pmod{m n} }[/math]

Zauważmy, że liczba [math]\displaystyle{ c }[/math] określona modulo [math]\displaystyle{ m n }[/math] jest rozwiązaniem kongruencji [math]\displaystyle{ (1) }[/math]. Istotnie z twierdzenia J10 mamy

[math]\displaystyle{ \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]\displaystyle{ m, n }[/math] są względnie pierwsze, zatem otrzymujemy, że

[math]\displaystyle{ W (c) \equiv 0 \pmod{m n} }[/math]

Wynika stąd, że każdemu układowi rozwiązań [math]\displaystyle{ (3) }[/math] odpowiada dokładnie jedno rozwiązanie kongruencji [math]\displaystyle{ (1) }[/math].

Podsumujmy: jeżeli kongruencje

[math]\displaystyle{ \begin{align} W (x) &\equiv 0 \pmod{m}\\ W (x) &\equiv 0 \pmod{n} \end{align} }[/math]

mają odpowiednio [math]\displaystyle{ r }[/math] i [math]\displaystyle{ s }[/math] pierwiastków, to liczba różnych układów kongruencji [math]\displaystyle{ (3) }[/math] jest równa iloczynowi [math]\displaystyle{ r s }[/math] i istnieje [math]\displaystyle{ r s }[/math] różnych rozwiązań kongruencji

[math]\displaystyle{ W(x) \equiv 0 \pmod{m n} }[/math]

Twierdzenie Lagrange'a

Twierdzenie J12
Kongruencja

[math]\displaystyle{ a_1 x + a_0 \equiv 0 \pmod{p} }[/math]

gdzie [math]\displaystyle{ p \nmid a_1 }[/math], ma dokładnie jedno rozwiązanie modulo [math]\displaystyle{ p }[/math].

Dowód

A. Istnienie rozwiązania

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

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

[math]\displaystyle{ a_1 r \equiv 1 \pmod{p} }[/math]

Mnożąc rozpatrywaną kongruencję przez [math]\displaystyle{ r }[/math], otrzymujemy

[math]\displaystyle{ a_1 r x + a_0 r \equiv 0 \pmod{p} }[/math]

Zatem

[math]\displaystyle{ x \equiv - a_0 r \pmod{p} }[/math]

B. Brak innych rozwiązań

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

[math]\displaystyle{ a_1 x + a_0 \equiv 0 \pmod{p} }[/math]

Jeśli oznaczymy je przez [math]\displaystyle{ x_1 }[/math] i [math]\displaystyle{ x_2 }[/math], to otrzymamy

[math]\displaystyle{ a_1 x_1 + a_0 \equiv 0 \equiv a_1 x_2 + a_0 \pmod{p} }[/math]

Czyli

[math]\displaystyle{ a_1 x_1 \equiv a_1 x_2 \pmod{p} }[/math]

[math]\displaystyle{ p \mid a_1 (x_1 - x_2) }[/math]

Ponieważ [math]\displaystyle{ p \nmid a_1 }[/math], to z lematu Euklidesa (C74) otrzymujemy natychmiast [math]\displaystyle{ p \mid (x_1 - x_2) }[/math]. Skąd wynika, że [math]\displaystyle{ x_1 \equiv x_2 \!\! \pmod{p} }[/math], wbrew założeniu, że [math]\displaystyle{ x_1 }[/math] i [math]\displaystyle{ x_2 }[/math] są dwoma różnymi rozwiązaniami. Co kończy dowód.
□

Twierdzenie J13 (Joseph Louis Lagrange, 1768)
Jeżeli wielomian [math]\displaystyle{ W_n (x) = \sum_{k = 0}^{n} a_k x^k }[/math] ma stopień [math]\displaystyle{ n }[/math] modulo [math]\displaystyle{ p }[/math], gdzie [math]\displaystyle{ n \geqslant 1 }[/math], to kongruencja

[math]\displaystyle{ W_n (x) \equiv 0 \pmod{p} }[/math]

ma co najwyżej [math]\displaystyle{ n }[/math] rozwiązań.

Dowód

Indukcja matematyczna. Z J12 wiemy, że dowodzone twierdzenie jest prawdziwe dla [math]\displaystyle{ n = 1 }[/math]. Załóżmy, że twierdzenie jest prawdziwe dla wszystkich liczb całkowitych dodatnich nie większych od [math]\displaystyle{ n - 1 }[/math]. Niech wielomian [math]\displaystyle{ W_n (x) }[/math] ma stopień [math]\displaystyle{ n }[/math] modulo [math]\displaystyle{ p }[/math]. Jeżeli kongruencja

[math]\displaystyle{ W_n (x) \equiv 0 \pmod{p} }[/math]

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

[math]\displaystyle{ W_n (x) - W_n (s) = (x - s) V_{n - 1} (x) }[/math]

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

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

[math]\displaystyle{ W_n (x) \equiv (x - s) V_{n - 1} (x) \pmod{p} }[/math]

Ponieważ [math]\displaystyle{ p }[/math] jest liczbą pierwszą, to z rozpatrywanej kongruencji

[math]\displaystyle{ W_n (x) \equiv 0 \pmod{p} }[/math]

wynika, że musi być (zobacz C74)

[math]\displaystyle{ 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]\displaystyle{ V_{n - 1} (x) \pmod{p} }[/math]

ma co najwyżej [math]\displaystyle{ n - 1 }[/math] rozwiązań, zatem kongruencja

[math]\displaystyle{ W_n (x) \equiv 0 \pmod{p} }[/math]

ma nie więcej niż [math]\displaystyle{ n }[/math] rozwiązań. Co należało pokazać.
□

Twierdzenie J14
Jeżeli kongruencja

[math]\displaystyle{ 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]\displaystyle{ n }[/math] rozwiązań, to wszystkie współczynniki [math]\displaystyle{ a_k }[/math], gdzie [math]\displaystyle{ k = 0, \ldots, n }[/math], muszą być podzielne przez [math]\displaystyle{ p }[/math].

Dowód

Niech [math]\displaystyle{ S \subset \{ 0, 1, \ldots, n \} }[/math] będzie zbiorem takim, że dla każdego [math]\displaystyle{ k \in S }[/math] jest [math]\displaystyle{ p \nmid a_k }[/math]. Przypuśćmy, że [math]\displaystyle{ S }[/math] jest zbiorem niepustym. Niech [math]\displaystyle{ j }[/math] oznacza największy element zbioru [math]\displaystyle{ S }[/math]. Jeżeli [math]\displaystyle{ j = 0 }[/math], to wielomian [math]\displaystyle{ W_n (x) = \sum_{k = 0}^{n} a_k x^k }[/math] jest stopnia [math]\displaystyle{ 0 }[/math] modulo [math]\displaystyle{ p }[/math] i

[math]\displaystyle{ a_0 \not\equiv 0 \pmod{p} }[/math]

Konsekwentnie, dla dowolnego [math]\displaystyle{ x \in \mathbb{Z} }[/math] jest

[math]\displaystyle{ 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]\displaystyle{ 1 \leqslant k \leqslant n }[/math] mamy [math]\displaystyle{ 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]\displaystyle{ n }[/math].

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

Przykład J15
Z twierdzenia Lagrange'a wynika, że kongruencja

[math]\displaystyle{ x^p - x - 1 \equiv 0 \pmod{p} }[/math]

ma co najwyżej [math]\displaystyle{ p }[/math] rozwiązań. W rzeczywistości nie ma ani jednego rozwiązania, bo z twierdzenia Fermata wiemy, że dla dowolnej liczby pierwszej [math]\displaystyle{ p }[/math] jest

[math]\displaystyle{ x^p \equiv x \pmod{p} }[/math]

Przykład J16
Zauważmy, że w przypadku, gdy [math]\displaystyle{ n \geqslant p }[/math], możemy zawsze wielomian przekształcić do postaci takiej, że [math]\displaystyle{ n \lt p }[/math]. Niech [math]\displaystyle{ p = 5 }[/math] i

[math]\displaystyle{ W(x) = x^{15} + 11 x^{11} + 5 x^5 + 2 x^2 + x + 1 }[/math]

Ponieważ [math]\displaystyle{ x^5 \equiv x \!\! \pmod{5} }[/math], to

[math]\displaystyle{ 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 faktu, że [math]\displaystyle{ W(x) }[/math] można zapisać w postaci

[math]\displaystyle{ 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]\displaystyle{ x^5 - x \equiv 0 \!\! \pmod{5} }[/math] na mocy twierdzenia Fermata.

Twierdzenie Wilsona

Twierdzenie J17 (John Wilson, 1770)
Liczba całkowita [math]\displaystyle{ p \geqslant 2 }[/math] jest liczbą pierwszą wtedy i tylko wtedy, gdy

[math]\displaystyle{ (p - 1) ! \equiv - 1 \pmod{p} }[/math]

Dowód

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

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

[math]\displaystyle{ (p - 1) ! \equiv - 1 \pmod{d} }[/math]

czyli

[math]\displaystyle{ 0 \equiv - 1 \pmod{d} }[/math]

co jest niemożliwe.

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

Łatwo sprawdzamy, że twierdzenie jest prawdziwe dla [math]\displaystyle{ p = 2 }[/math]. Niech teraz [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Rozważmy wielomiany

[math]\displaystyle{ W(x) = (x - 1) (x - 2) \cdot \ldots \cdot (x - (p - 1)) }[/math]

oraz

[math]\displaystyle{ V(x) = x^{p - 1} - 1 }[/math]

Zauważmy, że

• stopnie tych wielomianów są równe [math]\displaystyle{ p - 1 }[/math]
• współczynniki wiodące są równe [math]\displaystyle{ 1 }[/math]
• wyrazy wolne są równe odpowiednio [math]\displaystyle{ (p - 1) ! }[/math] oraz [math]\displaystyle{ - 1 }[/math]
• wielomiany mają [math]\displaystyle{ p - 1 }[/math] rozwiązań modulo [math]\displaystyle{ p }[/math]

Niech

[math]\displaystyle{ U(x) = W (x) - V (x) }[/math]

Zauważmy, że

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

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

Twierdzenie J18
Liczba całkowita nieparzysta [math]\displaystyle{ p \geqslant 3 }[/math] jest liczbą pierwszą wtedy i tylko wtedy, gdy

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

Dowód

Z twierdzenia Wilsona wiemy, że liczba całkowita [math]\displaystyle{ p \geqslant 2 }[/math] jest liczbą pierwszą wtedy i tylko wtedy, gdy

[math]\displaystyle{ (p - 1) ! \equiv - 1 \pmod{p} }[/math]

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

[math]\displaystyle{ 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]\displaystyle{ (- 1)^{\tfrac{p - 1}{2}} \cdot \left[ \left( {\small\frac{p - 1}{2}} \right) ! \right]^2 \equiv - 1 \!\! \pmod{p} }[/math]

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

Co należało pokazać.
□

Twierdzenie Fermata

Twierdzenie J19 (Pierre de Fermat, 1640)
Niech [math]\displaystyle{ a \in \mathbb{Z} }[/math]. Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą

• to liczba [math]\displaystyle{ a^p - a }[/math] jest podzielna przez [math]\displaystyle{ p }[/math], czyli [math]\displaystyle{ a^p \equiv a \!\! \pmod p }[/math]
• i jeśli dodatkowo [math]\displaystyle{ p \nmid a }[/math], to liczba [math]\displaystyle{ a^{p - 1} - 1 }[/math] jest podzielna przez [math]\displaystyle{ p }[/math], czyli [math]\displaystyle{ a^{p - 1} \equiv 1 \!\! \pmod p }[/math]

Dowód

Punkt 1.

Zauważmy, że
a) twierdzenie jest prawdziwe dla [math]\displaystyle{ a = 0 }[/math]
b) w przypadku, gdy [math]\displaystyle{ p = 2 }[/math] wyrażenie [math]\displaystyle{ a^p - a = a^2 - a = a (a - 1) }[/math] jest podzielne przez [math]\displaystyle{ 2 }[/math], bo jedna z liczb [math]\displaystyle{ a - 1 }[/math] i [math]\displaystyle{ a }[/math] jest liczbą parzystą
c) w przypadku, gdy [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i twierdzenie jest prawdziwe dla [math]\displaystyle{ a \geqslant 1 }[/math], to jest też prawdziwe dla [math]\displaystyle{ - a }[/math], bo

[math]\displaystyle{ (- a)^p - (- a) = (- 1)^p a^p + a = - a^p + a = - (a^p - a) }[/math]

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

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

[math]\displaystyle{ (a + 1)^p - (a + 1) = \sum_{k = 0}^{p} \binom{p}{k} \cdot a^k - a - 1 }[/math]

[math]\displaystyle{ \;\;\,\, = 1 + \sum_{k = 1}^{p - 1} \binom{p}{k} \cdot a^k + a^p - a - 1 }[/math]

[math]\displaystyle{ \;\;\,\, = a^p - a + \sum^{p - 1}_{k = 1} \binom{p}{k} \cdot a^k }[/math]

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

Punkt 2.

Z punktu 1. wiemy, że liczba pierwsza [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ a^p - a = a (a^{p - 1} - 1) }[/math]. Jeżeli [math]\displaystyle{ p \nmid a }[/math], to z lematu Euklidesa (zobacz twierdzenie C74) wynika natychmiast, że [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ a^{p - 1} - 1 }[/math].
□

Twierdzenie J20
Niech [math]\displaystyle{ x, y \in \mathbb{Z} }[/math]. Jeżeli [math]\displaystyle{ \gcd (x, y) = 1 }[/math] i liczba pierwsza nieparzysta [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ x^2 + y^2 }[/math], to [math]\displaystyle{ p }[/math] jest postaci [math]\displaystyle{ 4 k + 1 }[/math].

Dowód

Z założenia

[math]\displaystyle{ x^2 \equiv - y^2 \!\! \pmod{p} }[/math]

Przypuśćmy, że [math]\displaystyle{ p \mid y }[/math]. Wtedy z powyższej kongruencji mamy natychmiast, że [math]\displaystyle{ p \mid x }[/math], wbrew założeniu, że [math]\displaystyle{ \gcd (x, y) = 1 }[/math]. Zatem [math]\displaystyle{ p \nmid y }[/math] i z twierdzenia Fermata dostajemy

[math]\displaystyle{ 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]\displaystyle{ {\small\frac{p - 1}{2}} }[/math] musi być liczbą parzystą, czyli [math]\displaystyle{ p = 4 k + 1 }[/math]. Co należało pokazać.
□

Zadanie J21
Niech [math]\displaystyle{ x, y, n \geqslant 0 }[/math]. Pokazać, że jedynymi rozwiązaniami równania

[math]\displaystyle{ x^2 + y^2 = 2^n }[/math]

są liczby

• [math]\displaystyle{ x = 2^{n / 2} \, }[/math] i [math]\displaystyle{ \, y = 0 \, }[/math] lub [math]\displaystyle{ \, x = 0 \, }[/math] i [math]\displaystyle{ \, y = 2^{n / 2} }[/math], gdy [math]\displaystyle{ 2 \mid n }[/math]
• [math]\displaystyle{ x = y = 2^{(n - 1) / 2} }[/math], gdy [math]\displaystyle{ 2 \nmid n }[/math]

Rozwiązanie

A. Gdy jedna z liczb [math]\displaystyle{ x, y }[/math] jest równa [math]\displaystyle{ 0 }[/math] (powiedzmy [math]\displaystyle{ y }[/math]), to mamy [math]\displaystyle{ x = 2^{n / 2} }[/math], gdy [math]\displaystyle{ n }[/math] jest parzyste. Gdy [math]\displaystyle{ n }[/math] jest nieparzyste, to rozwiązanie nie istnieje. Od tej pory będziemy zakładali, że [math]\displaystyle{ x, y \geqslant 1 }[/math]

B. Wiemy, że kwadrat liczby nieparzystej przystaje do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ 4 }[/math]. Gdy obie liczby [math]\displaystyle{ x, y }[/math] są nieparzyste, to modulo [math]\displaystyle{ 4 }[/math] mamy

[math]\displaystyle{ 2 \equiv 2^n \!\! \pmod{4} }[/math]

Kongruencja ta jest prawdziwa tylko dla [math]\displaystyle{ n = 1 }[/math] i w tym przypadku mamy [math]\displaystyle{ (x, y) = (1, 1) }[/math].

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

[math]\displaystyle{ u^2 + 2^{2 b - 2 a} w^2 = 2^{n - 2 a} }[/math]

Widzimy, że nie może być [math]\displaystyle{ a \lt b }[/math], bo suma liczby nieparzystej i parzystej nie jest liczbą parzystą. Zatem [math]\displaystyle{ a = b }[/math] i otrzymujemy równanie

[math]\displaystyle{ u^2 + w^2 = 2^{n - 2 a} }[/math]

które ma rozwiązanie w liczbach nieparzystych tylko dla wykładnika [math]\displaystyle{ n - 2 a = 1 }[/math]. Mamy [math]\displaystyle{ u = w = 1 }[/math], zatem [math]\displaystyle{ x = y = 2^{(n - 1) / 2} }[/math] i [math]\displaystyle{ n }[/math] musi być liczbą nieparzystą.
□

Twierdzenie J22
Niech [math]\displaystyle{ x, y \in \mathbb{Z}_+ }[/math]. Jeżeli [math]\displaystyle{ x \neq y }[/math], to liczba [math]\displaystyle{ x^2 + y^2 }[/math] ma dzielnik pierwszy postaci [math]\displaystyle{ 4 k + 1 }[/math].

Dowód

W przypadku, gdy [math]\displaystyle{ x = y }[/math] mamy [math]\displaystyle{ x^2 + y^2 = 2 y^2 }[/math] i jeśli liczba [math]\displaystyle{ y }[/math] nie ma dzielnika pierwszego postaci [math]\displaystyle{ 4 k + 1 }[/math], to nie ma go również liczba [math]\displaystyle{ 2 y^2 }[/math]. Przykładowo [math]\displaystyle{ 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]\displaystyle{ x \neq y }[/math]. Analogiczna sytuacja ma miejsce, gdy jedna z liczb [math]\displaystyle{ x, y }[/math] jest równa zero. Dlatego zakładamy, że [math]\displaystyle{ x, y \in \mathbb{Z}_+ }[/math].

Niech [math]\displaystyle{ \gcd (x, y) = d }[/math], zatem mamy [math]\displaystyle{ x = a d }[/math], [math]\displaystyle{ y = b d }[/math]. Wynika stąd, że [math]\displaystyle{ x^2 + y^2 = d^2 (a^2 + b^2) }[/math], gdzie [math]\displaystyle{ \gcd (a, b) = 1 \, }[/math] i [math]\displaystyle{ \, a \neq b }[/math]. Ponieważ [math]\displaystyle{ \, a \neq b }[/math], to liczba [math]\displaystyle{ a^2 + b^2 }[/math] musi mieć dzielnik pierwszy nieparzysty (zobacz J21). Z twierdzenia J20 zastosowanego do liczby [math]\displaystyle{ a^2 + b^2 }[/math] wynika, że [math]\displaystyle{ a^2 + b^2 }[/math] musi mieć dzielnik pierwszy postaci [math]\displaystyle{ 4 k + 1 }[/math].
□

Kryterium Eulera

Definicja J23
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą i [math]\displaystyle{ a \in \mathbb{Z} }[/math]. Powiemy, że liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math], jeżeli kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{p} }[/math]

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

Powiemy, że liczba [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], jeżeli kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{p} }[/math]

nie ma rozwiązania.

Twierdzenie J24
Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą, to wśród liczb [math]\displaystyle{ 1, 2, \ldots, p - 1 }[/math] istnieje dokładnie [math]\displaystyle{ {\small\frac{p - 1}{2}} }[/math] liczb kwadratowych modulo [math]\displaystyle{ p }[/math] i tyle samo liczb niekwadratowych modulo [math]\displaystyle{ p }[/math].

Dowód

Zauważmy, że w rozważanym zbiorze liczb [math]\displaystyle{ \{ 1, 2, \ldots, p - 1 \} }[/math], kwadraty liczb [math]\displaystyle{ k }[/math] i [math]\displaystyle{ p - k }[/math] są takimi samymi liczbami modulo [math]\displaystyle{ p }[/math], co wynika z oczywistej kongruencji

[math]\displaystyle{ k^2 \equiv (p - k)^2 \pmod{p} }[/math]

Pozwala to wypisać pary liczb, których kwadraty są identyczne modulo [math]\displaystyle{ p }[/math]

[math]\displaystyle{ (1, p - 1), (2, p - 2), \ldots, \left( {\small\frac{p - 1}{2}}, p - {\small\frac{p - 1}{2}} \right) }[/math]

Ponieważ

[math]\displaystyle{ 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]\displaystyle{ \{ 1, 2, \ldots, p - 1 \} }[/math]. Co więcej, liczby [math]\displaystyle{ 1^2, 2^2, \ldots, \left( {\small\frac{p - 1}{2}} \right)^2 }[/math] są wszystkie różne modulo [math]\displaystyle{ p }[/math]. Istotnie, przypuśćmy, że [math]\displaystyle{ 1 \leqslant i, j \leqslant {\small\frac{p - 1}{2}} }[/math] oraz [math]\displaystyle{ i \neq j }[/math], a jednocześnie [math]\displaystyle{ i^2 \equiv j^2 \!\! \pmod{p} }[/math]. Gdyby tak było, to mielibyśmy

[math]\displaystyle{ (i - j) (i + j) \equiv 0 \pmod{p} }[/math]

Łatwo zauważamy, że jest to niemożliwe, bo żaden z czynników nie jest podzielny przez [math]\displaystyle{ p }[/math], co wynika z prostych oszacowań

[math]\displaystyle{ 1 \leqslant | i - j | \leqslant i + j \lt p - 1 }[/math]

[math]\displaystyle{ 2 \lt i + j \lt p - 1 }[/math]

Ponieważ (z definicji) liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math], jeżeli kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{p} }[/math]

ma rozwiązanie, to liczba kwadratowa modulo [math]\displaystyle{ p }[/math] musi przystawać do pewnego kwadratu modulo [math]\displaystyle{ p }[/math].

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

Twierdzenie J25 (kryterium Eulera, 1748)
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą i [math]\displaystyle{ p \nmid a }[/math]. Modulo [math]\displaystyle{ p }[/math] mamy

●	liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ a^{(p - 1) / 2} \equiv 1 \pmod{p} }[/math]
●	liczba [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ a^{(p - 1) / 2} \equiv - 1 \pmod{p} }[/math]

Dowód

Punkt 1.

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

[math]\displaystyle{ x^{(p - 1) / 2} \equiv 1 \pmod{p} }[/math]

Zauważmy, że

A	[math]\displaystyle{ | Q | = {\small\frac{p - 1}{2}} }[/math]	zobacz J24
B	[math]\displaystyle{ | S | \leqslant {\small\frac{p - 1}{2}} }[/math]	zobacz twierdzenie Lagrange'a J13
C	jeżeli [math]\displaystyle{ a \in Q }[/math], to [math]\displaystyle{ a \in S \qquad }[/math]	wynika z ciągu implikacji:          [math]\displaystyle{ a \in Q \qquad \Longrightarrow \qquad a \equiv k^2 \pmod{p} }[/math]          [math]\displaystyle{ 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]             [math]\displaystyle{ a^{(p - 1) / 2} \equiv 1 \pmod{p} \qquad \Longrightarrow \qquad a \in S }[/math]
D	[math]\displaystyle{ Q \subseteq S }[/math]	z punktu C wynika, że każdy element zbioru [math]\displaystyle{ Q }[/math] należy do zbioru [math]\displaystyle{ S }[/math]

Łącząc rezultaty z tabeli, otrzymujemy

[math]\displaystyle{ {\small\frac{p - 1}{2}} = | Q | \leqslant | S | \leqslant {\small\frac{p - 1}{2}} }[/math]

Skąd łatwo widzimy, że

[math]\displaystyle{ | Q | = | S | = {\small\frac{p - 1}{2}} }[/math]

Ponieważ [math]\displaystyle{ Q \subseteq S }[/math], a zbiory [math]\displaystyle{ Q }[/math] i [math]\displaystyle{ S }[/math] są równoliczne, to zbiory te są równe (zobacz J26). Prostą konsekwencją równości zbiorów [math]\displaystyle{ Q }[/math] i [math]\displaystyle{ S }[/math] jest stwierdzenie

liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ a^{(p - 1) / 2} \equiv 1 \pmod{p} }[/math]

Co kończy dowód punktu pierwszego.

Punkt 2.

Z udowodnionego już punktu pierwszego wynika, że

liczba [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ a^{(p - 1) / 2} \not\equiv 1 \pmod{p} }[/math]

Z twierdzenia Fermata

[math]\displaystyle{ 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]\displaystyle{ a^{(p - 1) / 2} - 1 \not\equiv 0 \pmod{p} }[/math], to musi być

[math]\displaystyle{ a^{(p - 1) / 2} + 1 \equiv 0 \pmod{p} }[/math]

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

liczba [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ a^{(p - 1) / 2} \equiv - 1 \pmod{p} }[/math]

Co należało pokazać.
□

Zadanie J26
Niech [math]\displaystyle{ A }[/math] i [math]\displaystyle{ B }[/math] będą zbiorami skończonymi. Pokazać, że jeżeli [math]\displaystyle{ A \subseteq B \;\; \text{i} \;\; | A | = | B | }[/math], to [math]\displaystyle{ \; A = B }[/math].

Rozwiązanie

Ponieważ zbiór [math]\displaystyle{ A }[/math] jest podzbiorem zbioru [math]\displaystyle{ B }[/math], to zbiór [math]\displaystyle{ B }[/math] można przedstawić w postaci sumy zbiorów [math]\displaystyle{ A }[/math] i [math]\displaystyle{ C }[/math] takich, że żaden element zbioru [math]\displaystyle{ C }[/math] nie jest elementem zbioru [math]\displaystyle{ A }[/math]. Zatem

[math]\displaystyle{ B = A \cup C \qquad \text{i} \qquad A \cap C = \varnothing }[/math]

Ponieważ z założenia zbiory [math]\displaystyle{ A }[/math] i [math]\displaystyle{ C }[/math] są rozłączne, to wiemy, że

[math]\displaystyle{ | A \cup C | = | A | + | C | }[/math]

Czyli

[math]\displaystyle{ | B | = | A \cup C | = | A | + | C | }[/math]

Skąd wynika, że [math]\displaystyle{ | C | = 0 }[/math], zatem zbiór [math]\displaystyle{ C }[/math] jest zbiorem pustym i otrzymujemy natychmiast [math]\displaystyle{ B = A }[/math]. Co należało pokazać.

Uwaga (przypadek zbiorów skończonych)
Najczęściej prawdziwe jest jedynie oszacowanie [math]\displaystyle{ | A \cup C | \leqslant | A | + | C | }[/math], bo niektóre elementy mogą zostać policzone dwa razy. Elementy liczone dwukrotnie to te, które należą do iloczynu zbiorów [math]\displaystyle{ | A | }[/math] i [math]\displaystyle{ | C | }[/math], zatem od sumy [math]\displaystyle{ | A | + | C | }[/math] musimy odjąć liczbę elementów iloczynu zbiorów [math]\displaystyle{ | A | }[/math] i [math]\displaystyle{ | C | }[/math]. Co daje ogólny wzór

[math]\displaystyle{ | A \cup C | = | A | + | C | - | A \cap C | }[/math]

□

Symbol Legendre'a

Definicja J27
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą i [math]\displaystyle{ a \in \mathbb{Z} }[/math]. Symbolem Legendre'a nazywamy funkcję [math]\displaystyle{ a }[/math] i [math]\displaystyle{ p }[/math] zdefiniowaną następująco

[math]\displaystyle{ \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} = \begin{cases} \;\;\: 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{cases} }[/math]

Uwaga J28
Powyższa definicja pozwala nam zapisać kryterium Eulera w zwartej formie, która obejmuje również przypadek, gdy [math]\displaystyle{ p \mid a }[/math]

[math]\displaystyle{ a^{(p - 1) / 2} \equiv \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \pmod{p} }[/math]

Twierdzenie J29*
Niech [math]\displaystyle{ a, b \in \mathbb{Z} }[/math] oraz [math]\displaystyle{ p, q }[/math] będą nieparzystymi liczbami pierwszymi. Symbol Legendre'a ma następujące właściwości

1.	[math]\displaystyle{ \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \,\, = \,\, 0 \quad \Longleftrightarrow \quad \gcd (a, p) \gt 1 }[/math]
2.	[math]\displaystyle{ 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]
3.	[math]\displaystyle{ \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]
4.	[math]\displaystyle{ a^{(p - 1) / 2} \equiv \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \pmod{p} }[/math]
5.	[math]\displaystyle{ \left( {\small\frac{1}{p}} \right)_{\small{\!\! L}} \,\, = \,\, 1 }[/math]
6.	[math]\displaystyle{ \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]
7.	[math]\displaystyle{ \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]
8.	[math]\displaystyle{ \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]
9.	[math]\displaystyle{ \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]

Symbol Jacobiego

Definicja J30
Niech liczby [math]\displaystyle{ a \in \mathbb{Z} }[/math] i [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math] będą względnie pierwsze. Powiemy, że liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ m }[/math], jeżeli kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{m} }[/math]

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

Powiemy, że liczba [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ m }[/math], jeżeli kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{m} }[/math]

nie ma rozwiązania.

Uwaga J31
Prosta funkcja pozwala łatwo sprawdzić, czy liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ m }[/math].

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

Uwaga J32
Ponieważ często można spotkać definicję liczb kwadratowych i niekwadratowych modulo [math]\displaystyle{ m }[/math], w której warunek [math]\displaystyle{ \gcd (a, m) = 1 }[/math] zostaje pominięty, to Czytelnik powinien zawsze upewnić się, jaka definicja jest stosowana. Najczęściej w takim przypadku liczba [math]\displaystyle{ 0 }[/math] nie jest uznawana za liczbę kwadratową modulo [math]\displaystyle{ m }[/math].

Przykładowo:

[math]\displaystyle{ \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]\displaystyle{ 10 }[/math] to [math]\displaystyle{ \left\{ 1, 9 \right\} }[/math], a niekwadratowe to [math]\displaystyle{ \left\{ 3, 7 \right\} }[/math]. Liczby [math]\displaystyle{ \left\{ 0, 2, 4, 5, 6, 8 \right\} }[/math] nie są ani liczbami kwadratowymi, ani liczbami niekwadratowymi modulo [math]\displaystyle{ 10 }[/math].

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

Inny przykład. Niech [math]\displaystyle{ m = 210 = 2 \cdot 3 \cdot 5 \cdot 7 }[/math]. W zależności od przyjętej definicji najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ m }[/math] będzie albo [math]\displaystyle{ 11 }[/math], albo [math]\displaystyle{ 2 }[/math].

Zadanie J33
Niech liczby [math]\displaystyle{ m, n \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ \gcd (m, n) = 1 }[/math]. Pokazać, że liczba [math]\displaystyle{ a \in \mathbb{Z} }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ m n }[/math] wtedy i tylko wtedy, gdy jest liczbą kwadratową modulo [math]\displaystyle{ m }[/math] i modulo [math]\displaystyle{ n }[/math].

Rozwiązanie

Niech [math]\displaystyle{ W(x) = x^2 - a }[/math]. Zauważmy, że liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ m }[/math] wtedy i tylko wtedy, gdy kongruencja [math]\displaystyle{ W(x) \equiv 0 \!\! \pmod{m} }[/math] ma rozwiązanie. Dalsza analiza problemu przebiega dokładnie tak, jak to zostało przedstawione w uwadze J11.
□

Definicja J34
Symbol Jacobiego [math]\displaystyle{ \left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} }[/math] jest uogólnieniem symbolu Legendre'a [math]\displaystyle{ \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} }[/math] dla dodatnich liczb nieparzystych. Niech [math]\displaystyle{ n = \prod_i p_i^{\alpha_i} }[/math] będzie rozkładem liczby [math]\displaystyle{ n }[/math] na czynniki pierwsze, wtedy

[math]\displaystyle{ \left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} = \prod_i \left( {\small\frac{a}{p_i}} \right)_{\small{\!\! L}}^{\!\! \alpha_i} }[/math]

Uwaga J35
Zauważmy, że w przypadku gdy [math]\displaystyle{ 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]\displaystyle{ a \in \mathbb{Z} }[/math] jest [math]\displaystyle{ \left( {\small\frac{a}{1}} \right)_{\small{\!\! J}} = 1 }[/math].

Twierdzenie J36*
Niech [math]\displaystyle{ a, b \in \mathbb{Z} }[/math] oraz [math]\displaystyle{ m, n \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ m, n }[/math] będą liczbami nieparzystymi. Symbol Jacobiego ma następujące właściwości

1.	[math]\displaystyle{ \left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} \,\, = \,\, 0 \quad \Longleftrightarrow \quad \gcd (a, n) \gt 1 }[/math]
2.	[math]\displaystyle{ 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]
3.	[math]\displaystyle{ \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]
4.	[math]\displaystyle{ \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]
5.	[math]\displaystyle{ \left( {\small\frac{1}{n}} \right)_{\small{\!\! J}} \,\, = \,\, 1 }[/math]
6.	[math]\displaystyle{ \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]
7.	[math]\displaystyle{ \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]
8.	[math]\displaystyle{ \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]
9.	[math]\displaystyle{ \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]

Uwaga J37
Zauważmy, że poza zmienionym założeniem tabela z powyższego twierdzenia i tabela z twierdzenia J29 różnią się jedynie punktem czwartym. Oczywiście jest to tylko podobieństwo formalne – symbol Legendre'a i symbol Jacobiego są różnymi funkcjami.

Uwaga J38
Zauważmy, że w przypadku, gdy [math]\displaystyle{ m }[/math] jest liczbą nieparzystą

• jeżeli [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1 }[/math], to [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ m }[/math]
• jeżeli [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ m }[/math], to nie musi być [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1 }[/math]
• jeżeli [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = + 1 }[/math], to [math]\displaystyle{ a }[/math] nie musi być liczbą kwadratową modulo [math]\displaystyle{ m }[/math]
• jeżeli [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ m }[/math], to jest [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = + 1 }[/math]

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

Modulo [math]\displaystyle{ 9 }[/math] liczbami niekwadratowymi są: [math]\displaystyle{ 2, 5, 8 }[/math]. Modulo [math]\displaystyle{ 25 }[/math] liczbami niekwadratowymi są: [math]\displaystyle{ 2, 3, 7, 8, 12, 13, 17, 18, 22, 23 }[/math].

Uwaga J39
Wszystkie liczby kwadratowe i niekwadratowe modulo [math]\displaystyle{ m }[/math] można łatwo znaleźć, wykorzystując prosty program:

Pokaż kod

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
}

Zadanie J40
Pokazać, że

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

Rozwiązanie

Zauważmy, że

[math]\displaystyle{ \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]\displaystyle{ \; = (- 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]\displaystyle{ \; = (- 1)^{m - 1} \cdot \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}} }[/math]

[math]\displaystyle{ \; = \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}} }[/math]

bo [math]\displaystyle{ m }[/math] jest liczbą nieparzystą.

Rozważmy liczby nieparzyste [math]\displaystyle{ m }[/math] postaci [math]\displaystyle{ 6 k + r }[/math], gdzie [math]\displaystyle{ r = 1, 3, 5 }[/math]. Mamy

[math]\displaystyle{ \left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}} }[/math]

[math]\displaystyle{ \; = \left( {\small\frac{6 k + r}{3}} \right)_{\small{\!\! J}} }[/math]

[math]\displaystyle{ \; = \left( {\small\frac{r}{3}} \right)_{\small{\!\! J}} }[/math]

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

bo odpowiednio dla [math]\displaystyle{ r = 1, 3, 5 }[/math] jest

[math]\displaystyle{ \left( {\small\frac{1}{3}} \right)_{\small{\!\! J}} = 1 }[/math]

[math]\displaystyle{ \left( {\small\frac{3}{3}} \right)_{\small{\!\! J}} = 0 }[/math]

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

Zadanie J41
Pokazać, że

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

Rozwiązanie

Punkt 1.

Przy wyliczaniu symboli Legendre'a i Jacobiego, zawsze warto sprawdzić, czy da się ustalić przystawanie liczb modulo [math]\displaystyle{ 4 }[/math]. W tym przypadku mamy

[math]\displaystyle{ 3 \equiv 3 \pmod{4} }[/math]

i odpowiednio dla różnych postaci liczby [math]\displaystyle{ m }[/math] jest

[math]\displaystyle{ m = 12 k + 1 \equiv 1 \pmod{4} }[/math]

[math]\displaystyle{ m = 12 k + 5 \equiv 1 \pmod{4} }[/math]

[math]\displaystyle{ m = 12 k + 7 \equiv 3 \pmod{4} }[/math]

[math]\displaystyle{ m = 12 k + 11 \equiv 3 \pmod{4} }[/math]

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

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

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

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

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

Punkt 2.

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

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

Rozważmy liczby nieparzyste [math]\displaystyle{ m }[/math] postaci [math]\displaystyle{ 10 k + r }[/math], gdzie [math]\displaystyle{ r = 1, 3, 5, 7, 9 }[/math]. Mamy

[math]\displaystyle{ \left( {\small\frac{5}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{m}{5}} \right)_{\small{\!\! J}} }[/math]

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

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

[math]\displaystyle{ \:\, \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]\displaystyle{ r = 1, 3, 5, 7, 9 }[/math] jest

[math]\displaystyle{ \left( {\small\frac{1}{5}} \right)_{\small{\!\! J}} = 1 }[/math]

[math]\displaystyle{ \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]\displaystyle{ \left( {\small\frac{5}{5}} \right)_{\small{\!\! J}} = 0 }[/math]

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

[math]\displaystyle{ \left( {\small\frac{9}{5}} \right)_{\small{\!\! J}} = \left( {\small\frac{3}{5}} \right)_{\small{\!\! J}}^{\! 2} = 1 }[/math]

Co należało pokazać.
□

Uwaga J42
Wykorzystując podane w twierdzeniu J36 właściwości symbolu Jacobiego, możemy napisać prostą funkcję w PARI/GP znajdującą jego wartość. Zauważmy, że nie potrzebujemy znać rozkładu liczby [math]\displaystyle{ n }[/math] na czynniki pierwsze.

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 ≡ 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 ≡ 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 ≡ n ≡ 3 (mod 4)
       a = a % n;
     );
if( n == 1, return(w), return(0) ); \\ n jest teraz równe gcd(a, n)
}

Uwaga J43
Jeżeli [math]\displaystyle{ m }[/math] jest liczbą pierwszą, to symbol Jacobiego jest symbolem Legendre'a, czyli [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{a}{m}} \right)_{\small{\!\! L}} }[/math]. Jeżeli [math]\displaystyle{ m }[/math] jest liczbą złożoną, to symbol Legendre'a [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! L}} }[/math] nie istnieje, a symbol Jacobiego [math]\displaystyle{ \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 formie uproszczonej [math]\displaystyle{ (a \mid m) }[/math] i nie będziemy rozróżniali tych symboli. Interpretacja zapisu jest prosta:

• jeżeli wiemy, że [math]\displaystyle{ m }[/math] jest liczbą pierwszą, to symbol [math]\displaystyle{ (a \mid m) }[/math] jest symbolem Legendre'a
• jeżeli wiemy, że [math]\displaystyle{ m }[/math] jest liczbą złożoną, to symbol [math]\displaystyle{ (a \mid m) }[/math] jest symbolem Jacobiego
• jeżeli nie wiemy, czy [math]\displaystyle{ m }[/math] jest liczbą pierwszą, czy złożoną, to symbol [math]\displaystyle{ (a \mid m) }[/math] jest symbolem Jacobiego

Rozwiązywanie kongruencji [math]\displaystyle{ x^2 \equiv a \!\! \pmod{m} }[/math]

Twierdzenie J44
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą, zaś [math]\displaystyle{ a }[/math] liczbą całkowitą taką, że [math]\displaystyle{ \gcd (a, p) = 1 }[/math]. Kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{p^n} }[/math]

ma rozwiązanie wtedy i tylko wtedy, gdy kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{p} }[/math]

ma rozwiązanie.

Dowód

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

Z założenia kongruencja [math]\displaystyle{ x^2 \equiv a \!\! \pmod{p^n} }[/math] ma rozwiązanie. Zatem istnieje taka liczba [math]\displaystyle{ r \in \mathbb{Z} }[/math], że

[math]\displaystyle{ r^2 \equiv a \pmod{p^n} }[/math]

Ponieważ [math]\displaystyle{ p^n \mid (r^2 - a) }[/math], to tym bardziej [math]\displaystyle{ p \mid (r^2 - a) }[/math], co oznacza, że prawdziwa jest kongruencja

[math]\displaystyle{ r^2 \equiv a \pmod{p} }[/math]

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

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

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

[math]\displaystyle{ x^2 \equiv a \pmod{p^n} }[/math]

ma rozwiązanie [math]\displaystyle{ x \equiv u_n \!\! \pmod{p^n} }[/math] i pokażmy, że twierdzenie jest prawdziwe dla [math]\displaystyle{ n + 1 }[/math], czyli że rozwiązanie ma kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{p^{n + 1}} }[/math]

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

[math]\displaystyle{ u^2_n - a = k p^n }[/math]

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

[math]\displaystyle{ 2 u_n \cdot s - p \cdot l = - k }[/math]

ma rozwiązanie (zobacz C76). Niech liczby [math]\displaystyle{ s_0 }[/math] i [math]\displaystyle{ l_0 }[/math] będą rozwiązaniem tego równania. Zatem

[math]\displaystyle{ 2 u_n \cdot s_0 - p \cdot l_0 = - k }[/math]

[math]\displaystyle{ 2 u_n \cdot s_0 p^n - l_0 \cdot p^{n + 1} = - k p^n }[/math]

[math]\displaystyle{ 2 u_n \cdot s_0 p^n - l_0 \cdot p^{n + 1} = - ( u^2_n - a ) }[/math]

[math]\displaystyle{ u^2_n + 2 u_n \cdot s_0 p^n = a + l_0 \cdot p^{n + 1} }[/math]

Modulo [math]\displaystyle{ p^{n + 1} }[/math] dostajemy

[math]\displaystyle{ u^2_n + 2 u_n \cdot s_0 p^n \equiv a \pmod{p^{n + 1}} }[/math]

[math]\displaystyle{ (u_n + s_0 p^n)^2 \equiv a \pmod{p^{n + 1}} }[/math]

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

[math]\displaystyle{ x^2 \equiv a \pmod{p^{n + 1}} }[/math]

Pokazaliśmy tym samym prawdziwość tezy indukcyjnej, co kończy dowód indukcyjny.
□

Uwaga J45
Dla niewielkich modułów rozwiązania dowolnej kongruencji możemy znaleźć przez bezpośrednie sprawdzenie. Omówimy teraz rozwiązania kongruencji [math]\displaystyle{ x^2 \equiv a \!\! \pmod{2^n} }[/math] dla [math]\displaystyle{ n = 1, 2, 3 }[/math]. Ponieważ zakładamy, że [math]\displaystyle{ \gcd (a, m) = \gcd (a, 2^n) = 1 }[/math], to [math]\displaystyle{ a }[/math] musi być liczbą nieparzystą, zaś [math]\displaystyle{ x }[/math] nie może być liczbą parzystą. Istotnie, gdyby tak było, to mielibyśmy [math]\displaystyle{ 0 \equiv 1 \!\! \pmod{2} }[/math], bo [math]\displaystyle{ 2 \mid 2^n }[/math].

Kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{2} }[/math]

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

Kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{4} }[/math]

ma dwa rozwiązania, gdy [math]\displaystyle{ a \equiv 1 \!\! \pmod{4} }[/math]. Rozwiązaniami są: [math]\displaystyle{ x \equiv 1, 3 \!\! \pmod{4} }[/math]. W przypadku, gdy [math]\displaystyle{ a \equiv 3 \!\! \pmod{4} }[/math] kongruencja nie ma rozwiązań.

Kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{8} }[/math]

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

Twierdzenie J46
Niech [math]\displaystyle{ n \geqslant 3 }[/math] i [math]\displaystyle{ a }[/math] będzie liczbą nieparzystą. Kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{2^n} }[/math]

ma rozwiązanie wtedy i tylko wtedy, gdy kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{8} }[/math]

ma rozwiązanie.

Dowód

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

Z założenia kongruencja [math]\displaystyle{ x^2 \equiv a \!\! \pmod{2^n} }[/math] ma rozwiązanie, zatem istnieje taka liczba [math]\displaystyle{ r \in \mathbb{Z} }[/math], że

[math]\displaystyle{ r^2 \equiv a \pmod{2^n} }[/math]

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

[math]\displaystyle{ r^2 \equiv a \pmod{2^3} }[/math]

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

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

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

[math]\displaystyle{ x^2 \equiv a \pmod{2^n} }[/math]

ma rozwiązanie [math]\displaystyle{ x \equiv u_n \!\! \pmod{2^n} }[/math] i pokażemy, że twierdzenie jest prawdziwe dla [math]\displaystyle{ n + 1 }[/math], czyli że rozwiązanie ma kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{2^{n + 1}} }[/math]

Z założenia istnieje taka liczba [math]\displaystyle{ k }[/math], że [math]\displaystyle{ u^2_n - a = k \cdot 2^n }[/math]. Niech

[math]\displaystyle{ 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]\displaystyle{ (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]\displaystyle{ \;\! = k \cdot 2^n + 2^n r + r^2 \cdot 2^{2 n - 2} }[/math]

[math]\displaystyle{ \;\! = 2^n (k + r) + r^2 \cdot 2^{2 n - 2} }[/math]

[math]\displaystyle{ \;\! \equiv 0 \pmod{2^{n + 1}} }[/math]

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

[math]\displaystyle{ x^2 \equiv a \pmod{2^{n + 1}} }[/math]

Pokazaliśmy tym samym prawdziwość tezy indukcyjnej, co kończy dowód indukcyjny.
□

Wniosek J47
Jeżeli [math]\displaystyle{ a }[/math] jest liczbą nieparzystą, to kongruencja [math]\displaystyle{ x^2 \equiv a \!\! \pmod{2^n} }[/math] ma rozwiązanie wtedy i tylko wtedy, gdy [math]\displaystyle{ a }[/math] jest postaci [math]\displaystyle{ 2 k + 1 }[/math], [math]\displaystyle{ 4 k + 1 }[/math] lub [math]\displaystyle{ 8 k + 1 }[/math] w zależności od tego, czy [math]\displaystyle{ n = 1 }[/math], czy [math]\displaystyle{ n = 2 }[/math], czy [math]\displaystyle{ n \geqslant 3 }[/math].

Uwaga J48
Niech [math]\displaystyle{ m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math] i [math]\displaystyle{ \gcd (a, m) = 1 }[/math]. Z chińskiego twierdzenia o resztach (zobacz J3 i J11) wynika, że kongruencja [math]\displaystyle{ x^2 \equiv a \!\! \pmod{m} }[/math] ma rozwiązanie wtedy i tylko wtedy, gdy ma rozwiązanie każda z kongruencji

[math]\displaystyle{ \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 J27, twierdzeń J44 i J46, uwagi J45 i wniosku J47 otrzymujemy

Twierdzenie J49
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ \gcd (a, m) = 1 }[/math]. Kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{m} }[/math]

ma rozwiązanie wtedy i tylko wtedy, gdy

●    dla każdego nieparzystego dzielnika pierwszego [math]\displaystyle{ p }[/math] liczby [math]\displaystyle{ m }[/math] jest  [math]\displaystyle{ \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} = 1 }[/math]

●    jeżeli  [math]\displaystyle{ 8 \mid m }[/math],  to  [math]\displaystyle{ 8 \mid ( a - 1 ) }[/math]

●    jeżeli  [math]\displaystyle{ 8 \nmid m }[/math],  ale  [math]\displaystyle{ 4 \mid m }[/math],  to  [math]\displaystyle{ 4 \mid ( a - 1 ) }[/math]

Twierdzenie J50
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ \gcd (a, m) = 1 }[/math]. Kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{m} }[/math]

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

●    jeżeli dla dowolnego nieparzystego dzielnika [math]\displaystyle{ d }[/math] liczby [math]\displaystyle{ m }[/math] jest [math]\displaystyle{ \left( {\small\frac{a}{d}} \right)_{\small{\!\! J}} = - 1 }[/math]

●    jeżeli  [math]\displaystyle{ 8 \mid m }[/math]  i  [math]\displaystyle{ 8 \nmid ( a - 1 ) }[/math]

●    jeżeli  [math]\displaystyle{ 8 \nmid m }[/math],  ale  [math]\displaystyle{ 4 \mid m }[/math]  i  [math]\displaystyle{ 4 \nmid ( a - 1 ) }[/math]

Dowód

Punkt 1.

Z założenia [math]\displaystyle{ d \mid m }[/math]. Gdyby kongruencja

[math]\displaystyle{ x^2 \equiv a \pmod{m} }[/math]

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

[math]\displaystyle{ x^2 \equiv a \pmod{d} }[/math]

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

Punkty 2. i 3. wynikają wprost z twierdzenia J49.
□

Przykład J51
Zauważmy, że [math]\displaystyle{ \left( {\small\frac{17}{19}} \right)_{\small{\!\! J}} = \left( {\small\frac{5}{19}} \right)_{\small{\!\! J}} = 1 }[/math] oraz [math]\displaystyle{ \left( {\small\frac{17}{23}} \right)_{\small{\!\! J}} = \left( {\small\frac{5}{23}} \right)_{\small{\!\! J}} = - 1 }[/math]. W tabelach zestawiliśmy kongruencje i ich rozwiązania.

Kongruencje	Rozwiązania
[math]\displaystyle{ x^2 \equiv 17 \pmod{16 \cdot 19} }[/math]	[math]\displaystyle{ 25, 63, 89, 127, 177, 215, 241, 279 }[/math]
[math]\displaystyle{ x^2 \equiv 17 \pmod{8 \cdot 19} }[/math]	[math]\displaystyle{ 13, 25, 51, 63, 89, 101, 127, 139 }[/math]
[math]\displaystyle{ x^2 \equiv 5 \;\, \pmod{8 \cdot 19} }[/math]	[math]\displaystyle{ \text{brak} }[/math]
[math]\displaystyle{ x^2 \equiv 5 \;\, \pmod{4 \cdot 19} }[/math]	[math]\displaystyle{ 9, 29, 47, 67 }[/math]

Kongruencje	Rozwiązania
[math]\displaystyle{ x^2 \equiv 17 \pmod{16 \cdot 23} }[/math]	[math]\displaystyle{ \text{brak} }[/math]
[math]\displaystyle{ x^2 \equiv 17 \pmod{8 \cdot 23} }[/math]	[math]\displaystyle{ \text{brak} }[/math]
[math]\displaystyle{ x^2 \equiv 5 \;\, \pmod{8 \cdot 23} }[/math]	[math]\displaystyle{ \text{brak} }[/math]
[math]\displaystyle{ x^2 \equiv 5 \;\, \pmod{4 \cdot 23} }[/math]	[math]\displaystyle{ \text{brak} }[/math]

Zadanie J52
Rozwiązać kongruencję, gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą

[math]\displaystyle{ x^2 + rx + s \equiv 0 \pmod{p} }[/math]

Rozwiązanie

Ponieważ [math]\displaystyle{ \gcd (2, p) = 1 }[/math], to nie zmniejszając ogólności kongruencję powyższą możemy zapisać w postaci

[math]\displaystyle{ 4 x^2 + 4 rx + 4 s \equiv 0 \pmod{p} }[/math]

[math]\displaystyle{ (2 x + r)^2 - r^2 + 4 s \equiv 0 \pmod{p} }[/math]

[math]\displaystyle{ (2 x + r)^2 \equiv r^2 - 4 s \pmod{p} }[/math]

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

[math]\displaystyle{ (2 x + r)^2 \equiv b^2 \pmod{p} }[/math]

[math]\displaystyle{ 2 x + r \equiv \pm b \pmod{p} }[/math]

[math]\displaystyle{ x \equiv {\small\frac{p + 1}{2}} \cdot (- r \pm b) \pmod{p} }[/math]

Jeśli [math]\displaystyle{ r^2 - 4 s }[/math] nie jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math], to kongruencja

[math]\displaystyle{ (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]\displaystyle{ x^2 + rx + s \equiv 0 \pmod{p} }[/math]

również nie ma rozwiązania.
□

Zadanie J53
Rozwiązać kongruencję

[math]\displaystyle{ 5 x^2 + 6 x + 8 \equiv 0 \pmod{19} }[/math]

Rozwiązanie

Rozwiązywanie kongruencji w przypadku konkretnych wartości liczb [math]\displaystyle{ r, s }[/math] jest łatwiejsze niż w przypadku ogólnym. Mnożąc obie strony kongruencji przez [math]\displaystyle{ 4 }[/math], otrzymujemy

[math]\displaystyle{ x^2 + 24 x + 32 \equiv 0 \pmod{19} }[/math]

[math]\displaystyle{ x^2 + 24 x + 13 \equiv 0 \pmod{19} }[/math]

Celowo zostawiliśmy parzysty współczynnik przy [math]\displaystyle{ x }[/math]. Gdyby był nieparzysty, to zawsze możemy dodać do niego nieparzysty moduł.

[math]\displaystyle{ (x + 12)^2 - 144 + 13 \equiv 0 \pmod{19} }[/math]

[math]\displaystyle{ (x + 12)^2 + 2 \equiv 0 \pmod{19} }[/math]

[math]\displaystyle{ (x + 12)^2 \equiv - 2 \pmod{19} }[/math]

[math]\displaystyle{ (x + 12)^2 \equiv 6^2 \pmod{19} }[/math]

[math]\displaystyle{ x + 12 \equiv \pm 6 \pmod{19} }[/math]

Otrzymujemy: [math]\displaystyle{ x \equiv 1 \!\! \pmod{19} }[/math] lub [math]\displaystyle{ x \equiv 13 \!\! \pmod{19} }[/math].

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

[math]\displaystyle{ x^2 + 24 x + 13 \equiv x^2 - 14 x + 13 \equiv (x - 1) (x - 13) \equiv 0 \pmod{19} }[/math]

□