|
|
Linia 1: |
Linia 1: |
− | <div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">22.03.2023</div> | + | <div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">11.11.2022</div> |
| | | |
| __FORCETOC__ | | __FORCETOC__ |
Linia 5: |
Linia 5: |
| | | |
| | | |
− | == Chińskie twierdzenie o resztach == | + | == Potęgowanie modulo == |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J1</span><br/> | + | <span style="font-size: 110%; font-weight: bold;">Uwaga K1</span><br/> |
− | Niech <math>a, u \in \mathbb{Z}</math> i <math>m, n \in \mathbb{Z}_+</math> i <math>\gcd (m, n) = 1</math>. Kongruencja
| + | Z twierdzenia Fermata (zobacz J18) wynika, że jeżeli liczby <math>a</math> i <math>m</math> są względnie pierwsze oraz <math>m</math> nie dzieli liczby <math>a^{m - 1} - 1</math>, to <math>m</math> jest liczbą złożoną. Każde twierdzenie pozwalające wykryć złożoność liczby może być wykorzystane do badania pierwszości liczb. Twierdzenia takie nie dają całkowitej pewności, że badana liczba jest pierwsza. Mamy na przykład <math>341 = 11 \cdot 31</math>, ale <math>341 | (2^{340} - 1)</math>, bo |
| | | |
− | ::<math>u \equiv a \pmod{m n}</math> | + | ::<math>2^{340} - 1 = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115775</math> |
| | | |
− | jest równoważna układowi kongruencji
| + | ::::<math>\;\;\; = 341 \cdot 6568166399348399444449977362370804334667582103327417990909058947107894050381703652143335757394742275</math> |
| | | |
− | ::<math>\begin{align}
| + | Widzimy, że nawet dla niewielkiej liczby <math>341</math>, potęga <math>2^{340} - 1</math> jest liczbą ogromną. Jeśli ta metoda ma mieć jakiekolwiek zastosowanie, to musimy znaleźć inny sposób obliczania reszty z dzielenia <math>a^n</math> przez <math>m</math>, czyli potęgowania modulo <math>m</math>. |
− | u &\equiv a \pmod{m} \\
| |
− | u &\equiv a \pmod{n}
| |
− | \end{align}</math>
| |
| | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | <math>\Longrightarrow</math><br/>
| |
− | Jeżeli liczba <math>u - a</math> jest podzielna przez iloczyn <math>m n</math>, to tym bardziej jest podzielna przez dowolny czynnik tego iloczynu, skąd wynika natychmiast wypisany układ kongruencji.
| |
| | | |
− | <math>\Longleftarrow</math><br/>
| |
− | Z kongruencji
| |
| | | |
− | ::<math>u \equiv a \pmod{m}</math> | + | <span style="font-size: 110%; font-weight: bold;">Uwaga K2</span><br/> |
| + | Wykorzystując wzór rekurencyjny |
| | | |
− | wynika, że <math>u - a = k m</math>, zaś z kongruencji
| + | ::<math>a^n = \left\{ \begin{array}{cll} |
| + | a & & \text{gdy } n = 1\\ |
| + | (a^2)^{{\large\frac{n}{2}}} & & \text{gdy } n \text{ jest parzyste}\\ |
| + | a \cdot (a^2)^{{\large\frac{n - 1}{2}}} & & \text{gdy } n \text{ jest nieparzyste} |
| + | \end{array} \right.</math> |
| | | |
− | ::<math>u \equiv a \pmod{n}</math>
| |
| | | |
− | otrzymujemy <math>n \, | \, (u - a)</math>, czyli <math>n \, | \, k m</math>. Ponieważ <math>\gcd (m, n) = 1</math>, zatem <math>n \, | \, k</math> (zobacz C72) i istnieje taka liczba całkowita <math>s</math>, że <math>k = s n</math>, czyli <math>u - a = s n m</math>, a stąd <math>u \equiv a \pmod{m n}</math>. Co kończy dowód.<br/>
| + | możemy napisać w PARI/GP prosty program do potęgowania modulo: |
− | □
| |
− | {{\Spoiler}}
| |
| | | |
| + | <span style="font-size: 90%; color:black;">modPower(a, n, m) = |
| + | \\ a - podstawa, n - wykładnik, m - moduł |
| + | { |
| + | '''local'''(w); |
| + | '''if'''( m == 1, '''return'''(0) ); |
| + | a = a % m; |
| + | w = 1; |
| + | '''while'''( n > 0, |
| + | '''if'''( n % 2 == 1, w = (w * a) % m; n = n - 1); \\ gdy n jest nieparzyste, wyłączamy a i zmniejszamy n o jeden |
| + | a = (a*a) % m; \\ wyliczamy nową podstawę modulo m |
| + | n = n/2; \\ dla nowej podstawy wykładnik jest dwa razy mniejszy |
| + | ); |
| + | '''return'''(w); |
| + | }</span> |
| | | |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J2</span><br/>
| + | Zauważmy, że w funkcji <code>modPower()</code> nie występują wyrażenia o wartości większej od <math>m^2</math>. |
− | Dla dowolnych liczb <math>a, b \in \mathbb{Z}</math> i względnie pierwszych liczb <math>m, n \in \mathbb{Z}_+</math> istnieje dokładnie jedna taka liczba <math>c</math> (określona modulo <math>m n</math>), że prawdziwy jest układ kongruencji
| |
− | | |
− | ::<math>\begin{align}
| |
− | c & \equiv a \pmod{m} \\
| |
− | c & \equiv b \pmod{n}
| |
− | \end{align}</math>
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Z założenia liczby <math>m</math> i <math>n</math> są względnie pierwsze, zatem na mocy lematu Bézouta (C.71) istnieją takie liczby <math>x, y \in \mathbb{Z}</math>, że
| |
− | | |
− | ::<math>m x + n y = 1</math>
| |
− | | |
− | Niech <math>c = a n y + b m x</math>. Modulo <math>m</math> dostajemy
| |
− | | |
− | ::<math>c \equiv a n y \pmod{m}</math>
| |
− | | |
− | ::<math>c \equiv a (1 - m x) \pmod{m}</math>
| |
− | | |
− | ::<math>c \equiv a \pmod{m}</math>
| |
− | | |
− | Natomiast modulo <math>n</math> mamy
| |
− | | |
− | ::<math>c \equiv b m x \pmod{n}</math>
| |
− | | |
− | ::<math>c \equiv b (1 - n y) \pmod{n}</math>
| |
− | | |
− | ::<math>c \equiv b \pmod{n}</math>
| |
− | | |
− | Pokazaliśmy tym samym istnienie szukanej liczby <math>c</math>. Przypuśćmy, że istnieją dwie takie liczby <math>c</math> i <math>d</math>. Z założenia <math>m \, | \, (d - a)</math> i <math>m \, | \, (c - a)</math>, zatem <math>m</math> dzieli różnicę tych liczb, czyli <math>m \, | \, (d - c)</math>. Podobnie pokazujemy, że <math>n \, | \, (d - c)</math>. Ponieważ liczby <math>m</math> i <math>n</math> są względnie pierwsze, to <math>m n \, | \, (d - c)</math> (zobacz C73), co oznacza, że
| |
− | | |
− | ::<math>d \equiv c \pmod{m n}</math>.
| |
| | | |
− | Czyli możemy powiedzieć, że wybrana przez nas liczba <math>c</math> jest określona modulo <math>m n</math> i tak rozumiana jest dokładnie jedna. W szczególności istnieje tylko jedna liczba <math>c</math> taka, że <math>1 \leqslant c \leqslant m n</math>.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
| | | |
| | | |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J3 (chińskie twierdzenie o resztach)</span><br/>
| |
− | Niech <math>a, b, c, u \in \mathbb{Z}</math> i <math>m, n \in \mathbb{Z}_+</math> oraz niech <math>\gcd (m, n) = 1</math>. Istnieje dokładnie jedna liczba <math>c</math> (określona modulo <math>m n</math>) taka, że kongruencja
| |
| | | |
− | ::<math>u \equiv c \pmod{m n}</math>
| + | == Liczby pseudopierwsze Fermata == |
| | | |
− | jest równoważna układowi kongruencji
| + | Liczby złożone nieparzyste spełniające równanie Fermata, otrzymały własną nazwę. |
| | | |
− | ::<math>\begin{align} | + | <span style="font-size: 110%; font-weight: bold;">Definicja K3</span><br/> |
− | u & \equiv a \pmod{m} \\
| + | Jeżeli <math>m</math> jest liczbą złożoną nieparzystą i dla pewnego <math>a \in \mathbb{Z}</math> prawdziwa jest kongruencja |
− | u & \equiv b \pmod{n}
| |
− | \end{align}</math> | |
| | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| + | ::<math>a^{m - 1} \equiv 1 \pmod m</math> |
− | Z twierdzenia J2 wiemy, że istnieje dokładnie jedna liczba <math>c</math> (określona modulo <math>m n</math>) taka, że prawdziwy jest układ kongruencji
| |
| | | |
− | ::<math>\begin{align} | + | to powiemy, że <math>m</math> jest liczbą pseudopierwszą Fermata przy podstawie <math>a</math> lub krótko: <math>m</math> jest PSP(<math>a</math>). |
− | c & \equiv a \pmod{m} \\
| |
− | c & \equiv b \pmod{n}
| |
− | \end{align}</math>
| |
| | | |
− | Korzystając z tego rezultatu i twierdzenia J1, otrzymujemy
| |
| | | |
− | ::<math>u \equiv c \pmod{m n} \qquad \Longleftrightarrow \qquad
| |
− | \begin{array}{l}
| |
− | u \equiv c \; \pmod{m} \\
| |
− | u \equiv c \; \pmod{n} \\
| |
− | \end{array} \qquad \Longleftrightarrow \qquad
| |
− | \begin{array}{l}
| |
− | u \equiv a \; \pmod{m} \\
| |
− | u \equiv b \:\, \pmod{n} \\
| |
− | \end{array} </math>
| |
| | | |
− | Co należało pokazać.<br/>
| + | <span style="font-size: 110%; font-weight: bold;">Uwaga K4</span><br/> |
− | □ | + | Zauważmy, że w definicji liczb pseudopierwszych Fermata nie musimy dodatkowo dołączać warunku <math>\gcd (a, m) = 1</math>, bo wynika on z przyjętej definicji. Mamy |
− | {{\Spoiler}}
| |
| | | |
| + | ::<math>\gcd (a^{m - 1}, m) = \gcd (1, m) = 1</math> |
| | | |
| + | Zatem <math>\gcd (a, m) = 1</math>. |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J4</span><br/> | + | Możemy też łatwo pokazać, że jeżeli <math>\gcd (a, m) = d > 1</math>, to liczba <math>m</math> nie może być liczbą pseudopierwszą Fermata przy podstawie <math>a</math>. Istotnie, gdyby tak było, to mielibyśmy |
− | 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>a^{m - 1} \equiv 1 \pmod{m}</math> |
− | 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>u = 4 k + 1</math>, które dla liczb <math>k</math> parzystych i nieparzystych ma postać
| + | Ponieważ <math>d|m</math>, to jest również |
| | | |
− | ::<math>u = 8 j + 1, \qquad u = 8 j + 5</math> | + | ::<math>a^{m - 1} \equiv 1 \pmod{d}</math> |
| | | |
− | i nie może być <math>u \equiv 3 \pmod{8}</math>.
| + | Ale modulo <math>d</math> otrzymujemy natychmiast |
| | | |
| + | ::<math>0 \equiv 1 \pmod{d}</math> |
| | | |
| + | Co jest niemożliwe, czyli <math>m</math> nie jest PSP(<math>a</math>). |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Zadanie J5</span><br/>
| |
− | Niech <math>u, a_1, \ldots, a_k \in \mathbb{Z}</math> i <math>m_1, \ldots, m_k \in \mathbb{Z}_+</math>. Pokazać, że jeżeli liczby <math>m_1, \ldots, m_k</math> są parami względnie pierwsze (czyli <math>\gcd (m_i, m_j) = 1</math> dla <math>i \neq j</math>), to istnieje dokładnie jedna liczba <math>c</math> (określona modulo <math>m_1 \cdot \ldots \cdot m_k</math>), ż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
| + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie K5</span><br/> |
− | | + | Dla każdej podstawy <math>a \geqslant 2</math> istnieje nieskończenie wiele liczb pseudopierwszych Fermata. |
− | ::<math>u \equiv c \;\; \pmod{m_1 \cdot \ldots \cdot m_k}</math>
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
| |
− | Indukcja matematyczna. Twierdzenie jest prawdziwe dla liczby <math>k = 2</math> (zobacz J3). Zakładając prawdziwość twierdzenia dla 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 J3 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 J6</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
| |
− | | |
− | ::<math>\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>35</math>. Jeśli chcemy zaoszczędzić sobie trudu, to wystarczy skorzystać z PARI/GP. Wpisując proste polecenie
| |
− | | |
− | <span style="font-size: 90%; color:black;">chinese( Mod(3,5), Mod(4,7) )</span>
| |
− | | |
− | uzyskujemy wynik <code>Mod(18, 35)</code>, zatem równoważna kongruencja ma postać
| |
− | | |
− | ::<math>n \equiv 18 \pmod{35}</math>
| |
− | | |
− | Jest to zarazem odpowiedź na postawione pytanie: najmniejsza liczba kulek wynosi <math>18</math>.
| |
− | | |
− | Gdybyśmy chcieli rozważać bardziej rozbudowany układ kongruencji, przykładowo
| |
− | | |
− | ::<math>\begin{align}
| |
− | n &\equiv 1 \pmod{2} \\
| |
− | n &\equiv 2 \pmod{3} \\
| |
− | n &\equiv 3 \pmod{5} \\
| |
− | n &\equiv 4 \pmod{7} \\
| |
− | n &\equiv 5 \pmod{11}
| |
− | \end{align}</math>
| |
− | | |
− | to argumenty należy zapisać w postaci wektora
| |
− | | |
− | <span style="font-size: 90%; color:black;">chinese( [Mod(1,2), Mod(2,3), Mod(3,5), Mod(4,7), Mod(5,11)] )</span>
| |
− | | |
− | Otrzymujemy <code>Mod(1523, 2310)</code>.
| |
− | | |
− | | |
− | | |
− | | |
− | | |
− | == Wielomiany ==
| |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J7</span><br/>
| |
− | Niech <math>W_n (x)</math> będzie dowolnym wielomianem stopnia <math>n</math>. Wielomian <math>W_n (x)</math> można przedstawić w postaci
| |
− | | |
− | ::<math>W_n (x) = W_n (s) + (x - s) V_{n - 1} (x)</math>
| |
− | | |
− | gdzie <math>V_{n - 1} (x)</math> jest wielomianem stopnia <math>n - 1</math>, a współczynniki wiodące wielomianów <math>W_n (x)</math> i <math>V_{n - 1} (x)</math> są sobie równe.
| |
| | | |
| {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} |
− | Z założenia <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math>, gdzie <math>a_n \neq 0</math>. Zauważmy, że
| + | Niech <math>a \in \mathbb{Z}</math> i <math>a \geqslant 2</math>. Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą, to |
− | | |
− | ::<math>W_n (x) - W_n (s) = \sum_{k = 0}^{n} a_k x^k - \sum_{k = 0}^{n} a_k s^k</math>
| |
| | | |
− | ::::::<math>\quad \; = \sum_{k = 1}^{n} a_k (x^k - s^k)</math>
| + | ::<math>a^p - 1 = (a - 1) (a^{p - 1} + a^{p - 2} + \ldots + a^2 + a + 1)</math> |
| | | |
− | Dla <math>k \geqslant 1</math> prawdziwy jest wzór
| + | oraz |
| | | |
− | ::<math>x^k - s^k = (x - s) \sum_{j = 1}^{k} x^{k - j} s^{j - 1}</math> | + | ::<math>a^p + 1 = (a + 1) (a^{p - 1} - a^{p - 2} + \ldots + a^2 - a + 1)</math> |
| | | |
− | ::::<math>\;\,\, = (x - s) (x^{k - 1} + s x^{k - 2} + \ldots + s^{k - 2} x + s^{k - 1})</math>
| + | Czyli <math>a - 1 | a^p - 1</math> oraz <math>a + 1 | a^p + 1</math>. |
| | | |
− | ::::<math>\;\,\, = (x - s) U^{(k)} (x)</math>
| |
| | | |
− | Gdzie przez <math>U^{(k)} (x) = \sum_{j = 1}^{k} x^{k - j} s^{j - 1}</math> oznaczyliśmy wielomian, którego stopień jest równy <math>k - 1</math>. Zatem możemy napisać
| + | Jeżeli przez <math>R_2 (a)</math> oznaczymy resztę z dzielenia liczby <math>a</math> przez <math>2</math> równą <math>0</math> lub <math>1</math>, to prawdziwe są kongruencje |
| | | |
− | ::<math>W_n (x) - W_n (s) = (x - s) \sum_{k = 1}^{n} a_k U^{(k)} (x)</math> | + | ::<math>a \equiv R_2 (a) \pmod 2</math> |
− | | |
− | Suma wypisana po prawej stronie jest pewnym wielomianem <math>V_{n - 1} (x)</math>. Ponieważ ze wszystkich wielomianów <math>a_k U^{(k)} (x)</math>, wielomian <math>a_n U^{(n)} (x)</math> ma największy stopień równy <math>n - 1</math>, to stopień wielomianu <math>V_{n - 1} (x)</math> jest równy <math>n - 1</math>. Czyli
| |
− | | |
− | ::<math>W_n (x) - W_n (s) = (x - s) V_{n - 1} (x)</math>
| |
− | | |
− | Niech <math>V_n (x) = \sum_{k = 0}^{n - 1} b_k x^k</math>. Mamy
| |
− | | |
− | ::<math>\sum_{k = 0}^{n} a_k x^k - W_n (s) = \sum_{k = 0}^{n - 1} b_k x^{k + 1} + s \sum_{k = 0}^{n - 1} b_k x^k</math>
| |
− | | |
− | Porównując wyrazy o największym stopniu, łatwo zauważamy, że <math>a_n = b_{n - 1}</math>. Czyli współczynnik wiodący wielomianu <math>V_{n - 1} (x)</math> jest równy <math>a_n</math>. Co należało pokazać.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Definicja J8</span><br/>
| |
− | Wielomian <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math>, gdzie <math>a_0, \ldots, a_n \in \mathbb{Z}</math> oraz <math>a_n \neq 0</math>, będziemy nazywali wielomianem całkowitym stopnia <math>n</math>.
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Definicja J9</span><br/>
| |
− | Powiemy, że wielomian całkowity <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math> jest stopnia <math>n</math> modulo <math>p</math>, gdzie <math>p</math> jest liczbą pierwszą, jeżeli <math>p \nmid a_n</math>. Jeżeli każdy współczynnik <math>a_k</math>, gdzie <math>k = 0, 1, \ldots, n</math>, jest podzielny przez <math>p</math>, to stopień wielomianu <math>W_n (x)</math> modulo <math>p</math> jest nieokreślony.
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J10</span><br/>
| |
− | Niech <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math> będzie wielomianem całkowitym i <math>m \in \mathbb{Z}_+</math>. Jeżeli prawdziwa jest kongruencja <math>x \equiv y \pmod{m}</math>, to
| |
− | | |
− | ::<math>W_n (x) \equiv W_n (y) \pmod{m}</math>
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Dla <math>k \geqslant 1</math> wyrażenie <math>x^k - y^k</math> jest podzielne przez <math>x - y</math>, co łatwo pokazać stosując indukcję matematyczną lub zauważając, że
| |
− | | |
− | ::<math>x^k - y^k = (x - y) \sum_{j = 1}^{k} x^{k - j} y^{j - 1}</math>
| |
− | | |
− | Z założenia <math>m \, | \, (x - y)</math>, zatem dla <math>k \geqslant 1</math> mamy <math>m \, | \, (x^k - y^k)</math>. Wynika stąd, że prawdziwe są kongruencje
| |
− | | |
− | ::<math>\begin{align}
| |
− | a_0 & \equiv a_0 \;\;\:\, \pmod{m}\\
| |
− | a_1 x & \equiv a_1 y \;\, \pmod{m}\\
| |
− | a_2 x^2 & \equiv a_2 y^2 \pmod{m}\\
| |
− | & \cdots \\
| |
− | a_n x^n & \equiv a_n y^n \pmod{m}
| |
− | \end{align}</math>
| |
− | | |
− | Dodając wypisane kongruencje stronami, otrzymujemy
| |
− | | |
− | ::<math>W_n (x) \equiv W_n (y) \pmod{m}</math>
| |
− | | |
− | Co należało pokazać.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J11</span><br/>
| |
− | Niech <math>W(x)</math> będzie wielomianem całkowitym. Rozważmy kongruencję
| |
− | | |
− | ::<math>W(x) \equiv 0 \pmod{m n} \qquad \qquad \qquad (1)</math>
| |
− | | |
− | gdzie liczby <math>m</math> i <math>n</math> są względnie pierwsze.
| |
− | | |
− | Kongruencja ta jest równoważna układowi kongruencji
| |
− | | |
− | ::<math>\begin{align}
| |
− | W (x) &\equiv 0 \pmod{m}\\
| |
− | W (x) &\equiv 0 \pmod{n}
| |
− | \end{align} \qquad \qquad \qquad \; (2)</math>
| |
− | | |
− | Zatem problem szukania rozwiązań kongruencji <math>(1)</math> możemy sprowadzić do szukania rozwiązań układu kongruencji <math>(2)</math>. W szczególności wynika stąd, że jeżeli któraś z kongruencji <math>(2)</math> nie ma rozwiązania, to kongruencja <math>W(x) \equiv 0 \pmod{m n}</math> również nie ma rozwiązania.
| |
− | | |
− | Załóżmy, że każda z kongruencji <math>(2)</math> ma przynajmniej jedno rozwiązanie i niech
| |
− | | |
− | :* <math>x \equiv a \pmod{m}</math> będzie pierwiastkiem kongruencji <math>W (x) \equiv 0 \pmod{m}</math>
| |
− | :* <math>x \equiv b \pmod{n}</math> będzie pierwiastkiem kongruencji <math>W (x) \equiv 0 \pmod{n}</math>
| |
− | | |
− | Pierwiastki te tworzą układ kongruencji
| |
− | | |
− | ::<math>\begin{align}
| |
− | x &\equiv a \pmod{m} \\
| |
− | x &\equiv b \pmod{n}
| |
− | \end{align} \qquad \qquad \qquad \qquad (3)</math>
| |
− | | |
− | Z chińskiego twierdzenia o resztach wiemy, że układ ten możemy zapisać w postaci równoważnej
| |
− | | |
− | ::<math>x \equiv c \pmod{m n}</math>
| |
− | | |
− | Zauważmy, że liczba <math>c</math> określona modulo <math>m n</math> jest rozwiązaniem kongruencji <math>(1)</math>. Istotnie z twierdzenia J10 mamy
| |
− | | |
− | ::<math>\begin{align}
| |
− | W (c) &\equiv W (a) \equiv 0 \pmod{m} \\
| |
− | W (c) &\equiv W (b) \equiv 0 \pmod{n}
| |
− | \end{align}</math>
| |
− | | |
− | ale liczby <math>m, n</math> są względnie pierwsze, zatem otrzymujemy, że
| |
− | | |
− | ::<math>W (c) \equiv 0 \pmod{m n}</math>
| |
− | | |
− | Wynika stąd, że każdemu układowi rozwiązań <math>(3)</math> odpowiada dokładnie jedno rozwiązanie kongruencji <math>(1)</math>.
| |
− | | |
− | Podsumujmy: jeżeli kongruencje
| |
− | | |
− | ::<math>\begin{align}
| |
− | W (x) &\equiv 0 \pmod{m}\\
| |
− | W (x) &\equiv 0 \pmod{n}
| |
− | \end{align}</math>
| |
− | | |
− | mają odpowiednio <math>r</math> i <math>s</math> pierwiastków, to liczba różnych układów kongruencji <math>(3)</math> jest równa iloczynowi <math>r s</math> i istnieje <math>r s</math> różnych rozwiązań kongruencji
| |
− | | |
− | ::<math>W(x) \equiv 0 \pmod{m n}</math>
| |
− | | |
− | | |
− | | |
− | | |
− | | |
− | == Twierdzenie Lagrange'a ==
| |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J12</span><br/>
| |
− | Kongruencja
| |
− | | |
− | ::<math>a_1 x + a_0 \equiv 0 \pmod{p}</math>
| |
− | | |
− | gdzie <math>p \nmid a_1</math>, ma dokładnie jedno rozwiązanie modulo <math>p</math>.
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | | |
− | '''A. Istnienie rozwiązania'''
| |
− | | |
− | Ponieważ rozpatrywaną kongruencję możemy zapisać w postaci <math>a_1 x + a_0 = k p</math>, to istnienie liczb <math>x</math> i <math>k</math>, dla których ta równość jest prawdziwa, wynika z twierdzenia C74. Poniżej przedstawimy jeszcze jeden sposób znalezienia rozwiązania.
| |
− | | |
− | Ponieważ <math>\gcd (a_1, p) = 1</math>, to istnieją takie liczby <math>r, s</math>, że <math>a_1 r + p s = 1</math> (zobacz C71 - lemat Bézouta). Zauważmy, że <math>p \nmid r</math>, bo gdyby tak było, to liczba pierwsza <math>p</math> dzieliłaby wyrażenie <math>a_1 r + p s</math>, ale jest to niemożliwe, bo <math>a_1 r + p s = 1</math>. Czyli modulo <math>p</math> mamy
| |
− | | |
− | ::<math>a_1 r \equiv 1 \pmod{p}</math>
| |
− | | |
− | Mnożąc rozpatrywaną kongruencję przez <math>r</math>, otrzymujemy
| |
− | | |
− | ::<math>a_1 r x + a_0 r \equiv 0 \pmod{p}</math>
| |
− | | |
− | Zatem
| |
− | | |
− | ::<math>x \equiv - a_0 r \pmod{p}</math>
| |
− | | |
− | '''B. Brak innych rozwiązań'''
| |
− | | |
− | Przypuśćmy, że istnieją dwa różne rozwiązania kongruencji
| |
− | | |
− | ::<math>a_1 x + a_0 \equiv 0 \pmod{p}</math>
| |
− | | |
− | Jeśli oznaczymy je przez <math>x_1</math> i <math>x_2</math>, to otrzymamy
| |
− | | |
− | ::<math>a_1 x_1 + a_0 \equiv 0 \equiv a_1 x_2 + a_0 \pmod{p}</math>
| |
− | | |
− | Czyli
| |
− | | |
− | ::<math>a_1 x_1 \equiv a_1 x_2 \pmod{p}</math>
| |
− | | |
− | ::<math>p \, | \, a_1 (x_1 - x_2)</math>
| |
− | | |
− | Ponieważ <math>p \nmid a_1</math>, to z lematu Euklidesa (C72) otrzymujemy natychmiast <math>p \, | \, (x_1 - x_2)</math>. Skąd wynika, że <math>x_1 \equiv x_2 \pmod{p}</math>, wbrew założeniu, że <math>x_1</math> i <math>x_2</math> są dwoma różnymi rozwiązaniami. Co kończy dowód.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J13 (Joseph Louis Lagrange, 1768)</span><br/>
| |
− | Jeżeli wielomian <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math> ma stopień <math>n</math> modulo <math>p</math>, gdzie <math>n \geqslant 1</math>, to kongruencja
| |
− | | |
− | ::<math>W_n (x) \equiv 0 \pmod{p}</math>
| |
− | | |
− | ma co najwyżej <math>n</math> rozwiązań.
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Indukcja matematyczna. Z J12 wiemy, że dowodzone twierdzenie jest prawdziwe dla <math>n = 1</math>. Załóżmy, że twierdzenie jest prawdziwe dla wszystkich liczb całkowitych dodatnich nie większych od <math>n - 1</math>. Niech wielomian <math>W_n (x)</math> ma stopień <math>n</math> modulo <math>p</math>. Jeżeli kongruencja
| |
− | | |
− | ::<math>W_n (x) \equiv 0 \pmod{p}</math>
| |
− | | |
− | nie ma żadnego rozwiązania, to dowodzone twierdzenie jest prawdziwe dla <math>n</math>. Przypuśćmy teraz, że wypisana wyżej kongruencja ma przynajmniej jeden pierwiastek <math>x \equiv s \pmod{p}</math>. Korzystając z twierdzenia J7, możemy napisać
| |
− | | |
− | ::<math>W_n (x) - W_n (s) = (x - s) V_{n - 1} (x)</math>
| |
− | | |
− | gdzie wielomian <math>V_{n - 1} (x)</math> ma stopień <math>n - 1</math> modulo <math>p</math>, bo wielomiany <math>W_n (x)</math> oraz <math>V_{n - 1} (x)</math> mają jednakowe współczynniki wiodące.
| |
− | | |
− | | |
− | Z założenia <math>x \equiv s \pmod{p}</math> jest jednym z pierwiastków kongruencji <math>W_n (x) \equiv 0 \pmod{p}</math>, zatem modulo <math>p</math> otrzymujemy
| |
− | | |
− | ::<math>W_n (x) \equiv (x - s) V_{n - 1} (x) \pmod{p}</math>
| |
− | | |
− | Ponieważ <math>p</math> jest liczbą pierwszą, to z rozpatrywanej kongruencji
| |
− | | |
− | ::<math>W_n (x) \equiv 0 \pmod{p}</math>
| |
− | | |
− | wynika, że musi być (zobacz C72)
| |
− | | |
− | ::<math>x \equiv s \pmod{p} \qquad \qquad \text{lub} \qquad \qquad V_{n - 1} (x) \equiv 0 \pmod{p}</math>
| |
− | | |
− | | |
− | Z założenia indukcyjnego kongruencja
| |
− | | |
− | ::<math>V_{n - 1} (x) \pmod{p}</math>
| |
− | | |
− | ma co najwyżej <math>n - 1</math> rozwiązań, zatem kongruencja
| |
− | | |
− | ::<math>W_n (x) \equiv 0 \pmod{p}</math>
| |
− | | |
− | ma nie więcej niż <math>n</math> rozwiązań. Co należało pokazać.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J14</span><br/>
| |
− | Jeżeli kongruencja
| |
− | | |
− | ::<math>a_n x^n + a_{n - 1} x^{n - 1} + \ldots + a_1 x + a_0 \equiv 0 \pmod{p}</math>
| |
− | | |
− | ma więcej niż <math>n</math> rozwiązań, to wszystkie współczynniki <math>a_k</math>, gdzie <math>k = 0, \ldots, n</math>, muszą być podzielne przez <math>p</math>.
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Niech <math>S \subset \{ 0, 1, \ldots, n \}</math> będzie zbiorem takim, że dla każdego <math>k \in S</math> jest <math>p \nmid a_k</math>. Przypuśćmy, że <math>S</math> jest zbiorem niepustym. Niech <math>j</math> oznacza największy element zbioru <math>S</math>. Jeżeli <math>j = 0</math>, to wielomian <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math> jest stopnia <math>0</math> modulo <math>p</math> i
| |
− | | |
− | ::<math>a_0 \not\equiv 0 \pmod{p}</math>
| |
− | | |
− | Konsekwentnie, dla dowolnego <math>x \in \mathbb{Z}</math> jest
| |
− | | |
− | ::<math>a_n x^n + a_{n - 1} x^{n - 1} + \ldots + a_1 x + a_0 \not\equiv 0 \pmod{p}</math>
| |
− | | |
− | bo dla każdego <math>1 \leqslant k \leqslant n</math> mamy <math>a_k \equiv 0 \pmod{p}</math>. Zatem rozpatrywana kongruencja nie ma ani jednego rozwiązania, czyli rozwiązań nie może być więcej niż <math>n</math>.
| |
− | | |
− | W przypadku gdy <math>j \neq 0</math>, z twierdzenia Lagrange'a wynika, że rozpatrywana kongruencja ma nie więcej niż <math>j \leqslant n</math> rozwiązań, ponownie wbrew założeniu, że kongruencja ta ma więcej niż <math>n</math> rozwiązań. Uczynione przypuszczenie, że <math>S</math> jest zbiorem niepustym, okazało się fałszywe, zatem zbiór <math>S</math> musi być zbiorem pustym. Co należało pokazać.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Przykład J15</span><br/>
| |
− | Z twierdzenia Lagrange'a wynika, że kongruencja
| |
− | | |
− | ::<math>x^p - x - 1 \equiv 0 \pmod{p}</math>
| |
− | | |
− | ma co najwyżej <math>p</math> rozwiązań. W rzeczywistości nie ma ani jednego rozwiązania, bo z twierdzenia Fermata wiemy, że dla dowolnej liczby pierwszej <math>p</math> jest
| |
− | | |
− | ::<math>x^p \equiv x \pmod{p}</math>
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Przykład J16</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
| |
− | | |
− | ::<math>W(x) = x^{15} + 11 x^{11} + 5 x^5 + 2 x^2 + x + 1</math>
| |
− | | |
− | Ponieważ <math>x^5 \equiv x \pmod{5}</math>, to
| |
− | | |
− | ::<math>W(x) \equiv x^3 + 11 x^3 + 5 x + 2 x^2 + x + 1 \equiv 12 x^3 + 2 x^2 + 6 x + 1 \pmod{5}</math>
| |
− | | |
− | Co wynika również z faktu, że <math>W(x)</math> można zapisać w postaci
| |
− | | |
− | ::<math>W(x) = x^{15} + 11 x^{11} + 5 x^5 + 2 x^2 + x + 1 = (x^5 - x) (x^{10} + 12 x^6 + 12 x^2 + 5) + 12 x^3 + 2 x^2 + 6 x + 1</math>
| |
− | | |
− | ale <math>x^5 - x \equiv 0 \pmod{5}</math> na mocy twierdzenia Fermata.
| |
− | | |
− | | |
− | | |
− | | |
− | | |
− | | |
− | | |
− | | |
− | == Twierdzenie Wilsona ==
| |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J17 (John Wilson, 1770)</span><br/>
| |
− | Liczba całkowita <math>p \geqslant 2</math> jest liczbą pierwszą wtedy i tylko wtedy, gdy
| |
− | | |
− | ::<math>(p - 1) ! \equiv - 1 \pmod{p}</math>
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | <math>\Longleftarrow</math><br/>
| |
− | Przypuśćmy, że prawdziwa jest kongruencja <math>(p - 1) ! \equiv - 1 \pmod{p}</math> oraz <math>p</math> jest liczbą złożoną. Zatem liczba <math>p</math> ma dzielnik <math>d</math> taki, że <math>2 \leqslant d \leqslant p - 1</math>. Ponieważ <math>d \, | \, p</math>, to prawdziwa jest kongruencja
| |
− | | |
− | ::<math>(p - 1) ! \equiv - 1 \pmod{d}</math>
| |
− | | |
− | czyli
| |
− | | |
− | ::<math>0 \equiv - 1 \pmod{d}</math>
| |
− | | |
− | co jest niemożliwe.
| |
− | | |
− | <math>\Longrightarrow</math><br/>
| |
− | Łatwo sprawdzamy, że twierdzenie jest prawdziwe dla <math>p = 2</math>. Niech teraz <math>p</math> będzie liczbą pierwszą nieparzystą. Rozważmy wielomiany
| |
− | | |
− | ::<math>W(x) = (x - 1) (x - 2) \cdot \ldots \cdot (x - (p - 1))</math>
| |
| | | |
| oraz | | oraz |
| | | |
− | ::<math>V(x) = x^{p - 1} - 1</math> | + | ::<math>a^n \equiv R_2 (a) \pmod 2</math> |
− | | |
− | Zauważmy, że
| |
− | | |
− | :* stopnie tych wielomianów są równe <math>p - 1</math>
| |
− | :* współczynniki wiodące są równe <math>1</math>
| |
− | :* wyrazy wolne są równe odpowiednio <math>(p - 1) !</math> oraz <math>- 1</math>
| |
− | :* wielomiany mają <math>p - 1</math> rozwiązań modulo <math>p</math>
| |
− | | |
− | Niech
| |
− | | |
− | ::<math>U(x) = W (x) - V (x)</math>
| |
− | | |
− | Zauważmy, że
| |
− | | |
− | :* stopień wielomianu <math>U(x)</math> jest równy <math>p - 2 \geqslant 1</math>, ponieważ wyrazy o najwyższym stopniu uległy redukcji
| |
− | :* wielomian <math>U(x)</math> ma <math>p - 1</math> rozwiązań modulo <math>p</math>, bo dla każdego <math>k \in \{ 1, 2, \ldots, p - 1 \}</math> mamy <math>U(k) = W (k) - V (k) \equiv 0 \pmod{p}</math>
| |
− | | |
− | Z twierdzenia Lagrange'a wiemy, że wielomian <math>U(x)</math> nie może mieć więcej niż <math>p - 2</math> rozwiązań modulo <math>p</math>. Zatem z twierdzenia J14 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}}
| |
− | | |
− | | |
− | | |
− | | |
− | | |
− | == Twierdzenie Fermata ==
| |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J18 (Pierre de Fermat, 1640)</span><br/>
| |
− | Niech <math>a \in \mathbb{Z}</math>. Jeżeli <math>p</math> jest liczbą pierwszą
| |
− | | |
− | :* to liczba <math>a^p - a</math> jest podzielna przez <math>p</math>, czyli <math>a^p \equiv a \pmod p</math>
| |
− | :* i jeśli dodatkowo <math>p \nmid a</math>, to liczba <math>a^{p - 1} - 1</math> jest podzielna przez <math>p</math>, czyli <math>a^{p - 1} \equiv 1 \pmod p</math>
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | '''Punkt 1.'''
| |
− | | |
− | Zauważmy, że<br/>
| |
− | a) twierdzenie jest prawdziwe dla <math>a = 0</math><br/>
| |
− | b) w przypadku, gdy <math>p = 2</math> wyrażenie <math>a^p - a = a^2 - a = a (a - 1)</math> jest podzielne przez <math>2</math>, bo jedna z liczb <math>a - 1</math> i <math>a</math> jest liczbą parzystą<br/>
| |
− | c) w przypadku, gdy <math>p</math> jest liczbą pierwszą nieparzystą i twierdzenie jest prawdziwe dla <math>a \geqslant 1</math>, to jest też prawdziwe dla <math>- a</math>, bo
| |
− | ::<math>(- a)^p - (- a) = (- 1)^p a^p + a = - a^p + a = - (a^p - a)</math><br/>
| |
− | | |
− | | |
− | Zatem wystarczy pokazać, że dla ustalonej liczby pierwszej nieparzystej <math>p</math> twierdzenie jest prawdziwe dla każdego <math>a \in \mathbb{Z}_+</math>.
| |
− | | |
− | Indukcja matematyczna. Dla <math>a = 1</math> mamy <math>1^p - 1 = 0</math> zatem liczba pierwsza <math>p</math> jest dzielnikiem rozważanego wyrażenia. Zakładając, że twierdzenie jest prawdziwe dla <math>a</math>, czyli <math>p|a^p - a</math>, otrzymujmy dla <math>a + 1</math>
| |
− | | |
− | ::<math>(a + 1)^p - (a + 1) = \sum_{k = 0}^{p} \binom{p}{k} \cdot a^k - a - 1</math>
| |
− | | |
− | :::::::<math>\;\;\,\, = 1 + \sum_{k = 1}^{p - 1} \binom{p}{k} \cdot a^k + a^p - a - 1</math>
| |
− | | |
− | :::::::<math>\;\;\,\, = a^p - a + \sum^{p - 1}_{k = 1} \binom{p}{k} \cdot a^k</math>
| |
− | | |
− | | |
− | Z założenia indukcyjnego <math>p|a^p - a</math>, zaś <math>\binom{p}{k} = {\small\frac{p!}{k! \cdot (p - k) !}}</math> dla <math>k = 1, 2, \ldots, p - 1</math> jest podzielne przez <math>p</math> (ponieważ <math>p</math> dzieli licznik, ale nie dzieli mianownika). Zatem <math>(a + 1)^p - (a + 1)</math> jest podzielne przez liczbę pierwszą <math>p</math>.
| |
− | | |
− | '''Punkt 2.'''
| |
− | | |
− | Z punktu 1. wiemy, że liczba pierwsza <math>p</math> dzieli <math>a^p - a = a (a^{p - 1} - 1)</math>. Jeżeli <math>p \nmid a</math>, to z lematu Euklidesa (zobacz twierdzenie C72) wynika natychmiast, że <math>p</math> dzieli <math>a^{p - 1} - 1</math>.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | | |
− | | |
− | == Kryterium Eulera ==
| |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Definicja J19</span><br/>
| |
− | Niech <math>p</math> będzie liczbą pierwszą i <math>a \in \mathbb{Z}</math>. Powiemy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>p</math>, jeżeli kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{p}</math>
| |
− | | |
− | ma rozwiązanie, czyli istnieje taka liczba <math>k \in \mathbb{Z}</math>, że <math>p \, | \, (k^2 - a)</math>.
| |
− | | |
− | Powiemy, że liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math>, jeżeli kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{p}</math>
| |
− | | |
− | nie ma rozwiązania.
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J20</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>.
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Zauważmy, że w rozważanym zbiorze liczb <math>\{ 1, 2, \ldots, p - 1 \}</math>, kwadraty liczb <math>k</math> i <math>p - k</math> są takimi samymi liczbami modulo <math>p</math>, co wynika z oczywistej kongruencji
| |
− | | |
− | ::<math>k^2 \equiv (p - k)^2 \pmod{p}</math>
| |
− | | |
− | Pozwala to wypisać pary liczb, których kwadraty są identyczne modulo <math>p</math>
| |
− | | |
− | ::<math>(1, p - 1), (2, p - 2), \ldots, \left( {\small\frac{p - 1}{2}}, p - {\small\frac{p - 1}{2}} \right)</math>
| |
− | | |
− | Ponieważ
| |
− | | |
− | ::<math>p - {\small\frac{p - 1}{2}} = {\small\frac{p + 1}{2}} = {\small\frac{p - 1}{2}} + 1</math>
| |
− | | |
− | to wypisane pary wyczerpują cały zbiór <math>\{ 1, 2, \ldots, p - 1 \}</math>. Co więcej, liczby <math>1^2, 2^2, \ldots, \left( {\small\frac{p - 1}{2}} \right)^2</math> są wszystkie różne modulo <math>p</math>. Istotnie, przypuśćmy, że <math>1 \leqslant i, j \leqslant {\small\frac{p - 1}{2}}</math> oraz <math>i \neq j</math>, a jednocześnie <math>i^2 \equiv j^2 \pmod{p}</math>. Gdyby tak było, to mielibyśmy
| |
− | | |
− | ::<math>(i - j) (i + j) \equiv 0 \pmod{p}</math>
| |
− | | |
− | Łatwo zauważamy, że jest to niemożliwe, bo żaden z czynników nie jest podzielny przez <math>p</math>, co wynika z prostych oszacowań
| |
− | | |
− | ::<math>1 \leqslant | i - j | \leqslant i + j < p - 1</math>
| |
− | | |
− | ::<math>2 < i + j < p - 1</math>
| |
− | | |
− | | |
− | Ponieważ (z definicji) liczba <math>a</math> jest liczbą kwadratową modulo <math>p</math>, jeżeli kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{p}</math>
| |
− | | |
− | ma rozwiązanie, to liczba kwadratowa modulo <math>p</math> musi przystawać do pewnego kwadratu modulo <math>p</math>.
| |
− | | |
− | Wynika stąd, że różnych liczb kwadratowych modulo <math>p</math> jest tyle samo, co kwadratów <math>1^2, 2^2, \ldots, \left( {\small\frac{p - 1}{2}} \right)^2</math>. Czyli jest ich dokładnie <math>{\small\frac{p - 1}{2}}</math>. Pozostałe liczby w zbiorze <math>\{ 1, 2, \ldots, p - 1 \}</math> to liczby niekwadratowe modulo <math>p</math> i jest ich również <math>{\small\frac{p - 1}{2}}</math>. Co należało pokazać.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J21 (kryterium Eulera, 1748)</span><br/>
| |
− | Niech <math>p</math> będzie liczbą pierwszą nieparzystą i <math>p \nmid a</math>. Modulo <math>p</math> mamy
| |
− | | |
− | ::{| border="0"
| |
− | |-style=height:2.5em
| |
− | | ● || liczba <math>a</math> jest liczbą kwadratową modulo <math>p</math> wtedy i tylko wtedy, gdy <math>a^{(p - 1) / 2} \equiv 1 \pmod{p}</math>
| |
− | |-style=height:2.5em
| |
− | | ● || liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math> wtedy i tylko wtedy, gdy <math>a^{(p - 1) / 2} \equiv - 1 \pmod{p}</math>
| |
− | |}
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | | |
− | '''Punkt 1.'''
| |
− | | |
− | Niech <math>Q \subset \{ 1, 2, \ldots, p - 1 \}</math> będzie zbiorem wszystkich liczb kwadratowych modulo <math>p</math>, a <math>S \subset \{ 1, 2, \ldots, p - 1 \}</math> będzie zbiorem wszystkich rozwiązań kongruencji
| |
− | | |
− | ::<math>x^{(p - 1) / 2} \equiv 1 \pmod{p}</math>
| |
− | | |
− | Zauważmy, że
| |
− | | |
− | ::{| border=1 style="border-collapse: collapse;"
| |
− | |-style=height:2.5em
| |
− | | '''A''' || <math>| Q | = {\small\frac{p - 1}{2}}</math> || zobacz J20
| |
− | |-style=height:2.5em
| |
− | | '''B''' || <math>| S | \leqslant {\small\frac{p - 1}{2}}</math> || zobacz twierdzenie Lagrange'a J13
| |
− | |-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>
| |
− | |-style=height:2.5em
| |
− | | '''D''' || <math>Q \subseteq S</math> || z punktu '''C''' wynika, że '''każdy''' element zbioru <math>Q</math> należy do zbioru <math>S</math>
| |
− | |}
| |
− | | |
| | | |
− | Łącząc rezultaty z tabeli, otrzymujemy
| + | dla dowolnej liczby całkowitej dodatniej <math>n</math>. Zatem modulo <math>2</math> jest |
| | | |
− | ::<math>{\small\frac{p - 1}{2}} = | Q | \leqslant | S | \leqslant {\small\frac{p - 1}{2}}</math> | + | ::<math>{\small\frac{a^p - 1}{a - 1}} \equiv R_2 (a) \cdot (p - 1) + 1 \equiv 1 \pmod 2</math> |
| | | |
− | Skąd łatwo widzimy, że
| + | ::<math>{\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2</math> |
| | | |
− | ::<math>| Q | = | S | = {\small\frac{p - 1}{2}}</math>
| + | Co oznacza, że |
| | | |
− | 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 J22). Prostą konsekwencją równości zbiorów <math>Q</math> i <math>S</math> jest stwierdzenie
| + | ::<math>m = {\small\frac{a^p - 1}{a - 1}} \cdot {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2</math> |
| | | |
− | ::{| border=0 style="background: #EEEEEE;"
| + | Czyli <math>m</math> jest '''złożoną liczbą nieparzystą'''. Pozostaje pokazać, że <math>a^{m - 1} \equiv 1 \pmod m</math>. |
− | |-style=height:2.0em
| |
− | | liczba <math>a</math> jest liczbą kwadratową modulo <math>p</math> wtedy i tylko wtedy, gdy <math>a^{(p - 1) / 2} \equiv 1 \pmod{p}</math>
| |
− | |}
| |
| | | |
− | Co kończy dowód punktu pierwszego.
| |
| | | |
− | '''Punkt 2.'''
| + | Z twierdzenia Fermata wiemy, że |
| | | |
− | Z udowodnionego już punktu pierwszego wynika<ref name="logic1"/>, że
| + | ::<math>a^p - 1 \equiv a - 1 \pmod p</math> |
| | | |
− | ::{| border=0 style="background: #EEEEEE;"
| + | Ponieważ <math>(a - 1) | (a^p - 1)</math>, to możemy napisać |
− | |-style=height:2.0em
| |
− | | liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math> wtedy i tylko wtedy, gdy <math>a^{(p - 1) / 2} \not\equiv 1 \pmod{p}</math>
| |
− | |}
| |
| | | |
− | Z twierdzenia Fermata
| + | ::<math>(a - 1) \cdot \left( {\small\frac{a^p - 1}{a - 1}} - 1 \right) \equiv 0 \pmod p</math> |
| | | |
− | ::<math>a^{p - 1} - 1 = (a^{(p - 1) / 2} - 1) \cdot (a^{(p - 1) / 2} + 1) \equiv 0 \pmod{p}</math>
| + | Z założenia <math>p \nmid (a - 1)</math>, zatem liczba pierwsza <math>p</math> musi dzielić <math>{\small\frac{a^p - 1}{a - 1}} - 1</math> i otrzymujemy |
| | | |
− | wynika natychmiast, że jeżeli <math>a^{(p - 1) / 2} - 1 \not\equiv 0 \pmod{p}</math>, to musi być
| + | ::<math>{\small\frac{a^p - 1}{a - 1}} \equiv 1 \pmod p</math> |
| | | |
− | ::<math>a^{(p - 1) / 2} + 1 \equiv 0 \pmod{p}</math>
| + | Postępując analogicznie jak wyżej, dostajemy |
| | | |
− | Fakt ten pozwala sformułować uzyskaną równoważność bardziej precyzyjnie
| + | ::<math>a^p + 1 \equiv a + 1 \pmod p</math> |
| | | |
− | ::{| border=0 style="background: #EEEEEE;" | + | ::<math>(a + 1) \cdot \left( {\small\frac{a^p + 1}{a + 1}} - 1 \right) \equiv 0 \pmod p</math> |
− | |-style=height:2.0em
| |
− | | liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math> wtedy i tylko wtedy, gdy <math>a^{(p - 1) / 2} \equiv - 1 \pmod{p}</math>
| |
− | |}
| |
| | | |
− | Co należało pokazać.<br/>
| + | ::<math>{\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod p</math> |
− | □
| |
− | {{\Spoiler}} | |
| | | |
| + | Wynika stąd, że <math>m \equiv 1 \pmod p</math>. |
| | | |
| + | Zbierając mamy <math>2| (m - 1)</math> i <math>p| (m - 1)</math>, zatem <math>2 p| (m - 1)</math>, czyli |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Zadanie J22</span><br/>
| + | ::<math>m = {\small\frac{a^{2 p} - 1}{a^2 - 1}} \equiv 1 \pmod{2 p}</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>.
| |
| | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
| + | Oznacza to, że <math>m = 1 + 2 k p</math> dla pewnej liczby całkowitej <math>k > 0</math>. |
− | Ponieważ zbiór <math>A</math> jest podzbiorem zbioru <math>B</math>, to zbiór <math>B</math> można przedstawić w postaci sumy zbiorów <math>A</math> i <math>C</math> takich, że żaden element zbioru <math>C</math> nie jest elementem zbioru <math>A</math>. Zatem
| |
| | | |
− | ::<math>B = A \cup C \qquad \text{i} \qquad A \cap C = \varnothing</math>
| |
| | | |
− | Ponieważ z założenia zbiory <math>A</math> i <math>C</math> są rozłączne, to wiemy, że
| + | Zauważmy teraz, że z definicji liczby <math>m</math> mamy <math>(a^2 - 1) m = a^{2 p} - 1</math>. Rozpatrując to równanie modulo <math>m</math>, otrzymujemy |
| | | |
− | ::<math>| A \cup C | = | A | + | C |</math> | + | ::<math>a^{2 p} \equiv 1 \pmod m</math> |
| | | |
− | Czyli
| + | Zatem modulo <math>m</math> jest |
| | | |
− | ::<math>| B | = | A \cup C | = | A | + | C |</math> | + | ::<math>a^{m - 1} = a^{2 k p} = (a^{2 p})^k \equiv 1^k \equiv 1 \pmod m</math> |
| | | |
− | Skąd wynika, że <math>| C | = 0</math>, zatem zbiór <math>C</math> jest zbiorem pustym i otrzymujemy natychmiast <math>B = A</math>. Co należało pokazać.
| + | Ponieważ dowolna liczba pierwsza <math>p > a^2 - 1</math> nie dzieli <math>a^2 - 1</math>, to dla każdego <math>a \geqslant 2</math> istnieje nieskończenie wiele liczb, które są PSP(<math>a</math>). Co należało pokazać.<br/> |
− | | |
− | | |
− | <span style="border-bottom-style: double;">Uwaga (przypadek zbiorów skończonych)</span><br/>
| |
− | Najczęściej prawdziwe jest jedynie oszacowanie <math>| 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>| A |</math> i <math>| C |</math>, zatem od sumy <math>| A | + | C |</math> musimy odjąć liczbę elementów iloczynu zbiorów <math>| A |</math> i <math>| C |</math>. Co daje ogólny wzór<ref name="sumazbiorow"/>
| |
− | | |
− | ::<math>| A \cup C | = | A | + | C | - | A \cap C |</math><br/>
| |
| □ | | □ |
| {{\Spoiler}} | | {{\Spoiler}} |
Linia 750: |
Linia 167: |
| | | |
| | | |
| + | <span style="font-size: 110%; font-weight: bold;">Przykład K6</span><br/> |
| + | Z dowodu twierdzenia K5 wynika, że jeżeli liczba <math>p</math> jest liczbą pierwszą nieparzystą i <math>p \nmid (a^2 - 1)</math>, to liczba <math>m = {\small\frac{a^{2 p} - 1}{a^2 - 1}}</math> jest PSP(<math>a</math>). Poniżej przedstawiamy przykłady takich liczb, dla kolejnych liczb pierwszych nieparzystych <math>p</math> takich, że <math>p \nmid (a^2 - 1)</math>. |
| | | |
| + | <span style="font-size: 90%; color:black;">'''for'''(a=2, 5, s=1; d=a^2-1; '''forprime'''(p=3, 50, '''if'''( d%p == 0, '''next'''() ); m=(a^(2*p)-1)/d; '''print'''("a= ", a, " m= ", m); s++; '''if'''( s>6, '''break'''() ) )) </span> |
| | | |
− | | + | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: right; margin-right: auto;" |
− | | + | ! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> |
− | | |
− | | |
− | | |
− | == Symbol Legendre'a ==
| |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Definicja J23</span><br/>
| |
− | Niech <math>p</math> będzie liczbą pierwszą nieparzystą i <math>a \in \mathbb{Z}</math>. Symbolem Legendre'a<ref name="legendre1"/> nazywamy funkcję <math>a</math> i <math>p</math> zdefiniowaną następująco
| |
− | | |
− | ::<math>\left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} =
| |
− | \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>
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J24</span><br/>
| |
− | Powyższa definicja pozwala nam zapisać kryterium Eulera w zwartej formie, która obejmuje również przypadek, gdy <math>p \, | \, a</math>
| |
− | | |
− | ::<math>a^{(p - 1) / 2} \equiv \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \pmod{p}</math>
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J25*</span><br/>
| |
− | Niech <math>a, b \in \mathbb{Z}</math> oraz <math>p, q</math> będą nieparzystymi liczbami pierwszymi. Symbol Legendre'a ma następujące właściwości
| |
− | | |
− | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: left; margin-right: auto;"
| |
− | |-
| |
− | | 1. || <math>\left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \,\, = \,\, 0 \quad \Longleftrightarrow \quad \gcd (a, p) > 1</math>
| |
| |- | | |- |
− | | 2. || <math>a \equiv b \pmod p \quad \Longrightarrow \quad \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} = \left( {\small\frac{b}{p}} \right)_{\small{\!\! L}}</math> | + | | || <math>341</math> || <math>91</math> || <math>17895697</math> || <math>406901</math> |
| |- | | |- |
− | | 3. || <math>\left( {\small\frac{a b}{p}} \right)_{\small{\!\! L}} \,\, = \,\, \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \cdot \left( {\small\frac{b}{p}} \right)_{\small{\!\! L}}</math> | + | | || <math>5461</math> || <math>7381</math> || <math>1172812402961</math> || <math>254313151</math> |
| |- | | |- |
− | | 4. || <math>a^{(p - 1) / 2} \equiv \left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} \pmod{p}</math> | + | | || <math>1398101</math> || <math>597871</math> || <math>300239975158033</math> || <math>99341074625651</math> |
| |- | | |- |
− | | 5. || <math>\left( {\small\frac{1}{p}} \right)_{\small{\!\! L}} \,\, = \,\, 1</math> | + | | || <math>22369621</math> || <math>3922632451</math> || <math>19676527011956855057</math> || <math>62088171641031901</math> |
| |- | | |- |
− | | 6. || <math>\left( {\small\frac{- 1}{p}} \right)_{\small{\!\! L}} \,\, = \,\, (- 1)^{\tfrac{p - 1}{2}} \,\, = \,\, | + | | || <math>5726623061</math> || <math>317733228541</math> || <math>5037190915060954894609</math> || <math>24253192047278086344401</math> |
− | \begin{cases}
| |
− | \;\;\: 1 & \text{gdy } p \equiv 1 \pmod{4} \\
| |
− | - 1 & \text{gdy } p \equiv 3 \pmod{4}
| |
− | \end{cases}</math>
| |
| |- | | |- |
− | | 7. || <math>\left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} \,\, = \,\, (- 1)^{\tfrac{p^2 - 1}{8}} \,\, = \,\, | + | | || <math>91625968981</math> || <math>2084647712458321</math> || <math>330117343809434739973099793</math> || <math>15158245029548803965250651</math> |
− | \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>\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>\left( {\small\frac{p}{q}} \right)_{\small{\!\! L}} \,\, = \,\, \left( {\small\frac{q}{p}} \right)_{\small{\!\! L}} \cdot (-1)^{\tfrac{q - 1}{2} \cdot \tfrac{p - 1}{2}} \,\, = \,\, \left( {\small\frac{q}{p}} \right)_{\small{\!\! L}} \cdot
| |
− | \begin{cases}
| |
− | \;\;\: 1 & \text{gdy } p \equiv 1 \pmod{4} \;\;\; \text{lub} \;\;\; q \equiv 1 \pmod{4} \\
| |
− | - 1 & \text{gdy } p \equiv q \equiv 3 \pmod{4}
| |
− | \end{cases}</math>
| |
| |} | | |} |
| | | |
| | | |
| | | |
| + | <span style="font-size: 110%; font-weight: bold;">Uwaga K7</span><br/> |
| + | Wykorzystując funkcję potęgowania modulo, możemy napisać prosty program do testowania pierwszości liczb w oparciu o twierdzenie Fermata. |
| | | |
| + | <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">PSP</span>(m, a) = |
| + | { |
| + | '''if'''( modPower(a, m-1, m) == 1, '''return'''(1), '''return'''(0) ); |
| + | }</span> |
| | | |
| | | |
| | | |
| + | <span style="font-size: 110%; font-weight: bold;">Przykład K8</span><br/> |
| + | Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Fermata dla podstaw <math>a</math> od <math>2</math> do <math>15</math> |
| | | |
− | == Symbol Jacobiego ==
| + | <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=1; '''forstep'''(m=1, 2000, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">PSP</span>(m, a) && !'''isprime'''(m), '''print'''("a=", a, " m=", m); s++ ); '''if'''( s>5, '''break'''() ) ))</span> |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Definicja J26</span><br/> | |
− | Niech liczby <math>a \in \mathbb{Z}</math> i <math>m \in \mathbb{Z}_+</math> będą względnie pierwsze. Powiemy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>m</math>, jeżeli kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{m}</math>
| |
− | | |
− | ma rozwiązanie, czyli istnieje taka liczba <math>k \in \mathbb{Z}</math>, że <math>m \, | \, (k^2 - a)</math>.
| |
− | | |
− | Powiemy, że liczba <math>a</math> jest liczbą niekwadratową modulo <math>m</math>, jeżeli kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{m}</math>
| |
− | | |
− | nie ma rozwiązania.
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Zadanie J27</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>.
| |
− | | |
− | {{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 J11.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Definicja J28</span><br/>
| |
− | Symbol Jacobiego<ref name="jacobi1"/> <math>\left( {\small\frac{a}{n}} \right)_{\small{\!\! J}}</math> jest uogólnieniem symbolu Legendre'a <math>\left( {\small\frac{a}{p}} \right)_{\small{\!\! L}}</math> dla dodatnich liczb nieparzystych.
| |
− | Niech <math>n = \prod_i p_i^{\alpha_i}</math> będzie rozkładem liczby <math>n</math> na czynniki pierwsze, wtedy
| |
| | | |
− | ::<math>\left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} = \prod_i \left( {\small\frac{a}{p_i}} \right)_{\small{\!\! L}}^{\!\! \alpha_i}</math> | + | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: right; margin-right: auto;" |
− | | + | ! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math> |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J29</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>.
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J30*</span><br/> | |
− | Niech <math>a, b \in \mathbb{Z}</math> oraz <math>m, n \in \mathbb{Z}_+</math> i <math>m, n</math> będą liczbami nieparzystymi. Symbol Jacobiego ma następujące właściwości
| |
− | | |
− | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: left; margin-right: auto;"
| |
− | |-
| |
− | | 1. || <math>\left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} \,\, = \,\, 0 \quad \Longleftrightarrow \quad \gcd (a, n) > 1</math>
| |
− | |-
| |
− | | 2. || <math>a \equiv b \pmod n \quad \Longrightarrow \quad \left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} = \left( {\small\frac{b}{n}} \right)_{\small{\!\! J}}</math>
| |
− | |-
| |
− | | 3. || <math>\left( {\small\frac{a b}{n}} \right)_{\small{\!\! J}} \,\, = \,\, \left( {\small\frac{a}{n}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{b}{n}} \right)_{\small{\!\! J}}</math>
| |
| |- | | |- |
− | | 4. || <math>\left( {\small\frac{a}{m n}} \right)_{\small{\!\! J}} \,\, = \,\, \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{a}{n}} \right)_{\small{\!\! J}}</math> | + | | || <math>341</math> || <math>91</math> || <math>15</math> || <math>217</math> || <math>35</math> || <math>25</math> || <math>9</math> || <math>91</math> || <math>9</math> || <math>15</math> || <math>65</math> || <math>21</math> || <math>15</math> || <math>341</math> |
| |- | | |- |
− | | 5. || <math>\left( {\small\frac{1}{n}} \right)_{\small{\!\! J}} \,\, = \,\, 1</math> | + | | || <math>561</math> || <math>121</math> || <math>85</math> || <math>561</math> || <math>185</math> || <math>325</math> || <math>21</math> || <math>121</math> || <math>33</math> || <math>133</math> || <math>91</math> || <math>85</math> || <math>39</math> || <math>1477</math> |
| |- | | |- |
− | | 6. || <math>\left( {\small\frac{- 1}{n}} \right)_{\small{\!\! J}} \,\, = \,\, (- 1)^{\tfrac{n - 1}{2}} \,\, = \,\, | + | | || <math>645</math> || <math>671</math> || <math>91</math> || <math>781</math> || <math>217</math> || <math>561</math> || <math>45</math> || <math>205</math> || <math>91</math> || <math>259</math> || <math>133</math> || <math>105</math> || <math>65</math> || <math>1541</math> |
− | \begin{cases}
| |
− | \;\;\: 1 & \text{gdy } n \equiv 1 \pmod{4} \\
| |
− | - 1 & \text{gdy } n \equiv 3 \pmod{4}
| |
− | \end{cases}</math>
| |
| |- | | |- |
− | | 7. || <math>\left( {\small\frac{2}{n}} \right)_{\small{\!\! J}} \,\, = \,\, (- 1)^{\tfrac{n^2 - 1}{8}} \,\, = \,\, | + | | || <math>1105</math> || <math>703</math> || <math>341</math> || <math>1541</math> || <math>301</math> || <math>703</math> || <math>63</math> || <math>511</math> || <math>99</math> || <math>305</math> || <math>143</math> || <math>231</math> || <math>195</math> || <math>1687</math> |
− | \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>\left( {\small\frac{- 2}{n}} \right)_{\small{\!\! J}} \,\, = \,\, (- 1)^{\tfrac{(n - 1)(n - 3)}{8}} \,\, = \,\, | + | | || <math>1387</math> || <math>949</math> || <math>435</math> || <math>1729</math> || <math>481</math> || <math>817</math> || <math>65</math> || <math>671</math> || <math>259</math> || <math>481</math> || <math>145</math> || <math>357</math> || <math>481</math> || <math>1729</math> |
− | \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>\left( {\small\frac{m}{n}} \right)_{\small{\!\! J}} \,\, = \,\, \left( {\small\frac{n}{m}} \right)_{\small{\!\! J}} \cdot (-1)^{\tfrac{n - 1}{2} \cdot \tfrac{m - 1}{2}} \,\, = \,\, \left( {\small\frac{n}{m}} \right)_{\small{\!\! J}} \cdot | |
− | \begin{cases}
| |
− | \;\;\: 1 & \text{gdy } m \equiv 1 \pmod{4} \;\;\; \text{lub} \;\;\; n \equiv 1 \pmod{4} \\
| |
− | - 1 & \text{gdy } m \equiv n \equiv 3 \pmod{4}
| |
− | \end{cases}</math>
| |
| |} | | |} |
| | | |
| | | |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J31</span><br/> | + | <span style="font-size: 110%; font-weight: bold;">Przykład K9</span><br/> |
− | Zauważmy, że poza zmienionym założeniem tabela z powyższego twierdzenia i tabela z twierdzenia J25 różnią się jedynie punktem czwartym. Oczywiście jest to tylko podobieństwo formalne – symbol Legendre'a i symbol Jacobiego są różnymi funkcjami.
| + | Tabela pokazuje ilość liczb pseudopierwszych Fermata dla podstaw <math>a</math> od <math>2</math> do <math>15</math> |
| | | |
| + | <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=0; '''forstep'''(k=1, 10^6, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">PSP</span>(k, a) && !'''isprime'''(k), s++ )); '''print'''("a= ", a, " ", s))</span> |
| | | |
| + | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: right; margin-right: auto;" |
| + | ! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math> |
| + | |- |
| + | | #PSP(<math>a</math>) <math> < 10^6</math> || <math>245</math> || <math>243</math> || <math>464</math> || <math>238</math> || <math>301</math> || <math>229</math> || <math>678</math> || <math>362</math> || <math>271</math> || <math>236</math> || <math>378</math> || <math>257</math> || <math>283</math> || <math>203</math> |
| + | |- |
| + | | #PSP(<math>a</math>) <math> < 10^7</math> || <math>750</math> || <math>749</math> || <math>1347</math> || <math>726</math> || <math>895</math> || <math>651</math> || <math>1993</math> || <math>1150</math> || <math>766</math> || <math>672</math> || <math>1091</math> || <math>719</math> || <math>817</math> || <math>614</math> |
| + | |- |
| + | | #PSP(<math>a</math>) <math> < 10^8</math> || <math>2057</math> || <math>2131</math> || <math>3805</math> || <math>1910</math> || <math>2314</math> || <math>1782</math> || <math>5407</math> || <math>3214</math> || <math>2091</math> || <math>1891</math> || <math>2933</math> || <math>1929</math> || <math>2155</math> || <math>1718</math> |
| + | |- |
| + | | #PSP(<math>a</math>) <math> < 10^9</math> || <math>5597</math> || <math>5767</math> || <math>10173</math> || <math>5146</math> || <math>6204</math> || <math>4923</math> || <math>14629</math> || <math>8670</math> || <math>5599</math> || <math>5020</math> || <math>7781</math> || <math>5082</math> || <math>5848</math> || <math>4665</math> |
| + | |} |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J32</span><br/>
| |
− | Zauważmy, że w przypadku, gdy <math>m</math> jest liczbą nieparzystą
| |
| | | |
− | :* jeżeli <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math>, to <math>a</math> jest liczbą niekwadratową modulo <math>m</math>
| |
− | :* jeżeli <math>a</math> jest liczbą niekwadratową modulo <math>m</math>, to '''nie musi być''' <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math>
| |
− | :* jeżeli <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = + 1</math>, to <math>a</math> '''nie musi być''' liczbą kwadratową modulo <math>m</math>
| |
− | :* jeżeli <math>a</math> jest liczbą kwadratową modulo <math>m</math>, to jest <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = + 1</math>
| |
| | | |
− | Przykład: jeżeli <math>\gcd (a, m) = 1</math>, to <math>\left( {\small\frac{a}{m^2}} \right)_{\small{\!\! J}} = \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}^2 = + 1</math>, ale <math>a</math> może być liczbą niekwadratową modulo <math>m^2</math>.
| + | <span style="font-size: 110%; font-weight: bold;">Uwaga K10</span><br/> |
| + | Można pokazać, że jeżeli <math>m</math> jest liczbą nieparzystą złożoną i istnieje przynajmniej jedna liczba <math>a</math> względnie pierwsza z <math>m</math>, taka że |
| | | |
− | Modulo <math>9</math> liczbami niekwadratowymi są: <math>2, 5, 8</math>. Modulo <math>25</math> liczbami niekwadratowymi są: <math>2, 3, 7, 8, 12, 13, 17, 18, 22, 23</math>.
| + | ::<math>a^{m - 1} \not\equiv 1 \pmod m</math> |
| | | |
| + | to dla co najmniej połowy liczb <math>b \in [1, m - 1]</math> względnie pierwszych z <math>m</math> jest |
| | | |
| + | ::<math>b^{m - 1} \not\equiv 1 \pmod m</math> |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J33</span><br/> | + | Zatem przeprowadzając test Fermata, możemy z prawdopodobieństwem nie mniejszym niż <math>\tfrac{1}{2}</math> twierdzić, że liczba, która przeszła test, jest liczbą pierwszą. Wykonując test <math>k</math> razy dla <math>k</math> różnych podstaw z przedziału <math>[1, m - 1]</math> możemy z prawdopodobieństwem większym niż <math>1 - \left( \tfrac{1}{2} \right)^k</math> twierdzić, że badana liczba <math>m</math> jest pierwsza. |
− | Wszystkie liczby kwadratowe i niekwadratowe modulo <math>m</math> można łatwo znaleźć, wykorzystując prosty program:
| |
| | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż kod|Hide=Ukryj kod}}
| + | Niestety, istnieją liczby złożone <math>m</math> takie, że |
− | <span style="font-size: 90%; color:black;">QRandQNR(m) =
| |
− | {
| |
− | '''local'''(k, S, V);
| |
− | S = [];
| |
− | V = [];
| |
− | '''for'''(k = 1, m - 1, '''if'''( '''gcd'''(k, m) > 1, '''next'''() ); S = '''concat'''(S, k));
| |
− | S = '''Set'''(S); \\ zbiór liczb względnie pierwszych z m
| |
− | '''for'''(k = 1, m - 1, '''if'''( '''gcd'''(k, m) > 1, '''next'''() ); V = '''concat'''(V, k^2 % m));
| |
− | V = '''Set'''(V); \\ zbiór liczb kwadratowych modulo m
| |
− | '''print'''("QR: ", V);
| |
− | '''print'''("QNR: ", '''setminus'''(S, V)); \\ różnica zbiorów S i V
| |
− | }</span>
| |
− | <br/>
| |
− | {{\Spoiler}}
| |
| | | |
| + | ::<math>a^{m - 1} \equiv 1 \pmod m</math> |
| | | |
| + | dla każdego <math>a</math> względnie pierwszego z <math>m</math>. Liczby te nazywamy liczbami Carmichaela i jest ich nieskończenie wiele. Pokazano, że dla dostatecznie dużych <math>x</math> ilość liczb Carmichaela mniejszych od <math>x</math> przekracza <math>x^{1/3}</math><ref name="Carmichael1"/><ref name="Carmichael2"/><ref name="Carmichael3"/>. Test Fermata jest zatem zbyt zawodny, aby można było go stosować. |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Zadanie J34</span><br/>
| |
− | Pokazać, że
| |
| | | |
− | ::<math>\left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 12}{m}} \right)_{\small{\!\! J}} =
| |
− | \begin{cases}
| |
− | \;\;\: 1 & \text{gdy } m = 6 k + 1 \\
| |
− | \;\;\: 0 & \text{gdy } m = 6 k + 3 \\
| |
− | - 1 & \text{gdy } m = 6 k + 5
| |
− | \end{cases}</math>
| |
| | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
| + | <span style="font-size: 110%; font-weight: bold;">Przykład K11</span><br/> |
− | Zauważmy, że
| + | Oto wszystkie liczby Carmichaela mniejsze od <math>100 000</math> |
| | | |
− | ::<math>\left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 1}{m}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{3}{m}} \right)_{\small{\!\! J}}</math> | + | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: left; margin-right: auto;" |
| + | | <math>561=3⋅11⋅17</math> || <math>1105=5⋅13⋅17</math> || <math>1729=7⋅13⋅19</math> || <math>2465=5⋅17⋅29</math> |
| + | |- |
| + | | <math>2821=7⋅13⋅31</math> || <math>6601=7⋅23⋅41</math> || <math>8911=7⋅19⋅67</math> || <math>10585=5⋅29⋅73</math> |
| + | |- |
| + | | <math>15841=7⋅31⋅73</math> || <math>29341=13⋅37⋅61</math> || <math>41041=7⋅11⋅13⋅41</math> || <math>46657=13⋅37⋅97</math> |
| + | |- |
| + | | <math>52633=7⋅73⋅103</math> || <math>62745=3⋅5⋅47⋅89</math> || <math>63973=7⋅13⋅19⋅37</math> || <math>75361=11⋅13⋅17⋅31</math> |
| + | |} |
| | | |
− | ::::<math>\; = (- 1)^{\tfrac{m - 1}{2}} \cdot (- 1)^{\tfrac{m - 1}{2} \cdot \tfrac{3 - 1}{2}} \cdot \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}}</math>
| |
| | | |
− | ::::<math>\; = (- 1)^{m - 1} \cdot \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}}</math>
| |
| | | |
− | ::::<math>\; = \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}}</math>
| |
| | | |
− | bo <math>m</math> jest liczbą nieparzystą.
| |
| | | |
− | Rozważmy liczby nieparzyste <math>m</math> postaci <math>6 k + r</math>, gdzie <math>r = 1, 3, 5</math>. Mamy
| + | == Test Millera-Rabina == |
| | | |
− | ::<math>\left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{m}{3}} \right)_{\small{\!\! J}}</math>
| + | Rozpoczniemy od udowodnienia prostego twierdzenia |
| | | |
− | ::::<math>\; = \left( {\small\frac{6 k + r}{3}} \right)_{\small{\!\! J}}</math>
| + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie K12</span><br/> |
− | | + | Jeśli <math>m</math> jest liczbą pierwszą nieparzystą i <math>x^2 \equiv 1 \pmod m</math>, to albo <math>x \equiv - 1 \pmod m</math>, albo <math>x \equiv 1 \pmod m</math>. |
− | ::::<math>\; = \left( {\small\frac{r}{3}} \right)_{\small{\!\! J}}</math>
| |
− | | |
− | ::::<math>\; =
| |
− | \begin{cases}
| |
− | \;\;\: 1 & \text{gdy } r = 1 \\
| |
− | \;\;\: 0 & \text{gdy } r = 3 \\
| |
− | - 1 & \text{gdy } r = 5
| |
− | \end{cases}</math>
| |
− | | |
− | bo odpowiednio dla <math>r = 1, 3, 5</math> jest
| |
− | | |
− | ::<math>\left( {\small\frac{1}{3}} \right)_{\small{\!\! J}} = 1</math>
| |
− | | |
− | ::<math>\left( {\small\frac{3}{3}} \right)_{\small{\!\! J}} = 0</math>
| |
− | | |
− | ::<math>\left( {\small\frac{5}{3}} \right)_{\small{\!\! J}} = \left( {\small\frac{2}{3}} \right)_{\small{\!\! J}} = (- 1)^{\tfrac{9 - 1}{8}} = - 1</math>
| |
− | | |
− | Łatwo zauważamy, że
| |
− | | |
− | ::<math>\left( {\small\frac{- 12}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 3 \cdot 2^2}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}} \cdot \left( {\small\frac{2}{m}} \right)_{\small{\!\! J}}^{\! 2} = \left( {\small\frac{- 3}{m}} \right)_{\small{\!\! J}}</math>
| |
− | | |
− | Co należało pokazać.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Zadanie J35</span><br/> | |
− | Pokazać, że
| |
− | | |
− | ::<math>\left( {\small\frac{3}{m}} \right)_{\small{\!\! J}} =
| |
− | \begin{cases}
| |
− | \;\;\: 1 & \text{gdy } m = 12 k \pm 1 \\
| |
− | \;\;\: 0 & \text{gdy } m = 12 k \pm 3 \\
| |
− | - 1 & \text{gdy } m = 12 k \pm 5
| |
− | \end{cases}</math>
| |
− | | |
− | | |
− | ::<math>\left( {\small\frac{- 4}{m}} \right)_{\small{\!\! J}} =
| |
− | \begin{cases}
| |
− | \;\;\: 1 & \text{gdy } m = 4 k + 1 \\
| |
− | - 1 & \text{gdy } m = 4 k + 3
| |
− | \end{cases}</math>
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
| |
− | | |
− | ::<math>\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>\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>\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>\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>
| |
− | <br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J36</span><br/>
| |
− | Wykorzystując podane w twierdzeniu J30 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) =
| |
− | {
| |
− | '''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)
| |
− | }</span>
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J37</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.
| |
− | | |
− | W przyszłości symbol Legendre'a / Jacobiego będziemy zapisywali w formie uproszczonej <math>(a \, | \, m)</math> i nie będziemy rozróżniali tych symboli. Interpretacja zapisu jest prosta:
| |
− | | |
− | :* jeżeli '''wiemy''', że <math>m</math> jest liczbą pierwszą, to symbol <math>(a \, | \, m)</math> jest symbolem Legendre'a
| |
− | :* jeżeli '''wiemy''', że <math>m</math> jest liczbą złożoną, to symbol <math>(a \, | \, m)</math> jest symbolem Jacobiego
| |
− | :* jeżeli '''nie wiemy''', czy <math>m</math> jest liczbą pierwszą, czy złożoną, to symbol <math>(a \, | \, m)</math> jest symbolem Jacobiego
| |
− | | |
− | | |
− | | |
− | | |
− | | |
− | == Rozwiązywanie kongruencji <math>x^2 \equiv a \pmod{m}</math> ==
| |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J38</span><br/>
| |
− | Niech <math>p</math> będzie liczbą pierwszą nieparzystą, zaś <math>a</math> liczbą całkowitą taką, że <math>\gcd (a, p) = 1</math>. Kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{p^n}</math>
| |
− | | |
− | ma rozwiązanie wtedy i tylko wtedy, gdy kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{p}</math>
| |
− | | |
− | ma rozwiązanie.
| |
| | | |
| {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} |
| + | Z założenia |
| | | |
− | <math>\Large{\Longrightarrow}</math> | + | ::<math>x^2 \equiv 1 \pmod m</math> |
| | | |
− | Z założenia kongruencja <math>x^2 \equiv a \pmod{p^n}</math> ma rozwiązanie. Zatem istnieje taka liczba <math>r \in \mathbb{Z}</math>, że
| + | Zatem <math>m | (x^2 - 1)</math>, czyli <math>m | (x - 1) (x + 1)</math>. Ponieważ z założenia <math>m</math> jest liczbą pierwszą nieparzystą, to <math>m</math> dzieli dokładnie jedną z liczb <math>x - 1</math> i <math>x + 1</math>. Istotnie, gdyby <math>m | (x - 1)</math> <math>\text{i} \;\, m | (x + 1)</math>, to <math>m</math> dzieliłaby również ich różnicę równą <math>2</math>, co jest niemożliwe w przypadku gdy <math>m</math> jest liczbą pierwszą nieparzystą.<br/> |
− | | |
− | ::<math>r^2 \equiv a \pmod{p^n}</math>
| |
− | | |
− | Ponieważ <math>p^n \, | \, (r^2 - a)</math>, to tym bardziej <math>p \, | \, (r^2 - a)</math>, co oznacza, że prawdziwa jest kongruencja
| |
− | | |
− | ::<math>r^2 \equiv a \pmod{p}</math>
| |
− | | |
− | Skąd wynika natychmiast, że kongruencja <math>x^2 \equiv a \pmod{p}</math> ma rozwiązanie.
| |
− | | |
− | <math>\Large{\Longleftarrow}</math>
| |
− | | |
− | Indukcja matematyczna. Z uczynionego w twierdzeniu założenia wiemy, że kongruencja <math>x^2 \equiv a \pmod{p}</math> ma rozwiązanie. Zatem twierdzenie jest prawdziwe dla <math>n = 1</math>. Załóżmy teraz (założenie indukcyjne), że kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{p^n}</math>
| |
− | | |
− | ma rozwiązanie <math>x \equiv u_n \pmod{p^n}</math> i pokażmy, że twierdzenie jest prawdziwe dla <math>n + 1</math>, czyli że rozwiązanie ma kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{p^{n + 1}}</math>
| |
− | | |
− | Wiemy, że liczba <math>u_n</math> jest określona modulo <math>p^n</math>. Nie tracąc ogólności, możemy założyć, że <math>1 \leqslant u_n < p^n</math>. Wartość <math>u_n</math> może zostać wybrana dowolnie (modulo <math>p^n</math>), ale musi zostać ustalona — wymaga tego precyzja i czytelność dowodu. Zatem
| |
− | | |
− | ::<math>u^2_n - a = k p^n</math>
| |
− | | |
− | Zauważmy, że liczba <math>k</math> jest jednoznacznie określona, bo wartość <math>u_n</math> została ustalona. Ponieważ <math>\gcd (2 u_n, p) = 1</math>, to równanie
| |
− | | |
− | ::<math>2 u_n \cdot s - p \cdot l = - k</math>
| |
− | | |
− | ma rozwiązanie (zobacz C74). Niech liczby <math>s_0</math> i <math>l_0</math> będą rozwiązaniem tego równania. Zatem
| |
− | | |
− | ::<math>2 u_n \cdot s_0 - p \cdot l_0 = - k</math>
| |
− | | |
− | ::<math>2 u_n \cdot s_0 p^n - l_0 \cdot p^{n + 1} = - k p^n</math>
| |
− | | |
− | ::<math>2 u_n \cdot s_0 p^n - l_0 \cdot p^{n + 1} = - ( u^2_n - a )</math>
| |
− | | |
− | ::<math>u^2_n + 2 u_n \cdot s_0 p^n = a + l_0 \cdot p^{n + 1}</math>
| |
− | | |
− | Modulo <math>p^{n + 1}</math> dostajemy
| |
− | | |
− | ::<math>u^2_n + 2 u_n \cdot s_0 p^n \equiv a \pmod{p^{n + 1}}</math>
| |
− | | |
− | ::<math>(u_n + s_0 p^n)^2 \equiv a \pmod{p^{n + 1}}</math>
| |
− | | |
− | bo <math>p^{n + 1} \, | \, p^{2 n}</math>. Zatem liczba <math>u_{n + 1} = u_n + s_0 p^n</math> jest rozwiązaniem kongruencji
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{p^{n + 1}}</math>
| |
− | | |
− | Pokazaliśmy tym samym prawdziwość tezy indukcyjnej, co kończy dowód indukcyjny.<br/>
| |
| □ | | □ |
| {{\Spoiler}} | | {{\Spoiler}} |
Linia 1144: |
Linia 294: |
| | | |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J39</span><br/> | + | Prace Gary'ego Millera<ref name="Miller1"/> i Michaela Rabina<ref name="Rabin1"/> pozwoliły sformułować znacznie silniejszy test. Podstawą tego testu jest następujące twierdzenie |
− | 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>.
| |
| | | |
− | Kongruencja
| + | <span style="font-size: 110%; font-weight: bold;">Twierdzenie K13</span><br/> |
| + | Jeżeli <math>m</math> jest liczbą pierwszą nieparzystą i <math>m - 1 = 2^r d</math>, gdzie <math>d</math> jest liczbą nieparzystą, to dla dowolnego <math>a \in [1, m - 1]</math> jest albo |
| | | |
− | ::<math>x^2 \equiv a \pmod{2}</math> | + | ::<math>a^d \equiv 1 \pmod m</math> |
| | | |
− | ma dokładnie jedno rozwiązanie <math>x \equiv 1 \pmod{2}</math>.
| + | albo |
| | | |
− | Kongruencja
| + | ::<math>a^{2^k d} \equiv - 1 \pmod m</math> |
| | | |
− | ::<math>x^2 \equiv a \pmod{4}</math>
| + | dla pewnego <math>k \in [0, r - 1]</math>. |
− | | |
− | ma dwa rozwiązania, gdy <math>a \equiv 1 \pmod{4}</math>. Rozwiązaniami są: <math>x \equiv 1, 3 \pmod{4}</math>. W przypadku, gdy <math>a \equiv 3 \pmod{4}</math> kongruencja nie ma rozwiązań.
| |
− | | |
− | Kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{8}</math>
| |
− | | |
− | ma cztery rozwiązania, gdy <math>a \equiv 1 \pmod{8}</math>. Rozwiązaniami są: <math>x \equiv 1, 3, 5, 7 \pmod{8}</math>. W przypadku, gdy <math>a \equiv 3, 5, 7 \pmod{8}</math> kongruencja nie ma rozwiązań.
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J40</span><br/>
| |
− | Niech <math>n \geqslant 3</math> i <math>a</math> będzie liczbą nieparzystą. Kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{2^n}</math>
| |
− | | |
− | ma rozwiązanie wtedy i tylko wtedy, gdy kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{8}</math>
| |
− | | |
− | ma rozwiązanie.
| |
| | | |
| {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} | | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}} |
| + | Rozważmy ciąg <math>r + 1</math> liczb zdefiniowanych następująco |
| | | |
− | <math>\Large{\Longrightarrow}</math> | + | ::<math>\begin{array}{l} |
− | | + | u_0 = a^d\\ |
− | Z założenia kongruencja <math>x^2 \equiv a \pmod{2^n}</math> ma rozwiązanie, zatem istnieje taka liczba <math>r \in \mathbb{Z}</math>, że
| + | u_1 = a^{2 d} = (a^d)^2\\ |
− | | + | u_2 = a^{2^2 d} = (a^{2 d})^2\\ |
− | ::<math>r^2 \equiv a \pmod{2^n}</math>
| + | \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots\\ |
− | | + | u_{r - 1} = a^{2^{r - 1} d} = (a^{2^{r - 2}})^2\\ |
− | Ponieważ <math>2^n \, | \, (r^2 - a)</math>, gdzie <math>n \geqslant 3</math>, to tym bardziej <math>2^3 \, | \, (r^2 - a)</math>. Co oznacza, że prawdziwa jest kongruencja
| + | u_r = a^{2^r d} = (a^{2^{r - 1} d})^2 = a^{m - 1} |
− | | + | \end{array}</math> |
− | ::<math>r^2 \equiv a \pmod{2^3}</math>
| |
− | | |
− | Skąd wynika natychmiast, że kongruencja <math>x^2 \equiv a \pmod{8}</math> ma rozwiązanie.
| |
− | | |
− | <math>\Large{\Longleftarrow}</math>
| |
− | | |
− | Indukcja matematyczna. Z uczynionego w twierdzeniu założenia wiemy, że kongruencja <math>x^2 \equiv a \pmod{8}</math> ma rozwiązanie. Zatem twierdzenie jest prawdziwe dla <math>n = 3</math>. Załóżmy teraz (założenie indukcyjne), że kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{2^n}</math>
| |
− | | |
− | ma rozwiązanie <math>x \equiv u_n \pmod{2^n}</math> i pokażemy, że twierdzenie jest prawdziwe dla <math>n + 1</math>, czyli że rozwiązanie ma kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{2^{n + 1}}</math>
| |
− | | |
− | Z założenia istnieje taka liczba <math>k</math>, że <math>u^2_n - a = k \cdot 2^n</math>. Niech
| |
− | | |
− | ::<math>r =
| |
− | \begin{cases}
| |
− | 0 & \text{gdy } k \text{ jest liczbą parzystą}\\
| |
− | 1 & \text{gdy } k \text{ jest liczbą nieparzystą}
| |
− | \end{cases}</math>
| |
| | | |
− | Zauważmy, że
| + | Wyrazy ciągu <math>(u_i)</math> są dane wzorem ogólnym |
| | | |
− | ::<math>(u_n + r \cdot 2^{n - 1})^2 - a = u^2_n - a + 2^n r + r^2 \cdot 2^{2 n - 2}</math> | + | ::<math>u_i = a^{2^i d}</math> |
| | | |
− | ::::::::<math>\;\! = k \cdot 2^n + 2^n r + r^2 \cdot 2^{2 n - 2}</math>
| + | gdzie <math>i = 0, 1, \ldots, r</math> |
| | | |
− | ::::::::<math>\;\! = 2^n (k + r) + r^2 \cdot 2^{2 n - 2}</math>
| + | Zauważmy, że mogą zdarzyć się następujące sytuacje |
| | | |
− | ::::::::<math>\;\! \equiv 0 \pmod{2^{n + 1}}</math> | + | :a) żaden z wyrazów ciągu <math>(u_i)</math> nie przystaje do <math>1</math> modulo <math>m</math> |
| | | |
− | bo <math>k + r</math> jest liczbą parzystą, a dla <math>n \geqslant 3</math> mamy <math>2 n - 2 \geqslant n + 1</math>. Zatem liczba <math>u_{n + 1} = u_n + r \cdot 2^{n - 1}</math> jest rozwiązaniem kongruencji
| + | :b) wszystkie wyrazy ciągu <math>(u_i)</math> przystają do <math>1</math> modulo <math>m</math> |
| | | |
− | ::<math>x^2 \equiv a \pmod{2^{n + 1}}</math> | + | :c) <math>u_k</math> jest pierwszym wyrazem ciągu <math>(u_i)</math>, który przystaje do <math>1</math> modulo <math>m</math> |
| | | |
− | Pokazaliśmy tym samym prawdziwość tezy indukcyjnej, co kończy dowód indukcyjny.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
| | | |
| + | Co możemy zapisać jako |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Wniosek J41</span><br/>
| + | :a) <math>u_i \not\equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</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>.
| |
| | | |
| + | :b) <math>u_i \equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</math> |
| | | |
| + | :c) <math>u_k \equiv 1 \pmod m \quad</math> dla pewnego <math>k \in [0, r]</math> |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J42</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 J3 i J11) 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}
| + | Z definicji każdy wyraz ciągu <math>(u_i)</math> jest kwadratem poprzedniego. W szczególności oznacza to, że jeżeli dla pewnego <math>k \in [0, r]</math> jest <math>u_k \equiv 1 \pmod m</math>, to <math>u_i \equiv 1 \pmod m</math> dla wszystkich <math>i \geqslant k</math>. Ten fakt pozwala doprecyzować zapis poszczególnych przypadków. |
− | x^2 & \equiv a \pmod{p^{\alpha_1}_1} \\
| |
− | & \,\,\,\cdots \\
| |
− | x^2 & \equiv a \pmod{p^{\alpha_s}_s} \\
| |
− | \end{align}</math> | |
| | | |
− | Z definicji J23, twierdzeń J38 i J40, uwagi J39 i wniosku J41 otrzymujemy
| + | :a) <math>u_i \not\equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, r]</math> |
| | | |
| + | :b) <math>u_0 \equiv 1 \pmod m</math> |
| | | |
| + | :c) <math>u_0 \not\equiv 1 \pmod m \quad</math> dla każdego <math>i \in [0, k - 1] \quad</math> oraz <math>\quad u_k \equiv 1 \pmod m \quad </math> dla każdego <math>i \in [k, r] , \quad</math> gdzie <math>k \geqslant 1</math> |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J43</span><br/>
| |
− | Niech <math>m \in \mathbb{Z}_+</math> i <math>\gcd (a, m) = 1</math>. Kongruencja
| |
| | | |
− | ::<math>x^2 \equiv a \pmod{m}</math>
| + | W przypadku a) mamy <math>u_r = a^{m - 1} \not\equiv 1 \pmod m</math>, zatem liczba <math>m</math> byłaby liczbą złożoną, wbrew założeniu, że jest liczbą pierwszą.<br/> |
| | | |
− | ma rozwiązanie wtedy i tylko wtedy, gdy
| + | Przypadek b) jest możliwy (np. dla <math>m = 41</math> i <math>a = 10</math>), ale nie pozwala powiedzieć nic więcej ani o liczbie <math>m</math>, ani o wyrazach ciągu <math>(u_i)</math>, które wszystkie przystają do <math>1</math> modulo <math>m</math>.<br/> |
| | | |
− | ::{| border="0"
| + | W przypadku c) mamy <math>u_k \equiv 1 \pmod m</math>, czyli <math>(u_{k - 1})^2 \equiv 1 \pmod m</math>. Z twierdzenia K12 wiemy, że musi być albo <math>u_{k - 1} \equiv - 1 \pmod m</math>, albo <math>u_{k - 1} \equiv 1 \pmod m</math>. Ale drugi przypadek nie może zachodzić, bo założyliśmy, że <math>u_k</math> jest pierwszym wyrazem ciągu <math>(u_i)</math>, który przystaje do <math>1</math> modulo <math>m</math>. Zatem musi być <math>u_{k - 1} \equiv - 1 \pmod m</math>.<br/> |
− | |-style=height:1em
| |
− | | ● dla każdego nieparzystego dzielnika pierwszego <math>p</math> liczby <math>m</math> jest <math>\left( {\small\frac{a}{p}} \right)_{\small{\!\! L}} = 1</math>
| |
− | |-style=height:1em
| |
− | | ● jeżeli <math>8 \, | \, m</math>, to <math>8 \, | \, ( a - 1 )</math>
| |
− | |-style=height:2.5em
| |
− | | ● jeżeli <math>8 \nmid m</math>, ale <math>4 \, | \, m</math>, to <math>4 \, | \, ( a - 1 )</math>
| |
− | |}
| |
| | | |
− | | + | Co kończy dowód twierdzenia.<br/> |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Zadanie J44</span><br/>
| |
− | Rozwiązać kongruencję, gdzie <math>p</math> jest liczbą pierwszą nieparzystą
| |
− | | |
− | ::<math>x^2 + rx + s \equiv 0 \pmod{p}</math>
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
| |
− | Ponieważ <math>\gcd (2, p) = 1</math>, to nie zmniejszając ogólności kongruencję powyższą możemy zapisać w postaci
| |
− | | |
− | ::<math>4 x^2 + 4 rx + 4 s \equiv 0 \pmod{p}</math>
| |
− | | |
− | ::<math>(2 x + r)^2 - r^2 + 4 s \equiv 0 \pmod{p}</math>
| |
− | | |
− | ::<math>(2 x + r)^2 \equiv r^2 - 4 s \pmod{p}</math>
| |
− | | |
− | Widzimy, że rozpatrywana kongruencja ma rozwiązanie wtedy i tylko wtedy, gdy liczba <math>r^2 - 4 s</math> jest liczbą kwadratową modulo <math>p</math>. Istotnie, jeśli jest liczbą kwadratową, to istnieje taka liczba <math>b</math>, że <math>b^2 \equiv r^2 - 4 s \pmod{p}</math>, zatem otrzymujemy
| |
− | | |
− | ::<math>(2 x + r)^2 \equiv b^2 \pmod{p}</math>
| |
− | | |
− | ::<math>2 x + r \equiv \pm b \pmod{p}</math>
| |
− | | |
− | ::<math>x \equiv {\small\frac{p + 1}{2}} \cdot (- r \pm b) \pmod{p}</math>
| |
− | | |
− | Jeśli <math>r^2 - 4 s</math> nie jest liczbą kwadratową modulo <math>p</math>, to kongruencja
| |
− | | |
− | ::<math>(2 x + r)^2 \equiv r^2 - 4 s \pmod{p}</math>
| |
− | | |
− | nie ma rozwiązania. Wynika stąd, że równoważna jej kongruencja
| |
− | | |
− | ::<math>x^2 + rx + s \equiv 0 \pmod{p}</math>
| |
− | | |
− | również nie ma rozwiązania.<br/>
| |
| □ | | □ |
| {{\Spoiler}} | | {{\Spoiler}} |
Linia 1301: |
Linia 364: |
| | | |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Zadanie J45</span><br/> | + | <span style="font-size: 110%; font-weight: bold;">Definicja K14</span><br/> |
− | Rozwiązać kongruencję
| + | Złożoną liczbę nieparzystą <math>m</math>, która spełnia twierdzenie K13 dla pewnej liczby <math>a \in \mathbb{Z}</math>, będziemy nazywali liczbą silnie pseudopierwszą przy podstawie <math>a</math> (w skrócie: SPSP(<math>a</math>)). |
− | | |
− | ::<math>5 x^2 + 6 x + 8 \equiv 0 \pmod{19}</math>
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
| |
− | Mnożąc obie strony kongruencji przez <math>4</math>, otrzymujemy
| |
− | | |
− | ::<math>x^2 + 24 x + 32 \equiv 0 \pmod{19}</math>
| |
− | | |
− | ::<math>x^2 + 5 x + 13 \equiv 0 \pmod{19}</math>
| |
− | | |
− | ::<math>4 x^2 + 4 \cdot 5 x + 4 \cdot 13 \equiv 0 \pmod{19}</math>
| |
− | | |
− | ::<math>(2 x + 5)^2 - 25 + 52 \equiv 0 \pmod{19}</math>
| |
− | | |
− | ::<math>(2 x + 5)^2 - 6 + 14 \equiv 0 \pmod{19}</math>
| |
− | | |
− | ::<math>(2 x + 5)^2 \equiv - 8 \pmod{19}</math>
| |
− | | |
− | ::<math>(2 x + 5)^2 \equiv 7^2 \pmod{19}</math>
| |
− | | |
− | ::<math>2 x + 5 \equiv \pm 7 \pmod{19}</math>
| |
− | | |
− | ::<math>2 x \equiv - 5 \pm 7 \pmod{19}</math>
| |
− | | |
− | Mnożąc obie strony kongruencji przez <math>10</math>, otrzymujemy: <math>x \equiv 13 \pmod{19}</math> lub <math>x \equiv 1 \pmod{19}</math>.
| |
| | | |
− | Nieco spostrzegawczości pozwala znaleźć rozwiązanie kongruencji natychmiast. W naszym przypadku wystarczyło zauważyć, że
| |
| | | |
− | ::<math>x^2 + 5 x + 13 \equiv x^2 - 14 x + 13 \equiv (x - 1) (x - 13) \pmod{19}</math><br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
| | | |
| + | <span style="font-size: 110%; font-weight: bold;">Uwaga K15</span><br/> |
| + | Niech <math>a</math> będzie liczbą całkowitą względnie pierwszą z <math>m</math> i <math>a \in [1, m - 1]</math>. Można pokazać, że jeżeli <math>m \neq 9</math> jest liczbą nieparzystą złożoną, to co najwyżej <math>\tfrac{1}{4}</math> liczb <math>a</math> stanowią liczby silnie pseudopierwsze. Zatem w przypadku liczb silnie pseudopierwszych nie istnieje odpowiednik liczb Carmichaela. Czyli nie istnieją liczby złożone nieparzyste <math>m</math>, dla których twierdzenie K13 byłoby prawdziwe dla wszystkich podstaw <math>a</math>. |
| | | |
| + | Wynika stąd, że jeżeli dla <math>k</math> różnych liczb <math>a</math> prawdziwe jest twierdzenie K13, to prawdopodobieństwo uznania liczby złożonej <math>m</math> za pierwszą wynosi <math>\left( \tfrac{1}{4} \right)^k</math>. |
| | | |
| | | |
| | | |
− | == Najmniejsze liczby niekwadratowe modulo == | + | <span style="font-size: 110%; font-weight: bold;">Uwaga K16</span><br/> |
| + | Wykorzystując twierdzenie K13, możemy napisać w PARI/GP prosty program do testowania pierwszości liczb. |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J46</span><br/> | + | <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, a) = |
− | 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.
| |
− | | |
− | | |
− | | |
− | | |
− | {| style="border-spacing: 5px; border: 2px solid black; background: transparent;"
| |
− | | '''A.''' Najmniejsze liczby niekwadratowe modulo <math>p</math>
| |
− | |}
| |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Przykład J47</span><br/>
| |
− | W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math>
| |
− | | |
− | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: center; margin-right: auto;"
| |
− | ! <math>\boldsymbol{m}</math>
| |
− | | <math>3</math> || <math>5</math> || <math>7</math> || <math>9</math> || <math>11</math> || <math>13</math> || <math>15</math> || <math>17</math> || <math>19</math> || <math>21</math> || <math>23</math> || <math>25</math> || <math>27</math> || <math>29</math> || <math>31</math> || <math>33</math> || <math>35</math> || <math>37</math> || <math>39</math> || <math>41</math> || <math>43</math> || <math>45</math> || <math>47</math> || <math>49</math> || <math>51</math>
| |
− | |-
| |
− | ! <math>\boldsymbol{g( p )}</math>
| |
− | | <math>2</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math>
| |
− | |}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J48</span><br/>
| |
− | Do wyszukiwania liczb <math>g = g (p)</math> Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP
| |
− | | |
− | <span style="font-size: 90%; color:black;">A(p) =
| |
| { | | { |
− | '''if'''( p == 2, '''return'''(0) ); | + | '''local'''(d, k, r, x); |
− | '''if'''( !'''isprime'''(p), '''return'''(0) ); | + | '''if'''( m % 2 == 0, '''return'''(m == 2) ); |
− | '''forprime'''(q = 2, p, '''if'''( jacobi(q, p) == -1, '''return'''(q) )); | + | r = '''valuation'''(m - 1, 2); \\ wykładnik, z jakim liczba 2 występuje w rozwinięciu na czynniki pierwsze liczby m - 1 |
| + | d = (m - 1) / 2^r; |
| + | x = modPower(a, d, m); |
| + | '''if'''( x == 1 || x == m - 1, '''return'''(1) ); \\ x = m - 1 to przypadek k == 0 |
| + | k = 0; |
| + | '''while'''( k++ < r, |
| + | x = x^2 % m; |
| + | '''if'''( x == m - 1, '''return'''(1) ); |
| + | ); |
| + | '''return'''(0); |
| }</span> | | }</span> |
| | | |
− | Zauważmy, że choć wyliczamy symbol Jacobiego, to jest to w rzeczywistości symbol Legendre'a, '''bo wiemy''', że liczba <math>p</math> jest liczbą pierwszą (w przypadku, gdy <math>p</math> jest liczbą złożoną, funkcja zwraca zero).
| |
| | | |
| | | |
− | | + | <span style="font-size: 110%; font-weight: bold;">Zadanie K17</span><br/> |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J49</span><br/> | + | Pokazać, że jeżeli liczba <math>m</math> jest SPSP(<math>a</math>), to jest PSP(<math>a</math>). |
− | 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ą.
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Przypuśćmy, że <math>g = a b</math> jest liczbą złożoną, gdzie <math>1 < a, b < g</math>. Z założenia <math>g</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math>, zatem liczby <math>a, b</math> są liczbami kwadratowymi modulo <math>p</math>. Z definicji liczb kwadratowych muszą istnieć takie liczby <math>r, s</math>, że
| |
− | | |
− | ::<math>r^2 \equiv a \pmod{p}</math>
| |
− | | |
− | ::<math>s^2 \equiv b \pmod{p}</math>
| |
− | | |
− | Skąd wynika, że
| |
− | | |
− | ::<math>g = a b \equiv (r s)^2 \pmod{p}</math>
| |
− | | |
− | Wbrew założeniu, że <math>g</math> jest liczbą niekwadratową modulo <math>p</math>.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Zadanie J50</span><br/>
| |
− | Pokazać, że najmniejszą liczbą niekwadratową modulo <math>p</math> jest
| |
− | | |
− | :* liczba <math>2</math> wtedy i tylko wtedy, gdy <math>p = 8 k \pm 3</math>
| |
− | :* liczba <math>3</math> wtedy i tylko wtedy, gdy <math>p = 24 k \pm 7</math>
| |
− | :* liczba <math>\geqslant 5</math> wtedy i tylko wtedy, gdy <math>p = 24 k \pm 1</math>
| |
| | | |
| {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}} | | {{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 J25 p.7) wiemy, że | + | Z założenia <math>m</math> jest SPSP(<math>a</math>), zatem spełniony jest dokładnie jeden z warunków |
− | | |
− | ::<math>\left( {\small\frac{2}{p}} \right)_{\small{\!\! L}} \,\, =
| |
− | \,\,
| |
− | \begin{cases}
| |
− | \;\;\: 1 & \text{gdy } p \equiv 1, 7 \pmod{8} \\
| |
− | - 1 & \text{gdy } p \equiv 3, 5 \pmod{8}
| |
− | \end{cases}</math>
| |
− | | |
− | Wynika stąd natychmiast, dla liczb pierwszych <math>p</math> postaci <math>8 k \pm 3</math> (i tylko dla takich liczb) liczba <math>2</math> jest liczbą niekwadratową, czyli również najmniejszą liczbą niekwadratową modulo <math>p</math>.
| |
− | | |
− | Z zadania J35 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 + 7</math>
| |
− | | |
− | ::<math>p = 8 k + 7 \quad \text{i} \quad p = 12 j + 5</math>
| |
− | | |
− | ::<math>p = 8 k + 7 \quad \text{i} \quad p = 12 j + 7</math>
| |
− | | |
− | Drugi i trzeci nie są możliwe, bo modulo <math>4</math> otrzymujemy
| |
− | | |
− | ::<math>p \equiv 1 \pmod{4} \quad \text{i} \quad p \equiv 3 \pmod{4}</math>
| |
− | | |
− | ::<math>p \equiv 3 \pmod{4} \quad \text{i} \quad p \equiv 1 \pmod{4}</math>
| |
− | | |
− | a z pierwszego i czwartego mamy
| |
− | | |
− | ::<math>3 p = 24 k + 3 \quad \text{i} \quad 2 p = 24 j + 10 \qquad \;\: \Longrightarrow \qquad p = 24 (k - j) - 7 \qquad \Longrightarrow \qquad p \equiv - 7 \pmod{24}</math>
| |
| | | |
− | ::<math>3 p = 24 k + 21 \quad \text{i} \quad 2 p = 24 j + 14 \qquad \Longrightarrow \qquad p = 24 (k - j) + 7 \qquad \Longrightarrow \qquad p \equiv 7 \pmod{24}</math> | + | :* <math>a^d \equiv 1 \pmod m</math> |
| + | :* <math>a^{2^k \cdot d} \equiv - 1 \pmod m</math>, dla pewnego <math>k \in [0, r - 1]</math> |
| | | |
− | Zauważmy, że problem mogliśmy zapisać w postaci układu kongruencji
| + | gdzie <math>m - 1 = 2^r \cdot d</math>, przy czym <math>d</math> jest liczbą nieparzystą. |
| | | |
− | ::<math>p \equiv \pm 1 \pmod{8}</math>
| + | Jeżeli spełniony jest pierwszy warunek, to |
| | | |
− | ::<math>p \equiv \pm 5 \pmod{12}</math> | + | ::<math>(a^d)^{2^r} \equiv 1 \pmod m</math> |
| | | |
− | Gdyby moduły tych kongruencji były względnie pierwsze, to każdemu wyborowi znaków odpowiadałaby pewna kongruencja równoważna (zobacz J3). Widzimy, że w 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ć
| + | ::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math> |
| | | |
− | chinese(Mod(1, 8), Mod(5, 12)) = Mod(17, 24)
| + | Czyli <math>m</math> jest PSP(<math>a</math>). |
− | chinese(Mod(1, 8), Mod(-5, 12)) - błąd
| |
− | chinese(Mod(-1, 8), Mod(5, 12)) - błąd
| |
− | chinese(Mod(-1, 8), Mod(-5, 12)) = Mod(7, 24)
| |
| | | |
− | Ostatni punkt zadania rozwiążemy tą metodą. Liczba większa lub równa <math>5</math> jest najmniejszą liczbą niekwadratową modulo <math>p</math> wtedy i tylko wtedy, gdy liczby <math>2</math> i <math>3</math> są liczbami kwadratowymi modulo <math>p</math>, co oznacza, że liczba pierwsza <math>p</math> spełnia kongruencje
| + | Jeżeli spełniony jest drugi warunek, to |
| | | |
− | ::<math>p \equiv \pm 1 \pmod{8}</math> | + | ::<math>(a^{2^k \cdot d})^{2^{r - k}} \equiv (- 1)^{2^{r - k}} \pmod m</math> |
| | | |
− | ::<math>p \equiv \pm 1 \pmod{12}</math> | + | ::<math>a^{2^r \cdot d} \equiv 1 \pmod m</math> |
| | | |
− | Postępując jak wyżej, otrzymujemy
| + | Czyli <math>m</math> jest PSP(<math>a</math>).<br/> |
− | | |
− | chinese(Mod(1, 8), Mod(1, 12)) = Mod(1, 24)
| |
− | chinese(Mod(1, 8), Mod(-1, 12)) - błąd
| |
− | chinese(Mod(-1, 8), Mod(1, 12)) - błąd
| |
− | chinese(Mod(-1, 8), Mod(-1, 12)) = Mod(23, 24)
| |
− | | |
− | Co należało pokazać.<br/>
| |
| □ | | □ |
| {{\Spoiler}} | | {{\Spoiler}} |
Linia 1471: |
Linia 428: |
| | | |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J51</span><br/> | + | <span style="font-size: 110%; font-weight: bold;">Przykład K18</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
| + | Pokażemy, że jeżeli <math>m</math> jest PSP(<math>2</math>), to <math>2^m - 1</math> jest SPSP(<math>2</math>). |
| | | |
− | ::<math>g (p) < \sqrt{p} + {\small\frac{1}{2}}</math>
| + | Z założenia <math>m</math> jest złożoną liczbą nieparzystą, zatem <math>N = 2^m - 1</math> jest złożoną liczbą nieparzystą. Ponieważ <math>m</math> jest FPSP(<math>2</math>), to |
| | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| + | ::<math>2^{m - 1} \equiv 1 \pmod m</math> |
− | Ponieważ <math>g \nmid p</math>, to z oszacowania <math>x - 1 < \lfloor x \rfloor \leqslant x</math> wynika, że
| |
| | | |
− | ::<math>{\small\frac{p}{g}} - 1 < \left\lfloor {\small\frac{p}{g}} \right\rfloor < {\small\frac{p}{g}}</math>
| + | Wynika stąd natychmiast, że <math>2^{m - 1} - 1 = k m</math>, gdzie <math>k</math> jest liczbą nieparzystą. Zatem |
| | | |
− | ::<math>p < g \left\lfloor {\small\frac{p}{g}} \right\rfloor + g < p + g</math> | + | ::<math>N - 1 = 2^m - 2 = 2 (2^{m - 1} - 1) = 2 k m</math> |
| | | |
− | Niech <math>u = \left\lfloor {\small\frac{p}{g}} \right\rfloor + 1</math>, mamy
| + | Widzimy, że liczba <math>2</math> występuje w pierwszej potędze w rozwinięciu liczby <math>N - 1</math> na czynniki pierwsze i łatwo otrzymujemy, że |
| | | |
− | ::<math>0 < g u - p < g</math> | + | ::<math>2^{(N - 1) / 2} = 2^{k m} = (2^m)^k = (2^m - 1 + 1)^k = (N + 1)^k \equiv 1 \pmod N</math> |
| | | |
− | Liczba <math>g u - p</math> musi być liczbą kwadratową modulo <math>p</math>, zatem
| + | Czyli <math>N = 2^m - 1</math> jest SPSP(<math>2</math>). |
| | | |
− | ::<math>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>g</math> jest najmniejszą liczbą taką, że <math>\left( {\small\frac{g}{p}} \right)_{\small{\!\! L}} = - 1</math>. Wynika stąd, że musi być <math>g \leqslant u</math> i łatwo znajdujemy, że
| |
| | | |
− | ::<math>g \leqslant \left\lfloor {\small\frac{p}{g}} \right\rfloor + 1 < {\small\frac{p}{g}} + 1</math> | + | <span style="font-size: 110%; font-weight: bold;">Przykład K19</span><br/> |
| + | Tabela zawiera najmniejsze liczby silnie pseudopierwsze dla podstaw <math>a</math> od <math>2</math> do <math>15</math> |
| | | |
− | ::<math>g^2 < p + g</math> | + | <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=1; '''forstep'''(m=3, 20000, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, a) && !'''isprime'''(m), '''print'''("a=", a, " m=", m); s++ ); '''if'''( s>5, '''break'''() ) ))</span> |
| | | |
− | Ponieważ wypisane liczby są liczbami całkowitymi, to ostatnią nierówność możemy zapisać w postaci
| + | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: center; margin-right: auto;" |
− | | + | ! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math> |
− | ::<math>g^2 \leqslant p + g - 1</math>
| + | |- |
− | | + | | || <math>2047</math> || <math>121</math> || <math>341</math> || <math>781</math> || <math>217</math> || <math>25</math> || <math>9</math> || <math>91</math> || <math>9</math> || <math>133</math> || <math>91</math> || <math>85</math> || <math>15</math> || <math>1687</math> |
− | Skąd otrzymujemy
| + | |- |
− | | + | | || <math>3277</math> || <math>703</math> || <math>1387</math> || <math>1541</math> || <math>481</math> || <math>325</math> || <math>65</math> || <math>121</math> || <math>91</math> || <math>793</math> || <math>133</math> || <math>1099</math> || <math>841</math> || <math>3277</math> |
− | ::<math>\left( g - {\small\frac{1}{2}} \right)^2 \leqslant p - {\small\frac{3}{4}}</math>
| + | |- |
− | | + | | || <math>4033</math> || <math>1891</math> || <math>2047</math> || <math>5461</math> || <math>1111</math> || <math>703</math> || <math>481</math> || <math>671</math> || <math>1729</math> || <math>2047</math> || <math>145</math> || <math>5149</math> || <math>2743</math> || <math>6541</math> |
− | ::<math>g \leqslant {\small\frac{1}{2}} + \sqrt{p - {\small\frac{3}{4}}} < {\small\frac{1}{2}} + \sqrt{p}</math>
| + | |- |
− | | + | | || <math>4681</math> || <math>3281</math> || <math>3277</math> || <math>5611</math> || <math>1261</math> || <math>2101</math> || <math>511</math> || <math>703</math> || <math>4187</math> || <math>4577</math> || <math>247</math> || <math>7107</math> || <math>3277</math> || <math>14041</math> |
− | Co należało pokazać.<br/>
| + | |- |
− | □
| + | | || <math>8321</math> || <math>8401</math> || <math>4033</math> || <math>7813</math> || <math>2701</math> || <math>2353</math> || <math>1417</math> || <math>1541</math> || <math>6533</math> || <math>5041</math> || <math>1649</math> || <math>8911</math> || <math>5713</math> || <math>14701</math> |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J52*</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"/>
| |
− | | |
− | ::<math>g (p) \leqslant 1.1 \cdot p^{1 / 4} \log p</math>
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J53</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"/>
| |
− | | |
− | ::<math>\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>
| |
− | | |
− | | |
− | | |
− | | |
− | | |
− | {| style="border-spacing: 5px; border: 2px solid black; background: transparent;"
| |
− | | '''B.''' Najmniejsze liczby niekwadratowe modulo <math>m</math>, gdzie <math>m</math> jest liczbą nieparzystą | |
| |} | | |} |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J54</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>.
| |
| | | |
| | | |
| + | <span style="font-size: 110%; font-weight: bold;">Przykład K20</span><br/> |
| + | Tabela pokazuje ilość liczb silnie pseudopierwszych dla podstaw <math>a</math> od <math>2</math> do <math>15</math> |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Przykład J55</span><br/> | + | <span style="font-size: 90%; color:black;">'''for'''(a=2, 15, s=0; '''forstep'''(k=3, 10^6, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(k, a) && !'''isprime'''(k), s++ )); '''print'''("a= ", a, " ", s))</span> |
− | W tabeli przedstawiliśmy najmniejsze liczby niekwadratowe modulo <math>p</math> i najmniejsze liczby niekwadratowe modulo <math>m</math>.
| |
| | | |
− | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: center; margin-right: auto;" | + | ::{| class="wikitable plainlinks" style="font-size: 90%; text-align: center; margin-right: auto;" |
− | ! <math>\boldsymbol{m}</math> | + | ! <math>\boldsymbol{a}</math> !! <math>\boldsymbol{2}</math> !! <math>\boldsymbol{3}</math> !! <math>\boldsymbol{4}</math> !! <math>\boldsymbol{5}</math> !! <math>\boldsymbol{6}</math> !! <math>\boldsymbol{7}</math> !! <math>\boldsymbol{8}</math> !! <math>\boldsymbol{9}</math> !! <math>\boldsymbol{10}</math> !! <math>\boldsymbol{11}</math> !! <math>\boldsymbol{12}</math> !! <math>\boldsymbol{13}</math> !! <math>\boldsymbol{14}</math> !! <math>\boldsymbol{15}</math> |
− | | <math>3</math> || <math>5</math> || <math>7</math> || <math>9</math> || <math>11</math> || <math>13</math> || <math>15</math> || <math>17</math> || <math>19</math> || <math>21</math> || <math>23</math> || <math>25</math> || <math>27</math> || <math>29</math> || <math>31</math> || <math>33</math> || <math>35</math> || <math>37</math> || <math>39</math> || <math>41</math> || <math>43</math> || <math>45</math> || <math>47</math> || <math>49</math> || <math>51</math> | + | |- |
| + | | #SPSP(<math>a</math>) <math> < 10^6</math> || <math>46</math> || <math>73</math> || <math>97</math> || <math>64</math> || <math>73</math> || <math>66</math> || <math>127</math> || <math>161</math> || <math>62</math> || <math>58</math> || <math>90</math> || <math>71</math> || <math>74</math> || <math>45</math> |
| + | |- |
| + | | #SPSP(<math>a</math>) <math> < 10^7</math> || <math>162</math> || <math>207</math> || <math>305</math> || <math>199</math> || <math>203</math> || <math>177</math> || <math>377</math> || <math>459</math> || <math>158</math> || <math>157</math> || <math>251</math> || <math>193</math> || <math>190</math> || <math>148</math> |
| |- | | |- |
− | ! <math>\boldsymbol{g( p )}</math>
| + | | #SPSP(<math>a</math>) <math> < 10^8</math> || <math>488</math> || <math>582</math> || <math>833</math> || <math>475</math> || <math>486</math> || <math>446</math> || <math>1023</math> || <math>1241</math> || <math>437</math> || <math>430</math> || <math>666</math> || <math>472</math> || <math>440</math> || <math>398</math> |
− | | <math>2</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math>
| |
| |- | | |- |
− | ! <math>\boldsymbol{g( m )}</math>
| + | | #SPSP(<math>a</math>) <math> < 10^9</math> || <math>1282</math> || <math>1514</math> || <math>2162</math> || <math>1268</math> || <math>1232</math> || <math>1163</math> || <math>2599</math> || <math>3210</math> || <math>1113</math> || <math>1125</math> || <math>1655</math> || <math>1142</math> || <math>1151</math> || <math>1041</math> |
− | | <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>3</math> || <math>2</math>
| |
| |} | | |} |
| | | |
| + | Widzimy, że liczb silnie pseudopierwszych jest znacznie mniej niż liczb pseudopierwszych Fermata. |
| | | |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J56</span><br/>
| |
− | Do wyszukiwania liczb <math>g = g (m)</math> Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP
| |
| | | |
− | <span style="font-size: 90%; color:black;">B(m) =
| + | <span style="font-size: 110%; font-weight: bold;">Uwaga K21</span><br/> |
− | {
| + | Interesujące i pożyteczne będzie zbadanie najmniejszych liczb silnie pseudopierwszych dla wielu podstaw. Niech badanymi podstawami będą kolejne liczby pierwsze. Najmniejszą liczbę SPSP(<math>2</math>) już znamy: <math>2047</math>. Najmniejszą liczbę, która jest jednocześnie SPSP(<math>2</math>) i SPSP(<math>3</math>) musimy poszukać. Prostym poleceniem |
− | '''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) ));
| |
− | }</span>
| |
| | | |
| + | <span style="font-size: 90%; color:black;">'''forstep'''(m=3, 2*10^6, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2) && isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 3) && !'''isprime'''(m), '''print'''("m=", m) ) )</span> |
| | | |
| + | znajdujemy, że <math>m = 1373653</math>. Więcej czasu będzie wymagało znalezienie liczby jednocześnie silnie pseudopierwszej względem podstaw <math>2, 3, 5</math>. Poleceniem |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J57</span><br/> | + | <span style="font-size: 90%; color:black;">'''forstep'''(m=3, 26*10^6, 2, '''if'''( isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 2) && isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 3) && isPrimeOr<span style="background-color: #fee481;">SPSP</span>(m, 5) && !'''isprime'''(m), '''print'''("m=", m) ) )</span> |
− | 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ą.
| |
| | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| + | znajdujemy, że szukana liczba to <math>m = 25326001</math>. |
− | Przypuśćmy, że <math>g = a b</math> jest liczbą złożoną, gdzie <math>1 < a, b < g</math>. Z założenia <math>g</math> jest najmniejszą liczbą niekwadratową modulo <math>m</math>, zatem liczby <math>a, b</math> są liczbami kwadratowymi modulo <math>m</math>. Z definicji liczb kwadratowych muszą istnieć takie liczby <math>r, s</math>, że
| |
| | | |
− | ::<math>r^2 \equiv a \pmod{m}</math>
| |
| | | |
− | ::<math>s^2 \equiv b \pmod{m}</math>
| + | Stosując bardziej wyrafinowane metody<ref name="SPSPtoNbases"/><ref name="Jaeschke1"/> znaleziono wartości liczb silnie pseudopierwszych względem wielu podstaw, które są kolejnymi liczbami pierwszymi, dla większej ilości liczb pierwszych<ref name="A014233"/>. Dla przykładu |
| | | |
− | Skąd wynika, że
| + | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: right; margin-right: auto;" |
− | | + | ! <math>\boldsymbol{n}</math> !! <math>\boldsymbol{m}</math> |
− | ::<math>g = a b \equiv (r s)^2 \pmod{m}</math>
| + | |- |
− | | + | | <math>1</math> || <math>2047</math> |
− | Wbrew założeniu, że <math>g</math> jest liczbą niekwadratową modulo <math>m</math>.<br/>
| + | |- |
− | □
| + | | <math>2</math> || <math>1373653</math> |
− | {{\Spoiler}}
| + | |- |
− | | + | | <math>3</math> || <math>25326001</math> |
− | | + | |- |
− | | + | | <math>4</math> || <math>3215031751</math> |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J58</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>.
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Wiemy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>m</math> wtedy i tylko wtedy, gdy kongruencja
| |
− | | |
− | ::<math>x^2 \equiv a \pmod{m}</math>
| |
− | | |
− | ma rozwiązanie. Przypuśćmy, że liczba <math>a</math> jest liczbą kwadratową modulo <math>m</math>. Zatem istnieje taka liczba <math>k \in \mathbb{Z}</math>, że
| |
− | | |
− | ::<math>k^2 \equiv a \pmod{m}</math>
| |
− | | |
− | Ponieważ z założenia <math>p \, | \, m</math>, to prawdziwa jest też kongruencja
| |
− | | |
− | ::<math>k^2 \equiv a \pmod{p}</math>
| |
− | | |
− | co przeczy założeniu, że liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math>.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J59</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>.
| |
− | | |
− | {{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 J58). 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
| |
− | | |
− | ::<math>x^2 \equiv g \pmod{m}</math>
| |
− | | |
− | nie ma rozwiązania. Niech <math>m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>. Zatem przynajmniej jedna z kongruencji
| |
− | | |
− | ::<math>x^2 \equiv g \pmod{p^{\alpha_k}_k}</math>
| |
− | | |
− | musi nie mieć rozwiązania (zobacz J11). Z twierdzenia J38 wiemy, że wtedy kongruencja
| |
− | | |
− | ::<math>x^2 \equiv g \pmod{p_k}</math>
| |
− | | |
− | również nie ma rozwiązania. Zatem <math>g</math> jest liczbą niekwadratową modulo <math>p_k</math> i <math>g < g_k</math>, co przeczy definicji liczby <math>g_k</math>.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J60</span><br/>
| |
− | Jeżeli <math>m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>, to
| |
− | | |
− | ::<math>g(m) = \min ( g (p_1), \ldots, g (p_s) )</math>
| |
− | | |
− | gdzie <math>g(m)</math> jest najmniejszą liczbą kwadratową modulo <math>m</math>, a <math>g(p_k)</math> są najmniejszymi liczbami kwadratowymi modulo <math>p_k</math>.
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Twierdzenie jest prostym wnioskiem z twierdzenia J59.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J61</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
| |
− | | |
− | ::<math>g(m) < \sqrt{m} + {\small\frac{1}{2}} \qquad \qquad \;\;\: \text{dla } m \geqslant 3</math>
| |
− | | |
− | ::<math>g(m) \leqslant 1.1 \cdot m^{1 / 4} \log m \qquad \qquad \text{dla } m \geqslant 5</math>
| |
− | | |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Niech <math>p</math> będzie dzielnikiem pierwszym liczby <math>m</math> takim, że <math>g(m) = g (p)</math> (z twierdzenia J59 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>
| |
− | | |
− | Podane w twierdzeniu oszacowania wynikają natychmiast z twierdzeń J51 i J52.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− | | |
− | | |
− | | |
− | | |
− | | |
− | {| style="border-spacing: 5px; border: 2px solid black; background: transparent;"
| |
− | | '''C.''' Najmniejsze dodatnie liczby niekwadratowe <math>a</math> takie, że <math>\left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} = - 1</math> | |
− | |} | |
− | | |
− | <span style="font-size: 110%; font-weight: bold;">Przykład J62</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>.
| |
− | | |
− | ::{| class="wikitable plainlinks" style="font-size: 100%; text-align: center; margin-right: auto;"
| |
− | ! <math>\boldsymbol{m}</math>
| |
− | | <math>3</math> || <math>5</math> || <math>7</math> || <math>9</math> || <math>11</math> || <math>13</math> || <math>15</math> || <math>17</math> || <math>19</math> || <math>21</math> || <math>23</math> || <math>25</math> || <math>27</math> || <math>29</math> || <math>31</math> || <math>33</math> || <math>35</math> || <math>37</math> || <math>39</math> || <math>41</math> || <math>43</math> || <math>45</math> || <math>47</math> || <math>49</math> || <math>51</math>
| |
| |- | | |- |
− | ! <math>\boldsymbol{g( p )}</math>
| + | | <math>5</math> || <math>2152302898747</math> |
− | | <math>2</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>-</math> || <math>2</math> || <math>-</math> || <math>3</math> || <math>2</math> || <math>-</math> || <math>5</math> || <math>-</math> || <math>-</math>
| |
| |- | | |- |
− | ! <math>\boldsymbol{g( m )}</math>
| + | | <math>6</math> || <math>3474749660383</math> |
− | | <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>3</math> || <math>2</math>
| |
| |- | | |- |
− | ! <math>\boldsymbol{c( m )}</math>
| + | | <math>7</math> || <math>341550071728321</math> |
− | | <math>2</math> || <math>2</math> || <math>3</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>7</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>-</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>5</math> || <math>2</math> || <math>2</math> || <math>7</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>5</math> || <math>-</math> || <math>2</math>
| |
| |} | | |} |
| | | |
| + | Podane w prawej kolumnie liczby <math>m</math> są najmniejszymi liczbami jednocześnie silnie pseudopierwszymi względem podstaw <math>p_1, \ldots, p_n</math>. Zauważmy, że wyniki te mają bardzo praktyczne zastosowanie. Przykładowo, jeśli <math>m</math> przechodzi test Millera-Rabina dla siedmiu podstaw <math>a = 2, 3, 5, 7, 11, 13, 17</math> i jest liczbą mniejszą od <math>3.41 \cdot 10^{14}</math>, to jest z pewnością liczbą pierwszą. |
| | | |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J63</span><br/>
| |
− | Do wyszukiwania liczb <math>c = c (m)</math> Czytelnik może wykorzystać prostą funkcję napisaną w PARI/GP
| |
| | | |
− | <span style="font-size: 90%; color:black;">C(m) =
| |
− | {
| |
− | '''if'''( m%2 == 0, '''return'''(0) );
| |
− | '''if'''( '''issquare'''(m), '''return'''(0) );
| |
− | '''forprime'''(p = 2, m, '''if'''( jacobi(p, m) == -1, '''return'''(p) ));
| |
− | }</span>
| |
| | | |
| + | == Uzupełnienie == |
| | | |
| + | <span style="font-size: 110%; font-weight: bold;">Uwaga K22</span><br/> |
| + | W funkcji <code>isPrimeOr<span style="background-color: #fee481;">SPSP</span>()</code> wykorzystaliśmy zaimplementowane w PARI/GP funkcje: |
| | | |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J64</span><br/> | + | * <code>gcd(a, b)</code> – znajduje największy wspólny dzielnik liczb a i b |
− | 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.
| + | * <code>valuation(a, b)</code> – znajduje największą wartość liczby <math>r</math> taką, że <math>b^r | a</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>).
| + | Wprowadzenie tych funkcji pozwoliło zwiększyć czytelność kodu, ale bez trudu możemy sami je napisać: |
| | | |
− | Dla <math>c(m)</math> nie są prawdziwe oszacowania podane w twierdzeniu J51. Łatwo zauważamy, że
| + | <span style="font-size: 90%; color:black;">gcd2(a, b) = |
| + | { |
| + | '''while'''( b <> 0, a = b; b = a % b ); |
| + | '''return'''(a); |
| + | }</span> |
| | | |
− | ::<math>c = c (15) = 7 > \sqrt{15} + {\small\frac{1}{2}} \approx 4.37</math>
| |
| | | |
− | ::<math>c = c (39) = 7 > \sqrt{39} + {\small\frac{1}{2}} \approx 6.74</math> | + | <span style="font-size: 90%; color:black;">valuation2(a, b) = |
| + | { |
| + | '''local'''(s); |
| + | s = 0; |
| + | '''while'''(a % b == 0, s++; a = a / b); |
| + | '''return'''(s); |
| + | }</span> |
| | | |
− | ::<math>c = c (105) = 11 > \sqrt{105} + {\small\frac{1}{2}} \approx 10.75</math>
| |
− |
| |
− | ::<math>c = c (231) = 17 > \sqrt{231} + {\small\frac{1}{2}} \approx 15.7</math>
| |
− |
| |
− | Nie ma więcej takich przypadków dla <math>m < 10^9</math>.
| |
− |
| |
− |
| |
− |
| |
− | <span style="font-size: 110%; font-weight: bold;">Twierdzenie J65</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ą.
| |
− |
| |
− | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
− | Przypuśćmy, że <math>c = a b</math> jest liczbą złożoną, gdzie <math>1 < a, b < c</math>. Mamy
| |
− |
| |
− | ::<math>- 1 = \left( {\small\frac{c}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{a b}{m}} \right)_{\small{\!\! J}} = \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}}</math><math>\left( {\small\frac{b}{m}} \right)_{\small{\!\! J}}</math>
| |
− |
| |
− | Zatem jeden z czynników po prawej stronie musi być równy <math>- 1</math> wbrew definicji liczby <math>c</math>.<br/>
| |
− | □
| |
− | {{\Spoiler}}
| |
− |
| |
− |
| |
− |
| |
− | <span style="font-size: 110%; font-weight: bold;">Uwaga J66</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"/>
| |
− |
| |
− | ::<math>\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>
| |
| | | |
| | | |
Linia 1756: |
Linia 569: |
| <references> | | <references> |
| | | |
− | <ref name="CRT1">Wikipedia, ''Chińskie twierdzenie o resztach'', ([https://pl.wikipedia.org/wiki/Chi%C5%84skie_twierdzenie_o_resztach Wiki-pl]), ([https://en.wikipedia.org/wiki/Chinese_remainder_theorem Wiki-en])</ref> | + | <ref name="Carmichael1">W. R. Alford, Andrew Granville and Carl Pomerance, ''There are Infinitely Many Carmichael Numbers'', Annals of Mathematics, '''140''', (1994), 703-722</ref> |
| | | |
− | <ref name="CRT2">CRT to często używany skrót od angielskiej nazwy twierdzenia: ''Chinese remainder theorem''</ref> | + | <ref name="Carmichael2">Glyn Harman, ''On the Number of Carmichael Numbers up to x'', Bull. London Math. Soc. 37 (2005) 641–650</ref> |
| | | |
− | <ref name="logic1">Wikipedia, ''Logical equivalence'', ([https://en.wikipedia.org/wiki/Logical_equivalence Wiki-en])</ref> | + | <ref name="Carmichael3">Glyn Harman, ''Watt’s Mean Value Theorem and Carmichael Numbers'', International Journal of Number Theory, Vol. 4, No. 2 (2008) 241–248</ref> |
| | | |
− | <ref name="sumazbiorow">Wikipedia, ''Zasada włączeń i wyłączeń'', ([https://pl.wikipedia.org/wiki/Zasada_w%C5%82%C4%85cze%C5%84_i_wy%C5%82%C4%85cze%C5%84 Wiki-pl]), ([https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle Wiki-en])</ref> | + | <ref name="Miller1">Gary L. Miller, ''Riemann's Hypothesis and Tests for Primality'', Journal of Computer and System Sciences '''13''', 300-317 (1976)</ref> |
| | | |
− | <ref name="jacobi1">Wikipedia, ''Symbol Jacobiego'', ([https://pl.wikipedia.org/wiki/Symbol_Jacobiego Wiki-pl]), ([https://en.wikipedia.org/wiki/Jacobi_symbol Wiki-en])</ref> | + | <ref name="Rabin1">Michael O. Rabin, ''Probabilistic Algorithm for Testing Primality'', Journal of Number Theory '''12''', 128-138 (1980)</ref> |
| | | |
− | <ref name="legendre1">Wikipedia, ''Symbol Legendre’a'', ([https://pl.wikipedia.org/wiki/Symbol_Legendre%E2%80%99a Wiki-pl]), ([https://en.wikipedia.org/wiki/Legendre_symbol Wiki-en])</ref> | + | <ref name="SPSPtoNbases">Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr., ''The Pseudoprimes to 25*10^9'', Mathematics of Computation, Vol. 35, No. 151 (1980), 1003-1026</ref> |
| | | |
− | <ref name="Norton1">Karl K. Norton, ''Numbers with Small Prime Factors, and the Least ''k''th Power Non-Residue'', Memoirs of the American Mathematical Society, No. 106 (1971)</ref> | + | <ref name="Jaeschke1">Gerhard Jaeschke, ''On Strong Pseudoprimes to Several Bases'', Mathematics of Computation, Vol. 61, No. 204 (Oct., 1993), 915-926</ref> |
| | | |
− | <ref name="Trevino1">Enrique Treviño, ''The least k-th power non-residue'', Journal of Number Theory, Volume 149 (2015)</ref> | + | <ref name="A014233">On-Line Encyclopedia of Integer Sequences, ''Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness'', ([https://oeis.org/A014233 A014233])</ref> |
− | | |
− | <ref name="Trevino2">Kevin J. McGown and Enrique Treviño, ''The least quadratic non-residue'', Mexican Mathematicians in the World (2021)</ref>
| |
− | | |
− | <ref name="Erdos1">Paul Erdős, ''Számelméleti megjegyzések I'', Afar. Lapok, v. 12 (1961)</ref>
| |
− | | |
− | <ref name="BaillieWagstaff1">Robert Baillie and Samuel S. Wagstaff Jr., ''Lucas Pseudoprimes'', Mathematics of Computation Vol. 35, No. 152 (1980), ([http://mpqs.free.fr/LucasPseudoprimes.pdf LINK])</ref>
| |
| | | |
| </references> | | </references> |
− |
| |
− |
| |
− |
| |
− |
| |
− |
| |
− |
| |
| | | |
| | | |
11.11.2022
Potęgowanie modulo
Uwaga K1
Z twierdzenia Fermata (zobacz J18) wynika, że jeżeli liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ m }[/math] są względnie pierwsze oraz [math]\displaystyle{ m }[/math] nie dzieli liczby [math]\displaystyle{ a^{m - 1} - 1 }[/math], to [math]\displaystyle{ m }[/math] jest liczbą złożoną. Każde twierdzenie pozwalające wykryć złożoność liczby może być wykorzystane do badania pierwszości liczb. Twierdzenia takie nie dają całkowitej pewności, że badana liczba jest pierwsza. Mamy na przykład [math]\displaystyle{ 341 = 11 \cdot 31 }[/math], ale [math]\displaystyle{ 341 | (2^{340} - 1) }[/math], bo
- [math]\displaystyle{ 2^{340} - 1 = 2239744742177804210557442280568444278121645497234649534899989100963791871180160945380877493271607115775 }[/math]
- [math]\displaystyle{ \;\;\; = 341 \cdot 6568166399348399444449977362370804334667582103327417990909058947107894050381703652143335757394742275 }[/math]
Widzimy, że nawet dla niewielkiej liczby [math]\displaystyle{ 341 }[/math], potęga [math]\displaystyle{ 2^{340} - 1 }[/math] jest liczbą ogromną. Jeśli ta metoda ma mieć jakiekolwiek zastosowanie, to musimy znaleźć inny sposób obliczania reszty z dzielenia [math]\displaystyle{ a^n }[/math] przez [math]\displaystyle{ m }[/math], czyli potęgowania modulo [math]\displaystyle{ m }[/math].
Uwaga K2
Wykorzystując wzór rekurencyjny
- [math]\displaystyle{ a^n = \left\{ \begin{array}{cll}
a & & \text{gdy } n = 1\\
(a^2)^{{\large\frac{n}{2}}} & & \text{gdy } n \text{ jest parzyste}\\
a \cdot (a^2)^{{\large\frac{n - 1}{2}}} & & \text{gdy } n \text{ jest nieparzyste}
\end{array} \right. }[/math]
możemy napisać w PARI/GP prosty program do potęgowania modulo:
modPower(a, n, m) =
\\ a - podstawa, n - wykładnik, m - moduł
{
local(w);
if( m == 1, return(0) );
a = a % m;
w = 1;
while( n > 0,
if( n % 2 == 1, w = (w * a) % m; n = n - 1); \\ gdy n jest nieparzyste, wyłączamy a i zmniejszamy n o jeden
a = (a*a) % m; \\ wyliczamy nową podstawę modulo m
n = n/2; \\ dla nowej podstawy wykładnik jest dwa razy mniejszy
);
return(w);
}
Zauważmy, że w funkcji modPower()
nie występują wyrażenia o wartości większej od [math]\displaystyle{ m^2 }[/math].
Liczby pseudopierwsze Fermata
Liczby złożone nieparzyste spełniające równanie Fermata, otrzymały własną nazwę.
Definicja K3
Jeżeli [math]\displaystyle{ m }[/math] jest liczbą złożoną nieparzystą i dla pewnego [math]\displaystyle{ a \in \mathbb{Z} }[/math] prawdziwa jest kongruencja
- [math]\displaystyle{ a^{m - 1} \equiv 1 \pmod m }[/math]
to powiemy, że [math]\displaystyle{ m }[/math] jest liczbą pseudopierwszą Fermata przy podstawie [math]\displaystyle{ a }[/math] lub krótko: [math]\displaystyle{ m }[/math] jest PSP([math]\displaystyle{ a }[/math]).
Uwaga K4
Zauważmy, że w definicji liczb pseudopierwszych Fermata nie musimy dodatkowo dołączać warunku [math]\displaystyle{ \gcd (a, m) = 1 }[/math], bo wynika on z przyjętej definicji. Mamy
- [math]\displaystyle{ \gcd (a^{m - 1}, m) = \gcd (1, m) = 1 }[/math]
Zatem [math]\displaystyle{ \gcd (a, m) = 1 }[/math].
Możemy też łatwo pokazać, że jeżeli [math]\displaystyle{ \gcd (a, m) = d \gt 1 }[/math], to liczba [math]\displaystyle{ m }[/math] nie może być liczbą pseudopierwszą Fermata przy podstawie [math]\displaystyle{ a }[/math]. Istotnie, gdyby tak było, to mielibyśmy
- [math]\displaystyle{ a^{m - 1} \equiv 1 \pmod{m} }[/math]
Ponieważ [math]\displaystyle{ d|m }[/math], to jest również
- [math]\displaystyle{ a^{m - 1} \equiv 1 \pmod{d} }[/math]
Ale modulo [math]\displaystyle{ d }[/math] otrzymujemy natychmiast
- [math]\displaystyle{ 0 \equiv 1 \pmod{d} }[/math]
Co jest niemożliwe, czyli [math]\displaystyle{ m }[/math] nie jest PSP([math]\displaystyle{ a }[/math]).
Twierdzenie K5
Dla każdej podstawy [math]\displaystyle{ a \geqslant 2 }[/math] istnieje nieskończenie wiele liczb pseudopierwszych Fermata.
Dowód
Niech [math]\displaystyle{ a \in \mathbb{Z} }[/math] i [math]\displaystyle{ a \geqslant 2 }[/math]. Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą, to
- [math]\displaystyle{ a^p - 1 = (a - 1) (a^{p - 1} + a^{p - 2} + \ldots + a^2 + a + 1) }[/math]
oraz
- [math]\displaystyle{ a^p + 1 = (a + 1) (a^{p - 1} - a^{p - 2} + \ldots + a^2 - a + 1) }[/math]
Czyli [math]\displaystyle{ a - 1 | a^p - 1 }[/math] oraz [math]\displaystyle{ a + 1 | a^p + 1 }[/math].
Jeżeli przez [math]\displaystyle{ R_2 (a) }[/math] oznaczymy resztę z dzielenia liczby [math]\displaystyle{ a }[/math] przez [math]\displaystyle{ 2 }[/math] równą [math]\displaystyle{ 0 }[/math] lub [math]\displaystyle{ 1 }[/math], to prawdziwe są kongruencje
- [math]\displaystyle{ a \equiv R_2 (a) \pmod 2 }[/math]
oraz
- [math]\displaystyle{ a^n \equiv R_2 (a) \pmod 2 }[/math]
dla dowolnej liczby całkowitej dodatniej [math]\displaystyle{ n }[/math]. Zatem modulo [math]\displaystyle{ 2 }[/math] jest
- [math]\displaystyle{ {\small\frac{a^p - 1}{a - 1}} \equiv R_2 (a) \cdot (p - 1) + 1 \equiv 1 \pmod 2 }[/math]
- [math]\displaystyle{ {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2 }[/math]
Co oznacza, że
- [math]\displaystyle{ m = {\small\frac{a^p - 1}{a - 1}} \cdot {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod 2 }[/math]
Czyli [math]\displaystyle{ m }[/math] jest złożoną liczbą nieparzystą. Pozostaje pokazać, że [math]\displaystyle{ a^{m - 1} \equiv 1 \pmod m }[/math].
Z twierdzenia Fermata wiemy, że
- [math]\displaystyle{ a^p - 1 \equiv a - 1 \pmod p }[/math]
Ponieważ [math]\displaystyle{ (a - 1) | (a^p - 1) }[/math], to możemy napisać
- [math]\displaystyle{ (a - 1) \cdot \left( {\small\frac{a^p - 1}{a - 1}} - 1 \right) \equiv 0 \pmod p }[/math]
Z założenia [math]\displaystyle{ p \nmid (a - 1) }[/math], zatem liczba pierwsza [math]\displaystyle{ p }[/math] musi dzielić [math]\displaystyle{ {\small\frac{a^p - 1}{a - 1}} - 1 }[/math] i otrzymujemy
- [math]\displaystyle{ {\small\frac{a^p - 1}{a - 1}} \equiv 1 \pmod p }[/math]
Postępując analogicznie jak wyżej, dostajemy
- [math]\displaystyle{ a^p + 1 \equiv a + 1 \pmod p }[/math]
- [math]\displaystyle{ (a + 1) \cdot \left( {\small\frac{a^p + 1}{a + 1}} - 1 \right) \equiv 0 \pmod p }[/math]
- [math]\displaystyle{ {\small\frac{a^p + 1}{a + 1}} \equiv 1 \pmod p }[/math]
Wynika stąd, że [math]\displaystyle{ m \equiv 1 \pmod p }[/math].
Zbierając mamy [math]\displaystyle{ 2| (m - 1) }[/math] i [math]\displaystyle{ p| (m - 1) }[/math], zatem [math]\displaystyle{ 2 p| (m - 1) }[/math], czyli
- [math]\displaystyle{ m = {\small\frac{a^{2 p} - 1}{a^2 - 1}} \equiv 1 \pmod{2 p} }[/math]
Oznacza to, że [math]\displaystyle{ m = 1 + 2 k p }[/math] dla pewnej liczby całkowitej [math]\displaystyle{ k \gt 0 }[/math].
Zauważmy teraz, że z definicji liczby [math]\displaystyle{ m }[/math] mamy [math]\displaystyle{ (a^2 - 1) m = a^{2 p} - 1 }[/math]. Rozpatrując to równanie modulo [math]\displaystyle{ m }[/math], otrzymujemy
- [math]\displaystyle{ a^{2 p} \equiv 1 \pmod m }[/math]
Zatem modulo [math]\displaystyle{ m }[/math] jest
- [math]\displaystyle{ a^{m - 1} = a^{2 k p} = (a^{2 p})^k \equiv 1^k \equiv 1 \pmod m }[/math]
Ponieważ dowolna liczba pierwsza [math]\displaystyle{ p \gt a^2 - 1 }[/math] nie dzieli [math]\displaystyle{ a^2 - 1 }[/math], to dla każdego [math]\displaystyle{ a \geqslant 2 }[/math] istnieje nieskończenie wiele liczb, które są PSP([math]\displaystyle{ a }[/math]). Co należało pokazać.
□
Przykład K6
Z dowodu twierdzenia K5 wynika, że jeżeli liczba [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ p \nmid (a^2 - 1) }[/math], to liczba [math]\displaystyle{ m = {\small\frac{a^{2 p} - 1}{a^2 - 1}} }[/math] jest PSP([math]\displaystyle{ a }[/math]). Poniżej przedstawiamy przykłady takich liczb, dla kolejnych liczb pierwszych nieparzystych [math]\displaystyle{ p }[/math] takich, że [math]\displaystyle{ p \nmid (a^2 - 1) }[/math].
for(a=2, 5, s=1; d=a^2-1; forprime(p=3, 50, if( d%p == 0, next() ); m=(a^(2*p)-1)/d; print("a= ", a, " m= ", m); s++; if( s>6, break() ) ))
[math]\displaystyle{ \boldsymbol{a} }[/math] |
[math]\displaystyle{ \boldsymbol{2} }[/math] |
[math]\displaystyle{ \boldsymbol{3} }[/math] |
[math]\displaystyle{ \boldsymbol{4} }[/math] |
[math]\displaystyle{ \boldsymbol{5} }[/math]
|
|
[math]\displaystyle{ 341 }[/math] |
[math]\displaystyle{ 91 }[/math] |
[math]\displaystyle{ 17895697 }[/math] |
[math]\displaystyle{ 406901 }[/math]
|
|
[math]\displaystyle{ 5461 }[/math] |
[math]\displaystyle{ 7381 }[/math] |
[math]\displaystyle{ 1172812402961 }[/math] |
[math]\displaystyle{ 254313151 }[/math]
|
|
[math]\displaystyle{ 1398101 }[/math] |
[math]\displaystyle{ 597871 }[/math] |
[math]\displaystyle{ 300239975158033 }[/math] |
[math]\displaystyle{ 99341074625651 }[/math]
|
|
[math]\displaystyle{ 22369621 }[/math] |
[math]\displaystyle{ 3922632451 }[/math] |
[math]\displaystyle{ 19676527011956855057 }[/math] |
[math]\displaystyle{ 62088171641031901 }[/math]
|
|
[math]\displaystyle{ 5726623061 }[/math] |
[math]\displaystyle{ 317733228541 }[/math] |
[math]\displaystyle{ 5037190915060954894609 }[/math] |
[math]\displaystyle{ 24253192047278086344401 }[/math]
|
|
[math]\displaystyle{ 91625968981 }[/math] |
[math]\displaystyle{ 2084647712458321 }[/math] |
[math]\displaystyle{ 330117343809434739973099793 }[/math] |
[math]\displaystyle{ 15158245029548803965250651 }[/math]
|
Uwaga K7
Wykorzystując funkcję potęgowania modulo, możemy napisać prosty program do testowania pierwszości liczb w oparciu o twierdzenie Fermata.
isPrimeOrPSP(m, a) =
{
if( modPower(a, m-1, m) == 1, return(1), return(0) );
}
Przykład K8
Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Fermata dla podstaw [math]\displaystyle{ a }[/math] od [math]\displaystyle{ 2 }[/math] do [math]\displaystyle{ 15 }[/math]
for(a=2, 15, s=1; forstep(m=1, 2000, 2, if( isPrimeOrPSP(m, a) && !isprime(m), print("a=", a, " m=", m); s++ ); if( s>5, break() ) ))
[math]\displaystyle{ \boldsymbol{a} }[/math] |
[math]\displaystyle{ \boldsymbol{2} }[/math] |
[math]\displaystyle{ \boldsymbol{3} }[/math] |
[math]\displaystyle{ \boldsymbol{4} }[/math] |
[math]\displaystyle{ \boldsymbol{5} }[/math] |
[math]\displaystyle{ \boldsymbol{6} }[/math] |
[math]\displaystyle{ \boldsymbol{7} }[/math] |
[math]\displaystyle{ \boldsymbol{8} }[/math] |
[math]\displaystyle{ \boldsymbol{9} }[/math] |
[math]\displaystyle{ \boldsymbol{10} }[/math] |
[math]\displaystyle{ \boldsymbol{11} }[/math] |
[math]\displaystyle{ \boldsymbol{12} }[/math] |
[math]\displaystyle{ \boldsymbol{13} }[/math] |
[math]\displaystyle{ \boldsymbol{14} }[/math] |
[math]\displaystyle{ \boldsymbol{15} }[/math]
|
|
[math]\displaystyle{ 341 }[/math] |
[math]\displaystyle{ 91 }[/math] |
[math]\displaystyle{ 15 }[/math] |
[math]\displaystyle{ 217 }[/math] |
[math]\displaystyle{ 35 }[/math] |
[math]\displaystyle{ 25 }[/math] |
[math]\displaystyle{ 9 }[/math] |
[math]\displaystyle{ 91 }[/math] |
[math]\displaystyle{ 9 }[/math] |
[math]\displaystyle{ 15 }[/math] |
[math]\displaystyle{ 65 }[/math] |
[math]\displaystyle{ 21 }[/math] |
[math]\displaystyle{ 15 }[/math] |
[math]\displaystyle{ 341 }[/math]
|
|
[math]\displaystyle{ 561 }[/math] |
[math]\displaystyle{ 121 }[/math] |
[math]\displaystyle{ 85 }[/math] |
[math]\displaystyle{ 561 }[/math] |
[math]\displaystyle{ 185 }[/math] |
[math]\displaystyle{ 325 }[/math] |
[math]\displaystyle{ 21 }[/math] |
[math]\displaystyle{ 121 }[/math] |
[math]\displaystyle{ 33 }[/math] |
[math]\displaystyle{ 133 }[/math] |
[math]\displaystyle{ 91 }[/math] |
[math]\displaystyle{ 85 }[/math] |
[math]\displaystyle{ 39 }[/math] |
[math]\displaystyle{ 1477 }[/math]
|
|
[math]\displaystyle{ 645 }[/math] |
[math]\displaystyle{ 671 }[/math] |
[math]\displaystyle{ 91 }[/math] |
[math]\displaystyle{ 781 }[/math] |
[math]\displaystyle{ 217 }[/math] |
[math]\displaystyle{ 561 }[/math] |
[math]\displaystyle{ 45 }[/math] |
[math]\displaystyle{ 205 }[/math] |
[math]\displaystyle{ 91 }[/math] |
[math]\displaystyle{ 259 }[/math] |
[math]\displaystyle{ 133 }[/math] |
[math]\displaystyle{ 105 }[/math] |
[math]\displaystyle{ 65 }[/math] |
[math]\displaystyle{ 1541 }[/math]
|
|
[math]\displaystyle{ 1105 }[/math] |
[math]\displaystyle{ 703 }[/math] |
[math]\displaystyle{ 341 }[/math] |
[math]\displaystyle{ 1541 }[/math] |
[math]\displaystyle{ 301 }[/math] |
[math]\displaystyle{ 703 }[/math] |
[math]\displaystyle{ 63 }[/math] |
[math]\displaystyle{ 511 }[/math] |
[math]\displaystyle{ 99 }[/math] |
[math]\displaystyle{ 305 }[/math] |
[math]\displaystyle{ 143 }[/math] |
[math]\displaystyle{ 231 }[/math] |
[math]\displaystyle{ 195 }[/math] |
[math]\displaystyle{ 1687 }[/math]
|
|
[math]\displaystyle{ 1387 }[/math] |
[math]\displaystyle{ 949 }[/math] |
[math]\displaystyle{ 435 }[/math] |
[math]\displaystyle{ 1729 }[/math] |
[math]\displaystyle{ 481 }[/math] |
[math]\displaystyle{ 817 }[/math] |
[math]\displaystyle{ 65 }[/math] |
[math]\displaystyle{ 671 }[/math] |
[math]\displaystyle{ 259 }[/math] |
[math]\displaystyle{ 481 }[/math] |
[math]\displaystyle{ 145 }[/math] |
[math]\displaystyle{ 357 }[/math] |
[math]\displaystyle{ 481 }[/math] |
[math]\displaystyle{ 1729 }[/math]
|
Przykład K9
Tabela pokazuje ilość liczb pseudopierwszych Fermata dla podstaw [math]\displaystyle{ a }[/math] od [math]\displaystyle{ 2 }[/math] do [math]\displaystyle{ 15 }[/math]
for(a=2, 15, s=0; forstep(k=1, 10^6, 2, if( isPrimeOrPSP(k, a) && !isprime(k), s++ )); print("a= ", a, " ", s))
[math]\displaystyle{ \boldsymbol{a} }[/math] |
[math]\displaystyle{ \boldsymbol{2} }[/math] |
[math]\displaystyle{ \boldsymbol{3} }[/math] |
[math]\displaystyle{ \boldsymbol{4} }[/math] |
[math]\displaystyle{ \boldsymbol{5} }[/math] |
[math]\displaystyle{ \boldsymbol{6} }[/math] |
[math]\displaystyle{ \boldsymbol{7} }[/math] |
[math]\displaystyle{ \boldsymbol{8} }[/math] |
[math]\displaystyle{ \boldsymbol{9} }[/math] |
[math]\displaystyle{ \boldsymbol{10} }[/math] |
[math]\displaystyle{ \boldsymbol{11} }[/math] |
[math]\displaystyle{ \boldsymbol{12} }[/math] |
[math]\displaystyle{ \boldsymbol{13} }[/math] |
[math]\displaystyle{ \boldsymbol{14} }[/math] |
[math]\displaystyle{ \boldsymbol{15} }[/math]
|
#PSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^6 }[/math] |
[math]\displaystyle{ 245 }[/math] |
[math]\displaystyle{ 243 }[/math] |
[math]\displaystyle{ 464 }[/math] |
[math]\displaystyle{ 238 }[/math] |
[math]\displaystyle{ 301 }[/math] |
[math]\displaystyle{ 229 }[/math] |
[math]\displaystyle{ 678 }[/math] |
[math]\displaystyle{ 362 }[/math] |
[math]\displaystyle{ 271 }[/math] |
[math]\displaystyle{ 236 }[/math] |
[math]\displaystyle{ 378 }[/math] |
[math]\displaystyle{ 257 }[/math] |
[math]\displaystyle{ 283 }[/math] |
[math]\displaystyle{ 203 }[/math]
|
#PSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^7 }[/math] |
[math]\displaystyle{ 750 }[/math] |
[math]\displaystyle{ 749 }[/math] |
[math]\displaystyle{ 1347 }[/math] |
[math]\displaystyle{ 726 }[/math] |
[math]\displaystyle{ 895 }[/math] |
[math]\displaystyle{ 651 }[/math] |
[math]\displaystyle{ 1993 }[/math] |
[math]\displaystyle{ 1150 }[/math] |
[math]\displaystyle{ 766 }[/math] |
[math]\displaystyle{ 672 }[/math] |
[math]\displaystyle{ 1091 }[/math] |
[math]\displaystyle{ 719 }[/math] |
[math]\displaystyle{ 817 }[/math] |
[math]\displaystyle{ 614 }[/math]
|
#PSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^8 }[/math] |
[math]\displaystyle{ 2057 }[/math] |
[math]\displaystyle{ 2131 }[/math] |
[math]\displaystyle{ 3805 }[/math] |
[math]\displaystyle{ 1910 }[/math] |
[math]\displaystyle{ 2314 }[/math] |
[math]\displaystyle{ 1782 }[/math] |
[math]\displaystyle{ 5407 }[/math] |
[math]\displaystyle{ 3214 }[/math] |
[math]\displaystyle{ 2091 }[/math] |
[math]\displaystyle{ 1891 }[/math] |
[math]\displaystyle{ 2933 }[/math] |
[math]\displaystyle{ 1929 }[/math] |
[math]\displaystyle{ 2155 }[/math] |
[math]\displaystyle{ 1718 }[/math]
|
#PSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^9 }[/math] |
[math]\displaystyle{ 5597 }[/math] |
[math]\displaystyle{ 5767 }[/math] |
[math]\displaystyle{ 10173 }[/math] |
[math]\displaystyle{ 5146 }[/math] |
[math]\displaystyle{ 6204 }[/math] |
[math]\displaystyle{ 4923 }[/math] |
[math]\displaystyle{ 14629 }[/math] |
[math]\displaystyle{ 8670 }[/math] |
[math]\displaystyle{ 5599 }[/math] |
[math]\displaystyle{ 5020 }[/math] |
[math]\displaystyle{ 7781 }[/math] |
[math]\displaystyle{ 5082 }[/math] |
[math]\displaystyle{ 5848 }[/math] |
[math]\displaystyle{ 4665 }[/math]
|
Uwaga K10
Można pokazać, że jeżeli [math]\displaystyle{ m }[/math] jest liczbą nieparzystą złożoną i istnieje przynajmniej jedna liczba [math]\displaystyle{ a }[/math] względnie pierwsza z [math]\displaystyle{ m }[/math], taka że
- [math]\displaystyle{ a^{m - 1} \not\equiv 1 \pmod m }[/math]
to dla co najmniej połowy liczb [math]\displaystyle{ b \in [1, m - 1] }[/math] względnie pierwszych z [math]\displaystyle{ m }[/math] jest
- [math]\displaystyle{ b^{m - 1} \not\equiv 1 \pmod m }[/math]
Zatem przeprowadzając test Fermata, możemy z prawdopodobieństwem nie mniejszym niż [math]\displaystyle{ \tfrac{1}{2} }[/math] twierdzić, że liczba, która przeszła test, jest liczbą pierwszą. Wykonując test [math]\displaystyle{ k }[/math] razy dla [math]\displaystyle{ k }[/math] różnych podstaw z przedziału [math]\displaystyle{ [1, m - 1] }[/math] możemy z prawdopodobieństwem większym niż [math]\displaystyle{ 1 - \left( \tfrac{1}{2} \right)^k }[/math] twierdzić, że badana liczba [math]\displaystyle{ m }[/math] jest pierwsza.
Niestety, istnieją liczby złożone [math]\displaystyle{ m }[/math] takie, że
- [math]\displaystyle{ a^{m - 1} \equiv 1 \pmod m }[/math]
dla każdego [math]\displaystyle{ a }[/math] względnie pierwszego z [math]\displaystyle{ m }[/math]. Liczby te nazywamy liczbami Carmichaela i jest ich nieskończenie wiele. Pokazano, że dla dostatecznie dużych [math]\displaystyle{ x }[/math] ilość liczb Carmichaela mniejszych od [math]\displaystyle{ x }[/math] przekracza [math]\displaystyle{ x^{1/3} }[/math][1][2][3]. Test Fermata jest zatem zbyt zawodny, aby można było go stosować.
Przykład K11
Oto wszystkie liczby Carmichaela mniejsze od [math]\displaystyle{ 100 000 }[/math]
[math]\displaystyle{ 561=3⋅11⋅17 }[/math] |
[math]\displaystyle{ 1105=5⋅13⋅17 }[/math] |
[math]\displaystyle{ 1729=7⋅13⋅19 }[/math] |
[math]\displaystyle{ 2465=5⋅17⋅29 }[/math]
|
[math]\displaystyle{ 2821=7⋅13⋅31 }[/math] |
[math]\displaystyle{ 6601=7⋅23⋅41 }[/math] |
[math]\displaystyle{ 8911=7⋅19⋅67 }[/math] |
[math]\displaystyle{ 10585=5⋅29⋅73 }[/math]
|
[math]\displaystyle{ 15841=7⋅31⋅73 }[/math] |
[math]\displaystyle{ 29341=13⋅37⋅61 }[/math] |
[math]\displaystyle{ 41041=7⋅11⋅13⋅41 }[/math] |
[math]\displaystyle{ 46657=13⋅37⋅97 }[/math]
|
[math]\displaystyle{ 52633=7⋅73⋅103 }[/math] |
[math]\displaystyle{ 62745=3⋅5⋅47⋅89 }[/math] |
[math]\displaystyle{ 63973=7⋅13⋅19⋅37 }[/math] |
[math]\displaystyle{ 75361=11⋅13⋅17⋅31 }[/math]
|
Test Millera-Rabina
Rozpoczniemy od udowodnienia prostego twierdzenia
Twierdzenie K12
Jeśli [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ x^2 \equiv 1 \pmod m }[/math], to albo [math]\displaystyle{ x \equiv - 1 \pmod m }[/math], albo [math]\displaystyle{ x \equiv 1 \pmod m }[/math].
Dowód
Z założenia
- [math]\displaystyle{ x^2 \equiv 1 \pmod m }[/math]
Zatem [math]\displaystyle{ m | (x^2 - 1) }[/math], czyli [math]\displaystyle{ m | (x - 1) (x + 1) }[/math]. Ponieważ z założenia [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą, to [math]\displaystyle{ m }[/math] dzieli dokładnie jedną z liczb [math]\displaystyle{ x - 1 }[/math] i [math]\displaystyle{ x + 1 }[/math]. Istotnie, gdyby [math]\displaystyle{ m | (x - 1) }[/math] [math]\displaystyle{ \text{i} \;\, m | (x + 1) }[/math], to [math]\displaystyle{ m }[/math] dzieliłaby również ich różnicę równą [math]\displaystyle{ 2 }[/math], co jest niemożliwe w przypadku gdy [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą.
□
Prace Gary'ego Millera[4] i Michaela Rabina[5] pozwoliły sformułować znacznie silniejszy test. Podstawą tego testu jest następujące twierdzenie
Twierdzenie K13
Jeżeli [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ m - 1 = 2^r d }[/math], gdzie [math]\displaystyle{ d }[/math] jest liczbą nieparzystą, to dla dowolnego [math]\displaystyle{ a \in [1, m - 1] }[/math] jest albo
- [math]\displaystyle{ a^d \equiv 1 \pmod m }[/math]
albo
- [math]\displaystyle{ a^{2^k d} \equiv - 1 \pmod m }[/math]
dla pewnego [math]\displaystyle{ k \in [0, r - 1] }[/math].
Dowód
Rozważmy ciąg [math]\displaystyle{ r + 1 }[/math] liczb zdefiniowanych następująco
- [math]\displaystyle{ \begin{array}{l}
u_0 = a^d\\
u_1 = a^{2 d} = (a^d)^2\\
u_2 = a^{2^2 d} = (a^{2 d})^2\\
\ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots\\
u_{r - 1} = a^{2^{r - 1} d} = (a^{2^{r - 2}})^2\\
u_r = a^{2^r d} = (a^{2^{r - 1} d})^2 = a^{m - 1}
\end{array} }[/math]
Wyrazy ciągu [math]\displaystyle{ (u_i) }[/math] są dane wzorem ogólnym
- [math]\displaystyle{ u_i = a^{2^i d} }[/math]
gdzie [math]\displaystyle{ i = 0, 1, \ldots, r }[/math]
Zauważmy, że mogą zdarzyć się następujące sytuacje
- a) żaden z wyrazów ciągu [math]\displaystyle{ (u_i) }[/math] nie przystaje do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math]
- b) wszystkie wyrazy ciągu [math]\displaystyle{ (u_i) }[/math] przystają do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math]
- c) [math]\displaystyle{ u_k }[/math] jest pierwszym wyrazem ciągu [math]\displaystyle{ (u_i) }[/math], który przystaje do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math]
Co możemy zapisać jako
- a) [math]\displaystyle{ u_i \not\equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [0, r] }[/math]
- b) [math]\displaystyle{ u_i \equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [0, r] }[/math]
- c) [math]\displaystyle{ u_k \equiv 1 \pmod m \quad }[/math] dla pewnego [math]\displaystyle{ k \in [0, r] }[/math]
Z definicji każdy wyraz ciągu [math]\displaystyle{ (u_i) }[/math] jest kwadratem poprzedniego. W szczególności oznacza to, że jeżeli dla pewnego [math]\displaystyle{ k \in [0, r] }[/math] jest [math]\displaystyle{ u_k \equiv 1 \pmod m }[/math], to [math]\displaystyle{ u_i \equiv 1 \pmod m }[/math] dla wszystkich [math]\displaystyle{ i \geqslant k }[/math]. Ten fakt pozwala doprecyzować zapis poszczególnych przypadków.
- a) [math]\displaystyle{ u_i \not\equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [0, r] }[/math]
- b) [math]\displaystyle{ u_0 \equiv 1 \pmod m }[/math]
- c) [math]\displaystyle{ u_0 \not\equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [0, k - 1] \quad }[/math] oraz [math]\displaystyle{ \quad u_k \equiv 1 \pmod m \quad }[/math] dla każdego [math]\displaystyle{ i \in [k, r] , \quad }[/math] gdzie [math]\displaystyle{ k \geqslant 1 }[/math]
W przypadku a) mamy [math]\displaystyle{ u_r = a^{m - 1} \not\equiv 1 \pmod m }[/math], zatem liczba [math]\displaystyle{ m }[/math] byłaby liczbą złożoną, wbrew założeniu, że jest liczbą pierwszą.
Przypadek b) jest możliwy (np. dla [math]\displaystyle{ m = 41 }[/math] i [math]\displaystyle{ a = 10 }[/math]), ale nie pozwala powiedzieć nic więcej ani o liczbie [math]\displaystyle{ m }[/math], ani o wyrazach ciągu [math]\displaystyle{ (u_i) }[/math], które wszystkie przystają do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math].
W przypadku c) mamy [math]\displaystyle{ u_k \equiv 1 \pmod m }[/math], czyli [math]\displaystyle{ (u_{k - 1})^2 \equiv 1 \pmod m }[/math]. Z twierdzenia K12 wiemy, że musi być albo [math]\displaystyle{ u_{k - 1} \equiv - 1 \pmod m }[/math], albo [math]\displaystyle{ u_{k - 1} \equiv 1 \pmod m }[/math]. Ale drugi przypadek nie może zachodzić, bo założyliśmy, że [math]\displaystyle{ u_k }[/math] jest pierwszym wyrazem ciągu [math]\displaystyle{ (u_i) }[/math], który przystaje do [math]\displaystyle{ 1 }[/math] modulo [math]\displaystyle{ m }[/math]. Zatem musi być [math]\displaystyle{ u_{k - 1} \equiv - 1 \pmod m }[/math].
Co kończy dowód twierdzenia.
□
Definicja K14
Złożoną liczbę nieparzystą [math]\displaystyle{ m }[/math], która spełnia twierdzenie K13 dla pewnej liczby [math]\displaystyle{ a \in \mathbb{Z} }[/math], będziemy nazywali liczbą silnie pseudopierwszą przy podstawie [math]\displaystyle{ a }[/math] (w skrócie: SPSP([math]\displaystyle{ a }[/math])).
Uwaga K15
Niech [math]\displaystyle{ a }[/math] będzie liczbą całkowitą względnie pierwszą z [math]\displaystyle{ m }[/math] i [math]\displaystyle{ a \in [1, m - 1] }[/math]. Można pokazać, że jeżeli [math]\displaystyle{ m \neq 9 }[/math] jest liczbą nieparzystą złożoną, to co najwyżej [math]\displaystyle{ \tfrac{1}{4} }[/math] liczb [math]\displaystyle{ a }[/math] stanowią liczby silnie pseudopierwsze. Zatem w przypadku liczb silnie pseudopierwszych nie istnieje odpowiednik liczb Carmichaela. Czyli nie istnieją liczby złożone nieparzyste [math]\displaystyle{ m }[/math], dla których twierdzenie K13 byłoby prawdziwe dla wszystkich podstaw [math]\displaystyle{ a }[/math].
Wynika stąd, że jeżeli dla [math]\displaystyle{ k }[/math] różnych liczb [math]\displaystyle{ a }[/math] prawdziwe jest twierdzenie K13, to prawdopodobieństwo uznania liczby złożonej [math]\displaystyle{ m }[/math] za pierwszą wynosi [math]\displaystyle{ \left( \tfrac{1}{4} \right)^k }[/math].
Uwaga K16
Wykorzystując twierdzenie K13, możemy napisać w PARI/GP prosty program do testowania pierwszości liczb.
isPrimeOrSPSP(m, a) =
{
local(d, k, r, x);
if( m % 2 == 0, return(m == 2) );
r = valuation(m - 1, 2); \\ wykładnik, z jakim liczba 2 występuje w rozwinięciu na czynniki pierwsze liczby m - 1
d = (m - 1) / 2^r;
x = modPower(a, d, m);
if( x == 1 || x == m - 1, return(1) ); \\ x = m - 1 to przypadek k == 0
k = 0;
while( k++ < r,
x = x^2 % m;
if( x == m - 1, return(1) );
);
return(0);
}
Zadanie K17
Pokazać, że jeżeli liczba [math]\displaystyle{ m }[/math] jest SPSP([math]\displaystyle{ a }[/math]), to jest PSP([math]\displaystyle{ a }[/math]).
Rozwiązanie
Z założenia [math]\displaystyle{ m }[/math] jest SPSP([math]\displaystyle{ a }[/math]), zatem spełniony jest dokładnie jeden z warunków
- [math]\displaystyle{ a^d \equiv 1 \pmod m }[/math]
- [math]\displaystyle{ a^{2^k \cdot d} \equiv - 1 \pmod m }[/math], dla pewnego [math]\displaystyle{ k \in [0, r - 1] }[/math]
gdzie [math]\displaystyle{ m - 1 = 2^r \cdot d }[/math], przy czym [math]\displaystyle{ d }[/math] jest liczbą nieparzystą.
Jeżeli spełniony jest pierwszy warunek, to
- [math]\displaystyle{ (a^d)^{2^r} \equiv 1 \pmod m }[/math]
- [math]\displaystyle{ a^{2^r \cdot d} \equiv 1 \pmod m }[/math]
Czyli [math]\displaystyle{ m }[/math] jest PSP([math]\displaystyle{ a }[/math]).
Jeżeli spełniony jest drugi warunek, to
- [math]\displaystyle{ (a^{2^k \cdot d})^{2^{r - k}} \equiv (- 1)^{2^{r - k}} \pmod m }[/math]
- [math]\displaystyle{ a^{2^r \cdot d} \equiv 1 \pmod m }[/math]
Czyli [math]\displaystyle{ m }[/math] jest PSP([math]\displaystyle{ a }[/math]).
□
Przykład K18
Pokażemy, że jeżeli [math]\displaystyle{ m }[/math] jest PSP([math]\displaystyle{ 2 }[/math]), to [math]\displaystyle{ 2^m - 1 }[/math] jest SPSP([math]\displaystyle{ 2 }[/math]).
Z założenia [math]\displaystyle{ m }[/math] jest złożoną liczbą nieparzystą, zatem [math]\displaystyle{ N = 2^m - 1 }[/math] jest złożoną liczbą nieparzystą. Ponieważ [math]\displaystyle{ m }[/math] jest FPSP([math]\displaystyle{ 2 }[/math]), to
- [math]\displaystyle{ 2^{m - 1} \equiv 1 \pmod m }[/math]
Wynika stąd natychmiast, że [math]\displaystyle{ 2^{m - 1} - 1 = k m }[/math], gdzie [math]\displaystyle{ k }[/math] jest liczbą nieparzystą. Zatem
- [math]\displaystyle{ N - 1 = 2^m - 2 = 2 (2^{m - 1} - 1) = 2 k m }[/math]
Widzimy, że liczba [math]\displaystyle{ 2 }[/math] występuje w pierwszej potędze w rozwinięciu liczby [math]\displaystyle{ N - 1 }[/math] na czynniki pierwsze i łatwo otrzymujemy, że
- [math]\displaystyle{ 2^{(N - 1) / 2} = 2^{k m} = (2^m)^k = (2^m - 1 + 1)^k = (N + 1)^k \equiv 1 \pmod N }[/math]
Czyli [math]\displaystyle{ N = 2^m - 1 }[/math] jest SPSP([math]\displaystyle{ 2 }[/math]).
Przykład K19
Tabela zawiera najmniejsze liczby silnie pseudopierwsze dla podstaw [math]\displaystyle{ a }[/math] od [math]\displaystyle{ 2 }[/math] do [math]\displaystyle{ 15 }[/math]
for(a=2, 15, s=1; forstep(m=3, 20000, 2, if( isPrimeOrSPSP(m, a) && !isprime(m), print("a=", a, " m=", m); s++ ); if( s>5, break() ) ))
[math]\displaystyle{ \boldsymbol{a} }[/math] |
[math]\displaystyle{ \boldsymbol{2} }[/math] |
[math]\displaystyle{ \boldsymbol{3} }[/math] |
[math]\displaystyle{ \boldsymbol{4} }[/math] |
[math]\displaystyle{ \boldsymbol{5} }[/math] |
[math]\displaystyle{ \boldsymbol{6} }[/math] |
[math]\displaystyle{ \boldsymbol{7} }[/math] |
[math]\displaystyle{ \boldsymbol{8} }[/math] |
[math]\displaystyle{ \boldsymbol{9} }[/math] |
[math]\displaystyle{ \boldsymbol{10} }[/math] |
[math]\displaystyle{ \boldsymbol{11} }[/math] |
[math]\displaystyle{ \boldsymbol{12} }[/math] |
[math]\displaystyle{ \boldsymbol{13} }[/math] |
[math]\displaystyle{ \boldsymbol{14} }[/math] |
[math]\displaystyle{ \boldsymbol{15} }[/math]
|
|
[math]\displaystyle{ 2047 }[/math] |
[math]\displaystyle{ 121 }[/math] |
[math]\displaystyle{ 341 }[/math] |
[math]\displaystyle{ 781 }[/math] |
[math]\displaystyle{ 217 }[/math] |
[math]\displaystyle{ 25 }[/math] |
[math]\displaystyle{ 9 }[/math] |
[math]\displaystyle{ 91 }[/math] |
[math]\displaystyle{ 9 }[/math] |
[math]\displaystyle{ 133 }[/math] |
[math]\displaystyle{ 91 }[/math] |
[math]\displaystyle{ 85 }[/math] |
[math]\displaystyle{ 15 }[/math] |
[math]\displaystyle{ 1687 }[/math]
|
|
[math]\displaystyle{ 3277 }[/math] |
[math]\displaystyle{ 703 }[/math] |
[math]\displaystyle{ 1387 }[/math] |
[math]\displaystyle{ 1541 }[/math] |
[math]\displaystyle{ 481 }[/math] |
[math]\displaystyle{ 325 }[/math] |
[math]\displaystyle{ 65 }[/math] |
[math]\displaystyle{ 121 }[/math] |
[math]\displaystyle{ 91 }[/math] |
[math]\displaystyle{ 793 }[/math] |
[math]\displaystyle{ 133 }[/math] |
[math]\displaystyle{ 1099 }[/math] |
[math]\displaystyle{ 841 }[/math] |
[math]\displaystyle{ 3277 }[/math]
|
|
[math]\displaystyle{ 4033 }[/math] |
[math]\displaystyle{ 1891 }[/math] |
[math]\displaystyle{ 2047 }[/math] |
[math]\displaystyle{ 5461 }[/math] |
[math]\displaystyle{ 1111 }[/math] |
[math]\displaystyle{ 703 }[/math] |
[math]\displaystyle{ 481 }[/math] |
[math]\displaystyle{ 671 }[/math] |
[math]\displaystyle{ 1729 }[/math] |
[math]\displaystyle{ 2047 }[/math] |
[math]\displaystyle{ 145 }[/math] |
[math]\displaystyle{ 5149 }[/math] |
[math]\displaystyle{ 2743 }[/math] |
[math]\displaystyle{ 6541 }[/math]
|
|
[math]\displaystyle{ 4681 }[/math] |
[math]\displaystyle{ 3281 }[/math] |
[math]\displaystyle{ 3277 }[/math] |
[math]\displaystyle{ 5611 }[/math] |
[math]\displaystyle{ 1261 }[/math] |
[math]\displaystyle{ 2101 }[/math] |
[math]\displaystyle{ 511 }[/math] |
[math]\displaystyle{ 703 }[/math] |
[math]\displaystyle{ 4187 }[/math] |
[math]\displaystyle{ 4577 }[/math] |
[math]\displaystyle{ 247 }[/math] |
[math]\displaystyle{ 7107 }[/math] |
[math]\displaystyle{ 3277 }[/math] |
[math]\displaystyle{ 14041 }[/math]
|
|
[math]\displaystyle{ 8321 }[/math] |
[math]\displaystyle{ 8401 }[/math] |
[math]\displaystyle{ 4033 }[/math] |
[math]\displaystyle{ 7813 }[/math] |
[math]\displaystyle{ 2701 }[/math] |
[math]\displaystyle{ 2353 }[/math] |
[math]\displaystyle{ 1417 }[/math] |
[math]\displaystyle{ 1541 }[/math] |
[math]\displaystyle{ 6533 }[/math] |
[math]\displaystyle{ 5041 }[/math] |
[math]\displaystyle{ 1649 }[/math] |
[math]\displaystyle{ 8911 }[/math] |
[math]\displaystyle{ 5713 }[/math] |
[math]\displaystyle{ 14701 }[/math]
|
Przykład K20
Tabela pokazuje ilość liczb silnie pseudopierwszych dla podstaw [math]\displaystyle{ a }[/math] od [math]\displaystyle{ 2 }[/math] do [math]\displaystyle{ 15 }[/math]
for(a=2, 15, s=0; forstep(k=3, 10^6, 2, if( isPrimeOrSPSP(k, a) && !isprime(k), s++ )); print("a= ", a, " ", s))
[math]\displaystyle{ \boldsymbol{a} }[/math] |
[math]\displaystyle{ \boldsymbol{2} }[/math] |
[math]\displaystyle{ \boldsymbol{3} }[/math] |
[math]\displaystyle{ \boldsymbol{4} }[/math] |
[math]\displaystyle{ \boldsymbol{5} }[/math] |
[math]\displaystyle{ \boldsymbol{6} }[/math] |
[math]\displaystyle{ \boldsymbol{7} }[/math] |
[math]\displaystyle{ \boldsymbol{8} }[/math] |
[math]\displaystyle{ \boldsymbol{9} }[/math] |
[math]\displaystyle{ \boldsymbol{10} }[/math] |
[math]\displaystyle{ \boldsymbol{11} }[/math] |
[math]\displaystyle{ \boldsymbol{12} }[/math] |
[math]\displaystyle{ \boldsymbol{13} }[/math] |
[math]\displaystyle{ \boldsymbol{14} }[/math] |
[math]\displaystyle{ \boldsymbol{15} }[/math]
|
#SPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^6 }[/math] |
[math]\displaystyle{ 46 }[/math] |
[math]\displaystyle{ 73 }[/math] |
[math]\displaystyle{ 97 }[/math] |
[math]\displaystyle{ 64 }[/math] |
[math]\displaystyle{ 73 }[/math] |
[math]\displaystyle{ 66 }[/math] |
[math]\displaystyle{ 127 }[/math] |
[math]\displaystyle{ 161 }[/math] |
[math]\displaystyle{ 62 }[/math] |
[math]\displaystyle{ 58 }[/math] |
[math]\displaystyle{ 90 }[/math] |
[math]\displaystyle{ 71 }[/math] |
[math]\displaystyle{ 74 }[/math] |
[math]\displaystyle{ 45 }[/math]
|
#SPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^7 }[/math] |
[math]\displaystyle{ 162 }[/math] |
[math]\displaystyle{ 207 }[/math] |
[math]\displaystyle{ 305 }[/math] |
[math]\displaystyle{ 199 }[/math] |
[math]\displaystyle{ 203 }[/math] |
[math]\displaystyle{ 177 }[/math] |
[math]\displaystyle{ 377 }[/math] |
[math]\displaystyle{ 459 }[/math] |
[math]\displaystyle{ 158 }[/math] |
[math]\displaystyle{ 157 }[/math] |
[math]\displaystyle{ 251 }[/math] |
[math]\displaystyle{ 193 }[/math] |
[math]\displaystyle{ 190 }[/math] |
[math]\displaystyle{ 148 }[/math]
|
#SPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^8 }[/math] |
[math]\displaystyle{ 488 }[/math] |
[math]\displaystyle{ 582 }[/math] |
[math]\displaystyle{ 833 }[/math] |
[math]\displaystyle{ 475 }[/math] |
[math]\displaystyle{ 486 }[/math] |
[math]\displaystyle{ 446 }[/math] |
[math]\displaystyle{ 1023 }[/math] |
[math]\displaystyle{ 1241 }[/math] |
[math]\displaystyle{ 437 }[/math] |
[math]\displaystyle{ 430 }[/math] |
[math]\displaystyle{ 666 }[/math] |
[math]\displaystyle{ 472 }[/math] |
[math]\displaystyle{ 440 }[/math] |
[math]\displaystyle{ 398 }[/math]
|
#SPSP([math]\displaystyle{ a }[/math]) [math]\displaystyle{ \lt 10^9 }[/math] |
[math]\displaystyle{ 1282 }[/math] |
[math]\displaystyle{ 1514 }[/math] |
[math]\displaystyle{ 2162 }[/math] |
[math]\displaystyle{ 1268 }[/math] |
[math]\displaystyle{ 1232 }[/math] |
[math]\displaystyle{ 1163 }[/math] |
[math]\displaystyle{ 2599 }[/math] |
[math]\displaystyle{ 3210 }[/math] |
[math]\displaystyle{ 1113 }[/math] |
[math]\displaystyle{ 1125 }[/math] |
[math]\displaystyle{ 1655 }[/math] |
[math]\displaystyle{ 1142 }[/math] |
[math]\displaystyle{ 1151 }[/math] |
[math]\displaystyle{ 1041 }[/math]
|
Widzimy, że liczb silnie pseudopierwszych jest znacznie mniej niż liczb pseudopierwszych Fermata.
Uwaga K21
Interesujące i pożyteczne będzie zbadanie najmniejszych liczb silnie pseudopierwszych dla wielu podstaw. Niech badanymi podstawami będą kolejne liczby pierwsze. Najmniejszą liczbę SPSP([math]\displaystyle{ 2 }[/math]) już znamy: [math]\displaystyle{ 2047 }[/math]. Najmniejszą liczbę, która jest jednocześnie SPSP([math]\displaystyle{ 2 }[/math]) i SPSP([math]\displaystyle{ 3 }[/math]) musimy poszukać. Prostym poleceniem
forstep(m=3, 2*10^6, 2, if( isPrimeOrSPSP(m, 2) && isPrimeOrSPSP(m, 3) && !isprime(m), print("m=", m) ) )
znajdujemy, że [math]\displaystyle{ m = 1373653 }[/math]. Więcej czasu będzie wymagało znalezienie liczby jednocześnie silnie pseudopierwszej względem podstaw [math]\displaystyle{ 2, 3, 5 }[/math]. Poleceniem
forstep(m=3, 26*10^6, 2, if( isPrimeOrSPSP(m, 2) && isPrimeOrSPSP(m, 3) && isPrimeOrSPSP(m, 5) && !isprime(m), print("m=", m) ) )
znajdujemy, że szukana liczba to [math]\displaystyle{ m = 25326001 }[/math].
Stosując bardziej wyrafinowane metody[6][7] znaleziono wartości liczb silnie pseudopierwszych względem wielu podstaw, które są kolejnymi liczbami pierwszymi, dla większej ilości liczb pierwszych[8]. Dla przykładu
[math]\displaystyle{ \boldsymbol{n} }[/math] |
[math]\displaystyle{ \boldsymbol{m} }[/math]
|
[math]\displaystyle{ 1 }[/math] |
[math]\displaystyle{ 2047 }[/math]
|
[math]\displaystyle{ 2 }[/math] |
[math]\displaystyle{ 1373653 }[/math]
|
[math]\displaystyle{ 3 }[/math] |
[math]\displaystyle{ 25326001 }[/math]
|
[math]\displaystyle{ 4 }[/math] |
[math]\displaystyle{ 3215031751 }[/math]
|
[math]\displaystyle{ 5 }[/math] |
[math]\displaystyle{ 2152302898747 }[/math]
|
[math]\displaystyle{ 6 }[/math] |
[math]\displaystyle{ 3474749660383 }[/math]
|
[math]\displaystyle{ 7 }[/math] |
[math]\displaystyle{ 341550071728321 }[/math]
|
Podane w prawej kolumnie liczby [math]\displaystyle{ m }[/math] są najmniejszymi liczbami jednocześnie silnie pseudopierwszymi względem podstaw [math]\displaystyle{ p_1, \ldots, p_n }[/math]. Zauważmy, że wyniki te mają bardzo praktyczne zastosowanie. Przykładowo, jeśli [math]\displaystyle{ m }[/math] przechodzi test Millera-Rabina dla siedmiu podstaw [math]\displaystyle{ a = 2, 3, 5, 7, 11, 13, 17 }[/math] i jest liczbą mniejszą od [math]\displaystyle{ 3.41 \cdot 10^{14} }[/math], to jest z pewnością liczbą pierwszą.
Uzupełnienie
Uwaga K22
W funkcji isPrimeOrSPSP()
wykorzystaliśmy zaimplementowane w PARI/GP funkcje:
gcd(a, b)
– znajduje największy wspólny dzielnik liczb a i b
valuation(a, b)
– znajduje największą wartość liczby [math]\displaystyle{ r }[/math] taką, że [math]\displaystyle{ b^r | a }[/math]
Wprowadzenie tych funkcji pozwoliło zwiększyć czytelność kodu, ale bez trudu możemy sami je napisać:
gcd2(a, b) =
{
while( b <> 0, a = b; b = a % b );
return(a);
}
valuation2(a, b) =
{
local(s);
s = 0;
while(a % b == 0, s++; a = a / b);
return(s);
}
Przypisy
- ↑ W. R. Alford, Andrew Granville and Carl Pomerance, There are Infinitely Many Carmichael Numbers, Annals of Mathematics, 140, (1994), 703-722
- ↑ Glyn Harman, On the Number of Carmichael Numbers up to x, Bull. London Math. Soc. 37 (2005) 641–650
- ↑ Glyn Harman, Watt’s Mean Value Theorem and Carmichael Numbers, International Journal of Number Theory, Vol. 4, No. 2 (2008) 241–248
- ↑ Gary L. Miller, Riemann's Hypothesis and Tests for Primality, Journal of Computer and System Sciences 13, 300-317 (1976)
- ↑ Michael O. Rabin, Probabilistic Algorithm for Testing Primality, Journal of Number Theory 12, 128-138 (1980)
- ↑ Carl Pomerance, J. L. Selfridge and Samuel S. Wagstaff, Jr., The Pseudoprimes to 25*10^9, Mathematics of Computation, Vol. 35, No. 151 (1980), 1003-1026
- ↑ Gerhard Jaeschke, On Strong Pseudoprimes to Several Bases, Mathematics of Computation, Vol. 61, No. 204 (Oct., 1993), 915-926
- ↑ On-Line Encyclopedia of Integer Sequences, Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness, (A014233)