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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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



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]

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

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

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


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

Rozwiązanie


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

Dowód


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


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


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


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


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


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


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 C49).

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


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


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


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


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


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


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


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


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


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


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


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


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


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


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


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

 

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

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

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


Ponieważ [math]\displaystyle{ \mathbb{g} (p) \geqslant \mathbb{n} (p) }[/math], to z twierdzenia K18 otrzymujemy natychmiast, że istnieje niekończenie wiele liczb pierwszych [math]\displaystyle{ p }[/math] takich, że najmniejszy generator modulo [math]\displaystyle{ p }[/math] jest większy od [math]\displaystyle{ {\small\frac{\log p}{2 L \log 2}} }[/math], gdzie [math]\displaystyle{ L }[/math] jest stałą Linnika (zobacz C31). 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


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


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


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


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


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]

[math]\displaystyle{ 561=3⋅11⋅17 }[/math] [math]\displaystyle{ 1105=5⋅13⋅17 }[/math] [math]\displaystyle{ 1729=7⋅13⋅19 }[/math] [math]\displaystyle{ 2465=5⋅17⋅29 }[/math]
[math]\displaystyle{ 2821=7⋅13⋅31 }[/math] [math]\displaystyle{ 6601=7⋅23⋅41 }[/math] [math]\displaystyle{ 8911=7⋅19⋅67 }[/math] [math]\displaystyle{ 10585=5⋅29⋅73 }[/math]
[math]\displaystyle{ 15841=7⋅31⋅73 }[/math] [math]\displaystyle{ 29341=13⋅37⋅61 }[/math] [math]\displaystyle{ 41041=7⋅11⋅13⋅41 }[/math] [math]\displaystyle{ 46657=13⋅37⋅97 }[/math]
[math]\displaystyle{ 52633=7⋅73⋅103 }[/math] [math]\displaystyle{ 62745=3⋅5⋅47⋅89 }[/math] [math]\displaystyle{ 63973=7⋅13⋅19⋅37 }[/math] [math]\displaystyle{ 75361=11⋅13⋅17⋅31 }[/math]


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

Rozwiązanie


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


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


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


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


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



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


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


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


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


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


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


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


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


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


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

Rozwiązanie


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


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


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


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


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


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



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


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


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


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


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


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

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


Zadanie 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


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


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


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


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]
[math]\displaystyle{ \;\; \boldsymbol{n} \;\; }[/math] [math]\displaystyle{ \;\; \boldsymbol{\alpha} \;\; }[/math] [math]\displaystyle{ \boldsymbol{f (\alpha)} }[/math] [math]\displaystyle{ \boldsymbol{f' (\alpha)} }[/math] [math]\displaystyle{ \boldsymbol{k f' (\alpha) \equiv - {\small\frac{f (\alpha)}{5^n}} \!\! \pmod{5}} }[/math] [math]\displaystyle{ \boldsymbol{k \!\! \pmod{5}} }[/math] [math]\displaystyle{ \boldsymbol{\beta \equiv \alpha + k \cdot 5^n \!\! \pmod{5^{n + 1}}} }[/math]
[math]\displaystyle{ 1 }[/math] [math]\displaystyle{ 4 }[/math] [math]\displaystyle{ 10 = 5^n \cdot 2 }[/math] [math]\displaystyle{ 3 }[/math] [math]\displaystyle{ 3 k \equiv 3 \!\! \pmod{5} }[/math] [math]\displaystyle{ 1 }[/math] [math]\displaystyle{ 4 + 1 \cdot 5^n \equiv 9 }[/math]

Zauważmy, że [math]\displaystyle{ k }[/math] jest określone modulo [math]\displaystyle{ 5 }[/math], ale możemy je w tym przypadku wstawić do kongruencji określonej modulo [math]\displaystyle{ 25 }[/math], bo modulo [math]\displaystyle{ 25 }[/math] mielibyśmy [math]\displaystyle{ k \equiv 1 + 5 t }[/math], gdzie [math]\displaystyle{ t = 0, 1, 2, 3, 4 }[/math] i niezależnie od wyboru wartości liczby [math]\displaystyle{ t }[/math] otrzymujemy [math]\displaystyle{ \beta \equiv \alpha + k \cdot 5 \equiv 4 + (1 + 5 t) \cdot 5 \equiv 4 + 5 + 25 t \equiv 9 \!\! \pmod{25} }[/math].








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.












 

Źródło: „https://henryk-dabrowski.pl/index.php?title=Rząd_liczby_modulo_i_generatory_modulo._Kongruencje_wielomianowe._Lemat_Hensela&oldid=829”