Rząd liczby modulo i generatory modulo. Kongruencje wielomianowe. Lemat Hensela

08.04.2024

Rząd liczby modulo

Uwaga L1
Niech [math]\displaystyle{ a \in \mathbb{Z} }[/math], [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math] oraz [math]\displaystyle{ \gcd (a, m) = 1 }[/math]. Z twierdzenia Eulera (zobacz J27) wynika natychmiast, że zbiór [math]\displaystyle{ S }[/math] złożony z liczb [math]\displaystyle{ t \in \mathbb{Z}_+ }[/math] takich, że [math]\displaystyle{ a^t \equiv 1 \!\! \pmod{m} }[/math] nie jest zbiorem pustym. Jeśli tak, to zbiór [math]\displaystyle{ S }[/math] ma element najmniejszy. Wynika stąd poprawność następującej definicji.

Definicja L2
Niech [math]\displaystyle{ a \in \mathbb{Z} }[/math], [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math] oraz [math]\displaystyle{ \gcd (a, m) = 1 }[/math]. Rzędem liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] nazywamy najmniejszą liczbę całkowitą dodatnią [math]\displaystyle{ h }[/math] taką, że

[math]\displaystyle{ a^h \equiv 1 \!\! \pmod{m} }[/math]

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

Uwaga L3

•    z twierdzenia Eulera wynika oszacowanie [math]\displaystyle{ \operatorname{ord}(a, m) \leqslant \varphi (m) }[/math]
•    jeżeli [math]\displaystyle{ \operatorname{ord}(a, m) = h }[/math], to [math]\displaystyle{ \gcd (a, m) = 1 }[/math], bo gdyby było [math]\displaystyle{ \gcd (a, m) = d \gt 1 }[/math], to z kongruencji [math]\displaystyle{ a^h \equiv 1 \!\! \pmod{m} }[/math] mielibyśmy natychmiast [math]\displaystyle{ 0 \equiv 1 \!\! \pmod{d} }[/math]
•    [math]\displaystyle{ \operatorname{ord}(1, m) = 1 }[/math] dla [math]\displaystyle{ m \geqslant 1 \; }[/math] i [math]\displaystyle{ \; \operatorname{ord}(- 1, m) = 2 }[/math] dla [math]\displaystyle{ m \geqslant 3 }[/math]
•    rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] łatwo znajdziemy, wpisując w PARI/GP polecenie znorder(Mod(a, m))

Przykład L4
Zauważmy, że modulo [math]\displaystyle{ 15 }[/math] jest

[math]\displaystyle{ 2^1 \equiv 2, \qquad 2^2 \equiv 4, \qquad 2^3 \equiv 8, \qquad 2^4 \equiv 1 }[/math]

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

Twierdzenie L5
Niech [math]\displaystyle{ a \in \mathbb{Z} \; }[/math] i [math]\displaystyle{ \; m \in \mathbb{Z}_+ }[/math]. Jeżeli rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] jest równy [math]\displaystyle{ h }[/math], to liczby [math]\displaystyle{ a, a^2, \ldots, a^h }[/math] są różne modulo [math]\displaystyle{ m }[/math].

Dowód

Przypuśćmy, dla uzyskania sprzeczności, że [math]\displaystyle{ a^i \equiv a^j \!\! \pmod{m} }[/math] dla różnych liczb [math]\displaystyle{ 1 \leqslant i, j \leqslant h }[/math]. Nie zmniejszając ogólności, możemy założyć, że [math]\displaystyle{ i \gt j }[/math]. Czyli [math]\displaystyle{ 1 \leqslant i - j \leqslant h - 1 }[/math] i otrzymujemy

[math]\displaystyle{ a^j (a^{i - j} - 1) \equiv 0 \!\! \pmod{m} }[/math]

Ponieważ [math]\displaystyle{ \gcd (a, m) = 1 }[/math], to [math]\displaystyle{ m }[/math] musi dzielić wyrażenie [math]\displaystyle{ a^{i - j} - 1 }[/math] (zobacz C74). Zatem

[math]\displaystyle{ a^{i - j} - 1 \equiv 0 \!\! \pmod{m} }[/math]

[math]\displaystyle{ a^{i - j} \equiv 1 \!\! \pmod{m} }[/math]

Wbrew założeniu, że rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] jest równy [math]\displaystyle{ h }[/math]. Co należało pokazać.
□

Zadanie L6
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Pokazać, że jeżeli

[math]\displaystyle{ a^n \not\equiv - 1 \!\! \pmod{p} }[/math]

to [math]\displaystyle{ 2 n }[/math] nie może być rzędem liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p }[/math].

Rozwiązanie

Przypuśćmy, dla uzyskania sprzeczności, że [math]\displaystyle{ 2 n }[/math] jest rzędem [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p }[/math]. Z definicji mamy

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

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

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

[math]\displaystyle{ a^n \equiv - 1 \!\! \pmod{p} \qquad \qquad \text{albo} \qquad \qquad a^n \equiv 1 \!\! \pmod{p} }[/math]

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

[math]\displaystyle{ a^n \equiv 1 \!\! \pmod{p} }[/math]

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

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

[math]\displaystyle{ 13^6 \equiv - 1 \!\! \pmod{17} }[/math]

ale [math]\displaystyle{ \operatorname{ord}(13, 17) = 4 \neq 2 \cdot 6 }[/math].
□

Twierdzenie L7
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ \: }[/math] i [math]\displaystyle{ \; \gcd (a, m) = 1 }[/math]. Rzędy liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ a^{- 1} }[/math] modulo [math]\displaystyle{ m }[/math] są równe.

Dowód

Ponieważ z założenia [math]\displaystyle{ \gcd (a, m) = 1 }[/math], to liczba [math]\displaystyle{ a }[/math] ma element odwrotny modulo [math]\displaystyle{ m }[/math] (zobacz H17, H18). Dla uproszczenia zapisu rozważmy liczby [math]\displaystyle{ x, y }[/math] takie, że

[math]\displaystyle{ x y \equiv 1 \!\! \pmod{m} }[/math]

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

[math]\displaystyle{ x^h \equiv 1 \!\! \pmod{m} }[/math]

[math]\displaystyle{ x^h y^h \equiv y^h \!\! \pmod{m} }[/math]

[math]\displaystyle{ (x y)^h \equiv y^h \!\! \pmod{m} }[/math]

[math]\displaystyle{ 1 \equiv y^h \!\! \pmod{m} }[/math]

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

[math]\displaystyle{ \operatorname{ord}(x, m) \lt \operatorname{ord}(y, m) \leqslant \operatorname{ord}(x, m) }[/math]

Co jest niemożliwe. Uzyskana sprzeczność kończy dowód.
□

Twierdzenie L8
Niech [math]\displaystyle{ m, n \in \mathbb{Z}_+ }[/math], zaś [math]\displaystyle{ a }[/math] liczbą całkowitą taką, że [math]\displaystyle{ \gcd (a, m) = 1 }[/math], wtedy

•    [math]\displaystyle{ a^w \equiv 1 \!\! \pmod{m} \quad \qquad \Longleftrightarrow \qquad \quad \operatorname{ord}(a, m) \mid w }[/math]

•    [math]\displaystyle{ m \mid n \qquad \qquad \Longrightarrow \qquad \qquad \operatorname{ord}(a, m) \mid \operatorname{ord}(a, n) }[/math]

Dowód

Punkt 1.

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

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

[math]\displaystyle{ 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]\displaystyle{ h }[/math] jest z definicji najmniejszą liczbą dodatnią, dla której [math]\displaystyle{ a^h \equiv 1 \!\! \pmod{m} }[/math] oraz [math]\displaystyle{ r \lt h }[/math], to musi być [math]\displaystyle{ r = 0 }[/math], co oznacza, że [math]\displaystyle{ h \mid w }[/math].

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

Jeżeli [math]\displaystyle{ h }[/math] jest dzielnikiem wykładnika [math]\displaystyle{ w }[/math], to istnieje liczba [math]\displaystyle{ s }[/math] taka, że [math]\displaystyle{ w = s \cdot h }[/math], zatem

[math]\displaystyle{ 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]\displaystyle{ h = \operatorname{ord}(a, m) }[/math] oraz [math]\displaystyle{ f = \operatorname{ord}(a, n) }[/math]. Z założenia [math]\displaystyle{ m \mid n }[/math], zatem z kongruencji [math]\displaystyle{ a^f \equiv 1 \!\! \pmod{n} }[/math] wynika kongruencja [math]\displaystyle{ a^f \equiv 1 \!\! \pmod{m} }[/math]. Ponieważ rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] jest równy [math]\displaystyle{ h }[/math], to wykładnik [math]\displaystyle{ f }[/math] musi być wielokrotnością [math]\displaystyle{ h }[/math] (zobacz punkt 1.), czyli [math]\displaystyle{ h \mid f }[/math]. Co należało pokazać.
□

Zadanie L9
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ \: }[/math] i [math]\displaystyle{ \; p }[/math] będzie liczbą pierwszą. Pokazać, że jeżeli [math]\displaystyle{ \gcd (a, m) = 1 }[/math], to [math]\displaystyle{ \operatorname{ord}(a, m) \mid \varphi (m) }[/math].

Rozwiązanie

Z twierdzenia Eulera wiemy, że [math]\displaystyle{ a^{\varphi (m)} \equiv 1 \!\! \pmod{m} }[/math], zatem [math]\displaystyle{ \varphi (m) }[/math] musi być wielokrotnością rzędu liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] (zobacz L8 p.1). Co należało pokazać.
□

Uwaga L10
Z zadania L9 wynika, że w czasie znajdowania rzędu liczby możemy ograniczyć się do rozpatrywania jedynie dzielników [math]\displaystyle{ \varphi (m) }[/math]. Znajdźmy rząd liczby [math]\displaystyle{ 3 }[/math] modulo [math]\displaystyle{ 37 }[/math]. Dzielnikami [math]\displaystyle{ \varphi (37) = 36 }[/math] są liczby [math]\displaystyle{ 1, 2, 3, 4, 6, 9, 12, 18, 36 }[/math]. Sprawdzając, otrzymujemy modulo [math]\displaystyle{ 37 }[/math]

[math]\displaystyle{ 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]\displaystyle{ \operatorname{ord}(3, 37) = 18 }[/math].

Zadanie L11
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Pokazać, że jeżeli [math]\displaystyle{ p \mid (n^2 + 1) }[/math], to [math]\displaystyle{ p }[/math] jest postaci [math]\displaystyle{ 4 k + 1 }[/math].

Rozwiązanie

Z założenia [math]\displaystyle{ n^2 + 1 \equiv 0 \!\! \pmod{p} }[/math], czyli [math]\displaystyle{ n^2 \equiv - 1 \!\! \pmod{p} }[/math], zatem [math]\displaystyle{ n^4 \equiv 1 \!\! \pmod{p} }[/math].

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

Zadanie L12
Jeżeli [math]\displaystyle{ n \in \mathbb{Z}_+ \: }[/math] i [math]\displaystyle{ \; a \geqslant 2 }[/math], to liczba [math]\displaystyle{ n }[/math] jest dzielnikiem [math]\displaystyle{ \varphi (a^n - 1) }[/math].

Rozwiązanie

Łatwo widzimy, że [math]\displaystyle{ \gcd (a, a^n - 1) = 1 }[/math]. Niech [math]\displaystyle{ \operatorname{ord}(a, a^n - 1) = h }[/math].

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

Dla wykładników [math]\displaystyle{ r \lt n }[/math] dostajemy [math]\displaystyle{ a^r - 1 \lt a^n - 1 }[/math] i nie może być [math]\displaystyle{ (a^n - 1) \mid (a^r - 1) }[/math], bo większa liczba nie może dzielić mniejszej.

Zatem dla [math]\displaystyle{ r \lt n }[/math] mamy [math]\displaystyle{ a^r \not\equiv 1 \!\! \pmod{a^n - 1} }[/math]. Wynika stąd, że [math]\displaystyle{ h = n }[/math]. Ponieważ [math]\displaystyle{ \operatorname{ord}(a, a^n - 1) = n }[/math], to [math]\displaystyle{ n \mid \varphi (a^n - 1) }[/math]. Co należało pokazać.
□

Zadanie L13
Niech [math]\displaystyle{ a, m, n \in \mathbb{Z}_+ }[/math]. Pokazać, że [math]\displaystyle{ \gcd (a^m - 1, a^n - 1) = a^{\gcd (m, n)} - 1 }[/math].

Rozwiązanie

Zauważmy, że prawdziwy jest następujący ciąg równoważności.

[math]\displaystyle{ \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]\displaystyle{ \gcd (a^m - 1, a^n - 1) \mid (a^{\gcd (m, n)} - 1) }[/math]

oraz

[math]\displaystyle{ (a^{\gcd (m, n)} - 1) \mid \gcd (a^m - 1, a^n - 1) }[/math]

Czyli [math]\displaystyle{ | \gcd (a^m - 1, a^n - 1) | = | a^{\gcd (m, n)} - 1 | }[/math]. Co należało pokazać. Zobacz też twierdzenie H15.
□

Zadanie L14
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ \: }[/math] i [math]\displaystyle{ \; \gcd (a, m) = 1 }[/math]. Pokazać, że

[math]\displaystyle{ a \equiv b \!\! \pmod{m} \qquad \quad \Longrightarrow \qquad \quad \operatorname{ord}(a, m) = \operatorname{ord}(b, m) }[/math]

Rozwiązanie

Zauważmy najpierw, że ponieważ [math]\displaystyle{ a \equiv b \!\! \pmod{m} }[/math], to [math]\displaystyle{ \gcd (b, m) = 1 }[/math], czyli rząd liczby [math]\displaystyle{ b }[/math] jest określony. Oznaczmy: [math]\displaystyle{ h = \operatorname{ord}(a, m) }[/math], [math]\displaystyle{ f = \operatorname{ord}(b, m) }[/math].

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

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

Ponieważ [math]\displaystyle{ f \mid h \; }[/math] i [math]\displaystyle{ \; h \mid f }[/math], to [math]\displaystyle{ | h | = | f | }[/math]. Co należało pokazać.
□

Twierdzenie L15
Jeżeli [math]\displaystyle{ \gcd (a b, m) = 1 }[/math] oraz [math]\displaystyle{ \gcd (\operatorname{ord}(a, m), \operatorname{ord}(b, m)) = 1 }[/math], to

[math]\displaystyle{ \operatorname{ord}(a b, m) = \operatorname{ord}(a, m) \cdot \operatorname{ord}(b, m) }[/math]

Dowód

Z założenia [math]\displaystyle{ \gcd (a b, m) = 1 }[/math], czyli [math]\displaystyle{ \gcd (a, m) = 1 \; }[/math] i [math]\displaystyle{ \; \gcd (b, m) = 1 }[/math]. Czyli liczby [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] mają określone rzędy modulo [math]\displaystyle{ m }[/math].

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

[math]\displaystyle{ a^h \equiv 1 \!\! \pmod{m} }[/math]

[math]\displaystyle{ b^f \equiv 1 \!\! \pmod{m} }[/math]

Czyli

[math]\displaystyle{ (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]\displaystyle{ r \lt h f }[/math], dla którego [math]\displaystyle{ (a b)^r \equiv 1 \!\! \pmod{m} }[/math]. Mielibyśmy

[math]\displaystyle{ (a b)^r \equiv 1 \!\! \pmod{m} }[/math]

[math]\displaystyle{ (a b)^{r h} \equiv 1 \!\! \pmod{m} }[/math]

[math]\displaystyle{ (a^h)^r \cdot b^{r h} \equiv 1 \!\! \pmod{m} }[/math]

[math]\displaystyle{ b^{r h} \equiv 1 \!\! \pmod{m} }[/math]

Zatem [math]\displaystyle{ f \mid r h }[/math], ale z założenia [math]\displaystyle{ \gcd (h, f) = 1 }[/math], czyli [math]\displaystyle{ f \mid r }[/math].

Podobnie pokazujemy, że [math]\displaystyle{ h \mid r }[/math].

Ponieważ [math]\displaystyle{ h }[/math] i [math]\displaystyle{ f }[/math] są względnie pierwsze, to [math]\displaystyle{ h f \mid r }[/math] (zobacz C75), zatem [math]\displaystyle{ h f \leqslant r }[/math]. Uzyskana sprzeczność kończy dowód.
□

Zadanie L16
Niech [math]\displaystyle{ m \geqslant 3 }[/math] będzie liczbą całkowitą. Pokazać, że jeżeli rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] jest liczbą nieparzystą, to

[math]\displaystyle{ \operatorname{ord}(- a, m) = 2 \cdot \operatorname{ord}(a, m) }[/math]

Rozwiązanie

Zauważmy, że wzór nie jest prawdziwy dla [math]\displaystyle{ m = 2 }[/math], bo dla dowolnej liczby nieparzystej [math]\displaystyle{ a }[/math] mamy [math]\displaystyle{ \operatorname{ord}(\pm a, 2) = 1 }[/math].

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

Z założenia rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] jest liczbą nieparzystą, zatem

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

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

Zadanie L17
Niech [math]\displaystyle{ a \in \mathbb{Z} }[/math] i [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math]. Pokazać, że jeżeli liczby [math]\displaystyle{ a, m }[/math] są nieparzyste i [math]\displaystyle{ \operatorname{ord}(a, m) = h }[/math], to [math]\displaystyle{ \operatorname{ord}(a, 2 m) = h }[/math].

Rozwiązanie

Zauważmy, że liczby [math]\displaystyle{ a, m }[/math] nie mogą być jednocześnie parzyste, bo mielibyśmy [math]\displaystyle{ \gcd (a, m) \geqslant 2 }[/math] i rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] nie byłby określony (zobacz L3). Z założenia rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math] istnieje i jest równy [math]\displaystyle{ h }[/math], zatem [math]\displaystyle{ \gcd (a, m) = 1 }[/math]. Ponieważ [math]\displaystyle{ a }[/math] jest liczbą nieparzystą, to [math]\displaystyle{ \gcd (a, 2) = 1 }[/math], czyli [math]\displaystyle{ \gcd (a, 2 m) = 1 }[/math] (zobacz H6). Co oznacza, że rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ 2 m }[/math] jest określony. Niech [math]\displaystyle{ f = \operatorname{ord}(a, 2 m) }[/math], zatem

[math]\displaystyle{ a^f \equiv 1 \!\! \pmod{2 m} }[/math]

Skąd dostajemy

[math]\displaystyle{ a^f \equiv 1 \!\! \pmod{m} }[/math]

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

[math]\displaystyle{ a^h \equiv 1 \!\! \pmod{m} }[/math]

[math]\displaystyle{ a^h \equiv 1 \!\! \pmod{2} }[/math]

Uwzględniając, że [math]\displaystyle{ \gcd (2, m) = 1 }[/math], układ ten możemy w sposób równoważny zapisać w postaci

[math]\displaystyle{ a^h \equiv 1 \!\! \pmod{2 m} }[/math]

(zobacz J1). Ponieważ [math]\displaystyle{ f }[/math] jest rzędem liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ 2 m }[/math], to [math]\displaystyle{ f \mid h }[/math]. Otrzymaliśmy, że [math]\displaystyle{ h \mid f \; }[/math] i [math]\displaystyle{ \; f \mid h }[/math], zatem [math]\displaystyle{ | f | = | h | }[/math]. Co należało pokazać.
□

Twierdzenie L18
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ \: }[/math] i [math]\displaystyle{ \; \gcd (a, m) = 1 }[/math]. Rząd liczby [math]\displaystyle{ a^r }[/math] modulo [math]\displaystyle{ m }[/math] jest równy

[math]\displaystyle{ \operatorname{ord}(a^r, m) = {\small\frac{h}{\gcd (r, h)}} }[/math]

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

Dowód

Aby ułatwić sobie operowanie liczbami występującymi w dowodzonym wzorze, wprowadzimy oznaczenia

[math]\displaystyle{ b = a^r \qquad \quad f = \operatorname{ord}(b, m) \qquad \quad d = \gcd (r, h) }[/math]

Ponieważ [math]\displaystyle{ d = \gcd (r, h) }[/math], to możemy napisać [math]\displaystyle{ r = s \cdot d \; }[/math] i [math]\displaystyle{ \; h = t \cdot d }[/math], gdzie [math]\displaystyle{ \gcd (s, t) = 1 }[/math] (zobacz H11).

Z definicji liczb [math]\displaystyle{ b \: }[/math] i [math]\displaystyle{ \: f }[/math] mamy

[math]\displaystyle{ b^f = a^{r f} \equiv 1 \!\! \pmod{m} }[/math]

Ponieważ rząd liczby [math]\displaystyle{ a }[/math] jest równy [math]\displaystyle{ h }[/math], to [math]\displaystyle{ h \mid r f }[/math], czyli [math]\displaystyle{ t d \mid s d f }[/math], zatem [math]\displaystyle{ t \mid s f }[/math], ale [math]\displaystyle{ \gcd (s, t) = 1 }[/math] i dostajemy, że [math]\displaystyle{ t \mid f }[/math].

Zauważmy teraz, że

[math]\displaystyle{ b^t = (a^r)^t = (a^{s d})^{\tfrac{h}{d}} = (a^s)^h = (a^h)^s \equiv 1 \!\! \pmod{m} }[/math]

Zatem [math]\displaystyle{ f \mid t }[/math]. Ponieważ [math]\displaystyle{ t \mid f }[/math] oraz [math]\displaystyle{ f \mid t }[/math], to [math]\displaystyle{ | f | = | t | }[/math]. Wynika stąd

[math]\displaystyle{ f = t = {\small\frac{h}{d}} = {\small\frac{h}{\gcd (r, h)}} }[/math]

Co należało pokazać.
□

Zadanie L19
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math], [math]\displaystyle{ \gcd (a, m) = 1 }[/math] oraz [math]\displaystyle{ h = \operatorname{ord}(a, m) }[/math]. Jeżeli [math]\displaystyle{ d \mid h }[/math], to [math]\displaystyle{ \operatorname{ord}(a^d, m) = {\small\frac{h}{d}} }[/math].

Rozwiązanie

Wystarczy sprawdzić, że liczba [math]\displaystyle{ {\small\frac{h}{d}} }[/math] jest rzędem liczby [math]\displaystyle{ a^d }[/math] modulo [math]\displaystyle{ m }[/math]. Łatwo otrzymujemy

[math]\displaystyle{ (a^d)^{\tfrac{h}{d}} = a^h \equiv 1 \!\! \pmod{m} }[/math]

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

Zadanie L20
Niech [math]\displaystyle{ p \in \mathbb{P} }[/math]. Jeżeli istnieje liczba całkowita [math]\displaystyle{ a }[/math] względnie pierwsza z [math]\displaystyle{ p }[/math] taka, że [math]\displaystyle{ \operatorname{ord}(a, p) = h }[/math], to

•    liczby [math]\displaystyle{ a, a^2, \ldots, a^h }[/math] są wszystkimi liczbami modulo [math]\displaystyle{ p }[/math] spełniającymi kongruencję [math]\displaystyle{ x^h \equiv 1 \!\! \pmod{p} }[/math]

•    istnieje dokładnie [math]\displaystyle{ \varphi (h) }[/math] liczb [math]\displaystyle{ x }[/math], dla których [math]\displaystyle{ \operatorname{ord}(x, p) = h }[/math]

Rozwiązanie

Punkt 1.

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

[math]\displaystyle{ (a^k)^h = (a^h)^k \equiv 1^k \equiv 1 \!\! \pmod{p} }[/math]

Z twierdzenia L5 wiemy, że liczby [math]\displaystyle{ a, a^2, \ldots, a^h }[/math] są różne modulo [math]\displaystyle{ p }[/math]. Z twierdzenia Lagrange'a wiemy, że kongruencja

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

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

Punkt 2.

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

Z twierdzenia L18 wiemy, że

[math]\displaystyle{ \operatorname{ord}(a^k, m) = {\small\frac{h}{\gcd (k, h)}} }[/math]

Ponieważ istnieje [math]\displaystyle{ \varphi (h) }[/math] liczb całkowitych dodatnich [math]\displaystyle{ k \leqslant h }[/math] takich, że [math]\displaystyle{ \gcd (k, h) = 1 }[/math], to istnieje dokładnie [math]\displaystyle{ \varphi (h) }[/math] liczb [math]\displaystyle{ a^k }[/math] (różnych modulo [math]\displaystyle{ p }[/math]) takich, że [math]\displaystyle{ \operatorname{ord}(a^k, p) = h }[/math]. Co należało pokazać.
□

Twierdzenie L21
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą i [math]\displaystyle{ h \in \mathbb{Z}_+ }[/math]. Jeżeli [math]\displaystyle{ h \mid (p - 1) }[/math], to istnieje [math]\displaystyle{ \varphi (h) }[/math] liczb, których rząd modulo [math]\displaystyle{ p }[/math] jest równy [math]\displaystyle{ h }[/math].

Dowód

Zauważmy, że dowodzone twierdzenie jest istotnie różne od punktu 2. zadania L20, bo teraz nie zakładamy istnienia liczby [math]\displaystyle{ a }[/math] takiej, że [math]\displaystyle{ \operatorname{ord}(a, p) = h }[/math].

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

[math]\displaystyle{ 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]\displaystyle{ f(h) \leqslant \varphi (h) }[/math].

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

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

[math]\displaystyle{ \sum_{h \mid (p - 1)} f (h) = p - 1 }[/math]

gdzie sumowanie przebiega po wszystkich dodatnich dzielnikach [math]\displaystyle{ h }[/math] liczby [math]\displaystyle{ p - 1 }[/math].

Z twierdzenia H44 wiemy, że

[math]\displaystyle{ \sum_{h \mid (p - 1)} \varphi (h) = p - 1 }[/math]

Zatem, uwzględniając oszacowanie [math]\displaystyle{ f(h) \leqslant \varphi (h) }[/math], możemy napisać

[math]\displaystyle{ 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]\displaystyle{ h }[/math] liczby [math]\displaystyle{ p - 1 }[/math] jest [math]\displaystyle{ f(h) = \varphi (h) }[/math]. Co należało pokazać.
□

Zadanie L22
Niech [math]\displaystyle{ a \in \mathbb{Z} \; }[/math] i [math]\displaystyle{ \; p }[/math] będzie liczbą pierwszą postaci [math]\displaystyle{ p = 6 k + 1 }[/math]. Pokazać, że jeżeli [math]\displaystyle{ \operatorname{ord}(a, p) = 3 }[/math], to [math]\displaystyle{ \operatorname{ord}(a + 1, p) = 6 }[/math].

Rozwiązanie

Założenie, że liczba pierwsza jest postaci [math]\displaystyle{ 6 k + 1 }[/math], jest konieczne, bo liczby [math]\displaystyle{ 3 }[/math] i [math]\displaystyle{ 6 }[/math] muszą być dzielnikami [math]\displaystyle{ \varphi (p) = p - 1 }[/math]. Dla liczb pierwszych postaci [math]\displaystyle{ 6 k + 5 }[/math] nigdy nie będzie [math]\displaystyle{ \operatorname{ord}(a, p) = 3 }[/math]. Z twierdzenia L21 wiemy, dla liczb pierwszych postaci [math]\displaystyle{ 6 k + 1 }[/math] istnieją dwie liczby, których rząd jest równy [math]\displaystyle{ 3 }[/math] i dwie liczby, których rząd jest równy [math]\displaystyle{ 6 }[/math].

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

[math]\displaystyle{ a + 1 \not\equiv 1 \!\! \pmod{p} }[/math]

[math]\displaystyle{ (a + 1)^2 = a^2 + a + 1 + a \equiv a \not\equiv 1 \!\! \pmod{p} }[/math]

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

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

[math]\displaystyle{ (a + 1)^5 \equiv - a \not\equiv 1 \!\! \pmod{p} , \; }[/math] bo gdyby [math]\displaystyle{ a \equiv - 1 \!\! \pmod{p} }[/math], to [math]\displaystyle{ a^2 \equiv 1 \!\! \pmod{p} \; }[/math] i mielibyśmy [math]\displaystyle{ \operatorname{ord}(a, p) = 2 }[/math]

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

Zatem [math]\displaystyle{ \operatorname{ord}(a + 1, p) = 6 }[/math]. Co należało pokazać.
□

Twierdzenie L23
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ \: }[/math] i [math]\displaystyle{ \; \gcd (a, m) = 1 }[/math]. Kongruencja [math]\displaystyle{ a^r \equiv a^s }[/math] modulo [math]\displaystyle{ \boldsymbol{m} }[/math] jest prawdziwa wtedy i tylko wtedy, gdy prawdziwa jest kongruencja [math]\displaystyle{ r \equiv s }[/math] modulo rząd liczby [math]\displaystyle{ \boldsymbol{a} }[/math]

[math]\displaystyle{ a^r \equiv a^s \!\! \pmod{m} \quad \qquad \Longleftrightarrow \qquad \quad r \equiv s \!\! \pmod{\operatorname{ord}(a, m)} }[/math]

Dowód

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

Jeśli [math]\displaystyle{ 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]\displaystyle{ s \gt r }[/math], zatem rozważaną kongruencję możemy zapisać w postaci

[math]\displaystyle{ a^r \equiv a^s \!\! \pmod{m} }[/math]

[math]\displaystyle{ a^r - a^s \equiv 0 \!\! \pmod{m} }[/math]

[math]\displaystyle{ a^r \cdot (a^{s - r} - 1) \equiv 0 \!\! \pmod{m} }[/math]

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

[math]\displaystyle{ a^{s - r} - 1 \equiv 0 \!\! \pmod{m} }[/math]

[math]\displaystyle{ a^{s - r} \equiv 1 \!\! \pmod{m} }[/math]

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

[math]\displaystyle{ r \equiv s \!\! \pmod{\operatorname{ord}(a, m}) }[/math]

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

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

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

Zadanie L24
Niech [math]\displaystyle{ m \in \mathbb{Z}_+ \: }[/math] i [math]\displaystyle{ \; \gcd (a, m) = 1 }[/math] oraz [math]\displaystyle{ h = \operatorname{ord}(a, m) }[/math]. Pokazać, że jeżeli [math]\displaystyle{ r \equiv s \!\! \pmod{h} }[/math], to [math]\displaystyle{ \operatorname{ord}(a^r, m) = \operatorname{ord}(a^s, m) }[/math].

Rozwiązanie

Jeżeli [math]\displaystyle{ r \equiv s \!\! \pmod{h} }[/math], to z twierdzenia L23 wynika, że [math]\displaystyle{ a^r \equiv a^s \!\! \pmod{m} }[/math] i na mocy L14 mamy [math]\displaystyle{ \operatorname{ord}(a^r, m) = \operatorname{ord}(a^s, m) }[/math]. Co należało pokazać.
□

Twierdzenie L25
Niech [math]\displaystyle{ m, r \in \mathbb{Z}_+ \: }[/math] i [math]\displaystyle{ \; a \in \mathbb{Z} }[/math]. Jeżeli

[math]\displaystyle{ a^r \equiv 1 \!\! \pmod{m} }[/math]

oraz dla każdego dzielnika pierwszego [math]\displaystyle{ q }[/math] liczby [math]\displaystyle{ r }[/math] jest

[math]\displaystyle{ a^{\tfrac{r}{q}} \not\equiv 1 \!\! \pmod{m} }[/math]

to [math]\displaystyle{ \operatorname{ord}(a, m) = r }[/math].

Dowód

Z założenia

[math]\displaystyle{ a^r \equiv 1 \!\! \pmod{m} }[/math]

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

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

[math]\displaystyle{ a^h \equiv 1 \!\! \pmod{m} }[/math]

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

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

Zadanie L26
Niech [math]\displaystyle{ a, n \in \mathbb{Z}_+ \: }[/math] i [math]\displaystyle{ \; p }[/math] będzie liczbą pierwszą nieparzystą. Pokazać, że jeżeli [math]\displaystyle{ p \mid (a^{2^{\large n}} + 1) }[/math], to [math]\displaystyle{ p \equiv 1 \!\! \pmod{2^{n + 1}} }[/math].

Rozwiązanie

Z założenia

[math]\displaystyle{ a^{2^{\large n}} \equiv - 1 \!\! \pmod{p} }[/math]

Zatem

[math]\displaystyle{ (a^{2^{\large n}})^2 = a^{2^{\large n + 1}} \equiv 1 \!\! \pmod{p} }[/math]

Z twierdzenia L25 wynika natychmiast, że [math]\displaystyle{ \operatorname{ord}(a, p) = 2^{n + 1} }[/math]. Ponieważ [math]\displaystyle{ \operatorname{ord}(a, p) \mid \varphi (p) }[/math] (zobacz L9), to [math]\displaystyle{ 2^{n + 1} \mid (p - 1) }[/math]. Co należało pokazać.
□

Zadanie L27
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Pokazać, że istnieje nieskończenie wiele liczb pierwszych postaci [math]\displaystyle{ 2^{n + 1} k + 1 }[/math].

Rozwiązanie

Zauważmy, że problem jest szczególnym przypadkiem twierdzenia Dirichleta (zobacz C27). Załóżmy, dla uzyskania sprzeczności, że istnieje jedynie skończona ilość liczb pierwszych [math]\displaystyle{ p_1, \ldots, p_s }[/math] postaci [math]\displaystyle{ 2^{n + 1} k + 1 }[/math] i niech

[math]\displaystyle{ a = (2 p_1 \cdot \ldots \cdot p_s)^{2^{\large n}} + 1 }[/math]

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

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

Twierdzenie L28
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą, a [math]\displaystyle{ F_n = 2^{2^{\large n}} + 1 }[/math] oznacza liczbę Fermata. Jeżeli liczba pierwsza [math]\displaystyle{ p }[/math] jest dzielnikiem [math]\displaystyle{ F_n }[/math], gdzie [math]\displaystyle{ n \geqslant 2 }[/math], to [math]\displaystyle{ p }[/math] jest postaci [math]\displaystyle{ p = 2^{n + 2} k + 1 }[/math].

Dowód

Z założenia

[math]\displaystyle{ 2^{2^{\large n}} \equiv - 1 \!\! \pmod{p} }[/math]

Podnosząc do kwadratu otrzymujemy

[math]\displaystyle{ (2^{2^{\large n}})^2 = 2^{2^{\large n + 1}} \equiv 1 \!\! \pmod{p} }[/math]

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

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

Zatem

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

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

[math]\displaystyle{ \left( {\small\frac{2}{p}} \right)_{\small{\!\! J}} = (- 1)^{(p^{\large 2} - 1) / 8} = 1 }[/math]

Czyli [math]\displaystyle{ 2 }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math] i z kryterium Eulera mamy

[math]\displaystyle{ 2^{\tfrac{p - 1}{2}} = 2^{k \cdot 2^{\large n}} \equiv 1 \!\! \pmod{p} }[/math]

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

Twierdzenie L29
Jeżeli [math]\displaystyle{ m \geqslant 3 }[/math] jest liczbą nieparzystą, to kongruencja [math]\displaystyle{ x^{m - 1} \equiv - 1 \!\! \pmod{m} }[/math] nie ma rozwiązań.

Dowód

Przypuśćmy, w celu uzyskania sprzeczności, że [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą lub potęgą liczby pierwszej nieparzystej. Wtedy mielibyśmy

[math]\displaystyle{ x^{p - 1} \equiv - 1 \!\! \pmod{p} \qquad \qquad \text{lub} \qquad \qquad x^{p^n - 1} \equiv - 1 \!\! \pmod{p^n} }[/math]

[math]\displaystyle{ \quad \; x^{(p - 1) (1 + p + p^2 + \ldots + p^{n - 1})} \equiv - 1 \!\! \pmod{p} }[/math]

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

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

[math]\displaystyle{ a^{m - 1} \equiv - 1 \!\! \pmod{m} }[/math]

Niech [math]\displaystyle{ p }[/math] oznacza dowolny czynnik pierwszy [math]\displaystyle{ q_i }[/math]. Ponieważ [math]\displaystyle{ p \mid m }[/math], to możemy zapisaną kongruencję rozpatrywać modulo [math]\displaystyle{ p }[/math]. Zatem

[math]\displaystyle{ a^{m - 1} \equiv - 1 \!\! \pmod{p} }[/math]

Podnosząc obie strony kongruencji do kwadratu, dostajemy

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

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

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

[math]\displaystyle{ h \mid 2^{u + 1} w \qquad \qquad \text{i} \qquad \qquad h \nmid 2^u w }[/math]

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

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

[math]\displaystyle{ p \equiv 1 \!\! \pmod{2^{u + 1}} }[/math]

Ponieważ przez [math]\displaystyle{ p }[/math] oznaczyliśmy dowolny dzielnik pierwszy [math]\displaystyle{ q_i }[/math] liczby [math]\displaystyle{ m }[/math], to otrzymujemy

[math]\displaystyle{ 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]\displaystyle{ m = 2^u w + 1 }[/math], gdzie [math]\displaystyle{ w }[/math] jest liczbą nieparzystą. Otrzymana sprzeczność kończy dowód.
□

Generatory modulo

Uwaga L30
Jedynymi liczbami naturalnymi mającymi generatory są liczby [math]\displaystyle{ 2, 4, p^k, 2 p^k }[/math], gdzie [math]\displaystyle{ k \geqslant 1 }[/math] i [math]\displaystyle{ p }[/math] oznacza liczbę pierwszą nieparzystą. Zatem istnienie generatora jest raczej wyjątkiem niż regułą. Zbadamy właściwości generatorów, a następnie wyjaśnimy, dlaczego tak niewiele liczb ma generator.

Generatory modulo [math]\displaystyle{ \boldsymbol{m} }[/math]

 

Definicja L31
Jeżeli [math]\displaystyle{ g }[/math] jest dowolną liczbą całkowitą taką, że [math]\displaystyle{ \gcd (g, m) = 1 }[/math] oraz rząd liczby [math]\displaystyle{ g }[/math] modulo [math]\displaystyle{ m }[/math] jest równy [math]\displaystyle{ \varphi (m) }[/math], to liczbę [math]\displaystyle{ g }[/math] nazywamy generatorem lub pierwiastkiem pierwotnym modulo [math]\displaystyle{ m }[/math].

Uwaga L32
Niech [math]\displaystyle{ g }[/math] będzie generatorem modulo [math]\displaystyle{ m }[/math]. Nazwa „generator” wynika z prostej właściwości generatorów: kolejne potęgi [math]\displaystyle{ g^1, g^2, \ldots, g^{\varphi (m)} }[/math] są różne modulo [math]\displaystyle{ m }[/math] (zobacz L5) i generują wszystkie liczby względnie pierwsze z [math]\displaystyle{ m }[/math] (oczywiście modulo [math]\displaystyle{ m }[/math]).

W przypadku, gdy [math]\displaystyle{ m = p }[/math] jest liczbą pierwszą, zbiory [math]\displaystyle{ \{ g^1, g^2, \ldots, g^{p - 1} \} \; }[/math] i [math]\displaystyle{ \; \{ 1, 2, \ldots, p - 1 \} }[/math] są równe modulo [math]\displaystyle{ p }[/math] (zobacz H24).

Przykład L33
W tabeli przedstawiliśmy generatory dla początkowych wartości [math]\displaystyle{ m }[/math]

[math]\displaystyle{ \boldsymbol{m} }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 11 }[/math]	[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ 14 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 16 }[/math]	[math]\displaystyle{ 17 }[/math]	[math]\displaystyle{ 18 }[/math]
[math]\displaystyle{ \boldsymbol{φ(m)} }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ 16 }[/math]	[math]\displaystyle{ 6 }[/math]
generatory	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 2,3 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 3,5 }[/math]	[math]\displaystyle{ - }[/math]	[math]\displaystyle{ 2,5 }[/math]	[math]\displaystyle{ 3,7 }[/math]	[math]\displaystyle{ 2,6,7,8 }[/math]	[math]\displaystyle{ - }[/math]	[math]\displaystyle{ 2,6,7,11 }[/math]	[math]\displaystyle{ 3,5 }[/math]	[math]\displaystyle{ - }[/math]	[math]\displaystyle{ - }[/math]	[math]\displaystyle{ 3,5,6,7,10,11,12,14 }[/math]	[math]\displaystyle{ 5,11 }[/math]

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

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

Zadanie L34
Niech [math]\displaystyle{ g \in \mathbb{Z} }[/math], [math]\displaystyle{ \; k, m \in \mathbb{Z}_+ \; }[/math] i [math]\displaystyle{ \; \gcd (g, m) = 1 }[/math]. Jeżeli liczba [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ m }[/math], to liczby [math]\displaystyle{ g^k }[/math], gdzie [math]\displaystyle{ k }[/math] spełnia warunek [math]\displaystyle{ \gcd (k, \varphi (m)) = 1 }[/math], są generatorami modulo [math]\displaystyle{ m }[/math].

Rozwiązanie

Ponieważ [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ m }[/math], to [math]\displaystyle{ \operatorname{ord}(g, m) = \varphi (m) }[/math], zatem (zobacz L18)

[math]\displaystyle{ \operatorname{ord}(g^k, m) = {\small\frac{\varphi (m)}{\gcd (k, \varphi (m))}} }[/math]

Z założenia [math]\displaystyle{ \gcd (k, \varphi (m)) = 1 }[/math], czyli [math]\displaystyle{ \operatorname{ord}(g^k, m) = \varphi (m) }[/math]. Co należało pokazać.
□

Twierdzenie L35
Jeżeli liczba [math]\displaystyle{ m }[/math] ma generator, to ma ich dokładnie [math]\displaystyle{ \varphi (\varphi (m)) }[/math].

Dowód

Rozważmy zbiór [math]\displaystyle{ S = \{ g^1, g^2, \ldots, g^{\varphi (m)} \} }[/math]. Ponieważ [math]\displaystyle{ \gcd (g, m) = 1 }[/math], to wszystkie elementy zbioru [math]\displaystyle{ S }[/math] są względnie pierwsze z [math]\displaystyle{ m }[/math]. Zauważmy, że wszystkie elementy zbioru [math]\displaystyle{ S }[/math] są różne modulo [math]\displaystyle{ m }[/math] (zobacz L5), zatem zbiór [math]\displaystyle{ S }[/math] zawiera wszystkie liczby względnie pierwsze z [math]\displaystyle{ m }[/math] (rozpatrywane modulo [math]\displaystyle{ m }[/math]).

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

[math]\displaystyle{ \operatorname{ord}(g^k, m) = {\small\frac{\varphi (m)}{\gcd (k, \varphi (m))}} }[/math]

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

Twierdzenie L36
Jeżeli liczba [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ m }[/math], to dla [math]\displaystyle{ m \geqslant 3 }[/math] jest

[math]\displaystyle{ g^{\varphi (m) / 2} \equiv - 1 \!\! \pmod{m} }[/math]

Dowód

Pokażemy, że jeżeli liczba [math]\displaystyle{ m \geqslant 3 }[/math] ma generator, to kongruencja

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

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

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

[math]\displaystyle{ g^{2 k} \equiv 1 \!\! \pmod{m} }[/math]

Przypomnijmy (zobacz H38), że dla [math]\displaystyle{ m \geqslant 3 }[/math] wartości funkcji Eulera [math]\displaystyle{ \varphi (m) }[/math] są liczbami parzystymi. Ponieważ rząd liczby [math]\displaystyle{ g }[/math] modulo [math]\displaystyle{ m }[/math] jest równy [math]\displaystyle{ \varphi (m) }[/math], to [math]\displaystyle{ \varphi (m) \mid 2k }[/math] (zobacz L8 p.1), zatem [math]\displaystyle{ 2 k = s \cdot \varphi (m) }[/math], gdzie [math]\displaystyle{ s }[/math] jest liczbą całkowitą, czyli [math]\displaystyle{ k = s \cdot {\small\frac{\varphi (m)}{2}} }[/math]. W zależności od parzystości liczby [math]\displaystyle{ s }[/math] otrzymujemy

•    dla [math]\displaystyle{ s = 2 t }[/math]

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

•    dla [math]\displaystyle{ s = 2 t + 1 }[/math]

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

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

[math]\displaystyle{ 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]\displaystyle{ m }[/math], bo dla [math]\displaystyle{ m \geqslant 3 }[/math] nie jest możliwa kongruencja

[math]\displaystyle{ 1 \equiv - 1 \!\! \pmod{m} }[/math]

ponieważ [math]\displaystyle{ m \nmid 2 }[/math].

Łącząc powyższe rezultaty, otrzymujemy, że musi być [math]\displaystyle{ g^{\varphi (m) / 2} \equiv - 1 \!\! \pmod{m} }[/math]. Co należało udowodnić.
□

Uwaga L37
Twierdzenie odwrotne nie jest prawdziwe, czyli istnieją liczby [math]\displaystyle{ a }[/math] niebędące generatorami, dla których [math]\displaystyle{ a^{\varphi (m) / 2} \equiv - 1 \!\! \pmod{m} }[/math]. Przykładowo dla modułu [math]\displaystyle{ m = 41 }[/math] mamy [math]\displaystyle{ 3^4 \equiv 3^{20} \equiv - 1 \!\! \pmod{41} }[/math]. Natomiast łatwo pokażemy, że kongruencja

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

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

Twierdzenie L38
Jeżeli liczby [math]\displaystyle{ g_1 }[/math] i [math]\displaystyle{ g_2 }[/math] są generatorami modulo [math]\displaystyle{ m }[/math], to liczba [math]\displaystyle{ a \equiv g_1 g_2 \!\! \pmod{m} }[/math] nie jest generatorem.

Dowód

Policzmy

[math]\displaystyle{ 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]\displaystyle{ a \equiv g_1 g_2 \!\! \pmod{m} }[/math] nie jest generatorem modulo [math]\displaystyle{ m }[/math]. Co należało pokazać.
□

Zadanie L39
Pokazać, że dla [math]\displaystyle{ m = 5 }[/math] i [math]\displaystyle{ m \geqslant 7 }[/math] iloczyn wszystkich generatorów modulo [math]\displaystyle{ m }[/math] przystaje do [math]\displaystyle{ 1 }[/math].

Rozwiązanie

Niech [math]\displaystyle{ g }[/math] będzie generatorem modulo [math]\displaystyle{ m }[/math]. Zauważmy, że dla [math]\displaystyle{ m \geqslant 7 }[/math] liczby [math]\displaystyle{ g }[/math] i [math]\displaystyle{ g^{- 1} }[/math] są zawsze różne modulo [math]\displaystyle{ m }[/math]. Istotnie, gdyby było

[math]\displaystyle{ g \equiv g^{- 1} \!\! \pmod{m} }[/math]

to mielibyśmy

[math]\displaystyle{ g^2 \equiv 1 \!\! \pmod{m} }[/math]

i rząd liczby [math]\displaystyle{ g }[/math] modulo [math]\displaystyle{ m }[/math] byłby nie większy od [math]\displaystyle{ 2 }[/math], ale [math]\displaystyle{ \varphi (m) \gt 2 }[/math] dla [math]\displaystyle{ m \geqslant 7 }[/math] (zobacz H41), czyli liczba [math]\displaystyle{ g }[/math] nie byłaby generatorem wbrew założeniu.

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

[math]\displaystyle{ \prod_i g_i = \prod_k g_k g_{k}^{- 1} \equiv 1 \!\! \pmod{m} }[/math]

Przypadek [math]\displaystyle{ m = 5 }[/math] sprawdzamy bezpośrednio. Co należało pokazać.
□

Twierdzenie L40
Niech [math]\displaystyle{ g, m \in \mathbb{Z} \; }[/math] i [math]\displaystyle{ \; m \geqslant 3 }[/math] oraz [math]\displaystyle{ \gcd (g, m) = 1 }[/math]. Liczba [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ m }[/math] wtedy i tylko wtedy, gdy

[math]\displaystyle{ g^{\tfrac{\varphi (m)}{q}} \not\equiv 1 \!\! \pmod{m} }[/math]

dla każdego dzielnika pierwszego [math]\displaystyle{ q }[/math] liczby [math]\displaystyle{ \varphi (m) }[/math].

Dowód

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

Przypuśćmy, dla uzyskania sprzeczności, że dla pewnego dzielnika pierwszego [math]\displaystyle{ q }[/math] liczby [math]\displaystyle{ \varphi (m) }[/math] jest

[math]\displaystyle{ g^{\tfrac{\varphi (m)}{q}} \equiv 1 \!\! \pmod{m} }[/math]

Zatem

[math]\displaystyle{ \operatorname{ord}(g, m) \leqslant {\small\frac{\varphi (m)}{q}} \lt \varphi (m) }[/math]

Wbrew założeniu, że liczba [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math].

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

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

[math]\displaystyle{ g^h \equiv 1 \!\! \pmod{m} }[/math]

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

[math]\displaystyle{ 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]\displaystyle{ d = 1 \; }[/math] i [math]\displaystyle{ \; h = \varphi (m) }[/math], czyli [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ m }[/math]. Co należało pokazać.
□

Generatory modulo [math]\displaystyle{ \boldsymbol{p} }[/math]

 

Uwaga L41
Przedstawimy poniżej postać twierdzenia L40 w przypadku, gdy moduł [math]\displaystyle{ m }[/math] jest liczbą pierwszą. Oczywiście twierdzenie L40 jest bardziej ogólne, ale znacznie wygodniej jest korzystać ze szczególnej postaci w przypadku, gdy wiemy, że rozpatrywana liczba [math]\displaystyle{ m }[/math] jest liczbą pierwszą.

Twierdzenie L42
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą, [math]\displaystyle{ g \in \mathbb{Z} \; }[/math] i [math]\displaystyle{ \; p \nmid g }[/math]. Liczba [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math] wtedy i tylko wtedy, gdy

[math]\displaystyle{ g^{\tfrac{p - 1}{q}} \not\equiv 1 \!\! \pmod{p} }[/math]

dla każdego dzielnika pierwszego [math]\displaystyle{ q }[/math] liczby [math]\displaystyle{ p - 1 }[/math].

Twierdzenie L43
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Jeżeli liczba [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to [math]\displaystyle{ g }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math].

Dowód

Pierwszy sposób
Z założenia [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], zatem z twierdzenia L36 mamy

[math]\displaystyle{ g^{\tfrac{p - 1}{2}} \equiv - 1 \!\! \pmod{p} }[/math]

I z kryterium Eulera (zobacz J31) wynika natychmiast, że [math]\displaystyle{ g }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math]. Co należało pokazać.

Drugi sposób
Z założenia [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], ale z twierdzenia L42 wiemy, że [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math] wtedy i tylko wtedy, gdy dla wszystkich dzielników pierwszych [math]\displaystyle{ q }[/math] liczby [math]\displaystyle{ p - 1 }[/math] jest

[math]\displaystyle{ g^{\tfrac{p - 1}{q}} \not\equiv 1 \!\! \pmod{p} }[/math]

W przypadku liczb pierwszych nieparzystych liczba [math]\displaystyle{ 2 }[/math] jest zawsze dzielnikiem [math]\displaystyle{ p - 1 }[/math], zatem jeżeli [math]\displaystyle{ g }[/math] jest generatorem, to

[math]\displaystyle{ g^{\tfrac{p - 1}{2}} \not\equiv 1 \!\! \pmod{p} }[/math]

I z kryterium Eulera wynika, że [math]\displaystyle{ g }[/math] nie może być liczbą kwadratową modulo [math]\displaystyle{ p }[/math], czyli [math]\displaystyle{ g }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math]. Co należało pokazać.
□

Twierdzenie L44
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Jeżeli liczba [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math], to [math]\displaystyle{ a }[/math] nie jest generatorem modulo [math]\displaystyle{ p }[/math].

Dowód

Z założenia [math]\displaystyle{ a }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math], zatem z kryterium Eulera (zobacz J31) mamy

[math]\displaystyle{ a^{\tfrac{p - 1}{2}} \equiv 1 \!\! \pmod{p} }[/math]

Zatem [math]\displaystyle{ \operatorname{ord}(a, p) \leqslant {\small\frac{p - 1}{2}} \lt p - 1 }[/math], czyli [math]\displaystyle{ a }[/math] nie jest generatorem modulo [math]\displaystyle{ p }[/math].
□

Uwaga L45
Ponieważ liczba generatorów modulo liczba pierwsza [math]\displaystyle{ p }[/math] jest równa [math]\displaystyle{ \varphi (p - 1) }[/math], to z zadań H49, H50 wynika, że

•    [math]\displaystyle{ \varphi (p - 1) = {\small\frac{p - 1}{2}} }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ p - 1 = 2^k }[/math]

•    [math]\displaystyle{ \varphi (p - 1) = {\small\frac{p - 1}{2}} - 1 }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ p - 1 = 2 q }[/math], gdzie [math]\displaystyle{ q \geqslant 3 }[/math] jest liczbą pierwszą

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

Drugi punkt odpowiada sytuacji, gdy wszystkie liczby niekwadratowe modulo [math]\displaystyle{ p }[/math], poza dokładnie jedną, są generatorami modulo [math]\displaystyle{ p }[/math]. Liczba pierwsza [math]\displaystyle{ p }[/math] musi być postaci [math]\displaystyle{ p = 2 q + 1 }[/math], gdzie [math]\displaystyle{ q \geqslant 3 }[/math] jest liczbą pierwszą. Łatwo możemy stwierdzić, że liczba [math]\displaystyle{ - 1 }[/math] jest jedyną liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], która w tym przypadku nie jest generatorem modulo [math]\displaystyle{ p }[/math]. Z kryterium Eulera (zobacz J31) otrzymujemy

[math]\displaystyle{ (- 1)^{\tfrac{p - 1}{2}} = (- 1)^q = - 1 }[/math]

czyli [math]\displaystyle{ - 1 }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math].

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

Zadanie L46
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą postaci [math]\displaystyle{ 4 k + 3 }[/math]. Pokazać, że jeżeli [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to [math]\displaystyle{ - g }[/math] nie jest generatorem modulo [math]\displaystyle{ p }[/math].

Rozwiązanie

Policzmy

[math]\displaystyle{ (- g)^{\varphi (p) / 2} = (- g)^{\tfrac{p - 1}{2}} }[/math]

[math]\displaystyle{ \: = (- 1)^{\tfrac{p - 1}{2}} g^{\tfrac{p - 1}{2}} }[/math]

[math]\displaystyle{ \: \equiv (- 1)^{\tfrac{4 k + 2}{2}} \cdot (- 1) }[/math]

[math]\displaystyle{ \: \equiv - (- 1)^{2 k + 1} }[/math]

[math]\displaystyle{ \: \equiv + 1 \!\! \pmod{p} }[/math]

Zatem [math]\displaystyle{ - g }[/math] nie może być generatorem modulo [math]\displaystyle{ p }[/math], dla liczby pierwszej [math]\displaystyle{ p }[/math] postaci [math]\displaystyle{ 4 k + 3 }[/math]. Co należało pokazać.
□

Zadanie L47
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą postaci [math]\displaystyle{ 4 k + 1 }[/math]. Pokazać, że jeżeli liczba [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to liczba [math]\displaystyle{ - g }[/math] też jest generatorem modulo [math]\displaystyle{ p }[/math].

Rozwiązanie

Niech [math]\displaystyle{ h = \operatorname{ord}(- g, p) }[/math]. Z definicji mamy [math]\displaystyle{ (- g)^h \equiv 1 \pmod{p} }[/math]. Podnosząc obie strony kongruencji do kwadratu, otrzymujemy

[math]\displaystyle{ g^{2 h} \equiv 1 \!\! \pmod{p} }[/math]

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

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

Ponownie rząd liczby [math]\displaystyle{ g }[/math] musi dzielić [math]\displaystyle{ h }[/math], czyli [math]\displaystyle{ (p - 1) \mid h }[/math].

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

Zadanie L48
Niech [math]\displaystyle{ p, q \in \mathbb{P} }[/math], gdzie [math]\displaystyle{ q \geqslant 3 }[/math]. Pokazać, że jeżeli [math]\displaystyle{ p = 2 q + 1 \; }[/math] i [math]\displaystyle{ \; g \not\equiv - 1 \!\! \pmod{p} }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], to [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math].

Rozwiązanie

Zauważmy, że liczba [math]\displaystyle{ p - 1 }[/math] ma tylko dwa dzielniki pierwsze. Ponieważ z założenia [math]\displaystyle{ g }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], to (zobacz J31)

[math]\displaystyle{ g^{\tfrac{p - 1}{2}} \equiv - 1 \!\! \pmod{p} }[/math]

Mamy też

[math]\displaystyle{ g^{\tfrac{p - 1}{q}} = g^2 \not\equiv 1 \!\! \pmod{p} }[/math]

Istotnie, gdyby prawdziwa była kongruencja

[math]\displaystyle{ g^2 \equiv 1 \!\! \pmod{p} }[/math]

to mielibyśmy [math]\displaystyle{ g \equiv - 1 \!\! \pmod{p} \; }[/math] lub [math]\displaystyle{ \; g \equiv 1 \!\! \pmod{p} }[/math]. Pierwszy przypadek nie jest możliwy ze względu na uczynione założenie, a w drugim przypadku [math]\displaystyle{ g }[/math] byłaby liczbą kwadratową modulo [math]\displaystyle{ p }[/math], bo (zobacz J42 p.2)

[math]\displaystyle{ \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, zatem [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math]. Co należało pokazać.
□

Zadanie L49
Niech [math]\displaystyle{ p \in \mathbb{P} }[/math]. Pokazać, że jeżeli liczba [math]\displaystyle{ p - 1 }[/math] ma dzielnik pierwszy nieparzysty [math]\displaystyle{ q }[/math], to istnieje liczba całkowita [math]\displaystyle{ a }[/math], która jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math] i nie jest generatorem modulo [math]\displaystyle{ p }[/math].

Rozwiązanie

Wiemy, że istnieje [math]\displaystyle{ {\small\frac{p - 1}{2}} }[/math] liczb niekwadratowych modulo [math]\displaystyle{ p }[/math] (zobacz J30). Oznaczmy przez [math]\displaystyle{ b }[/math] dowolną z tych liczb, czyli

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

Niech teraz [math]\displaystyle{ a = b^q }[/math]. Liczba [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], bo

[math]\displaystyle{ \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]\displaystyle{ a^{\tfrac{p - 1}{q}} = (b^q)^{\tfrac{p - 1}{q}} = b^{p - 1} \equiv 1 \!\! \pmod{p} }[/math]

Ponieważ [math]\displaystyle{ \operatorname{ord}(a, p) \leqslant {\small\frac{p - 1}{q}} \lt p - 1 }[/math], to [math]\displaystyle{ a }[/math] nie jest generatorem modulo [math]\displaystyle{ p }[/math]. Co należało pokazać.
□

Zadanie L50
Pokazać, że istnieje nieskończenie wiele liczb pierwszych, dla których liczba [math]\displaystyle{ 2 }[/math] nie jest generatorem. Wskazówka: rozważyć liczby pierwsze postaci [math]\displaystyle{ p = 2^n k + 1 }[/math].

Rozwiązanie

Dla [math]\displaystyle{ n \geqslant 3 }[/math] liczbę [math]\displaystyle{ p }[/math] możemy zapisać w postaci [math]\displaystyle{ p = 8 k \cdot 2^{n - 3} + 1 }[/math], zatem [math]\displaystyle{ p \equiv 1 \!\! \pmod{8} }[/math] i liczba [math]\displaystyle{ 2 }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math] (zobacz J34 p.7), czyli nie jest generatorem modulo [math]\displaystyle{ p }[/math]. Ponieważ liczb pierwszych postaci [math]\displaystyle{ p = 2^n k + 1 }[/math] istnieje nieskończenie wiele (zobacz L27 lub C27), to możemy stwierdzić, że istnieje nieskończenie wiele liczb pierwszych, dla których liczba [math]\displaystyle{ 2 }[/math] nie jest generatorem. Co należało pokazać.
□

Zadanie L51
Pokazać, że jeżeli liczby [math]\displaystyle{ q \geqslant 7 }[/math] oraz [math]\displaystyle{ p = 4 q + 1 }[/math] są liczbami pierwszymi, to liczby [math]\displaystyle{ 2 \: }[/math] i [math]\displaystyle{ \: 3 }[/math] są generatorami modulo [math]\displaystyle{ p }[/math].

Rozwiązanie

Liczby pierwsze [math]\displaystyle{ p = 4 q + 1 }[/math] tworzą ciąg [math]\displaystyle{ 13, 29, 53, 149, 173, 269, 293, 317, 389, 509, 557, 653, 773, 797, \ldots }[/math]

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

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

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

Widzimy, że liczby [math]\displaystyle{ 2 \: }[/math] i [math]\displaystyle{ \: 3 }[/math] są liczbami niekwadratowymi modulo [math]\displaystyle{ p }[/math], bo odpowiednio [math]\displaystyle{ p \equiv 5 \!\! \pmod{8} \; }[/math] i [math]\displaystyle{ \; p \equiv 5 \!\! \pmod{12} }[/math] (zobacz J42 p.7 i J47).

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

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

Z kryterium Eulera (zobacz J31) mamy

[math]\displaystyle{ a^{(p - 1) / 2} = a^{2 q} \equiv - 1 \!\! \pmod{p} }[/math]

Widzimy, że nie może być [math]\displaystyle{ a^q \equiv 1 \!\! \pmod{p} }[/math], bo wtedy byłoby [math]\displaystyle{ a^{2 q} \equiv 1 \!\! \pmod{p} }[/math]. Zatem musi być [math]\displaystyle{ a^{4 q} \equiv 1 \!\! \pmod{p} }[/math], czyli rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p }[/math] jest równy [math]\displaystyle{ p - 1 }[/math] i [math]\displaystyle{ a }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math].
□

Zadanie L52
Znaleźć rozwiązania układu kongruencji

[math]\displaystyle{ \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]\displaystyle{ 2 }[/math] jest generatorem modulo [math]\displaystyle{ 13 }[/math].

Rozwiązanie

Dokonujemy podstawień: [math]\displaystyle{ 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]

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

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

Korzystając z twierdzenia L23, dostajemy

[math]\displaystyle{ \left\{ \begin{array}{rl} 7 x + 5 z \equiv 2 & \pmod{12} \\ 5 x + 6 z \equiv 8 & \pmod{12} \\ \end{array} \right. }[/math]

Mnożąc pierwszą kongruencję przez [math]\displaystyle{ 5 }[/math], drugą przez [math]\displaystyle{ 7 }[/math], otrzymujemy

[math]\displaystyle{ \left\{ \begin{array}{rl} 35 x + 25 z \equiv 10 & \pmod{12} \\ 35 x + 42 z \equiv 56 & \pmod{12} \\ \end{array} \right. }[/math]

[math]\displaystyle{ \left\{ \begin{array}{rl} - x + z \equiv 10 & \pmod{12} \\ - x + 6 z \equiv 8 & \pmod{12} \\ \end{array} \right. }[/math]

Odejmując kongruencje od siebie, mamy

[math]\displaystyle{ \begin{array}{rl} 5 z \equiv - 2 & \pmod{12} \\ 25 z \equiv - 10 & \pmod{12} \\ z \equiv 2 & \pmod{12} \\ \end{array} }[/math]

Czyli [math]\displaystyle{ y \equiv 2^2 \equiv 4 \!\! \pmod{13} }[/math]. Podstawiając [math]\displaystyle{ z \equiv 2 \!\! \pmod{12} }[/math] do pierwszej kongruencji, dostajemy [math]\displaystyle{ x \equiv 4 \!\! \pmod{12} }[/math]. Zatem rozwiązaniem układu kongruencji są liczby [math]\displaystyle{ x \equiv 4 \!\! \pmod{12} }[/math] oraz [math]\displaystyle{ y \equiv 4 \!\! \pmod{13} }[/math].
□

Liczby, które nie mają generatora

 

Uwaga L53
Rozważymy dwa przypadki: gdy liczba pierwsza nieparzysta [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ m }[/math] i gdy liczba pierwsza nieparzysta [math]\displaystyle{ p }[/math] nie dzieli [math]\displaystyle{ m }[/math]. W pierwszym przypadku [math]\displaystyle{ m }[/math] jest postaci [math]\displaystyle{ m = r p^k }[/math], a w drugim [math]\displaystyle{ m = 2^k }[/math].

Twierdzenie L54
Niech [math]\displaystyle{ k, m \in \mathbb{Z}_+ }[/math] i liczba [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Jeżeli [math]\displaystyle{ m = r p^k }[/math], gdzie [math]\displaystyle{ p \nmid r \; }[/math] i [math]\displaystyle{ \; r \geqslant 3 }[/math], to nie istnieją generatory modulo [math]\displaystyle{ m }[/math].

Dowód

Niech [math]\displaystyle{ a }[/math] będzie dowolną liczbą całkowitą i [math]\displaystyle{ \gcd (a, m) = 1 }[/math]. Ponieważ [math]\displaystyle{ \varphi (r) \; }[/math] i [math]\displaystyle{ \; \varphi (p^k) }[/math] są liczbami parzystymi (zobacz H38), to z twierdzenia Eulera otrzymujemy

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

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

Ponieważ liczby [math]\displaystyle{ r \; }[/math] i [math]\displaystyle{ \; p^k }[/math] są względnie pierwsze, zatem (zobacz J1)

[math]\displaystyle{ a^{\varphi (m) / 2} \equiv 1 \!\! \pmod{r p^k} }[/math]

Co oznacza, że nie istnieje liczba, której rząd modulo [math]\displaystyle{ m = r p^k }[/math] wynosiłby [math]\displaystyle{ \varphi (m) }[/math], czyli nie istnieją generatory modulo [math]\displaystyle{ m }[/math].
□

Wniosek L55
Z twierdzenia L54 wynika natychmiast, że poza potęgami liczby [math]\displaystyle{ 2 }[/math] jedynie liczby postaci [math]\displaystyle{ p^k }[/math] i [math]\displaystyle{ 2 p^k }[/math], gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą, mogą mieć generatory. Problem istnienia generatorów dla liczb postaci [math]\displaystyle{ 2^k }[/math] rozstrzyga następne twierdzenie.

Twierdzenie L56
Nie istnieją generatory modulo [math]\displaystyle{ 2^k }[/math] dla [math]\displaystyle{ k \geqslant 3 }[/math]

Dowód

Udowodnimy (indukcja matematyczna), że dla dowolnej liczby nieparzystej [math]\displaystyle{ a }[/math] i [math]\displaystyle{ k \geqslant 3 }[/math] prawdziwa jest kongruencja

[math]\displaystyle{ a^{2^{\large {k - 2}}} \equiv 1 \!\! \pmod{2^k} \qquad \qquad (1) }[/math]

Wzór jest prawdziwy dla [math]\displaystyle{ k = 3 }[/math], bo dla dowolnej liczby nieparzystej [math]\displaystyle{ a }[/math] prawdziwa jest kongruencja

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

Dla dowodu wystarczy rozważyć modulo [math]\displaystyle{ 8 }[/math] liczby nieparzyste postaci [math]\displaystyle{ 4 j + 1 }[/math] i [math]\displaystyle{ 4 j + 3 }[/math].

Załóżmy, że wzór [math]\displaystyle{ (1) }[/math] jest prawdziwy dla pewnego [math]\displaystyle{ k \geqslant 3 }[/math]. Z uczynionego założenia wynika, że istnieje taka liczba całkowita [math]\displaystyle{ t }[/math], że

[math]\displaystyle{ a^{2^{\large {k - 2}}} = 1 + t \cdot 2^k }[/math]

Podnosząc obie strony powyższej równości do kwadratu, z łatwością pokazujemy, że dowodzony wzór jest prawdziwy dla [math]\displaystyle{ k + 1 }[/math]

[math]\displaystyle{ 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]\displaystyle{ (1) }[/math]. Ze wzoru [math]\displaystyle{ (1) }[/math] wynika natychmiast, że [math]\displaystyle{ \operatorname{ord}(a, 2^k) \leqslant 2^{k - 2} }[/math], ale [math]\displaystyle{ \varphi (2^k) = 2^{k - 1} }[/math], zatem rząd liczby nieparzystej [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ 2^k }[/math] nigdy nie będzie równy [math]\displaystyle{ \varphi (2^k) }[/math]. Co należało pokazać.
□

Liczba pierwsza ma generator

 

Uwaga L57
Zauważmy, że istnienie generatora dla liczby pierwszej [math]\displaystyle{ p }[/math] jest prostym wnioskiem z twierdzenia L21. Ponieważ [math]\displaystyle{ h = p - 1 }[/math] dzieli liczbę [math]\displaystyle{ p - 1 }[/math], to istnieje [math]\displaystyle{ \varphi (p - 1) }[/math] liczb, których rząd modulo [math]\displaystyle{ p }[/math] jest równy [math]\displaystyle{ h = p - 1 = \varphi (p) }[/math], czyli generatorów modulo [math]\displaystyle{ p }[/math]. Dowód twierdzenia L21 jest dowodem niekonstruktywnym – nie pokazaliśmy jawnie sposobu otrzymania liczby, która byłaby generatorem modulo [math]\displaystyle{ p }[/math]. W kolejnym twierdzeniu przedstawimy dowód konstruktywny.

Twierdzenie L58 (Carl Friedrich Gauss, 1801)
Każda liczba pierwsza ma generator.

Dowód

Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą. Liczba [math]\displaystyle{ p = 2 }[/math] ma generator [math]\displaystyle{ g = 1 }[/math], bo [math]\displaystyle{ \varphi (2) = 1 }[/math]. Zatem możemy założyć, że [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą. Niech liczba [math]\displaystyle{ p - 1 }[/math] ma następujący rozkład na czynniki pierwsze

[math]\displaystyle{ p - 1 = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s }[/math]

Z twierdzenia Lagrange'a (zobacz J14) wynika, że każda z kongruencji

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

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

[math]\displaystyle{ (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 wypisanych wyżej kongruencji istnieje taka liczba [math]\displaystyle{ w_i \not\equiv 0 \!\! \pmod{p} }[/math], która nie jest rozwiązaniem powyższej kongruencji.

Zdefiniujmy liczbę [math]\displaystyle{ a_i }[/math] następująco

[math]\displaystyle{ a_i = (w_i)^{(p - 1) / q_i^{\large \alpha_i}} }[/math]

Zauważmy, że

[math]\displaystyle{ (a_i)^{q_i^{\large \alpha_i}} = (w_i)^{p - 1} \equiv 1 \!\! \pmod{p} }[/math]

oraz

[math]\displaystyle{ (a_i)^{q_i^{\large \alpha_i - 1}} = (w_i)^{\tfrac{p - 1}{q_i}} \not\equiv 1 \!\! \pmod{p} }[/math]

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

[math]\displaystyle{ \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]\displaystyle{ w_i }[/math] wybraliśmy tak, aby [math]\displaystyle{ \gcd (w_i, p) = 1 }[/math], czyli [math]\displaystyle{ \gcd (a_i, p) = 1 }[/math]. Ponieważ spełnione są założenia twierdzenia L15, to

[math]\displaystyle{ \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]\displaystyle{ a_1 \cdot \ldots \cdot a_s }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math].
□

Kwadrat liczby pierwszej ma generator

 

Twierdzenie L59
Niech [math]\displaystyle{ p \in \mathbb{P} }[/math], [math]\displaystyle{ a \in \mathbb{Z} }[/math] i [math]\displaystyle{ \gcd (a, p) = 1 }[/math]. Jeżeli [math]\displaystyle{ h = \operatorname{ord}(a, p) }[/math], to

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

Dowód

1. Przypadek, gdy [math]\displaystyle{ \boldsymbol{a^h \equiv 1 \!\! \pmod{p^2}} }[/math]

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

2. Przypadek, gdy [math]\displaystyle{ \boldsymbol{a^h \not\equiv 1 \!\! \pmod{p^2}} }[/math]

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

Z definicji liczby [math]\displaystyle{ h }[/math] mamy

[math]\displaystyle{ a^h \equiv 1 \!\! \pmod{p} }[/math]

Z powyższej kongruencji oraz twierdzenia L97 wynika, że

[math]\displaystyle{ a^{h p} \equiv 1 \!\! \pmod{p^2} }[/math]

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

[math]\displaystyle{ 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]\displaystyle{ f = h }[/math], bo mielibyśmy [math]\displaystyle{ a^h \equiv 1 \!\! \pmod{p^2} }[/math], wbrew założeniu. Zatem musi być [math]\displaystyle{ f = h p }[/math]. Co należało pokazać.
□

Twierdzenie L60
Niech [math]\displaystyle{ h }[/math] będzie rzędem liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p }[/math]. Rząd przynajmniej jednej z liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ a + p }[/math] modulo [math]\displaystyle{ p^2 }[/math] jest równy [math]\displaystyle{ h p }[/math].

Dowód

Z założenia [math]\displaystyle{ \operatorname{ord}(a, p) = \operatorname{ord}(a + p, p) = h }[/math] (zobacz L14). Z twierdzenia L59 wiemy, że rząd każdej z liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ a + p }[/math] modulo [math]\displaystyle{ p^2 }[/math] może być równy [math]\displaystyle{ h }[/math] lub [math]\displaystyle{ h p }[/math]. Udowodnimy, że rzędy liczb [math]\displaystyle{ a }[/math] i [math]\displaystyle{ a + p }[/math] modulo [math]\displaystyle{ p^2 }[/math] nie mogą być jednocześnie równe [math]\displaystyle{ h }[/math], zatem rząd przynajmniej jednej z nich jest równy [math]\displaystyle{ h p }[/math].

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

[math]\displaystyle{ 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]\displaystyle{ (a + p)^h = \sum_{i = 0}^h \binom{h}{i} a^{h - i} p^i }[/math]

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

Zatem modulo [math]\displaystyle{ p^2 }[/math] jest

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

[math]\displaystyle{ \;\;\: \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]\displaystyle{ \;\;\: \equiv h \cdot a^{h - 1} p \!\! \pmod{p^2} }[/math]

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

Przykład L61
Niech [math]\displaystyle{ p = 7 }[/math]. Dla [math]\displaystyle{ a = 2, 3, 4, 5, 6 }[/math] mamy odpowiednio [math]\displaystyle{ h = \operatorname{ord}(a, p) = 3, 6, 3, 6, 2 }[/math]. Łatwo sprawdzamy, że dla tych liczb jest

[math]\displaystyle{ \operatorname{ord}(a, p^2) = \operatorname{ord}(a + p, p^2) = h p }[/math]

Twierdzenie L62
Jeżeli liczba [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to [math]\displaystyle{ g }[/math] lub [math]\displaystyle{ g + p }[/math] jest generatorem modulo [math]\displaystyle{ p^2 }[/math].

Dowód

Jeżeli [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to rząd liczby [math]\displaystyle{ g }[/math] modulo [math]\displaystyle{ p }[/math] jest równy [math]\displaystyle{ \varphi (p) = p - 1 }[/math]. Z twierdzenia L60 otrzymujemy natychmiast, że rząd przynajmniej jednej z liczb [math]\displaystyle{ g }[/math] lub [math]\displaystyle{ g + p }[/math] jest równy [math]\displaystyle{ (p - 1) p = \varphi (p^2) }[/math], czyli jedna z tych liczb jest generatorem modulo [math]\displaystyle{ p^2 }[/math]. Co należało pokazać.
□

Liczba [math]\displaystyle{ \boldsymbol{p^n} }[/math] ma generator ([math]\displaystyle{ \boldsymbol{p \geqslant 3} }[/math])

 

Twierdzenie L63
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą i [math]\displaystyle{ n \geqslant 2 }[/math]. Jeżeli [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p^n }[/math], to jest generatorem modulo [math]\displaystyle{ p^{n + 1} }[/math].

Dowód

Niech [math]\displaystyle{ f = \operatorname{ord}(g, p^{n + 1}) }[/math]. Z założenia [math]\displaystyle{ h = \operatorname{ord}(g, p^n) = \varphi (p^n) }[/math].

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

Z zadania L9 mamy [math]\displaystyle{ f \mid \varphi (p^{n + 1}) }[/math], czyli [math]\displaystyle{ k \varphi (p^n) \mid \varphi (p^{n + 1}) }[/math], zatem (zobacz H36) [math]\displaystyle{ k \varphi (p^n) \mid p \varphi (p^n) }[/math]. Wynika stąd, że [math]\displaystyle{ k \mid p }[/math], zatem [math]\displaystyle{ k = 1 }[/math] lub [math]\displaystyle{ k = p }[/math].

Jeżeli [math]\displaystyle{ k = p }[/math], to [math]\displaystyle{ f = p \varphi (p^n) = \varphi (p^{n + 1}) }[/math] i twierdzenie zostało dowiedzione.

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

[math]\displaystyle{ g^{\varphi (p^{\large n})} \not\equiv 1 \!\! \pmod{p^{n + 1}} }[/math]

Z twierdzenia Eulera mamy

[math]\displaystyle{ g^{\varphi (p^{\large n - 1})} \equiv 1 \!\! \pmod{p^{n - 1}} }[/math]

Zatem istnieje taka liczba całkowita [math]\displaystyle{ s }[/math], że

[math]\displaystyle{ g^{\varphi (p^{\large n - 1})} = 1 + s p^{n - 1} }[/math]

Gdyby [math]\displaystyle{ p \mid s }[/math], to modulo [math]\displaystyle{ p^n }[/math] mielibyśmy

[math]\displaystyle{ g^{\varphi (p^{\large n - 1})} \equiv 1 \!\! \pmod{p^n} }[/math]

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

Korzystając ze wzoru dwumianowego, dostajemy

[math]\displaystyle{ g^{\varphi (p^{\large n})} = g^{p \varphi (p^{\large n - 1})} }[/math]

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

[math]\displaystyle{ \quad \: = (1 + s p^{n - 1})^p = }[/math]

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

[math]\displaystyle{ \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]\displaystyle{ \quad \: \not\equiv 1 \!\! \pmod{p^{n + 1}} }[/math]

Wystarczy zauważyć, że w przedostatniej linii trzeci i czwarty wyraz są podzielne przez [math]\displaystyle{ p^{n + 1} }[/math], co wynika z prostych oszacowań

•    dla [math]\displaystyle{ \; n \geqslant 2 \; }[/math] jest [math]\displaystyle{ \; 1 + 2 (n - 1) \geqslant n + 1 }[/math]

•    dla [math]\displaystyle{ \; n \geqslant 2 \; }[/math] oraz [math]\displaystyle{ \; i \geqslant 3 \; }[/math] jest [math]\displaystyle{ \; i(n - 1) = n - 1 + (i - 1)(n - 1) \geqslant n - 1 + 2 \cdot 1 = n + 1 }[/math]

Co należało pokazać.
□

Liczba [math]\displaystyle{ \boldsymbol{2 p^n} }[/math] ma generator ([math]\displaystyle{ \boldsymbol{p \geqslant 3} }[/math])

 

Twierdzenie L64
Każda liczba [math]\displaystyle{ 2 p^n }[/math] ma generator, gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ n \geqslant 1 }[/math].

Dowód

Niech [math]\displaystyle{ g }[/math] będzie generatorem modulo [math]\displaystyle{ p^n }[/math]. Nie zmniejszając ogólności, możemy założyć, że [math]\displaystyle{ g }[/math] jest liczbą nieparzystą (gdyby było inaczej, to rozpatrywalibyśmy liczbę [math]\displaystyle{ g + p^n }[/math], która też jest generatorem modulo [math]\displaystyle{ p^n }[/math]). Ponieważ liczby [math]\displaystyle{ g \, }[/math] i [math]\displaystyle{ \, p^n }[/math] są nieparzyste i [math]\displaystyle{ \operatorname{ord}(g, p^n) = \varphi (p^n) }[/math], to [math]\displaystyle{ \operatorname{ord}(g, 2 p^n) = \varphi (p^n) = \varphi (2 p^n) }[/math] (zobacz L17), czyli [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ 2 p^n }[/math].

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

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

[math]\displaystyle{ \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]\displaystyle{ \operatorname{ord}(g, 2 p^n) = \varphi (2 p^n) }[/math], czyli [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ 2 p^n }[/math]. Co należało pokazać.
□

Najmniejsze dodatnie generatory modulo [math]\displaystyle{ \boldsymbol{p} }[/math] i modulo [math]\displaystyle{ \boldsymbol{p^2} }[/math]

 

Uwaga L65
Z twierdzenia L43 wiemy, że każdy generator [math]\displaystyle{ g }[/math] modulo [math]\displaystyle{ p }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math]. Ale nie każda liczba niekwadratowa modulo [math]\displaystyle{ p }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math] (zobacz L49). Wynika stąd, że najmniejszy dodatni generator [math]\displaystyle{ \mathbb{g} (p) }[/math] modulo [math]\displaystyle{ p }[/math] nie może być mniejszy od najmniejszej dodatniej liczby niekwadratowej [math]\displaystyle{ \mathbb{n} (p) }[/math] modulo [math]\displaystyle{ p }[/math], czyli [math]\displaystyle{ \mathbb{g} (p) \geqslant \mathbb{n} (p) }[/math].

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

[math]\displaystyle{ \boldsymbol{p} }[/math]	[math]\displaystyle{ 41 }[/math]	[math]\displaystyle{ 43 }[/math]	[math]\displaystyle{ 103 }[/math]	[math]\displaystyle{ 109 }[/math]	[math]\displaystyle{ 151 }[/math]	[math]\displaystyle{ 157 }[/math]	[math]\displaystyle{ 191 }[/math]	[math]\displaystyle{ 229 }[/math]	[math]\displaystyle{ 251 }[/math]	[math]\displaystyle{ 271 }[/math]	[math]\displaystyle{ 277 }[/math]	[math]\displaystyle{ 283 }[/math]	[math]\displaystyle{ 307 }[/math]	[math]\displaystyle{ 311 }[/math]	[math]\displaystyle{ 313 }[/math]	[math]\displaystyle{ 331 }[/math]	[math]\displaystyle{ 337 }[/math]	[math]\displaystyle{ 367 }[/math]	[math]\displaystyle{ 397 }[/math]	[math]\displaystyle{ 409 }[/math]	[math]\displaystyle{ 439 }[/math]	[math]\displaystyle{ 457 }[/math]	[math]\displaystyle{ 499 }[/math]
[math]\displaystyle{ \boldsymbol{\mathbb{n} (p)} }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 11 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 2 }[/math]
[math]\displaystyle{ \boldsymbol{\mathbb{g} (p)} }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 19 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 17 }[/math]	[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ 7 }[/math]

Ponieważ [math]\displaystyle{ \mathbb{g} (p) \geqslant \mathbb{n} (p) }[/math], to z twierdzenia K18 otrzymujemy natychmiast, że istnieje niekończenie wiele liczb pierwszych [math]\displaystyle{ p }[/math] takich, że najmniejszy generator modulo [math]\displaystyle{ p }[/math] jest większy od [math]\displaystyle{ {\small\frac{\log p}{2 L \log 2}} }[/math], gdzie [math]\displaystyle{ L }[/math] jest stałą Linnika (zobacz C30). Zobacz też K16 i K17.

Liczby [math]\displaystyle{ \mathbb{g} (p) }[/math] są bardzo małe, podobnie jak najmniejsze dodatnie liczby niekwadratowe [math]\displaystyle{ \mathbb{n} (p) }[/math]. Przypuszczamy, że istnieje skończona granica

[math]\displaystyle{ \lim_{x \rightarrow \infty} {\small\frac{1}{\pi (x)}} \sum_{p \leqslant x} \mathbb{g} (p) = 4.9264 \ldots }[/math]

gdzie [math]\displaystyle{ p }[/math] są nieparzystymi liczbami pierwszymi.

Oszacowania [math]\displaystyle{ \mathbb{g} (p) }[/math]:

•    oszacowanie [math]\displaystyle{ \mathbb{g} (p) \lt \sqrt{p} - 2 }[/math] jest prawdziwe dla [math]\displaystyle{ 409 \lt p \lt 2.5 \cdot 10^{15} }[/math] i dla [math]\displaystyle{ p \gt 3.67 \cdot 10^{71} }[/math]

•    oszacowanie [math]\displaystyle{ \mathbb{g} (p) \lt \sqrt{p} }[/math] jest prawdziwe dla [math]\displaystyle{ p \gt 10^{56} }[/math]

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

Twierdzenie L66
Niech [math]\displaystyle{ a }[/math] będzie generatorem modulo [math]\displaystyle{ p }[/math]. Prawdziwe są następujące stwierdzenia

•    rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p^2 }[/math] jest równy [math]\displaystyle{ p - 1 }[/math] lub [math]\displaystyle{ p(p - 1) }[/math]

•    [math]\displaystyle{ a }[/math] jest generatorem modulo [math]\displaystyle{ p^2 }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ a^{p - 1} \not\equiv 1 \!\! \pmod{p^2} }[/math]

•    jeżeli [math]\displaystyle{ 1 \lt a, b \lt p \; }[/math] i [math]\displaystyle{ \; b \, }[/math] jest elementem odwrotnym liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p }[/math], to co najmniej jedna z liczb [math]\displaystyle{ a, b }[/math] jest generatorem modulo [math]\displaystyle{ p^2 }[/math]

•    jeżeli [math]\displaystyle{ \mathbb{g} (p^2) }[/math] jest najmniejszym dodatnim generatorem modulo [math]\displaystyle{ p^2 }[/math], to prawdziwe jest oszacowanie [math]\displaystyle{ \mathbb{g} (p^2) \lt p }[/math]

Dowód

Punkt 1.

Niech [math]\displaystyle{ f = \operatorname{ord}(a, p^2) }[/math]. Z definicji rzędu liczby

[math]\displaystyle{ a^f \equiv 1 \!\! \pmod{p^2} }[/math]

Zatem

[math]\displaystyle{ a^f \equiv 1 \!\! \pmod{p} }[/math]

Ponieważ [math]\displaystyle{ a }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to [math]\displaystyle{ (p - 1) \mid f }[/math], czyli [math]\displaystyle{ f = s (p - 1) }[/math]. Z zadania L9 wiemy, że [math]\displaystyle{ s(p - 1) \mid p (p - 1) }[/math], zatem [math]\displaystyle{ s \mid p }[/math] i otrzymujemy [math]\displaystyle{ s = 1 }[/math] lub [math]\displaystyle{ s = p }[/math].

Wynika stąd, że jeżeli [math]\displaystyle{ a }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to rząd liczby [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ p^2 }[/math] jest równy [math]\displaystyle{ p - 1 }[/math] lub [math]\displaystyle{ p(p - 1) }[/math].

Punkt 2.

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

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

[math]\displaystyle{ \operatorname{ord}(a, p^2) \leqslant p - 1 \lt p (p - 1) = \varphi (p^2) }[/math]

Wbrew założeniu, że [math]\displaystyle{ a }[/math] jest generatorem modulo [math]\displaystyle{ p^2 }[/math].

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

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

Punkt 3.

W pracy 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 Margaret Maxfield.

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

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

[math]\displaystyle{ b \equiv a^{h - 1} \!\! \pmod{p} }[/math]

Zatem dla pewnej liczby całkowitej [math]\displaystyle{ k }[/math] jest

[math]\displaystyle{ b = a^{h - 1} + k p }[/math]

Przypuśćmy, dla uzyskania sprzeczności, że [math]\displaystyle{ p \mid k }[/math]. Dostajemy

[math]\displaystyle{ b \equiv a^{h - 1} \!\! \pmod{p^2} }[/math]

[math]\displaystyle{ a b \equiv a^h \equiv 1 \!\! \pmod{p^2} }[/math]

Ale z założenia [math]\displaystyle{ 1 \lt a, b \lt p }[/math], zatem [math]\displaystyle{ 0 \lt a b - 1 \lt p^2 - 1 \lt p^2 }[/math], czyli [math]\displaystyle{ p^2 \nmid (a b - 1) }[/math]. Wynika stąd, że uczynione przypuszczenie jest nieprawdziwe i [math]\displaystyle{ p \nmid k }[/math].

Zgodnie z punktem 2. pozostaje pokazać, że [math]\displaystyle{ b^h \not\equiv 1 \!\! \pmod{p^2} }[/math]. Mamy

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

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

[math]\displaystyle{ \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]\displaystyle{ \quad \: \equiv (a^h)^{h - 1} + h a^{(h - 1)^{\large 2}} \cdot k p \!\! \pmod{p^2} }[/math]

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

[math]\displaystyle{ \quad \: \not\equiv 1 \!\! \pmod{p^2} }[/math]

gdzie uwzględniliśmy, że

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

Zadanie L67
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Pokazać, że jeżeli liczba [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p^2 }[/math], to [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math].

Rozwiązanie

Pierwszy sposób
Przypuśćmy, w celu otrzymania sprzeczności, że [math]\displaystyle{ g }[/math] nie jest generatorem modulo [math]\displaystyle{ p }[/math]. Zatem istnieje liczba [math]\displaystyle{ r \in \mathbb{Z}_+ }[/math] i [math]\displaystyle{ r \lt p - 1 }[/math] taka, że

[math]\displaystyle{ g^r \equiv 1 \!\! \pmod{p} }[/math]

Z twierdzenia L97 dostajemy

[math]\displaystyle{ g^{rp} \equiv 1 \!\! \pmod{p^2} }[/math]

Ale [math]\displaystyle{ r p \lt (p - 1) p = \varphi (p^2) }[/math], wbrew założeniu, że [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p^2 }[/math].

Drugi sposób
Niech [math]\displaystyle{ h = \operatorname{ord}(g, p) }[/math], zatem

[math]\displaystyle{ g^h \equiv 1 \!\! \pmod{p} }[/math]

Z twierdzenia L97 otrzymujemy

[math]\displaystyle{ g^{h p} \equiv 1 \!\! \pmod{p^2} }[/math]

Ponieważ [math]\displaystyle{ g }[/math] jest generatorem modulo [math]\displaystyle{ p^2 }[/math], to [math]\displaystyle{ \operatorname{ord}(g, p^2) = \varphi (p^2) = p (p - 1) }[/math], zatem [math]\displaystyle{ p(p - 1) \mid h p }[/math], czyli [math]\displaystyle{ (p - 1) \mid h }[/math] i otrzymujemy

[math]\displaystyle{ h = s (p - 1) \leqslant \varphi (p) = p - 1 }[/math]

Skąd wynika, że [math]\displaystyle{ h = p - 1 }[/math]. Co należało pokazać.
□

Zadanie L68
Niech [math]\displaystyle{ a \in \mathbb{Z} }[/math] i [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Pokazać, że jeżeli [math]\displaystyle{ a^n }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to [math]\displaystyle{ a }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math].

Rozwiązanie

Zauważmy, że [math]\displaystyle{ n }[/math] musi być liczbą nieparzystą, bo gdy [math]\displaystyle{ n }[/math] jest liczbą parzystą, to [math]\displaystyle{ a^n }[/math] jest liczbą kwadratową i nie może być generatorem modulo [math]\displaystyle{ p }[/math] (zobacz L44). Załóżmy, dla uzyskania sprzeczności, że [math]\displaystyle{ a }[/math] nie jest generatorem modulo [math]\displaystyle{ p }[/math]. Zatem musi istnieć taki dzielnik pierwszy [math]\displaystyle{ q }[/math] liczby [math]\displaystyle{ p - 1 }[/math], że

[math]\displaystyle{ a^{\tfrac{p - 1}{q}} \equiv 1 \!\! \pmod{p} }[/math]

Podnosząc obie strony kongruencji do [math]\displaystyle{ n }[/math]-tej potęgi, otrzymujemy

[math]\displaystyle{ (a^n)^{\tfrac{p - 1}{q}} \equiv 1 \!\! \pmod{p} }[/math]

Wbrew założeniu, że liczba [math]\displaystyle{ a^n }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math].
□

Zadanie L69
Pokazać, że jeżeli [math]\displaystyle{ 8 }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], to liczba pierwsza [math]\displaystyle{ p }[/math] musi być postaci [math]\displaystyle{ p = 24 k + 5 }[/math] lub [math]\displaystyle{ p = 24 k + 11 }[/math].

Rozwiązanie

Załóżmy dla uzyskania sprzeczności, że [math]\displaystyle{ 3 \mid (p - 1) }[/math]. Zatem

[math]\displaystyle{ 8^{\tfrac{p - 1}{3}} = 2^{p - 1} \equiv 1 \!\! \pmod{p} }[/math]

Wbrew założeniu, że [math]\displaystyle{ 8 }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math] (zobacz L42). Wynika stąd, że [math]\displaystyle{ 3 \nmid (p - 1) }[/math] i musi być

[math]\displaystyle{ p - 1 = 3 k + 1 \qquad \qquad \text{lub} \qquad \qquad p - 1 = 3 k + 2 }[/math]

Czyli

[math]\displaystyle{ 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]\displaystyle{ p }[/math] byłaby liczbą złożoną.

Z zadania L68 wiemy, że liczba [math]\displaystyle{ 2 }[/math] jest generatorem modulo [math]\displaystyle{ p }[/math], zatem jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], skąd wynika, że liczba pierwsza [math]\displaystyle{ p }[/math] musi być postaci [math]\displaystyle{ p = 8 k \pm 3 }[/math] (zobacz J34 p.7). Z chińskiego twierdzenia o resztach (zobacz J3) wynika, że układom kongruencji

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

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

Najmniejsze liczby pierwsze [math]\displaystyle{ p }[/math], dla których liczba [math]\displaystyle{ 8 }[/math] jest generatorem: [math]\displaystyle{ 11, 29, 53, 59, 83, 101, 107, \ldots }[/math]
□

Przykład L70

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

Pokaż tabele

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ \boldsymbol{p} }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]
[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 3 }[/math]
[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 7 }[/math]
[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 23 }[/math]
[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 41 }[/math]
[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 71 }[/math]
[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 313 }[/math]
[math]\displaystyle{ 11 }[/math]	[math]\displaystyle{ 643 }[/math]
[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 4111 }[/math]
[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ 457 }[/math]
[math]\displaystyle{ 14 }[/math]	[math]\displaystyle{ 1031 }[/math]
[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 439 }[/math]
[math]\displaystyle{ 16 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 17 }[/math]	[math]\displaystyle{ 311 }[/math]
[math]\displaystyle{ 18 }[/math]	[math]\displaystyle{ 53173 }[/math]
[math]\displaystyle{ 19 }[/math]	[math]\displaystyle{ 191 }[/math]
[math]\displaystyle{ 20 }[/math]	[math]\displaystyle{ 107227 }[/math]
[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ 409 }[/math]
[math]\displaystyle{ 22 }[/math]	[math]\displaystyle{ 3361 }[/math]
[math]\displaystyle{ 23 }[/math]	[math]\displaystyle{ 2161 }[/math]
[math]\displaystyle{ 24 }[/math]	[math]\displaystyle{ 533821 }[/math]
[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ - }[/math]

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ \boldsymbol{p} }[/math]
[math]\displaystyle{ 26 }[/math]	[math]\displaystyle{ 12391 }[/math]
[math]\displaystyle{ 27 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 28 }[/math]	[math]\displaystyle{ 133321 }[/math]
[math]\displaystyle{ 29 }[/math]	[math]\displaystyle{ 15791 }[/math]
[math]\displaystyle{ 30 }[/math]	[math]\displaystyle{ 124153 }[/math]
[math]\displaystyle{ 31 }[/math]	[math]\displaystyle{ 5881 }[/math]
[math]\displaystyle{ 32 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ 268969 }[/math]
[math]\displaystyle{ 34 }[/math]	[math]\displaystyle{ 48889 }[/math]
[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 64609 }[/math]
[math]\displaystyle{ 36 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 37 }[/math]	[math]\displaystyle{ 36721 }[/math]
[math]\displaystyle{ 38 }[/math]	[math]\displaystyle{ 55441 }[/math]
[math]\displaystyle{ 39 }[/math]	[math]\displaystyle{ 166031 }[/math]
[math]\displaystyle{ 40 }[/math]	[math]\displaystyle{ 1373989 }[/math]
[math]\displaystyle{ 41 }[/math]	[math]\displaystyle{ 156601 }[/math]
[math]\displaystyle{ 42 }[/math]	[math]\displaystyle{ 2494381 }[/math]
[math]\displaystyle{ 43 }[/math]	[math]\displaystyle{ 95471 }[/math]
[math]\displaystyle{ 44 }[/math]	[math]\displaystyle{ 71761 }[/math]
[math]\displaystyle{ 45 }[/math]	[math]\displaystyle{ 95525767 }[/math]
[math]\displaystyle{ 46 }[/math]	[math]\displaystyle{ 273001 }[/math]
[math]\displaystyle{ 47 }[/math]	[math]\displaystyle{ 275641 }[/math]
[math]\displaystyle{ 48 }[/math]	[math]\displaystyle{ 823766851 }[/math]
[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 50 }[/math]	[math]\displaystyle{ 23126821 }[/math]

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ \boldsymbol{p} }[/math]
[math]\displaystyle{ 51 }[/math]	[math]\displaystyle{ 322999 }[/math]
[math]\displaystyle{ 52 }[/math]	[math]\displaystyle{ 129361 }[/math]
[math]\displaystyle{ 53 }[/math]	[math]\displaystyle{ 161831 }[/math]
[math]\displaystyle{ 54 }[/math]	[math]\displaystyle{ 4348468741 }[/math]
[math]\displaystyle{ 55 }[/math]	[math]\displaystyle{ 459841 }[/math]
[math]\displaystyle{ 56 }[/math]	[math]\displaystyle{ 219605251 }[/math]
[math]\displaystyle{ 57 }[/math]	[math]\displaystyle{ 471769 }[/math]
[math]\displaystyle{ 58 }[/math]	[math]\displaystyle{ 336361 }[/math]
[math]\displaystyle{ 59 }[/math]	[math]\displaystyle{ 712321 }[/math]
[math]\displaystyle{ 60 }[/math]	[math]\displaystyle{ 697591 }[/math]
[math]\displaystyle{ 61 }[/math]	[math]\displaystyle{ 1171921 }[/math]
[math]\displaystyle{ 62 }[/math]	[math]\displaystyle{ 658681 }[/math]
[math]\displaystyle{ 63 }[/math]	[math]\displaystyle{ 102896401 }[/math]
[math]\displaystyle{ 64 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 65 }[/math]	[math]\displaystyle{ 11089681 }[/math]
[math]\displaystyle{ 66 }[/math]	[math]\displaystyle{ 27955201 }[/math]
[math]\displaystyle{ 67 }[/math]	[math]\displaystyle{ 3384481 }[/math]
[math]\displaystyle{ 68 }[/math]	[math]\displaystyle{ 3733801 }[/math]
[math]\displaystyle{ 69 }[/math]	[math]\displaystyle{ 110881 }[/math]
[math]\displaystyle{ 70 }[/math]	[math]\displaystyle{ 5620201 }[/math]
[math]\displaystyle{ 71 }[/math]	[math]\displaystyle{ 3659401 }[/math]
[math]\displaystyle{ 72 }[/math]	[math]\displaystyle{ 226547941621 }[/math]
[math]\displaystyle{ 73 }[/math]	[math]\displaystyle{ 760321 }[/math]
[math]\displaystyle{ 74 }[/math]	[math]\displaystyle{ 8954401 }[/math]
[math]\displaystyle{ 75 }[/math]	[math]\displaystyle{ 194515471 }[/math]

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ \boldsymbol{p} }[/math]
[math]\displaystyle{ 76 }[/math]	[math]\displaystyle{ 25291561 }[/math]
[math]\displaystyle{ 77 }[/math]	[math]\displaystyle{ 8359009 }[/math]
[math]\displaystyle{ 78 }[/math]	[math]\displaystyle{ 102009601 }[/math]
[math]\displaystyle{ 79 }[/math]	[math]\displaystyle{ 7510801 }[/math]
[math]\displaystyle{ 80 }[/math]	[math]\displaystyle{ 596653488817 }[/math]
[math]\displaystyle{ 81 }[/math]	[math]\displaystyle{ - }[/math]
[math]\displaystyle{ 82 }[/math]	[math]\displaystyle{ 24818641 }[/math]
[math]\displaystyle{ 83 }[/math]	[math]\displaystyle{ 16889161 }[/math]
[math]\displaystyle{ 84 }[/math]	[math]\displaystyle{ 16271999719 }[/math]
[math]\displaystyle{ 85 }[/math]	[math]\displaystyle{ 23821561 }[/math]
[math]\displaystyle{ 86 }[/math]	[math]\displaystyle{ 7415641 }[/math]
[math]\displaystyle{ 87 }[/math]	[math]\displaystyle{ 41299801 }[/math]
[math]\displaystyle{ 88 }[/math]	[math]\displaystyle{ 264935161 }[/math]
[math]\displaystyle{ 89 }[/math]	[math]\displaystyle{ 6366361 }[/math]
[math]\displaystyle{ 90 }[/math]	[math]\displaystyle{ 341058118633 }[/math]
[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 70716649 }[/math]
[math]\displaystyle{ 92 }[/math]	[math]\displaystyle{ 110591881 }[/math]
[math]\displaystyle{ 93 }[/math]	[math]\displaystyle{ 65150401 }[/math]
[math]\displaystyle{ 94 }[/math]	[math]\displaystyle{ 5109721 }[/math]
[math]\displaystyle{ 95 }[/math]	[math]\displaystyle{ 29128969 }[/math]
[math]\displaystyle{ 96 }[/math]	[math]\displaystyle{ 5260410488191 }[/math]
[math]\displaystyle{ 97 }[/math]	[math]\displaystyle{ 17551561 }[/math]
[math]\displaystyle{ 98 }[/math]	[math]\displaystyle{ 179199874981 }[/math]
[math]\displaystyle{ 99 }[/math]	[math]\displaystyle{ 2648833321 }[/math]
[math]\displaystyle{ 100 }[/math]	[math]\displaystyle{ - }[/math]

□

Kongruencje wielomianowe

Definicja L71
Kongruencjami wielomianowymi modulo liczba pierwsza [math]\displaystyle{ p }[/math] nazywamy kongruencje postaci

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

gdzie [math]\displaystyle{ W_n (x) = a_n x^n + \ldots + a_1 x + a_0 }[/math].

Jeżeli [math]\displaystyle{ p \nmid a_n }[/math], to powiemy, że stopień kongruecji [math]\displaystyle{ W_n (x) \equiv 0 \!\! \pmod{p} }[/math] jest równy [math]\displaystyle{ n }[/math] (zobacz J9, J10, J14).

Twierdzenie L72
Niech [math]\displaystyle{ x, a \in \mathbb{Z} }[/math], [math]\displaystyle{ \; n, m \in \mathbb{Z}_+ \; }[/math] i [math]\displaystyle{ \; \gcd (a, m) = 1 }[/math]. Rozważmy kongruencje

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

[math]\displaystyle{ x^n \equiv 1 \!\! \pmod{m} }[/math]

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

Dowód

Niech zbiory [math]\displaystyle{ S_1 = \{ \varepsilon_1, \ldots, \varepsilon_r \} }[/math] i [math]\displaystyle{ S_a = \{ \alpha_1, \ldots, \alpha_t \} }[/math] będą zbiorami wszystkich (różnych modulo [math]\displaystyle{ m }[/math]) rozwiązań kongruencji [math]\displaystyle{ x^n \equiv 1 \!\! \pmod{m} }[/math] i odpowiednio [math]\displaystyle{ x^n \equiv a \!\! \pmod{m} }[/math].

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

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

[math]\displaystyle{ \gcd (\alpha^n_1, m) = \gcd (a, m) = 1 }[/math]

czyli [math]\displaystyle{ \gcd (\alpha_1, m) = 1 }[/math], zatem [math]\displaystyle{ \alpha_1 }[/math] ma element odwrotny modulo [math]\displaystyle{ m }[/math].

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

•   są wszystkie różne modulo [math]\displaystyle{ m }[/math], bo liczba [math]\displaystyle{ \alpha_1 }[/math] ma element odwrotny (zobacz H21), zatem z definicji [math]\displaystyle{ | S_1 | = | S_{\Alpha} | }[/math]

•   są rozwiązaniami kongruencji [math]\displaystyle{ x^n \equiv a \!\! \pmod{m} }[/math], bo

[math]\displaystyle{ (\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]\displaystyle{ S_{\Alpha} \subseteq S_a }[/math] i [math]\displaystyle{ | S_{\Alpha} | \leqslant | S_a | }[/math].

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

•   są wszystkie różne modulo [math]\displaystyle{ m }[/math], bo liczba [math]\displaystyle{ \alpha^{- 1}_1 }[/math] ma element odwrotny (zobacz H21), zatem z definicji [math]\displaystyle{ | S_a | = | S_{\Epsilon} | }[/math]

•   są rozwiązaniami kongruencji [math]\displaystyle{ x^n \equiv 1 \!\! \pmod{m} }[/math], bo

[math]\displaystyle{ (\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]\displaystyle{ S_{\Epsilon} \subseteq S_1 }[/math] i [math]\displaystyle{ | S_{\Epsilon} | \leqslant | S_1 | }[/math].

Łącząc oszacowania, otrzymujemy

[math]\displaystyle{ | S_1 | = | S_{\Alpha} | \leqslant | S_a | = | S_{\Epsilon} | \leqslant | S_1 | }[/math]

Wynika stąd, że [math]\displaystyle{ | S_1 | = | S_a | }[/math]. Co należało pokazać.
□

Zadanie L73
Niech [math]\displaystyle{ m \geqslant 3 }[/math] będzie liczbą, która ma generator i istnieją rozwiązania kongruencji [math]\displaystyle{ x^2 \equiv a \!\! \pmod{m} }[/math]. Pokazać, że istnieją dokładnie dwa rozwiązania tej kongruencji. Wskazówka: zobacz dowód twierdzenia L36.

Twierdzenie L74
Niech [math]\displaystyle{ x, a \in \mathbb{Z} }[/math], [math]\displaystyle{ \; n \in \mathbb{Z}_+ }[/math], liczba [math]\displaystyle{ p }[/math] będzie liczbą pierwszą taką, że [math]\displaystyle{ p \nmid a \; }[/math] i [math]\displaystyle{ \; d = \gcd (n, p - 1) }[/math]. Kongruencja

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

ma rozwiązanie wtedy i tylko wtedy, gdy kongruencja

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

ma rozwiązanie.

Dowód

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

Z założenia kongruencja [math]\displaystyle{ x^n \equiv a \!\! \pmod{p} }[/math] ma rozwiązanie, powiedzmy [math]\displaystyle{ x \equiv u \!\! \pmod{p} }[/math]. Ponieważ [math]\displaystyle{ d \mid n }[/math], to

[math]\displaystyle{ a \equiv u^n \equiv u^{k d} \equiv (u^k)^d \!\! \pmod{p} }[/math]

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

Z założenia kongruencja [math]\displaystyle{ x^d \equiv a \!\! \pmod{p} }[/math] ma rozwiązanie, powiedzmy [math]\displaystyle{ x \equiv u \!\! \pmod{p} }[/math]. Z lematu Bézouta (zobacz C73) wiemy, że istnieją takie liczby [math]\displaystyle{ r, s }[/math], że [math]\displaystyle{ n r + (p - 1) s = d }[/math]. Zatem

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

Twierdzenie L75
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą. Jeżeli [math]\displaystyle{ d \mid (p - 1) }[/math], to kongruencja [math]\displaystyle{ x^d \equiv 1 \!\! \pmod{p} }[/math] ma dokładnie [math]\displaystyle{ d }[/math] rozwiązań modulo [math]\displaystyle{ p }[/math].

Dowód

Zauważmy, że jeżeli [math]\displaystyle{ d \mid (p - 1) }[/math], to

[math]\displaystyle{ 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]\displaystyle{ x^{p - 1} - 1 \equiv 0 \!\! \pmod{p} \qquad \qquad \qquad (1) }[/math]

ma dokładnie [math]\displaystyle{ p - 1 }[/math] rozwiązań modulo [math]\displaystyle{ p }[/math] i są nimi liczby [math]\displaystyle{ 1, 2, \ldots, p - 1 }[/math].

Z twierdzenia Lagrange'a liczba rozwiązań kongruencji

[math]\displaystyle{ x^d - 1 \equiv 0 \!\! \pmod{p} \qquad \qquad \qquad \;\;\; (2) }[/math]

spełnia warunek [math]\displaystyle{ \alpha \leqslant d }[/math], a liczba rozwiązań kongruencji

[math]\displaystyle{ 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]\displaystyle{ \beta \leqslant p - 1 - d }[/math]. Z tych dwóch warunków wynika, że

[math]\displaystyle{ \alpha + \beta \leqslant p - 1 }[/math]

Jednocześnie każde rozwiązanie kongruencji [math]\displaystyle{ (1) }[/math] jest rozwiązaniem jednej lub obydwu kongruencji [math]\displaystyle{ (2) }[/math] i [math]\displaystyle{ (3) }[/math], zatem musi być

[math]\displaystyle{ p - 1 \leqslant \alpha + \beta }[/math]

Łącząc, dostajemy

[math]\displaystyle{ p - 1 \leqslant \alpha + \beta \leqslant p - 1 }[/math]

Czyli [math]\displaystyle{ \alpha + \beta = p - 1 }[/math]. Z prostego oszacowania

[math]\displaystyle{ \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]\displaystyle{ \alpha = d }[/math].

Jeśli tak, to [math]\displaystyle{ \beta = p - 1 - \alpha = p - 1 - d }[/math].

Co należało pokazać.
□

Twierdzenie L76
Niech [math]\displaystyle{ p \nmid a \; }[/math] i [math]\displaystyle{ \; d = \gcd (n, p - 1) }[/math]. Jeżeli jedna z kongruencji

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

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

ma rozwiązania, to każda z tych kongruencji ma dokładnie [math]\displaystyle{ d }[/math] rozwiązań.

Dowód

Dowód jest prostym wnioskiem z twierdzeń L74, L72 i L75.

Niech [math]\displaystyle{ S_{n, a} }[/math], [math]\displaystyle{ S_{n, 1} }[/math], [math]\displaystyle{ S_{d, a} }[/math] i [math]\displaystyle{ S_{d, 1} }[/math] będą odpowiednio zbiorami (różnych modulo [math]\displaystyle{ p }[/math]) rozwiązań kongruencji

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

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

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

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

gdzie [math]\displaystyle{ p \nmid a }[/math] i [math]\displaystyle{ d = \gcd (n, p - 1) }[/math]. Oto co na temat ilości rozwiązań możemy powiedzieć na podstawie wspomnianych twierdzeń.

Z twierdzenia L74:   [math]\displaystyle{ | S_{n, a} | = | S_{d, a} | }[/math]

Z twierdzenia L72:   [math]\displaystyle{ | S_{n, a} | = | S_{n, 1} | }[/math]   (jeżeli kongruencja [math]\displaystyle{ x^n \equiv a \!\! \pmod{p} }[/math] ma rozwiązania)

Z twierdzenia L75:   [math]\displaystyle{ | S_{d, 1} | = d }[/math]

Jeżeli [math]\displaystyle{ x^n \equiv a \!\! \pmod{p} }[/math] ma rozwiązania, to korzystając kolejno z twierdzeń L74, L72 i L75, otrzymujemy

[math]\displaystyle{ | S_{n, a} | = | S_{d, a} | = | S_{d, 1} | = d }[/math]

Jeżeli [math]\displaystyle{ x^d \equiv a \!\! \pmod{p} }[/math] ma rozwiązania, to z twierdzenia L74 wynika, że [math]\displaystyle{ | S_{d, a} | = | S_{n, a} | }[/math]. Z twierdzeń L72 i L75 otrzymujemy [math]\displaystyle{ | 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 wypisanych w twierdzeniu kongruencji ma rozwiązania, mamy

[math]\displaystyle{ | S_{n, a} | = | S_{d, a} | = d }[/math]

Co było do pokazania.
□

Uwaga L77
Wykorzystując pojęcie rzędu liczby i generatora, znajdziemy warunek, który rozstrzyga, kiedy kongruencja [math]\displaystyle{ x^n \equiv a \!\! \pmod{p} }[/math] ma rozwiązania. Przedstawimy też metodę, która pozwala znaleźć wszystkie rozwiązania tej kongruencji.

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

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

ma rozwiązania wtedy i tylko wtedy, gdy

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

gdzie [math]\displaystyle{ d = \gcd (n, p - 1) }[/math]. Jeżeli powyższy warunek jest spełniony, to istnieje dokładnie [math]\displaystyle{ d }[/math] rozwiązań modulo [math]\displaystyle{ p }[/math].

Dowód

Niech [math]\displaystyle{ g }[/math] będzie generatorem modulo [math]\displaystyle{ p }[/math] i niech [math]\displaystyle{ x \equiv g^y }[/math], [math]\displaystyle{ a \equiv g^b }[/math] modulo [math]\displaystyle{ p }[/math]. Z twierdzenia L23 dostajemy

[math]\displaystyle{ x^n \equiv a \!\! \pmod{p} \qquad \qquad \Longleftrightarrow \qquad \qquad (g^y)^n \equiv g^b \!\! \pmod{p} }[/math]

[math]\displaystyle{ \: \Longleftrightarrow \qquad \qquad g^{n y} \equiv g^b \!\! \pmod{p} }[/math]

[math]\displaystyle{ \: \Longleftrightarrow \qquad \qquad n y \equiv b \!\! \pmod{p - 1} }[/math]

Kongruencja [math]\displaystyle{ n y \equiv b \!\! \pmod{p - 1} }[/math] nie ma rozwiązań, gdy [math]\displaystyle{ d \nmid b }[/math] lub ma [math]\displaystyle{ d }[/math] rozwiązań, gdy [math]\displaystyle{ d \mid b }[/math]. Warunek [math]\displaystyle{ d \mid b }[/math] możemy równoważnie przekształcić

[math]\displaystyle{ d \mid b \qquad \qquad \Longleftrightarrow \qquad \qquad (p - 1) \biggr\rvert {\small\frac{(p - 1)b}{d}} }[/math]

[math]\displaystyle{ \:\, \Longleftrightarrow \qquad \qquad {\small\frac{b \cdot (p - 1)}{d}} \equiv 0 \!\! \pmod{p - 1} }[/math]

[math]\displaystyle{ \:\, \Longleftrightarrow \qquad \qquad g^{b (p - 1) / d} \equiv 1 \!\! \pmod{p} }[/math]

[math]\displaystyle{ \:\, \Longleftrightarrow \qquad \qquad a^{(p - 1)/ d} \equiv 1 \!\! \pmod{p} }[/math]

Jeżeli [math]\displaystyle{ d \mid b }[/math], to przechodząc do kongruencji równoważnej (zobacz L99), dostajemy

[math]\displaystyle{ {\small\frac{n}{d}} \cdot y \equiv {\small\frac{b}{d}} \;\, \left( \operatorname{mod} \,\, {\small\frac{p - 1}{d}} \right) }[/math]

Czyli

[math]\displaystyle{ 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]\displaystyle{ d }[/math] rozwiązań powyższej kongruencji modulo [math]\displaystyle{ p - 1 }[/math] i tyle samo rozwiązań ma kongruencja [math]\displaystyle{ x^n \equiv a \!\! \pmod{p} }[/math]. Co kończy dowód.
□

Zadanie L79
Pokazać, że kongruencja [math]\displaystyle{ x^3 \equiv 3 \!\! \pmod{31} }[/math] nie ma rozwiązania.

Rozwiązanie

Łatwo znajdujemy, że [math]\displaystyle{ {\small\frac{p - 1}{\gcd (n, p - 1)}} = {\small\frac{30}{3}} = 10 \; }[/math] oraz [math]\displaystyle{ \; 3^{10} \equiv 3 \cdot (3^3)^3 \equiv 3 \cdot (- 4)^3 \equiv - 6 \not\equiv 1 \!\! \pmod{31} }[/math].
□

Zadanie L80
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą postaci [math]\displaystyle{ p = 6 k + 5 }[/math]. Pokazać, że dla każdej liczby całkowitej [math]\displaystyle{ a }[/math] kongruencja [math]\displaystyle{ x^3 \equiv a \!\! \pmod{p} }[/math] ma jedno rozwiązanie i jest ono postaci [math]\displaystyle{ u \equiv a^{4 k + 3} \!\! \pmod{p} }[/math].

Rozwiązanie

Jeżeli [math]\displaystyle{ p \mid a }[/math], to kongruencja [math]\displaystyle{ x^3 \equiv 0 \!\! \pmod{p} }[/math] ma jedno rozwiązanie [math]\displaystyle{ x \equiv 0 \!\! \pmod{p} }[/math]. Jeżeli [math]\displaystyle{ p \nmid a }[/math] i (z założenia) [math]\displaystyle{ p }[/math] jest postaci [math]\displaystyle{ 6 k + 5 }[/math], to

[math]\displaystyle{ d = \gcd (n, p - 1) = \gcd (3, 6 k + 4) = 1 }[/math]

Wynika stąd, że dla każdej liczby całkowitej [math]\displaystyle{ a }[/math] takiej, że [math]\displaystyle{ p \nmid a }[/math] kongruencja [math]\displaystyle{ x^3 \equiv a \!\! \pmod{p} }[/math] ma rozwiązanie, bo z twierdzenia Fermata otrzymujemy

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

Ilość rozwiązań jest równa [math]\displaystyle{ d = 1 }[/math]. Możemy łatwo podać jawną postać rozwiązania. Istotnie, niech [math]\displaystyle{ u \equiv a^{4 k + 3} \!\! \pmod{p} }[/math], gdzie [math]\displaystyle{ p = 6 k + 5 }[/math]. Mamy

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

□

Zadanie L81
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą. Znaleźć rozwiązania kongruencji [math]\displaystyle{ x^3 \equiv 1 \!\! \pmod{p} }[/math].

Rozwiązanie

Łatwo sprawdzamy, że dla [math]\displaystyle{ p = 2, 3, 5 }[/math] mamy tylko jedno rozwiązanie [math]\displaystyle{ x \equiv 1 \!\! \pmod{p} }[/math]. Jest to oczywiste rozwiązanie prawdziwe dla wszystkich liczb pierwszych [math]\displaystyle{ p }[/math]. Ponieważ

[math]\displaystyle{ x^3 - 1 = (x - 1) (x^2 + x + 1) }[/math]

to problem istnienia kolejnych rozwiązań sprowadza się do poszukiwania rozwiązań kongruencji

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

Niech [math]\displaystyle{ p \geqslant 5 }[/math], ponieważ [math]\displaystyle{ \gcd (4, p) = 1 }[/math], to liczba [math]\displaystyle{ 4 }[/math] ma element odwrotny modulo [math]\displaystyle{ p }[/math] i możemy napisać

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

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

Liczba [math]\displaystyle{ - 3 }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p = 6 k + 1 }[/math] i liczbą niekwadratową dla [math]\displaystyle{ p = 6 k + 5 }[/math] (zobacz J46). Zatem dla liczb pierwszych postaci [math]\displaystyle{ p = 6 k + 5 }[/math] kongruencja [math]\displaystyle{ x^3 \equiv 1 \!\! \pmod{p} }[/math] ma tylko jedno rozwiązanie [math]\displaystyle{ x \equiv 1 \!\! \pmod{p} }[/math].

W przypadku liczb pierwszych postaci [math]\displaystyle{ p = 6 k + 1 }[/math] kongruencja [math]\displaystyle{ (1) }[/math] ma rozwiązania. Niech [math]\displaystyle{ u }[/math] oznacza liczbę będącą rozwiązaniem kongruencji [math]\displaystyle{ u^2 \equiv - 3 \!\! \pmod{p} }[/math]. Otrzymujemy

[math]\displaystyle{ 2 x + 1 \equiv \pm u \!\! \pmod{p} }[/math]

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

Ponieważ [math]\displaystyle{ 2^{- 1} \equiv {\small\frac{p + 1}{2}} \!\! \pmod{p} }[/math], to

[math]\displaystyle{ 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]\displaystyle{ u' }[/math] oznaczyliśmy nieparzystą z liczb [math]\displaystyle{ u }[/math] i [math]\displaystyle{ p - u }[/math], zapewniając tym samym parzystość licznika. Zatem dla liczb pierwszych postaci [math]\displaystyle{ p = 6 k + 1 }[/math] kongruencja [math]\displaystyle{ x^3 \equiv 1 \!\! \pmod{p} }[/math] ma trzy rozwiązania [math]\displaystyle{ x \equiv 1, {\small\frac{- 1 - u'}{2}}, {\small\frac{- 1 + u'}{2}} \!\! \pmod{p} }[/math].
□

Zadanie L82
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą postaci [math]\displaystyle{ p = 6 k + 1 }[/math]. Znaleźć rozwiązania kongruencji [math]\displaystyle{ x^3 \equiv 1 \!\! \pmod{p} }[/math].

Rozwiązanie

Zauważmy, że

[math]\displaystyle{ d = \gcd (3, p - 1) = \gcd (3, 6 k) = 3 }[/math]

Ponieważ kongruencja [math]\displaystyle{ x^3 \equiv 1 \!\! \pmod{p} }[/math] ma rozwiązania, bo [math]\displaystyle{ x \equiv 1 \!\! \pmod{p} }[/math] jest rozwiązaniem dla każdej liczby pierwszej [math]\displaystyle{ p }[/math], to ma dokładnie trzy rozwiązania różne modulo [math]\displaystyle{ p }[/math].

Rozwiązania najprościej wypisać, korzystając z tego, że każda liczba pierwsza ma generator. Niech [math]\displaystyle{ g }[/math] będzie generatorem modulo [math]\displaystyle{ p }[/math]. Liczby

[math]\displaystyle{ 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]\displaystyle{ p }[/math], bo [math]\displaystyle{ 0 \lt {\small\frac{p - 1}{3}} \lt 2 \cdot {\small\frac{p - 1}{3}} \lt p - 1 \lt p }[/math] i są rozwiązaniami kongruencji [math]\displaystyle{ x^3 \equiv 1 \!\! \pmod{p} }[/math], co można łatwo sprawdzić. Mamy

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

[math]\displaystyle{ (u_2)^3 \equiv (g^{p - 1})^2 \equiv 1 \!\! \pmod{p} }[/math]

Oczywiście dla każdej liczby [math]\displaystyle{ a }[/math] względnie pierwszej z [math]\displaystyle{ p }[/math] możemy napisać analogiczne wzory

[math]\displaystyle{ 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]\displaystyle{ (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 zaraz pokażemy dlaczego. Zauważmy, że w ogólności muszą być spełnione warunki

[math]\displaystyle{ u_1 \equiv a^{(p - 1) / 3} \not\equiv 1 \!\! \pmod{p} }[/math]

[math]\displaystyle{ u_2 \equiv a^{2 (p - 1) / 3} \not\equiv 1 \!\! \pmod{p} }[/math]

[math]\displaystyle{ a^{(p - 1) / 3} \not\equiv a^{2 (p - 1) / 3} \!\! \pmod{p} }[/math]

Pierwszy warunek zapewnia, że [math]\displaystyle{ u_1 \not\equiv u_3 \!\! \pmod{p} }[/math], drugi, że [math]\displaystyle{ u_2 \not\equiv u_3 \!\! \pmod{p} }[/math], a ostatni zapewnia, że [math]\displaystyle{ u_1 \not\equiv u_2 \!\! \pmod{p} }[/math].

Trzeci warunek możemy zapisać w postaci

[math]\displaystyle{ a^{(p - 1) / 3} (1 - a^{(p - 1) / 3}) \not\equiv 0 \!\! \pmod{p} }[/math]

Oczywiście [math]\displaystyle{ a^{(p - 1) / 3} \not\equiv 0 \!\! \pmod{p} }[/math], bo z założenia [math]\displaystyle{ p \nmid a }[/math]. Nie może też być [math]\displaystyle{ 1 - a^{(p - 1) / 3} \equiv 0 \!\! \pmod{p} }[/math], bo w warunku pierwszym założyliśmy, że [math]\displaystyle{ a^{(p - 1) / 3} \not\equiv 1 \!\! \pmod{p} }[/math].

Ponieważ [math]\displaystyle{ u_2 \equiv (u_1)^2 \!\! \pmod{p} }[/math], to warunek drugi możemy zapisać jako [math]\displaystyle{ (u_1)^2 \not\equiv 1 \!\! \pmod{p} }[/math], czyli [math]\displaystyle{ (u_1 - 1) (u_1 + 1) \not\equiv 0 \!\! \pmod{p} }[/math]. Ze względu na pierwszy warunek nie może być [math]\displaystyle{ u_1 \equiv 1 \!\! \pmod{p} }[/math] i pozostaje jedynie [math]\displaystyle{ u_1 \not\equiv - 1 \!\! \pmod{p} }[/math]. Zauważmy, że warunki

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

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

odpowiadają założeniu, że rząd liczby [math]\displaystyle{ a }[/math] nie dzieli liczb [math]\displaystyle{ {\small\frac{p - 1}{3}} \; }[/math] i [math]\displaystyle{ \; {\small\frac{2 (p - 1)}{3}} }[/math].

Wynika stąd, że dysponując dowolną liczbą [math]\displaystyle{ a }[/math] względnie pierwszą z [math]\displaystyle{ p }[/math] taką, że [math]\displaystyle{ a^{(p - 1) / 3} \not\equiv \pm 1 \!\! \pmod{p} }[/math], możemy utworzyć wszystkie rozwiązania kongruencji [math]\displaystyle{ 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]\displaystyle{ 6 k + 1 }[/math] ([math]\displaystyle{ p \leqslant 47056180177 }[/math]), jest równa tylko [math]\displaystyle{ 1.694548 }[/math].
□

Zadanie L83
Niech [math]\displaystyle{ a \in \mathbb{Z} }[/math], [math]\displaystyle{ \; p }[/math] będzie liczbą pierwszą postaci [math]\displaystyle{ p = 6 k + 1 \; }[/math] i [math]\displaystyle{ \; p \nmid a }[/math]. Znaleźć rozwiązania kongruencji [math]\displaystyle{ x^3 \equiv a \!\! \pmod{p} }[/math].

Rozwiązanie

Zauważmy, że

[math]\displaystyle{ d = \gcd (3, p - 1) = \gcd (3, 6 k) = 3 }[/math]

Zatem, jeżeli kongruencja [math]\displaystyle{ x^3 \equiv a \!\! \pmod{p} }[/math] ma rozwiązania, to ma [math]\displaystyle{ 3 }[/math] rozwiązania różne modulo [math]\displaystyle{ p }[/math].

Niech [math]\displaystyle{ g }[/math] będzie generatorem modulo [math]\displaystyle{ p }[/math]. Ponieważ liczby [math]\displaystyle{ g^1, g^2, \ldots, g^{p - 1} }[/math] są wszystkie różne modulo [math]\displaystyle{ p }[/math] (zobacz L32), to istnieje taki wykładnik dodatni [math]\displaystyle{ r \lt p }[/math], że [math]\displaystyle{ a \equiv g^r \!\! \pmod{p} }[/math]. Liczba [math]\displaystyle{ r }[/math] może być postaci [math]\displaystyle{ 3 k }[/math] lub [math]\displaystyle{ 3 k + 1 }[/math], lub [math]\displaystyle{ 3 k + 2 }[/math]. Zobaczmy, jak ten fakt wpływa na istnienie rozwiązań.

[math]\displaystyle{ a^{(p - 1) / d} \equiv (g^{3 k})^{(p - 1) / 3} \equiv g^{k (p - 1)} \equiv 1 \!\! \pmod{p} }[/math]

Widzimy, że w przypadku, gdy [math]\displaystyle{ a \equiv g^{3 k} \!\! \pmod{p} }[/math], to rozpatrywana kongruencja ma rozwiązania.

[math]\displaystyle{ 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]\displaystyle{ g^{(p - 1) / 3} \equiv 1 \!\! \pmod{p} }[/math], bo rząd liczby [math]\displaystyle{ g }[/math] byłby nie większy od [math]\displaystyle{ {\small\frac{p - 1}{3}} }[/math], wbrew założeniu, że [math]\displaystyle{ g }[/math] jest generatorem. Podobnie otrzymujemy dla przypadku, gdy [math]\displaystyle{ r = 3 k + 2 }[/math].

Podsumowując: jeżeli [math]\displaystyle{ a \equiv g^r \!\! \pmod{p} \; }[/math] i [math]\displaystyle{ \; 3 \mid r }[/math], to kongruencja [math]\displaystyle{ x^3 \equiv a \!\! \pmod{p} }[/math] ma trzy rozwiązania

[math]\displaystyle{ 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]\displaystyle{ p }[/math], bo [math]\displaystyle{ 0 \lt {\small\frac{r}{3}} \lt {\small\frac{r + (p - 1)}{3}} \lt {\small\frac{r + 2 (p - 1)}{3}} \lt p }[/math]

Jeżeli [math]\displaystyle{ 3 \nmid r }[/math], to kongruencja [math]\displaystyle{ x^3 \equiv a \!\! \pmod{p} }[/math] nie ma rozwiązań.

Warto jeszcze zauważyć, że wśród liczb [math]\displaystyle{ a }[/math] takich, że [math]\displaystyle{ 0 \lt a \lt p = 6 k + 1 }[/math], liczby sześcienne modulo [math]\displaystyle{ p }[/math] (czyli takie, dla których kongruencja [math]\displaystyle{ x^3 \equiv a \!\! \pmod{p} }[/math] ma rozwiązanie) stanowią [math]\displaystyle{ {\small\frac{1}{3}} }[/math] tych liczb, a pozostałe [math]\displaystyle{ {\small\frac{2}{3}} }[/math] to liczby niesześcienne modulo [math]\displaystyle{ p }[/math].
□

Przykład L84
Jeżeli w kongruencji [math]\displaystyle{ x^n \equiv a \!\! \pmod{p} }[/math] [math]\displaystyle{ n }[/math] jest liczbą parzystą, zaś [math]\displaystyle{ a }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], to kongruencja ta nie ma rozwiązania. Jest to łatwo widoczne, jeśli położymy [math]\displaystyle{ n = 2 k \; }[/math] i [math]\displaystyle{ \; y = x^k }[/math], wtedy kongruencja [math]\displaystyle{ y^2 \equiv a \!\! \pmod{p} }[/math] w sposób oczywisty nie ma rozwiązania.

Zadanie L85
Znaleźć rozwiązania kongruencji

[math]\displaystyle{ x^2 \equiv 11 \!\! \pmod{13} }[/math]   Odp.: brak rozwiązań

[math]\displaystyle{ x^2 \equiv 10 \!\! \pmod{13} }[/math]   Odp.: [math]\displaystyle{ x \equiv 6 \!\! \pmod{13} \; }[/math] i [math]\displaystyle{ \; x \equiv 7 \!\! \pmod{13} }[/math]

[math]\displaystyle{ x^3 \equiv 5 \!\! \pmod{13} }[/math]   Odp.: [math]\displaystyle{ x \equiv 7 \!\! \pmod{13} }[/math], [math]\displaystyle{ x \equiv 8 \!\! \pmod{13} \; }[/math] i [math]\displaystyle{ \; x \equiv 11 \!\! \pmod{13} }[/math]

[math]\displaystyle{ x^7 \equiv 4 \!\! \pmod{13} }[/math]   Odp.: [math]\displaystyle{ x \equiv 4 \!\! \pmod{13} }[/math]

Wskazówka: liczba [math]\displaystyle{ 2 }[/math] jest generatorem modulo [math]\displaystyle{ 13 }[/math].

Rozwiązanie

W każdym przypadku będziemy stosowali podstawienie [math]\displaystyle{ x \equiv 2^y \!\! \pmod{13} }[/math].

Punkt 1.

[math]\displaystyle{ x^2 \equiv 11 \!\! \pmod{13} }[/math]

[math]\displaystyle{ 2^{2 y} \equiv 11 \equiv 2^7 \!\! \pmod{13} }[/math]

[math]\displaystyle{ 2 y \equiv 7 \!\! \pmod{12} }[/math]

Powyższa kongruencja nie ma rozwiązań, bo w ogólności kongruencja [math]\displaystyle{ a x \equiv b \!\! \pmod{m} }[/math] ma rozwiązanie wtedy i tylko wtedy, gdy [math]\displaystyle{ \gcd (a, m) \mid b }[/math] (zobacz C76). Jeżeli [math]\displaystyle{ \gcd (a, m) \mid b }[/math], to istnieje [math]\displaystyle{ \gcd (a, m) }[/math] różnych rozwiązań modulo [math]\displaystyle{ m }[/math].

Punkt 2.

[math]\displaystyle{ x^2 \equiv 10 \!\! \pmod{13} }[/math]

[math]\displaystyle{ 2^{2 y} \equiv 10 \equiv 2^{10} \!\! \pmod{13} }[/math]

[math]\displaystyle{ 2 y \equiv 10 \!\! \pmod{12} }[/math]

Ponieważ [math]\displaystyle{ \gcd (2, 12) \mid 10 }[/math], to istnieją [math]\displaystyle{ 2 }[/math] rozwiązania. Przechodząc do kongruencji równoważnej (zobacz L99), dostajemy

[math]\displaystyle{ y \equiv 5 \!\! \pmod{6} }[/math]

Co modulo [math]\displaystyle{ 12 }[/math] daje dwa rozwiązania [math]\displaystyle{ y \equiv 5 \!\! \pmod{12} \; }[/math] i [math]\displaystyle{ \; y \equiv 11 \!\! \pmod{12} }[/math]. Otrzymujemy

[math]\displaystyle{ x \equiv 2^5 \equiv 6 \!\! \pmod{13} }[/math] i [math]\displaystyle{ x \equiv 2^{11} \equiv 7 \!\! \pmod{13} }[/math]

Punkt 3.

[math]\displaystyle{ x^3 \equiv 5 \!\! \pmod{13} }[/math]

[math]\displaystyle{ 2^{3 y} \equiv 5 \equiv 2^9 \!\! \pmod{13} }[/math]

[math]\displaystyle{ 3 y \equiv 9 \!\! \pmod{12} }[/math]

Ponieważ [math]\displaystyle{ \gcd (3, 12) \mid 9 }[/math], to istnieją [math]\displaystyle{ 3 }[/math] rozwiązania. Przechodząc do kongruencji równoważnej, dostajemy

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

Co modulo [math]\displaystyle{ 12 }[/math] daje trzy rozwiązania: [math]\displaystyle{ y \equiv 3 \!\! \pmod{12} }[/math], [math]\displaystyle{ y \equiv 7 \!\! \pmod{12} \; }[/math] i [math]\displaystyle{ \; y \equiv 11 \!\! \pmod{12} }[/math]. Otrzymujemy [math]\displaystyle{ x \equiv 2^3 \equiv 8 \!\! \pmod{13} }[/math], [math]\displaystyle{ x \equiv 2^7 \equiv 11 \!\! \pmod{13} \; }[/math] [math]\displaystyle{ \text{i} \;\; x \equiv 2^{11} \equiv 7 \!\! \pmod{13} }[/math]

Punkt 4.

[math]\displaystyle{ x^7 \equiv 4 \!\! \pmod{13} }[/math]

[math]\displaystyle{ 2^{7 y} \equiv 4 \equiv 2^2 \!\! \pmod{13} }[/math]

[math]\displaystyle{ 7 y \equiv 2 \!\! \pmod{12} }[/math]

[math]\displaystyle{ y \equiv 14 \equiv 2 \!\! \pmod{12} }[/math]

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

□

Zadanie L86
Korzystając z faktu, że [math]\displaystyle{ 12 }[/math] jest generatorem modulo [math]\displaystyle{ 31 }[/math], znaleźć rozwiązania kongruencji [math]\displaystyle{ x^{14} \equiv 12^6 \!\! \pmod{31} }[/math].

Rozwiązanie

Zapiszmy [math]\displaystyle{ x \equiv 12^y \!\! \pmod{31} }[/math], gdzie [math]\displaystyle{ 0 \leqslant y \leqslant 30 }[/math], zatem należy rozwiązać kongruencję [math]\displaystyle{ 12^{14 y} \equiv 12^6 \!\! \pmod{31} }[/math], czyli modulo [math]\displaystyle{ 30 }[/math] mamy

[math]\displaystyle{ \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 przedziale [math]\displaystyle{ [0, 30] }[/math] są liczby [math]\displaystyle{ 9, 24 }[/math]. Odpowiednio dla [math]\displaystyle{ x }[/math] mamy [math]\displaystyle{ x \equiv 12^9, 12^{24} \!\! \pmod{31} }[/math], czyli [math]\displaystyle{ x \equiv 15, 16 \!\! \pmod{31} }[/math].
□

Lemat Hensela

 

Wielomiany

 

Twierdzenie L87
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math] będzie liczbą całkowitą dodatnią. Dla dowolnych liczb całkowitych [math]\displaystyle{ x, s }[/math] prawdziwy jest wzór

[math]\displaystyle{ x^n = s^n + (x - s) \cdot n s^{n - 1} + (x - s)^2 \cdot R_{n - 2} (x) }[/math]

gdzie [math]\displaystyle{ R_{n - 2} (x) }[/math] jest pewnym wielomianem całkowitym stopnia [math]\displaystyle{ n - 2 }[/math]. Dla [math]\displaystyle{ n = 1 }[/math] wielomian [math]\displaystyle{ R_{n - 2} (x) }[/math] jest wielomianem zerowym.

Dowód

Indukcja matematyczna. Dla [math]\displaystyle{ n = 1, 2, 3 }[/math] mamy

[math]\displaystyle{ x = s + (x - s) \cdot 1 + (x - s)^2 \cdot 0 }[/math]

[math]\displaystyle{ x^2 = s^2 + (x - s) \cdot 2 s + (x - s)^2 \cdot 1 }[/math]

[math]\displaystyle{ 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]\displaystyle{ [1, n] }[/math], otrzymujemy dla [math]\displaystyle{ n + 1 }[/math]

[math]\displaystyle{ x^{n + 1} = x \cdot x^n }[/math]

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

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

Ponieważ [math]\displaystyle{ x }[/math] możemy zapisać w postaci [math]\displaystyle{ x = s + (x - s) }[/math], to

[math]\displaystyle{ 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]\displaystyle{ \;\;\; = 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]\displaystyle{ \;\;\; = s^{n + 1} + (x - s) \cdot (n + 1) s^n + (x - s)^2 [n s^{n - 1} + x R_{n - 2} (x)] }[/math]

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

gdzie oznaczyliśmy [math]\displaystyle{ 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.
□

Twierdzenie L88
Jeżeli [math]\displaystyle{ W_n (x) }[/math] jest wielomianem całkowitym stopnia [math]\displaystyle{ n \geqslant 1 }[/math], zaś [math]\displaystyle{ W'_n (x) }[/math] jego pochodną, to

[math]\displaystyle{ W_n (x) = W_n (s) + (x - s) \cdot W'_n (s) + (x - s)^2 \cdot V_{n - 2} (x) }[/math]

gdzie [math]\displaystyle{ V_{n - 2} (x) }[/math] jest pewnym wielomianem całkowitym. Dla [math]\displaystyle{ n = 1 }[/math] wielomian [math]\displaystyle{ V_{n - 2} (x) }[/math] jest wielomianem zerowym.

Dowód

W przypadku gdy [math]\displaystyle{ W_n (x) }[/math] jest wielomianem stopnia pierwszego, mamy [math]\displaystyle{ W_1 (x) = a x + b }[/math] i możemy napisać

[math]\displaystyle{ a x + b = (a s + b) + (x - s) a + (x - s)^2 \cdot 0 }[/math]

[math]\displaystyle{ W_1 (x) = W_1 (s) + (x - s) \cdot W_1' (s) + (x - s)^2 \cdot 0 }[/math]

W przypadku gdy [math]\displaystyle{ n \geqslant 2 }[/math], mamy [math]\displaystyle{ W_n (x) = \sum_{k = 0}^{n} a_k x^k }[/math], gdzie [math]\displaystyle{ a_n \neq 0 }[/math]. Oczywiście pochodna wielomianu [math]\displaystyle{ W_n (x) }[/math] jest równa [math]\displaystyle{ W'_n (x) = \sum^n_{k = 1} k a_k x^{k - 1} }[/math]. Korzystając z twierdzenia L87, dostajemy

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

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

[math]\displaystyle{ \quad \,\, = \sum_{k = 1}^{n} a_k [(x - s) \cdot k s^{k - 1} + (x - s)^2 \cdot R_{k - 2} (x)] }[/math]

[math]\displaystyle{ \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]\displaystyle{ \quad \,\, = (x - s) W'_n (s) + (x - s)^2 V_{n - 2} (x) }[/math]

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

Rozwiązania kongruencji wielomianowych modulo [math]\displaystyle{ \boldsymbol{p^n} }[/math]

 

Twierdzenie L89
Niech [math]\displaystyle{ a, r \in \mathbb{Z} }[/math], [math]\displaystyle{ r \geqslant 2 }[/math] i [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą oraz [math]\displaystyle{ \gcd (a r, p) = 1 }[/math]. Kongruencja [math]\displaystyle{ x^r \equiv a \!\! \pmod{p^n} }[/math] ma rozwiązanie wtedy i tylko wtedy, gdy kongruencja [math]\displaystyle{ x^r \equiv a \!\! \pmod{p} }[/math] ma rozwiązanie.

Dowód

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

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

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

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

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

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

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

W przypadku, gdy [math]\displaystyle{ r = 2 }[/math] twierdzenie jest prawdziwe (zobacz J50). Niech [math]\displaystyle{ r \geqslant 3 }[/math].

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

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

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

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

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

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

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

[math]\displaystyle{ r u^{r - 1}_n \cdot s - p \cdot l = - k }[/math]

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

[math]\displaystyle{ k + r u^{r - 1}_n \cdot s_0 = l_0 \cdot p }[/math]

[math]\displaystyle{ k p^n + r u^{r - 1}_n \cdot s_0 p^n = l_0 \cdot p^{n + 1} }[/math]

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

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

Ponieważ

[math]\displaystyle{ (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]\displaystyle{ (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]\displaystyle{ p^{n + 1} }[/math] dostajemy

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

bo [math]\displaystyle{ n j \geqslant n + 1 }[/math] dla [math]\displaystyle{ j \geqslant 2 }[/math].

Czyli liczba [math]\displaystyle{ u_{n + 1} = u_n + s_0 p^n }[/math] jest rozwiązaniem kongruencji

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

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

Uwaga L90
Niech [math]\displaystyle{ \beta }[/math] będzie rozwiązaniem kongruencji [math]\displaystyle{ f(x) \equiv 0 \!\! \pmod{p^{n + 1}} }[/math], gdzie [math]\displaystyle{ f(x) }[/math] jest wielomianem całkowitym. Rozważmy kongruencje

[math]\displaystyle{ f (\beta) \equiv 0 \!\! \pmod{p^{n + 1}} \qquad \qquad (1) }[/math]

[math]\displaystyle{ f (\beta) \equiv 0 \!\! \pmod{p^n} \qquad \qquad \;\;\,\, (2) }[/math]

[math]\displaystyle{ f(x) \equiv 0 \!\! \pmod{p^n} \qquad \qquad \;\;\,\, (3) }[/math]

Zauważmy, że

•   rozwiązanie [math]\displaystyle{ \beta }[/math] w przypadku kongruencji [math]\displaystyle{ (1) }[/math] jest określone modulo [math]\displaystyle{ p^{n + 1} }[/math]
•   kongruencja [math]\displaystyle{ (2) }[/math] wynika z kongruencji [math]\displaystyle{ (1) }[/math]
•   rozwiązania [math]\displaystyle{ \alpha_1, \ldots, \alpha_s }[/math] kongruencji [math]\displaystyle{ (3) }[/math] są określone modulo [math]\displaystyle{ p^n }[/math]
•   modulo [math]\displaystyle{ p^n }[/math] rozwiązanie [math]\displaystyle{ \beta }[/math] musi być identyczne z jednym z rozwiązań [math]\displaystyle{ \alpha_1, \ldots, \alpha_s }[/math] kongruencji [math]\displaystyle{ (3) }[/math]
•   nie zmniejszając ogólności, możemy to rozwiązanie [math]\displaystyle{ \alpha_i }[/math], któremu odpowiada rozwiązanie [math]\displaystyle{ \beta }[/math], oznaczyć po prostu przez [math]\displaystyle{ \alpha }[/math]

Z powyższych spostrzeżeń wynika, że

[math]\displaystyle{ \beta \equiv \alpha \!\! \pmod{p^n} }[/math]

gdzie [math]\displaystyle{ \alpha }[/math] jest rozwiązaniem kongruencji [math]\displaystyle{ (3) }[/math]. Zatem

[math]\displaystyle{ \beta = \alpha + k \cdot p^n }[/math]

Rozpatrując powyższe równanie modulo [math]\displaystyle{ p^{n + 1} }[/math], dostajemy

[math]\displaystyle{ \beta \equiv \alpha + k \cdot p^n \!\! \pmod{p^{n + 1}} }[/math]

Ponieważ [math]\displaystyle{ p^n \mid (\beta - \alpha) }[/math], to przechodząc do kongruencji równoważnej (zobacz L99), dostajemy

[math]\displaystyle{ {\small\frac{\beta - \alpha}{p^n}} \equiv k \!\! \pmod{p} }[/math]

Czyli liczba [math]\displaystyle{ k }[/math] jest określona modulo [math]\displaystyle{ p }[/math].

Podsumujmy. Otrzymaliśmy wzór

[math]\displaystyle{ \beta \equiv \alpha + k \cdot p^n \!\! \pmod{p^{n + 1}} }[/math]

który wiąże rozwiązanie [math]\displaystyle{ \beta }[/math] kongruencji [math]\displaystyle{ (1) }[/math] z pewnym rozwiązaniem [math]\displaystyle{ \alpha }[/math] kongruencji [math]\displaystyle{ (3) }[/math]. Podkreślmy, że wzór ten uzyskaliśmy przy założeniu, że kongruencja [math]\displaystyle{ (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]\displaystyle{ (3) }[/math] pociągało za sobą istnienie rozwiązania kongruencji [math]\displaystyle{ (1) }[/math].

Na zakończenie zilustrujmy powyższe rozważania przykładem. Niech [math]\displaystyle{ f(x) = (x - 2) (x - 3) + 7 }[/math]. Rozwiązania [math]\displaystyle{ u_n }[/math] i [math]\displaystyle{ v_n }[/math] kongruencji [math]\displaystyle{ f(x) \equiv 0 \!\! \pmod{7^n} }[/math] otrzymujemy, uwzględniając [math]\displaystyle{ n }[/math] początkowych składników sum

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

Twierdzenie L91
Jeżeli [math]\displaystyle{ f(x) }[/math] jest wielomianem całkowitym, zaś [math]\displaystyle{ p }[/math] liczbą pierwszą, to prawdziwa jest kongruencja

[math]\displaystyle{ f(x + k p^n) \equiv f (x) + k p^n \cdot f' (x) \!\! \pmod{p^{n + 1}} }[/math]

Dowód

Niech [math]\displaystyle{ s \in \mathbb{Z} }[/math]. Korzystając z twierdzenia L88 i kładąc [math]\displaystyle{ x = s + k p^n }[/math], otrzymujemy

[math]\displaystyle{ 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]\displaystyle{ f(s + k p^n) \equiv f (s) + k p^n \cdot f' (s) \!\! \pmod{p^{n + 1}} }[/math]

bo [math]\displaystyle{ 2 n \geqslant n + 1 }[/math] dla [math]\displaystyle{ n \geqslant 1 }[/math]. Zauważmy, że [math]\displaystyle{ s }[/math] jest dowolną liczbą całkowitą, zatem wystarczy zmienić oznaczenie [math]\displaystyle{ s \longrightarrow x }[/math], aby otrzymać tezę twierdzenia.
□

Twierdzenie L92 (lemat Hensela)
Niech [math]\displaystyle{ \alpha, \beta \in \mathbb{Z} \; }[/math] i [math]\displaystyle{ \; p }[/math] będzie liczbą pierwszą, [math]\displaystyle{ f(x) }[/math] wielomianem całkowitym, a [math]\displaystyle{ f' (x) }[/math] jego pochodną. Jeżeli dla pewnego [math]\displaystyle{ \alpha }[/math] spełnione są warunki

[math]\displaystyle{ 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]\displaystyle{ \beta }[/math] taka, że [math]\displaystyle{ f (\beta) \equiv 0 \!\! \pmod{p^{n + 1}} }[/math].

Dowód

Wiemy, że (zobacz L91)

[math]\displaystyle{ 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]\displaystyle{ k }[/math], aby prawa strona kongruencji była równa zero.

[math]\displaystyle{ f (\alpha) + k p^n \cdot f' (\alpha) \equiv 0 \!\! \pmod{p^{n + 1}} }[/math]

Z założenia [math]\displaystyle{ p^n \mid f (\alpha) }[/math]. Przechodząc do kongruencji równoważnej (zobacz L99) otrzymujemy

[math]\displaystyle{ {\small\frac{f (\alpha)}{p^n}} + k \cdot f' (\alpha) \equiv 0 \!\! \pmod{p} }[/math]

[math]\displaystyle{ k \cdot f' (\alpha) \equiv - {\small\frac{f (\alpha)}{p^n}} \!\! \pmod{p} }[/math]

[math]\displaystyle{ k \equiv - {\small\frac{f (\alpha)}{p^n}} \cdot [f' (\alpha)]^{- 1} \!\! \pmod{p} }[/math]

Ponieważ z założenia [math]\displaystyle{ p \nmid f' (\alpha) }[/math], to liczba [math]\displaystyle{ f' (\alpha) }[/math] ma element odwrotny modulo [math]\displaystyle{ p }[/math]. Zatem [math]\displaystyle{ \beta = \alpha + k p^n \; }[/math] i [math]\displaystyle{ \; f (\beta) \equiv 0 \!\! \pmod{p^{n + 1}} }[/math]. Co należało pokazać.
□

Przykład L93
Rozważmy wielomian

[math]\displaystyle{ f(x) = x^2 + 10 x + 11 \qquad \qquad f' (x) = 2 x + 10 }[/math]

Łatwo sprawdzamy, że

[math]\displaystyle{ f(x) \equiv 0 \!\! \pmod{5} \; \qquad \text{dla} \quad x \equiv 2, 3 \!\! \pmod{5} }[/math]

[math]\displaystyle{ f' (x) \not\equiv 0 \!\! \pmod{5} \qquad \text{dla} \quad x \equiv 2, 3 \!\! \pmod{5} }[/math]

Korzystając z twierdzenia Hensela, znajdziemy pierwiastki wielomianu [math]\displaystyle{ f(x) }[/math] modulo [math]\displaystyle{ 5^n }[/math]. Zbadamy tylko przypadek [math]\displaystyle{ x \equiv 2 \!\! \pmod{5} }[/math].

Modulo 25

Rozważmy kongruencję

[math]\displaystyle{ k f' (2) \equiv - {\small\frac{f (2)}{5}} \!\! \pmod{5} }[/math]

[math]\displaystyle{ 4 k \equiv - {\small\frac{35}{5}} \equiv - 7 \equiv 3 \!\! \pmod{5} }[/math]

[math]\displaystyle{ k \equiv 2 \!\! \pmod{5} }[/math]

Zatem otrzymujemy rozwiązanie modulo [math]\displaystyle{ 25 }[/math]

[math]\displaystyle{ x \equiv 2 + 2 \cdot 5 \equiv 12 \!\! \pmod{25} }[/math]

Modulo 125

Rozważmy kongruencję

[math]\displaystyle{ k f' (12) \equiv - {\small\frac{f (12)}{25}} \!\! \pmod{5} }[/math]

[math]\displaystyle{ 4 k \equiv - {\small\frac{275}{25}} \equiv - 11 \equiv 4 \!\! \pmod{5} }[/math]

[math]\displaystyle{ k \equiv 1 \!\! \pmod{5} }[/math]

Zatem otrzymujemy rozwiązanie modulo [math]\displaystyle{ 125 }[/math]

[math]\displaystyle{ x \equiv 12 + 1 \cdot 25 \equiv 37 \!\! \pmod{125} }[/math]

Zbierając i kontynuując obliczenia dla kolejnych potęg liczby [math]\displaystyle{ 5 }[/math], gdzie

[math]\displaystyle{ f(x) = x^2 + 15 x + 31 \qquad \qquad f' (x) = 2 x + 15 }[/math]

otrzymujemy

[math]\displaystyle{ \;\; \boldsymbol{n} \;\; }[/math]	[math]\displaystyle{ \;\; \boldsymbol{\alpha} \;\; }[/math]	[math]\displaystyle{ \boldsymbol{f (\alpha)} }[/math]	[math]\displaystyle{ \boldsymbol{f' (\alpha)} }[/math]	[math]\displaystyle{ \boldsymbol{k f' (\alpha) \equiv - {\small\frac{f (\alpha)}{5^n}} \!\! \pmod{5}} }[/math]	[math]\displaystyle{ \boldsymbol{k \!\! \pmod{5}} }[/math]	[math]\displaystyle{ \boldsymbol{\beta \equiv \alpha + k \cdot 5^n \!\! \pmod{5^{n + 1}}} }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 35 = 5^n \cdot 7 }[/math]	[math]\displaystyle{ 14 }[/math]	[math]\displaystyle{ 4 k \equiv 3 \!\! \pmod{5} }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 2 + 2 \cdot 5^n \equiv 12 }[/math]
[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 275 = 5^n \cdot 11 }[/math]	[math]\displaystyle{ 34 }[/math]	[math]\displaystyle{ 4 k \equiv 4 \!\! \pmod{5} }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 12 + 1 \cdot 5^n \equiv 37 }[/math]
[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 37 }[/math]	[math]\displaystyle{ 1750 = 5^n \cdot 14 }[/math]	[math]\displaystyle{ 84 }[/math]	[math]\displaystyle{ 4 k \equiv 1 \!\! \pmod{5} }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 37 + 4 \cdot 5^n \equiv 537 }[/math]
[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 537 }[/math]	[math]\displaystyle{ 293750 = 5^n \cdot 470 }[/math]	[math]\displaystyle{ 1084 }[/math]	[math]\displaystyle{ 4 k \equiv 0 \!\! \pmod{5} }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 537 + 0 \cdot 5^n \equiv 537 }[/math]
[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 537 }[/math]	[math]\displaystyle{ 293750 = 5^n \cdot 94 }[/math]	[math]\displaystyle{ 1084 }[/math]	[math]\displaystyle{ 4 k \equiv 1 \!\! \pmod{5} }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 537 + 4 \cdot 5^n \equiv 13037 }[/math]

Zadanie L94
Niech [math]\displaystyle{ f(x) = x^3 - 2 x + 7 }[/math]. Korzystając z lematu Hensela, znaleźć rozwiązania kongruencji [math]\displaystyle{ f(x) \equiv 0 \!\! \pmod{11^6} }[/math].

Rozwiązanie

Mamy

[math]\displaystyle{ f(x) = x^3 - 2 x + 7 \qquad \qquad \text{i} \qquad \qquad f' (x) = 3 x^2 - 2 }[/math].

Kongruencja [math]\displaystyle{ f(x) \equiv 0 \!\! \pmod{11} }[/math] ma jedno rozwiązanie [math]\displaystyle{ x \equiv 2 \!\! \pmod{11} }[/math]. Sporządzimy podobną tabelę jak w przykładzie L93.

[math]\displaystyle{ \;\; \boldsymbol{n} \;\; }[/math]	[math]\displaystyle{ \boldsymbol{\alpha} }[/math]	[math]\displaystyle{ \boldsymbol{f (\alpha)} }[/math]	[math]\displaystyle{ \boldsymbol{f' (\alpha)} }[/math]	[math]\displaystyle{ \boldsymbol{k f' (\alpha) \equiv - {\small\frac{f (\alpha)}{11^n}} \!\! \pmod{11}} }[/math]	[math]\displaystyle{ \boldsymbol{k \!\! \pmod{11}} }[/math]	[math]\displaystyle{ \boldsymbol{\beta \equiv \alpha + k \cdot 11^n \!\! \pmod{11^{n + 1}}} }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 11 = 11^n \cdot 1 }[/math]	[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 10 k \equiv 10 \!\! \pmod{11} }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 2 + 1 \cdot 11^n \equiv 13 }[/math]
[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ 2178 = 11^n \cdot 18 }[/math]	[math]\displaystyle{ 505 }[/math]	[math]\displaystyle{ 10 k \equiv 4 \!\! \pmod{11} }[/math]	[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 13 + 7 \cdot 11^n \equiv 860 }[/math]
[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 860 }[/math]	[math]\displaystyle{ 636054287 = 11^n \cdot 477877 }[/math]	[math]\displaystyle{ 2218798 }[/math]	[math]\displaystyle{ 10 k \equiv 7 \!\! \pmod{11} }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 860 + 4 \cdot 11^n \equiv 6184 }[/math]
[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 6184 }[/math]	[math]\displaystyle{ 236487625143 = 11^n \cdot 16152423 }[/math]	[math]\displaystyle{ 114725566 }[/math]	[math]\displaystyle{ 10 k \equiv 10 \!\! \pmod{11} }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 6184 + 1 \cdot 11^n \equiv 20825 }[/math]
[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 20825 }[/math]	[math]\displaystyle{ 9031398973982 = 11^n \cdot 56077882 }[/math]	[math]\displaystyle{ 1301041873 }[/math]	[math]\displaystyle{ 10 k \equiv 8 \!\! \pmod{11} }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 20825 + 3 \cdot 11^n \equiv 503978 }[/math]

Znajdujemy, że [math]\displaystyle{ f(x) \equiv 0 \!\! \pmod{11^6} }[/math] dla [math]\displaystyle{ x = 503978 }[/math].
□

Z lematu Hensela wynika natychmiast.
Twierdzenie L95
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą, [math]\displaystyle{ f(x) }[/math] wielomianem całkowitym, a [math]\displaystyle{ f' (x) }[/math] jego pochodną. Jeżeli dla pewnej liczby całkowitej [math]\displaystyle{ x = \alpha }[/math] wielomian [math]\displaystyle{ f(x) }[/math] ma rozwiązanie modulo [math]\displaystyle{ p }[/math] [math]\displaystyle{ \text{i} \; f' (\alpha) \not\equiv 0 \!\! \pmod{p} }[/math], to [math]\displaystyle{ f(x) }[/math] ma rozwiązanie modulo [math]\displaystyle{ p^n }[/math] dla dowolnego [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math].

Przykład L96
Pokazaliśmy (zobacz L89), że jeżeli kongruencja [math]\displaystyle{ x^r \equiv a \!\! \pmod{p} }[/math] ma rozwiązanie, to kongruencja [math]\displaystyle{ x^r \equiv a \!\! \pmod{p^n} }[/math] też ma rozwiązanie. Z lematu Hensela rezultat ten otrzymujemy natychmiast. Z założenia istnieje takie [math]\displaystyle{ \alpha }[/math], że [math]\displaystyle{ \alpha^r \equiv a \!\! \pmod{p} }[/math]. Pochodna wielomianu [math]\displaystyle{ x^r - a }[/math] jest równa [math]\displaystyle{ r x^{r - 1} }[/math] i musi być [math]\displaystyle{ r \alpha^{r - 1} \not\equiv 0 \!\! \pmod{p} }[/math]. Skąd otrzymujemy [math]\displaystyle{ \gcd (\alpha r, p) = 1 }[/math] (warunek ten jest dodatkowym założeniem w twierdzeniu L89) i przy tym założeniu istnieje rozwiązanie kongruencji [math]\displaystyle{ x^r \equiv a \!\! \pmod{p^n} }[/math].

Uzupełnienie

Twierdzenie L97
Niech [math]\displaystyle{ k, m \in \mathbb{Z}_+ \; }[/math] i [math]\displaystyle{ \; a, b \in \mathbb{Z} }[/math]. Jeżeli [math]\displaystyle{ a \equiv b \!\! \pmod{m^k} }[/math], to [math]\displaystyle{ a^m \equiv b^m \!\! \pmod{m^{k + 1}} }[/math].

Dowód

Dla [math]\displaystyle{ m = 1 }[/math] twierdzenie jest prawdziwe. Niech [math]\displaystyle{ m \geqslant 2 }[/math]. Z założenia istnieje taka liczba całkowita [math]\displaystyle{ s }[/math], że [math]\displaystyle{ a = b + s m^k }[/math]. Korzystając z dwumianu Newtona, otrzymujemy

[math]\displaystyle{ a^m = (b + s m^k)^m }[/math]

[math]\displaystyle{ \quad \;\: = \sum_{i = 0}^m \binom{m}{i} (s m^k)^i \cdot b^{m - i} }[/math]

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \quad \;\: \equiv b^m \!\! \pmod{m^{k + 1}} }[/math]

Ponieważ dla [math]\displaystyle{ i \geqslant 2 }[/math] oraz [math]\displaystyle{ k \geqslant 1 }[/math] mamy [math]\displaystyle{ i k = k + (i - 1) k \geqslant k + 1 }[/math], zatem [math]\displaystyle{ m^{k + 1} \mid m^{i k} }[/math]. Co było do pokazania.
□

Twierdzenie L98
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ \; }[/math] i [math]\displaystyle{ \; \gcd (a, b) = 1 }[/math]. Jeżeli [math]\displaystyle{ d \mid a^{n} b \; }[/math] i [math]\displaystyle{ \; d \nmid a^{n - 1} b }[/math], to [math]\displaystyle{ d = a^{n} r }[/math], gdzie [math]\displaystyle{ \gcd (a, r) = 1 \; }[/math] i [math]\displaystyle{ \; r \mid b }[/math].

Dowód

Zapiszmy [math]\displaystyle{ d }[/math] w postaci [math]\displaystyle{ d = a^t r }[/math], gdzie [math]\displaystyle{ \gcd (a, r) = 1 }[/math]. Łatwo zauważamy, że

•    ponieważ [math]\displaystyle{ a^t \mid d \; }[/math] i [math]\displaystyle{ \; d \mid a^{n} b }[/math], to [math]\displaystyle{ a^t \mid a^{n} b }[/math], ale [math]\displaystyle{ \gcd (a, b) = 1 }[/math], zatem (zobacz C74) [math]\displaystyle{ a^t \mid a^{n} }[/math], skąd wynika, że [math]\displaystyle{ t \leqslant n }[/math]

•    ponieważ [math]\displaystyle{ r \mid d \; }[/math] i [math]\displaystyle{ \; d \mid a^{n} b }[/math], to [math]\displaystyle{ r \mid a^{n} b }[/math], ale [math]\displaystyle{ \gcd (a, r) = 1 }[/math], zatem (zobacz C74) [math]\displaystyle{ r \mid b }[/math], skąd wynika, że [math]\displaystyle{ b = r k }[/math], gdzie [math]\displaystyle{ \gcd (a, k) = 1 }[/math]

•    ponieważ [math]\displaystyle{ d \nmid a^{n - 1} b }[/math], to [math]\displaystyle{ a^t r \nmid a^{n - 1} r k }[/math], czyli [math]\displaystyle{ a^t \nmid a^{n - 1} k }[/math], ale [math]\displaystyle{ a \nmid k }[/math], bo [math]\displaystyle{ \gcd (a, k) = 1 }[/math], zatem musi być [math]\displaystyle{ t \gt n - 1 }[/math]

Łącząc uzyskane oszacowania, dostajemy [math]\displaystyle{ n - 1 \lt t \leqslant n }[/math], skąd wynika, że [math]\displaystyle{ t = n }[/math], czyli [math]\displaystyle{ d = a^{n} r }[/math]. Co należało pokazać.
□

Twierdzenie L99
Niech [math]\displaystyle{ a, b, c \in \mathbb{Z} }[/math] i [math]\displaystyle{ m \in \mathbb{Z}_+ }[/math]. Prawdziwa jest następująca równoważność kongruencji

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

Dowód

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

Z założenia [math]\displaystyle{ a c \equiv b c \!\! \pmod{m} }[/math], zatem [math]\displaystyle{ a c - b c = k m }[/math], gdzie [math]\displaystyle{ k }[/math] jest pewną liczbą całkowitą, stąd

[math]\displaystyle{ (a - b) \cdot {\small\frac{c}{\gcd (m, c)}} = k \cdot {\small\frac{m}{\gcd (m, c)}} }[/math]

Zauważmy, że liczby [math]\displaystyle{ {\small\frac{c}{\gcd (m, c)}} \; }[/math] i [math]\displaystyle{ \; {\small\frac{m}{\gcd (m, c)}} }[/math] są liczbami całkowitymi i są względnie pierwsze (zobacz H11).

Ponieważ liczba [math]\displaystyle{ {\small\frac{c}{\gcd (m, c)}} }[/math] musi dzielić prawą stronę i jest względnie pierwsza z [math]\displaystyle{ {\small\frac{m}{\gcd (m, c)}} }[/math], zatem [math]\displaystyle{ {\small\frac{c}{\gcd (m, c)}} }[/math] dzieli [math]\displaystyle{ k }[/math] (zobacz C74), czyli

[math]\displaystyle{ k = {\small\frac{c}{\gcd (m, c)}} \cdot s }[/math]

dla pewnego całkowitego [math]\displaystyle{ s }[/math]. Stąd

[math]\displaystyle{ (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]\displaystyle{ a - b = s \cdot {\small\frac{m}{\gcd (m, c)}} }[/math]

Co należało pokazać.

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

Z założenia [math]\displaystyle{ a \equiv b \;\, \left( \operatorname{mod} \,\, {\small\frac{m}{\gcd (m, c)}} \right) }[/math], zatem

[math]\displaystyle{ 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]\displaystyle{ \;\:\, \Longrightarrow \qquad \qquad {\small\frac{m}{\gcd (m, c)}} \cdot \gcd (m, c) \biggr\rvert (a - b) \cdot \gcd (m, c) }[/math]

[math]\displaystyle{ \;\;\, \Longrightarrow \qquad \qquad m \mid (a - b) \cdot \gcd (m, c) }[/math]

[math]\displaystyle{ \;\;\, \Longrightarrow \qquad \qquad m \biggr\rvert (a - b) \cdot \gcd (m, c) \cdot {\small\frac{c}{\gcd (m, c)}} }[/math]

[math]\displaystyle{ \;\;\, \Longrightarrow \qquad \qquad m \mid (a - b) \cdot c }[/math]

[math]\displaystyle{ \;\;\, \Longrightarrow \qquad \qquad a \cdot c \equiv b \cdot c \!\! \pmod{m} }[/math]

Co należało pokazać.
□

Uwaga L100
Rozważmy kongruencję

[math]\displaystyle{ 3 x \equiv 2 \!\! \pmod{5} }[/math]

Oczywiście liczba [math]\displaystyle{ 3 }[/math] ma element odwrotny [math]\displaystyle{ 3^{- 1} \equiv 2 \!\! \pmod{5} }[/math] i łatwo znajdujemy rozwiązanie [math]\displaystyle{ x \equiv 4 \!\! \pmod{5} }[/math]. W zbiorze liczb całkowitych mamy taki obraz

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

Jeśli pomnożymy obie strony kongruencji i moduł przez [math]\displaystyle{ 5 }[/math], to otrzymamy kongruencję równoważną (zobacz L99)

[math]\displaystyle{ 15 x \equiv 10 \!\! \pmod{25} }[/math]

Teraz liczba [math]\displaystyle{ 15 }[/math] nie ma elemetu odwrotnego modulo [math]\displaystyle{ 25 }[/math], ale dla tak małego modułu bez trudu znajdujemy rozwiązania kongruencji [math]\displaystyle{ x \equiv 4, 9, 14, 19, 24 \!\! \pmod{25} }[/math]. W zbiorze liczb całkowitych mamy taki obraz

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

Zbiór rozwiązań nie uległ zmianie, jedynie inaczej je teraz klasyfikujemy. Zauważmy, że

• każde rozwiązanie kongruencji modulo [math]\displaystyle{ 5 }[/math] jest rozwiązaniem kongruencji modulo [math]\displaystyle{ 25 }[/math]
• modulo [math]\displaystyle{ 25 }[/math] rozwiązania mają postać [math]\displaystyle{ x = 4 + 5 t }[/math], gdzie [math]\displaystyle{ t = 0, 1, 2, 3, 4 }[/math]

Nie ma w tym nic zaskakującego, bo

[math]\displaystyle{ 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]\displaystyle{ 3 x \equiv 2 \!\! \pmod{25} }[/math]

Ale rozwiązaniem tej kongruencji jest [math]\displaystyle{ x \equiv 9 \!\! \pmod{25} }[/math]. W zbiorze liczb całkowitych mamy teraz taki obraz

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

I zgubilibyśmy [math]\displaystyle{ 80 }[/math]% rozwiązań.

Rozwiązania kongruencji [math]\displaystyle{ 3 x \equiv 2 \!\! \pmod{25} }[/math] możemy znaleźć, korzystając z lematu Hensela (zobacz L92).

[math]\displaystyle{ f(x) = 3 x - 2 \qquad \qquad f' (x) = 3 }[/math]

[math]\displaystyle{ \;\; \boldsymbol{n} \;\; }[/math]	[math]\displaystyle{ \;\; \boldsymbol{\alpha} \;\; }[/math]	[math]\displaystyle{ \boldsymbol{f (\alpha)} }[/math]	[math]\displaystyle{ \boldsymbol{f' (\alpha)} }[/math]	[math]\displaystyle{ \boldsymbol{k f' (\alpha) \equiv - {\small\frac{f (\alpha)}{5^n}} \!\! \pmod{5}} }[/math]	[math]\displaystyle{ \boldsymbol{k \!\! \pmod{5}} }[/math]	[math]\displaystyle{ \boldsymbol{\beta \equiv \alpha + k \cdot 5^n \!\! \pmod{5^{n + 1}}} }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 10 = 5^n \cdot 2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 3 k \equiv 3 \!\! \pmod{5} }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 4 + 1 \cdot 5^n \equiv 9 }[/math]

Zauważmy, że [math]\displaystyle{ k }[/math] jest określone modulo [math]\displaystyle{ 5 }[/math], ale możemy je w tym przypadku wstawić do kongruencji określonej modulo [math]\displaystyle{ 25 }[/math], bo modulo [math]\displaystyle{ 25 }[/math] mielibyśmy [math]\displaystyle{ k \equiv 1 + 5 t }[/math], gdzie [math]\displaystyle{ t = 0, 1, 2, 3, 4 }[/math] i niezależnie od wyboru wartości liczby [math]\displaystyle{ t }[/math] otrzymujemy [math]\displaystyle{ \beta \equiv \alpha + k \cdot 5 \equiv 4 + (1 + 5 t) \cdot 5 \equiv 4 + 5 + 25 t \equiv 9 \!\! \pmod{25} }[/math].