CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego: Różnice pomiędzy wersjami
Linia 107: | Linia 107: | ||
<span style="font-size: 110%; font-weight: bold;">Uwaga J3</span><br/> | <span style="font-size: 110%; font-weight: bold;">Uwaga J3</span><br/> | ||
− | Chińskie twierdzenie o resztach<ref name="CRT1"/> (CRT<ref name="CRT2"/>) pozostaje prawdziwe w przypadku układu skończonej liczby kongruencji | + | Chińskie twierdzenie o resztach<ref name="CRT1"/> (CRT<ref name="CRT2"/>) pozostaje prawdziwe w 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} | ::<math>\begin{align} | ||
Linia 122: | Linia 122: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span style="font-size: 110%; font-weight: bold;">Zadanie J4</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>), ż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 sposób równoważny w 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 J2). Zakładając prawdziwość twierdzenia dla wszystkich liczb naturalnych należących do przedziału <math>[2, k]</math> otrzymujemy dla <math>k + 1</math> układ | ||
+ | |||
+ | ::<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 założenia indukcyjnego. Z twierdzenia J2 wynika, że układ ten można zapisać w sposób równoważny w 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 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/> | ||
+ | □ | ||
+ | {{\Spoiler}} | ||
+ | |||
+ | |||
+ | |||
+ | <span style="font-size: 110%; font-weight: bold;">Przykład J5</span><br/> | ||
Dysponujemy pewną ilością kulek. Grupując je po <math>5</math>, zostają nam <math>3</math>, a 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 | Dysponujemy pewną ilością kulek. Grupując je po <math>5</math>, zostają nam <math>3</math>, a 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 | ||
Linia 162: | Linia 193: | ||
== Wielomiany == | == Wielomiany == | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J6</span><br/> |
Niech <math>W_n (x)</math> będzie dowolnym wielomianem stopnia <math>n</math>. Wielomian <math>W_n (x)</math> można przedstawić w postaci | Niech <math>W_n (x)</math> będzie dowolnym wielomianem stopnia <math>n</math>. Wielomian <math>W_n (x)</math> można przedstawić w postaci | ||
Linia 202: | Linia 233: | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja | + | <span style="font-size: 110%; font-weight: bold;">Definicja J7</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>. | 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 | + | <span style="font-size: 110%; font-weight: bold;">Definicja J8</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. | 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 | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J9</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 | 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 | ||
Linia 242: | Linia 273: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J10</span><br/> |
Niech <math>W(x)</math> będzie wielomianem całkowitym. Rozważmy kongruencję | Niech <math>W(x)</math> będzie wielomianem całkowitym. Rozważmy kongruencję | ||
Linia 274: | Linia 305: | ||
::<math>x \equiv c \pmod{m n}</math> | ::<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 twierdzenia | + | Zauważmy, że liczba <math>c</math> określona modulo <math>m n</math> jest rozwiązaniem kongruencji <math>(1)</math>. Istotnie z twierdzenia J9 mamy |
::<math>\begin{align} | ::<math>\begin{align} | ||
Linia 304: | Linia 335: | ||
== Twierdzenie Lagrange'a == | == Twierdzenie Lagrange'a == | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J11</span><br/> |
Kongruencja | Kongruencja | ||
Linia 351: | Linia 382: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J12 (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 | 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 | ||
Linia 359: | Linia 390: | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | Indukcja matematyczna. Z | + | Indukcja matematyczna. Z J11 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> | ::<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 twierdzenia | + | 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 twierdzenia J6, możemy napisać |
::<math>W_n (x) - W_n (s) = (x - s) V_{n - 1} (x)</math> | ::<math>W_n (x) - W_n (s) = (x - s) V_{n - 1} (x)</math> | ||
Linia 397: | Linia 428: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J13</span><br/> |
Jeżeli kongruencja | Jeżeli kongruencja | ||
Linia 421: | Linia 452: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span style="font-size: 110%; font-weight: bold;">Przykład J14</span><br/> |
Z twierdzenia Lagrange'a wynika, że kongruencja | Z twierdzenia Lagrange'a wynika, że kongruencja | ||
Linia 432: | Linia 463: | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span style="font-size: 110%; font-weight: bold;">Przykład J15</span><br/> |
Zauważmy, że w 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 | Zauważmy, że w 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 | ||
Linia 457: | Linia 488: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J16 (John Wilson, 1770)</span><br/> |
Liczba całkowita <math>p \geqslant 2</math> jest liczbą pierwszą wtedy i tylko wtedy, gdy | Liczba całkowita <math>p \geqslant 2</math> jest liczbą pierwszą wtedy i tylko wtedy, gdy | ||
Linia 499: | Linia 530: | ||
:* 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> | :* 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 twierdzenia | + | 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 twierdzenia J13 wynika natychmiast, że liczba pierwsza <math>p</math> musi dzielić każdy współczynnik <math>a_k</math> wielomianu <math>U(x)</math> i w szczególności musi dzielić wyraz wolny, który jest równy <math>(p - 1) ! + 1</math>. Co należało pokazać.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 508: | Linia 539: | ||
== Twierdzenie Fermata == | == Twierdzenie Fermata == | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J17 (Pierre de Fermat, 1640)</span><br/> |
Niech <math>a \in \mathbb{Z}</math>. Jeżeli <math>p</math> jest liczbą pierwszą | Niech <math>a \in \mathbb{Z}</math>. Jeżeli <math>p</math> jest liczbą pierwszą | ||
Linia 549: | Linia 580: | ||
== Kryterium Eulera == | == Kryterium Eulera == | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja | + | <span style="font-size: 110%; font-weight: bold;">Definicja J18</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 | 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 | ||
Linia 564: | Linia 595: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J19</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 tyle samo liczb niekwadratowych modulo <math>p</math>. | 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 tyle samo liczb niekwadratowych modulo <math>p</math>. | ||
Linia 603: | Linia 634: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J20 (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 | Niech <math>p</math> będzie liczbą pierwszą nieparzystą i <math>p \nmid a</math>. Modulo <math>p</math> mamy | ||
Linia 625: | Linia 656: | ||
::{| border=1 style="border-collapse: collapse;" | ::{| border=1 style="border-collapse: collapse;" | ||
|-style=height:2.5em | |-style=height:2.5em | ||
− | | '''A''' || <math>| Q | = {\small\frac{p - 1}{2}}</math> || zobacz | + | | '''A''' || <math>| Q | = {\small\frac{p - 1}{2}}</math> || zobacz J19 |
|-style=height:2.5em | |-style=height:2.5em | ||
− | | '''B''' || <math>| S | \leqslant {\small\frac{p - 1}{2}}</math> || zobacz twierdzenie Lagrange'a | + | | '''B''' || <math>| S | \leqslant {\small\frac{p - 1}{2}}</math> || zobacz twierdzenie Lagrange'a J12 |
|-style=height:2.5em | |-style=height:2.5em | ||
| '''C''' || jeżeli <math>a \in Q</math>, to <math>a \in S \qquad </math> || wynika z ciągu implikacji:<br/> <math>a \in Q \qquad \Longrightarrow \qquad a \equiv k^2 \pmod{p}</math><br/> <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> <br/> <math>a^{(p - 1) / 2} \equiv 1 \pmod{p} \qquad \Longrightarrow \qquad a \in S</math> | | '''C''' || jeżeli <math>a \in Q</math>, to <math>a \in S \qquad </math> || wynika z ciągu implikacji:<br/> <math>a \in Q \qquad \Longrightarrow \qquad a \equiv k^2 \pmod{p}</math><br/> <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> <br/> <math>a^{(p - 1) / 2} \equiv 1 \pmod{p} \qquad \Longrightarrow \qquad a \in S</math> | ||
Linia 643: | Linia 674: | ||
::<math>| Q | = | S | = {\small\frac{p - 1}{2}}</math> | ::<math>| Q | = | S | = {\small\frac{p - 1}{2}}</math> | ||
− | Ponieważ <math>Q \subseteq S</math>, a zbiory <math>Q</math> i <math>S</math> są równoliczne, to zbiory te są równe (zobacz | + | Ponieważ <math>Q \subseteq S</math>, a zbiory <math>Q</math> i <math>S</math> są równoliczne, to zbiory te są równe (zobacz J21). Prostą konsekwencją równości zbiorów <math>Q</math> i <math>S</math> jest stwierdzenie |
::{| border=0 style="background: #EEEEEE;" | ::{| border=0 style="background: #EEEEEE;" | ||
Linia 682: | Linia 713: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span style="font-size: 110%; font-weight: bold;">Zadanie J21</span><br/> |
Niech <math>A</math> i <math>B</math> będą zbiorami skończonymi. Pokazać, że jeżeli <math>A \subseteq B \;\; \text{i} \;\; | A | = | B |</math>, to <math>\; A = B</math>. | Niech <math>A</math> i <math>B</math> będą zbiorami skończonymi. Pokazać, że jeżeli <math>A \subseteq B \;\; \text{i} \;\; | A | = | B |</math>, to <math>\; A = B</math>. | ||
Linia 719: | Linia 750: | ||
== Symbol Legendre'a == | == Symbol Legendre'a == | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja | + | <span style="font-size: 110%; font-weight: bold;">Definicja J22</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 | 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 | ||
Linia 731: | Linia 762: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J23</span><br/> |
Powyższa definicja pozwala nam zapisać kryterium Eulera w zwartej formie, która obejmuje również przypadek, gdy <math>p \, | \, a</math> | Powyższa definicja pozwala nam zapisać kryterium Eulera w zwartej formie, która obejmuje również przypadek, gdy <math>p \, | \, a</math> | ||
Linia 738: | Linia 769: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J24*</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 | 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 | ||
Linia 787: | Linia 818: | ||
== Symbol Jacobiego == | == Symbol Jacobiego == | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja | + | <span style="font-size: 110%; font-weight: bold;">Definicja J25</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 | 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 | ||
Linia 802: | Linia 833: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span style="font-size: 110%; font-weight: bold;">Zadanie J26</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 tylko wtedy, gdy jest liczbą kwadratową modulo <math>m</math> i modulo <math>n</math>. | 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 tylko wtedy, gdy jest liczbą kwadratową modulo <math>m</math> i modulo <math>n</math>. | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | {{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 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 uwadze | + | Niech <math>W(x) = x^2 - a</math>. Zauważmy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>m</math> wtedy i 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 uwadze J10.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 812: | Linia 843: | ||
− | <span style="font-size: 110%; font-weight: bold;">Definicja | + | <span style="font-size: 110%; font-weight: bold;">Definicja J27</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. | 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 | Niech <math>n = \prod_i p_i^{\alpha_i}</math> będzie rozkładem liczby <math>n</math> na czynniki pierwsze, wtedy | ||
Linia 820: | Linia 851: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J28</span><br/> |
Zauważmy, że w 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>. | Zauważmy, że w 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 | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J29*</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 | 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 | ||
Linia 867: | Linia 898: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J30</span><br/> |
− | Zauważmy, że poza zmienionym założeniem tabela z powyższego twierdzenia i tabela z twierdzenia | + | Zauważmy, że poza zmienionym założeniem tabela z powyższego twierdzenia i tabela z twierdzenia J24 różnią się jedynie punktem czwartym. Oczywiście jest to tylko podobieństwo formalne – symbol Legendre'a i symbol Jacobiego są różnymi funkcjami. |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J31</span><br/> |
Zauważmy, że w przypadku, gdy <math>m</math> jest liczbą nieparzystą | Zauważmy, że w przypadku, gdy <math>m</math> jest liczbą nieparzystą | ||
Linia 886: | Linia 917: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J32</span><br/> |
Wszystkie liczby kwadratowe i niekwadratowe modulo <math>m</math> można łatwo znaleźć, wykorzystując prosty program: | Wszystkie liczby kwadratowe i niekwadratowe modulo <math>m</math> można łatwo znaleźć, wykorzystując prosty program: | ||
Linia 907: | Linia 938: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span style="font-size: 110%; font-weight: bold;">Zadanie J33</span><br/> |
Pokazać, że | Pokazać, że | ||
Linia 963: | Linia 994: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span style="font-size: 110%; font-weight: bold;">Zadanie J34</span><br/> |
Pokazać, że | Pokazać, że | ||
Linia 995: | Linia 1026: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J35</span><br/> |
− | Wykorzystując podane w twierdzeniu | + | Wykorzystując podane w twierdzeniu J29 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>n</math> na czynniki pierwsze. |
<span style="font-size: 90%; color:black;">jacobi(a, n) = | <span style="font-size: 90%; color:black;">jacobi(a, n) = | ||
Linia 1020: | Linia 1051: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J36</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 symbol Jacobiego <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}</math> dostarcza jedynie ograniczonych informacji. | 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 symbol Jacobiego <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}</math> dostarcza jedynie ograniczonych informacji. | ||
Linia 1035: | Linia 1066: | ||
== Rozwiązywanie kongruencji <math>x^2 \equiv a \pmod{m}</math> == | == Rozwiązywanie kongruencji <math>x^2 \equiv a \pmod{m}</math> == | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J37</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 | 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 | ||
Linia 1104: | Linia 1135: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J38</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 \, | \, 2^n</math>. | 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 \, | \, 2^n</math>. | ||
Linia 1127: | Linia 1158: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J39</span><br/> |
Niech <math>n \geqslant 3</math> i <math>a</math> będzie liczbą nieparzystą. Kongruencja | Niech <math>n \geqslant 3</math> i <math>a</math> będzie liczbą nieparzystą. Kongruencja | ||
Linia 1189: | Linia 1220: | ||
− | <span style="font-size: 110%; font-weight: bold;">Wniosek | + | <span style="font-size: 110%; font-weight: bold;">Wniosek J40</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 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 zależności od tego, czy <math>n = 1</math>, czy <math>n = 2</math>, czy <math>n \geqslant 3</math>. | Jeżeli <math>a</math> jest liczbą nieparzystą, to kongruencja <math>x^2 \equiv a \pmod{2^n}</math> ma rozwiązanie wtedy i 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 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 | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J41</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 chińskiego twierdzenia o resztach (zobacz J2 i | + | Niech <math>m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math> i <math>\gcd (a, m) = 1</math>. Z chińskiego twierdzenia o resztach (zobacz J2 i J10) wynika, że kongruencja <math>x^2 \equiv a \pmod{m}</math> ma rozwiązanie wtedy i tylko wtedy, gdy ma rozwiązanie każda z kongruencji |
::<math>\begin{align} | ::<math>\begin{align} | ||
Linia 1203: | Linia 1234: | ||
\end{align}</math> | \end{align}</math> | ||
− | Z definicji | + | Z definicji J22, twierdzeń J37 i J39, uwagi J38 i wniosku J40 otrzymujemy |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J42</span><br/> |
Niech <math>m \in \mathbb{Z}_+</math> i <math>\gcd (a, m) = 1</math>. Kongruencja | Niech <math>m \in \mathbb{Z}_+</math> i <math>\gcd (a, m) = 1</math>. Kongruencja | ||
Linia 1225: | Linia 1256: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span style="font-size: 110%; font-weight: bold;">Zadanie J43</span><br/> |
Rozwiązać kongruencję, gdzie <math>p</math> jest liczbą pierwszą nieparzystą | Rozwiązać kongruencję, gdzie <math>p</math> jest liczbą pierwszą nieparzystą | ||
Linia 1261: | Linia 1292: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span style="font-size: 110%; font-weight: bold;">Zadanie J44</span><br/> |
Rozwiązać kongruencję | Rozwiązać kongruencję | ||
Linia 1301: | Linia 1332: | ||
== Najmniejsze liczby niekwadratowe modulo == | == Najmniejsze liczby niekwadratowe modulo == | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J45</span><br/> |
Najmniejsze liczby niekwadratowe modulo przedstawiamy Czytelnikowi jedynie jako pewną ciekawostkę. Jednocześnie jest to nietrudny temat, który pozwala lepiej poznać i zrozumieć liczby kwadratowe modulo, liczby niekwadratowe modulo, symbol Legendre'a i symbol Jacobiego. | Najmniejsze liczby niekwadratowe modulo przedstawiamy Czytelnikowi jedynie jako pewną ciekawostkę. Jednocześnie jest to nietrudny temat, który pozwala lepiej poznać i zrozumieć liczby kwadratowe modulo, liczby niekwadratowe modulo, symbol Legendre'a i symbol Jacobiego. | ||
Linia 1311: | Linia 1342: | ||
|} | |} | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span style="font-size: 110%; font-weight: bold;">Przykład J46</span><br/> |
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math> | W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math> | ||
Linia 1324: | Linia 1355: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J47</span><br/> |
Do wyszukiwania liczb <math>g = g (p)</math> Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP | Do wyszukiwania liczb <math>g = g (p)</math> Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP | ||
Linia 1338: | Linia 1369: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J48</span><br/> |
Niech <math>g \in \mathbb{Z}_+</math> i niech <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli <math>g</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>, to jest liczbą pierwszą. | Niech <math>g \in \mathbb{Z}_+</math> i niech <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli <math>g</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>, to jest liczbą pierwszą. | ||
Linia 1358: | Linia 1389: | ||
− | <span style="font-size: 110%; font-weight: bold;">Zadanie | + | <span style="font-size: 110%; font-weight: bold;">Zadanie J49</span><br/> |
Pokazać, że najmniejszą liczbą niekwadratową modulo <math>p</math> jest | Pokazać, że najmniejszą liczbą niekwadratową modulo <math>p</math> jest | ||
Linia 1366: | Linia 1397: | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | ||
− | Z właściwości symbolu Legendre'a (zobacz | + | Z właściwości symbolu Legendre'a (zobacz J24 p.7) wiemy, że |
::<math>\left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} \,\, = | ::<math>\left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} \,\, = | ||
Linia 1377: | Linia 1408: | ||
Wynika stąd natychmiast, dla liczb pierwszych <math>p</math> postaci <math>8 k \pm 3</math> (i tylko dla takich liczb) liczba <math>2</math> jest liczbą niekwadratową, czyli również najmniejszą liczbą niekwadratową modulo <math>p</math>. | Wynika stąd natychmiast, dla liczb pierwszych <math>p</math> postaci <math>8 k \pm 3</math> (i tylko dla takich liczb) liczba <math>2</math> jest liczbą niekwadratową, czyli również najmniejszą liczbą niekwadratową modulo <math>p</math>. | ||
− | Z zadania | + | Z zadania J34 wynika, że liczba <math>3</math> jest liczbą niekwadratową jedynie dla liczb pierwszych postaci <math>12 k \pm 5</math>. Zatem dla liczb pierwszych, które są jednocześnie postaci <math>p = 8 k \pm 1</math> i <math>p = 12 j \pm 5</math>, liczba <math>3</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>. Z czterech warunków |
::<math>p = 8 k + 1 \quad \text{i} \quad p = 12 j + 5</math> | ::<math>p = 8 k + 1 \quad \text{i} \quad p = 12 j + 5</math> | ||
Linia 1431: | Linia 1462: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J50</span><br/> |
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, a <math>g</math> będzie najmniejszą liczbą niekwadratową modulo <math>p</math>. Prawdziwe jest oszacowanie | Niech <math>p</math> będzie liczbą pierwszą nieparzystą, a <math>g</math> będzie najmniejszą liczbą niekwadratową modulo <math>p</math>. Prawdziwe jest oszacowanie | ||
Linia 1473: | Linia 1504: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J51*</span><br/> |
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, a <math>g</math> będzie najmniejszą liczbą niekwadratową modulo <math>p</math>. Dla <math>p \geqslant 5</math> prawdziwe jest oszacowanie<ref name="Norton1"/><ref name="Trevino1"/><ref name="Trevino2"/> | Niech <math>p</math> będzie liczbą pierwszą nieparzystą, a <math>g</math> będzie najmniejszą liczbą niekwadratową modulo <math>p</math>. Dla <math>p \geqslant 5</math> prawdziwe jest oszacowanie<ref name="Norton1"/><ref name="Trevino1"/><ref name="Trevino2"/> | ||
Linia 1480: | Linia 1511: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J52</span><br/> |
Liczby <math>g = g (p)</math> są zaskakująco małe. Średnia wartość <math>g = g (p)</math>, gdzie <math>p</math> są nieparzystymi liczbami pierwszymi, jest równa<ref name="Erdos1"/> | Liczby <math>g = g (p)</math> są zaskakująco małe. Średnia wartość <math>g = g (p)</math>, gdzie <math>p</math> są nieparzystymi liczbami pierwszymi, jest równa<ref name="Erdos1"/> | ||
Linia 1493: | Linia 1524: | ||
|} | |} | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J53</span><br/> |
Najmniejsze liczby niekwadratowe modulo <math>m</math> są naturalnym uogólnieniem najmniejszych liczb niekwadratowych modulo <math>p</math>. W jednym i drugim przypadku liczba <math>g</math> jest najmniejszą liczbą niekwadratową w zbiorze wszystkich liczb niekwadratowych dodatnich nie większych od <math>p</math> lub <math>m</math>. Dlatego będziemy je oznaczali również jako <math>g(m)</math>. | Najmniejsze liczby niekwadratowe modulo <math>m</math> są naturalnym uogólnieniem najmniejszych liczb niekwadratowych modulo <math>p</math>. W jednym i drugim przypadku liczba <math>g</math> jest najmniejszą liczbą niekwadratową w zbiorze wszystkich liczb niekwadratowych dodatnich nie większych od <math>p</math> lub <math>m</math>. Dlatego będziemy je oznaczali również jako <math>g(m)</math>. | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span style="font-size: 110%; font-weight: bold;">Przykład J54</span><br/> |
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math> i najmniejsze liczby niekwadratowe modulo <math>m</math>. | W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math> i najmniejsze liczby niekwadratowe modulo <math>m</math>. | ||
Linia 1514: | Linia 1545: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J55</span><br/> |
Do wyszukiwania liczb <math>g = g (m)</math> Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP | Do wyszukiwania liczb <math>g = g (m)</math> Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP | ||
Linia 1526: | Linia 1557: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J56</span><br/> |
Niech <math>m \in \mathbb{Z}_+</math> będzie liczbą nieparzystą. Jeżeli <math>g</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>, to <math>g</math> jest liczbą pierwszą. | Niech <math>m \in \mathbb{Z}_+</math> będzie liczbą nieparzystą. Jeżeli <math>g</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>, to <math>g</math> jest liczbą pierwszą. | ||
Linia 1546: | Linia 1577: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J57</span><br/> |
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli <math>a</math> jest liczbą niekwadratową modulo <math>p</math> i <math>p \, | \, m</math>, to <math>a</math> jest liczbą niekwadratową modulo <math>m</math>. | Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli <math>a</math> jest liczbą niekwadratową modulo <math>p</math> i <math>p \, | \, m</math>, to <math>a</math> jest liczbą niekwadratową modulo <math>m</math>. | ||
Linia 1568: | Linia 1599: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J58</span><br/> |
Jeżeli liczba <math>g = g (m)</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>, to istnieje taki dzielnik pierwszy <math>p</math> liczby <math>m</math>, że <math>g</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>. | Jeżeli liczba <math>g = g (m)</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>, to istnieje taki dzielnik pierwszy <math>p</math> liczby <math>m</math>, że <math>g</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>. | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | Przypuśćmy, że taki dzielnik pierwszy nie istnieje. Zatem mamy zbiór dzielników pierwszych liczby <math>m</math>: <math>\{ p_1, \ldots, p_s \}</math> i powiązany z dzielnikami pierwszymi <math>p_k</math> zbiór najmniejszych liczb niekwadratowych modulo <math>p_k</math>: <math>\{ g_1, \ldots, g_s \}</math>, z których każda jest liczbą niekwadratową modulo <math>m</math> (zobacz | + | Przypuśćmy, że taki dzielnik pierwszy nie istnieje. Zatem mamy zbiór dzielników pierwszych liczby <math>m</math>: <math>\{ p_1, \ldots, p_s \}</math> i powiązany z dzielnikami pierwszymi <math>p_k</math> zbiór najmniejszych liczb niekwadratowych modulo <math>p_k</math>: <math>\{ g_1, \ldots, g_s \}</math>, z których każda jest liczbą niekwadratową modulo <math>m</math> (zobacz J57). Wynika stąd, że liczba <math>g = g (m)</math> musi być mniejsza od każdej z liczb <math>g_k</math>. |
Z definicji liczba <math>g = g (m)</math> jest liczbą niekwadratową modulo <math>m</math>, co oznacza, że kongruencja | Z definicji liczba <math>g = g (m)</math> jest liczbą niekwadratową modulo <math>m</math>, co oznacza, że kongruencja | ||
Linia 1582: | Linia 1613: | ||
::<math>x^2 \equiv g \pmod{p^{\alpha_k}_k}</math> | ::<math>x^2 \equiv g \pmod{p^{\alpha_k}_k}</math> | ||
− | musi nie mieć rozwiązania (zobacz | + | musi nie mieć rozwiązania (zobacz J10). Z twierdzenia J37 wiemy, że wtedy kongruencja |
::<math>x^2 \equiv g \pmod{p_k}</math> | ::<math>x^2 \equiv g \pmod{p_k}</math> | ||
Linia 1592: | Linia 1623: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J59</span><br/> |
Jeżeli <math>m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>, to | Jeżeli <math>m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>, to | ||
Linia 1600: | Linia 1631: | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | Twierdzenie jest prostym wnioskiem z twierdzenia | + | Twierdzenie jest prostym wnioskiem z twierdzenia J58.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 1606: | Linia 1637: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J60</span><br/> |
Niech <math>m \in \mathbb{Z}_+</math> będzie liczbą nieparzystą, a <math>g(m)</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>. Prawdziwe są oszacowania | Niech <math>m \in \mathbb{Z}_+</math> będzie liczbą nieparzystą, a <math>g(m)</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>. Prawdziwe są oszacowania | ||
Linia 1614: | Linia 1645: | ||
{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | ||
− | Niech <math>p</math> będzie dzielnikiem pierwszym liczby <math>m</math> takim, że <math>g(m) = g (p)</math> (z twierdzenia | + | Niech <math>p</math> będzie dzielnikiem pierwszym liczby <math>m</math> takim, że <math>g(m) = g (p)</math> (z twierdzenia J58 wiemy, że taki dzielnik istnieje). Jeżeli prawdziwe jest oszacowanie <math>g(p) < F (p)</math>, gdzie <math>F(x)</math> jest funkcją rosnącą, to |
::<math>g(m) = g (p) < F (p) \leqslant F (m)</math> | ::<math>g(m) = g (p) < F (p) \leqslant F (m)</math> | ||
− | Podane w twierdzeniu oszacowania wynikają natychmiast z twierdzeń | + | Podane w twierdzeniu oszacowania wynikają natychmiast z twierdzeń J50 i J51.<br/> |
□ | □ | ||
{{\Spoiler}} | {{\Spoiler}} | ||
Linia 1630: | Linia 1661: | ||
|} | |} | ||
− | <span style="font-size: 110%; font-weight: bold;">Przykład | + | <span style="font-size: 110%; font-weight: bold;">Przykład J61</span><br/> |
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math>, najmniejsze liczby niekwadratowe modulo <math>m</math> i najmniejsze dodatnie liczby niekwadratowe <math>a</math> takie, że <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math>. | W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math>, najmniejsze liczby niekwadratowe modulo <math>m</math> i najmniejsze dodatnie liczby niekwadratowe <math>a</math> takie, że <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math>. | ||
Linia 1649: | Linia 1680: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J62</span><br/> |
Do wyszukiwania liczb <math>c = c (m)</math> Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP | Do wyszukiwania liczb <math>c = c (m)</math> Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP | ||
Linia 1661: | Linia 1692: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J63</span><br/> |
Najmniejsze dodatnie liczby niekwadratowe <math>a</math> takie, że <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math> oznaczyliśmy jako <math>c(m)</math>. Zauważmy, że są to liczby inne od <math>g(p)</math> i <math>g(m)</math>. Wystarczy zwrócić uwagę na występujące w tabeli liczby <math>g(p)</math>, <math>g(m)</math> i <math>c(m)</math> dla <math>m = 15, 33, 39</math>. Różnice wynikają z innej definicji liczb <math>c(m)</math> – jeżeli liczba <math>a</math> jest liczbą niekwadratową modulo <math>m</math>, to symbol Jacobiego <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}</math> nie musi być równy <math>- 1</math>. I tak czasami bywa, co bardzo dobrze pokazuje powyższa tabela. | Najmniejsze dodatnie liczby niekwadratowe <math>a</math> takie, że <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math> oznaczyliśmy jako <math>c(m)</math>. Zauważmy, że są to liczby inne od <math>g(p)</math> i <math>g(m)</math>. Wystarczy zwrócić uwagę na występujące w tabeli liczby <math>g(p)</math>, <math>g(m)</math> i <math>c(m)</math> dla <math>m = 15, 33, 39</math>. Różnice wynikają z innej definicji liczb <math>c(m)</math> – jeżeli liczba <math>a</math> jest liczbą niekwadratową modulo <math>m</math>, to symbol Jacobiego <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}</math> nie musi być równy <math>- 1</math>. I tak czasami bywa, co bardzo dobrze pokazuje powyższa tabela. | ||
Ponieważ <math>c(m)</math> nie zawsze będzie najmniejszą liczbą kwadratową modulo <math>m</math>, to mamy natychmiast oszacowanie: <math>c(m) \geqslant g (m)</math> (poza przypadkami, gdy <math>m = n^2</math>). | Ponieważ <math>c(m)</math> nie zawsze będzie najmniejszą liczbą kwadratową modulo <math>m</math>, to mamy natychmiast oszacowanie: <math>c(m) \geqslant g (m)</math> (poza przypadkami, gdy <math>m = n^2</math>). | ||
− | Dla <math>c(m)</math> nie są prawdziwe oszacowania podane w twierdzeniu | + | Dla <math>c(m)</math> nie są prawdziwe oszacowania podane w twierdzeniu J50. Łatwo zauważamy, że |
::<math>c = c (15) = 7 > \sqrt{15} + {\small\frac{1}{2}} \approx 4.37</math> | ::<math>c = c (15) = 7 > \sqrt{15} + {\small\frac{1}{2}} \approx 4.37</math> | ||
Linia 1680: | Linia 1711: | ||
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie | + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J64</span><br/> |
Niech <math>c, m \in \mathbb{Z}_+</math> i niech <math>m \geqslant 3</math> będzie liczbą nieparzystą, a <math>c</math> będzie najmniejszą liczbą taką, że <math>\left( {\small\frac{c}{m}} \right)_{\small{\!\! J}} = - 1</math>. Liczba <math>c</math> musi być liczbą pierwszą. | Niech <math>c, m \in \mathbb{Z}_+</math> i niech <math>m \geqslant 3</math> będzie liczbą nieparzystą, a <math>c</math> będzie najmniejszą liczbą taką, że <math>\left( {\small\frac{c}{m}} \right)_{\small{\!\! J}} = - 1</math>. Liczba <math>c</math> musi być liczbą pierwszą. | ||
Linia 1694: | Linia 1725: | ||
− | <span style="font-size: 110%; font-weight: bold;">Uwaga | + | <span style="font-size: 110%; font-weight: bold;">Uwaga J65</span><br/> |
Liczby <math>c = c (m)</math> są zaskakująco małe. Średnia wartość <math>c = c (m)</math>, gdzie <math>m</math> są liczbami nieparzystymi (przyjmujemy <math>c(m) = 0</math>, gdy <math>m</math> jest liczbą kwadratową) wynosi<ref name="BaillieWagstaff1"/> | Liczby <math>c = c (m)</math> są zaskakująco małe. Średnia wartość <math>c = c (m)</math>, gdzie <math>m</math> są liczbami nieparzystymi (przyjmujemy <math>c(m) = 0</math>, gdy <math>m</math> jest liczbą kwadratową) wynosi<ref name="BaillieWagstaff1"/> | ||
Wersja z 17:55, 26 mar 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]
[math]\displaystyle{ \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{ \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 \, | \, (u - a) }[/math], czyli [math]\displaystyle{ n \, | \, k m }[/math]. Ponieważ [math]\displaystyle{ \gcd (m, n) = 1 }[/math], zatem [math]\displaystyle{ n \, | \, k }[/math] (zobacz C72) 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 (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} \qquad \qquad \qquad (1) }[/math]
jest równoważna układowi kongruencji
- [math]\displaystyle{ \begin{align} u &\equiv a \pmod{m} \\ u &\equiv b \pmod{n} \end{align} \qquad \qquad \qquad \; (2) }[/math]
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.69) 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]. Dla tak wybranej wartości liczby [math]\displaystyle{ c }[/math] dostajemy kolejno
- [math]\displaystyle{ u \equiv c \pmod{m n} }[/math]
Z twierdzenia J1
- [math]\displaystyle{ \begin{align} u &\equiv c \pmod{m} \\ u &\equiv c \pmod{n} \end{align} }[/math]
Zatem
- [math]\displaystyle{ \begin{align} u &\equiv a n y + b m x \pmod{m} \\ u &\equiv a n y + b m x \pmod{n} \end{align} }[/math]
Ponieważ [math]\displaystyle{ \; b m x \equiv 0 \pmod{m} \; }[/math] oraz [math]\displaystyle{ \; a n y \equiv 0 \pmod{n} }[/math], to
- [math]\displaystyle{ \begin{align} u &\equiv a n y \pmod{m} \\ u &\equiv b m x \pmod{n} \end{align} }[/math]
Ale [math]\displaystyle{ m x + n y = 1 }[/math], zatem
- [math]\displaystyle{ \begin{align} u &\equiv a (1 - m x) \pmod{m} \\ u &\equiv b (1 - n y) \pmod{n} \end{align} }[/math]
Ponieważ [math]\displaystyle{ \; 1 - m x \equiv 1 \pmod{m} \; }[/math] oraz [math]\displaystyle{ \; 1 - n y \equiv 1 \pmod{n} }[/math], to
- [math]\displaystyle{ \begin{align} u &\equiv a \pmod{m} \\ u &\equiv b \pmod{n} \end{align} }[/math]
Zauważmy, że kolejne przejścia były równoważne, zatem udowodniliśmy równoważność kongruencji [math]\displaystyle{ (1) }[/math] i układu kongruencji [math]\displaystyle{ (2) }[/math].
Przypuśćmy, że istnieją dwie takie liczby [math]\displaystyle{ c }[/math] i [math]\displaystyle{ d }[/math], że przy dzieleniu przez [math]\displaystyle{ m }[/math] dają resztę [math]\displaystyle{ a }[/math], zaś przy dzieleniu przez [math]\displaystyle{ n }[/math] dają resztę [math]\displaystyle{ b }[/math]. Zatem [math]\displaystyle{ m \, | \, (d - c) }[/math] i [math]\displaystyle{ n \, | \, (d - c) }[/math]. Ponieważ liczby [math]\displaystyle{ m }[/math] i [math]\displaystyle{ n }[/math] są względnie pierwsze, to [math]\displaystyle{ m n \, | \, (d - c) }[/math] (zobacz C73), 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].
□
Uwaga J3
Chińskie twierdzenie o resztach[1] (CRT[2]) 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 J4
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]), ż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]
Indukcja matematyczna. Twierdzenie jest prawdziwe dla liczby [math]\displaystyle{ k = 2 }[/math] (zobacz J2). Zakładając prawdziwość twierdzenia dla wszystkich liczb naturalnych należących do przedziału [math]\displaystyle{ [2, k] }[/math] otrzymujemy dla [math]\displaystyle{ k + 1 }[/math] układ
- [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 J2 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 J5
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 J6
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.
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 J7
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 J8
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 J9
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]
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 \, | \, (x - y) }[/math], zatem dla [math]\displaystyle{ k \geqslant 1 }[/math] mamy [math]\displaystyle{ m \, | \, (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 J10
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 J9 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 J11
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].
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 C74. 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 C71 - 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 \, | \, a_1 (x_1 - x_2) }[/math]
Ponieważ [math]\displaystyle{ p \nmid a_1 }[/math], to z lematu Euklidesa (C72) otrzymujemy natychmiast [math]\displaystyle{ p \, | \, (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 J12 (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ń.
Indukcja matematyczna. Z J11 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 J6, 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 C72)
- [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 J13
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].
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 J14
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 J15
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 J16 (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]
[math]\displaystyle{ \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 \, | \, 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{ \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 J13 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 Fermata
Twierdzenie J17 (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]
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]
- [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|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|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 C72) wynika natychmiast, że [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ a^{p - 1} - 1 }[/math].
□
Kryterium Eulera
Definicja J18
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 \, | \, (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 J19
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].
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 J20 (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]
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 J19 B [math]\displaystyle{ | S | \leqslant {\small\frac{p - 1}{2}} }[/math] zobacz twierdzenie Lagrange'a J12 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 J21). 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[3], ż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 J21
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].
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[4]
- [math]\displaystyle{ | A \cup C | = | A | + | C | - | A \cap C | }[/math]
- [math]\displaystyle{ | A \cup C | = | A | + | C | - | A \cap C | }[/math]
□
Symbol Legendre'a
Definicja J22
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą i [math]\displaystyle{ a \in \mathbb{Z} }[/math]. Symbolem Legendre'a[5] 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 \, | \, a \end{cases} }[/math]
Uwaga J23
Powyższa definicja pozwala nam zapisać kryterium Eulera w zwartej formie, która obejmuje również przypadek, gdy [math]\displaystyle{ p \, | \, a }[/math]
- [math]\displaystyle{ a^{(p - 1) / 2} \equiv \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \pmod{p} }[/math]
Twierdzenie J24*
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 J25
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 \, | \, (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.
Zadanie J26
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].
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 J10.
□
Definicja J27
Symbol Jacobiego[6] [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 J28
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 J29*
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 J30
Zauważmy, że poza zmienionym założeniem tabela z powyższego twierdzenia i tabela z twierdzenia J24 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 J31
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 J32
Wszystkie liczby kwadratowe i niekwadratowe modulo [math]\displaystyle{ m }[/math] można łatwo znaleźć, wykorzystując prosty program:
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 J33
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]
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 J34
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{- 4}{m}} \right)_{\small{\!\! J}} = \begin{cases} \;\;\: 1 & \text{gdy } m = 4 k + 1 \\ - 1 & \text{gdy } m = 4 k + 3 \end{cases} }[/math]
- [math]\displaystyle{ \left( {\small\frac{3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{\tfrac{m - 1}{2} \cdot \tfrac{3 - 1}{2}} = \left( {\small\frac{12 k + 1}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{\tfrac{12 k}{2}} = \left( {\small\frac{1}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{6 k} = 1 }[/math]
- [math]\displaystyle{ \left( {\small\frac{3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{\tfrac{m - 1}{2} \cdot \tfrac{3 - 1}{2}} = \left( {\small\frac{12 k + 5}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{\tfrac{12 k + 4}{2}} = \left( {\small\frac{5}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{(6 k + 2)} = \left( {\small\frac{2}{3}} \right)_{\small{\!\! J}} = - 1 }[/math]
- [math]\displaystyle{ \left( {\small\frac{3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{\tfrac{m - 1}{2} \cdot \tfrac{3 - 1}{2}} = \left( {\small\frac{12 k + 7}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{\tfrac{12 k + 6}{2}} = \left( {\small\frac{1}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{(6 k + 3)} = - 1 }[/math]
- [math]\displaystyle{ \left( {\small\frac{3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{\tfrac{m - 1}{2} \cdot \tfrac{3 - 1}{2}} = \left( {\small\frac{12 k + 11}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{\tfrac{12 k + 10}{2}} = \left( {\small\frac{2}{3}} \right)_{\small{\!\! J}} \cdot (- 1)^{(6 k + 5)} = (- 1) \cdot (- 1) = 1 }[/math]
□
Uwaga J35
Wykorzystując podane w twierdzeniu J29 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 J36
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 \, | \, 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 \, | \, m) }[/math] jest symbolem Legendre'a
- jeżeli wiemy, że [math]\displaystyle{ m }[/math] jest liczbą złożoną, to symbol [math]\displaystyle{ (a \, | \, 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 \, | \, m) }[/math] jest symbolem Jacobiego
Rozwiązywanie kongruencji [math]\displaystyle{ x^2 \equiv a \pmod{m} }[/math]
Twierdzenie J37
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.
[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 \, | \, (r^2 - a) }[/math], to tym bardziej [math]\displaystyle{ p \, | \, (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 C74). 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} \, | \, 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 J38
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 \, | \, 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 J39
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.
[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 \, | \, (r^2 - a) }[/math], gdzie [math]\displaystyle{ n \geqslant 3 }[/math], to tym bardziej [math]\displaystyle{ 2^3 \, | \, (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 J40
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 J41
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 J2 i J10) 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 J22, twierdzeń J37 i J39, uwagi J38 i wniosku J40 otrzymujemy
Twierdzenie J42
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 \, | \, m }[/math], to [math]\displaystyle{ 8 \, | \, ( a - 1 ) }[/math] ● jeżeli [math]\displaystyle{ 8 \nmid m }[/math], ale [math]\displaystyle{ 4 \, | \, m }[/math], to [math]\displaystyle{ 4 \, | \, ( a - 1 ) }[/math]
Zadanie J43
Rozwiązać kongruencję, gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą
- [math]\displaystyle{ x^2 + rx + s \equiv 0 \pmod{p} }[/math]
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 J44
Rozwiązać kongruencję
- [math]\displaystyle{ 5 x^2 + 6 x + 8 \equiv 0 \pmod{19} }[/math]
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 + 5 x + 13 \equiv 0 \pmod{19} }[/math]
- [math]\displaystyle{ 4 x^2 + 4 \cdot 5 x + 4 \cdot 13 \equiv 0 \pmod{19} }[/math]
- [math]\displaystyle{ (2 x + 5)^2 - 25 + 52 \equiv 0 \pmod{19} }[/math]
- [math]\displaystyle{ (2 x + 5)^2 - 6 + 14 \equiv 0 \pmod{19} }[/math]
- [math]\displaystyle{ (2 x + 5)^2 \equiv - 8 \pmod{19} }[/math]
- [math]\displaystyle{ (2 x + 5)^2 \equiv 7^2 \pmod{19} }[/math]
- [math]\displaystyle{ 2 x + 5 \equiv \pm 7 \pmod{19} }[/math]
- [math]\displaystyle{ 2 x \equiv - 5 \pm 7 \pmod{19} }[/math]
Mnożąc obie strony kongruencji przez [math]\displaystyle{ 10 }[/math], otrzymujemy: [math]\displaystyle{ x \equiv 13 \pmod{19} }[/math] lub [math]\displaystyle{ x \equiv 1 \pmod{19} }[/math].
Nieco spostrzegawczości pozwala znaleźć rozwiązanie kongruencji natychmiast. W naszym przypadku wystarczyło zauważyć, że
- [math]\displaystyle{ x^2 + 5 x + 13 \equiv x^2 - 14 x + 13 \equiv (x - 1) (x - 13) \pmod{19} }[/math]
- [math]\displaystyle{ x^2 + 5 x + 13 \equiv x^2 - 14 x + 13 \equiv (x - 1) (x - 13) \pmod{19} }[/math]
□
Najmniejsze liczby niekwadratowe modulo
Uwaga J45
Najmniejsze liczby niekwadratowe modulo przedstawiamy Czytelnikowi jedynie jako pewną ciekawostkę. Jednocześnie jest to nietrudny temat, który pozwala lepiej poznać i zrozumieć liczby kwadratowe modulo, liczby niekwadratowe modulo, symbol Legendre'a i symbol Jacobiego.
A. Najmniejsze liczby niekwadratowe modulo [math]\displaystyle{ p }[/math] |
Przykład J46
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo [math]\displaystyle{ p }[/math]
[math]\displaystyle{ \boldsymbol{m} }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 7 }[/math] [math]\displaystyle{ 9 }[/math] [math]\displaystyle{ 11 }[/math] [math]\displaystyle{ 13 }[/math] [math]\displaystyle{ 15 }[/math] [math]\displaystyle{ 17 }[/math] [math]\displaystyle{ 19 }[/math] [math]\displaystyle{ 21 }[/math] [math]\displaystyle{ 23 }[/math] [math]\displaystyle{ 25 }[/math] [math]\displaystyle{ 27 }[/math] [math]\displaystyle{ 29 }[/math] [math]\displaystyle{ 31 }[/math] [math]\displaystyle{ 33 }[/math] [math]\displaystyle{ 35 }[/math] [math]\displaystyle{ 37 }[/math] [math]\displaystyle{ 39 }[/math] [math]\displaystyle{ 41 }[/math] [math]\displaystyle{ 43 }[/math] [math]\displaystyle{ 45 }[/math] [math]\displaystyle{ 47 }[/math] [math]\displaystyle{ 49 }[/math] [math]\displaystyle{ 51 }[/math] [math]\displaystyle{ \boldsymbol{g( p )} }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ - }[/math]
Uwaga J47
Do wyszukiwania liczb [math]\displaystyle{ g = g (p) }[/math] Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP
A(p) =
{
if( p == 2, return(0) );
if( !isprime(p), return(0) );
forprime(q = 2, p, if( jacobi(q, p) == -1, return(q) ));
}
Zauważmy, że choć wyliczamy symbol Jacobiego, to jest to w rzeczywistości symbol Legendre'a, bo wiemy, że liczba [math]\displaystyle{ p }[/math] jest liczbą pierwszą (w przypadku, gdy [math]\displaystyle{ p }[/math] jest liczbą złożoną, funkcja zwraca zero).
Twierdzenie J48
Niech [math]\displaystyle{ g \in \mathbb{Z}_+ }[/math] i niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Jeżeli [math]\displaystyle{ g }[/math] jest najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], to jest liczbą pierwszą.
Przypuśćmy, że [math]\displaystyle{ g = a b }[/math] jest liczbą złożoną, gdzie [math]\displaystyle{ 1 \lt a, b \lt g }[/math]. Z założenia [math]\displaystyle{ g }[/math] jest najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], zatem liczby [math]\displaystyle{ a, b }[/math] są liczbami kwadratowymi modulo [math]\displaystyle{ p }[/math]. Z definicji liczb kwadratowych muszą istnieć takie liczby [math]\displaystyle{ r, s }[/math], że
- [math]\displaystyle{ r^2 \equiv a \pmod{p} }[/math]
- [math]\displaystyle{ s^2 \equiv b \pmod{p} }[/math]
Skąd wynika, że
- [math]\displaystyle{ g = a b \equiv (r s)^2 \pmod{p} }[/math]
Wbrew założeniu, że [math]\displaystyle{ g }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math].
□
Zadanie J49
Pokazać, że najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ p }[/math] jest
- liczba [math]\displaystyle{ 2 }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ p = 8 k \pm 3 }[/math]
- liczba [math]\displaystyle{ 3 }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ p = 24 k \pm 7 }[/math]
- liczba [math]\displaystyle{ \geqslant 5 }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ p = 24 k \pm 1 }[/math]
Z właściwości symbolu Legendre'a (zobacz J24 p.7) wiemy, że
- [math]\displaystyle{ \left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} \,\, = \,\, \begin{cases} \;\;\: 1 & \text{gdy } p \equiv 1, 7 \pmod{8} \\ - 1 & \text{gdy } p \equiv 3, 5 \pmod{8} \end{cases} }[/math]
Wynika stąd natychmiast, dla liczb pierwszych [math]\displaystyle{ p }[/math] postaci [math]\displaystyle{ 8 k \pm 3 }[/math] (i tylko dla takich liczb) liczba [math]\displaystyle{ 2 }[/math] jest liczbą niekwadratową, czyli również najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ p }[/math].
Z zadania J34 wynika, że liczba [math]\displaystyle{ 3 }[/math] jest liczbą niekwadratową jedynie dla liczb pierwszych postaci [math]\displaystyle{ 12 k \pm 5 }[/math]. Zatem dla liczb pierwszych, które są jednocześnie postaci [math]\displaystyle{ p = 8 k \pm 1 }[/math] i [math]\displaystyle{ p = 12 j \pm 5 }[/math], liczba [math]\displaystyle{ 3 }[/math] jest najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ p }[/math]. Z czterech warunków
- [math]\displaystyle{ p = 8 k + 1 \quad \text{i} \quad p = 12 j + 5 }[/math]
- [math]\displaystyle{ p = 8 k + 1 \quad \text{i} \quad p = 12 j + 7 }[/math]
- [math]\displaystyle{ p = 8 k + 7 \quad \text{i} \quad p = 12 j + 5 }[/math]
- [math]\displaystyle{ p = 8 k + 7 \quad \text{i} \quad p = 12 j + 7 }[/math]
Drugi i trzeci nie są możliwe, bo modulo [math]\displaystyle{ 4 }[/math] otrzymujemy
- [math]\displaystyle{ p \equiv 1 \pmod{4} \quad \text{i} \quad p \equiv 3 \pmod{4} }[/math]
- [math]\displaystyle{ p \equiv 3 \pmod{4} \quad \text{i} \quad p \equiv 1 \pmod{4} }[/math]
a z pierwszego i czwartego mamy
- [math]\displaystyle{ 3 p = 24 k + 3 \quad \text{i} \quad 2 p = 24 j + 10 \qquad \;\: \Longrightarrow \qquad p = 24 (k - j) - 7 \qquad \Longrightarrow \qquad p \equiv - 7 \pmod{24} }[/math]
- [math]\displaystyle{ 3 p = 24 k + 21 \quad \text{i} \quad 2 p = 24 j + 14 \qquad \Longrightarrow \qquad p = 24 (k - j) + 7 \qquad \Longrightarrow \qquad p \equiv 7 \pmod{24} }[/math]
Zauważmy, że problem mogliśmy zapisać w postaci układu kongruencji
- [math]\displaystyle{ p \equiv \pm 1 \pmod{8} }[/math]
- [math]\displaystyle{ p \equiv \pm 5 \pmod{12} }[/math]
Gdyby moduły tych kongruencji były względnie pierwsze, to każdemu wyborowi znaków odpowiadałaby pewna kongruencja równoważna (zobacz J2). Widzimy, że w przypadku, gdy moduły nie są względnie pierwsze, kongruencja równoważna może istnieć, ale nie musi. Rozwiązując taki problem, wygodnie jest skorzystać z programu PARI/GP. Wystarczy wpisać
chinese(Mod(1, 8), Mod(5, 12)) = Mod(17, 24) chinese(Mod(1, 8), Mod(-5, 12)) - błąd chinese(Mod(-1, 8), Mod(5, 12)) - błąd chinese(Mod(-1, 8), Mod(-5, 12)) = Mod(7, 24)
Ostatni punkt zadania rozwiążemy tą metodą. Liczba większa lub równa [math]\displaystyle{ 5 }[/math] jest najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ p }[/math] wtedy i tylko wtedy, gdy liczby [math]\displaystyle{ 2 }[/math] i [math]\displaystyle{ 3 }[/math] są liczbami kwadratowymi modulo [math]\displaystyle{ p }[/math], co oznacza, że liczba pierwsza [math]\displaystyle{ p }[/math] spełnia kongruencje
- [math]\displaystyle{ p \equiv \pm 1 \pmod{8} }[/math]
- [math]\displaystyle{ p \equiv \pm 1 \pmod{12} }[/math]
Postępując jak wyżej, otrzymujemy
chinese(Mod(1, 8), Mod(1, 12)) = Mod(1, 24) chinese(Mod(1, 8), Mod(-1, 12)) - błąd chinese(Mod(-1, 8), Mod(1, 12)) - błąd chinese(Mod(-1, 8), Mod(-1, 12)) = Mod(23, 24)
Co należało pokazać.
□
Twierdzenie J50
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą, a [math]\displaystyle{ g }[/math] będzie najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ p }[/math]. Prawdziwe jest oszacowanie
- [math]\displaystyle{ g (p) \lt \sqrt{p} + {\small\frac{1}{2}} }[/math]
Ponieważ [math]\displaystyle{ g \nmid p }[/math], to z oszacowania [math]\displaystyle{ x - 1 \lt \lfloor x \rfloor \leqslant x }[/math] wynika, że
- [math]\displaystyle{ {\small\frac{p}{g}} - 1 \lt \left\lfloor {\small\frac{p}{g}} \right\rfloor \lt {\small\frac{p}{g}} }[/math]
- [math]\displaystyle{ p \lt g \left\lfloor {\small\frac{p}{g}} \right\rfloor + g \lt p + g }[/math]
Niech [math]\displaystyle{ u = \left\lfloor {\small\frac{p}{g}} \right\rfloor + 1 }[/math], mamy
- [math]\displaystyle{ 0 \lt g u - p \lt g }[/math]
Liczba [math]\displaystyle{ g u - p }[/math] musi być liczbą kwadratową modulo [math]\displaystyle{ p }[/math], zatem
- [math]\displaystyle{ 1 = \left( {\small\frac{g u - p}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{g}{p}} \right)_{\small{\!\! L}} \cdot \left( {\small\frac{u}{p}} \right)_{\small{\!\! L}} = - \left( {\small\frac{u}{p}} \right)_{\small{\!\! L}} }[/math]
Ale z założenia [math]\displaystyle{ g }[/math] jest najmniejszą liczbą taką, że [math]\displaystyle{ \left( {\small\frac{g}{p}} \right)_{\small{\!\! L}} = - 1 }[/math]. Wynika stąd, że musi być [math]\displaystyle{ g \leqslant u }[/math] i łatwo znajdujemy, że
- [math]\displaystyle{ g \leqslant \left\lfloor {\small\frac{p}{g}} \right\rfloor + 1 \lt {\small\frac{p}{g}} + 1 }[/math]
- [math]\displaystyle{ g^2 \lt p + g }[/math]
Ponieważ wypisane liczby są liczbami całkowitymi, to ostatnią nierówność możemy zapisać w postaci
- [math]\displaystyle{ g^2 \leqslant p + g - 1 }[/math]
Skąd otrzymujemy
- [math]\displaystyle{ \left( g - {\small\frac{1}{2}} \right)^2 \leqslant p - {\small\frac{3}{4}} }[/math]
- [math]\displaystyle{ g \leqslant {\small\frac{1}{2}} + \sqrt{p - {\small\frac{3}{4}}} \lt {\small\frac{1}{2}} + \sqrt{p} }[/math]
Co należało pokazać.
□
Twierdzenie J51*
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą, a [math]\displaystyle{ g }[/math] będzie najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ p }[/math]. Dla [math]\displaystyle{ p \geqslant 5 }[/math] prawdziwe jest oszacowanie[7][8][9]
- [math]\displaystyle{ g (p) \leqslant 1.1 \cdot p^{1 / 4} \log p }[/math]
Uwaga J52
Liczby [math]\displaystyle{ g = g (p) }[/math] są zaskakująco małe. Średnia wartość [math]\displaystyle{ g = g (p) }[/math], gdzie [math]\displaystyle{ p }[/math] są nieparzystymi liczbami pierwszymi, jest równa[10]
- [math]\displaystyle{ \lim_{x \to \infty} {\small\frac{1}{\pi (x)}} \sum_{p \leqslant x} g (p) = \sum_{k = 1}^{\infty} {\small\frac{p_k}{2^k}} = 3.674643966 \ldots }[/math]
B. Najmniejsze liczby niekwadratowe modulo [math]\displaystyle{ m }[/math], gdzie [math]\displaystyle{ m }[/math] jest liczbą nieparzystą |
Uwaga J53
Najmniejsze liczby niekwadratowe modulo [math]\displaystyle{ m }[/math] są naturalnym uogólnieniem najmniejszych liczb niekwadratowych modulo [math]\displaystyle{ p }[/math]. W jednym i drugim przypadku liczba [math]\displaystyle{ g }[/math] jest najmniejszą liczbą niekwadratową w zbiorze wszystkich liczb niekwadratowych dodatnich nie większych od [math]\displaystyle{ p }[/math] lub [math]\displaystyle{ m }[/math]. Dlatego będziemy je oznaczali również jako [math]\displaystyle{ g(m) }[/math].
Przykład J54
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo [math]\displaystyle{ p }[/math] i najmniejsze liczby niekwadratowe modulo [math]\displaystyle{ m }[/math].
[math]\displaystyle{ \boldsymbol{m} }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 7 }[/math] [math]\displaystyle{ 9 }[/math] [math]\displaystyle{ 11 }[/math] [math]\displaystyle{ 13 }[/math] [math]\displaystyle{ 15 }[/math] [math]\displaystyle{ 17 }[/math] [math]\displaystyle{ 19 }[/math] [math]\displaystyle{ 21 }[/math] [math]\displaystyle{ 23 }[/math] [math]\displaystyle{ 25 }[/math] [math]\displaystyle{ 27 }[/math] [math]\displaystyle{ 29 }[/math] [math]\displaystyle{ 31 }[/math] [math]\displaystyle{ 33 }[/math] [math]\displaystyle{ 35 }[/math] [math]\displaystyle{ 37 }[/math] [math]\displaystyle{ 39 }[/math] [math]\displaystyle{ 41 }[/math] [math]\displaystyle{ 43 }[/math] [math]\displaystyle{ 45 }[/math] [math]\displaystyle{ 47 }[/math] [math]\displaystyle{ 49 }[/math] [math]\displaystyle{ 51 }[/math] [math]\displaystyle{ \boldsymbol{g( p )} }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ \boldsymbol{g( m )} }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math]
Uwaga J55
Do wyszukiwania liczb [math]\displaystyle{ g = g (m) }[/math] Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP
B(m) =
{
local(w);
if( m%2 == 0, return(0) );
forprime(p = 2, m, w = -1; for(k = 2, (m - 1)/2, if( k^2%m == p, w = 1; break() )); if( w == -1, return(p) ));
}
Twierdzenie J56
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math] będzie liczbą nieparzystą. Jeżeli [math]\displaystyle{ g }[/math] jest najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ m }[/math], to [math]\displaystyle{ g }[/math] jest liczbą pierwszą.
Przypuśćmy, że [math]\displaystyle{ g = a b }[/math] jest liczbą złożoną, gdzie [math]\displaystyle{ 1 \lt a, b \lt g }[/math]. Z założenia [math]\displaystyle{ g }[/math] jest najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ m }[/math], zatem liczby [math]\displaystyle{ a, b }[/math] są liczbami kwadratowymi modulo [math]\displaystyle{ m }[/math]. Z definicji liczb kwadratowych muszą istnieć takie liczby [math]\displaystyle{ r, s }[/math], że
- [math]\displaystyle{ r^2 \equiv a \pmod{m} }[/math]
- [math]\displaystyle{ s^2 \equiv b \pmod{m} }[/math]
Skąd wynika, że
- [math]\displaystyle{ g = a b \equiv (r s)^2 \pmod{m} }[/math]
Wbrew założeniu, że [math]\displaystyle{ g }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ m }[/math].
□
Twierdzenie J57
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Jeżeli [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math] i [math]\displaystyle{ p \, | \, m }[/math], to [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ m }[/math].
Wiemy, że liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ m }[/math] wtedy i tylko wtedy, gdy kongruencja
- [math]\displaystyle{ x^2 \equiv a \pmod{m} }[/math]
ma rozwiązanie. Przypuśćmy, że liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ m }[/math]. Zatem istnieje taka liczba [math]\displaystyle{ k \in \mathbb{Z} }[/math], że
- [math]\displaystyle{ k^2 \equiv a \pmod{m} }[/math]
Ponieważ z założenia [math]\displaystyle{ p \, | \, m }[/math], to prawdziwa jest też kongruencja
- [math]\displaystyle{ k^2 \equiv a \pmod{p} }[/math]
co przeczy założeniu, że liczba [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math].
□
Twierdzenie J58
Jeżeli liczba [math]\displaystyle{ g = g (m) }[/math] jest najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ m }[/math], to istnieje taki dzielnik pierwszy [math]\displaystyle{ p }[/math] liczby [math]\displaystyle{ m }[/math], że [math]\displaystyle{ g }[/math] jest najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ p }[/math].
Przypuśćmy, że taki dzielnik pierwszy nie istnieje. Zatem mamy zbiór dzielników pierwszych liczby [math]\displaystyle{ m }[/math]: [math]\displaystyle{ \{ p_1, \ldots, p_s \} }[/math] i powiązany z dzielnikami pierwszymi [math]\displaystyle{ p_k }[/math] zbiór najmniejszych liczb niekwadratowych modulo [math]\displaystyle{ p_k }[/math]: [math]\displaystyle{ \{ g_1, \ldots, g_s \} }[/math], z których każda jest liczbą niekwadratową modulo [math]\displaystyle{ m }[/math] (zobacz J57). Wynika stąd, że liczba [math]\displaystyle{ g = g (m) }[/math] musi być mniejsza od każdej z liczb [math]\displaystyle{ g_k }[/math].
Z definicji liczba [math]\displaystyle{ g = g (m) }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ m }[/math], co oznacza, że kongruencja
- [math]\displaystyle{ x^2 \equiv g \pmod{m} }[/math]
nie ma rozwiązania. Niech [math]\displaystyle{ m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math]. Zatem przynajmniej jedna z kongruencji
- [math]\displaystyle{ x^2 \equiv g \pmod{p^{\alpha_k}_k} }[/math]
musi nie mieć rozwiązania (zobacz J10). Z twierdzenia J37 wiemy, że wtedy kongruencja
- [math]\displaystyle{ x^2 \equiv g \pmod{p_k} }[/math]
również nie ma rozwiązania. Zatem [math]\displaystyle{ g }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p_k }[/math] i [math]\displaystyle{ g \lt g_k }[/math], co przeczy definicji liczby [math]\displaystyle{ g_k }[/math].
□
Twierdzenie J59
Jeżeli [math]\displaystyle{ m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math], to
- [math]\displaystyle{ g(m) = \min ( g (p_1), \ldots, g (p_s) ) }[/math]
gdzie [math]\displaystyle{ g(m) }[/math] jest najmniejszą liczbą kwadratową modulo [math]\displaystyle{ m }[/math], a [math]\displaystyle{ g(p_k) }[/math] są najmniejszymi liczbami kwadratowymi modulo [math]\displaystyle{ p_k }[/math].
Twierdzenie jest prostym wnioskiem z twierdzenia J58.
□
Twierdzenie J60
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math] będzie liczbą nieparzystą, a [math]\displaystyle{ g(m) }[/math] jest najmniejszą liczbą niekwadratową modulo [math]\displaystyle{ m }[/math]. Prawdziwe są oszacowania
- [math]\displaystyle{ g(m) \lt \sqrt{m} + {\small\frac{1}{2}} \qquad \qquad \;\;\: \text{dla } m \geqslant 3 }[/math]
- [math]\displaystyle{ g(m) \leqslant 1.1 \cdot m^{1 / 4} \log m \qquad \qquad \text{dla } m \geqslant 5 }[/math]
Niech [math]\displaystyle{ p }[/math] będzie dzielnikiem pierwszym liczby [math]\displaystyle{ m }[/math] takim, że [math]\displaystyle{ g(m) = g (p) }[/math] (z twierdzenia J58 wiemy, że taki dzielnik istnieje). Jeżeli prawdziwe jest oszacowanie [math]\displaystyle{ g(p) \lt F (p) }[/math], gdzie [math]\displaystyle{ F(x) }[/math] jest funkcją rosnącą, to
- [math]\displaystyle{ g(m) = g (p) \lt F (p) \leqslant F (m) }[/math]
Podane w twierdzeniu oszacowania wynikają natychmiast z twierdzeń J50 i J51.
□
C. Najmniejsze dodatnie liczby niekwadratowe [math]\displaystyle{ a }[/math] takie, że [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1 }[/math] |
Przykład J61
W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo [math]\displaystyle{ p }[/math], najmniejsze liczby niekwadratowe modulo [math]\displaystyle{ m }[/math] i najmniejsze dodatnie liczby niekwadratowe [math]\displaystyle{ a }[/math] takie, że [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1 }[/math].
[math]\displaystyle{ \boldsymbol{m} }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 7 }[/math] [math]\displaystyle{ 9 }[/math] [math]\displaystyle{ 11 }[/math] [math]\displaystyle{ 13 }[/math] [math]\displaystyle{ 15 }[/math] [math]\displaystyle{ 17 }[/math] [math]\displaystyle{ 19 }[/math] [math]\displaystyle{ 21 }[/math] [math]\displaystyle{ 23 }[/math] [math]\displaystyle{ 25 }[/math] [math]\displaystyle{ 27 }[/math] [math]\displaystyle{ 29 }[/math] [math]\displaystyle{ 31 }[/math] [math]\displaystyle{ 33 }[/math] [math]\displaystyle{ 35 }[/math] [math]\displaystyle{ 37 }[/math] [math]\displaystyle{ 39 }[/math] [math]\displaystyle{ 41 }[/math] [math]\displaystyle{ 43 }[/math] [math]\displaystyle{ 45 }[/math] [math]\displaystyle{ 47 }[/math] [math]\displaystyle{ 49 }[/math] [math]\displaystyle{ 51 }[/math] [math]\displaystyle{ \boldsymbol{g( p )} }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ \boldsymbol{g( m )} }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ \boldsymbol{c( m )} }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 7 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 7 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 2 }[/math] [math]\displaystyle{ 5 }[/math] [math]\displaystyle{ - }[/math] [math]\displaystyle{ 2 }[/math]
Uwaga J62
Do wyszukiwania liczb [math]\displaystyle{ c = c (m) }[/math] Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP
C(m) =
{
if( m%2 == 0, return(0) );
if( issquare(m), return(0) );
forprime(p = 2, m, if( jacobi(p, m) == -1, return(p) ));
}
Uwaga J63
Najmniejsze dodatnie liczby niekwadratowe [math]\displaystyle{ a }[/math] takie, że [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1 }[/math] oznaczyliśmy jako [math]\displaystyle{ c(m) }[/math]. Zauważmy, że są to liczby inne od [math]\displaystyle{ g(p) }[/math] i [math]\displaystyle{ g(m) }[/math]. Wystarczy zwrócić uwagę na występujące w tabeli liczby [math]\displaystyle{ g(p) }[/math], [math]\displaystyle{ g(m) }[/math] i [math]\displaystyle{ c(m) }[/math] dla [math]\displaystyle{ m = 15, 33, 39 }[/math]. Różnice wynikają z innej definicji liczb [math]\displaystyle{ c(m) }[/math] – jeżeli liczba [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ m }[/math], to symbol Jacobiego [math]\displaystyle{ \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} }[/math] nie musi być równy [math]\displaystyle{ - 1 }[/math]. I tak czasami bywa, co bardzo dobrze pokazuje powyższa tabela.
Ponieważ [math]\displaystyle{ c(m) }[/math] nie zawsze będzie najmniejszą liczbą kwadratową modulo [math]\displaystyle{ m }[/math], to mamy natychmiast oszacowanie: [math]\displaystyle{ c(m) \geqslant g (m) }[/math] (poza przypadkami, gdy [math]\displaystyle{ m = n^2 }[/math]).
Dla [math]\displaystyle{ c(m) }[/math] nie są prawdziwe oszacowania podane w twierdzeniu J50. Łatwo zauważamy, że
- [math]\displaystyle{ c = c (15) = 7 \gt \sqrt{15} + {\small\frac{1}{2}} \approx 4.37 }[/math]
- [math]\displaystyle{ c = c (39) = 7 \gt \sqrt{39} + {\small\frac{1}{2}} \approx 6.74 }[/math]
- [math]\displaystyle{ c = c (105) = 11 \gt \sqrt{105} + {\small\frac{1}{2}} \approx 10.75 }[/math]
- [math]\displaystyle{ c = c (231) = 17 \gt \sqrt{231} + {\small\frac{1}{2}} \approx 15.7 }[/math]
Nie ma więcej takich przypadków dla [math]\displaystyle{ m \lt 10^9 }[/math].
Twierdzenie J64
Niech [math]\displaystyle{ c, m \in \mathbb{Z}_+ }[/math] i niech [math]\displaystyle{ m \geqslant 3 }[/math] będzie liczbą nieparzystą, a [math]\displaystyle{ c }[/math] będzie najmniejszą liczbą taką, że [math]\displaystyle{ \left( {\small\frac{c}{m}} \right)_{\small{\!\! J}} = - 1 }[/math]. Liczba [math]\displaystyle{ c }[/math] musi być liczbą pierwszą.
Przypuśćmy, że [math]\displaystyle{ c = a b }[/math] jest liczbą złożoną, gdzie [math]\displaystyle{ 1 \lt a, b \lt c }[/math]. Mamy
- [math]\displaystyle{ - 1 = \left( {\small\frac{c}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{a b}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} }[/math][math]\displaystyle{ \left( {\small\frac{b}{m}} \right)_{\small{\!\! J}} }[/math]
Zatem jeden z czynników po prawej stronie musi być równy [math]\displaystyle{ - 1 }[/math] wbrew definicji liczby [math]\displaystyle{ c }[/math].
□
Uwaga J65
Liczby [math]\displaystyle{ c = c (m) }[/math] są zaskakująco małe. Średnia wartość [math]\displaystyle{ c = c (m) }[/math], gdzie [math]\displaystyle{ m }[/math] są liczbami nieparzystymi (przyjmujemy [math]\displaystyle{ c(m) = 0 }[/math], gdy [math]\displaystyle{ m }[/math] jest liczbą kwadratową) wynosi[11]
- [math]\displaystyle{ \lim_{x \to \infty} {\small\frac{1}{x / 2}} \underset{m \; \text{nieparzyste}}{\sum_{m \leqslant x}} c (m) = \sum_{k = 2}^{\infty} {\small\frac{p_k + 1}{2^{k - 1}}} \prod^{k - 1}_{j = 1} \left( 1 - {\small\frac{1}{p_j}} \right) = 3.147755149 \ldots }[/math]
Przypisy
- ↑ Wikipedia, Chińskie twierdzenie o resztach, (Wiki-pl), (Wiki-en)
- ↑ CRT to często używany skrót od angielskiej nazwy twierdzenia: Chinese remainder theorem
- ↑ Wikipedia, Logical equivalence, (Wiki-en)
- ↑ Wikipedia, Zasada włączeń i wyłączeń, (Wiki-pl), (Wiki-en)
- ↑ Wikipedia, Symbol Legendre’a, (Wiki-pl), (Wiki-en)
- ↑ Wikipedia, Symbol Jacobiego, (Wiki-pl), (Wiki-en)
- ↑ Karl K. Norton, Numbers with Small Prime Factors, and the Least kth Power Non-Residue, Memoirs of the American Mathematical Society, No. 106 (1971)
- ↑ Enrique Treviño, The least k-th power non-residue, Journal of Number Theory, Volume 149 (2015)
- ↑ Kevin J. McGown and Enrique Treviño, The least quadratic non-residue, Mexican Mathematicians in the World (2021)
- ↑ Paul Erdős, Számelméleti megjegyzések I, Afar. Lapok, v. 12 (1961)
- ↑ Robert Baillie and Samuel S. Wagstaff Jr., Lucas Pseudoprimes, Mathematics of Computation Vol. 35, No. 152 (1980), (LINK)