Tekst źródłowy strony Rząd liczby modulo i generatory modulo. Kongruencje wielomianowe. Lemat Hensela

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

__FORCETOC__



== Rząd liczby modulo ==

<span id="L1" style="font-size: 110%; font-weight: bold;">Uwaga L1</span><br/>
Niech <math>a \in \mathbb{Z}</math>, <math>m \in \mathbb{Z}_+</math> oraz <math>\gcd (a, m) = 1</math>. Z&nbsp;twierdzenia Eulera (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J27|J27]]) wynika natychmiast, że zbiór <math>S</math> złożony z&nbsp;liczb <math>t \in \mathbb{Z}_+</math> takich, że <math>a^t \equiv 1 \!\! \pmod{m}</math> nie jest zbiorem pustym. Jeśli tak, to zbiór <math>S</math> ma element najmniejszy. Wynika stąd poprawność następującej definicji.



<span id="L2" style="font-size: 110%; font-weight: bold;">Definicja L2</span><br/>
Niech <math>a \in \mathbb{Z}</math>, <math>m \in \mathbb{Z}_+</math> oraz <math>\gcd (a, m) = 1</math>. Rzędem liczby <math>a</math> modulo <math>m</math><ref name="order1"/> nazywamy najmniejszą liczbę całkowitą dodatnią <math>h</math> taką, że

::<math>a^h \equiv 1 \!\! \pmod{m}</math>

Liczbę tę będziemy oznaczali następująco <math>h = \operatorname{ord}(a, m)</math>.



<span id="L3" style="font-size: 110%; font-weight: bold;">Uwaga L3</span><br/>

:*&nbsp;&nbsp;&nbsp;z twierdzenia Eulera wynika oszacowanie <math>\operatorname{ord}(a, m) \leqslant \varphi (m)</math>
:*&nbsp;&nbsp;&nbsp;jeżeli <math>\operatorname{ord}(a, m) = h</math>, to <math>\gcd (a, m) = 1</math>, bo gdyby było <math>\gcd (a, m) = d > 1</math>, to z&nbsp;kongruencji <math>a^h \equiv 1 \!\! \pmod{m}</math> mielibyśmy natychmiast <math>0 \equiv 1 \!\! \pmod{d}</math>
:*&nbsp;&nbsp;&nbsp;<math>\operatorname{ord}(1, m) = 1</math> dla <math>m \geqslant 1 \;</math> i <math>\; \operatorname{ord}(- 1, m) = 2</math> dla <math>m \geqslant 3</math>
:*&nbsp;&nbsp;&nbsp;rząd liczby <math>a</math> modulo <math>m</math> łatwo znajdziemy, wpisując w&nbsp;PARI/GP polecenie <code><span style="font-size: 90%; color:black;">znorder(Mod(a, m))</span></code>



<span id="L4" style="font-size: 110%; font-weight: bold;">Przykład L4</span><br/>
Zauważmy, że modulo <math>15</math> jest

::<math>2^1 \equiv 2, \qquad 2^2 \equiv 4, \qquad 2^3 \equiv 8, \qquad 2^4 \equiv 1</math>

Zatem <math>\operatorname{ord}(2, 15) = 4</math>. Czytelnik równie łatwo pokaże, że <math>\operatorname{ord}(5, 21) = 6 \;</math> i <math>\; \operatorname{ord}(3, 11) = 5</math>.



<span id="L5" style="font-size: 110%; font-weight: bold;">Twierdzenie L5</span><br/>
Niech <math>a \in \mathbb{Z} \;</math> i <math>\; m \in \mathbb{Z}_+</math>. Jeżeli rząd liczby <math>a</math> modulo <math>m</math> jest równy <math>h</math>, to liczby <math>a, a^2, \ldots, a^h</math> są różne modulo <math>m</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Przypuśćmy, dla uzyskania sprzeczności, że <math>a^i \equiv a^j \!\! \pmod{m}</math> dla różnych liczb <math>1 \leqslant i, j \leqslant h</math>. Nie zmniejszając ogólności, możemy założyć, że <math>i > j</math>. Czyli <math>1 \leqslant i - j \leqslant h - 1</math> i&nbsp;otrzymujemy

::<math>a^j (a^{i - j} - 1) \equiv 0 \!\! \pmod{m}</math>

Ponieważ <math>\gcd (a, m) = 1</math>, to <math>m</math> musi dzielić wyrażenie <math>a^{i - j} - 1</math> (zobacz [[Ciągi liczbowe#C75|C75]]). Zatem

::<math>a^{i - j} - 1 \equiv 0 \!\! \pmod{m}</math>

::<math>a^{i - j} \equiv 1 \!\! \pmod{m}</math>

Wbrew założeniu, że rząd liczby <math>a</math> modulo <math>m</math> jest równy <math>h</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L6" style="font-size: 110%; font-weight: bold;">Zadanie L6</span><br/>
Niech <math>n \in \mathbb{Z}_+</math> i <math>p</math> będzie liczbą pierwszą nieparzystą. Pokazać, że jeżeli

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

to <math>2 n</math> nie może być rzędem liczby <math>a</math> modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Przypuśćmy, dla uzyskania sprzeczności, że <math>2 n</math> jest rzędem <math>a</math> modulo <math>p</math>. Z&nbsp;definicji mamy

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

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

Liczba pierwsza <math>p</math> może dzielić tylko jeden z&nbsp;wypisanych czynników. Istotnie, gdyby dzieliła obydwa, to dzieliłaby również ich różnicę i&nbsp;mielibyśmy <math>p \mid 2</math>. Co jest niemożliwe, bo <math>p \geqslant 3</math>. Zatem prawdziwa musi być dokładnie jedna z&nbsp;kongruencji

::<math>a^n \equiv - 1 \!\! \pmod{p} \qquad \qquad \text{albo} \qquad \qquad a^n \equiv 1 \!\! \pmod{p}</math>

Pierwsza z&nbsp;kongruencji nie może zachodzić, bo byłoby to sprzeczne z&nbsp;założeniem twierdzenia. Wynika stąd, że musi być

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

Co oznacza, że <math>\operatorname{ord}(a, p) \leqslant n < 2 n</math> wbrew uczynionemu przez nas przypuszczeniu. Uzyskana sprzeczność pokazuje, że <math>2 n</math> nie może być rzędem <math>a</math> modulo <math>p</math>.

'''Uwaga''': wynik ten nie oznacza, że jeżeli <math>a^n \equiv - 1 \!\! \pmod{p}</math>, to <math>2 n</math> jest rzędem liczby <math>a</math> modulo <math>p</math>. Dla przykładu

::<math>13^6 \equiv - 1 \!\! \pmod{17}</math>

ale <math>\operatorname{ord}(13, 17) = 4 \neq 2 \cdot 6</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L7" style="font-size: 110%; font-weight: bold;">Twierdzenie L7</span><br/>
Niech <math>m \in \mathbb{Z}_+ \:</math> i <math>\; \gcd (a, m) = 1</math>. Rzędy liczb <math>a</math> i <math>a^{- 1}</math> modulo <math>m</math> są równe.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Ponieważ z&nbsp;założenia <math>\gcd (a, m) = 1</math>, to liczba <math>a</math> ma element odwrotny modulo <math>m</math> (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H17|H17]], [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H18|H18]]). Dla uproszczenia zapisu rozważmy liczby <math>x, y</math> takie, że

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

Pokażemy, że <math>\operatorname{ord}(x, m) = \operatorname{ord}(y, m)</math>. Przypuśćmy, w&nbsp;celu uzyskania sprzeczności, że rzędy liczb <math>x, y</math> modulo <math>m</math> są różne. Nie zmniejszając ogólności, możemy założyć, że <math>\operatorname{ord}(x, m) < \operatorname{ord}(y, m)</math>. Niech <math>h = \operatorname{ord}(x, m)</math>. Ponieważ <math>h</math> jest rzędem liczby <math>x</math> modulo <math>m</math>, to

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

::<math>x^h y^h \equiv y^h \!\! \pmod{m}</math>

::<math>(x y)^h \equiv y^h \!\! \pmod{m}</math>

::<math>1 \equiv y^h \!\! \pmod{m}</math>

Zatem <math>\operatorname{ord}(y, m) \leqslant h</math> (zobacz [[#L2|L2]]). Wynika stąd ciąg nierówności

::<math>\operatorname{ord}(x, m) < \operatorname{ord}(y, m) \leqslant \operatorname{ord}(x, m)</math>

Co jest niemożliwe. Uzyskana sprzeczność kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span id="L8" style="font-size: 110%; font-weight: bold;">Twierdzenie L8</span><br/>
Niech <math>m, n \in \mathbb{Z}_+</math>, zaś <math>a</math> liczbą całkowitą taką, że <math>\gcd (a, m) = 1</math>, wtedy

:*&nbsp;&nbsp;&nbsp;<math>a^w \equiv 1 \!\! \pmod{m} \quad \qquad \Longleftrightarrow \qquad \quad \operatorname{ord}(a, m) \mid w</math>

:*&nbsp;&nbsp;&nbsp;<math>m \mid n \qquad \qquad \Longrightarrow \qquad \qquad \operatorname{ord}(a, m) \mid \operatorname{ord}(a, n)</math>

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

'''Punkt 1.'''

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

Niech <math>h = \operatorname{ord}(a, m)</math>. Z&nbsp;twierdzenia o&nbsp;dzieleniu z&nbsp;resztą możemy napisać <math>w = k \cdot h + r</math>, gdzie <math>r \in [0, h - 1]</math>, zatem

::<math>a^w = a^{k h + r} = (a^h)^k \cdot a^r \equiv 1^k \cdot a^r \equiv a^r \equiv 1 \!\! \pmod{m}</math>

Ponieważ <math>h</math> jest z&nbsp;definicji najmniejszą liczbą dodatnią, dla której <math>a^h \equiv 1 \!\! \pmod{m}</math> oraz <math>r < h</math>, to musi być <math>r = 0</math>, co oznacza, że <math>h \mid w</math>.

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

Jeżeli <math>h</math> jest dzielnikiem wykładnika <math>w</math>, to istnieje liczba <math>s</math> taka, że <math>w = s \cdot h</math>, zatem

::<math>a^w = a^{s h} = (a^h)^s \equiv 1^s \equiv 1 \!\! \pmod{m}</math>

Co należało pokazać.

'''Punkt 2.'''

Niech <math>h = \operatorname{ord}(a, m)</math> oraz <math>f = \operatorname{ord}(a, n)</math>. Z&nbsp;założenia <math>m \mid n</math>, zatem z&nbsp;kongruencji <math>a^f \equiv 1 \!\! \pmod{n}</math> wynika kongruencja <math>a^f \equiv 1 \!\! \pmod{m}</math>. Ponieważ rząd liczby <math>a</math> modulo <math>m</math> jest równy <math>h</math>, to wykładnik <math>f</math> musi być wielokrotnością <math>h</math> (zobacz punkt 1.), czyli <math>h \mid f</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L9" style="font-size: 110%; font-weight: bold;">Zadanie L9</span><br/>
Niech <math>m \in \mathbb{Z}_+ \:</math> i <math>\; p</math> będzie liczbą pierwszą. Pokazać, że jeżeli <math>\gcd (a, m) = 1</math>, to <math>\operatorname{ord}(a, m) \mid \varphi (m)</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Z twierdzenia Eulera wiemy, że <math>a^{\varphi (m)} \equiv 1 \!\! \pmod{m}</math>, zatem <math>\varphi (m)</math> musi być wielokrotnością rzędu liczby <math>a</math> modulo <math>m</math> (zobacz [[#L8|L8]] p.1). Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L10" style="font-size: 110%; font-weight: bold;">Uwaga L10</span><br/>
Z zadania [[#L9|L9]] wynika, że w&nbsp;czasie znajdowania rzędu liczby możemy ograniczyć się do rozpatrywania jedynie dzielników <math>\varphi (m)</math>. Znajdźmy rząd liczby <math>3</math> modulo <math>37</math>. Dzielnikami <math>\varphi (37) = 36</math> są liczby <math>1, 2, 3, 4, 6, 9, 12, 18, 36</math>. Sprawdzając, otrzymujemy modulo <math>37</math>

::<math>3^1 \equiv 3, \qquad 3^2 \equiv 9, \qquad 3^3 \equiv 27 \equiv - 10, \qquad 3^4 \equiv - 10 \cdot 3 \equiv 7, \qquad 3^6 \equiv 100 \equiv - 11, \qquad 3^9 \equiv 110 \equiv - 1, \qquad 3^{12} \equiv 10, \qquad 3^{18} \equiv 1</math>

Zatem <math>\operatorname{ord}(3, 37) = 18</math>.



<span id="L11" style="font-size: 110%; font-weight: bold;">Zadanie L11</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Pokazać, że jeżeli <math>p \mid (n^2 + 1)</math>, to <math>p</math> jest postaci <math>4 k + 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Z założenia <math>n^2 + 1 \equiv 0 \!\! \pmod{p}</math>, czyli <math>n^2 \equiv - 1 \!\! \pmod{p}</math>, zatem <math>n^4 \equiv 1 \!\! \pmod{p}</math>.

Nie może być <math>n \equiv 1 \!\! \pmod{p}</math>, bo mielibyśmy <math>n^2 \equiv 1 \!\! \pmod{p}</math>. Z&nbsp;założenia nie jest <math>n^2 \equiv 1 \!\! \pmod{p}</math>. Nie może też być <math>n^3 \equiv 1 \!\! \pmod{p}</math>, bo mielibyśmy <math>- n \equiv 1 \!\! \pmod{p}</math> i&nbsp;ponownie <math>n^2 \equiv 1 \!\! \pmod{p}</math>. Zatem rząd liczby <math>n</math> modulo <math>p</math> wynosi <math>4</math>. Z&nbsp;zadania [[#L9|L9]] mamy <math>4 \mid \varphi (p)</math>, czyli <math>4 \mid (p - 1)</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L12" style="font-size: 110%; font-weight: bold;">Zadanie L12</span><br/>
Jeżeli <math>n \in \mathbb{Z}_+ \:</math> i <math>\; a \geqslant 2</math>, to liczba <math>n</math> jest dzielnikiem <math>\varphi (a^n - 1)</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Łatwo widzimy, że <math>\gcd (a, a^n - 1) = 1</math>. Niech <math>\operatorname{ord}(a, a^n - 1) = h</math>.

Oczywiście <math>(a^n - 1) \mid (a^n - 1)</math>, czyli <math>a^n \equiv 1 \!\! \pmod{a^n - 1}</math>, zatem <math>h \leqslant n</math>.

Dla wykładników <math>r < n</math> dostajemy <math>a^r - 1 < a^n - 1</math> i&nbsp;nie może być <math>(a^n - 1) \mid (a^r - 1)</math>, bo większa liczba nie może dzielić mniejszej.

Zatem dla <math>r < n</math> mamy <math>a^r \not\equiv 1 \!\! \pmod{a^n - 1}</math>. Wynika stąd, że <math>h = n</math>. Ponieważ <math>\operatorname{ord}(a, a^n - 1) = n</math>, to <math>n \mid \varphi (a^n - 1)</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L13" style="font-size: 110%; font-weight: bold;">Zadanie L13</span><br/>
Niech <math>a, m, n \in \mathbb{Z}_+</math>. Pokazać, że <math>\gcd (a^m - 1, a^n - 1) = a^{\gcd (m, n)} - 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zauważmy, że prawdziwy jest następujący ciąg równoważności.


::<math>\begin{array}{lcll}
d \mid \gcd (a^m - 1, a^n - 1) & \qquad \Longleftrightarrow \qquad & d \mid (a^m - 1) \qquad \; \text{i} \qquad \; d \mid (a^m - 1) & \quad \text{(zobacz H3)} \\
 & & & \\
 & \qquad \Longleftrightarrow \qquad & a^m \equiv 1 \; \pmod{d} \qquad \text{i} \qquad a^n \equiv 1 \; \pmod{d} & \\
 & & & \\
 & \qquad \Longleftrightarrow \qquad & \operatorname{ord}(a, d) \mid m \qquad \text{i} \qquad \operatorname{ord}(a, d) \mid n & \quad \text{(zobacz L8 p.1)} \\
 & & & \\
 & \qquad \Longleftrightarrow \qquad & \operatorname{ord}(a, d) \mid \gcd (m, n) & \quad \text{(zobacz H3)} \\
 & & & \\
 & \qquad \Longleftrightarrow \qquad & a^{\gcd (m, n)} \equiv 1 \; \pmod{d} & \quad \text{(zobacz L8 p.1)} \\
 & & & \\
 & \qquad \Longleftrightarrow \qquad & d \mid (a^{\gcd (m, n)} - 1) & \\
\end{array}</math>

Wynika stąd, że

::<math>\gcd (a^m - 1, a^n - 1) \mid (a^{\gcd (m, n)} - 1)</math>

oraz

::<math>(a^{\gcd (m, n)} - 1) \mid \gcd (a^m - 1, a^n - 1)</math>

Czyli <math>| \gcd (a^m - 1, a^n - 1) | = | a^{\gcd (m, n)} - 1 |</math>. Co należało pokazać. Zobacz też twierdzenie [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H15|H15]].<br/>
&#9633;
{{\Spoiler}}



<span id="L14" style="font-size: 110%; font-weight: bold;">Zadanie L14</span><br/>
Niech <math>m \in \mathbb{Z}_+ \:</math> i <math>\; \gcd (a, m) = 1</math>. Pokazać, że

::<math>a \equiv b \!\! \pmod{m} \qquad \quad \Longrightarrow \qquad \quad \operatorname{ord}(a, m) = \operatorname{ord}(b, m)</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zauważmy najpierw, że ponieważ <math>a \equiv b \!\! \pmod{m}</math>, to <math>\gcd (b, m) = 1</math>, czyli rząd liczby <math>b</math> jest określony. Oznaczmy: <math>h = \operatorname{ord}(a, m)</math>, <math>f = \operatorname{ord}(b, m)</math>.

Z założenia <math>h</math> jest rzędem liczby <math>a</math> modulo <math>m</math>, zatem <math>1 \equiv a^h \equiv b^h \!\! \pmod{m}</math>, ale <math>f</math> jest rzędem liczby <math>b</math> modulo <math>m</math>, zatem <math>f \mid h</math>.

Z założenia <math>f</math> jest rzędem liczby <math>b</math> modulo <math>m</math>, zatem <math>1 \equiv b^f \equiv a^f \!\! \pmod{m}</math>, ale <math>h</math> jest rzędem liczby <math>a</math> modulo <math>m</math>, zatem <math>h \mid f</math>.

Ponieważ <math>f \mid h \;</math> i <math>\; h \mid f</math>, to <math>| h | = | f |</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L15" style="font-size: 110%; font-weight: bold;">Twierdzenie L15</span><br/>
Jeżeli <math>\gcd (a b, m) = 1</math> oraz <math>\gcd (\operatorname{ord}(a, m), \operatorname{ord}(b, m)) = 1</math>, to

::<math>\operatorname{ord}(a b, m) = \operatorname{ord}(a, m) \cdot \operatorname{ord}(b, m)</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia <math>\gcd (a b, m) = 1</math>, czyli <math>\gcd (a, m) = 1 \;</math> i <math>\; \gcd (b, m) = 1</math>. Czyli liczby <math>a</math> i <math>b</math> mają określone rzędy modulo <math>m</math>.

Niech <math>h = \operatorname{ord}(a, m)</math> oraz <math>f = \operatorname{ord}(b, m)</math>. Zatem

::<math>a^h \equiv 1 \!\! \pmod{m}</math>

::<math>b^f \equiv 1 \!\! \pmod{m}</math>

Czyli

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

Przypuśćmy, dla uzyskania sprzeczności, że istnieje wykładnik <math>r < h f</math>, dla którego <math>(a b)^r \equiv 1 \!\! \pmod{m}</math>. Mielibyśmy

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

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

::<math>(a^h)^r \cdot b^{r h} \equiv 1 \!\! \pmod{m}</math>

::<math>b^{r h} \equiv 1 \!\! \pmod{m}</math>

Zatem <math>f \mid r h</math>, ale z&nbsp;założenia <math>\gcd (h, f) = 1</math>, czyli <math>f \mid r</math>.

Podobnie pokazujemy, że <math>h \mid r</math>.

Ponieważ <math>h</math> i <math>f</math> są względnie pierwsze, to <math>h f \mid r</math> (zobacz [[Ciągi liczbowe#C76|C76]]), zatem <math>h f \leqslant r</math>. Uzyskana sprzeczność kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span id="L16" style="font-size: 110%; font-weight: bold;">Zadanie L16</span><br/>
Niech <math>m \geqslant 3</math> będzie liczbą całkowitą. Pokazać, że jeżeli rząd liczby <math>a</math> modulo <math>m</math> jest liczbą nieparzystą, to

::<math>\operatorname{ord}(- a, m) = 2 \cdot \operatorname{ord}(a, m)</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zauważmy, że wzór nie jest prawdziwy dla <math>m = 2</math>, bo dla dowolnej liczby nieparzystej <math>a</math> mamy <math>\operatorname{ord}(\pm a, 2) = 1</math>.

Dla <math>m \geqslant 3</math> jest <math>\operatorname{ord}(- 1, m) = 2</math>, bo <math>(- 1)^2 \equiv 1 \!\! \pmod{m} \;</math> i <math>\; (- 1)^1 \not\equiv 1 \!\! \pmod{m}</math>.

Z założenia rząd liczby <math>a</math> modulo <math>m</math> jest liczbą nieparzystą, zatem

::<math>\gcd (\operatorname{ord}(- 1, m), \operatorname{ord}(a, m) ) = \gcd (2, \operatorname{ord}(a, m) ) = 1</math>

Ponieważ spełnione są założenia twierdzenia [[#L15|L15]], to

::<math>\operatorname{ord}(- a, m) = \operatorname{ord}(- 1, m) \cdot \operatorname{ord}(a, m) = 2 \cdot \operatorname{ord}(a, m)</math>

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



<span id="L17" style="font-size: 110%; font-weight: bold;">Zadanie L17</span><br/>
Niech <math>a \in \mathbb{Z}</math> i <math>m \in \mathbb{Z}_+</math>. Pokazać, że jeżeli liczby <math>a, m</math> są nieparzyste i <math>\operatorname{ord}(a, m) = h</math>, to <math>\operatorname{ord}(a, 2 m) = h</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zauważmy, że liczby <math>a, m</math> nie mogą być jednocześnie parzyste, bo mielibyśmy <math>\gcd (a, m) \geqslant 2</math> i&nbsp;rząd liczby <math>a</math> modulo <math>m</math> nie byłby określony (zobacz [[#L3|L3]]). Z&nbsp;założenia rząd liczby <math>a</math> modulo <math>m</math> istnieje i&nbsp;jest równy <math>h</math>, zatem <math>\gcd (a, m) = 1</math>. Ponieważ <math>a</math> jest liczbą nieparzystą, to <math>\gcd (a, 2) = 1</math>, czyli <math>\gcd (a, 2 m) = 1</math> (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H6|H6]]). Co oznacza, że rząd liczby <math>a</math> modulo <math>2 m</math> jest określony. Niech <math>f = \operatorname{ord}(a, 2 m)</math>, zatem

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

Skąd dostajemy

::<math>a^f \equiv 1 \!\! \pmod{m}</math>

Ponieważ <math>h</math> jest rzędem liczby <math>a</math> modulo <math>m</math>, to <math>h \mid f</math> (zobacz [[#L8|L8]] p.1). Z&nbsp;założenia <math>a</math> jest liczbą nieparzystą, zatem prawdziwy jest układ kongruencji

::<math>a^h \equiv 1 \!\! \pmod{m}</math>

::<math>a^h \equiv 1 \!\! \pmod{2}</math>

Uwzględniając, że <math>\gcd (2, m) = 1</math>, układ ten możemy w&nbsp;sposób równoważny zapisać w&nbsp;postaci

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

(zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J1|J1]]). Ponieważ <math>f</math> jest rzędem liczby <math>a</math> modulo <math>2 m</math>, to <math>f \mid h</math>. Otrzymaliśmy, że <math>h \mid f \;</math> i <math>\; f \mid h</math>, zatem <math>| f | = | h |</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L18" style="font-size: 110%; font-weight: bold;">Twierdzenie L18</span><br/>
Niech <math>m \in \mathbb{Z}_+ \:</math> i <math>\; \gcd (a, m) = 1</math>. Rząd liczby <math>a^r</math> modulo <math>m</math> jest równy

::<math>\operatorname{ord}(a^r, m) = {\small\frac{h}{\gcd (r, h)}}</math>

gdzie <math>h = \operatorname{ord}(a, m) \;</math> i <math>\; r \geqslant 0</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Aby ułatwić sobie operowanie liczbami występującymi w&nbsp;dowodzonym wzorze, wprowadzimy oznaczenia

::<math>b = a^r \qquad \quad f = \operatorname{ord}(b, m) \qquad \quad d = \gcd (r, h)</math>

Ponieważ <math>d = \gcd (r, h)</math>, to możemy napisać <math>r = s \cdot d \;</math> i <math>\; h = t \cdot d</math>, gdzie <math>\gcd (s, t) = 1</math> (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H11|H11]]).

Z definicji liczb <math>b \:</math> i <math>\: f</math> mamy

::<math>b^f = a^{r f} \equiv 1 \!\! \pmod{m}</math>

Ponieważ rząd liczby <math>a</math> jest równy <math>h</math>, to <math>h \mid r f</math>, czyli <math>t d \mid s d f</math>, zatem <math>t \mid s f</math>, ale <math>\gcd (s, t) = 1</math> i&nbsp;dostajemy, że <math>t \mid f</math>.

Zauważmy teraz, że

::<math>b^t = (a^r)^t = (a^{s d})^{\tfrac{h}{d}} = (a^s)^h = (a^h)^s \equiv 1 \!\! \pmod{m}</math>

Zatem <math>f \mid t</math>. Ponieważ <math>t \mid f</math> oraz <math>f \mid t</math>, to <math>| f | = | t |</math>. Wynika stąd

::<math>f = t = {\small\frac{h}{d}} = {\small\frac{h}{\gcd (r, h)}}</math>

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



<span id="L19" style="font-size: 110%; font-weight: bold;">Zadanie L19</span><br/>
Niech <math>m \in \mathbb{Z}_+</math>, <math>\gcd (a, m) = 1</math> oraz <math>h = \operatorname{ord}(a, m)</math>. Jeżeli <math>d \mid h</math>, to <math>\operatorname{ord}(a^d, m) = {\small\frac{h}{d}}</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Wystarczy sprawdzić, że liczba <math>{\small\frac{h}{d}}</math> jest rzędem liczby <math>a^d</math> modulo <math>m</math>. Łatwo otrzymujemy

::<math>(a^d)^{\tfrac{h}{d}} = a^h \equiv 1 \!\! \pmod{m}</math>

Zauważmy teraz, że gdyby istniała liczba <math>t < {\small\frac{h}{d}}</math> taka, że <math>(a^d)^t \equiv 1 \!\! \pmod{m}</math>, to mielibyśmy <math>a^{d t} \equiv 1 \!\! \pmod{m} \;</math> i <math>\; d t < h</math> wbrew założeniu, że <math>h</math> jest rzędem liczby <math>a</math> modulo <math>m</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L20" style="font-size: 110%; font-weight: bold;">Zadanie L20</span><br/>
Niech <math>p \in \mathbb{P}</math>. Jeżeli istnieje liczba całkowita <math>a</math> względnie pierwsza z <math>p</math> taka, że <math>\operatorname{ord}(a, p) = h</math>, to

:*&nbsp;&nbsp;&nbsp;liczby <math>a, a^2, \ldots, a^h</math> są wszystkimi liczbami modulo <math>p</math> spełniającymi kongruencję <math>x^h \equiv 1 \!\! \pmod{p}</math>

:*&nbsp;&nbsp;&nbsp;istnieje dokładnie <math>\varphi (h)</math> liczb <math>x</math>, dla których <math>\operatorname{ord}(x, p) = h</math>

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

Każda liczba <math>a^k</math>, gdzie <math>k = 1, \ldots, h</math>, spełnia kongruencję <math>x^h \equiv 1 \!\! \pmod{p}</math>, bo

::<math>(a^k)^h = (a^h)^k \equiv 1^k \equiv 1 \!\! \pmod{p}</math>

Z twierdzenia [[#L5|L5]] wiemy, że liczby <math>a, a^2, \ldots, a^h</math> są różne modulo <math>p</math>. Z&nbsp;twierdzenia Lagrange'a wiemy, że kongruencja

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

nie może mieć więcej niż <math>h</math> rozwiązań. Zatem nie może istnieć liczba <math>u</math> różna od każdej z&nbsp;liczb <math>a, a^2, \ldots, a^h</math> modulo <math>p</math> taka, że <math>u^h \equiv 1 \!\! \pmod{p}</math>, bo liczba <math>u</math> byłaby <math>(h + 1)</math>-szym rozwiązaniem wypisanej kongruencji, co jest niemożliwe.

'''Punkt 2.'''

Z punktu 1. wiemy, że liczby <math>a, a^2, \ldots, a^h</math> i&nbsp;tylko te liczby są rozwiązaniami kongruencji <math>x^h \equiv 1 \!\! \pmod{p}</math>. Zatem dla liczb innych niż <math>a, a^2, \ldots, a^h</math> zawsze będziemy mieli <math>x^h \not\equiv 1 \!\! \pmod{p}</math>, skąd natychmiast wynika, że <math>\operatorname{ord}(x, p) \neq h</math>.

Z twierdzenia [[#L18|L18]] wiemy, że

::<math>\operatorname{ord}(a^k, m) = {\small\frac{h}{\gcd (k, h)}}</math>

Ponieważ istnieje <math>\varphi (h)</math> liczb całkowitych dodatnich <math>k \leqslant h</math> takich, że <math>\gcd (k, h) = 1</math>, to istnieje dokładnie <math>\varphi (h)</math> liczb <math>a^k</math> (różnych modulo <math>p</math>) takich, że <math>\operatorname{ord}(a^k, p) = h</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L21" style="font-size: 110%; font-weight: bold;">Twierdzenie L21</span><br/>
Niech <math>p</math> będzie liczbą pierwszą i <math>h \in \mathbb{Z}_+</math>. Jeżeli <math>h \mid (p - 1)</math>, to istnieje <math>\varphi (h)</math> liczb, których rząd modulo <math>p</math> jest równy <math>h</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Zauważmy, że dowodzone twierdzenie jest istotnie różne od punktu 2. zadania [[#L20|L20]], bo teraz '''nie zakładamy''' istnienia liczby <math>a</math> takiej, że <math>\operatorname{ord}(a, p) = h</math>.

Niech ilość liczb <math>a</math>, dla których <math>\operatorname{ord}(a, p) = h</math>, będzie określona funkcją <math>f(h)</math>. Oczywiście <math>f(h) = 0</math> w&nbsp;przypadku, gdy <math>h \nmid (p - 1)</math> (zobacz [[#L9|L9]]). Możliwa jest też sytuacja, że <math>h \mid (p - 1)</math>, ale nie istnieje taka liczba <math>a</math>, dla której <math>\operatorname{ord}(a, p) = h</math>. Skoro nie istnieje ani jedna taka liczba <math>a</math>, dla której <math>\operatorname{ord}(a, p) = h</math>, to również w&nbsp;tym przypadku musi być <math>f(h) = 0</math>. W&nbsp;przypadku gdy <math>h \mid (p - 1)</math> i&nbsp;istnieje taka liczba <math>a</math>, dla której <math>\operatorname{ord}(a, p) = h</math>, to z&nbsp;zadania [[#L20|L20]] wiemy, że takich liczb jest <math>\varphi (h)</math>. Zbierając, mamy

::<math>
f(h) = 
\begin{cases}
      \;\; 0 & \text{jeżeli } h \nmid (p - 1) \\
      \;\; 0 & \text{jeżeli } h \mid (p - 1) \;\; \text{i} \;\; \text{nie istnieje liczba } a \text{ taka, że } \operatorname{ord}(a, p) = h \\
 \varphi (h) & \text{jeżeli } h \mid (p - 1) \;\; \text{i} \;\; \text{istnieje liczba } a \text{ taka, że } \operatorname{ord}(a, p) = h \\
\end{cases}
</math>

Otrzymujemy natychmiast oszacowanie <math>f(h) \leqslant \varphi (h)</math>.

Przy okazji zauważmy, że oszacowanie <math>f(h) \leqslant \varphi (h)</math> nie jest w&nbsp;ogólności prawdziwe dla modułu złożonego <math>m</math>. Przykładowo dla modułu <math>m = 33</math> mamy <math>12</math> liczb, których rząd <math>h = 10</math> (są to liczby <math>2, 5, 7, 8, 13, 14, 17, 19, 20, 26, 28, 29</math>), ale <math>\varphi (h) = \varphi (10) = 4</math>.

Ponieważ każda liczba <math>a \in \{ 1, 2, \ldots, p - 1 \}</math> jest względnie pierwsza z <math>p</math>, to dla każdej takiej liczby rząd <math>a</math> modulo <math>p</math> jest zdefiniowany, zatem liczba <math>h = \operatorname{ord}(a, p)</math> musi być dzielnikiem liczby <math>p - 1</math> (zobacz [[#L9|L9]]). Wynika stąd, że

::<math>\sum_{h \mid (p - 1)} f (h) = p - 1</math>

gdzie sumowanie przebiega po wszystkich dodatnich dzielnikach <math>h</math> liczby <math>p - 1</math>.

Z twierdzenia [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H44|H44]] wiemy, że

::<math>\sum_{h \mid (p - 1)} \varphi (h) = p - 1</math>

Zatem, uwzględniając oszacowanie <math>f(h) \leqslant \varphi (h)</math>, możemy napisać

::<math>0 = \sum_{h \mid (p - 1)} (\varphi (h) - f (h) ) = \sum_{h \mid (p - 1)} | \varphi (h) - f (h) |</math>

Skąd wynika natychmiast, że dla każdego dodatniego dzielnika <math>h</math> liczby <math>p - 1</math> jest <math>f(h) = \varphi (h)</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L22" style="font-size: 110%; font-weight: bold;">Zadanie L22</span><br/>
Niech <math>a \in \mathbb{Z} \;</math> i <math>\; p</math> będzie liczbą pierwszą postaci <math>p = 6 k + 1</math>. Pokazać, że jeżeli <math>\operatorname{ord}(a, p) = 3</math>, to <math>\operatorname{ord}(a + 1, p) = 6</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Założenie, że liczba pierwsza jest postaci <math>6 k + 1</math>, jest konieczne, bo liczby <math>3</math> i <math>6</math> muszą być dzielnikami <math>\varphi (p) = p - 1</math>. Dla liczb pierwszych postaci <math>6 k + 5</math> nigdy nie będzie <math>\operatorname{ord}(a, p) = 3</math>. Z&nbsp;twierdzenia [[#L21|L21]] wiemy, dla liczb pierwszych postaci <math>6 k + 1</math> istnieją dwie liczby, których rząd jest równy <math>3</math> i&nbsp;dwie liczby, których rząd jest równy <math>6</math>.

Z założenia <math>\operatorname{ord}(a, p) = 3</math>, zatem <math>a^3 \equiv 1 \!\! \pmod{p}</math>, czyli <math>(a - 1) (a^2 + a + 1) \equiv 0 \!\! \pmod{p}</math>. Zauważmy, że nie może być <math>a \equiv 1 \!\! \pmod{p}</math>, bo wtedy rząd liczby <math>a</math> modulo <math>p</math> byłby równy <math>1</math>, czyli musi być <math>a^2 + a + 1 \equiv 0 \!\! \pmod{p}</math>. Ponieważ z&nbsp;założenia rząd liczby <math>a</math> modulo <math>p</math> jest określony, to musi być <math>p \nmid a</math>, czyli <math>a \not\equiv 0 \!\! \pmod{p}</math>, zatem

::<math>a + 1 \not\equiv 1 \!\! \pmod{p}</math>

::<math>(a + 1)^2 = a^2 + a + 1 + a \equiv a \not\equiv 1 \!\! \pmod{p}</math>

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

::<math>(a + 1)^4 \equiv a^2 \not\equiv 1 \!\! \pmod{p} , \;</math> bo gdyby <math>a^2 \equiv 1 \!\! \pmod{p}</math>, to mielibyśmy <math>\operatorname{ord}(a, p) \leqslant 2</math>

::<math>(a + 1)^5 \equiv - a \not\equiv 1 \!\! \pmod{p} , \;</math> bo gdyby <math>a \equiv - 1 \!\! \pmod{p}</math>, to <math>a^2 \equiv 1 \!\! \pmod{p} \;</math> i&nbsp;mielibyśmy <math>\operatorname{ord}(a, p) = 2</math>

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

Zatem <math>\operatorname{ord}(a + 1, p) = 6</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L23" style="font-size: 110%; font-weight: bold;">Twierdzenie L23</span><br/>
Niech <math>m \in \mathbb{Z}_+ \:</math> i <math>\; \gcd (a, m) = 1</math>. Kongruencja <math>a^r \equiv a^s</math> '''modulo''' <math>\boldsymbol{m}</math> jest prawdziwa wtedy i&nbsp;tylko wtedy, gdy prawdziwa jest kongruencja <math>r \equiv s</math> '''modulo rząd liczby''' <math>\boldsymbol{a}</math>

::<math>a^r \equiv a^s \!\! \pmod{m} \quad \qquad \Longleftrightarrow \qquad \quad r \equiv s \!\! \pmod{\operatorname{ord}(a, m)}</math>

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

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

Jeśli <math>r = s</math>, to twierdzenie jest prawdziwe, bo każda liczba przystaje do samej siebie modulo dowolna liczba całkowita dodatnia. Nie zmniejszając ogólności, załóżmy, że <math>s > r</math>, zatem rozważaną kongruencję możemy zapisać w&nbsp;postaci

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

::<math>a^r - a^s \equiv 0 \!\! \pmod{m}</math>

::<math>a^r \cdot (a^{s - r} - 1) \equiv 0 \!\! \pmod{m}</math>

Ponieważ <math>\gcd (a, m) = 1</math>, to <math>m</math> nie może być dzielnikiem <math>a</math>, czyli <math>m</math> musi dzielić <math>a^{s - r} - 1</math>, co oznacza, że

::<math>a^{s - r} - 1 \equiv 0 \!\! \pmod{m}</math>

::<math>a^{s - r} \equiv 1 \!\! \pmod{m}</math>

Z twierdzenia [[#L8|L8]] p.1 wiemy, że <math>\operatorname{ord}(a, m)</math> jest dzielnikiem <math>s - r</math>, co możemy zapisać w&nbsp;postaci kongruencji

::<math>r \equiv s \!\! \pmod{\operatorname{ord}(a, m})</math>

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

Z założenia <math>r \equiv s \!\! \pmod{h}</math>, gdzie <math>h = \operatorname{ord}(a, m)</math>. Zatem dla pewnej liczby całkowitej <math>k</math> mamy <math>r = s + k \cdot h</math>, czyli

::<math>a^r = a^{s + k \cdot h} = a^s \cdot (a^h)^k \equiv a^s \cdot 1^k \equiv a^s \!\! \pmod{m}</math>

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



<span id="L24" style="font-size: 110%; font-weight: bold;">Zadanie L24</span><br/>
Niech <math>m \in \mathbb{Z}_+ \:</math> i <math>\; \gcd (a, m) = 1</math> oraz <math>h = \operatorname{ord}(a, m)</math>. Pokazać, że jeżeli <math>r \equiv s \!\! \pmod{h}</math>, to <math>\operatorname{ord}(a^r, m) = \operatorname{ord}(a^s, m)</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Jeżeli <math>r \equiv s \!\! \pmod{h}</math>, to z&nbsp;twierdzenia [[#L23|L23]] wynika, że <math>a^r \equiv a^s \!\! \pmod{m}</math> i&nbsp;na mocy [[#L14|L14]] mamy <math>\operatorname{ord}(a^r, m) = \operatorname{ord}(a^s, m)</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L25" style="font-size: 110%; font-weight: bold;">Twierdzenie L25</span><br/>
Niech <math>m, r \in \mathbb{Z}_+ \:</math> i <math>\; a \in \mathbb{Z}</math>. Jeżeli

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

oraz dla każdego dzielnika pierwszego <math>q</math> liczby <math>r</math> jest

::<math>a^{\tfrac{r}{q}} \not\equiv 1 \!\! \pmod{m}</math>

to <math>\operatorname{ord}(a, m) = r</math>.

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

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

Zatem <math>\gcd (a, m) = 1 \;</math> i <math>\; h \mid r</math>, gdzie oznaczyliśmy <math>h = \operatorname{ord}(a, m)</math>.

Przypuśćmy, dla uzyskania sprzeczności, że <math>r = h d \;</math> i <math>\; d > 1</math>. Konsekwentnie istnieje liczba pierwsza <math>q</math> taka, że <math>q \mid d</math>, czyli <math>q \mid r</math>. Ponieważ <math>h</math> jest rzędem liczby <math>a</math> modulo <math>m</math>, to

::<math>a^h \equiv 1 \!\! \pmod{m}</math>

Podnosząc obie strony kongruencji do potęgi <math>{\small\frac{d}{q}}</math>, dostajemy

::<math>1 \equiv (a^h)^{\tfrac{d}{q}} \equiv a^{\tfrac{h d}{q}} \equiv a^{\tfrac{r}{q}} \!\! \pmod{m}</math>

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



<span id="L26" style="font-size: 110%; font-weight: bold;">Zadanie L26</span><br/>
Niech <math>a, n \in \mathbb{Z}_+ \:</math> i <math>\; p</math> będzie liczbą pierwszą nieparzystą. Pokazać, że jeżeli <math>p \mid (a^{2^{\large n}} + 1)</math>, to <math>p \equiv 1 \!\! \pmod{2^{n + 1}}</math>.

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

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

Zatem

::<math>(a^{2^{\large n}})^2 = a^{2^{\large n + 1}} \equiv 1 \!\! \pmod{p}</math>

Z twierdzenia [[#L25|L25]] wynika natychmiast, że <math>\operatorname{ord}(a, p) = 2^{n + 1}</math>. Ponieważ <math>\operatorname{ord}(a, p) \mid \varphi (p)</math> (zobacz [[#L9|L9]]), to <math>2^{n + 1} \mid (p - 1)</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L27" style="font-size: 110%; font-weight: bold;">Zadanie L27</span><br/>
Niech <math>n \in \mathbb{Z}_+</math>. Pokazać, że istnieje nieskończenie wiele liczb pierwszych postaci <math>2^{n + 1} k + 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zauważmy, że problem jest szczególnym przypadkiem twierdzenia Dirichleta (zobacz [[Ciągi liczbowe#C28|C28]]). Załóżmy, dla uzyskania sprzeczności, że istnieje jedynie skończona ilość liczb pierwszych <math>p_1, \ldots, p_s</math> postaci <math>2^{n + 1} k + 1</math> i&nbsp;niech

::<math>a = (2 p_1 \cdot \ldots \cdot p_s)^{2^{\large n}} + 1</math>

Jeżeli liczba <math>a</math> jest liczbą pierwszą, to twierdzenie jest dowiedzione, bo <math>a</math> jest postaci <math>2^{n + 1} k + 1</math>. Istotnie

::<math>a = 2^{n + 1} \cdot \left[ 2^{2^{\large n} - n - 1} \cdot (p_1 \cdot \ldots \cdot p_s)^{2^{\large n}} \right] + 1</math>

Rozważmy teraz przypadek, gdy <math>a</math> jest liczbą złożoną. Liczba <math>a</math> ma dzielnik pierwszy nieparzysty <math>q</math>, bo sama jest liczbą nieparzystą. Ponieważ <math>q \mid a</math>, to <math>q \neq p_i</math> dla <math>i = 1, \ldots, s</math>. Z&nbsp;zadania [[#L26|L26]] wynika, że <math>q</math> ma postać <math>2^{n + 1} k + 1</math>. Otrzymaliśmy sprzeczność z&nbsp;założeniem, że liczby <math>p_1, p_2, \ldots, p_s</math> wyczerpują wszystkie liczby pierwsze postaci <math>2^{n + 1} k + 1</math>. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span id="L28" style="font-size: 110%; font-weight: bold;">Twierdzenie L28</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, a <math>F_n = 2^{2^{\large n}} + 1</math> oznacza liczbę Fermata. Jeżeli liczba pierwsza <math>p</math> jest dzielnikiem <math>F_n</math>, gdzie <math>n \geqslant 2</math>, to <math>p</math> jest postaci <math>p = 2^{n + 2} k + 1</math>.

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

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

Podnosząc do kwadratu otrzymujemy

::<math>(2^{2^{\large n}})^2 = 2^{2^{\large n + 1}} \equiv 1 \!\! \pmod{p}</math>

I z&nbsp;twierdzenia [[#L25|L25]] wynika natychmiast, że <math>\operatorname{ord}(2, p) = 2^{n + 1}</math>. Z&nbsp;własności rzędu liczby wiemy (zobacz [[#L9|L9]]), że <math>\operatorname{ord}(2, p) \mid \varphi (p)</math>, czyli <math>2^{n + 1} \mid (p - 1)</math>. Skąd otrzymujemy <math>p - 1 = k \cdot 2^{n + 1}</math> lub równoważnie

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

Zatem

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

(zobacz [[#L123|L123]]). Wynika stąd, że <math>{\small\frac{1}{8}} (p^2 - 1)</math> jest liczbą parzystą dla <math>n \geqslant 2 \;</math> i

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

Czyli <math>2</math> jest liczbą kwadratową modulo <math>p</math> i&nbsp;z&nbsp;kryterium Eulera mamy

::<math>2^{\tfrac{p - 1}{2}} = 2^{k \cdot 2^{\large n}} \equiv 1 \!\! \pmod{p}</math>

Ponieważ <math>\operatorname{ord}(2, p) = 2^{n + 1}</math>, to <math>2^{n + 1} \mid k \cdot 2^n</math> (zobacz [[#L8|L8]] p.1). Zatem <math>2 \mid k \;</math> i <math>\; k</math> musi być liczbą parzystą, skąd wynika natychmiast, że <math>p = k' \cdot 2^{n + 2} + 1</math>. Możemy łatwo sprawdzić, że dla <math>n = 0 \;</math> i <math>\; n = 1</math> twierdzenie nie jest prawdziwe.<br/>
&#9633;
{{\Spoiler}}



<span id="L29" style="font-size: 110%; font-weight: bold;">Twierdzenie L29</span><br/>
Jeżeli <math>m \geqslant 3</math> jest liczbą nieparzystą, to kongruencja <math>x^{m - 1} \equiv - 1 \!\! \pmod{m}</math> nie ma rozwiązań.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Przypuśćmy, w&nbsp;celu uzyskania sprzeczności, że <math>m</math> jest liczbą pierwszą nieparzystą lub potęgą liczby pierwszej nieparzystej. Wtedy mielibyśmy

::<math>x^{p - 1} \equiv - 1 \!\! \pmod{p} \qquad \qquad \text{lub} \qquad \qquad x^{p^n - 1} \equiv - 1 \!\! \pmod{p^n}</math>

::::::::::::::<math>\quad \; x^{(p - 1) (1 + p + p^2 + \ldots + p^{n - 1})} \equiv - 1 \!\! \pmod{p}</math>

I w&nbsp;każdym przypadku z&nbsp;twierdzenia Fermata mielibyśmy natychmiast <math>1 \equiv - 1 \!\! \pmod{p}</math>. Co jest niemożliwe. Zatem <math>m</math> musi być iloczynem liczb pierwszych nieparzystych.


Niech <math>m = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>. Ponieważ <math>m</math> jest liczbą nieparzystą, to może być zapisana w&nbsp;postaci <math>m = 2^u w + 1</math>, gdzie <math>w</math> jest liczbą nieparzystą. Przypuśćmy, że dla pewnego <math>x \equiv a \!\! \pmod{m}</math> rozpatrywana kongruencja ma rozwiązanie, czyli

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

Niech <math>p</math> oznacza dowolny czynnik pierwszy <math>q_i</math>. Ponieważ <math>p \mid m</math>, to możemy zapisaną kongruencję rozpatrywać modulo <math>p</math>. Zatem

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

Podnosząc obie strony kongruencji do kwadratu, dostajemy

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

Zauważmy, że <math>\gcd (a^{m - 1}, p) = \gcd (- 1, p) = 1</math>, zatem rząd liczby <math>a</math> modulo <math>p</math> jest określony.

Niech <math>h = \operatorname{ord}(a, p)</math> będzie rzędem liczby <math>a</math> modulo <math>p</math>. Z&nbsp;twierdzenia [[#L8|L8]] p.1 wynika, że <math>h \mid 2 (m - 1) \;</math> i <math>\; h \nmid (m - 1)</math>, czyli

::<math>h \mid 2^{u + 1} w \qquad \qquad \text{i} \qquad \qquad h \nmid 2^u w</math>

Z założenia <math>w</math> jest liczbą nieparzystą, zatem spełnione są założenia twierdzenia [[#L124|L124]], z&nbsp;którego wynika, że <math>h = 2^{u + 1} r</math>, gdzie <math>r \mid w</math>.

Ponieważ <math>h</math> jest rzędem liczby <math>a</math> modulo <math>p</math>, to <math>h = 2^{u + 1} r</math> dzieli <math>\varphi (p) = p - 1</math>. Zatem

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

Ponieważ przez <math>p</math> oznaczyliśmy dowolny dzielnik pierwszy <math>q_i</math> liczby <math>m</math>, to otrzymujemy

::<math>m = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s \equiv 1 \!\! \pmod{2^{u + 1}}</math>

Co jest niemożliwe, bo <math>m = 2^u w + 1</math>, gdzie <math>w</math> jest liczbą nieparzystą. Otrzymana sprzeczność kończy dowód.<br/>
&#9633;
{{\Spoiler}}





== Generatory modulo ==

<span id="L30" style="font-size: 110%; font-weight: bold;">Uwaga L30</span><br/>
Jedynymi liczbami naturalnymi mającymi generatory są liczby <math>2, 4, p^k, 2 p^k</math><ref name="generator1"/>, gdzie <math>k \geqslant 1</math> i <math>p</math> oznacza liczbę pierwszą nieparzystą. Zatem istnienie generatora jest raczej wyjątkiem niż regułą. Zbadamy właściwości generatorów, a&nbsp;następnie wyjaśnimy, dlaczego tak niewiele liczb ma generator.



=== <span style="border-bottom:2px solid #000;">Generatory modulo <math>\boldsymbol{m}</math></span> ===

&nbsp;

<span id="L31" style="font-size: 110%; font-weight: bold;">Definicja L31</span><br/>
Jeżeli <math>g</math> jest dowolną liczbą całkowitą taką, że <math>\gcd (g, m) = 1</math> oraz rząd liczby <math>g</math> modulo <math>m</math> jest równy <math>\varphi (m)</math>, to liczbę <math>g</math> nazywamy generatorem lub pierwiastkiem pierwotnym modulo <math>m</math><ref name="generator2"/>.



<span id="L32" style="font-size: 110%; font-weight: bold;">Uwaga L32</span><br/>
Niech <math>g</math> będzie generatorem modulo <math>m</math>. Nazwa „generator” wynika z&nbsp;prostej właściwości generatorów: kolejne potęgi <math>g^1, g^2, \ldots, g^{\varphi (m)}</math> są różne modulo <math>m</math> (zobacz [[#L5|L5]]) i&nbsp;generują wszystkie liczby względnie pierwsze z <math>m</math> (oczywiście modulo <math>m</math>).

W przypadku, gdy <math>m = p</math> jest liczbą pierwszą, zbiory <math>\{ g^1, g^2, \ldots, g^{p - 1} \} \;</math> i <math>\; \{ 1, 2, \ldots, p - 1 \}</math> są równe modulo <math>p</math> (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H24|H24]]).



<span id="L33" style="font-size: 110%; font-weight: bold;">Przykład L33</span><br/>
W tabeli przedstawiliśmy generatory dla początkowych wartości <math>m</math>

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{m}</math> 
| <math>1</math> || <math>2</math> || <math>3</math> || <math>4</math> || <math>5</math> || <math>6</math> || <math>7</math> || <math>8</math> || <math>9</math> || <math>10</math> || <math>11</math> || <math>12</math> || <math>13</math> || <math>14</math> || <math>15</math> || <math>16</math> || <math>17</math> || <math>18</math>
|-
! <math>\boldsymbol{φ(m)}</math> 
| <math>1</math> || <math>1</math> || <math>2</math> || <math>2</math> || <math>4</math> || <math>2</math> || <math>6</math> || <math>4</math> || <math>6</math> || <math>4</math> || <math>10</math> || <math>4</math> || <math>12</math> || <math>6</math> || <math>8</math> || <math>8</math> || <math>16</math> || <math>6</math>
|-
! generatory
| <math>0</math> || <math>1</math> || <math>2</math> || <math>3</math> || <math>2,3</math> || <math>5</math> || <math>3,5</math> || <math>-</math> || <math>2,5</math> || <math>3,7</math> || <math>2,6,7,8</math> || <math>-</math> || <math>2,6,7,11</math> || <math>3,5</math> || <math>-</math> || <math>-</math> || <math>3,5,6,7,10,11,12,14</math> || <math>5,11</math>
|}

Zauważmy, że dla liczb <math>8, 12, 15, 16</math> generatory nie istnieją. Na przykład generator modulo <math>8</math> nie istnieje, ponieważ dla liczb nieparzystych jest <math>a^2 \equiv 1 \!\! \pmod{8}</math>, ale <math>\varphi (8) = 4</math>.

Oczywiście, jeżeli <math>g</math> jest generatorem modulo <math>m</math>, to liczby <math>g + m</math>, <math>g + 2 m</math>, ... też są generatorami modulo <math>m</math>. Przykładowo <math>2^6 \equiv 11^6 \equiv 20^6 \equiv 1 \!\! \pmod{9}</math>.



<span id="L34" style="font-size: 110%; font-weight: bold;">Zadanie L34</span><br/>
Niech <math>g \in \mathbb{Z}</math>, <math>\; k, m \in \mathbb{Z}_+ \;</math> i <math>\; \gcd (g, m) = 1</math>. Jeżeli liczba <math>g</math> jest generatorem modulo <math>m</math>, to liczby <math>g^k</math>, gdzie <math>k</math> spełnia warunek <math>\gcd (k, \varphi (m)) = 1</math>, są generatorami modulo <math>m</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Ponieważ <math>g</math> jest generatorem modulo <math>m</math>, to <math>\operatorname{ord}(g, m) = \varphi (m)</math>, zatem (zobacz [[#L18|L18]])

::<math>\operatorname{ord}(g^k, m) = {\small\frac{\varphi (m)}{\gcd (k, \varphi (m))}}</math>

Z założenia <math>\gcd (k, \varphi (m)) = 1</math>, czyli <math>\operatorname{ord}(g^k, m) = \varphi (m)</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L35" style="font-size: 110%; font-weight: bold;">Twierdzenie L35</span><br/>
Jeżeli liczba <math>m</math> ma generator, to ma ich dokładnie <math>\varphi (\varphi (m))</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Rozważmy zbiór <math>S = \{ g^1, g^2, \ldots, g^{\varphi (m)} \}</math>. Ponieważ <math>\gcd (g, m) = 1</math>, to wszystkie elementy zbioru <math>S</math> są względnie pierwsze z <math>m</math>. Zauważmy, że wszystkie elementy zbioru <math>S</math> są różne modulo <math>m</math> (zobacz [[#L5|L5]]), zatem zbiór <math>S</math> zawiera '''wszystkie''' liczby względnie pierwsze z <math>m</math> (rozpatrywane modulo <math>m</math>).

Jeżeli liczba <math>g</math> jest generatorem modulo <math>m</math>, to <math>\operatorname{ord}(g, m) = \varphi (m)</math>. Ponieważ (zobacz [[#L18|L18]])

::<math>\operatorname{ord}(g^k, m) = {\small\frac{\varphi (m)}{\gcd (k, \varphi (m))}}</math>

to ilość liczb w&nbsp;zbiorze <math>S</math>, które mają rząd równy <math>\varphi (m)</math>, jest równa ilości liczb całkowitych <math>1 \leqslant k \leqslant \varphi (m)</math>, dla których <math>\gcd (k, \varphi (m)) = 1</math>. Ponieważ wśród liczb całkowitych <math>k = 1, 2, \ldots, \varphi (m)</math> istnieje dokładnie <math>\varphi (\varphi (m))</math> liczb względnie pierwszych z <math>\varphi (m)</math>, to istnieje <math>\varphi (\varphi (m))</math> generatorów. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L36" style="font-size: 110%; font-weight: bold;">Twierdzenie L36</span><br/>
Jeżeli liczba <math>g</math> jest generatorem modulo <math>m</math>, to dla <math>m \geqslant 3</math> jest

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

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Pokażemy, że jeżeli liczba <math>m \geqslant 3</math> ma generator, to kongruencja

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

ma dokładnie dwa rozwiązania. Wynik <math>g^{\varphi (m) / 2} \equiv - 1 \!\! \pmod{m}</math> będzie jedynie logiczną konsekwencją tego dowodu. Dla przykładu zauważmy, że kongruencja <math>x^2 \equiv 1 \!\! \pmod{15}</math> ma cztery rozwiązania: <math>x \equiv 1, 4, 11, 14 \!\! \pmod{15}</math>.


Jeżeli <math>x \equiv u \!\! \pmod{m}</math> jest rozwiązaniem kongruencji <math>x^2 \equiv 1 \!\! \pmod{m}</math>, to <math>\gcd (u^2, m) = \gcd (1, m) = 1</math>. Zatem liczba <math>u</math> jest względnie pierwsza z <math>m</math>. Ponieważ liczby <math>g^k</math>, gdzie <math>k = 1, 2, \ldots, \varphi (m)</math> są wszystkimi liczbami względnie pierwszymi z <math>m</math>, to możemy szukać rozwiązań, ograniczając się do tych liczb, czyli szukać rozwiązań kongruencji

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

Przypomnijmy (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H38|H38]]), że dla <math>m \geqslant 3</math> wartości funkcji Eulera <math>\varphi (m)</math> są liczbami parzystymi. Ponieważ rząd liczby <math>g</math> modulo <math>m</math> jest równy <math>\varphi (m)</math>, to <math>\varphi (m) \mid 2k</math> (zobacz [[#L8|L8]] p.1), zatem <math>2 k = s \cdot \varphi (m)</math>, gdzie <math>s</math> jest liczbą całkowitą, czyli <math>k = s \cdot {\small\frac{\varphi (m)}{2}}</math>. W&nbsp;zależności od parzystości liczby <math>s</math> otrzymujemy

*&nbsp;&nbsp;&nbsp;dla <math>s = 2 t</math>

::<math>g^k \equiv g^{s \cdot \varphi (m) / 2} \equiv g^{2 t \cdot \varphi (m) / 2} \equiv \left( g^{\varphi (m)} \right) ^{\! t} \equiv 1 \!\! \pmod{m}</math>

*&nbsp;&nbsp;&nbsp;dla <math>s = 2 t + 1</math>

::<math>g^k \equiv g^{s \cdot \varphi (m) / 2} \equiv g^{(2 t + 1) \cdot \varphi (m) / 2} \equiv g^{t \cdot \varphi (m)} \cdot g^{\varphi (m) / 2} \equiv g^{\varphi (m) / 2} \!\! \pmod{m}</math>

Ponieważ <math>g</math> jest generatorem, to <math>g^{\varphi (m) / 2} \not\equiv 1 \!\! \pmod{m}</math>. Pokazaliśmy tym samym, że jeżeli <math>g</math> jest generatorem modulo <math>m</math>, to dla <math>m \geqslant 3</math> kongruencja <math>x^2 \equiv 1 \!\! \pmod{m}</math> ma dokładnie dwa rozwiązania.


Z drugiej strony widzimy, że kongruencja <math>x^2 \equiv 1 \!\! \pmod{m}</math> ma co najmniej dwa rozwiązania, bo dwa rozwiązania możemy natychmiast wypisać

::<math>x \equiv 1 \!\! \pmod{m} \qquad \quad \text{i} \qquad \quad x \equiv - 1 \!\! \pmod{m}</math>

Rozwiązania te są różne modulo <math>m</math>, bo dla <math>m \geqslant 3</math> nie jest możliwa kongruencja

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

ponieważ <math>m \nmid 2</math>.


Łącząc powyższe rezultaty, otrzymujemy, że musi być <math>g^{\varphi (m) / 2} \equiv - 1 \!\! \pmod{m}</math>. Co należało udowodnić.<br/>
&#9633;
{{\Spoiler}}



<span id="L37" style="font-size: 110%; font-weight: bold;">Uwaga L37</span><br/>
Twierdzenie odwrotne nie jest prawdziwe, czyli istnieją liczby <math>a</math> niebędące generatorami, dla których <math>a^{\varphi (m) / 2} \equiv - 1 \!\! \pmod{m}</math>. Przykładowo dla modułu <math>m = 41</math> mamy <math>3^4 \equiv 3^{20} \equiv - 1 \!\! \pmod{41}</math>. Natomiast łatwo pokażemy, że kongruencja

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

ma rozwiązanie tylko dla modułów <math>m \geqslant 3</math> mających generator (zobacz twierdzenia [[#L54|L54]] i [[#L56|L56]]).



<span id="L38" style="font-size: 110%; font-weight: bold;">Twierdzenie L38</span><br/>
Jeżeli liczby <math>g_1</math> i <math>g_2</math> są generatorami modulo <math>m</math>, to liczba <math>a \equiv g_1 g_2 \!\! \pmod{m}</math> nie jest generatorem.

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

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

Zatem <math>a \equiv g_1 g_2 \!\! \pmod{m}</math> nie jest generatorem modulo <math>m</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L39" style="font-size: 110%; font-weight: bold;">Zadanie L39</span><br/>
Pokazać, że dla <math>m = 5</math> i <math>m \geqslant 7</math> iloczyn wszystkich generatorów modulo <math>m</math> przystaje do <math>1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Niech <math>g</math> będzie generatorem modulo <math>m</math>. Zauważmy, że dla <math>m \geqslant 7</math> liczby <math>g</math> i <math>g^{- 1}</math> są zawsze różne modulo <math>m</math>. Istotnie, gdyby było

::<math>g \equiv g^{- 1} \!\! \pmod{m}</math>

to mielibyśmy

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

i rząd liczby <math>g</math> modulo <math>m</math> byłby nie większy od <math>2</math>, ale <math>\varphi (m) > 2</math> dla <math>m \geqslant 7</math> (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H41|H41]]), czyli liczba <math>g</math> nie byłaby generatorem wbrew założeniu.

Ponieważ dla <math>m \geqslant 7</math> każdy generator <math>g</math> ma element odwrotny różny od <math>g</math>, to łącząc generatory w&nbsp;pary takie, że <math>g g' \equiv 1 \!\! \pmod{m}</math> otrzymujemy

::<math>\prod_i g_i = \prod_k g_k g_{k}^{- 1} \equiv 1 \!\! \pmod{m}</math>

Przypadek <math>m = 5</math> sprawdzamy bezpośrednio. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L40" style="font-size: 110%; font-weight: bold;">Twierdzenie L40</span><br/>
Niech <math>g, m \in \mathbb{Z} \;</math> i <math>\; m \geqslant 3</math> oraz <math>\gcd (g, m) = 1</math>. Liczba <math>g</math> jest generatorem modulo <math>m</math> wtedy i&nbsp;tylko wtedy, gdy

::<math>g^{\tfrac{\varphi (m)}{q}} \not\equiv 1 \!\! \pmod{m}</math>

dla każdego dzielnika pierwszego <math>q</math> liczby <math>\varphi (m)</math>.

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

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

Przypuśćmy, dla uzyskania sprzeczności, że dla pewnego dzielnika pierwszego <math>q</math> liczby <math>\varphi (m)</math> jest

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

Zatem

::<math>\operatorname{ord}(g, m) \leqslant {\small\frac{\varphi (m)}{q}} < \varphi (m)</math>

Wbrew założeniu, że liczba <math>g</math> jest generatorem modulo <math>p</math>.

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

Niech <math>h = \operatorname{ord}(g, m)</math>, zatem <math>h \mid \varphi (m)</math> (zobacz [[#L9|L9]]). Przypuśćmy, dla uzyskania sprzeczności, że <math>\varphi (m) = h d \;</math> i <math>\; d > 1</math>. Konsekwentnie istnieje liczba pierwsza <math>q</math> taka, że <math>q \mid d</math>, czyli <math>q \mid \varphi (m)</math>. Ponieważ <math>h</math> jest rzędem liczby <math>g</math> modulo <math>m</math>, to

::<math>g^h \equiv 1 \!\! \pmod{m}</math>

Podnosząc obie strony kongruencji do potęgi <math>{\small\frac{d}{q}}</math>, dostajemy

::<math>1 \equiv (g^h)^{\tfrac{d}{q}} \equiv g^{\tfrac{h d}{q}} \equiv g^{\tfrac{\varphi (m)}{q}} \!\! \pmod{m}</math>

Wbrew założeniu. Zatem musi być <math>d = 1 \;</math> i <math>\; h = \varphi (m)</math>, czyli <math>g</math> jest generatorem modulo <math>m</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



=== <span style="border-bottom:2px solid #000;">Generatory modulo <math>\boldsymbol{p}</math></span> ===

&nbsp;

<span id="L41" style="font-size: 110%; font-weight: bold;">Uwaga L41</span><br/>
Przedstawimy poniżej postać twierdzenia [[#L40|L40]] w&nbsp;przypadku, gdy moduł <math>m</math> jest liczbą pierwszą. Oczywiście twierdzenie [[#L40|L40]] jest bardziej ogólne, ale znacznie wygodniej jest korzystać ze szczególnej postaci w&nbsp;przypadku, gdy wiemy, że rozpatrywana liczba <math>m</math> jest liczbą pierwszą.



<span id="L42" style="font-size: 110%; font-weight: bold;">Twierdzenie L42</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą, <math>g \in \mathbb{Z} \;</math> i <math>\; p \nmid g</math>. Liczba <math>g</math> jest generatorem modulo <math>p</math> wtedy i&nbsp;tylko wtedy, gdy

::<math>g^{\tfrac{p - 1}{q}} \not\equiv 1 \!\! \pmod{p}</math>

dla każdego dzielnika pierwszego <math>q</math> liczby <math>p - 1</math>.



<span id="L43" style="font-size: 110%; font-weight: bold;">Twierdzenie L43</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli liczba <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> jest 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}}

<span style="border-bottom-style: double;">Pierwszy sposób</span><br/>
Z założenia <math>g</math> jest generatorem modulo <math>p</math>, zatem z&nbsp;twierdzenia [[#L36|L36]] mamy

::<math>g^{\tfrac{p - 1}{2}} \equiv - 1 \!\! \pmod{p}</math>

I z&nbsp;kryterium Eulera (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J31|J31]]) wynika natychmiast, że <math>g</math> jest liczbą niekwadratową modulo <math>p</math>. Co należało pokazać.

<br/><span style="border-bottom-style: double;">Drugi sposób</span><br/>
Z założenia <math>g</math> jest generatorem modulo <math>p</math>, ale z&nbsp;twierdzenia [[#L42|L42]] wiemy, że <math>g</math> jest generatorem modulo <math>p</math> wtedy i&nbsp;tylko wtedy, gdy dla wszystkich dzielników pierwszych <math>q</math> liczby <math>p - 1</math> jest

::<math>g^{\tfrac{p - 1}{q}} \not\equiv 1 \!\! \pmod{p}</math>

W przypadku liczb pierwszych nieparzystych liczba <math>2</math> jest zawsze dzielnikiem <math>p - 1</math>, zatem jeżeli <math>g</math> jest generatorem, to

::<math>g^{\tfrac{p - 1}{2}} \not\equiv 1 \!\! \pmod{p}</math>

I z&nbsp;kryterium Eulera wynika, że <math>g</math> nie może być liczbą kwadratową modulo <math>p</math>, czyli <math>g</math> jest liczbą niekwadratową modulo <math>p</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L44" style="font-size: 110%; font-weight: bold;">Twierdzenie L44</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli liczba <math>a</math> jest liczbą kwadratową modulo <math>p</math>, to <math>a</math> nie jest generatorem modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia <math>a</math> jest liczbą kwadratową modulo <math>p</math>, zatem z&nbsp;kryterium Eulera (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J31|J31]]) mamy

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

Zatem <math>\operatorname{ord}(a, p) \leqslant {\small\frac{p - 1}{2}} < p - 1</math>, czyli <math>a</math> nie jest generatorem modulo <math>p</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L45" style="font-size: 110%; font-weight: bold;">Uwaga L45</span><br/>
Ponieważ liczba generatorów modulo liczba pierwsza <math>p</math> jest równa <math>\varphi (p - 1)</math>, to z&nbsp;zadań [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H49|H49]], [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H50|H50]] wynika, że

:*&nbsp;&nbsp;&nbsp;<math>\varphi (p - 1) = {\small\frac{p - 1}{2}}</math> wtedy i&nbsp;tylko wtedy, gdy <math>p - 1 = 2^k</math>

:*&nbsp;&nbsp;&nbsp;<math>\varphi (p - 1) = {\small\frac{p - 1}{2}} - 1</math> wtedy i&nbsp;tylko wtedy, gdy <math>p - 1 = 2 q</math>, gdzie <math>q \geqslant 3</math> jest liczbą pierwszą

Zauważmy, że pierwszy punkt odpowiada sytuacji, gdy wszystkie liczby niekwadratowe modulo <math>p</math> są generatorami modulo <math>p</math>. Liczba pierwsza <math>p</math> musi być liczbą pierwszą Fermata <math>p = 2^{2^{\large n}} + 1</math> (zobacz [[Ciągi liczbowe#C49|C49]]).

Drugi punkt odpowiada sytuacji, gdy wszystkie liczby niekwadratowe modulo <math>p</math>, poza dokładnie jedną, są generatorami modulo <math>p</math>. Liczba pierwsza <math>p</math> musi być postaci <math>p = 2 q + 1</math>, gdzie <math>q \geqslant 3</math> jest liczbą pierwszą. Łatwo możemy stwierdzić, że liczba <math>- 1</math> jest jedyną liczbą niekwadratową modulo <math>p</math>, która w&nbsp;tym przypadku nie jest generatorem modulo <math>p</math>. Z&nbsp;kryterium Eulera (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J31|J31]]) otrzymujemy

::<math>(- 1)^{\tfrac{p - 1}{2}} = (- 1)^q = - 1</math>

czyli <math>- 1</math> jest liczbą niekwadratową modulo <math>p</math>.

Dla liczb pierwszych nieparzystych <math>\operatorname{ord}(- 1, p) = 2</math>, bo <math>(- 1)^1 \not\equiv 1 \!\! \pmod{p} \;</math> i <math>\; (- 1)^2 \equiv 1 \!\! \pmod{p}</math>. Natomiast dla liczb pierwszych postaci <math>p = 2 q + 1</math>, gdzie <math>q \geqslant 3</math> jest liczbą pierwszą, mamy <math>\varphi (p) = p - 1 = 2 q \geqslant 6</math>. Zatem nie może być <math>\operatorname{ord}(- 1, p) = \varphi (p)</math>.



<span id="L46" style="font-size: 110%; font-weight: bold;">Zadanie L46</span><br/>
Niech <math>p</math> będzie liczbą pierwszą postaci <math>4 k + 3</math>. Pokazać, że jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to <math>- g</math> nie jest generatorem modulo <math>p</math>.

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

::<math>(- g)^{\varphi (p) / 2} = (- g)^{\tfrac{p - 1}{2}}</math>

:::::<math>\: = (- 1)^{\tfrac{p - 1}{2}} g^{\tfrac{p - 1}{2}}</math>

:::::<math>\: \equiv (- 1)^{\tfrac{4 k + 2}{2}} \cdot (- 1)</math>

:::::<math>\: \equiv - (- 1)^{2 k + 1}</math>

:::::<math>\: \equiv + 1 \!\! \pmod{p}</math>

Zatem <math>- g</math> nie może być generatorem modulo <math>p</math>, dla liczby pierwszej <math>p</math> postaci <math>4 k + 3</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L47" style="font-size: 110%; font-weight: bold;">Zadanie L47</span><br/>
Niech <math>p</math> będzie liczbą pierwszą postaci <math>4 k + 1</math>. Pokazać, że jeżeli liczba <math>g</math> jest generatorem modulo <math>p</math>, to liczba <math>- g</math> też jest generatorem modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Niech <math>h = \operatorname{ord}(- g, p)</math>. Z&nbsp;definicji mamy <math>(- g)^h \equiv 1 \pmod{p}</math>. Podnosząc obie strony kongruencji do kwadratu, otrzymujemy

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

Ale rząd liczby <math>g</math> modulo <math>p</math> musi dzielić wykładnik <math>2 h</math>, zatem <math>(p - 1) \mid 2 h</math>, czyli <math>4 k \mid 2 h</math>, skąd wynika, że <math>h</math> musi być liczbą parzystą. Jeśli tak, to

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

Ponownie rząd liczby <math>g</math> musi dzielić <math>h</math>, czyli <math>(p - 1) \mid h</math>.

Z właściwości <math>h</math> jako rzędu liczby <math>- g</math> mamy <math>h \mid (p - 1)</math>. Wynika stąd, że <math>h = p - 1 \;</math> i <math>\; - g</math> jest generatorem modulo <math>p = 4 k + 1</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L48" style="font-size: 110%; font-weight: bold;">Zadanie L48</span><br/>
Niech <math>p, q \in \mathbb{P}</math>, gdzie <math>q \geqslant 3</math>. Pokazać, że jeżeli <math>p = 2 q + 1 \;</math> i <math>\; g \not\equiv - 1 \!\! \pmod{p}</math> jest liczbą niekwadratową modulo <math>p</math>, to <math>g</math> jest generatorem modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zauważmy, że liczba <math>p - 1</math> ma tylko dwa dzielniki pierwsze. Ponieważ z&nbsp;założenia <math>g</math> jest liczbą niekwadratową modulo <math>p</math>, to (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J31|J31]])

::<math>g^{\tfrac{p - 1}{2}} \equiv - 1 \!\! \pmod{p}</math>

Mamy też

::<math>g^{\tfrac{p - 1}{q}} = g^2 \not\equiv 1 \!\! \pmod{p}</math>

Istotnie, gdyby prawdziwa była kongruencja

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

to mielibyśmy <math>g \equiv - 1 \!\! \pmod{p} \;</math> lub <math>\; g \equiv 1 \!\! \pmod{p}</math>. Pierwszy przypadek nie jest możliwy ze względu na uczynione założenie, a&nbsp;w&nbsp;drugim przypadku <math>g</math> byłaby liczbą kwadratową modulo <math>p</math>, bo (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J42|J42]] p.2)

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

Widzimy, że spełnione są założenia twierdzenia [[#L42|L42]], zatem <math>g</math> jest generatorem modulo <math>p</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L49" style="font-size: 110%; font-weight: bold;">Zadanie L49</span><br/>
Niech <math>p \in \mathbb{P}</math>. Pokazać, że jeżeli liczba <math>p - 1</math> ma dzielnik pierwszy nieparzysty <math>q</math>, to istnieje liczba całkowita <math>a</math>, która jest liczbą niekwadratową modulo <math>p</math> i&nbsp;nie jest generatorem modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Wiemy, że istnieje <math>{\small\frac{p - 1}{2}}</math> liczb niekwadratowych modulo <math>p</math> (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J30|J30]]). Oznaczmy przez <math>b</math> dowolną z&nbsp;tych liczb, czyli

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

Niech teraz <math>a = b^q</math>. Liczba <math>a</math> jest liczbą niekwadratową modulo <math>p</math>, bo

::<math>\left( {\small\frac{a}{p}} \right)_{\small{\!\! J}} = \left( {\small\frac{b^q}{p}} \right)_{\small{\!\! J}} = \left[ \left( {\small\frac{b}{p}} \right)_{\small{\!\! J}} \right]^q = (- 1)^q = - 1</math>

Ale

::<math>a^{\tfrac{p - 1}{q}} = (b^q)^{\tfrac{p - 1}{q}} = b^{p - 1} \equiv 1 \!\! \pmod{p}</math>

Ponieważ <math>\operatorname{ord}(a, p) \leqslant {\small\frac{p - 1}{q}} < p - 1</math>, to <math>a</math> nie jest generatorem modulo <math>p</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L50" style="font-size: 110%; font-weight: bold;">Zadanie L50</span><br/>
Pokazać, że istnieje nieskończenie wiele liczb pierwszych, dla których liczba <math>2</math> nie jest generatorem. Wskazówka: rozważyć liczby pierwsze postaci <math>p = 2^n k + 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Dla <math>n \geqslant 3</math> liczbę <math>p</math> możemy zapisać w&nbsp;postaci <math>p = 8 k \cdot 2^{n - 3} + 1</math>, zatem <math>p \equiv 1 \!\! \pmod{8}</math> i&nbsp;liczba <math>2</math> jest liczbą kwadratową modulo <math>p</math> (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J34|J34]] p.7), czyli nie jest generatorem modulo <math>p</math>. Ponieważ liczb pierwszych postaci <math>p = 2^n k + 1</math> istnieje nieskończenie wiele (zobacz [[#L27|L27]] lub [[Ciągi liczbowe#C28|C28]]), to możemy stwierdzić, że istnieje nieskończenie wiele liczb pierwszych, dla których liczba <math>2</math> nie jest generatorem. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L51" style="font-size: 110%; font-weight: bold;">Zadanie L51</span><br/>
Pokazać, że jeżeli liczby <math>q \geqslant 7</math> oraz <math>p = 4 q + 1</math> są liczbami pierwszymi, to liczby <math>2 \:</math> i <math>\: 3</math> są generatorami modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Liczby pierwsze <math>p = 4 q + 1</math> tworzą ciąg <math>13, 29, 53, 149, 173, 269, 293, 317, 389, 509, 557, 653, 773, 797, \ldots</math>

Przypuszczamy, że liczb pierwszych <math>p</math> postaci <math>p = 4 q + 1</math> jest nieskończenie wiele, a&nbsp;ilość takich liczb <math>p \leqslant n</math> jest w&nbsp;przybliżeniu równa <math>{\small\frac{C n}{(\log n)^2}}</math>.

Dla <math>q = 3</math> łatwo sprawdzamy, że <math>\operatorname{ord}(2, 13) = 12 \;</math> i <math>\; \operatorname{ord}(3, 13) = 3</math>.

Ponieważ liczba <math>q \geqslant 7</math> jest liczbą pierwszą, to może być tylko postaci <math>q = 6 k + 1</math> lub <math>q = 6 k + 5</math>. Wynika stąd, że liczba <math>p = 4 q + 1</math> musi być postaci <math>p = 24 k + 5</math>, bo w&nbsp;drugim przypadku otrzymujemy <math>p = 24 k + 21</math>, która jest liczbą złożoną.

Widzimy, że liczby <math>2 \:</math> i <math>\: 3</math> są liczbami niekwadratowymi modulo <math>p</math>, bo odpowiednio <math>p \equiv 5 \!\! \pmod{8} \;</math> i <math>\; p \equiv 5 \!\! \pmod{12}</math> (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J42|J42]] p.7 i [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J47|J47]]).

Niech <math>a</math> oznacza dowolną z&nbsp;liczb <math>2</math> lub <math>3</math> i&nbsp;niech <math>h</math> będzie rzędem liczby <math>a</math> modulo <math>p</math>. Oczywiście <math>h \mid (p - 1)</math>, czyli <math>h \mid 4 q</math>, zatem możliwe wartości <math>h</math>, to <math>1, 2, 4, q, 2 q, 4 q</math>.

Ponieważ dla <math>p \geqslant 13</math> nie są możliwe kongruencje <math>a^1 \equiv 1 \!\! \pmod{p}</math>, <math>a^2 \equiv 1 \!\! \pmod{p}</math>, to <math>h \neq 1</math> i <math>h \neq 2</math>. Nie może też być <math>h = 4</math>, bo kongruencja <math>a^2 \equiv - 1 \!\! \pmod{p}</math> również nie jest możliwa (zobacz [[#L6|L6]]).

Z kryterium Eulera (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J31|J31]]) mamy

::<math>a^{(p - 1) / 2} = a^{2 q} \equiv - 1 \!\! \pmod{p}</math>

Widzimy, że nie może być <math>a^q \equiv 1 \!\! \pmod{p}</math>, bo wtedy byłoby <math>a^{2 q} \equiv 1 \!\! \pmod{p}</math>. Zatem musi być <math>a^{4 q} \equiv 1 \!\! \pmod{p}</math>, czyli rząd liczby <math>a</math> modulo <math>p</math> jest równy <math>p - 1</math> i <math>a</math> jest generatorem modulo <math>p</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L52" style="font-size: 110%; font-weight: bold;">Zadanie L52</span><br/>
Znaleźć rozwiązania układu kongruencji 

::<math>\left\{ 
\begin{array}{rl}
  11^x \cdot y^5 \equiv 4 & \pmod{13} \\
  6^x \cdot y^6 \equiv 9 & \pmod{13} \\
\end{array}
\right.</math>

Wskazówka: liczba <math>2</math> jest generatorem modulo <math>13</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Dokonujemy podstawień: <math>y \equiv 2^z \!\! \pmod{13}, \qquad 11 \equiv 2^7 \!\! \pmod{13}, \qquad 6 \equiv 2^5 \!\! \pmod{13}, \qquad 9 \equiv 2^8 \!\! \pmod{13}</math>

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left\{ 
\begin{array}{rl}
  2^{7 x} \cdot 2^{5 z} \equiv 2^2 & \pmod{13} \\
  2^{5 x} \cdot 2^{6 z} \equiv 2^8 & \pmod{13} \\
\end{array}
\right.</math><br/>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left\{ 
\begin{array}{rl}
  2^{7 x + 5 z} \equiv 2^2 & \pmod{13} \\
  2^{5 x + 6 z} \equiv 2^8 & \pmod{13} \\
\end{array}
\right.</math><br/>
</div>

Korzystając z&nbsp;twierdzenia [[#L23|L23]], dostajemy

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left\{ 
\begin{array}{rl}
  7 x + 5 z \equiv 2 & \pmod{12} \\
  5 x + 6 z \equiv 8 & \pmod{12} \\
\end{array}
\right.</math>
</div>

Mnożąc pierwszą kongruencję przez <math>5</math>, drugą przez <math>7</math>, otrzymujemy

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left\{ 
\begin{array}{rl}
  35 x + 25 z \equiv 10 & \pmod{12} \\
  35 x + 42 z \equiv 56 & \pmod{12} \\
\end{array}
\right.</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left\{ 
\begin{array}{rl}
  - x + z \equiv 10 & \pmod{12} \\
  - x + 6 z \equiv 8 & \pmod{12} \\
\end{array}
\right.</math>
</div>

Odejmując kongruencje od siebie, mamy 

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>
\begin{array}{rl}
  5 z \equiv - 2 & \pmod{12} \\
  25 z \equiv - 10 & \pmod{12} \\
  z \equiv 2 & \pmod{12} \\
\end{array}
</math>
</div>

Czyli <math>y \equiv 2^2 \equiv 4 \!\! \pmod{13}</math>. Podstawiając <math>z \equiv 2 \!\! \pmod{12}</math> do pierwszej kongruencji, dostajemy <math>x \equiv 4 \!\! \pmod{12}</math>. Zatem rozwiązaniem układu kongruencji są liczby <math>x \equiv 4 \!\! \pmod{12}</math> oraz <math>y \equiv 4 \!\! \pmod{13}</math>.<br/>
&#9633;
{{\Spoiler}}



=== <span style="border-bottom:2px solid #000;">Liczby, które nie mają generatora</span> ===

&nbsp;

<span id="L53" style="font-size: 110%; font-weight: bold;">Uwaga L53</span><br/>
Rozważymy dwa przypadki: gdy liczba pierwsza nieparzysta <math>p</math> dzieli <math>m</math> i&nbsp;gdy liczba pierwsza nieparzysta <math>p</math> nie dzieli <math>m</math>. W&nbsp;pierwszym przypadku <math>m</math> jest postaci <math>m = r p^k</math>, a&nbsp;w&nbsp;drugim <math>m = 2^k</math>.



<span id="L54" style="font-size: 110%; font-weight: bold;">Twierdzenie L54</span><br/>
Niech <math>k, m \in \mathbb{Z}_+</math> i&nbsp;liczba <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli <math>m = r p^k</math>, gdzie <math>p \nmid r \;</math> i <math>\; r \geqslant 3</math>, to nie istnieją generatory modulo <math>m</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>a</math> będzie dowolną liczbą całkowitą i <math>\gcd (a, m) = 1</math>. Ponieważ <math>\varphi (r) \;</math> i <math>\; \varphi (p^k)</math> są liczbami parzystymi (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H38|H38]]), to z&nbsp;twierdzenia Eulera otrzymujemy

::<math>a^{\varphi (m) / 2} = \left[ a^{\varphi (r)} \right]^{\varphi (p^k) / 2} \equiv 1 \!\! \pmod{r}</math>

::<math>a^{\varphi (m) / 2} = \left[ a^{\varphi (p^k)} \right]^{\varphi (r) / 2} \equiv 1 \!\! \pmod{p^k}</math>

Ponieważ liczby <math>r \;</math> i <math>\; p^k</math> są względnie pierwsze, zatem (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J1|J1]])

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

Co oznacza, że nie istnieje liczba, której rząd modulo <math>m = r p^k</math> wynosiłby <math>\varphi (m)</math>, czyli nie istnieją generatory modulo <math>m</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L55" style="font-size: 110%; font-weight: bold;">Wniosek L55</span><br/>
Z twierdzenia [[#L54|L54]] wynika natychmiast, że poza potęgami liczby <math>2</math> jedynie liczby postaci <math>p^k</math> i <math>2 p^k</math>, gdzie <math>p</math> jest liczbą pierwszą nieparzystą, mogą mieć generatory. Problem istnienia generatorów dla liczb postaci <math>2^k</math> rozstrzyga następne twierdzenie.



<span id="L56" style="font-size: 110%; font-weight: bold;">Twierdzenie L56</span><br/>
Nie istnieją generatory modulo <math>2^k</math> dla <math>k \geqslant 3</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Udowodnimy (indukcja matematyczna), że dla dowolnej liczby nieparzystej <math>a</math> i <math>k \geqslant 3</math> prawdziwa jest kongruencja

::<math>a^{2^{\large {k - 2}}} \equiv 1 \!\! \pmod{2^k} \qquad \qquad (1)</math>

Wzór jest prawdziwy dla <math>k = 3</math>, bo dla dowolnej liczby nieparzystej <math>a</math> prawdziwa jest kongruencja

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

Dla dowodu wystarczy rozważyć modulo <math>8</math> liczby nieparzyste postaci <math>4 j + 1</math> i <math>4 j + 3</math>.

Załóżmy, że wzór <math>(1)</math> jest prawdziwy dla pewnego <math>k \geqslant 3</math>. Z&nbsp;uczynionego założenia wynika, że istnieje taka liczba całkowita <math>t</math>, że

::<math>a^{2^{\large {k - 2}}} = 1 + t \cdot 2^k</math>

Podnosząc obie strony powyższej równości do kwadratu, z&nbsp;łatwością pokazujemy, że dowodzony wzór jest prawdziwy dla <math>k + 1</math>

::<math>a^{2^{\large {k - 1}}} = 1 + 2 t \cdot 2^k + t^2 \cdot 2^{2 k} \equiv 1 \!\! \pmod{2^{k + 1}}</math>

Co kończy dowód indukcyjny wzoru <math>(1)</math>. Ze wzoru <math>(1)</math> wynika natychmiast, że <math>\operatorname{ord}(a, 2^k) \leqslant 2^{k - 2}</math>, ale <math>\varphi (2^k) = 2^{k - 1}</math>, zatem rząd liczby nieparzystej <math>a</math> modulo <math>2^k</math> nigdy nie będzie równy <math>\varphi (2^k)</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



=== <span style="border-bottom:2px solid #000;">Liczba pierwsza ma generator</span> ===

&nbsp;

<span id="L57" style="font-size: 110%; font-weight: bold;">Uwaga L57</span><br/>
Zauważmy, że istnienie generatora dla liczby pierwszej <math>p</math> jest prostym wnioskiem z&nbsp;twierdzenia [[#L21|L21]]. Ponieważ <math>h = p - 1</math> dzieli liczbę <math>p - 1</math>, to istnieje <math>\varphi (p - 1)</math> liczb, których rząd modulo <math>p</math> jest równy <math>h = p - 1 = \varphi (p)</math>, czyli generatorów modulo <math>p</math>. Dowód twierdzenia [[#L21|L21]] jest dowodem niekonstruktywnym – nie pokazaliśmy jawnie sposobu otrzymania liczby, która byłaby generatorem modulo <math>p</math>. W&nbsp;kolejnym twierdzeniu przedstawimy dowód konstruktywny.



<span id="L58" style="font-size: 110%; font-weight: bold;">Twierdzenie L58 (Carl Friedrich Gauss, 1801)</span><br/>
Każda liczba pierwsza ma generator.

{{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 liczbą pierwszą. Liczba <math>p = 2</math> ma generator <math>g = 1</math>, bo <math>\varphi (2) = 1</math>. Zatem możemy założyć, że <math>p</math> jest liczbą pierwszą nieparzystą. Niech liczba <math>p - 1</math> ma następujący rozkład na czynniki pierwsze

::<math>p - 1 = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>

Z twierdzenia Lagrange'a (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J14|J14]]) wynika, że każda z&nbsp;kongruencji

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

ma co najwyżej <math>{\small\frac{p - 1}{q_i}}</math> rozwiązań. Ponieważ

::<math>(p - 1) - {\small\frac{p - 1}{q_i}} \geqslant (p - 1) - {\small\frac{p - 1}{2}} = {\small\frac{p - 1}{2}}</math>

to dla każdej z&nbsp;wypisanych wyżej kongruencji istnieje taka liczba <math>w_i \not\equiv 0 \!\! \pmod{p}</math>, '''która nie jest''' rozwiązaniem powyższej kongruencji.


Zdefiniujmy liczbę <math>a_i</math> następująco

::<math>a_i = (w_i)^{(p - 1) / q_i^{\large \alpha_i}}</math>

Zauważmy, że

::<math>(a_i)^{q_i^{\large \alpha_i}} = (w_i)^{p - 1} \equiv 1 \!\! \pmod{p}</math>

oraz

::<math>(a_i)^{q_i^{\large \alpha_i - 1}} = (w_i)^{\tfrac{p - 1}{q_i}} \not\equiv 1 \!\! \pmod{p}</math>

Zatem <math>\operatorname{ord}(a_i, p) = q^{\alpha_i}_i</math> (zobacz [[#L25|L25]]). Wynika stąd, że dla <math>i \neq j</math> jest 

::<math>\gcd (\operatorname{ord}(a_i, p), \operatorname{ord}(a_j, p) ) = \gcd (q^{\alpha_i}_i, q^{\alpha_j}_j) = 1</math>


Pamiętamy, że liczby <math>w_i</math> wybraliśmy tak, aby <math>\gcd (w_i, p) = 1</math>, czyli <math>\gcd (a_i, p) = 1</math>. Ponieważ spełnione są założenia twierdzenia [[#L15|L15]], to

::<math>\operatorname{ord}(a_1 \cdot \ldots \cdot a_s, p) = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s = p - 1</math>

Co oznacza, że liczba <math>a_1 \cdot \ldots \cdot a_s</math> jest generatorem modulo <math>p</math>.<br/>
&#9633;
{{\Spoiler}}



=== <span style="border-bottom:2px solid #000;">Kwadrat liczby pierwszej ma generator</span> ===

&nbsp;

<span id="L59" style="font-size: 110%; font-weight: bold;">Twierdzenie L59</span><br/>
Niech <math>p \in \mathbb{P}</math>, <math>a \in \mathbb{Z}</math> i <math>\gcd (a, p) = 1</math>. Jeżeli <math>h = \operatorname{ord}(a, p)</math>, to

::<math>\operatorname{ord}(a, p^2) =
\begin{cases}
 h & \text{gdy } a^h \equiv 1 \; \pmod{p^2} \\
 h p & \text{gdy } a^h \not\equiv 1 \; \pmod{p^2} \\
\end{cases}
</math>

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

'''1. Przypadek, gdy <math>\boldsymbol{a^h \equiv 1 \!\! \pmod{p^2}}</math>'''

Zauważmy, że nie istnieje liczba <math>d < h</math> taka, że <math>a^d \equiv 1 \!\! \pmod{p^2}</math>, bo mielibyśmy <math>a^d \equiv 1 \!\! \pmod{p}</math>, wbrew założeniu, że <math>h</math> jest rzędem liczby <math>a</math> modulo <math>p</math>. Zatem <math>\operatorname{ord}(a, p^2) = h</math>.

'''2. Przypadek, gdy <math>\boldsymbol{a^h \not\equiv 1 \!\! \pmod{p^2}}</math>'''

Niech <math>f = \operatorname{ord}(a, p^2)</math>. Ponieważ <math>p \mid p^2</math>, to <math>h \mid f</math> (zobacz [[#L8|L8]] p.2), czyli <math>f = s \cdot h</math>.

Z definicji liczby <math>h</math> mamy

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

Z powyższej kongruencji oraz twierdzenia [[#L123|L123]] wynika, że

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

Liczba <math>f</math> jest rzędem liczby <math>a</math> modulo <math>p^2</math>, zatem <math>f \mid h p</math> (zobacz [[#L8|L8]] p.1). Ponieważ <math>f = s \cdot h</math>, to mamy

::<math>s h \mid h p \qquad \Longrightarrow \qquad s \mid p \qquad \Longrightarrow \qquad s = 1 \qquad \text{lub} \qquad s = p \qquad \Longrightarrow \qquad f = h \qquad \text{lub} \qquad f = h p</math>

Ale nie może być <math>f = h</math>, bo mielibyśmy <math>a^h \equiv 1 \!\! \pmod{p^2}</math>, wbrew założeniu. Zatem musi być <math>f = h p</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L60" style="font-size: 110%; font-weight: bold;">Twierdzenie L60</span><br/>
Niech <math>h</math> będzie rzędem liczby <math>a</math> modulo <math>p</math>. Rząd przynajmniej jednej z&nbsp;liczb <math>a</math> i <math>a + p</math> modulo <math>p^2</math> jest równy <math>h p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Z założenia <math>\operatorname{ord}(a, p) = \operatorname{ord}(a + p, p) = h</math> (zobacz [[#L14|L14]]). Z&nbsp;twierdzenia [[#L59|L59]] wiemy, że rząd każdej z&nbsp;liczb <math>a</math> i <math>a + p</math> modulo <math>p^2</math> może być równy <math>h</math> lub <math>h p</math>. Udowodnimy, że rzędy liczb <math>a</math> i <math>a + p</math> modulo <math>p^2</math> nie mogą być jednocześnie równe <math>h</math>, zatem rząd przynajmniej jednej z&nbsp;nich jest równy <math>h p</math>.

Załóżmy, dla uzyskania sprzeczności, że <math>\operatorname{ord}(a, p^2) = \operatorname{ord}(a + p, p^2) = h</math>. Wynika stąd, że prawdziwe są kongruencje

::<math>a^h \equiv 1 \!\! \pmod{p^2} \qquad \text{i} \qquad (a + p)^h \equiv 1 \!\! \pmod{p^2}</math>

Ze wzoru dwumianowego dostajemy

::<math>(a + p)^h = \sum_{i = 0}^h \binom{h}{i} a^{h - i} p^i</math>

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

Zatem modulo <math>p^2</math> jest

::<math>0 \equiv (a + p)^h - a^h</math>

::<math>\;\;\: \equiv a^h + h \cdot a^{h - 1} p + \sum_{i = 2}^h \binom{h}{i} a^{h - i} p^i - a^h</math>

::<math>\;\;\: \equiv h \cdot a^{h - 1} p \!\! \pmod{p^2}</math>

Czyli <math>p^2 \mid (h \cdot a^{h - 1} p)</math>, zatem <math>p \mid (h \cdot a^{h - 1})</math>. Z&nbsp;założenia <math>\gcd (a, p) = 1</math>, skąd wynika, że <math>p \mid h</math>, ale <math>h</math> jest rzędem liczby <math>a</math> modulo <math>p</math>, zatem <math>h \mid \varphi (p)</math>. Łącząc, otrzymujemy, że <math>p \mid \varphi (p)</math>, czyli <math>p \mid (p - 1)</math>, co jest niemożliwe. Otrzymana sprzeczność kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span id="L61" style="font-size: 110%; font-weight: bold;">Przykład L61</span><br/>
Niech <math>p = 7</math>. Dla <math>a = 2, 3, 4, 5, 6</math> mamy odpowiednio <math>h = \operatorname{ord}(a, p) = 3, 6, 3, 6, 2</math>. Łatwo sprawdzamy, że dla tych liczb jest

::<math>\operatorname{ord}(a, p^2) = \operatorname{ord}(a + p, p^2) = h p</math>



<span id="L62" style="font-size: 110%; font-weight: bold;">Twierdzenie L62</span><br/>
Jeżeli liczba <math>g</math> jest generatorem modulo <math>p</math>, to <math>g</math> lub <math>g + p</math> jest generatorem modulo <math>p^2</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Jeżeli <math>g</math> jest generatorem modulo <math>p</math>, to rząd liczby <math>g</math> modulo <math>p</math> jest równy <math>\varphi (p) = p - 1</math>. Z&nbsp;twierdzenia [[#L60|L60]] otrzymujemy natychmiast, że rząd przynajmniej jednej z&nbsp;liczb <math>g</math> lub <math>g + p</math> jest równy <math>(p - 1) p = \varphi (p^2)</math>, czyli jedna z&nbsp;tych liczb jest generatorem modulo <math>p^2</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



=== <span style="border-bottom:2px solid #000;">Liczba <math>\boldsymbol{p^n}</math> ma generator (<math>\boldsymbol{p \geqslant 3}</math>)</span> ===

&nbsp;

<span id="L63" style="font-size: 110%; font-weight: bold;">Twierdzenie L63</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą i <math>n \geqslant 2</math>. Jeżeli <math>g</math> jest generatorem modulo <math>p^n</math>, to jest generatorem modulo <math>p^{n + 1}</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>f = \operatorname{ord}(g, p^{n + 1})</math>. Z&nbsp;założenia <math>h = \operatorname{ord}(g, p^n) = \varphi (p^n)</math>.

Ponieważ <math>p^n \mid p^{n + 1}</math>, to z&nbsp;twierdzenia [[#L8|L8]] p.2 wiemy, że <math>h \mid f</math>, zatem <math>f = k h = k \varphi (p^n)</math>.

Z zadania [[#L9|L9]] mamy <math>f \mid \varphi (p^{n + 1})</math>, czyli <math>k \varphi (p^n) \mid \varphi (p^{n + 1})</math>, zatem (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H36|H36]]) <math>k \varphi (p^n) \mid p \varphi (p^n)</math>. Wynika stąd, że <math>k \mid p</math>, zatem <math>k = 1</math> lub <math>k = p</math>.

Jeżeli <math>k = p</math>, to <math>f = p \varphi (p^n) = \varphi (p^{n + 1})</math> i&nbsp;twierdzenie zostało dowiedzione.

Jeżeli <math>k = 1</math>, to <math>f = \varphi (p^n)</math>. Aby wykluczyć wartość <math>k = 1</math>, wystarczy pokazać, że <math>f = \varphi (p^n)</math> nie może być rzędem liczby <math>g</math> modulo <math>p^{n + 1}</math>, czyli, że

::<math>g^{\varphi (p^{\large n})} \not\equiv 1 \!\! \pmod{p^{n + 1}}</math>

Z twierdzenia Eulera mamy

::<math>g^{\varphi (p^{\large n - 1})} \equiv 1 \!\! \pmod{p^{n - 1}}</math>

Zatem istnieje taka liczba całkowita <math>s</math>, że

::<math>g^{\varphi (p^{\large n - 1})} = 1 + s p^{n - 1}</math>

Gdyby <math>p \mid s</math>, to modulo <math>p^n</math> mielibyśmy

::<math>g^{\varphi (p^{\large n - 1})} \equiv 1 \!\! \pmod{p^n}</math>

Wbrew założeniu, że <math>h = \operatorname{ord}(g, p^n) = \varphi (p^n) = p \varphi (p^{n - 1})</math>. Zatem <math>p \nmid s</math>.

Korzystając ze wzoru dwumianowego, dostajemy

::<math>g^{\varphi (p^{\large n})} = g^{p \varphi (p^{\large n - 1})}</math>

:::<math>\quad \: = [g^{\varphi (p^{\large n - 1})}]^p</math>

:::<math>\quad \: = (1 + s p^{n - 1})^p =</math>

:::<math>\quad \: = \sum_{i = 0}^{p} \binom{p}{i} s^i p^{i (n - 1)} =</math>

:::<math>\quad \: = 1 + s p^n + {\small\frac{p (p - 1)}{2}} s^2 p^{2 (n - 1)} + \sum_{i = 3}^{p} \binom{p}{i} s^i p^{i (n - 1)}</math>

:::<math>\quad \: \not\equiv 1 \!\! \pmod{p^{n + 1}}</math>

Wystarczy zauważyć, że w&nbsp;przedostatniej linii trzeci i&nbsp;czwarty wyraz są podzielne przez <math>p^{n + 1}</math>, co wynika z&nbsp;prostych oszacowań

*&nbsp;&nbsp;&nbsp;dla <math>\; n \geqslant 2 \;</math> jest <math>\; 1 + 2 (n - 1) \geqslant n + 1</math>

*&nbsp;&nbsp;&nbsp;dla <math>\; n \geqslant 2 \;</math> oraz <math>\; i \geqslant 3 \; </math> jest <math>\; i(n - 1) = n - 1 + (i - 1)(n - 1) \geqslant n - 1 + 2 \cdot 1 = n + 1</math>

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



=== <span style="border-bottom:2px solid #000;">Liczba <math>\boldsymbol{2 p^n}</math> ma generator (<math>\boldsymbol{p \geqslant 3}</math>)</span> ===

&nbsp;

<span id="L64" style="font-size: 110%; font-weight: bold;">Twierdzenie L64</span><br/>
Każda liczba <math>2 p^n</math> ma generator, gdzie <math>p</math> jest liczbą pierwszą nieparzystą i <math>n \geqslant 1</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>g</math> będzie generatorem modulo <math>p^n</math>. Nie zmniejszając ogólności, możemy założyć, że <math>g</math> jest liczbą nieparzystą (gdyby było inaczej, to rozpatrywalibyśmy liczbę <math>g + p^n</math>, która też jest generatorem modulo <math>p^n</math>). Ponieważ liczby <math>g \,</math> i <math>\, p^n</math> są nieparzyste i <math>\operatorname{ord}(g, p^n) = \varphi (p^n)</math>, to <math>\operatorname{ord}(g, 2 p^n) = \varphi (p^n) = \varphi (2 p^n)</math> (zobacz [[#L17|L17]]), czyli <math>g</math> jest generatorem modulo <math>2 p^n</math>.

Jeśli nie chcemy wchodzić w&nbsp;szczegóły zadania [[#L17|L17]], to wystarczy zauważyć, że wybór liczby <math>g</math> tak, aby była nieparzystym generatorem modulo <math>p^n</math>, zapewnia nam, że <math>\gcd (g, 2 p^n) = 1</math>, czyli rząd liczby <math>g</math> modulo <math>2 p^n</math> jest określony.

Ponieważ <math>p^n \mid 2p^n</math>, to <math>\operatorname{ord}(g, p^n) \mid \operatorname{ord}(g, 2 p^n)</math> (zobacz [[#L8|L8]] p.2), zatem możemy napisać

::<math>\varphi (2 p^n) = \varphi (2) \varphi (p^n) = \varphi (p^n) = \operatorname{ord}(g, p^n) \leqslant \operatorname{ord}(g, 2 p^n) \leqslant \varphi (2 p^n)</math>

Skąd natychmiast otrzymujemy, że <math>\operatorname{ord}(g, 2 p^n) = \varphi (2 p^n)</math>, czyli <math>g</math> jest generatorem modulo <math>2 p^n</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



=== <span style="border-bottom:2px solid #000;">Najmniejsze dodatnie generatory modulo <math>\boldsymbol{p}</math> i&nbsp;modulo <math>\boldsymbol{p^2}</math></span> ===

&nbsp;

<span id="L65" style="font-size: 110%; font-weight: bold;">Uwaga L65</span><br/>
Z twierdzenia [[#L43|L43]] wiemy, że każdy generator <math>g</math> modulo <math>p</math> jest liczbą niekwadratową modulo <math>p</math>. Ale nie każda liczba niekwadratowa modulo <math>p</math> jest generatorem modulo <math>p</math> (zobacz [[#L49|L49]]). Wynika stąd, że najmniejszy dodatni generator <math>\mathbb{g} (p)</math> modulo <math>p</math> nie może być mniejszy od najmniejszej dodatniej liczby niekwadratowej <math>\mathbb{n} (p)</math> modulo <math>p</math>, czyli <math>\mathbb{g} (p) \geqslant \mathbb{n} (p)</math>.

W tabeli przedstawiliśmy przypadki, gdy <math>\mathbb{g} (p) > \mathbb{n} (p)</math> dla początkowych liczb pierwszych.

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|-
! <math>\boldsymbol{p}</math> 
| <math>41</math> || <math>43</math> || <math>103</math> || <math>109</math> || <math>151</math> || <math>157</math> || <math>191</math> || <math>229</math> || <math>251</math> || <math>271</math> || <math>277</math> || <math>283</math> || <math>307</math> || <math>311</math> || <math>313</math> || <math>331</math> || <math>337</math> || <math>367</math> || <math>397</math> || <math>409</math> || <math>439</math> || <math>457</math> || <math>499</math>
|-
! <math>\boldsymbol{\mathbb{n} (p)}</math> 
| <math>3</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>7</math> || <math>2</math> || <math>2</math> || <math>3</math> || <math>2</math> || <math>2</math> || <math>2</math> || <math>11</math> || <math>5</math> || <math>2</math> || <math>5</math> || <math>3</math> || <math>2</math> || <math>7</math> || <math>3</math> || <math>5</math> || <math>2</math>
|-
! <math>\boldsymbol{\mathbb{g} (p)}</math> 
| <math>6</math> || <math>3</math> || <math>5</math> || <math>6</math> || <math>6</math> || <math>5</math> || <math>19</math> || <math>6</math> || <math>6</math> || <math>6</math> || <math>5</math> || <math>3</math> || <math>5</math> || <math>17</math> || <math>10</math> || <math>3</math> || <math>10</math> || <math>6</math> || <math>5</math> || <math>21</math> || <math>15</math> || <math>13</math> || <math>7</math>
|}


Ponieważ <math>\mathbb{g} (p) \geqslant \mathbb{n} (p)</math>, to z&nbsp;twierdzenia [[Liczby kwadratowe i niekwadratowe modulo. Wybrane zagadnienia#K18|K18]] otrzymujemy natychmiast, że istnieje niekończenie wiele liczb pierwszych <math>p</math> takich, że najmniejszy generator modulo <math>p</math> jest większy od <math>{\small\frac{\log p}{2 L \log 2}}</math>, gdzie <math>L</math> jest stałą Linnika (zobacz [[Ciągi liczbowe#C31|C31]]). Zobacz też [[Liczby kwadratowe i niekwadratowe modulo. Wybrane zagadnienia#K16|K16]] i [[Liczby kwadratowe i niekwadratowe modulo. Wybrane zagadnienia#K17|K17]].


Liczby <math>\mathbb{g} (p)</math> są bardzo małe, podobnie jak najmniejsze dodatnie liczby niekwadratowe <math>\mathbb{n} (p)</math>. Przypuszczamy<ref name="ElliottMurata1"/><ref name="OliveiraSilva1"/>, że istnieje skończona granica

::<math>\lim_{x \rightarrow \infty} {\small\frac{1}{\pi (x)}} \sum_{p \leqslant x} \mathbb{g} (p) = 4.9264 \ldots</math>

gdzie <math>p</math> są nieparzystymi liczbami pierwszymi.


Oszacowania <math>\mathbb{g} (p)</math>:

:*&nbsp;&nbsp;&nbsp;oszacowanie <math>\mathbb{g} (p) < \sqrt{p} - 2</math> jest prawdziwe dla <math>409 < p < 2.5 \cdot 10^{15}</math> i&nbsp;dla <math>p > 3.67 \cdot 10^{71}</math><ref name="CohenOliveiraSilvaTrudgian1"/>

:*&nbsp;&nbsp;&nbsp;oszacowanie <math>\mathbb{g} (p) < \sqrt{p}</math> jest prawdziwe dla <math>p > 10^{56}</math><ref name="McGownTrudgian1"/>

Dla <math>\mathbb{g} (p^2)</math> możemy łatwo pokazać oszacowanie <math>\mathbb{g} (p^2) < p</math> (zobacz [[#L66|L66]]).



<span id="L66" style="font-size: 110%; font-weight: bold;">Twierdzenie L66</span><br/>
Niech <math>a</math> będzie generatorem modulo <math>p</math>. Prawdziwe są następujące stwierdzenia

:*&nbsp;&nbsp;&nbsp;rząd liczby <math>a</math> modulo <math>p^2</math> jest równy <math>p - 1</math> lub <math>p(p - 1)</math>

:*&nbsp;&nbsp;&nbsp;<math>a</math> jest generatorem modulo <math>p^2</math> wtedy i&nbsp;tylko wtedy, gdy <math>a^{p - 1}
\not\equiv 1 \!\! \pmod{p^2}</math>

:*&nbsp;&nbsp;&nbsp;jeżeli <math>1 < a, b < p \;</math> i <math>\; b \,</math> jest elementem odwrotnym liczby <math>a</math> modulo <math>p</math>, to co najmniej jedna z&nbsp;liczb <math>a, b</math> jest generatorem modulo <math>p^2</math>

:*&nbsp;&nbsp;&nbsp;jeżeli <math>\mathbb{g} (p^2)</math> jest najmniejszym dodatnim generatorem modulo <math>p^2</math>, to prawdziwe jest oszacowanie <math>\mathbb{g} (p^2) < 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>f = \operatorname{ord}(a, p^2)</math>. Z&nbsp;definicji rzędu liczby

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

Zatem

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

Ponieważ <math>a</math> jest generatorem modulo <math>p</math>, to <math>(p - 1) \mid f</math>, czyli <math>f = s (p - 1)</math>. Z&nbsp;zadania [[#L9|L9]] wiemy, że <math>s(p - 1) \mid p (p - 1)</math>, zatem <math>s \mid p</math> i&nbsp;otrzymujemy <math>s = 1</math> lub <math>s = p</math>.

Wynika stąd, że jeżeli <math>a</math> jest generatorem modulo <math>p</math>, to rząd liczby <math>a</math> modulo <math>p^2</math> jest równy <math>p - 1</math> lub <math>p(p - 1)</math>.


'''Punkt 2.'''

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

Przypuśćmy, dla uzyskania sprzeczności, że <math>a^{p - 1} \equiv 1 \!\! \pmod{p^2}</math>, zatem

::<math>\operatorname{ord}(a, p^2) \leqslant p - 1 < p (p - 1) = \varphi (p^2)</math>

Wbrew założeniu, że <math>a</math> jest generatorem modulo <math>p^2</math>.

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

Z założenia <math>g^{p - 1} \not\equiv 1 \!\! \pmod{p^2}</math>, zatem nie może być <math>\operatorname{ord}(g, p^2) = p - 1</math>. Z&nbsp;punktu 1. wynika natychmiast, że <math>\operatorname{ord}(g, p^2) = p (p - 1) = \varphi (p^2)</math>. Co należało pokazać.


'''Punkt 3.'''

W pracy<ref name="Lebesgue1"/> z 1867 roku Victor-Amédée Lebesgue podał dowodzone tutaj stwierdzenie bez dowodu. Poniższy dowód jest uproszczoną wersją dowodu przedstawionego przez Johna Maxfielda i&nbsp;Margaret Maxfield<ref name="Maxfield1"/>.

Z punktu 1. wiemy, że rząd liczby <math>a</math> modulo <math>p^2</math> jest równy <math>p - 1</math> lub <math>p(p - 1)</math>. Jeżeli <math>\operatorname{ord}(a, p^2) = p (p - 1)</math>, to twierdzenie jest dowiedzione. Musimy pokazać, że w&nbsp;przypadku gdy <math>\operatorname{ord}(a, p^2) = p - 1</math>, jest <math>\operatorname{ord}(b, p^2) = p (p - 1)</math>.

Dla poprawienia czytelności przekształceń oznaczmy <math>h = \operatorname{ord}(a, p) = p - 1</math>. Ponieważ <math>a b \equiv 1 \!\! \pmod{p}</math>, to <math>\operatorname{ord}(b, p) = h = p - 1</math> (zobacz [[#L7|L7]]). Zauważmy, że

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

Zatem dla pewnej liczby całkowitej <math>k</math> jest

::<math>b = a^{h - 1} + k p</math>

Przypuśćmy, dla uzyskania sprzeczności, że <math>p \mid k</math>. Dostajemy

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

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

Ale z&nbsp;założenia <math>1 < a, b < p</math>, zatem <math>0 < a b - 1 < p^2 - 1 < p^2</math>, czyli <math>p^2 \nmid (a b - 1)</math>. Wynika stąd, że uczynione przypuszczenie jest nieprawdziwe i <math>p \nmid k</math>.

Zgodnie z&nbsp;punktem 2. pozostaje pokazać, że <math>b^h \not\equiv 1 \!\! \pmod{p^2}</math>. Mamy

::<math>b^h = (a^{h - 1} + k p)^h</math>

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

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

::<math>\quad \: \equiv (a^h)^{h - 1} + h a^{(h - 1)^{\large 2}} \cdot k p \!\! \pmod{p^2}</math>

::<math>\quad \: \equiv 1 + h b^{3 h - 1} \cdot k p \!\! \pmod{p^2}</math>

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

gdzie uwzględniliśmy, że

::<math>(h - 1)^2 = (p - 2)^2 = p (p - 1) - (3 p - 4) = \varphi (p^2) - (3 h - 1)</math>

Co kończy dowód.


'''Punkt 4.'''

Punkt 4. jest prostym wnioskiem z&nbsp;punktu 3.<br/>
&#9633;
{{\Spoiler}}



<span id="L67" style="font-size: 110%; font-weight: bold;">Zadanie L67</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Pokazać, że jeżeli liczba <math>g</math> jest generatorem modulo <math>p^2</math>, to <math>g</math> jest generatorem modulo <math>p</math>.

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

<span style="border-bottom-style: double;">Pierwszy sposób</span><br/>
Przypuśćmy, w&nbsp;celu otrzymania sprzeczności, że <math>g</math> nie jest generatorem modulo <math>p</math>. Zatem istnieje liczba <math>r \in \mathbb{Z}_+</math> i <math>r < p - 1</math> taka, że

::<math>g^r \equiv 1 \!\! \pmod{p}</math>

Z twierdzenia [[#L123|L123]] dostajemy

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

Ale <math>r p < (p - 1) p = \varphi (p^2)</math>, wbrew założeniu, że <math>g</math> jest generatorem modulo <math>p^2</math>.

<br/><span style="border-bottom-style: double;">Drugi sposób</span><br/>
Niech <math>h = \operatorname{ord}(g, p)</math>, zatem

::<math>g^h \equiv 1 \!\! \pmod{p}</math>

Z twierdzenia [[#L123|L123]] otrzymujemy

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

Ponieważ <math>g</math> jest generatorem modulo <math>p^2</math>, to <math>\operatorname{ord}(g, p^2) = \varphi (p^2) = p (p - 1)</math>, zatem <math>p(p - 1) \mid h p</math>, czyli <math>(p - 1) \mid h</math> i&nbsp;otrzymujemy

::<math>h = s (p - 1) \leqslant \varphi (p) = p - 1</math>

Skąd wynika, że <math>h = p - 1</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L68" style="font-size: 110%; font-weight: bold;">Zadanie L68</span><br/>
Niech <math>a \in \mathbb{Z}</math> i <math>n \in \mathbb{Z}_+</math>. Pokazać, że jeżeli <math>a^n</math> jest generatorem modulo <math>p</math>, to <math>a</math> jest generatorem modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zauważmy, że <math>n</math> musi być liczbą nieparzystą, bo gdy <math>n</math> jest liczbą parzystą, to <math>a^n</math> jest liczbą kwadratową i&nbsp;nie może być generatorem modulo <math>p</math> (zobacz [[#L44|L44]]). Załóżmy, dla uzyskania sprzeczności, że <math>a</math> nie jest generatorem modulo <math>p</math>. Zatem musi istnieć taki dzielnik pierwszy <math>q</math> liczby <math>p - 1</math>, że

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

Podnosząc obie strony kongruencji do <math>n</math>-tej potęgi, otrzymujemy

::<math>(a^n)^{\tfrac{p - 1}{q}} \equiv 1 \!\! \pmod{p}</math>

Wbrew założeniu, że liczba <math>a^n</math> jest generatorem modulo <math>p</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L69" style="font-size: 110%; font-weight: bold;">Zadanie L69</span><br/>
Pokazać, że jeżeli <math>8</math> jest generatorem modulo <math>p</math>, to liczba pierwsza <math>p</math> musi być postaci <math>p = 24 k + 5</math> lub <math>p = 24 k + 11</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Załóżmy dla uzyskania sprzeczności, że <math>3 \mid (p - 1)</math>. Zatem

::<math>8^{\tfrac{p - 1}{3}} = 2^{p - 1} \equiv 1 \!\! \pmod{p}</math>

Wbrew założeniu, że <math>8</math> jest generatorem modulo <math>p</math> (zobacz [[#L42|L42]]). Wynika stąd, że <math>3 \nmid (p - 1)</math> i&nbsp;musi być

::<math>p - 1 = 3 k + 1 \qquad \qquad \text{lub} \qquad \qquad p - 1 = 3 k + 2</math>

Czyli

::<math>p = 3 k + 2 \qquad \qquad \quad \;\;\, \text{lub} \qquad \qquad p = 3 k + 3</math>

Drugi przypadek nie jest możliwy, bo liczba pierwsza <math>p</math> byłaby liczbą złożoną.

Z zadania [[#L68|L68]] wiemy, że liczba <math>2</math> jest generatorem modulo <math>p</math>, zatem jest liczbą niekwadratową modulo <math>p</math>, skąd wynika, że liczba pierwsza <math>p</math>
musi być postaci <math>p = 8 k \pm 3</math> (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J34|J34]] p.7). Z&nbsp;chińskiego twierdzenia o&nbsp;resztach (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J3|J3]]) wynika, że układom kongruencji

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>\left\{ \begin{array}{cc}
  p \equiv 2 & \pmod{3} \\
  p \equiv 3 & \pmod{8} \\
\end{array} \right. \qquad \qquad \qquad 
\left\{ \begin{array}{ccc}
  p \equiv 2 & \pmod{3} \\
  p \equiv 5 & \pmod{8} \\
\end{array} \right.</math>
</div>

odpowiadają kongruencje <math>p \equiv 11 \!\! \pmod{24} \;</math> i <math>\; p \equiv 5 \!\! \pmod{24}</math>. Co należało pokazać.

Najmniejsze liczby pierwsze <math>p</math>, dla których liczba <math>8</math> jest generatorem: <math>11, 29, 53, 59, 83, 101, 107, \ldots</math><br/>
&#9633;
{{\Spoiler}}



<span id="L70" style="font-size: 110%; font-weight: bold;">Przykład L70</span><br/>

Tabele zawierają najmniejsze liczby pierwsze <math>p</math> takie, że <math>\mathbb{g} (p) = n</math>, dla <math>1 \leqslant n \leqslant 100</math> (zobacz [https://oeis.org/A023048 A023048]).

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż tabele|Hide=Ukryj tabele}}

{| class="wikitable plainlinks"  style="display: inline-table; margin-left: 5px; margin-right: 50px; font-size: 85%; text-align: right;"
|-
! <math>\boldsymbol{n}</math> || <math>\boldsymbol{p}</math>
|-
| <math>1</math> || <math>2</math>
|-
| <math>2</math> || <math>3</math>
|-
| <math>3</math> || <math>7</math>
|-
| <math>4</math> || <math>-</math>
|-
| <math>5</math> || <math>23</math>
|-
| <math>6</math> || <math>41</math>
|-
| <math>7</math> || <math>71</math>
|-
| <math>8</math> || <math>-</math>
|-
| <math>9</math> || <math>-</math>
|-
| <math>10</math> || <math>313</math>
|-
| <math>11</math> || <math>643</math>
|-
| <math>12</math> || <math>4111</math>
|-
| <math>13</math> || <math>457</math>
|-
| <math>14</math> || <math>1031</math>
|-
| <math>15</math> || <math>439</math>
|-
| <math>16</math> || <math>-</math>
|-
| <math>17</math> || <math>311</math>
|-
| <math>18</math> || <math>53173</math>
|-
| <math>19</math> || <math>191</math>
|-
| <math>20</math> || <math>107227</math>
|-
| <math>21</math> || <math>409</math>
|-
| <math>22</math> || <math>3361</math>
|-
| <math>23</math> || <math>2161</math>
|-
| <math>24</math> || <math>533821</math>
|-
| <math>25</math> || <math>-</math>
|}
{| class="wikitable plainlinks"  style="display: inline-table; margin-left: 5px; margin-right: 50px; font-size: 85%; text-align: right;"
|-
! <math>\boldsymbol{n}</math> || <math>\boldsymbol{p}</math>
|-
| <math>26</math> || <math>12391</math>
|-
| <math>27</math> || <math>-</math>
|-
| <math>28</math> || <math>133321</math>
|-
| <math>29</math> || <math>15791</math>
|-
| <math>30</math> || <math>124153</math>
|-
| <math>31</math> || <math>5881</math>
|-
| <math>32</math> || <math>-</math>
|-
| <math>33</math> || <math>268969</math>
|-
| <math>34</math> || <math>48889</math>
|-
| <math>35</math> || <math>64609</math>
|-
| <math>36</math> || <math>-</math>
|-
| <math>37</math> || <math>36721</math>
|-
| <math>38</math> || <math>55441</math>
|-
| <math>39</math> || <math>166031</math>
|-
| <math>40</math> || <math>1373989</math>
|-
| <math>41</math> || <math>156601</math>
|-
| <math>42</math> || <math>2494381</math>
|-
| <math>43</math> || <math>95471</math>
|-
| <math>44</math> || <math>71761</math>
|-
| <math>45</math> || <math>95525767</math>
|-
| <math>46</math> || <math>273001</math>
|-
| <math>47</math> || <math>275641</math>
|-
| <math>48</math> || <math>823766851</math>
|-
| <math>49</math> || <math>-</math>
|-
| <math>50</math> || <math>23126821</math>
|}
{| class="wikitable plainlinks"  style="display: inline-table; margin-left: 5px; margin-right: 50px; font-size: 85%; text-align: right;"
|-
! <math>\boldsymbol{n}</math> || <math>\boldsymbol{p}</math>
|-
| <math>51</math> || <math>322999</math>
|-
| <math>52</math> || <math>129361</math>
|-
| <math>53</math> || <math>161831</math>
|-
| <math>54</math> || <math>4348468741</math>
|-
| <math>55</math> || <math>459841</math>
|-
| <math>56</math> || <math>219605251</math>
|-
| <math>57</math> || <math>471769</math>
|-
| <math>58</math> || <math>336361</math>
|-
| <math>59</math> || <math>712321</math>
|-
| <math>60</math> || <math>697591</math>
|-
| <math>61</math> || <math>1171921</math>
|-
| <math>62</math> || <math>658681</math>
|-
| <math>63</math> || <math>102896401</math>
|-
| <math>64</math> || <math>-</math>
|-
| <math>65</math> || <math>11089681</math>
|-
| <math>66</math> || <math>27955201</math>
|-
| <math>67</math> || <math>3384481</math>
|-
| <math>68</math> || <math>3733801</math>
|-
| <math>69</math> || <math>110881</math>
|-
| <math>70</math> || <math>5620201</math>
|-
| <math>71</math> || <math>3659401</math>
|-
| <math>72</math> || <math>226547941621</math>
|-
| <math>73</math> || <math>760321</math>
|-
| <math>74</math> || <math>8954401</math>
|-
| <math>75</math> || <math>194515471</math>
|}
{| class="wikitable plainlinks"  style="display: inline-table; margin-left: 5px; margin-right: 50px; font-size: 85%; text-align: right;"
|-
! <math>\boldsymbol{n}</math> || <math>\boldsymbol{p}</math>
|-
| <math>76</math> || <math>25291561</math>
|-
| <math>77</math> || <math>8359009</math>
|-
| <math>78</math> || <math>102009601</math>
|-
| <math>79</math> || <math>7510801</math>
|-
| <math>80</math> || <math>596653488817</math>
|-
| <math>81</math> || <math>-</math>
|-
| <math>82</math> || <math>24818641</math>
|-
| <math>83</math> || <math>16889161</math>
|-
| <math>84</math> || <math>16271999719</math>
|-
| <math>85</math> || <math>23821561</math>
|-
| <math>86</math> || <math>7415641</math>
|-
| <math>87</math> || <math>41299801</math>
|-
| <math>88</math> || <math>264935161</math>
|-
| <math>89</math> || <math>6366361</math>
|-
| <math>90</math> || <math>341058118633</math>
|-
| <math>91</math> || <math>70716649</math>
|-
| <math>92</math> || <math>110591881</math>
|-
| <math>93</math> || <math>65150401</math>
|-
| <math>94</math> || <math>5109721</math>
|-
| <math>95</math> || <math>29128969</math>
|-
| <math>96</math> || <math>5260410488191</math>
|-
| <math>97</math> || <math>17551561</math>
|-
| <math>98</math> || <math>179199874981</math>
|-
| <math>99</math> || <math>2648833321</math>
|-
| <math>100</math> || <math>-</math>
|}
<br/>
&#9633;
{{\Spoiler}}





== Liczby Carmichaela ==

&nbsp;

<span id="L71" style="font-size: 110%; font-weight: bold;">Definicja L71</span><br/>
Powiemy, że liczba całkowita <math>m</math> jest liczbą bezkwadratową<ref name="bezkwadratowa1"/>, jeżeli <math>m</math> nie jest podzielna żaden kwadrat liczby całkowitej z&nbsp;wyjątkiem liczby 1. Zatem w&nbsp;rozkładzie liczby bezkwadratowej na czynniki pierwsze każda liczba pierwsza występuje z&nbsp;wykładnikiem równym jeden.



<span id="L72" style="font-size: 110%; font-weight: bold;">Przykład L72</span><br/>
Liczby <math>1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30,31,33,34,35,37,38,39, \ldots</math> są liczbami bezkwadratowymi (zobacz [https://oeis.org/A005117 A005117]).



<span id="L73" style="font-size: 110%; font-weight: bold;">Zadanie L73</span><br/>
Pokazać, że każdą liczbę całkowitą dodatnią <math>n</math> można przedstawić jednoznacznie w&nbsp;postaci iloczynu <math>n = a^2 m</math>, gdzie <math>m</math> jest liczbą bezkwadratową.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Mamy <math>1 = 1^2 \cdot 1</math>. Niech liczba <math>m \geqslant 2</math> ma następujący rozkład na czynniki pierwsze <math>m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>. Zapiszmy wykładniki <math>\alpha_i</math> w&nbsp;postaci <math>\alpha_i = 2 \beta_i + \delta_i</math>, gdzie <math>\delta_i = 0</math>, jeżeli <math>\alpha_i</math> jest liczbą parzystą lub <math>\delta_i = 1</math>, jeżeli <math>\alpha_i</math> jest liczbą nieparzystą. Otrzymujemy

::<math>n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s</math>

::<math>\;\;\,\, = (p^{2 \beta_1}_1 \cdot p^{2 \beta_2}_2 \cdot \ldots \cdot p^{2 \beta_s}_s)(p^{\delta_1}_1 \cdot p^{\delta_2}_2 \cdot \ldots \cdot p^{\delta_s}_s)</math>

::<math>\;\;\,\, = (p^{\beta_1}_1 \cdot p^{\beta_2}_2 \cdot \ldots \cdot p^{\beta_s}_s)^2 (p^{\delta_1}_1 \cdot p^{\delta_2}_2 \cdot \ldots \cdot p^{\delta_s}_s)</math>

::<math>\;\;\,\, = a^2 \cdot m</math><br/>
&#9633;
{{\Spoiler}}



<span id="L74" style="font-size: 110%; font-weight: bold;">Definicja L74</span><br/>
Liczbami Carmichaela nazywamy złożone liczby nieparzyste <math>m</math> takie, że dla dowolnej liczby <math>a</math> względnie pierwszej z <math>m</math> jest

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



<span id="L75" style="font-size: 110%; font-weight: bold;">Przykład L75</span><br/>
Jeżeli liczba <math>a</math> jest względnie pierwsza z&nbsp;każdą z&nbsp;liczb <math>3</math>, <math>11</math> i <math>17</math>, to z&nbsp;twierdzenia Fermata dostajemy

::<math>a^2 \equiv 1 \!\! \pmod{3} \qquad \qquad \,\, a^{10} \equiv 1 \!\! \pmod{11} \qquad \qquad a^{16} \equiv 1 \!\! \pmod{17}</math>

Podnosząc strony wypisanych kongruencji odpowiednio do potęg <math>280</math>, <math>56</math> i <math>35</math>, mamy

::<math>a^{560} \equiv 1 \!\! \pmod{3} \qquad \qquad a^{560} \equiv 1 \!\! \pmod{11} \qquad \qquad a^{560} \equiv 1 \!\! \pmod{17}</math>

Ponieważ moduły <math>3</math>, <math>11</math> i <math>17</math> są względnie pierwsze, to możemy połączyć powyższe kongruencje (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J1|J1]]), otrzymując kongruencję o&nbsp;module <math>561 = 3 \cdot 11 \cdot 17</math>.

::<math>a^{560} \equiv 1 \!\! \pmod{561}</math>

Powyższa kongruencja jest prawdziwa dla każdej liczby <math>a</math> względnie pierwszej z <math>561</math>, zatem liczba <math>561</math> jest liczbą Carmichaela.



<span id="L76" style="font-size: 110%; font-weight: bold;">Przykład L76</span><br/>
Oto wszystkie liczby Carmichaela mniejsze od <math>100 000</math>

::{| class="wikitable plainlinks"  style="font-size: 90%; 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>
|}



<span id="L77" style="font-size: 110%; font-weight: bold;">Zadanie L77</span><br/>
Pokazać, że liczba złożona parzysta nie może być liczbą Carmichaela.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Liczba <math>m = 2</math> nie jest liczbą złożoną, a&nbsp;dla liczb złożonych parzystych <math>m \geqslant 4</math> łatwo zauważamy, że <math>\gcd (m - 1, m) = 1</math>, ale

::<math>(m - 1)^{m - 1} \equiv (- 1)^{m - 1} \equiv - 1 \!\! \pmod{m}</math><br/>
&#9633;
{{\Spoiler}}



<span id="L78" style="font-size: 110%; font-weight: bold;">Twierdzenie L78</span><br/>
Niech <math>p</math> będzie liczbą pierwszą nieparzystą. Jeżeli <math>p \mid m \;</math> i <math>\; m</math> jest liczbą Carmichaela, to <math>m</math> jest liczbą bezkwadratową i <math>\, (p - 1) \mid (m - 1)</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>m = p^u r</math>, gdzie <math>p</math> jest liczbą pierwszą nieparzystą i <math>\gcd (p, r) = 1</math>. Niech <math>g</math> będzie generatorem modulo <math>p^u</math>. Z&nbsp;chińskiego twierdzenia o&nbsp;resztach (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J3|J3]]) wiemy, że istnieje dokładnie jedna taka liczba <math>a</math> (określona modulo <math>p^u r</math>), że prawdziwy jest układ kongruencji

::<math>\begin{array}{l}
  a \equiv g \; \pmod{p^u} \\
  a \equiv 1 \; \pmod{r} \\
\end{array}</math>

Ponieważ liczby <math>p^u</math> i <math>\, r</math> są względnie pierwsze, to (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H8|H8]], [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H30|H30]])

::<math>\gcd (a, m) = \gcd (a, p^u) \cdot \gcd (a, r) = \gcd (g, p^u) \cdot \gcd (1, r) = 1</math>

Z założenia <math>m</math> jest liczbą Carmichaela, zatem możemy napisać

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

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

::<math>g^{m - 1} \equiv 1 \!\! \pmod{p^u}</math>

Ponieważ <math>g</math> jest generatorem modulo <math>p^u</math>, to <math>\operatorname{ord}(g, p^u) = \varphi (p^u) = (p - 1) p^{u - 1}</math>. Z&nbsp;twierdzenia [[#L8|L8]] p.1 otrzymujemy natychmiast, że

::<math>(p - 1) p^{u - 1} \mid (m - 1)</math>

Z założenia <math>p \mid m</math>, zatem <math>\gcd (m - 1, p) = 1</math>, skąd wynika, że musi być <math>u = 1 \;</math> i <math>\; (p - 1) \mid (m - 1)</math>, czyli <math>m</math> jest liczbą bezkwadratową. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L79" style="font-size: 110%; font-weight: bold;">Uwaga L79</span><br/>
Istnieje nieskończenie wiele liczb Carmichaela. Wiemy też, że dla dostatecznie dużych <math>x</math> ilość liczb Carmichaela mniejszych od <math>x</math> przekracza <math>x^{1 / 3}</math><ref name="AlfordGranvillePomerance1"/><ref name="Harman1"/><ref name="Harman2"/>. Zatem badanie pierwszości liczb testem Fermata jest obarczone trwałym i&nbsp;nieusuwalnym błędem, a&nbsp;tym samym jest zbyt zawodne. Jednak nie musimy tak bardzo obawiać się liczb Carmichaela, bo już niewielkie wzmocnienie testu Fermata rozwiązuje ten problem. Wystarczy, zamiast twierdzenia Fermata, wykorzystać kryterium Eulera (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J31|J31]] i [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J33|J33]])

::''Jeżeli <math>\, m \,</math> jest liczbą pierwszą nieparzystą, to <math>\; a^{\tfrac{m - 1}{2}} \equiv \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} \!\! \pmod{m}</math>.''



<span id="L80" style="font-size: 110%; font-weight: bold;">Twierdzenie L80</span><br/>
Nie istnieją złożone liczby nieparzyste <math>m</math> takie, że dla dowolnej liczby <math>a</math> względnie pierwszej z <math>m</math> jest

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

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Przypuśćmy, dla otrzymania sprzeczności, że takie liczby istnieją i&nbsp;niech <math>m</math> będzie jedną z&nbsp;nich. Ponieważ z&nbsp;założonej kongruencji otrzymujemy

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

to <math>m</math> musi być liczbą Carmichaela. Wynika stąd, że <math>m</math> jest nieparzystą liczbą bezkwadratową i&nbsp;możemy napisać <math>m = p r</math>, gdzie <math>p</math> jest liczbą pierwszą i <math>\gcd (p, r) = 1</math>. Niech <math>b</math> będzie dowolną liczbą niekwadratową modulo <math>p</math>. Z&nbsp;chińskiego twierdzenia o&nbsp;resztach (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J3|J3]]) wiemy, że istnieje dokładnie jedna taka liczba <math>c</math> (określona modulo <math>p r</math>), że prawdziwy jest układ kongruencji

::<math>\begin{array}{l}
  c \equiv b \; \pmod{p} \\
  c \equiv 1 \; \pmod{r} \\
\end{array}</math>

Ponieważ liczby <math>p</math> i <math>r</math> są względnie pierwsze, to (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H8|H8]], [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H30|H30]])

::<math>\gcd (c, m) = \gcd (c, p) \cdot \gcd (c, r) = \gcd (b, p) \cdot \gcd (1, r) = 1</math>

Dla tak określonej liczby <math>c</math> łatwo obliczamy symbol Jacobiego (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J42|J42]] p.4 i&nbsp;p.2)

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

Z uczynionego przez nas przypuszczenia wynika, że liczba <math>c</math> spełnia kongruencję

::<math>c^{\tfrac{m - 1}{2}} \equiv \left( {\small\frac{c}{m}} \right)_{\small{\!\! J}} \equiv - 1 \!\! \pmod{m}</math>

Ale gdyby tak było, to mielibyśmy

::<math>c^{\tfrac{m - 1}{2}} \equiv - 1 \!\! \pmod{r}</math>

::<math>1^{\tfrac{m - 1}{2}} \equiv - 1 \!\! \pmod{r}</math>

Co jest niemożliwe. Czyli przypuszczenie, że wszystkie liczby <math>a</math> względnie pierwsze z <math>m</math> spełniają kongruencję

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

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



<span id="L81" style="font-size: 110%; font-weight: bold;">Twierdzenie L81</span><br/>
Niech <math>m</math> będzie złożoną liczbą nieparzystą. Następujące warunki są równoważne

:1. dla dowolnej liczby całkowitej <math>a</math> jest <math>a^m \equiv a \!\! \pmod{m}</math>

:2. dla dowolnej liczby całkowitej <math>a</math> względnie pierwszej z <math>m</math> jest <math>a^{m - 1} \equiv 1 \!\! \pmod{m}</math>

:3. <math>m</math> jest liczbą bezkwadratową i&nbsp;dla dowolnego dzielnika pierwszego <math>p</math> liczby <math>m</math> jest <math>(p - 1) \mid (m - 1)</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Dowód przeprowadzimy, pokazując kolejno implikacje <math>1 \Longrightarrow 2 \Longrightarrow 3 \Longrightarrow 1</math>. Przypomnijmy, że liczby złożone są z&nbsp;definicji liczbami dodatnimi.

'''a)''' <math>\boldsymbol{1 \Longrightarrow 2}</math>

Z założenia <math>m</math> jest liczbą nieparzystą złożoną taką, że dowolna liczba całkowita <math>a</math> spełnia kongruencję <math>a^m \equiv a \!\! \pmod{m}</math>. Rozpatrując kongruencję <math>a^m \equiv a \!\! \pmod{m}</math> jedynie dla liczb <math>a</math> względnie pierwszych z <math>m</math>, natychmiast widzimy, że takie liczby <math>a</math> mają element odwrotny modulo <math>m</math> i&nbsp;z&nbsp;założonej kongruencji łatwo otrzymujemy <math>a^{m - 1} \equiv 1 \!\! \pmod{m}</math>.

'''b)''' <math>\boldsymbol{2 \Longrightarrow 3}</math>

Ta implikacja została pokazana w&nbsp;twierdzeniu [[#L78|L78]].

'''c)''' <math>\boldsymbol{3 \Longrightarrow 1}</math>

Z założenia <math>m</math> jest liczbą bezkwadratową nieparzystą, zatem <math>m = p_1 \cdot \ldots \cdot p_k</math>, gdzie liczby pierwsze nieparzyste <math>p_i</math> są wszystkie różne. Niech <math>a</math> będzie dowolną liczbą całkowitą.

W przypadku gdy liczba pierwsza <math>p_i \nmid a</math>, to z&nbsp;twierdzenia Fermata mamy

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

Ponieważ <math>(p_i - 1) \mid (m - 1)</math>, to istnieje taka liczba naturalna <math>k</math>, że <math>m - 1 = k \cdot (p_i - 1)</math>, zatem

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

Mnożąc obie strony kongruencji przez <math>a</math>, otrzymujemy

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

W przypadku gdy liczba pierwsza <math>p_i \mid a</math>, dostajemy

::<math>a \equiv 0 \equiv a^m \!\! \pmod{p_i}</math>

Zatem kongruencja <math>a^m \equiv a \!\! \pmod{p_i}</math>, gdzie <math>p_i</math> są dzielnikami pierwszymi liczby bezkwadratowej <math>m</math>, jest prawdziwa dla dowolnej liczby całkowitej <math>a</math>.

Ponieważ liczby <math>p_i</math> są parami względnie pierwsze, to układ kongruencji <math>a^m \equiv a \!\! \pmod{p_i}</math> możemy połączyć (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J1|J1]]), otrzymując kongruencję równoważną

::<math>a^m \equiv a \!\! \pmod{p_1 \cdot \ldots \cdot p_k}</math>

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



<span id="L82" style="font-size: 110%; font-weight: bold;">Twierdzenie L82</span><br/>
Jeżeli <math>m</math> jest liczbą Carmichaela, to

:*&nbsp;&nbsp;&nbsp;dowolny czynnik pierwszy liczby <math>m</math> spełnia oszacowanie <math>p < \sqrt{m}</math>

:*&nbsp;&nbsp;&nbsp;liczba <math>m</math> jest iloczynem przynajmniej trzech liczb pierwszych

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

'''Punkt 1.'''

Niech <math>p</math> będzie dzielnikiem pierwszym <math>m</math>. Z&nbsp;twierdzenia [[#L78|L78]] wiemy, że <math>m</math> jest liczbą bezkwadratową i <math>(p - 1) \mid (m - 1)</math>, zatem <math>m = p r</math>, gdzie <math>\gcd (p, r) = 1</math>. Ponieważ

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

to liczba <math>p - 1</math> musi dzielić <math>r - 1</math>. Wynika stąd, że <math>p - 1 \leqslant r - 1</math>, czyli <math>p^2 \leqslant r p = m</math>, ale <math>m</math> jest liczbą bezkwadratową, zatem równość nie jest możliwa i&nbsp;musi być <math>p^2 < m</math>.

'''Punkt 2.'''

Punkt ten wynika natychmiast z&nbsp;punktu pierwszego. Podamy jeszcze jeden, bardzo prosty dowód. Przypuśćmy, dla uzyskania sprzeczności, że <math>m = p q</math> jest liczbą Carmichaela, gdzie <math>p</math> i <math>q</math> są różnymi liczbami pierwszymi. Nie zmniejszając ogólności, możemy założyć, że <math>p > q</math>. Zatem

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

Z uczynionego przypuszczenia wynika, że <math>p - 1</math> dzieli <math>m - 1</math>, czyli <math>p - 1</math> musi dzielić <math>q - 1</math>, co jest niemożliwe dla <math>p > q</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L83" style="font-size: 110%; font-weight: bold;">Twierdzenie L83 (Jack Chernick</span><ref name="Chernick1"/><span style="font-size: 110%; font-weight: bold;">, 1939)</span><br/>
Niech <math>k \in \mathbb{Z}_+</math>. Następujące warunki są równoważne

:*&nbsp;&nbsp;&nbsp;jeżeli każda z&nbsp;liczb <math>6 k + 1</math>, <math>12 k + 1</math>, <math>18 k + 1</math> jest liczbą pierwszą, to ich iloczyn jest liczbą Carmichaela

:*&nbsp;&nbsp;&nbsp;jeżeli każda z&nbsp;liczb <math>p</math>, <math>2 p - 1</math>, <math>3 p - 2</math> jest liczbą pierwszą, to ich iloczyn jest liczbą Carmichaela

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

'''Punkt 1.'''

Jeżeli liczby <math>6 k + 1</math>, <math>12 k + 1</math>, <math>18 k + 1</math> są liczbami pierwszymi oraz liczba <math>a</math> jest względnie pierwsza z&nbsp;każdą z&nbsp;tych liczb, to z&nbsp;twierdzenia Fermata mamy

::<math>a^{6 k} \equiv 1 \!\! \pmod{6 k + 1} \qquad \qquad \:\, a^{12 k} \equiv 1 \!\! \pmod{12 k + 1} \qquad \qquad a^{18 k} \equiv 1 \!\! \pmod{18 k + 1}</math>

Podnosząc obie strony wypisanych wyżej kongruencji do potęgi o&nbsp;wykładniku <math>6</math>, <math>3</math> i <math>2</math>, dostajemy

::<math>a^{36 k} \equiv 1 \!\! \pmod{6 k + 1} \qquad \qquad a^{36 k} \equiv 1 \!\! \pmod{12 k + 1} \qquad \qquad a^{36 k} \equiv 1 \!\! \pmod{18 k + 1}</math>

Ale liczby <math>6 k + 1</math>, <math>12 k + 1</math>, <math>18 k + 1</math> są z&nbsp;założenia różnymi liczbami pierwszymi, zatem są parami względnie pierwsze i&nbsp;powyższy układ kongruencji możemy połączyć (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J1|J1]]), otrzymując kongruencję równoważną

::<math>a^{36 k} \equiv 1 \!\! \pmod{m}</math>

gdzie <math>m = (6 k + 1) (12 k + 1) (18 k + 1)</math>. Łatwo obliczamy

::<math>m - 1 = 1296 k^3 + 396 k^2 + 36 k = 36 k (36 k^2 + 11 k + 1) = 36 k \cdot s</math>

i dostajemy, że

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

Zauważmy jeszcze, że liczba <math>a</math> jest względnie pierwsza z <math>m</math>. Co należało pokazać.

'''Punkt 2.'''

Wszystkie liczby pierwsze <math>p \geqslant 7</math> muszą być postaci <math>6 k + 1</math> lub <math>6 k + 5</math>. Jeżeli liczba <math>p</math> i <math>2 p - 1</math> mają być pierwsze, to <math>p</math> musi być postaci <math>6 k + 1</math>. Istotnie, gdyby <math>p</math> była postaci <math>6 k + 5</math>, to <math>2 p - 1 = 12 k + 9</math> i&nbsp;liczba ta nie byłaby liczbą pierwszą. Jeżeli <math>p</math> jest postaci <math>6 k + 1</math>, to <math>2 p - 1</math> jest postaci <math>12 k + 1</math>, a <math>3 p - 2</math> jest postaci <math>18 k + 1</math> i&nbsp;jeśli liczby te są liczbami pierwszymi, to ich iloczyn jest liczbą Carmichaela, co pokazaliśmy w&nbsp;punkcie 1. twierdzenia.<br/>
&#9633;
{{\Spoiler}}





== Kryteria pierwszości Lucasa i&nbsp;Pocklingtona ==

<span id="L84" style="font-size: 110%; font-weight: bold;">Uwaga L84</span><br/>
Aby ułatwić Czytelnikowi zrozumienie tematu, rozpoczniemy od problemów związanych z&nbsp;terminologią. Będziemy nazywali '''testem''' pierwszości twierdzenie, które co do zasady pozwala określić jedynie pewne prawdopodobieństwo, że badana liczba jest liczbą pierwszą. Przykładem może być tutaj test Fermata, który wykorzystuje twierdzenie Fermata (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J22|J22]]).

::''Jeżeli <math>p</math> jest liczbą pierwszą i <math>\: p \nmid a</math>, to <math>a^{p - 1} \equiv 1 \!\! \pmod{p}</math>''

Niech <math>m</math> będzie badaną sprawdzaną liczbą. Jeżeli dla przypadkowo wybranej podstawy <math>a</math> takiej, że <math>\gcd (a, m) = 1</math> policzymy <math>a^{m - 1}</math> i&nbsp;otrzymamy, że <math>a^{m - 1} \equiv 1 \!\! \pmod{m}</math>, to z&nbsp;prawdopodobieństwem <math>{\small\frac{1}{2}}</math> możemy twierdzić, że <math>m</math> jest liczbą pierwszą<ref name="hd1"/>. Powtarzając test wielokrotnie dla różnych podstaw, upewniamy się, że badana liczba jest liczbą pierwszą.

Będziemy nazywali '''kryterium''' pierwszości twierdzenie, które pozwala ustalić, że badana liczba jest na pewno liczbą pierwszą. Przykładem może być tutaj twierdzenie

::''Jeżeli liczba <math>m > 0</math> nie jest podzielna przez żadną liczbę pierwszą <math>p \leqslant \sqrt{m}</math>, to <math>m</math> jest liczbą pierwszą.''

Z reguły obliczenia związane z&nbsp;kryterium pierwszości trwają znacznie dłużej i&nbsp;często wymagają wstępnych, dodatkowych przygotowań w&nbsp;porównaniu z&nbsp;obliczeniami korzystającymi z&nbsp;testów pierwszości. Oznacza to, że kryteriów pierwszości nie stosujemy do przypadkowych liczb, ale do liczb, które przeszły już wielokrotnie testy pierwszości silniejsze od testu Fermata (zobacz [[#L79|L79]], [[#L80|L80]]) i&nbsp;przypuszczenie, że są one liczbami pierwszymi, jest mocno uzasadnione. W&nbsp;szczególności dysponujemy już całym zbiorem liczb względnie pierwszych z <math>m</math>, dla których kongruencja <math>a^{m - 1} \equiv 1 \!\! \pmod{m}</math> jest prawdziwa.


Zauważmy, że test pierwszości Fermata po odpowiednim przeformułowaniu może być kryterium złożoności. Mamy

::''Jeżeli <math>\gcd (a, m) = 1 \;</math> i <math>\; a^{m - 1} \not\equiv 1 \!\! \pmod{m}</math>, to <math>m</math> jest liczbą złożoną.''

Wystarczy jeden właściwy wybór liczby <math>a</math> i&nbsp;mamy pewność, że <math>m</math> jest liczbą złożoną. Podobnie jak w&nbsp;kryterium pierwszości Lucasa (które za chwilę omówimy) – jeden właściwy wybór liczby <math>a</math> i&nbsp;mamy pewność, że liczba <math>m</math> jest liczbą pierwszą.


Podkreślmy, że przedstawiona wyżej terminologia nie jest obowiązująca. Poniżej przedstawiamy dwa kryteria pierwszości znane bardziej jako testy Lucasa ([[#L85|L85]] i [[#L89|L89]]). Pierwsze kryterium zostało sformułowane i&nbsp;udowodnione przez Lehmera (1927), a&nbsp;drugie przez Selfridge'a (1967).



<span id="L85" style="font-size: 110%; font-weight: bold;">Twierdzenie L85 (kryterium pierwszości Lucasa, Derrick Henry Lehmer</span><ref name="Lehmer1"/><span style="font-size: 110%; font-weight: bold;">, 1927)</span><br/>
Niech <math>m \geqslant 3</math> będzie liczbą całkowitą nieparzystą. Liczba <math>m</math> jest liczbą pierwszą wtedy i&nbsp;tylko wtedy, gdy istnieje taka liczba całkowita <math>a</math>, że spełnione są warunki

:*&nbsp;&nbsp;&nbsp;<math>a^{m - 1} \equiv 1 \!\! \pmod{m}</math>

:*&nbsp;&nbsp;&nbsp;dla każdego dzielnika pierwszego <math>q</math> liczby <math>m - 1</math> jest

::::<math>a^{\tfrac{m - 1}{q}} \not\equiv 1 \!\! \pmod{m}</math>

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

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

Z założenia <math>m</math> jest liczbą pierwszą nieparzystą, zatem istnieje liczba <math>a</math>, która jest generatorem modulo <math>m</math>. Z&nbsp;definicji generatora jest spełniony pierwszy warunek

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

Gdyby dla pewnego dzielnika pierwszego <math>q</math> liczby <math>m - 1</math> było

::<math>a^{\tfrac{m - 1}{q}} \equiv 1 \!\! \pmod{m}</math>

to mielibyśmy

::<math>\operatorname{ord}(a, m) \leqslant {\small\frac{m - 1}{q}} < m - 1</math>

Wbrew temu, że <math>a</math> jest generatorem modulo <math>m</math>.

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

Z twierdzenia [[#L25|L25]] dla <math>r = m - 1</math> otrzymujemy, że <math>\operatorname{ord}(a, m) = m - 1</math>. Ponieważ <math>\varphi (m) \leqslant m - 1</math> dla <math>m \geqslant 2</math>, to możemy napisać

::<math>m - 1 = \operatorname{ord}(a, m) \leqslant \varphi (m) \leqslant m - 1</math>

Skąd natychmiast wynika, że <math>\varphi (m) = m - 1</math>. Zatem <math>m</math> jest liczbą pierwszą (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H43|H43]]). Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L86" style="font-size: 110%; font-weight: bold;">Uwaga L86</span><br/>
Zauważmy też, że problem dowodu pierwszości liczby <math>m</math>, został przeniesiony na znalezienie faktoryzacji liczby <math>m - 1</math>, co w&nbsp;ogólnym przypadku może nie być łatwe, ale w&nbsp;przypadku liczb o&nbsp;szczególnej postaci może być bardzo proste.



<span id="L87" style="font-size: 110%; font-weight: bold;">Zadanie L87</span><br/>
Niech <math>n \in \mathbb{Z}_+</math>. Pokazać, że liczba Fermata <math>F_n = 2^{2^{\large n}} + 1</math> jest liczbą pierwszą wtedy i&nbsp;tylko wtedy, gdy

::<math>3^{(F_n - 1) / 2} \equiv - 1 \!\! \pmod{F_n}</math>

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

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

Zauważmy, że dla <math>n \geqslant 1</math> jest

::<math>F_n = 2^{2^{\large n}} + 1 \equiv (- 1)^{2^{\large n}} + 1 \equiv 2 \!\! \pmod{3}</math>

::<math>F_n = 2^{2^{\large n}} + 1 = 4 \cdot 2^{2^{\large n} - 2} + 1 \equiv 1 \!\! \pmod{4}</math>

Jeżeli <math>F_n</math> jest liczbą pierwszą, to z&nbsp;kryterium Eulera (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J31|J31]] i [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J33|J33]]) wiemy, że

::<math>3^{(F_n - 1) / 2} \equiv \left( {\small\frac{3}{F_n}} \right)_{\small{\!\! J}} \!\! \pmod{F_n}</math>

Ponieważ <math>F_n \equiv 1 \!\! \pmod{4}</math>, to z&nbsp;twierdzenia [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J42|J42]] p.9 dostajemy

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

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

Z założenia

::<math>3^{(F_n - 1) / 2} \equiv - 1 \!\! \pmod{F_n}</math>

Podnosząc obie strony kongruencji do kwadratu, dostajemy

::<math>3^{(F_n - 1)} \equiv 1 \!\! \pmod{F_n}</math>

Widzimy, że spełnione są założenia kryterium Lucasa ([[#L85|L85]]), zatem <math>F_n</math> jest liczbą pierwszą.<br/>
&#9633;
{{\Spoiler}}



<span id="L88" style="font-size: 110%; font-weight: bold;">Uwaga L88</span><br/>
Jeżeli stosując kryterium Lucasa, otrzymamy rezultat pozytywny (czyli <math>m</math> jest liczbą pierwszą), to liczba <math>a</math> jest generatorem modulo <math>m</math>. Co oznacza, że aby potwierdzić pierwszość liczby <math>m</math> liczba <math>a</math> musi być generatorem.

Na szczęście najmniejsze dodatnie generatory <math>\mathbb{g} (p)</math> są niewielkimi liczbami (zobacz [[#L65|L65]]) i&nbsp;przypuszczamy, że <math>\mathbb{g} (p)</math> jest rzędu <math>\log^6 \! p</math><ref name="Shoup1"/>. Jednak dla liczb pierwszych rzędu <math>10^{100}</math> liczba <math>\log^6 \! p</math> jest rzędu <math>10^{14}</math>.

Oczywiście szukając najmniejszego dodatniego generatora, wystarczy sprawdzać kolejne liczby niekwadratowe. Przykładowo najmniejszym generatorem liczby pierwszej <math>p = 45024841</math> jest <math>\mathbb{g} (p) = 111</math> i&nbsp;wystarczy wypróbować <math>14</math> kolejnych liczb niekwadratowych

::<math>29, 37, 41, 58, 73, 74, 82, 83, 87, 97, 101, 103, 107, 111</math>

Od takich problemów uwolni nas modyfikacja kryterium Lucasa znaleziona przez Selfridge'a i&nbsp;przedstawiona we wspólnej pracy z&nbsp;Johnem Brillhartem (1967).



<span id="L89" style="font-size: 110%; font-weight: bold;">Twierdzenie L89 (kryterium pierwszości Lucasa, John Lewis Selfridge</span><ref name="Selfridge1"/><span style="font-size: 110%; font-weight: bold;">, 1967)</span><br/>
Niech <math>m \geqslant 3</math> będzie liczbą całkowitą nieparzystą. Liczba <math>m</math> jest liczbą pierwszą wtedy i&nbsp;tylko wtedy, gdy dla każdego dzielnika pierwszego <math>q_i</math> liczby <math>m - 1</math> istnieje taka liczba całkowita <math>a_i</math>, że

:*&nbsp;&nbsp;&nbsp;<math>(a_i)^{m - 1} \equiv 1 \!\! \pmod{m}</math>

:*&nbsp;&nbsp;&nbsp;<math>(a_i)^{\tfrac{m - 1}{q_i}} \not\equiv 1 \!\! \pmod{m}</math>

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

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

Z założenia <math>m</math> jest liczbą pierwszą nieparzystą. Niech każda z&nbsp;liczb <math>a_i</math> będzie 
generatorem modulo <math>m</math> (liczby <math>a_i</math> nie muszą być wszystkie różne). Zatem 
dla każdej z&nbsp;tych liczb jest <math>\operatorname{ord}(a_i, m) = m - 1</math>. Gdyby dla pewnego dzielnika pierwszego <math>q_i</math> liczby <math>m - 1</math> było

::<math>(a_i)^{\tfrac{m - 1}{q_i}} \equiv 1 \!\! \pmod{m}</math>

to mielibyśmy

::<math>\operatorname{ord}(a_i, m) \leqslant {\small\frac{m - 1}{q_i}} < m - 1</math>

Wbrew temu, że <math>a_i</math> jest generatorem modulo <math>m</math>.

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

Będziemy chcieli pokazać, że <math>\varphi (m) = m - 1</math>. Z&nbsp;definicji funkcji <math>\varphi (m)</math> wynika, że <math>\varphi (m) \leqslant m - 1</math>, dla <math>m \geqslant 2</math>. Zatem wystarczy pokazać, że <math>m - 1</math> dzieli <math>\varphi (m)</math>. Z&nbsp;założenia <math>m - 1 = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>.

Zdefiniujmy odpowiadające liczbom <math>a_i</math> liczby <math>b_i</math> następująco

::<math>b_i \equiv (a_i)^{(m - 1) / q_i^{{\large\alpha_i}}} \!\! \pmod{m}</math>

Łatwo widzimy, że

::<math>(b_i)^{q_i^{{\large\alpha_i}}} \equiv (a_i)^{m - 1} \equiv 1 \!\! \pmod{m}</math>

::<math>(b_i)^{q_i^{{\large\alpha_i} - 1}} \equiv (a_i)^{\tfrac{m - 1}{q_i}} \not\equiv 1 \!\! \pmod{m}</math>

Z twierdzenia [[#L25|L25]] otrzymujemy natychmiast, że <math>\operatorname{ord}(b_i, m) = q^{\alpha_i}_i</math>. Zatem <math>q^{\alpha_i}_i \mid \varphi (m)</math> (zobacz [[#L9|L9]]). Ponieważ jest tak dla dowolnego <math>i = 1, \ldots, s</math>, to <math>(m - 1) \mid \varphi (m)</math>. Zatem <math>\varphi (m) = m - 1</math> i <math>m</math> jest liczbą pierwszą (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H43|H43]]). Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L90" style="font-size: 110%; font-weight: bold;">Przykład L90</span><br/>
Twierdzenie Selfridge'a stanowi istotny postęp w&nbsp;badaniu pierwszości liczb. Zauważmy, że kryterium Lucasa wymagało odszukania wśród liczb <math>1, 2, 3, \ldots, m - 1</math> generatora liczby pierwszej <math>m</math>. Jakkolwiek generatory są zazwyczaj niewielkimi liczbami, to mogło to w&nbsp;pewnych sytuacjach stanowić istotną trudność. W&nbsp;przypadku udowodnionego wyżej twierdzenia liczby <math>a_i</math> nie muszą być generatorami testowanej liczby pierwszej <math>m</math>. Rozważmy następujący przykład. Niech <math>m = 45024841</math>, najmniejszym generatorem modulo <math>m</math> jest <math>\mathbb{g} (m) = 111</math>. Liczba <math>m - 1</math> ma następujący rozkład na czynniki

::<math>m - 1 = 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 17 \cdot 1051</math>

Badanie pierwszości możemy rozpocząć od jak najmniejszych liczb <math>a_i</math> i&nbsp;w&nbsp;kolejnych krokach sprawdzać tylko nierozstrzygnięte przypadki. Zawsze rozpoczynamy od policzenia największego wspólnego dzielnika, bo obliczenie <math>\gcd (a_i, m)</math> jest wykonywane wielokrotnie szybciej niż obliczenie <math>(a_i)^{m - 1}</math> modulo <math>m</math>.


::<math>\begin{array}{lllll}
  \gcd (2, m) = 1 & \qquad & \gcd (3, m) = 1 & \qquad & \gcd (5, m) = 1 \\
  2^{m - 1} \equiv 1 \; \pmod{m} &  & 3^{m - 1} \equiv 1 \; \pmod{m} &  & 5^{m - 1} \equiv 1 \; \pmod{m} \\
  &  &  &  & \\
  2^{(m - 1) / 2} \equiv 1 \; \pmod{m} &  & 3^{(m - 1) / 2} \equiv 1 \; \pmod{m} &  & 5^{(m - 1) / 2} \equiv 1 \; \pmod{m} \\
  2^{(m - 1) / 3} \equiv 985647 \; \pmod{m} &  &  &  & \\
  2^{(m - 1) / 5} \equiv 1 \; \pmod{m} &  & 3^{(m - 1) / 5} \equiv   31295006 \; \pmod{m} &  & \\
  2^{(m - 1) / 7} \equiv 37450777 \; \pmod{m} &  &  &  & \\
  2^{(m - 1) / 17} \equiv 10033050 \; \pmod{m} &  &  &  & \\
  2^{(m - 1) / 1051} \equiv 27781907 \; \pmod{m} &  &  &  & \\
\end{array}</math>


Pozostało znalezienie liczby niekwadratowej modulo <math>m</math>, co nie jest trudnym zadaniem. Znajdujemy <math>29^{(m - 1) / 2} \equiv - 1 \!\! \pmod{m}</math>. Zauważmy, że żadna z&nbsp;użytych do testowania liczb nie jest generatorem modulo <math>m</math>.



<span id="L91" style="font-size: 110%; font-weight: bold;">Przykład L91</span><br/>
Trudniejszy przykład. Weźmy zupełnie przypadkową, dużą liczbę pierwszą. Wpisując w&nbsp;PARI/GP polecenie <code><span style="font-size: 90%; color:black;">m = nextprime(10^100)</span></code>, dostajemy <math>m = 10^{100} + 267</math>. Faktoryzacja liczby <math>m - 1</math> ma postać

::<math>m - 1 = 2 \cdot 3 \cdot 334667 \cdot 30887585377354279775821 \cdot 6992177388736382392966730145791 \cdot 23058946541016687800969797051238966440903</math>

Oznaczmy kolejne dzielniki pierwsze liczby <math>m - 1</math> przez <math>q_1, \ldots, q_6</math>.


::<math>\begin{array}{lllllll}
  \gcd (2, m) = 1 & \qquad & \gcd (3, m) = 1 & \qquad & \gcd (5, m) = 1 & \qquad & \gcd (7, m) = 1 \\
  2^{m - 1} \equiv 1 \; \pmod{m} &  & 3^{m - 1} \equiv 1 \; \pmod{m} &  & 5^{m - 1} \equiv 1 \; \pmod{m} &  & 7^{m - 1} \equiv 1 \; \pmod{m} \\
  &  &  &  &  &  & \\
  2^{(m - 1) / 2} \equiv - 1 \; \pmod{m} &  &  &  &  &  & \\
  2^{(m - 1) / 3} \equiv 1 \; \pmod{m} &  & 3^{(m - 1) / 3} \equiv 1 \; \pmod{m} &  & 5^{(m - 1) / 3} \equiv 1 \; \pmod{m} &  & 7^{(m - 1) / 3} \not\equiv 1 \; \pmod{m} \\
  2^{(m - 1) / q_3} \not\equiv 1 \; \pmod{m} &  &  &  &  &  & \\
  2^{(m - 1) / q_4} \not\equiv 1 \; \pmod{m} &  &  &  &  &  & \\
  2^{(m - 1) / q_5} \not\equiv 1 \; \pmod{m} &  &  &  &  &  & \\
  2^{(m - 1) / q_6} \not\equiv 1 \; \pmod{m} &  &  &  &  &  & \\
\end{array}</math>


Kryterium Lucasa potwierdziło, że <math>m</math> jest liczbą pierwszą. Nie jesteśmy zaskoczeni, ale należy pamiętać, że szukając następnej liczby pierwszej, PARI/GP wykonuje jedynie test BPSW. Tylko polecenie <code><span style="font-size: 90%; color:black;">isprime()</span></code> testuje pierwszość liczby bardzo dokładnie.



<span id="L92" style="font-size: 110%; font-weight: bold;">Przykład L92</span><br/>
Na podstawie twierdzenia [[#L89|L89]] możemy napisać prosty program, który sprawdza, czy badana liczba jest pierwsza.

 <span style="font-size: 90%; color:black;">LucasCriterion(m) = 
 {
 '''local'''(a, d, lenV, s, V, x, y);
 V = '''factor'''(m - 1)[,1]~;
 s = lenV = '''length'''(V);
 '''print'''(m);
 '''print'''(V);
 a = 2;
 '''while'''( a < m,
        d = '''gcd'''(a, m);
        '''if'''( d > 1, '''print'''("liczba złożona - dzielnik d = ", d); '''return'''(0) );
        x = '''Mod'''(a, m);
        y = '''lift'''( x^(m - 1) );
        '''if'''( y <> 1, '''print'''("liczba złożona - podstawa a = ", a); '''return'''(0) );
        '''for'''(k = 1, lenV, '''if'''( V[k] == 0, '''next'''() ); y = '''lift'''( x^((m - 1)/V[k]) ); '''if'''( y <> 1, '''print'''("a = ", a, "  k = ", k); V[k] = 0; s-- ));
        '''if'''( s == 0, '''return'''(1) );
        a = '''nextprime'''(a + 1);
      );
 }</span>



<span id="L93" style="font-size: 110%; font-weight: bold;">Przykład L93</span><br/>
Przykład liczb Carmichaela. Korzystając z&nbsp;programu, łatwo zauważymy, że są to liczby, z&nbsp;którymi kryterium Lucasa ma problem. W&nbsp;przypadku, gdy najmniejszy czynnik pierwszy takiej liczby jest dostatecznie duży, nie zdołamy wykryć, że badana liczba jest złożona, obliczając kolejne największe wspólne dzielniki. Liczbą Carmichaela jest <math>m = 252601 = 41 \cdot 61 \cdot 101</math>. Liczba <math>m - 1</math> ma następujący rozkład na czynniki pierwsze

::<math>m - 1 = 252600 = 2^3 \cdot 3 \cdot 5^2 \cdot 421</math>


::<math>\begin{array}{lllllll}
  \gcd (2, m) = 1 & \qquad & \gcd (3, m) = 1 & \qquad & \gcd (5, m) = 1 & \qquad & \gcd (41, m) = 41 \\
  2^{m - 1} \equiv 1 \; \pmod{m} &  & 3^{m - 1} \equiv 1 \; \pmod{m} &  & 5^{m - 1} \equiv 1 \; \pmod{m} &  & 41^{m - 1} \equiv 160187 \; \pmod{m} \\
  &  &  &  &  &  & \\
  2^{(m - 1) / 2} \equiv 1 \; \pmod{m} &  & 3^{(m - 1) / 2} \equiv   67772 \; \pmod{m} &  &  &  & \\
  2^{(m - 1) / 3} \equiv 153218 \; \pmod{m} &  &  &  &  &  & \\
  2^{(m - 1) / 5} \equiv 137556 \; \pmod{m} &  &  &  &  &  & \\
  2^{(m - 1) / 421} \equiv 1 \; \pmod{m} &  & 3^{(m - 1) / 421} \equiv 1 \; \pmod{m} &  & 5^{(m - 1) / 421} \equiv 1 \; \pmod{m} &  & \\
\end{array}</math>


Nie znajdziemy takiej liczby <math>a</math>, względnie pierwszej z <math>m</math>, dla której <math>a^{(m - 1) / 421} \not\equiv 1 \!\! \pmod{m}</math>. Ale czynnik pierwszy <math>41</math>
zostanie łatwo wykryty. Pozostawiamy Czytelnikowi sprawdzenie znacznie większej liczby Carmichaela

::<math>m = 8634001244918264082478118310255990038094844114723238926749605521</math>

::<math>m = 1128981829489795224271 \cdot 2257963658979590448541 \cdot 3386945488469385672811</math>

::<math>m - 1 = 2^4 \cdot 3^3 \cdot 5 \cdot 13 \cdot 29 \cdot 101 \cdot 197 \cdot 14537 \cdot 920729 \cdot 432560087927124607 \cdot 92039944498124001503569633</math>



<span id="L94" style="font-size: 110%; font-weight: bold;">Uwaga L94</span><br/>
Kryterium Lucasa możemy zmodyfikować tak, aby można było je stosować w&nbsp;przypadku, gdy nie są znane wszystkie dzielniki pierwsze liczby <math>m - 1</math>.



<span id="L95" style="font-size: 110%; font-weight: bold;">Twierdzenie L95 (kryterium Pocklingtona</span><ref name="Pocklington1"/><span style="font-size: 110%; font-weight: bold;">, 1914)</span><br/>
Niech <math>m \geqslant 3</math> będzie liczbą nieparzystą i <math>m = F R + 1</math>, gdzie <math>\gcd (F, R) = 1</math> oraz faktoryzacja liczby <math>F</math> jest znana. Jeżeli <math>F >
\sqrt{m} - 1</math> i&nbsp;dla każdego dzielnika pierwszego <math>q_i</math> liczby <math>F</math> istnieje liczba <math>a_i</math> taka, że

:*&nbsp;&nbsp;&nbsp;<math>(a_i)^{m - 1} \equiv 1 \!\! \pmod{m}</math>

:*&nbsp;&nbsp;&nbsp;<math>\gcd \left( (a_i)^{\tfrac{m - 1}{q_i}} - 1, m \right) = 1</math>

to <math>m</math> jest liczbą pierwszą.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Nim przejdziemy do dowodu, zauważmy, że będą nam potrzebne kongruencje modulo dzielnik pierwszy <math>p</math> liczby <math>m</math> (w dowodzie twierdzenia [[#L76|L76]] nie było takiej potrzeby). Dlatego konieczne było wzmocnienie założenia i&nbsp;zamiast <math>(a_i)^{(m - 1)/q_i} \not\equiv 1 \!\! \pmod{m}</math> mamy <math>\gcd \left( (a_i)^{(m - 1)/q_i} - 1, m \right) = 1</math>.


Z założenia faktoryzacja liczby <math>F</math> jest znana i&nbsp;możemy napisać <math>F = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math>. Niech <math>p</math> będzie dowolnym dzielnikiem pierwszym liczby <math>m</math>. Zatem <math>m = k p^u</math>, gdzie <math>\gcd (k, p^u) = 1</math> i&nbsp;z&nbsp;założonych warunków wynika, że (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H8|H8]], [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H30|H30]])

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

::<math>\gcd \left( (a_i)^{\tfrac{m - 1}{q_i}} - 1, p^u \right) = 1</math>

Skąd dostajemy natychmiast

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

::<math>\gcd \left( (a_i)^{\tfrac{m - 1}{q_i}} - 1, p \right) = 1</math>

Drugi z&nbsp;tych wzorów możemy przepisać w&nbsp;postaci równoważnej

::<math>(a_i)^{\tfrac{m - 1}{q_i}} \not\equiv 1 \!\! \pmod{p}</math>

Jeżeli zdefiniujemy liczby <math>b_i</math> następująco

::<math>b_i \equiv (a_i)^{(m - 1) / q_i^{\large\alpha_i}} \!\! \pmod{p}</math>

to łatwo zauważymy, że

::<math>(b_i)^{q_i^{\large\alpha_i}} \equiv (a_i)^{m - 1} \equiv 1 \!\! \pmod{p}</math>

::<math>(b_i)^{q_i^{{\large\alpha_i} - 1}} \equiv (a_i)^{\tfrac{m - 1}{q_i}} \not\equiv 1 \!\! \pmod{p}</math>

i z&nbsp;twierdzenia [[#L25|L25]] wynika, że <math>\operatorname{ord}(b_i, p) = q_i^{\alpha_i}</math>.

Zatem <math>q_i^{\alpha_i} \mid (p - 1)</math> (zobacz [[#L9|L9]]). Ponieważ jest tak dla dowolnego <math>i = 1, \ldots, s</math>, to <math>F \mid (p - 1)</math>, czyli <math>p = k F + 1</math> i&nbsp;otrzymujemy oszacowanie

::<math>p^2 = (k F + 1)^2 \geqslant (F + 1)^2 > \left( \sqrt{m} \right)^2 = m</math>

bo z&nbsp;założenia <math>F > \sqrt{m} - 1</math>. Ponieważ <math>p</math> jest dowolnym czynnikiem pierwszym liczby <math>m</math>, to nierówność <math>p^2 > m</math> oznacza, że <math>m</math> jest liczbą pierwszą. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L96" style="font-size: 110%; font-weight: bold;">Przykład L96</span><br/>
Niech <math>m = 9024713281</math>. Widzimy, że liczba <math>m - 1</math> jest podzielna przez <math>2, 3, 5, 11</math>. Łatwo ustalamy wykładniki tych liczb i&nbsp;dostajemy

::<math>m - 1 = 9024713280 = 2^6 \cdot 3^3 \cdot 5 \cdot 11 \cdot R</math>

Sprawdzamy, że <math>F^2 > m</math>, gdzie <math>F = 2^6 \cdot 3^3 \cdot 5 \cdot 11</math>. Dla każdego z&nbsp;dzielników pierwszych <math>2, 3, 5, 11</math> liczby <math>F</math> próbujemy znaleźć takie liczby <math>a_i</math>, aby spełnione były warunki z&nbsp;kryterium Pocklingtona. Zauważmy, że obliczając największy wspólny dzielnik, oczekujemy wyniku <math>1</math> lub <math>m</math>. Każdy inny rezultat oznaczałby, że <math>m</math> jest liczbą złożoną, a&nbsp;my szczęśliwym trafem znaleźliśmy dzielnik tej liczby.


::<math>\begin{array}{lllllll}
  \gcd (2, m) = 1 & \qquad & \gcd (3, m) = 1 & \qquad & \gcd (5, m) = 1 & \qquad & \gcd (7, m) = 1 \\
  2^{m - 1} \equiv 1 \; \pmod{m} &  & 3^{m - 1} \equiv 1 \; \pmod{m} &  & 5^{m - 1} \equiv 1 \; \pmod{m} &  & 7^{m - 1} \equiv 1 \; \pmod{m} \\
  &  &  &  &  &  & \\
  \gcd (2^{(m - 1) / 2} - 1, m) = m &  & \gcd (3^{(m - 1) / 2} - 1, m) = m &  & \gcd (5^{(m - 1) / 2} - 1, m) = m &  & \gcd (7^{(m - 1) / 2} - 1, m) = 1 \\
  \gcd (2^{(m - 1) / 3} - 1, m) = 1 &  &  &  &  &  & \\
  \gcd (2^{(m - 1) / 5} - 1, m) = 1 &  &  &  &  &  & \\
  \gcd (2^{(m - 1) / 11} - 1, m) = 1 &  &  &  &  &  & \\
\end{array}</math>


Zatem <math>m</math> jest liczbą pierwszą.





== Kongruencje wielomianowe ==

<span id="L97" style="font-size: 110%; font-weight: bold;">Definicja L97</span><br/>
Kongruencjami wielomianowymi modulo liczba pierwsza <math>p</math> nazywamy kongruencje postaci

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

gdzie <math>W_n (x) = a_n x^n + \ldots + a_1 x + a_0</math>.

Jeżeli <math>p \nmid a_n</math>, to powiemy, że stopień kongruecji <math>W_n (x) \equiv 0 \!\! \pmod{p}</math> jest równy <math>n</math> (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J9|J9]], [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J10|J10]], [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J14|J14]]).



<span id="L98" style="font-size: 110%; font-weight: bold;">Twierdzenie L98</span><br/>
Niech <math>x, a \in \mathbb{Z}</math>, <math>\; n, m \in \mathbb{Z}_+ \;</math> i <math>\; \gcd (a, m) = 1</math>. Rozważmy kongruencje

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

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

Jeżeli pierwsza z&nbsp;tych kongruencji ma rozwiązania, to obie kongruencje mają taką samą ilość rozwiązań.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech zbiory <math>S_1 = \{ \varepsilon_1, \ldots, \varepsilon_r \}</math> i <math>S_a = \{ \alpha_1, \ldots, \alpha_t \}</math> będą zbiorami wszystkich (różnych modulo <math>m</math>) rozwiązań kongruencji <math>x^n \equiv 1 \!\! \pmod{m}</math> i&nbsp;odpowiednio <math>x^n \equiv a \!\! \pmod{m}</math>.

Zbiory <math>S_1</math> i <math>S_a</math> nie są zbiorami pustymi, bo <math>1 \in S_1</math>, a&nbsp;kongruencja <math>x^n \equiv a \!\! \pmod{m}</math> ma z&nbsp;założenia przynajmniej jedno rozwiązanie.

Ponieważ liczba <math>\alpha_1</math> jest pierwiastkiem kongruencji <math>x^n \equiv a \!\! \pmod{m}</math>, to

::<math>\gcd (\alpha^n_1, m) = \gcd (a, m) = 1</math>

czyli <math>\gcd (\alpha_1, m) = 1</math>, zatem <math>\alpha_1</math> ma element odwrotny modulo <math>m</math>.

Niech liczby <math>\Alpha_i = \alpha_1 \cdot \varepsilon_i</math>, gdzie <math>\varepsilon_i \in S_1</math>, tworzą zbiór <math>S_{\Alpha} = \{ \Alpha_1, \ldots, \Alpha_r \}</math>. Łatwo zauważamy, że elementy zbioru <math>S_{\Alpha}</math>

*&nbsp;&nbsp;są wszystkie różne modulo <math>m</math>, bo liczba <math>\alpha_1</math> ma element odwrotny (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H21|H21]]), zatem z&nbsp;definicji <math>| S_1 | = | S_{\Alpha} |</math>

*&nbsp;&nbsp;są rozwiązaniami kongruencji <math>x^n \equiv a \!\! \pmod{m}</math>, bo

::<math>(\Alpha_i)^n = (\alpha_1 \cdot \varepsilon_i)^n = (\alpha_1)^n (\varepsilon_i)^n \equiv a \cdot 1 \equiv a \!\! \pmod{m}</math>

Zatem <math>S_{\Alpha} \subseteq S_a</math> i <math>| S_{\Alpha} | \leqslant | S_a |</math>.

Niech liczby <math>\Epsilon_j = \alpha^{- 1}_1 \cdot \alpha_j</math>, gdzie <math>\alpha_j \in S_a</math>, tworzą zbiór <math>S_{\Epsilon} = \{ \Epsilon_1, \ldots, \Epsilon_t \}</math>. Łatwo zauważamy, że elementy zbioru <math>S_{\Epsilon}</math>

*&nbsp;&nbsp;są wszystkie różne modulo <math>m</math>, bo liczba <math>\alpha^{- 1}_1</math> ma element odwrotny (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H21|H21]]), zatem z&nbsp;definicji <math>| S_a | = | S_{\Epsilon} |</math>

*&nbsp;&nbsp;są rozwiązaniami kongruencji <math>x^n \equiv 1 \!\! \pmod{m}</math>, bo

::<math>(\Epsilon_j)^n = (\alpha^{- 1}_1 \cdot \alpha_j)^n = (\alpha^{- 1}_1)^n \cdot (\alpha_j)^n \equiv [(\alpha_1)^n]^{- 1} \cdot a \equiv a^{- 1} \cdot a \equiv 1 \!\! \pmod{m}</math>

Zatem <math>S_{\Epsilon} \subseteq S_1</math> i <math>| S_{\Epsilon} | \leqslant | S_1 |</math>.

Łącząc oszacowania, otrzymujemy

::<math>| S_1 | = | S_{\Alpha} | \leqslant | S_a | = | S_{\Epsilon} | \leqslant | S_1 |</math>

Wynika stąd, że <math>| S_1 | = | S_a |</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L99" style="font-size: 110%; font-weight: bold;">Zadanie L99</span><br/>
Niech <math>m \geqslant 3</math> będzie liczbą, która ma generator i&nbsp;istnieją rozwiązania kongruencji <math>x^2 \equiv a \!\! \pmod{m}</math>. Pokazać, że istnieją dokładnie dwa rozwiązania tej kongruencji. Wskazówka: zobacz dowód twierdzenia [[#L36|L36]].



<span id="L100" style="font-size: 110%; font-weight: bold;">Twierdzenie L100</span><br/>
Niech <math>x, a \in \mathbb{Z}</math>, <math>\; n \in \mathbb{Z}_+</math>, liczba <math>p</math> będzie liczbą pierwszą taką, że <math>p \nmid a \;</math> i <math>\; d = \gcd (n, p - 1)</math>. Kongruencja

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

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

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

ma rozwiązanie.

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

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

Z założenia kongruencja <math>x^n \equiv a \!\! \pmod{p}</math> ma rozwiązanie, powiedzmy <math>x \equiv u \!\! \pmod{p}</math>. Ponieważ <math>d \mid n</math>, to

::<math>a \equiv u^n \equiv u^{k d} \equiv (u^k)^d \!\! \pmod{p}</math>

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

Z założenia kongruencja <math>x^d \equiv a \!\! \pmod{p}</math> ma rozwiązanie, powiedzmy <math>x \equiv u \!\! \pmod{p}</math>. Z&nbsp;lematu Bézouta (zobacz [[Ciągi liczbowe#C74|C74]]) wiemy, że istnieją takie liczby <math>r, s</math>, że <math>n r + (p - 1) s = d</math>. Zatem

::<math>a \equiv u^d \equiv u^{n r + (p - 1) s} \equiv (u^r)^n \cdot (u^{p - 1})^s \equiv (u^r)^n \!\! \pmod{p}</math>

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



<span id="L101" style="font-size: 110%; font-weight: bold;">Twierdzenie L101</span><br/>
Niech <math>p</math> będzie liczbą pierwszą. Jeżeli <math>d \mid (p - 1)</math>, to kongruencja <math>x^d \equiv 1 \!\! \pmod{p}</math> ma dokładnie <math>d</math> rozwiązań 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 jeżeli <math>d \mid (p - 1)</math>, to

::<math>x^{p - 1} - 1 = (x^d - 1) (1 + x^d + x^{2 d} + \ldots + x^{p - 1 - 2 d} + x^{p - 1 - d}) = (x^d - 1) \sum_{k = 1}^{(p - 1) / d} x^{p - 1 - k d}</math>

Z twierdzenia Fermata wiemy, że kongruencja

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

ma dokładnie <math>p - 1</math> rozwiązań modulo <math>p</math> i&nbsp;są nimi liczby <math>1, 2, \ldots, p - 1</math>.

Z twierdzenia Lagrange'a liczba rozwiązań kongruencji

::<math>x^d - 1 \equiv 0 \!\! \pmod{p} \qquad \qquad \qquad \;\;\; (2)</math>

spełnia warunek <math>\alpha \leqslant d</math>, a&nbsp;liczba rozwiązań kongruencji

::<math>x^{p - 1 - d} + x^{p - 1 - 2 d} + \ldots + x^d + 1 \equiv 0 \!\! \pmod{p} \qquad \qquad \qquad (3)</math>

spełnia warunek <math>\beta \leqslant p - 1 - d</math>. Z&nbsp;tych dwóch warunków wynika, że

::<math>\alpha + \beta \leqslant p - 1</math>

Jednocześnie każde rozwiązanie kongruencji <math>(1)</math> jest rozwiązaniem jednej lub obydwu kongruencji <math>(2)</math> i <math>(3)</math>, zatem musi być

::<math>p - 1 \leqslant \alpha + \beta</math>

Łącząc, dostajemy

::<math>p - 1 \leqslant \alpha + \beta \leqslant p - 1</math>

Czyli <math>\alpha + \beta = p - 1</math>. Z&nbsp;prostego oszacowania

::<math>\alpha \leqslant d = (p - 1) - (p - 1 - d) = \alpha + \beta - (p - 1 - d) \leqslant \alpha + (p - 1 - d) - (p - 1 - d) = \alpha</math>

otrzymujemy <math>\alpha = d</math>.

Jeśli tak, to <math>\beta = p - 1 - \alpha = p - 1 - d</math>.

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



<span id="L102" style="font-size: 110%; font-weight: bold;">Twierdzenie L102</span><br/>
Niech <math>p \nmid a \;</math> i <math>\; d = \gcd (n, p - 1)</math>. Jeżeli jedna z&nbsp;kongruencji

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

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

ma rozwiązania, to każda z&nbsp;tych kongruencji ma dokładnie <math>d</math> rozwiązań.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Dowód jest prostym wnioskiem z&nbsp;twierdzeń [[#L100|L100]], [[#L98|L98]] i [[#L101|L101]].

Niech <math>S_{n, a}</math>, <math>S_{n, 1}</math>, <math>S_{d, a}</math> i <math>S_{d, 1}</math> będą odpowiednio zbiorami (różnych modulo <math>p</math>) rozwiązań kongruencji

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

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

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

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

gdzie <math>p \nmid a</math> i <math>d = \gcd (n, p - 1)</math>. Oto co na temat ilości rozwiązań możemy powiedzieć na podstawie wspomnianych twierdzeń.

Z twierdzenia [[#L100|L100]]:&nbsp;&nbsp;&nbsp;<math>| S_{n, a} | = | S_{d, a} |</math>

Z twierdzenia [[#L98|L98]]:&nbsp;&nbsp;&nbsp;<math>| S_{n, a} | = | S_{n, 1} |</math>&nbsp;&nbsp;&nbsp;(jeżeli kongruencja <math>x^n \equiv a \!\! \pmod{p}</math> ma rozwiązania)

Z twierdzenia [[#L101|L101]]:&nbsp;&nbsp;&nbsp;<math>| S_{d, 1} | = d</math>

Jeżeli <math>x^n \equiv a \!\! \pmod{p}</math> ma rozwiązania, to korzystając kolejno z&nbsp;twierdzeń [[#L100|L100]], [[#L98|L98]] i [[#L101|L101]], otrzymujemy

::<math>| S_{n, a} | = | S_{d, a} | = | S_{d, 1} | = d</math>

Jeżeli <math>x^d \equiv a \!\! \pmod{p}</math> ma rozwiązania, to z&nbsp;twierdzenia [[#L100|L100]] wynika, że <math>| S_{d, a} | = | S_{n, a} |</math>. Z&nbsp;twierdzeń [[#L98|L98]] i [[#L101|L101]] otrzymujemy <math>| S_{d, a} | = | S_{d, 1} | = d</math>. Łącząc, dostajemy ten sam ciąg równości.

W szczególności, gdy jedna z&nbsp;wypisanych w&nbsp;twierdzeniu kongruencji ma rozwiązania, mamy

::<math>| S_{n, a} | = | S_{d, a} | = d</math>

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



<span id="L103" style="font-size: 110%; font-weight: bold;">Uwaga L103</span><br/>
Wykorzystując pojęcie rzędu liczby i&nbsp;generatora, znajdziemy warunek, który rozstrzyga, kiedy kongruencja <math>x^n \equiv a \!\! \pmod{p}</math> ma rozwiązania. Przedstawimy też metodę, która pozwala znaleźć wszystkie rozwiązania tej kongruencji.



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

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

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

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

gdzie <math>d = \gcd (n, p - 1)</math>. Jeżeli powyższy warunek jest spełniony, to istnieje dokładnie <math>d</math> rozwiązań modulo <math>p</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>g</math> będzie generatorem modulo <math>p</math> i&nbsp;niech <math>x \equiv g^y</math>, <math>a \equiv g^b</math> modulo <math>p</math>. Z&nbsp;twierdzenia [[#L23|L23]] dostajemy

::<math>x^n \equiv a \!\! \pmod{p} \qquad \qquad \Longleftrightarrow \qquad \qquad (g^y)^n \equiv g^b \!\! \pmod{p}</math>

::::::::::<math>\: \Longleftrightarrow \qquad \qquad g^{n y} \equiv g^b \!\! \pmod{p}</math>

::::::::::<math>\: \Longleftrightarrow \qquad \qquad n y \equiv b \!\! \pmod{p - 1}</math>


Kongruencja <math>n y \equiv b \!\! \pmod{p - 1}</math> nie ma rozwiązań, gdy <math>d \nmid b</math> lub ma <math>d</math> rozwiązań, gdy <math>d \mid b</math>. Warunek <math>d \mid b</math> możemy równoważnie przekształcić

<div style="margin-top: 1em; margin-bottom: 1em;">
::<math>d \mid b \qquad \qquad \Longleftrightarrow \qquad \qquad (p - 1) \biggr\rvert {\small\frac{(p - 1)b}{d}}</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
::::::<math>\:\, \Longleftrightarrow \qquad \qquad {\small\frac{b \cdot (p - 1)}{d}} \equiv 0 \!\! \pmod{p - 1}</math>
</div>

<div style="margin-top: 1.5em; margin-bottom: 1.5em;">
::::::<math>\:\, \Longleftrightarrow \qquad \qquad g^{b (p - 1) / d} \equiv 1 \!\! \pmod{p}</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
::::::<math>\:\, \Longleftrightarrow \qquad \qquad a^{(p - 1)/ d} \equiv 1 \!\! \pmod{p}</math>
</div>


Jeżeli <math>d \mid b</math>, to przechodząc do kongruencji równoważnej (zobacz [[#L125|L125]]), dostajemy

::<math>{\small\frac{n}{d}} \cdot y \equiv {\small\frac{b}{d}} \;\, \left( \operatorname{mod} \,\, {\small\frac{p - 1}{d}} \right)</math>

Czyli 

::<math>y \equiv {\small\frac{b}{d}} \cdot \left( {\small\frac{n}{d}} \right)^{- 1} \;\, \left( \operatorname{mod} \,\, {\small\frac{p - 1}{d}} \right)</math>

Wynika stąd, że istnieje dokładnie <math>d</math> rozwiązań powyższej kongruencji modulo <math>p - 1</math> i&nbsp;tyle samo rozwiązań ma kongruencja <math>x^n \equiv a \!\! \pmod{p}</math>. Co kończy dowód.<br/>
&#9633;
{{\Spoiler}}



<span id="L105" style="font-size: 110%; font-weight: bold;">Zadanie L105</span><br/>
Pokazać, że kongruencja <math>x^3 \equiv 3 \!\! \pmod{31}</math> nie ma rozwiązania.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Łatwo znajdujemy, że <math>{\small\frac{p - 1}{\gcd (n, p - 1)}} = {\small\frac{30}{3}} = 10 \;</math> oraz <math>\; 3^{10} \equiv 3 \cdot (3^3)^3 \equiv 3 \cdot (- 4)^3 \equiv - 6 \not\equiv 1 \!\! \pmod{31}</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L106" style="font-size: 110%; font-weight: bold;">Zadanie L106</span><br/>
Niech <math>p</math> będzie liczbą pierwszą postaci <math>p = 6 k + 5</math>. Pokazać, że dla każdej liczby całkowitej <math>a</math> kongruencja <math>x^3 \equiv a \!\! \pmod{p}</math> ma jedno rozwiązanie i&nbsp;jest ono postaci <math>u \equiv a^{4 k + 3} \!\! \pmod{p}</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Jeżeli <math>p \mid a</math>, to kongruencja <math>x^3 \equiv 0 \!\! \pmod{p}</math> ma jedno rozwiązanie <math>x \equiv 0 \!\! \pmod{p}</math>. Jeżeli <math>p \nmid a</math> i (z założenia) <math>p</math> jest postaci <math>6 k + 5</math>, to

::<math>d = \gcd (n, p - 1) = \gcd (3, 6 k + 4) = 1</math>

Wynika stąd, że dla każdej liczby całkowitej <math>a</math> takiej, że <math>p \nmid a</math> kongruencja <math>x^3 \equiv a \!\! \pmod{p}</math> ma rozwiązanie, bo z&nbsp;twierdzenia Fermata otrzymujemy

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

Ilość rozwiązań jest równa <math>d = 1</math>. Możemy łatwo podać jawną postać rozwiązania. Istotnie, niech <math>u \equiv a^{4 k + 3} \!\! \pmod{p}</math>, gdzie <math>p = 6 k + 5</math>. Mamy

::<math>u^3 = (a^{4 k + 3})^3 = a^{12 k  + 9} = a^{6 k + 5} a^{6 k + 4} = a^p a^{p - 1} \equiv a \!\! \pmod{p}</math><br/>
&#9633;
{{\Spoiler}}



<span id="L107" style="font-size: 110%; font-weight: bold;">Zadanie L107</span><br/>
Niech <math>p</math> będzie liczbą pierwszą. Znaleźć rozwiązania kongruencji <math>x^3 \equiv 1 \!\! \pmod{p}</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Łatwo sprawdzamy, że dla <math>p = 2, 3, 5</math> mamy tylko jedno rozwiązanie <math>x \equiv 1 \!\! \pmod{p}</math>. Jest to oczywiste rozwiązanie prawdziwe dla wszystkich liczb pierwszych <math>p</math>. Ponieważ

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

to problem istnienia kolejnych rozwiązań sprowadza się do poszukiwania rozwiązań kongruencji

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

Niech <math>p \geqslant 5</math>, ponieważ <math>\gcd (4, p) = 1</math>, to liczba <math>4</math> ma element odwrotny modulo <math>p</math> i&nbsp;możemy napisać

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

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

Liczba <math>- 3</math> jest liczbą kwadratową modulo <math>p = 6 k + 1</math> i&nbsp;liczbą niekwadratową dla <math>p = 6 k + 5</math> (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J46|J46]]). Zatem dla liczb pierwszych postaci <math>p = 6 k + 5</math> kongruencja <math>x^3 \equiv 1 \!\! \pmod{p}</math> ma tylko jedno rozwiązanie <math>x \equiv 1 \!\! \pmod{p}</math>.

W przypadku liczb pierwszych postaci <math>p = 6 k + 1</math> kongruencja <math>(1)</math> ma rozwiązania. Niech <math>u</math> oznacza liczbę będącą rozwiązaniem kongruencji <math>u^2 \equiv - 3 \!\! \pmod{p}</math>. Otrzymujemy

::<math>2 x + 1 \equiv \pm u \!\! \pmod{p}</math>

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

Ponieważ <math>2^{- 1} \equiv {\small\frac{p + 1}{2}} \!\! \pmod{p}</math>, to

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

gdzie przez <math>u'</math> oznaczyliśmy nieparzystą z&nbsp;liczb <math>u</math> i <math>p - u</math>, zapewniając tym samym parzystość licznika. Zatem dla liczb pierwszych postaci <math>p = 6 k + 1</math> kongruencja <math>x^3 \equiv 1 \!\! \pmod{p}</math> ma trzy rozwiązania <math>x \equiv 1, {\small\frac{- 1 - u'}{2}}, {\small\frac{- 1 + u'}{2}} \!\! \pmod{p}</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L108" style="font-size: 110%; font-weight: bold;">Zadanie L108</span><br/>
Niech <math>p</math> będzie liczbą pierwszą postaci <math>p = 6 k + 1</math>. Znaleźć rozwiązania kongruencji <math>x^3 \equiv 1 \!\! \pmod{p}</math>.

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

::<math>d = \gcd (3, p - 1) = \gcd (3, 6 k) = 3</math>

Ponieważ kongruencja <math>x^3 \equiv 1 \!\! \pmod{p}</math> ma rozwiązania, bo <math>x \equiv 1 \!\! \pmod{p}</math> jest rozwiązaniem dla każdej liczby pierwszej <math>p</math>, to ma dokładnie trzy rozwiązania różne modulo <math>p</math>.

Rozwiązania najprościej wypisać, korzystając z&nbsp;tego, że każda liczba pierwsza ma generator. Niech <math>g</math> będzie generatorem modulo <math>p</math>. Liczby

::<math>u_1 \equiv g^{(p - 1) / 3} \!\! \pmod{p} \qquad \qquad u_2 \equiv g^{2 (p - 1) / 3} \!\! \pmod{p} \qquad \qquad u_3 \equiv g^{(p - 1)} \equiv 1 \!\! \pmod{p}</math>

są różne modulo <math>p</math>, bo <math>0 < {\small\frac{p - 1}{3}} < 2 \cdot {\small\frac{p - 1}{3}} < p - 1 < p</math> i&nbsp;są rozwiązaniami kongruencji <math>x^3 \equiv 1 \!\! \pmod{p}</math>, co można łatwo sprawdzić. Mamy

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

::<math>(u_2)^3 \equiv (g^{p - 1})^2 \equiv 1 \!\! \pmod{p}</math>

Oczywiście dla każdej liczby <math>a</math> względnie pierwszej z <math>p</math> możemy napisać analogiczne wzory

::<math>u_1 \equiv a^{(p - 1) / 3} \!\! \pmod{p} \qquad \qquad u_2 \equiv a^{2 (p - 1) / 3} \!\! \pmod{p} \qquad \qquad u_3 \equiv a^{p - 1} \equiv 1 \!\! \pmod{p}</math>

i będziemy mieli <math>(u_1)^3 \equiv (u_2)^3 \equiv (u_3)^3 \equiv 1 \!\! \pmod{p}</math>.

Ale nie każdy wybór będzie dobry i&nbsp;zaraz pokażemy dlaczego. Zauważmy, że w&nbsp;ogólności muszą być spełnione warunki

::<math>u_1 \equiv a^{(p - 1) / 3} \not\equiv 1 \!\! \pmod{p}</math>

::<math>u_2 \equiv a^{2 (p - 1) / 3} \not\equiv 1 \!\! \pmod{p}</math>

::<math>a^{(p - 1) / 3} \not\equiv a^{2 (p - 1) / 3} \!\! \pmod{p}</math>

Pierwszy warunek zapewnia, że <math>u_1 \not\equiv u_3 \!\! \pmod{p}</math>, drugi, że <math>u_2 \not\equiv u_3 \!\! \pmod{p}</math>, a&nbsp;ostatni zapewnia, że <math>u_1 \not\equiv u_2 \!\! \pmod{p}</math>.

Trzeci warunek możemy zapisać w&nbsp;postaci

::<math>a^{(p - 1) / 3} (1 - a^{(p - 1) / 3}) \not\equiv 0 \!\! \pmod{p}</math>

Oczywiście <math>a^{(p - 1) / 3} \not\equiv 0 \!\! \pmod{p}</math>, bo z&nbsp;założenia <math>p \nmid a</math>. Nie może też być <math>1 - a^{(p - 1) / 3} \equiv 0 \!\! \pmod{p}</math>, bo w&nbsp;warunku pierwszym założyliśmy, że <math>a^{(p - 1) / 3} \not\equiv 1 \!\! \pmod{p}</math>.

Ponieważ <math>u_2 \equiv (u_1)^2 \!\! \pmod{p}</math>, to warunek drugi możemy zapisać jako <math>(u_1)^2 \not\equiv 1 \!\! \pmod{p}</math>, czyli <math>(u_1 - 1) (u_1 + 1) \not\equiv 0 \!\! \pmod{p}</math>. Ze względu na pierwszy warunek nie może być <math>u_1 \equiv 1 \!\! \pmod{p}</math> i&nbsp;pozostaje jedynie <math>u_1 \not\equiv - 1 \!\! \pmod{p}</math>. Zauważmy, że warunki

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

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

odpowiadają założeniu, że rząd liczby <math>a</math> nie dzieli liczb <math>{\small\frac{p - 1}{3}} \;</math> i <math>\; {\small\frac{2 (p - 1)}{3}}</math>.

Wynika stąd, że dysponując dowolną liczbą <math>a</math> względnie pierwszą z <math>p</math> taką, że <math>a^{(p - 1) / 3} \not\equiv \pm 1 \!\! \pmod{p}</math>, możemy utworzyć wszystkie rozwiązania kongruencji <math>x^3 \equiv 1 \!\! \pmod{p}</math>. Okazuje się, że bardzo łatwo znaleźć taką liczbę. Średnia liczba prób, które trzeba wykonać, aby znaleźć taką liczbę dla miliarda liczb pierwszych postaci <math>6 k + 1</math> (<math>p \leqslant 47056180177</math>), jest równa tylko <math>1.694548</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L109" style="font-size: 110%; font-weight: bold;">Zadanie L109</span><br/>
Niech <math>a \in \mathbb{Z}</math>, <math>\; p</math> będzie liczbą pierwszą postaci <math>p = 6 k + 1 \;</math> i <math>\; p \nmid a</math>. Znaleźć rozwiązania kongruencji <math>x^3 \equiv a \!\! \pmod{p}</math>.

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

::<math>d = \gcd (3, p - 1) = \gcd (3, 6 k) = 3</math>

Zatem, jeżeli kongruencja <math>x^3 \equiv a \!\! \pmod{p}</math> ma rozwiązania, to ma <math>3</math> rozwiązania różne modulo <math>p</math>.

Niech <math>g</math> będzie generatorem modulo <math>p</math>. Ponieważ liczby <math>g^1, g^2, \ldots, g^{p - 1}</math> są wszystkie różne modulo <math>p</math> (zobacz [[#L32|L32]]), to istnieje taki wykładnik dodatni <math>r < p</math>, że <math>a \equiv g^r \!\! \pmod{p}</math>. Liczba <math>r</math> może być postaci <math>3 k</math> lub <math>3 k + 1</math>, lub <math>3 k + 2</math>. Zobaczmy, jak ten fakt wpływa na istnienie rozwiązań.

::<math>a^{(p - 1) / d} \equiv (g^{3 k})^{(p - 1) / 3} \equiv g^{k (p - 1)} \equiv 1 \!\! \pmod{p}</math>

Widzimy, że w&nbsp;przypadku, gdy <math>a \equiv g^{3 k} \!\! \pmod{p}</math>, to rozpatrywana kongruencja ma rozwiązania.

::<math>a^{(p - 1) / d} \equiv (g^{3 k + 1})^{(p - 1) / 3} \equiv g^{3 k (p - 1) / 3 + (p - 1) / 3} \equiv g^{k (p - 1)} g^{(p - 1) / 3} \equiv g^{(p - 1) / 3} \not\equiv 1 \!\! \pmod{p}</math>

Oczywiście nie może być <math>g^{(p - 1) / 3} \equiv 1 \!\! \pmod{p}</math>, bo rząd liczby <math>g</math> byłby nie większy od <math>{\small\frac{p - 1}{3}}</math>, wbrew założeniu, że <math>g</math> jest generatorem. Podobnie otrzymujemy dla przypadku, gdy <math>r = 3 k + 2</math>.

Podsumowując: jeżeli <math>a \equiv g^r \!\! \pmod{p} \;</math> i <math>\; 3 \mid r</math>, to kongruencja <math>x^3 \equiv a \!\! \pmod{p}</math> ma trzy rozwiązania

::<math>u_1 \equiv g^{r / 3} g^{(p - 1) / 3} \!\! \pmod{p} \qquad \qquad u_2 \equiv g^{r / 3} g^{2 (p - 1) / 3} \!\! \pmod{p} \qquad \qquad u_3 \equiv g^{r / 3} \!\! \pmod{p}</math>

Powyższe rozwiązania są różne modulo <math>p</math>, bo <math>0 < {\small\frac{r}{3}} < {\small\frac{r + (p - 1)}{3}} < {\small\frac{r + 2 (p - 1)}{3}} < p</math>

Jeżeli <math>3 \nmid r</math>, to kongruencja <math>x^3 \equiv a \!\! \pmod{p}</math> nie ma rozwiązań.

Warto jeszcze zauważyć, że wśród liczb <math>a</math> takich, że <math>0 < a < p = 6 k + 1</math>, liczby sześcienne modulo <math>p</math> (czyli takie, dla których kongruencja <math>x^3 \equiv a \!\! \pmod{p}</math> ma rozwiązanie) stanowią <math>{\small\frac{1}{3}}</math> tych liczb, a&nbsp;pozostałe <math>{\small\frac{2}{3}}</math> to liczby niesześcienne modulo <math>p</math>.<br/>
&#9633;
{{\Spoiler}}



<span id="L110" style="font-size: 110%; font-weight: bold;">Przykład L110</span><br/>
Jeżeli w&nbsp;kongruencji <math>x^n \equiv a \!\! \pmod{p}</math> <math>n</math> jest liczbą parzystą, zaś <math>a</math> jest liczbą niekwadratową modulo <math>p</math>, to kongruencja ta nie ma rozwiązania. Jest to łatwo widoczne, jeśli położymy <math>n = 2 k \;</math> i <math>\; y = x^k</math>, wtedy kongruencja <math>y^2 \equiv a \!\! \pmod{p}</math> w&nbsp;sposób oczywisty nie ma rozwiązania.



<span id="L111" style="font-size: 110%; font-weight: bold;">Zadanie L111</span><br/>
Znaleźć rozwiązania kongruencji

::<math>x^2 \equiv 11 \!\! \pmod{13}</math>&nbsp;&nbsp;&nbsp;Odp.: brak rozwiązań

::<math>x^2 \equiv 10 \!\! \pmod{13}</math>&nbsp;&nbsp;&nbsp;Odp.: <math>x \equiv 6 \!\! \pmod{13} \;</math> i <math>\; x \equiv 7 \!\! \pmod{13}</math>

::<math>x^3 \equiv 5 \!\! \pmod{13}</math>&nbsp;&nbsp;&nbsp;Odp.: <math>x \equiv 7 \!\! \pmod{13}</math>, <math>x \equiv 8 \!\! \pmod{13} \;</math> i <math>\; x \equiv 11 \!\! \pmod{13}</math>

::<math>x^7 \equiv 4 \!\! \pmod{13}</math>&nbsp;&nbsp;&nbsp;Odp.: <math>x \equiv 4 \!\! \pmod{13}</math>

Wskazówka: liczba <math>2</math> jest generatorem modulo <math>13</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
W każdym przypadku będziemy stosowali podstawienie <math>x \equiv 2^y \!\! \pmod{13}</math>.

'''Punkt 1.'''

::<math>x^2 \equiv 11 \!\! \pmod{13}</math>

::<math>2^{2 y} \equiv 11 \equiv 2^7 \!\! \pmod{13}</math>

::<math>2 y \equiv 7 \!\! \pmod{12}</math>

Powyższa kongruencja nie ma rozwiązań, bo w&nbsp;ogólności kongruencja <math>a x \equiv b \!\! \pmod{m}</math> ma rozwiązanie wtedy i&nbsp;tylko wtedy, gdy <math>\gcd (a, m) \mid b</math> (zobacz [[Ciągi liczbowe#C77|C77]]). Jeżeli <math>\gcd (a, m) \mid b</math>, to istnieje <math>\gcd (a, m)</math> różnych rozwiązań modulo <math>m</math>.

'''Punkt 2.'''

::<math>x^2 \equiv 10 \!\! \pmod{13}</math>

::<math>2^{2 y} \equiv 10 \equiv 2^{10} \!\! \pmod{13}</math>

::<math>2 y \equiv 10 \!\! \pmod{12}</math>

Ponieważ <math>\gcd (2, 12) \mid 10</math>, to istnieją <math>2</math> rozwiązania. Przechodząc do kongruencji równoważnej (zobacz [[#L125|L125]]), dostajemy

::<math>y \equiv 5 \!\! \pmod{6}</math>

Co modulo <math>12</math> daje dwa rozwiązania <math>y \equiv 5 \!\! \pmod{12} \;</math> i <math>\; y \equiv 11 \!\! \pmod{12}</math>. Otrzymujemy

::<math>x \equiv 2^5 \equiv 6 \!\! \pmod{13}</math> i <math>x \equiv 2^{11} \equiv 7 \!\! \pmod{13}</math>

'''Punkt 3.'''

::<math>x^3 \equiv 5 \!\! \pmod{13}</math>

::<math>2^{3 y} \equiv 5 \equiv 2^9 \!\! \pmod{13}</math>

::<math>3 y \equiv 9 \!\! \pmod{12}</math>

Ponieważ <math>\gcd (3, 12) \mid 9</math>, to istnieją <math>3</math> rozwiązania. Przechodząc do kongruencji równoważnej, dostajemy

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

Co modulo <math>12</math> daje trzy rozwiązania: <math>y \equiv 3 \!\! \pmod{12}</math>, <math>y \equiv 7 \!\! \pmod{12} \;</math> i <math>\; y \equiv 11 \!\! \pmod{12}</math>. Otrzymujemy <math>x \equiv 2^3 \equiv 8 \!\! \pmod{13}</math>, <math>x \equiv 2^7 \equiv 11 \!\! \pmod{13} \;</math> <math>\text{i} \;\; x \equiv 2^{11} \equiv 7 \!\! \pmod{13}</math>

'''Punkt 4.'''

::<math>x^7 \equiv 4 \!\! \pmod{13}</math>

::<math>2^{7 y} \equiv 4 \equiv 2^2 \!\! \pmod{13}</math>

::<math>7 y \equiv 2 \!\! \pmod{12}</math>

::<math>y \equiv 14 \equiv 2 \!\! \pmod{12}</math>

::<math>x \equiv 2^2 \equiv 4 \!\! \pmod{13}</math><br/>
&#9633;
{{\Spoiler}}



<span id="L112" style="font-size: 110%; font-weight: bold;">Zadanie L112</span><br/>
Korzystając z&nbsp;faktu, że <math>12</math> jest generatorem modulo <math>31</math>, znaleźć rozwiązania kongruencji <math>x^{14} \equiv 12^6 \!\! \pmod{31}</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Rozwiązanie|Hide=Ukryj rozwiązanie}}
Zapiszmy <math>x \equiv 12^y \!\! \pmod{31}</math>, gdzie <math>0 \leqslant y \leqslant 30</math>, zatem należy rozwiązać kongruencję <math>12^{14 y} \equiv 12^6 \!\! \pmod{31}</math>, czyli modulo <math>30</math> mamy

::<math>\begin{array}{rl}
  14 y \equiv 6 & \pmod{30} \\
  7 y \equiv 3 & \pmod{15} \\
  13 \cdot 7 y \equiv 13 \cdot 3 & \pmod{15} \\
  y \equiv 39 \equiv 9 & \pmod{15} \\
\end{array}</math>

Rozwiązaniami w&nbsp;przedziale <math>[0, 30]</math> są liczby <math>9, 24</math>. Odpowiednio dla <math>x</math> mamy <math>x \equiv 12^9, 12^{24} \!\! \pmod{31}</math>, czyli <math>x \equiv 15, 16 \!\! \pmod{31}</math>.<br/>
&#9633;
{{\Spoiler}}





== Lemat Hensela ==

&nbsp;

=== <span style="border-bottom:2px solid #000;">Wielomiany</span> ===

&nbsp;

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

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

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

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

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

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

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

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

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

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

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

Ponieważ <math>x</math> możemy zapisać w&nbsp;postaci <math>x = s + (x - s)</math>, to

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

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

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

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

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



<span id="L114" style="font-size: 110%; font-weight: bold;">Twierdzenie L114</span><br/>
Jeżeli <math>W_n (x)</math> jest wielomianem całkowitym stopnia <math>n \geqslant 1</math>, zaś <math>W'_n (x)</math> jego pochodną, to

::<math>W_n (x) = W_n (s) + (x - s) \cdot W'_n (s) + (x - s)^2 \cdot V_{n - 2} (x)</math>

gdzie <math>V_{n - 2} (x)</math> jest pewnym wielomianem całkowitym. Dla <math>n = 1</math> wielomian <math>V_{n - 2} (x)</math> jest wielomianem zerowym.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
W przypadku gdy <math>W_n (x)</math> jest wielomianem stopnia pierwszego, mamy <math>W_1 (x) = a x + b</math> i&nbsp;możemy napisać

::<math>a x + b = (a s + b) + (x - s) a + (x - s)^2 \cdot 0</math>

::<math>W_1 (x) = W_1 (s) + (x - s) \cdot W_1' (s) + (x - s)^2 \cdot 0</math>

W przypadku gdy <math>n \geqslant 2</math>, mamy <math>W_n (x) = \sum_{k = 0}^{n} a_k x^k</math>, gdzie <math>a_n \neq 0</math>. Oczywiście pochodna wielomianu <math>W_n (x)</math> jest równa <math>W'_n (x) = \sum^n_{k = 1} k a_k x^{k - 1}</math>. Korzystając z&nbsp;twierdzenia [[#L113|L113]], dostajemy

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

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

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

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

::::::<math>\quad \,\, = (x - s) W'_n (s) + (x - s)^2 V_{n - 2} (x)</math>

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



=== <span style="border-bottom:2px solid #000;">Rozwiązania kongruencji wielomianowych modulo <math>\boldsymbol{p^n}</math></span> ===

&nbsp;

<span id="L115" style="font-size: 110%; font-weight: bold;">Twierdzenie L115</span><br/>
Niech <math>a, r \in \mathbb{Z}</math>, <math>r \geqslant 2</math> i <math>p</math> będzie liczbą pierwszą nieparzystą oraz <math>\gcd (a r, p) = 1</math>. Kongruencja <math>x^r \equiv a \!\! \pmod{p^n}</math> ma rozwiązanie wtedy i&nbsp;tylko wtedy, gdy kongruencja <math>x^r \equiv a \!\! \pmod{p}</math> ma rozwiązanie.

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

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

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

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

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

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

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

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

W przypadku, gdy <math>r = 2</math> twierdzenie jest prawdziwe (zobacz [[CRT, twierdzenia Lagrange'a, Wilsona i Fermata, kryterium Eulera, symbole Legendre'a i Jacobiego#J50|J50]]). Niech <math>r \geqslant 3</math>.

Indukcja matematyczna. Z&nbsp;uczynionego w&nbsp;twierdzeniu założenia wiemy, że kongruencja <math>x^r \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^r \equiv a \!\! \pmod{p^n}</math>

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

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

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

::<math>u^r_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 (r u_n, p) = 1</math>, to równanie

::<math>r u^{r - 1}_n \cdot s - p \cdot l = - k</math>

ma rozwiązanie (zobacz [[Ciągi liczbowe#C77|C77]]). Niech liczby <math>s_0</math> i <math>l_0</math> będą rozwiązaniem tego równania. Zatem

::<math>k + r u^{r - 1}_n \cdot s_0 = l_0 \cdot p</math>

::<math>k p^n + r u^{r - 1}_n \cdot s_0 p^n = l_0 \cdot p^{n + 1}</math>

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

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

Ponieważ

::<math>(u_n + s_0 p^n)^r = \sum_{j = 0}^{r} \binom{r}{j} (u_n)^{r - j} (s_0 p^n)^j = u^r_n + r u^{r - 1}_n \cdot s_0 p^n + \sum_{j = 2}^{r} \binom{r}{j} u^{r - j}_n s^j_0 p^{n j}</math>

to

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

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

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

bo <math>n j \geqslant n + 1</math> dla <math>j \geqslant 2</math>.

Czyli liczba <math>u_{n + 1} = u_n + s_0 p^n</math> jest rozwiązaniem kongruencji

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

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



<span id="L116" style="font-size: 110%; font-weight: bold;">Uwaga L116</span><br/>
Niech <math>\beta</math> będzie rozwiązaniem kongruencji <math>f(x) \equiv 0 \!\! \pmod{p^{n + 1}}</math>, gdzie <math>f(x)</math> jest wielomianem całkowitym. Rozważmy kongruencje

::<math>f (\beta) \equiv 0 \!\! \pmod{p^{n + 1}} \qquad \qquad (1)</math>

::<math>f (\beta) \equiv 0 \!\! \pmod{p^n} \qquad \qquad \;\;\,\, (2)</math>

::<math>f(x) \equiv 0 \!\! \pmod{p^n} \qquad \qquad \;\;\,\, (3)</math>

Zauważmy, że

:*&nbsp;&nbsp;rozwiązanie <math>\beta</math> w&nbsp;przypadku kongruencji <math>(1)</math> jest określone modulo <math>p^{n + 1}</math>
:*&nbsp;&nbsp;kongruencja <math>(2)</math> wynika z&nbsp;kongruencji <math>(1)</math>
:*&nbsp;&nbsp;rozwiązania <math>\alpha_1, \ldots, \alpha_s</math> kongruencji <math>(3)</math> są określone modulo <math>p^n</math>
:*&nbsp;&nbsp;modulo <math>p^n</math> rozwiązanie <math>\beta</math> musi być identyczne z&nbsp;jednym z&nbsp;rozwiązań <math>\alpha_1, \ldots, \alpha_s</math> kongruencji <math>(3)</math>
:*&nbsp;&nbsp;nie zmniejszając ogólności, możemy to rozwiązanie <math>\alpha_i</math>, któremu odpowiada rozwiązanie <math>\beta</math>, oznaczyć po prostu przez <math>\alpha</math>

Z powyższych spostrzeżeń wynika, że

::<math>\beta \equiv \alpha \!\! \pmod{p^n}</math>

gdzie <math>\alpha</math> jest rozwiązaniem kongruencji <math>(3)</math>. Zatem

::<math>\beta = \alpha + k \cdot p^n</math>

Rozpatrując powyższe równanie modulo <math>p^{n + 1}</math>, dostajemy

::<math>\beta \equiv \alpha + k \cdot p^n \!\! \pmod{p^{n + 1}}</math>

Ponieważ <math>p^n \mid (\beta - \alpha)</math>, to przechodząc do kongruencji równoważnej (zobacz [[#L125|L125]]), dostajemy

::<math>{\small\frac{\beta - \alpha}{p^n}} \equiv k \!\! \pmod{p}</math>

Czyli liczba <math>k</math> jest określona modulo <math>p</math>.

Podsumujmy. Otrzymaliśmy wzór

::<math>\beta \equiv \alpha + k \cdot p^n \!\! \pmod{p^{n + 1}}</math>

który wiąże rozwiązanie <math>\beta</math> kongruencji <math>(1)</math> z&nbsp;pewnym rozwiązaniem <math>\alpha</math> kongruencji <math>(3)</math>. Podkreślmy, że wzór ten uzyskaliśmy przy założeniu, że kongruencja <math>(1)</math> ma rozwiązanie.

Lemat Hensela, który za chwilę udowodnimy, precyzuje warunki, jakie muszą być spełnione, aby istnienie rozwiązania kongruencji <math>(3)</math> pociągało za sobą istnienie rozwiązania kongruencji <math>(1)</math>.

Na zakończenie zilustrujmy powyższe rozważania przykładem. Niech <math>f(x) = (x - 2) (x - 3) + 7</math>. Rozwiązania <math>u_n</math> i <math>v_n</math> kongruencji <math>f(x) \equiv 0
\!\! \pmod{7^n}</math> otrzymujemy, uwzględniając <math>n</math> początkowych składników sum

::<math>2 + 1 \cdot 7 + 1 \cdot 7^2 + 2 \cdot 7^3 + 5 \cdot 7^4 + 0 \cdot 7^5 + 2 \cdot 7^6 + 5 \cdot 7^7 + 0 \cdot 7^8 + 3 \cdot 7^9 + 10 \cdot 7^{10} + \ldots</math>

::<math>3 + 6 \cdot 7 + 5 \cdot 7^2 + 4 \cdot 7^3 + 1 \cdot 7^4 + 6 \cdot 7^5 + 4 \cdot 7^6 + 1 \cdot 7^7 + 6 \cdot 7^8 + 3 \cdot 7^9 + 6 \cdot 7^{10} + \ldots</math>



<span id="L117" style="font-size: 110%; font-weight: bold;">Twierdzenie L117</span><br/>
Jeżeli <math>f(x)</math> jest wielomianem całkowitym, zaś <math>p</math> liczbą pierwszą, to prawdziwa jest kongruencja

::<math>f(x + k p^n) \equiv f (x) + k p^n \cdot f' (x) \!\! \pmod{p^{n + 1}}</math>

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Niech <math>s \in \mathbb{Z}</math>. Korzystając z&nbsp;twierdzenia [[#L114|L114]] i&nbsp;kładąc <math>x = s + k p^n</math>, otrzymujemy

::<math>f(s + k p^n) = f (s) + k p^n \cdot f' (s) + k^2 p^{2 n} \cdot V (s + k p^n)</math>

Z powyższej równości wynika kongruencja

::<math>f(s + k p^n) \equiv f (s) + k p^n \cdot f' (s) \!\! \pmod{p^{n + 1}}</math>

bo <math>2 n \geqslant n + 1</math> dla <math>n \geqslant 1</math>. Zauważmy, że <math>s</math> jest dowolną liczbą całkowitą, zatem wystarczy zmienić oznaczenie <math>s \longrightarrow x</math>, aby otrzymać tezę twierdzenia.<br/>
&#9633;
{{\Spoiler}}



<span id="L118" style="font-size: 110%; font-weight: bold;">Twierdzenie L118 (lemat Hensela)</span><br/>
Niech <math>\alpha, \beta \in \mathbb{Z} \;</math> i <math>\; p</math> będzie liczbą pierwszą, <math>f(x)</math> wielomianem całkowitym, a <math>f' (x)</math> jego pochodną. Jeżeli dla pewnego <math>\alpha</math> spełnione są warunki

::<math>f (\alpha) \equiv 0 \!\! \pmod{p^n} \qquad \qquad \text{i} \qquad \qquad f' (\alpha) \not\equiv 0 \!\! \pmod{p}</math>

to istnieje liczba <math>\beta</math> taka, że <math>f (\beta) \equiv 0 \!\! \pmod{p^{n + 1}}</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Wiemy, że (zobacz [[#L117|L117]])

::<math>f (\alpha + k p^n) \equiv f (\alpha) + k p^n \cdot f' (\alpha) \!\! \pmod{p^{n + 1}}</math>

Zauważmy, że możemy tak wybrać wartość liczby <math>k</math>, aby prawa strona kongruencji była równa zero.

::<math>f (\alpha) + k p^n \cdot f' (\alpha) \equiv 0 \!\! \pmod{p^{n + 1}}</math>

Z założenia <math>p^n \mid f (\alpha)</math>. Przechodząc do kongruencji równoważnej (zobacz [[#L125|L125]]) otrzymujemy

::<math>{\small\frac{f (\alpha)}{p^n}} + k \cdot f' (\alpha) \equiv 0 \!\! \pmod{p}</math>

::<math>k \cdot f' (\alpha) \equiv - {\small\frac{f (\alpha)}{p^n}} \!\! \pmod{p}</math>

::<math>k \equiv - {\small\frac{f (\alpha)}{p^n}} \cdot [f' (\alpha)]^{- 1} \!\! \pmod{p}</math>

Ponieważ z&nbsp;założenia <math>p \nmid f' (\alpha)</math>, to liczba <math>f' (\alpha)</math> ma element odwrotny modulo <math>p</math>. Zatem <math>\beta = \alpha + k p^n \;</math> i <math>\; f (\beta) \equiv 0 \!\! \pmod{p^{n + 1}}</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L119" style="font-size: 110%; font-weight: bold;">Przykład L119</span><br/>
Rozważmy wielomian

::<math>f(x) = x^2 + 10 x + 11 \qquad \qquad f' (x) = 2 x + 10</math>

Łatwo sprawdzamy, że

::<math>f(x) \equiv 0 \!\! \pmod{5} \; \qquad \text{dla} \quad x \equiv 2, 3 \!\! \pmod{5}</math>

::<math>f' (x) \not\equiv 0 \!\! \pmod{5} \qquad \text{dla} \quad x \equiv 2, 3 \!\! \pmod{5}</math>

Korzystając z&nbsp;twierdzenia Hensela, znajdziemy pierwiastki wielomianu <math>f(x)</math> modulo <math>5^n</math>. Zbadamy tylko przypadek <math>x \equiv 2 \!\! \pmod{5}</math>.

'''Modulo 25'''

Rozważmy kongruencję

::<math>k f' (2) \equiv - {\small\frac{f (2)}{5}} \!\! \pmod{5}</math>

::<math>4 k \equiv - {\small\frac{35}{5}} \equiv - 7 \equiv 3 \!\! \pmod{5}</math>

::<math>k \equiv 2 \!\! \pmod{5}</math>

Zatem otrzymujemy rozwiązanie modulo <math>25</math>

::<math>x \equiv 2 + 2 \cdot 5 \equiv 12 \!\! \pmod{25}</math>

'''Modulo 125'''

Rozważmy kongruencję

::<math>k f' (12) \equiv - {\small\frac{f (12)}{25}} \!\! \pmod{5}</math>

::<math>4 k \equiv - {\small\frac{275}{25}} \equiv - 11 \equiv 4 \!\! \pmod{5}</math>

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

Zatem otrzymujemy rozwiązanie modulo <math>125</math>

::<math>x \equiv 12 + 1 \cdot 25 \equiv 37 \!\! \pmod{125}</math>


Zbierając i&nbsp;kontynuując obliczenia dla kolejnych potęg liczby <math>5</math>, gdzie

::<math>f(x) = x^2 + 15 x + 31 \qquad \qquad f' (x) = 2 x + 15</math>

otrzymujemy

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|- style="height: 4em"
! <math>\;\; \boldsymbol{n} \;\;</math> || <math>\;\; \boldsymbol{\alpha} \;\;</math> || <math>\boldsymbol{f (\alpha)}</math> || <math>\boldsymbol{f' (\alpha)}</math> || <math>\boldsymbol{k f' (\alpha) \equiv - {\small\frac{f (\alpha)}{5^n}} \!\! \pmod{5}}</math> || <math>\boldsymbol{k \!\! \pmod{5}}</math> || <math>\boldsymbol{\beta \equiv \alpha + k \cdot 5^n \!\! \pmod{5^{n + 1}}}</math>
|- style="height: 3.5em"
| <math>1</math> || <math>2</math> || <math>35 = 5^n \cdot 7</math> || <math>14</math> || <math>4 k \equiv 3 \!\! \pmod{5}</math> || <math>2</math> || <math>2 + 2 \cdot 5^n \equiv 12</math>
|- style="height: 3.5em"
| <math>2</math> || <math>12</math> || <math>275 = 5^n \cdot 11</math> || <math>34</math> || <math>4 k \equiv 4 \!\! \pmod{5}</math> || <math>1</math> || <math>12 + 1 \cdot 5^n \equiv 37</math>
|- style="height: 3.5em"
| <math>3</math> || <math>37</math> || <math>1750 = 5^n \cdot 14</math> || <math>84</math> || <math>4 k \equiv 1 \!\! \pmod{5}</math> || <math>4</math> || <math>37 + 4 \cdot 5^n \equiv 537</math>
|- style="height: 3.5em"
| <math>4</math> || <math>537</math> || <math>293750 = 5^n \cdot 470</math> || <math>1084</math> || <math>4 k \equiv 0 \!\! \pmod{5}</math> || <math>0</math> || <math>537 + 0 \cdot 5^n \equiv 537</math>
|- style="height: 3.5em"
| <math>5</math> || <math>537</math> || <math>293750 = 5^n \cdot 94</math> || <math>1084</math> || <math>4 k \equiv 1 \!\! \pmod{5}</math> || <math>4</math> || <math>537 + 4 \cdot 5^n \equiv 13037</math>
|}



<span id="L120" style="font-size: 110%; font-weight: bold;">Zadanie L120</span><br/>
Niech <math>f(x) = x^3 - 2 x + 7</math>. Korzystając z&nbsp;lematu Hensela, znaleźć rozwiązania kongruencji <math>f(x) \equiv 0 \!\! \pmod{11^6}</math>.

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

::<math>f(x) = x^3 - 2 x + 7 \qquad \qquad \text{i} \qquad \qquad f' (x) = 3 x^2 - 2</math>.

Kongruencja <math>f(x) \equiv 0 \!\! \pmod{11}</math> ma jedno rozwiązanie <math>x \equiv 2 \!\! \pmod{11}</math>. Sporządzimy podobną tabelę jak w&nbsp;przykładzie [[#L119|L119]].

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|- style="height: 4em"
! <math>\;\; \boldsymbol{n} \;\;</math> || <math>\boldsymbol{\alpha}</math> || <math>\boldsymbol{f (\alpha)}</math> || <math>\boldsymbol{f' (\alpha)}</math> || <math>\boldsymbol{k f' (\alpha) \equiv - {\small\frac{f (\alpha)}{11^n}} \!\! \pmod{11}}</math> || <math>\boldsymbol{k \!\! \pmod{11}}</math> || <math>\boldsymbol{\beta \equiv \alpha + k \cdot 11^n \!\! \pmod{11^{n + 1}}}</math>
|- style="height: 3.5em"
| <math>1</math> || <math>2</math> || <math>11 = 11^n \cdot 1</math> || <math>10</math> || <math>10 k \equiv 10 \!\! \pmod{11}</math> || <math>1</math> || <math>2 + 1 \cdot 11^n \equiv 13</math>
|- style="height: 3.5em"
| <math>2</math> || <math>13</math> || <math>2178 = 11^n \cdot 18</math> || <math>505</math> || <math>10 k \equiv 4 \!\! \pmod{11}</math> || <math>7</math> || <math>13 + 7 \cdot 11^n \equiv 860</math>
|- style="height: 3.5em"
| <math>3</math> || <math>860</math> || <math>636054287 = 11^n \cdot 477877</math> || <math>2218798</math> || <math>10 k \equiv 7 \!\! \pmod{11}</math> || <math>4</math> || <math>860 + 4 \cdot 11^n \equiv 6184</math>
|- style="height: 3.5em"
| <math>4</math> || <math>6184</math> || <math>236487625143 = 11^n \cdot 16152423</math> || <math>114725566</math> || <math>10 k \equiv 10  \!\! \pmod{11}</math> || <math>1</math> || <math>6184 + 1 \cdot 11^n \equiv 20825</math>
|- style="height: 3.5em"
| <math>5</math> || <math>20825</math> || <math>9031398973982 = 11^n \cdot 56077882</math> || <math>1301041873</math> || <math>10 k \equiv 8  \!\! \pmod{11}</math> || <math>3</math> || <math>20825 + 3 \cdot 11^n \equiv 503978</math>
|}

Znajdujemy, że <math>f(x) \equiv 0 \!\! \pmod{11^6}</math> dla <math>x = 503978</math>.<br/>
&#9633;
{{\Spoiler}}



Z lematu Hensela wynika natychmiast.<br/>
<span id="L121" style="font-size: 110%; font-weight: bold;">Twierdzenie L121</span><br/>
Niech <math>p</math> będzie liczbą pierwszą, <math>f(x)</math> wielomianem całkowitym, a <math>f' (x)</math> jego pochodną. Jeżeli dla pewnej liczby całkowitej <math>x = \alpha</math> wielomian <math>f(x)</math> ma rozwiązanie modulo <math>p</math> <math>\text{i} \; f' (\alpha) \not\equiv 0 \!\! \pmod{p}</math>, to <math>f(x)</math> ma rozwiązanie modulo <math>p^n</math> dla dowolnego <math>n \in \mathbb{Z}_+</math>.



<span id="L122" style="font-size: 110%; font-weight: bold;">Przykład L122</span><br/>
Pokazaliśmy (zobacz [[#L115|L115]]), że jeżeli kongruencja <math>x^r \equiv a \!\! \pmod{p}</math> ma rozwiązanie, to kongruencja <math>x^r \equiv a \!\! \pmod{p^n}</math> też ma rozwiązanie. Z&nbsp;lematu Hensela rezultat ten otrzymujemy natychmiast. Z&nbsp;założenia istnieje takie <math>\alpha</math>, że <math>\alpha^r \equiv a \!\! \pmod{p}</math>. Pochodna wielomianu <math>x^r - a</math> jest równa <math>r x^{r - 1}</math> i&nbsp;musi być <math>r \alpha^{r - 1} \not\equiv 0 \!\! \pmod{p}</math>. Skąd otrzymujemy <math>\gcd (\alpha r, p) = 1</math> (warunek ten jest dodatkowym założeniem w&nbsp;twierdzeniu [[#L115|L115]]) i&nbsp;przy tym założeniu istnieje rozwiązanie kongruencji <math>x^r \equiv a \!\! \pmod{p^n}</math>.





== Uzupełnienie ==

<span id="L123" style="font-size: 110%; font-weight: bold;">Twierdzenie L123</span><br/>
Niech <math>k, m \in \mathbb{Z}_+ \;</math> i <math>\; a, b \in \mathbb{Z}</math>. Jeżeli <math>a \equiv b \!\! \pmod{m^k}</math>, to <math>a^m \equiv b^m \!\! \pmod{m^{k + 1}}</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Dla <math>m = 1</math> twierdzenie jest prawdziwe. Niech <math>m \geqslant 2</math>. Z&nbsp;założenia istnieje taka liczba całkowita <math>s</math>, że <math>a = b + s m^k</math>. Korzystając z&nbsp;dwumianu Newtona, otrzymujemy

::<math>a^m = (b + s m^k)^m</math>

::<math>\quad \;\: = \sum_{i = 0}^m \binom{m}{i} (s m^k)^i \cdot b^{m - i}</math>

::<math>\quad \;\: = \binom{m}{0} \cdot b^m + \binom{m}{1} s m^k b^{m - 1} + \sum_{i = 2}^m \binom{m}{i} s^i m^{i k} b^{m - i}</math>

::<math>\quad \;\: = b^m + s m^{k + 1} b^{m - 1} + \sum_{i = 2}^m \binom{m}{i} s^i m^{i k} b^{m - i}</math>

::<math>\quad \;\: \equiv b^m \!\! \pmod{m^{k + 1}}</math>

Ponieważ dla <math>i \geqslant 2</math> oraz <math>k \geqslant 1</math> mamy <math>i k = k + (i - 1) k \geqslant k + 1</math>, zatem <math>m^{k + 1} \mid m^{i k}</math>. Co było do pokazania.<br/>
&#9633;
{{\Spoiler}}



<span id="L124" style="font-size: 110%; font-weight: bold;">Twierdzenie L124</span><br/>
Niech <math>n \in \mathbb{Z}_+ \;</math> i <math>\; \gcd (a, b) = 1</math>. Jeżeli <math>d \mid a^{n} b \;</math> i <math>\; d \nmid a^{n - 1} b</math>, to <math>d = a^{n} r</math>, gdzie <math>\gcd (a, r) = 1 \;</math> i <math>\; r \mid b</math>.

{{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
Zapiszmy <math>d</math> w&nbsp;postaci <math>d = a^t r</math>, gdzie <math>\gcd (a, r) = 1</math>. Łatwo zauważamy, że

:*&nbsp;&nbsp;&nbsp;ponieważ <math>a^t \mid d \;</math> i <math>\; d \mid a^{n} b</math>, to <math>a^t \mid a^{n} b</math>, ale <math>\gcd (a, b) = 1</math>, zatem (zobacz [[Ciągi liczbowe#C75|C75]]) <math>a^t \mid a^{n}</math>, skąd wynika, że <math>t \leqslant n</math>

:*&nbsp;&nbsp;&nbsp;ponieważ <math>r \mid d \;</math> i <math>\; d \mid a^{n} b</math>, to <math>r \mid a^{n} b</math>, ale <math>\gcd (a, r) = 1</math>, zatem (zobacz [[Ciągi liczbowe#C75|C75]]) <math>r \mid b</math>, skąd wynika, że <math>b = r k</math>, gdzie <math>\gcd (a, k) = 1</math>

:*&nbsp;&nbsp;&nbsp;ponieważ <math>d \nmid a^{n - 1} b</math>, to <math>a^t r \nmid a^{n - 1} r k</math>, czyli <math>a^t \nmid a^{n - 1} k</math>, ale <math>a \nmid k</math>, bo <math>\gcd (a, k) = 1</math>, zatem musi być <math>t > n - 1</math>

Łącząc uzyskane oszacowania, dostajemy <math>n - 1 < t \leqslant n</math>, skąd wynika, że <math>t = n</math>, czyli <math>d = a^{n} r</math>. Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L125" style="font-size: 110%; font-weight: bold;">Twierdzenie L125</span><br/>
Niech <math>a, b, c \in \mathbb{Z}</math> i <math>m \in \mathbb{Z}_+</math>. Prawdziwa jest następująca równoważność kongruencji

::<math>a \cdot c \equiv b \cdot c \!\! \pmod{m} \qquad \qquad \Longleftrightarrow \qquad \qquad a \equiv b \;\, \left( \operatorname{mod} \,\, {\small\frac{m}{\gcd (m, c)}} \right)</math>

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

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

Z założenia <math>a c \equiv b c \!\! \pmod{m}</math>, zatem <math>a c - b c = k m</math>, gdzie <math>k</math> jest pewną liczbą całkowitą, stąd

::<math>(a - b) \cdot {\small\frac{c}{\gcd (m, c)}} = k \cdot {\small\frac{m}{\gcd (m, c)}}</math>

Zauważmy, że liczby <math>{\small\frac{c}{\gcd (m, c)}} \;</math> i <math>\; {\small\frac{m}{\gcd (m, c)}}</math> są liczbami całkowitymi i&nbsp;są względnie pierwsze (zobacz [[Największy wspólny dzielnik, element odwrotny modulo, funkcja Eulera#H11|H11]]).

Ponieważ liczba <math>{\small\frac{c}{\gcd (m, c)}}</math> musi dzielić prawą stronę i&nbsp;jest względnie pierwsza z <math>{\small\frac{m}{\gcd (m, c)}}</math>, zatem <math>{\small\frac{c}{\gcd (m, c)}}</math> dzieli <math>k</math> (zobacz [[Ciągi liczbowe#C75|C75]]), czyli

::<math>k = {\small\frac{c}{\gcd (m, c)}} \cdot s</math>

dla pewnego całkowitego <math>s</math>. Stąd

::<math>(a - b) \cdot {\small\frac{c}{\gcd (m, c)}} = {\small\frac{c}{\gcd (m, c)}} \cdot s \cdot {\small\frac{m}{\gcd (m, c)}}</math>

I ostatecznie otrzymujemy

::<math>a - b = s \cdot {\small\frac{m}{\gcd (m, c)}}</math>

Co należało pokazać.


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

Z założenia <math>a \equiv b \;\, \left( \operatorname{mod} \,\, {\small\frac{m}{\gcd (m, c)}} \right)</math>, zatem

::<math>a \equiv b \;\, \left( \operatorname{mod} \,\, {\small\frac{m}{\gcd (m, c)}} \right) \qquad \qquad \Longrightarrow \qquad \qquad {\small\frac{m}{\gcd (m, c)}} \biggr\rvert (a - b)</math>

::::::::::::<math>\;\:\, \Longrightarrow \qquad \qquad {\small\frac{m}{\gcd (m, c)}} \cdot \gcd (m, c) \biggr\rvert (a - b) \cdot \gcd (m, c)</math>

<div style="margin-top: 1em; margin-bottom: 1em;">
::::::::::::<math>\;\;\, \Longrightarrow \qquad \qquad m \mid (a - b) \cdot \gcd (m, c)</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
::::::::::::<math>\;\;\, \Longrightarrow \qquad \qquad m \biggr\rvert (a - b) \cdot \gcd (m, c) \cdot {\small\frac{c}{\gcd (m, c)}}</math>
</div>

<div style="margin-top: 1em; margin-bottom: 1em;">
::::::::::::<math>\;\;\, \Longrightarrow \qquad \qquad m \mid (a - b) \cdot c</math>
</div>

<div style="margin-top: 1.5em; margin-bottom: 1em;">
::::::::::::<math>\;\;\, \Longrightarrow \qquad \qquad a \cdot c \equiv b \cdot c \!\! \pmod{m}</math>
</div>
Co należało pokazać.<br/>
&#9633;
{{\Spoiler}}



<span id="L126" style="font-size: 110%; font-weight: bold;">Uwaga L126</span><br/>
Rozważmy kongruencję

::<math>3 x \equiv 2 \!\! \pmod{5}</math>

Oczywiście liczba <math>3</math> ma element odwrotny <math>3^{- 1} \equiv 2 \!\! \pmod{5}</math> i&nbsp;łatwo znajdujemy rozwiązanie <math>x \equiv 4 \!\! \pmod{5}</math>. W&nbsp;zbiorze liczb całkowitych mamy taki obraz

<div style="font-size: 80%; margin-top: 1.5em; margin-bottom: 1.5em;">
<math>\boldsymbol{[}1, 2, 3, {\color{Red}\boldsymbol{4}}, 5\boldsymbol{]}, \boldsymbol{[}6, 7, 8, {\color{Red}\boldsymbol{9}}, 10\boldsymbol{]}, \boldsymbol{[}11, 12, 13, {\color{Red}\boldsymbol{14}}, 15\boldsymbol{]}, \boldsymbol{[}16, 17, 18, {\color{Red}\boldsymbol{19}}, 20\boldsymbol{]}, \boldsymbol{[}21, 22, 23, {\color{Red}\boldsymbol{24}}, 25\boldsymbol{]}, \boldsymbol{[}26, 27, 28, {\color{Red}\boldsymbol{29}}, 30\boldsymbol{]}, \boldsymbol{[}31, 32, 33, {\color{Red}\boldsymbol{34}}, 35\boldsymbol{]}, \boldsymbol{[}36, 37, 38, {\color{Red}\boldsymbol{39}}, 40\boldsymbol{]}, \boldsymbol{[}41, 42, 43, {\color{Red}\boldsymbol{44}}, 45\boldsymbol{]}, \boldsymbol{[}46, 47, 48, {\color{Red}\boldsymbol{49}}, 50\boldsymbol{]}, \boldsymbol{[}51, 52, 53, {\color{Red}\boldsymbol{54}}, 55\boldsymbol{]}, \boldsymbol{[}56, \dots</math>
</div>

Jeśli pomnożymy obie strony kongruencji i&nbsp;moduł przez <math>5</math>, to otrzymamy kongruencję równoważną (zobacz [[#L125|L125]])

::<math>15 x \equiv 10 \!\! \pmod{25}</math>

Teraz liczba <math>15</math> nie ma elemetu odwrotnego modulo <math>25</math>, ale dla tak małego modułu bez trudu znajdujemy rozwiązania kongruencji <math>x \equiv 4, 9, 14, 19, 24 \!\! \pmod{25}</math>. W&nbsp;zbiorze liczb całkowitych mamy taki obraz

<div style="font-size: 80%; margin-top: 1.5em; margin-bottom: 1.5em;">
<math>\boldsymbol{[}1, 2, 3, {\color{Red}\boldsymbol{4}}, 5, 6, 7, 8, {\color{Red}\boldsymbol{9}}, 10, 11, 12, 13, {\color{Red}\boldsymbol{14}}, 15, 16, 17, 18, {\color{Red}\boldsymbol{19}}, 20, 21, 22, 23, {\color{Red}\boldsymbol{24}}, 25\boldsymbol{]}, \boldsymbol{[}26, 27, 28, {\color{Red}\boldsymbol{29}}, 30, 31, 32, 33, {\color{Red}\boldsymbol{34}}, 35, 36, 37, 38, {\color{Red}\boldsymbol{39}}, 40, 41, 42, 43, {\color{Red}\boldsymbol{44}}, 45, 46, 47, 48, {\color{Red}\boldsymbol{49}}, 50\boldsymbol{]}, \boldsymbol{[}51, 52, 53, {\color{Red}\boldsymbol{54}}, 55, 56, 57, 58, {\color{Red}\boldsymbol{59}}, 60, \ldots</math>
</div>

Zbiór rozwiązań nie uległ zmianie, jedynie inaczej je teraz klasyfikujemy. Zauważmy, że

:* każde rozwiązanie kongruencji modulo <math>5</math> jest rozwiązaniem kongruencji modulo <math>25</math>
:* modulo <math>25</math> rozwiązania mają postać <math>x = 4 + 5 t</math>, gdzie <math>t = 0, 1, 2, 3, 4</math>

Nie ma w&nbsp;tym nic zaskakującego, bo

::<math>15 x = 15 (4 + 5 t) = 60 + 75 t \equiv 10 \!\! \pmod{25}</math>

Tak, jak być powinno.


Gdybyśmy dokonali całkowicie nieuprawnionego podzielenia stron kongruencji bez dzielenia modułu, to otrzymalibyśmy

::<math>3 x \equiv 2 \!\! \pmod{25}</math>

Ale rozwiązaniem tej kongruencji jest <math>x \equiv 9 \!\! \pmod{25}</math>. W&nbsp;zbiorze liczb całkowitych mamy teraz taki obraz

<div style="font-size: 80%; margin-top: 1.5em; margin-bottom: 1.5em;">
<math>\boldsymbol{[}1, 2, 3, 4, 5, 6, 7, 8, {\color{Red}\boldsymbol{9}}, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25\boldsymbol{]}, \boldsymbol{[}26, 27, 28, 29, 30, 31, 32, 33, {\color{Red}\boldsymbol{34}}, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50\boldsymbol{]}, \boldsymbol{[}51, 52, 53, 54, 55, 56, 57, 58, {\color{Red}\boldsymbol{59}}, 60, 61, \ldots</math>
</div>

I zgubilibyśmy <math>80</math>% rozwiązań.


Rozwiązania kongruencji <math>3 x \equiv 2 \!\! \pmod{25}</math> możemy znaleźć, korzystając z&nbsp;lematu Hensela (zobacz [[#L118|L118]]).

::<math>f(x) = 3 x - 2 \qquad \qquad f' (x) = 3</math>

::{| class="wikitable plainlinks"  style="font-size: 90%; text-align: center; margin-right: auto;"
|- style="height: 4em"
! <math>\;\; \boldsymbol{n} \;\;</math> || <math>\;\; \boldsymbol{\alpha} \;\;</math> || <math>\boldsymbol{f (\alpha)}</math> || <math>\boldsymbol{f' (\alpha)}</math> || <math>\boldsymbol{k f' (\alpha) \equiv - {\small\frac{f (\alpha)}{5^n}} \!\! \pmod{5}}</math> || <math>\boldsymbol{k \!\! \pmod{5}}</math> || <math>\boldsymbol{\beta \equiv \alpha + k \cdot 5^n \!\! \pmod{5^{n + 1}}}</math>
|- style="height: 3.5em"
| <math>1</math> || <math>4</math> || <math>10 = 5^n \cdot 2</math> || <math>3</math> || <math>3 k \equiv 3 \!\! \pmod{5}</math> || <math>1</math> || <math>4 + 1 \cdot 5^n \equiv 9</math>
|}

Zauważmy, że <math>k</math> jest określone modulo <math>5</math>, ale możemy je w&nbsp;tym przypadku wstawić do kongruencji określonej modulo <math>25</math>, bo modulo <math>25</math> mielibyśmy <math>k \equiv 1 + 5 t</math>, gdzie <math>t = 0, 1, 2, 3, 4</math> i&nbsp;niezależnie od wyboru wartości liczby <math>t</math> otrzymujemy <math>\beta \equiv \alpha + k \cdot 5 \equiv 4 + (1 + 5 t) \cdot 5 \equiv 4 + 5 + 25 t \equiv 9 \!\! \pmod{25}</math>.















== Przypisy ==
<references>

<ref name="order1">ang. ''order of'' <math>a</math> ''modulo'' <math>m</math></ref>

<ref name="generator1">Niekiedy do tej listy dodaje się liczbę <math>1</math>, dla której każda liczba całkowita jest generatorem: <math>\varphi (1) = 1</math>, <math>\gcd (a, 1) = 1</math>, <math>a^1 \equiv 1 \!\! \pmod{1}</math>.</ref>

<ref name="generator2">ang. ''generator or primitive root modulo'' <math>m</math></ref>

<ref name="ElliottMurata1">P. D. T. A. Elliott and Leo Murata, ''On the average of the least primitive root modulo p'', Journal of the London Mathematical Society, vol. 56, no. 2, pp. 435-454, 1997</ref>

<ref name="OliveiraSilva1">Tomás Oliveira e&nbsp;Silva, ''Least primitive root of prime numbers'', ([https://sweet.ua.pt/tos/p_roots.html LINK])</ref>

<ref name="CohenOliveiraSilvaTrudgian1">Stephen D. Cohen, Tomás Oliveira e&nbsp;Silva and Tim Trudgian, ''On Grosswald's conjecture on primitive roots'', Acta Arithmetica (2016), Volume: 172, Issue: 3, page 263-270</ref>

<ref name="McGownTrudgian1">Kevin J. McGown and Tim Trudgian, ''Explicit upper bounds on the least primitive root'', Proc. Amer. Math. Soc. 148 (2020), no. 3, 1049-1061.</ref>

<ref name="Lebesgue1">Victor-Amédée Lebesgue, ''Théorème sur les racines primitives'', Comptes rendus des séances de l'Académie des Sciences LXIV (24 June 1867), 1268-1269.</ref>

<ref name="Maxfield1">John Maxfield and Margaret Maxfield, ''The Existence of Integers Less than p&nbsp;Belonging to ep<sup>r-1</sup> (mod p<sup>r</sup>)'', Mathematics Magazine, Vol. 33, No. 4 (Mar. - Apr., 1960), pp. 219-220</ref>

<ref name="bezkwadratowa1">liczba bezkwadratowa (ang. ''squarefree integer or square-free integer'')</ref>

<ref name="AlfordGranvillePomerance1">W. R. Alford, Andrew Granville and Carl Pomerance, ''There are Infinitely Many Carmichael Numbers'', Annals of Mathematics, '''140''', (1994),  703-722</ref>

<ref name="Harman1">Glyn Harman, ''On the Number of Carmichael Numbers up to x'', Bull. London Math. Soc. 37 (2005) 641–650</ref>

<ref name="Harman2">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="Chernick1">Jack Chernick, ''On Fermat's simple theorem'', Bulletin of the American Mathematical Society, vol. 45(4), 1939, 269-274</ref>

<ref name="hd1">O ile liczba <math>m</math> nie jest liczbą Carmichaela.</ref>

<ref name="Lehmer1">Derrick Henry Lehmer, ''Tests for primality by the converse of Fermat's theorem'', Bulletin of the American Mathematical Society, vol. 33 (1927), 327-340.</ref>

<ref name="Shoup1">Victor Shoup, ''Searching for primitive roots in finite fields'', Mathematics of Computation 58 (1992), 369-380.</ref>

<ref name="Selfridge1">John Brillhart and John Lewis Selfridge, ''Some factorizations of 2<sup>n</sup> &plusmn; 1 and related results'', Mathematics of Computation, 21 (1967), 87-96.</ref>

<ref name="Pocklington1">Henry Cabourn Pocklington, ''The determination of the prime or composite nature of large numbers by Fermat's theorem'', Proceedings of the Cambridge Philosophical Society, vol. 18 (1914–1916), 29-30.</ref>

</references>























&nbsp;