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

Z Henryk Dąbrowski
Przejdź do nawigacji Przejdź do wyszukiwania
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][1] 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 L123). 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 L124, 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][2], 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][3].


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]

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 L123 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.


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[4][5], ż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][6]
  •    oszacowanie [math]\displaystyle{ \mathbb{g} (p) \lt \sqrt{p} }[/math] jest prawdziwe dla [math]\displaystyle{ p \gt 10^{56} }[/math][7]

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[8] 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[9].

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 L123 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 L123 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




Liczby Carmichaela

 

Definicja L71
Powiemy, że liczba całkowita [math]\displaystyle{ m }[/math] jest liczbą bezkwadratową[10], jeżeli [math]\displaystyle{ m }[/math] nie jest podzielna żaden kwadrat liczby całkowitej z wyjątkiem liczby 1. Zatem w rozkładzie liczby bezkwadratowej na czynniki pierwsze każda liczba pierwsza występuje z wykładnikiem równym jeden.


Przykład L72
Liczby [math]\displaystyle{ 1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30,31,33,34,35,37,38,39, \ldots }[/math] są liczbami bezkwadratowymi (zobacz A005117).


Zadanie L73
Pokazać, że każdą liczbę całkowitą dodatnią [math]\displaystyle{ n }[/math] można przedstawić jednoznacznie w postaci iloczynu [math]\displaystyle{ n = a^2 m }[/math], gdzie [math]\displaystyle{ m }[/math] jest liczbą bezkwadratową.

Rozwiązanie

Mamy [math]\displaystyle{ 1 = 1^2 \cdot 1 }[/math]. Niech liczba [math]\displaystyle{ m \geqslant 2 }[/math] ma następujący rozkład na czynniki pierwsze [math]\displaystyle{ m = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math]. Zapiszmy wykładniki [math]\displaystyle{ \alpha_i }[/math] w postaci [math]\displaystyle{ \alpha_i = 2 \beta_i + \delta_i }[/math], gdzie [math]\displaystyle{ \delta_i = 0 }[/math], jeżeli [math]\displaystyle{ \alpha_i }[/math] jest liczbą parzystą lub [math]\displaystyle{ \delta_i = 1 }[/math], jeżeli [math]\displaystyle{ \alpha_i }[/math] jest liczbą nieparzystą. Otrzymujemy

[math]\displaystyle{ n = p^{\alpha_1}_1 \cdot \ldots \cdot p^{\alpha_s}_s }[/math]
[math]\displaystyle{ \;\;\,\, = (p^{2 \beta_1}_1 \cdot p^{2 \beta_2}_2 \cdot \ldots \cdot p^{2 \beta_s}_s)(p^{\delta_1}_1 \cdot p^{\delta_2}_2 \cdot \ldots \cdot p^{\delta_s}_s) }[/math]
[math]\displaystyle{ \;\;\,\, = (p^{\beta_1}_1 \cdot p^{\beta_2}_2 \cdot \ldots \cdot p^{\beta_s}_s)^2 (p^{\delta_1}_1 \cdot p^{\delta_2}_2 \cdot \ldots \cdot p^{\delta_s}_s) }[/math]
[math]\displaystyle{ \;\;\,\, = a^2 \cdot m }[/math]


Definicja L74
Liczbami Carmichaela nazywamy złożone liczby nieparzyste [math]\displaystyle{ m }[/math] takie, że dla dowolnej liczby [math]\displaystyle{ a }[/math] względnie pierwszej z [math]\displaystyle{ m }[/math] jest

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


Przykład L75
Jeżeli liczba [math]\displaystyle{ a }[/math] jest względnie pierwsza z każdą z liczb [math]\displaystyle{ 3 }[/math], [math]\displaystyle{ 11 }[/math] i [math]\displaystyle{ 17 }[/math], to z twierdzenia Fermata dostajemy

[math]\displaystyle{ a^2 \equiv 1 \!\! \pmod{3} \qquad \qquad \,\, a^{10} \equiv 1 \!\! \pmod{11} \qquad \qquad a^{16} \equiv 1 \!\! \pmod{17} }[/math]

Podnosząc strony wypisanych kongruencji odpowiednio do potęg [math]\displaystyle{ 280 }[/math], [math]\displaystyle{ 56 }[/math] i [math]\displaystyle{ 35 }[/math], mamy

[math]\displaystyle{ a^{560} \equiv 1 \!\! \pmod{3} \qquad \qquad a^{560} \equiv 1 \!\! \pmod{11} \qquad \qquad a^{560} \equiv 1 \!\! \pmod{17} }[/math]

Ponieważ moduły [math]\displaystyle{ 3 }[/math], [math]\displaystyle{ 11 }[/math] i [math]\displaystyle{ 17 }[/math] są względnie pierwsze, to możemy połączyć powyższe kongruencje (zobacz J1), otrzymując kongruencję o module [math]\displaystyle{ 561 = 3 \cdot 11 \cdot 17 }[/math].

[math]\displaystyle{ a^{560} \equiv 1 \!\! \pmod{561} }[/math]

Powyższa kongruencja jest prawdziwa dla każdej liczby [math]\displaystyle{ a }[/math] względnie pierwszej z [math]\displaystyle{ 561 }[/math], zatem liczba [math]\displaystyle{ 561 }[/math] jest liczbą Carmichaela.


Przykład L76
Oto wszystkie liczby Carmichaela mniejsze od [math]\displaystyle{ 100 000 }[/math]


Zadanie L77
Pokazać, że liczba złożona parzysta nie może być liczbą Carmichaela.

Rozwiązanie

Liczba [math]\displaystyle{ m = 2 }[/math] nie jest liczbą złożoną, a dla liczb złożonych parzystych [math]\displaystyle{ m \geqslant 4 }[/math] łatwo zauważamy, że [math]\displaystyle{ \gcd (m - 1, m) = 1 }[/math], ale

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


Twierdzenie L78
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. Jeżeli [math]\displaystyle{ p \mid m \; }[/math] i [math]\displaystyle{ \; m }[/math] jest liczbą Carmichaela, to [math]\displaystyle{ m }[/math] jest liczbą bezkwadratową i [math]\displaystyle{ \, (p - 1) \mid (m - 1) }[/math].

Dowód

Niech [math]\displaystyle{ m = p^u r }[/math], gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ \gcd (p, r) = 1 }[/math]. Niech [math]\displaystyle{ g }[/math] będzie generatorem modulo [math]\displaystyle{ p^u }[/math]. Z chińskiego twierdzenia o resztach (zobacz J3) wiemy, że istnieje dokładnie jedna taka liczba [math]\displaystyle{ a }[/math] (określona modulo [math]\displaystyle{ p^u r }[/math]), że prawdziwy jest układ kongruencji

[math]\displaystyle{ \begin{array}{l} a \equiv g \; \pmod{p^u} \\ a \equiv 1 \; \pmod{r} \\ \end{array} }[/math]

Ponieważ liczby [math]\displaystyle{ p^u }[/math] i [math]\displaystyle{ \, r }[/math] są względnie pierwsze, to (zobacz H8, H30)

[math]\displaystyle{ \gcd (a, m) = \gcd (a, p^u) \cdot \gcd (a, r) = \gcd (g, p^u) \cdot \gcd (1, r) = 1 }[/math]

Z założenia [math]\displaystyle{ m }[/math] jest liczbą Carmichaela, zatem możemy napisać

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

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

[math]\displaystyle{ (p - 1) p^{u - 1} \mid (m - 1) }[/math]

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


Uwaga L79
Istnieje nieskończenie wiele liczb Carmichaela. Wiemy też, że dla dostatecznie dużych [math]\displaystyle{ x }[/math] ilość liczb Carmichaela mniejszych od [math]\displaystyle{ x }[/math] przekracza [math]\displaystyle{ x^{1 / 3} }[/math][11][12][13]. Zatem badanie pierwszości liczb testem Fermata jest obarczone trwałym i nieusuwalnym błędem, a tym samym jest zbyt zawodne. Jednak nie musimy tak bardzo obawiać się liczb Carmichaela, bo już niewielkie wzmocnienie testu Fermata rozwiązuje ten problem. Wystarczy, zamiast twierdzenia Fermata, wykorzystać kryterium Eulera (zobacz J31 i J33)

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


Twierdzenie L80
Nie istnieją złożone liczby nieparzyste [math]\displaystyle{ m }[/math] takie, że dla dowolnej liczby [math]\displaystyle{ a }[/math] względnie pierwszej z [math]\displaystyle{ m }[/math] jest

[math]\displaystyle{ a^{\tfrac{m - 1}{2}} \equiv \left( {\small\frac{a}{m}} \right)_{\small{\!\! J}} \!\! \pmod{m} }[/math]
Dowód

Przypuśćmy, dla otrzymania sprzeczności, że takie liczby istnieją i niech [math]\displaystyle{ m }[/math] będzie jedną z nich. Ponieważ z założonej kongruencji otrzymujemy

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

to [math]\displaystyle{ m }[/math] musi być liczbą Carmichaela. Wynika stąd, że [math]\displaystyle{ m }[/math] jest nieparzystą liczbą bezkwadratową i możemy napisać [math]\displaystyle{ m = p r }[/math], gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą i [math]\displaystyle{ \gcd (p, r) = 1 }[/math]. Niech [math]\displaystyle{ b }[/math] będzie dowolną liczbą niekwadratową modulo [math]\displaystyle{ p }[/math]. Z chińskiego twierdzenia o resztach (zobacz J3) wiemy, że istnieje dokładnie jedna taka liczba [math]\displaystyle{ c }[/math] (określona modulo [math]\displaystyle{ p r }[/math]), że prawdziwy jest układ kongruencji

[math]\displaystyle{ \begin{array}{l} c \equiv b \; \pmod{p} \\ c \equiv 1 \; \pmod{r} \\ \end{array} }[/math]

Ponieważ liczby [math]\displaystyle{ p }[/math] i [math]\displaystyle{ r }[/math] są względnie pierwsze, to (zobacz H8, H30)

[math]\displaystyle{ \gcd (c, m) = \gcd (c, p) \cdot \gcd (c, r) = \gcd (b, p) \cdot \gcd (1, r) = 1 }[/math]

Dla tak określonej liczby [math]\displaystyle{ c }[/math] łatwo obliczamy symbol Jacobiego (zobacz J42 p.4 i p.2)

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

Z uczynionego przez nas przypuszczenia wynika, że liczba [math]\displaystyle{ c }[/math] spełnia kongruencję

[math]\displaystyle{ c^{\tfrac{m - 1}{2}} \equiv \left( {\small\frac{c}{m}} \right)_{\small{\!\! J}} \equiv - 1 \!\! \pmod{m} }[/math]

Ale gdyby tak było, to mielibyśmy

[math]\displaystyle{ c^{\tfrac{m - 1}{2}} \equiv - 1 \!\! \pmod{r} }[/math]
[math]\displaystyle{ 1^{\tfrac{m - 1}{2}} \equiv - 1 \!\! \pmod{r} }[/math]

Co jest niemożliwe. Czyli przypuszczenie, że wszystkie liczby [math]\displaystyle{ a }[/math] względnie pierwsze z [math]\displaystyle{ m }[/math] spełniają kongruencję

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

jest fałszywe. Co należało pokazać.


Twierdzenie L81
Niech [math]\displaystyle{ m }[/math] będzie złożoną liczbą nieparzystą. Następujące warunki są równoważne

1. dla dowolnej liczby całkowitej [math]\displaystyle{ a }[/math] jest [math]\displaystyle{ a^m \equiv a \!\! \pmod{m} }[/math]
2. dla dowolnej liczby całkowitej [math]\displaystyle{ a }[/math] względnie pierwszej z [math]\displaystyle{ m }[/math] jest [math]\displaystyle{ a^{m - 1} \equiv 1 \!\! \pmod{m} }[/math]
3. [math]\displaystyle{ m }[/math] jest liczbą bezkwadratową i dla dowolnego dzielnika pierwszego [math]\displaystyle{ p }[/math] liczby [math]\displaystyle{ m }[/math] jest [math]\displaystyle{ (p - 1) \mid (m - 1) }[/math]
Dowód

Dowód przeprowadzimy, pokazując kolejno implikacje [math]\displaystyle{ 1 \Longrightarrow 2 \Longrightarrow 3 \Longrightarrow 1 }[/math]. Przypomnijmy, że liczby złożone są z definicji liczbami dodatnimi.

a) [math]\displaystyle{ \boldsymbol{1 \Longrightarrow 2} }[/math]

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

b) [math]\displaystyle{ \boldsymbol{2 \Longrightarrow 3} }[/math]

Ta implikacja została pokazana w twierdzeniu L78.

c) [math]\displaystyle{ \boldsymbol{3 \Longrightarrow 1} }[/math]

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

W przypadku gdy liczba pierwsza [math]\displaystyle{ p_i \nmid a }[/math], to z twierdzenia Fermata mamy

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

Ponieważ [math]\displaystyle{ (p_i - 1) \mid (m - 1) }[/math], to istnieje taka liczba naturalna [math]\displaystyle{ k }[/math], że [math]\displaystyle{ m - 1 = k \cdot (p_i - 1) }[/math], zatem

[math]\displaystyle{ a^{m - 1} = a^{k \cdot (p_i - 1)} = (a^{p_i - 1})^k \equiv 1^k \equiv 1 \!\! \pmod{p_i} }[/math]

Mnożąc obie strony kongruencji przez [math]\displaystyle{ a }[/math], otrzymujemy

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

W przypadku gdy liczba pierwsza [math]\displaystyle{ p_i \mid a }[/math], dostajemy

[math]\displaystyle{ a \equiv 0 \equiv a^m \!\! \pmod{p_i} }[/math]

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

Ponieważ liczby [math]\displaystyle{ p_i }[/math] są parami względnie pierwsze, to układ kongruencji [math]\displaystyle{ a^m \equiv a \!\! \pmod{p_i} }[/math] możemy połączyć (zobacz J1), otrzymując kongruencję równoważną

[math]\displaystyle{ a^m \equiv a \!\! \pmod{p_1 \cdot \ldots \cdot p_k} }[/math]

Co należało pokazać.


Twierdzenie L82
Jeżeli [math]\displaystyle{ m }[/math] jest liczbą Carmichaela, to

  •    dowolny czynnik pierwszy liczby [math]\displaystyle{ m }[/math] spełnia oszacowanie [math]\displaystyle{ p \lt \sqrt{m} }[/math]
  •    liczba [math]\displaystyle{ m }[/math] jest iloczynem przynajmniej trzech liczb pierwszych
Dowód

Punkt 1.

Niech [math]\displaystyle{ p }[/math] będzie dzielnikiem pierwszym [math]\displaystyle{ m }[/math]. Z twierdzenia L78 wiemy, że [math]\displaystyle{ m }[/math] jest liczbą bezkwadratową i [math]\displaystyle{ (p - 1) \mid (m - 1) }[/math], zatem [math]\displaystyle{ m = p r }[/math], gdzie [math]\displaystyle{ \gcd (p, r) = 1 }[/math]. Ponieważ

[math]\displaystyle{ m - 1 = p r - 1 = r (p - 1) + r - 1 }[/math]

to liczba [math]\displaystyle{ p - 1 }[/math] musi dzielić [math]\displaystyle{ r - 1 }[/math]. Wynika stąd, że [math]\displaystyle{ p - 1 \leqslant r - 1 }[/math], czyli [math]\displaystyle{ p^2 \leqslant r p = m }[/math], ale [math]\displaystyle{ m }[/math] jest liczbą bezkwadratową, zatem równość nie jest możliwa i musi być [math]\displaystyle{ p^2 \lt m }[/math].

Punkt 2.

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

[math]\displaystyle{ m - 1 = p q - 1 = (p - 1) q + (q - 1) }[/math]

Z uczynionego przypuszczenia wynika, że [math]\displaystyle{ p - 1 }[/math] dzieli [math]\displaystyle{ m - 1 }[/math], czyli [math]\displaystyle{ p - 1 }[/math] musi dzielić [math]\displaystyle{ q - 1 }[/math], co jest niemożliwe dla [math]\displaystyle{ p \gt q }[/math].


Twierdzenie L83 (Jack Chernick[14], 1939)
Niech [math]\displaystyle{ k \in \mathbb{Z}_+ }[/math]. Następujące warunki są równoważne

  •    jeżeli każda z liczb [math]\displaystyle{ 6 k + 1 }[/math], [math]\displaystyle{ 12 k + 1 }[/math], [math]\displaystyle{ 18 k + 1 }[/math] jest liczbą pierwszą, to ich iloczyn jest liczbą Carmichaela
  •    jeżeli każda z liczb [math]\displaystyle{ p }[/math], [math]\displaystyle{ 2 p - 1 }[/math], [math]\displaystyle{ 3 p - 2 }[/math] jest liczbą pierwszą, to ich iloczyn jest liczbą Carmichaela
Dowód

Punkt 1.

Jeżeli liczby [math]\displaystyle{ 6 k + 1 }[/math], [math]\displaystyle{ 12 k + 1 }[/math], [math]\displaystyle{ 18 k + 1 }[/math] są liczbami pierwszymi oraz liczba [math]\displaystyle{ a }[/math] jest względnie pierwsza z każdą z tych liczb, to z twierdzenia Fermata mamy

[math]\displaystyle{ a^{6 k} \equiv 1 \!\! \pmod{6 k + 1} \qquad \qquad \:\, a^{12 k} \equiv 1 \!\! \pmod{12 k + 1} \qquad \qquad a^{18 k} \equiv 1 \!\! \pmod{18 k + 1} }[/math]

Podnosząc obie strony wypisanych wyżej kongruencji do potęgi o wykładniku [math]\displaystyle{ 6 }[/math], [math]\displaystyle{ 3 }[/math] i [math]\displaystyle{ 2 }[/math], dostajemy

[math]\displaystyle{ a^{36 k} \equiv 1 \!\! \pmod{6 k + 1} \qquad \qquad a^{36 k} \equiv 1 \!\! \pmod{12 k + 1} \qquad \qquad a^{36 k} \equiv 1 \!\! \pmod{18 k + 1} }[/math]

Ale liczby [math]\displaystyle{ 6 k + 1 }[/math], [math]\displaystyle{ 12 k + 1 }[/math], [math]\displaystyle{ 18 k + 1 }[/math] są z założenia różnymi liczbami pierwszymi, zatem są parami względnie pierwsze i powyższy układ kongruencji możemy połączyć (zobacz J1), otrzymując kongruencję równoważną

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

gdzie [math]\displaystyle{ m = (6 k + 1) (12 k + 1) (18 k + 1) }[/math]. Łatwo obliczamy

[math]\displaystyle{ m - 1 = 1296 k^3 + 396 k^2 + 36 k = 36 k (36 k^2 + 11 k + 1) = 36 k \cdot s }[/math]

i dostajemy, że

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

Zauważmy jeszcze, że liczba [math]\displaystyle{ a }[/math] jest względnie pierwsza z [math]\displaystyle{ m }[/math]. Co należało pokazać.

Punkt 2.

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



Kryteria pierwszości Lucasa i Pocklingtona

Uwaga L84
Aby ułatwić Czytelnikowi zrozumienie tematu, rozpoczniemy od problemów związanych z terminologią. Będziemy nazywali testem pierwszości twierdzenie, które co do zasady pozwala określić jedynie pewne prawdopodobieństwo, że badana liczba jest liczbą pierwszą. Przykładem może być tutaj test Fermata, który wykorzystuje twierdzenie Fermata (zobacz J22).

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

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

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

Jeżeli liczba [math]\displaystyle{ m \gt 0 }[/math] nie jest podzielna przez żadną liczbę pierwszą [math]\displaystyle{ p \leqslant \sqrt{m} }[/math], to [math]\displaystyle{ m }[/math] jest liczbą pierwszą.

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


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

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

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


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


Twierdzenie L85 (kryterium pierwszości Lucasa, Derrick Henry Lehmer[16], 1927)
Niech [math]\displaystyle{ m \geqslant 3 }[/math] będzie liczbą całkowitą nieparzystą. Liczba [math]\displaystyle{ m }[/math] jest liczbą pierwszą wtedy i tylko wtedy, gdy istnieje taka liczba całkowita [math]\displaystyle{ a }[/math], że spełnione są warunki

  •    [math]\displaystyle{ a^{m - 1} \equiv 1 \!\! \pmod{m} }[/math]
  •    dla każdego dzielnika pierwszego [math]\displaystyle{ q }[/math] liczby [math]\displaystyle{ m - 1 }[/math] jest
[math]\displaystyle{ a^{\tfrac{m - 1}{q}} \not\equiv 1 \!\! \pmod{m} }[/math]
Dowód

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

Z założenia [math]\displaystyle{ m }[/math] jest liczbą pierwszą nieparzystą, zatem istnieje liczba [math]\displaystyle{ a }[/math], która jest generatorem modulo [math]\displaystyle{ m }[/math]. Z definicji generatora jest spełniony pierwszy warunek

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

Gdyby dla pewnego dzielnika pierwszego [math]\displaystyle{ q }[/math] liczby [math]\displaystyle{ m - 1 }[/math] było

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

to mielibyśmy

[math]\displaystyle{ \operatorname{ord}(a, m) \leqslant {\small\frac{m - 1}{q}} \lt m - 1 }[/math]

Wbrew temu, że [math]\displaystyle{ a }[/math] jest generatorem modulo [math]\displaystyle{ m }[/math].

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

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

[math]\displaystyle{ m - 1 = \operatorname{ord}(a, m) \leqslant \varphi (m) \leqslant m - 1 }[/math]

Skąd natychmiast wynika, że [math]\displaystyle{ \varphi (m) = m - 1 }[/math]. Zatem [math]\displaystyle{ m }[/math] jest liczbą pierwszą (zobacz H43). Co należało pokazać.


Uwaga L86
Zauważmy też, że problem dowodu pierwszości liczby [math]\displaystyle{ m }[/math], został przeniesiony na znalezienie faktoryzacji liczby [math]\displaystyle{ m - 1 }[/math], co w ogólnym przypadku może nie być łatwe, ale w przypadku liczb o szczególnej postaci może być bardzo proste.


Zadanie L87
Niech [math]\displaystyle{ n \in \mathbb{Z}_+ }[/math]. Pokazać, że liczba Fermata [math]\displaystyle{ F_n = 2^{2^{\large n}} + 1 }[/math] jest liczbą pierwszą wtedy i tylko wtedy, gdy

[math]\displaystyle{ 3^{(F_n - 1) / 2} \equiv - 1 \!\! \pmod{F_n} }[/math]
Rozwiązanie

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

Zauważmy, że dla [math]\displaystyle{ n \geqslant 1 }[/math] jest

[math]\displaystyle{ F_n = 2^{2^{\large n}} + 1 \equiv (- 1)^{2^{\large n}} + 1 \equiv 2 \!\! \pmod{3} }[/math]
[math]\displaystyle{ F_n = 2^{2^{\large n}} + 1 = 4 \cdot 2^{2^{\large n} - 2} + 1 \equiv 1 \!\! \pmod{4} }[/math]

Jeżeli [math]\displaystyle{ F_n }[/math] jest liczbą pierwszą, to z kryterium Eulera (zobacz J31 i J33) wiemy, że

[math]\displaystyle{ 3^{(F_n - 1) / 2} \equiv \left( {\small\frac{3}{F_n}} \right)_{\small{\!\! J}} \!\! \pmod{F_n} }[/math]

Ponieważ [math]\displaystyle{ F_n \equiv 1 \!\! \pmod{4} }[/math], to z twierdzenia J42 p.9 dostajemy

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

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

Z założenia

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

Podnosząc obie strony kongruencji do kwadratu, dostajemy

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

Widzimy, że spełnione są założenia kryterium Lucasa (L85), zatem [math]\displaystyle{ F_n }[/math] jest liczbą pierwszą.


Uwaga L88
Jeżeli stosując kryterium Lucasa, otrzymamy rezultat pozytywny (czyli [math]\displaystyle{ m }[/math] jest liczbą pierwszą), to liczba [math]\displaystyle{ a }[/math] jest generatorem modulo [math]\displaystyle{ m }[/math]. Co oznacza, że aby potwierdzić pierwszość liczby [math]\displaystyle{ m }[/math] liczba [math]\displaystyle{ a }[/math] musi być generatorem.

Na szczęście najmniejsze dodatnie generatory [math]\displaystyle{ \mathbb{g} (p) }[/math] są niewielkimi liczbami (zobacz L65) i przypuszczamy, że [math]\displaystyle{ \mathbb{g} (p) }[/math] jest rzędu [math]\displaystyle{ \log^6 \! p }[/math][17]. Jednak dla liczb pierwszych rzędu [math]\displaystyle{ 10^{100} }[/math] liczba [math]\displaystyle{ \log^6 \! p }[/math] jest rzędu [math]\displaystyle{ 10^{14} }[/math].

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

[math]\displaystyle{ 29, 37, 41, 58, 73, 74, 82, 83, 87, 97, 101, 103, 107, 111 }[/math]

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


Twierdzenie L89 (kryterium pierwszości Lucasa, John Lewis Selfridge[18], 1967)
Niech [math]\displaystyle{ m \geqslant 3 }[/math] będzie liczbą całkowitą nieparzystą. Liczba [math]\displaystyle{ m }[/math] jest liczbą pierwszą wtedy i tylko wtedy, gdy dla każdego dzielnika pierwszego [math]\displaystyle{ q_i }[/math] liczby [math]\displaystyle{ m - 1 }[/math] istnieje taka liczba całkowita [math]\displaystyle{ a_i }[/math], że

  •    [math]\displaystyle{ (a_i)^{m - 1} \equiv 1 \!\! \pmod{m} }[/math]
  •    [math]\displaystyle{ (a_i)^{\tfrac{m - 1}{q_i}} \not\equiv 1 \!\! \pmod{m} }[/math]
Dowód

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

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

[math]\displaystyle{ (a_i)^{\tfrac{m - 1}{q_i}} \equiv 1 \!\! \pmod{m} }[/math]

to mielibyśmy

[math]\displaystyle{ \operatorname{ord}(a_i, m) \leqslant {\small\frac{m - 1}{q_i}} \lt m - 1 }[/math]

Wbrew temu, że [math]\displaystyle{ a_i }[/math] jest generatorem modulo [math]\displaystyle{ m }[/math].

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

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

Zdefiniujmy odpowiadające liczbom [math]\displaystyle{ a_i }[/math] liczby [math]\displaystyle{ b_i }[/math] następująco

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

Łatwo widzimy, że

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

Z twierdzenia L25 otrzymujemy natychmiast, że [math]\displaystyle{ \operatorname{ord}(b_i, m) = q^{\alpha_i}_i }[/math]. Zatem [math]\displaystyle{ q^{\alpha_i}_i \mid \varphi (m) }[/math] (zobacz L9). Ponieważ jest tak dla dowolnego [math]\displaystyle{ i = 1, \ldots, s }[/math], to [math]\displaystyle{ (m - 1) \mid \varphi (m) }[/math]. Zatem [math]\displaystyle{ \varphi (m) = m - 1 }[/math] i [math]\displaystyle{ m }[/math] jest liczbą pierwszą (zobacz H43). Co należało pokazać.


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

[math]\displaystyle{ m - 1 = 2^3 \cdot 3^2 \cdot 5 \cdot 7 \cdot 17 \cdot 1051 }[/math]

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


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


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


Przykład L91
Trudniejszy przykład. Weźmy zupełnie przypadkową, dużą liczbę pierwszą. Wpisując w PARI/GP polecenie m = nextprime(10^100), dostajemy [math]\displaystyle{ m = 10^{100} + 267 }[/math]. Faktoryzacja liczby [math]\displaystyle{ m - 1 }[/math] ma postać

[math]\displaystyle{ m - 1 = 2 \cdot 3 \cdot 334667 \cdot 30887585377354279775821 \cdot 6992177388736382392966730145791 \cdot 23058946541016687800969797051238966440903 }[/math]

Oznaczmy kolejne dzielniki pierwsze liczby [math]\displaystyle{ m - 1 }[/math] przez [math]\displaystyle{ q_1, \ldots, q_6 }[/math].


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


Kryterium Lucasa potwierdziło, że [math]\displaystyle{ m }[/math] jest liczbą pierwszą. Nie jesteśmy zaskoczeni, ale należy pamiętać, że szukając następnej liczby pierwszej, PARI/GP wykonuje jedynie test BPSW. Tylko polecenie isprime() testuje pierwszość liczby bardzo dokładnie.


Przykład L92
Na podstawie twierdzenia L89 możemy napisać prosty program, który sprawdza, czy badana liczba jest pierwsza.

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


Przykład L93
Przykład liczb Carmichaela. Korzystając z programu, łatwo zauważymy, że są to liczby, z którymi kryterium Lucasa ma problem. W przypadku, gdy najmniejszy czynnik pierwszy takiej liczby jest dostatecznie duży, nie zdołamy wykryć, że badana liczba jest złożona, obliczając kolejne największe wspólne dzielniki. Liczbą Carmichaela jest [math]\displaystyle{ m = 252601 = 41 \cdot 61 \cdot 101 }[/math]. Liczba [math]\displaystyle{ m - 1 }[/math] ma następujący rozkład na czynniki pierwsze

[math]\displaystyle{ m - 1 = 252600 = 2^3 \cdot 3 \cdot 5^2 \cdot 421 }[/math]


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


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

[math]\displaystyle{ m = 8634001244918264082478118310255990038094844114723238926749605521 }[/math]
[math]\displaystyle{ m = 1128981829489795224271 \cdot 2257963658979590448541 \cdot 3386945488469385672811 }[/math]
[math]\displaystyle{ m - 1 = 2^4 \cdot 3^3 \cdot 5 \cdot 13 \cdot 29 \cdot 101 \cdot 197 \cdot 14537 \cdot 920729 \cdot 432560087927124607 \cdot 92039944498124001503569633 }[/math]


Uwaga L94
Kryterium Lucasa możemy zmodyfikować tak, aby można było je stosować w przypadku, gdy nie są znane wszystkie dzielniki pierwsze liczby [math]\displaystyle{ m - 1 }[/math].


Twierdzenie L95 (kryterium Pocklingtona[19], 1914)
Niech [math]\displaystyle{ m \geqslant 3 }[/math] będzie liczbą nieparzystą i [math]\displaystyle{ m = F R + 1 }[/math], gdzie [math]\displaystyle{ \gcd (F, R) = 1 }[/math] oraz faktoryzacja liczby [math]\displaystyle{ F }[/math] jest znana. Jeżeli [math]\displaystyle{ F \gt \sqrt{m} - 1 }[/math] i dla każdego dzielnika pierwszego [math]\displaystyle{ q_i }[/math] liczby [math]\displaystyle{ F }[/math] istnieje liczba [math]\displaystyle{ a_i }[/math] taka, że

  •    [math]\displaystyle{ (a_i)^{m - 1} \equiv 1 \!\! \pmod{m} }[/math]
  •    [math]\displaystyle{ \gcd \left( (a_i)^{\tfrac{m - 1}{q_i}} - 1, m \right) = 1 }[/math]

to [math]\displaystyle{ m }[/math] jest liczbą pierwszą.

Dowód

Nim przejdziemy do dowodu, zauważmy, że będą nam potrzebne kongruencje modulo dzielnik pierwszy [math]\displaystyle{ p }[/math] liczby [math]\displaystyle{ m }[/math] (w dowodzie twierdzenia L76 nie było takiej potrzeby). Dlatego konieczne było wzmocnienie założenia i zamiast [math]\displaystyle{ (a_i)^{(m - 1)/q_i} \not\equiv 1 \!\! \pmod{m} }[/math] mamy [math]\displaystyle{ \gcd \left( (a_i)^{(m - 1)/q_i} - 1, m \right) = 1 }[/math].


Z założenia faktoryzacja liczby [math]\displaystyle{ F }[/math] jest znana i możemy napisać [math]\displaystyle{ F = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s }[/math]. Niech [math]\displaystyle{ p }[/math] będzie dowolnym dzielnikiem pierwszym liczby [math]\displaystyle{ m }[/math]. Zatem [math]\displaystyle{ m = k p^u }[/math], gdzie [math]\displaystyle{ \gcd (k, p^u) = 1 }[/math] i z założonych warunków wynika, że (zobacz H8, H30)

[math]\displaystyle{ (a_i)^{m - 1} \equiv 1 \!\! \pmod{p^u} }[/math]
[math]\displaystyle{ \gcd \left( (a_i)^{\tfrac{m - 1}{q_i}} - 1, p^u \right) = 1 }[/math]

Skąd dostajemy natychmiast

[math]\displaystyle{ (a_i)^{m - 1} \equiv 1 \!\! \pmod{p} }[/math]
[math]\displaystyle{ \gcd \left( (a_i)^{\tfrac{m - 1}{q_i}} - 1, p \right) = 1 }[/math]

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

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

Jeżeli zdefiniujemy liczby [math]\displaystyle{ b_i }[/math] następująco

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

to łatwo zauważymy, że

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

i z twierdzenia L25 wynika, że [math]\displaystyle{ \operatorname{ord}(b_i, p) = q_i^{\alpha_i} }[/math].

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

[math]\displaystyle{ p^2 = (k F + 1)^2 \geqslant (F + 1)^2 \gt \left( \sqrt{m} \right)^2 = m }[/math]

bo z założenia [math]\displaystyle{ F \gt \sqrt{m} - 1 }[/math]. Ponieważ [math]\displaystyle{ p }[/math] jest dowolnym czynnikiem pierwszym liczby [math]\displaystyle{ m }[/math], to nierówność [math]\displaystyle{ p^2 \gt m }[/math] oznacza, że [math]\displaystyle{ m }[/math] jest liczbą pierwszą. Co należało pokazać.


Przykład L96
Niech [math]\displaystyle{ m = 9024713281 }[/math]. Widzimy, że liczba [math]\displaystyle{ m - 1 }[/math] jest podzielna przez [math]\displaystyle{ 2, 3, 5, 11 }[/math]. Łatwo ustalamy wykładniki tych liczb i dostajemy

[math]\displaystyle{ m - 1 = 9024713280 = 2^6 \cdot 3^3 \cdot 5 \cdot 11 \cdot R }[/math]

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


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


Zatem [math]\displaystyle{ m }[/math] jest liczbą pierwszą.



Kongruencje wielomianowe

Definicja L97
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 L98
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 L99
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 L100
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 L101
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 L102
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ń L100, L98 i L101.

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 L100:   [math]\displaystyle{ | S_{n, a} | = | S_{d, a} | }[/math]

Z twierdzenia L98:   [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 L101:   [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ń L100, L98 i L101, 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 L100 wynika, że [math]\displaystyle{ | S_{d, a} | = | S_{n, a} | }[/math]. Z twierdzeń L98 i L101 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 L103
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 L104
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 L125), 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 L105
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 L106
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 L107
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 L108
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 L109
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 L110
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 L111
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 L125), 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 L112
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 L113
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 L114
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 L113, 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 L115
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 L116
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 L125), 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 L117
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 L114 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 L118 (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 L117)

[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 L125) 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 L119
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


Zadanie L120
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 L119.

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


Z lematu Hensela wynika natychmiast.
Twierdzenie L121
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 L122
Pokazaliśmy (zobacz L115), ż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 L115) i przy tym założeniu istnieje rozwiązanie kongruencji [math]\displaystyle{ x^r \equiv a \!\! \pmod{p^n} }[/math].



Uzupełnienie

Twierdzenie L123
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 L124
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 L125
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 L126
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 L125)

[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 L118).

[math]\displaystyle{ f(x) = 3 x - 2 \qquad \qquad f' (x) = 3 }[/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].








Przypisy

  1. ang. order of [math]\displaystyle{ a }[/math] modulo [math]\displaystyle{ m }[/math]
  2. Niekiedy do tej listy dodaje się liczbę [math]\displaystyle{ 1 }[/math], dla której każda liczba całkowita jest generatorem: [math]\displaystyle{ \varphi (1) = 1 }[/math], [math]\displaystyle{ \gcd (a, 1) = 1 }[/math], [math]\displaystyle{ a^1 \equiv 1 \!\! \pmod{1} }[/math].
  3. ang. generator or primitive root modulo [math]\displaystyle{ m }[/math]
  4. P. D. T. A. Elliott and Leo Murata, On the average of the least primitive root modulo p, Journal of the London Mathematical Society, vol. 56, no. 2, pp. 435-454, 1997
  5. Tomás Oliveira e Silva, Least primitive root of prime numbers, (LINK)
  6. Stephen D. Cohen, Tomás Oliveira e Silva and Tim Trudgian, On Grosswald's conjecture on primitive roots, Acta Arithmetica (2016), Volume: 172, Issue: 3, page 263-270
  7. Kevin J. McGown and Tim Trudgian, Explicit upper bounds on the least primitive root, Proc. Amer. Math. Soc. 148 (2020), no. 3, 1049-1061.
  8. Victor-Amédée Lebesgue, Théorème sur les racines primitives, Comptes rendus des séances de l'Académie des Sciences LXIV (24 June 1867), 1268-1269.
  9. John Maxfield and Margaret Maxfield, The Existence of Integers Less than p Belonging to epr-1 (mod pr), Mathematics Magazine, Vol. 33, No. 4 (Mar. - Apr., 1960), pp. 219-220
  10. liczba bezkwadratowa (ang. squarefree integer or square-free integer)
  11. W. R. Alford, Andrew Granville and Carl Pomerance, There are Infinitely Many Carmichael Numbers, Annals of Mathematics, 140, (1994), 703-722
  12. Glyn Harman, On the Number of Carmichael Numbers up to x, Bull. London Math. Soc. 37 (2005) 641–650
  13. Glyn Harman, Watt’s Mean Value Theorem and Carmichael Numbers, International Journal of Number Theory, Vol. 4, No. 2 (2008) 241–248
  14. Jack Chernick, On Fermat's simple theorem, Bulletin of the American Mathematical Society, vol. 45(4), 1939, 269-274
  15. O ile liczba [math]\displaystyle{ m }[/math] nie jest liczbą Carmichaela.
  16. Derrick Henry Lehmer, Tests for primality by the converse of Fermat's theorem, Bulletin of the American Mathematical Society, vol. 33 (1927), 327-340.
  17. Victor Shoup, Searching for primitive roots in finite fields, Mathematics of Computation 58 (1992), 369-380.
  18. John Brillhart and John Lewis Selfridge, Some factorizations of 2n ± 1 and related results, Mathematics of Computation, 21 (1967), 87-96.
  19. Henry Cabourn Pocklington, The determination of the prime or composite nature of large numbers by Fermat's theorem, Proceedings of the Cambridge Philosophical Society, vol. 18 (1914–1916), 29-30.