Testy pierwszości. Liczby pseudopierwsze Lucasa i liczby silnie pseudopierwsze Lucasa. Test BPSW: Różnice pomiędzy wersjami

Aktualna wersja na dzień 18:40, 17 mar 2024

11.01.2023

Ciągi Lucasa

Definicja N1
Niech [math]\displaystyle{ P, Q \in \mathbb{Z} \setminus \{0\} }[/math] oraz [math]\displaystyle{ D = P^2 - 4 Q \neq 0 }[/math]. Ciągi Lucasa [math]\displaystyle{ U_n = U_n (P, Q) }[/math] i [math]\displaystyle{ V_n = V_n (P, Q) }[/math] definiujemy następująco

[math]\displaystyle{ U_n = {\small\frac{\alpha^n - \beta^n}{\alpha - \beta}} = {\small\frac{\alpha^n - \beta^n}{\sqrt{D}}} }[/math]

[math]\displaystyle{ V_n = \alpha^n + \beta^n }[/math]

gdzie liczby

[math]\displaystyle{ \alpha = {\small\frac{P + \sqrt{D}}{2}} }[/math]

[math]\displaystyle{ \beta = {\small\frac{P - \sqrt{D}}{2}} }[/math]

są pierwiastkami równania [math]\displaystyle{ x^2 - P x + Q = 0 }[/math].

Uwaga N2
Zauważmy, że:

[math]\displaystyle{ P = \alpha + \beta }[/math]

[math]\displaystyle{ Q = \alpha \beta }[/math]

[math]\displaystyle{ \sqrt{D} = \alpha - \beta }[/math]

[math]\displaystyle{ U_0 = 0 }[/math], [math]\displaystyle{ U_1 = 1 }[/math], [math]\displaystyle{ V_0 = 2 }[/math] i [math]\displaystyle{ V_1 = P }[/math]

Warunek [math]\displaystyle{ P^2 - 4 Q \neq 0 }[/math] wyklucza następujące pary [math]\displaystyle{ (P, Q) }[/math]

[math]\displaystyle{ (0, 0), (\pm 2, 1), (\pm 4, 4), (\pm 6, 9), (\pm 8, 16), (\pm 10, 25), (\pm 12, 36), ..., (\pm 2 n, n^2), ... }[/math]

Uwaga N3
Oczywiście liczby [math]\displaystyle{ \alpha }[/math] i [math]\displaystyle{ \beta }[/math] są również pierwiastkami równania

[math]\displaystyle{ x^{n + 2} - P x^{n + 1} + Q x^n = 0 }[/math]

Wynika stąd, że ciągi [math]\displaystyle{ (\alpha^n) }[/math] i [math]\displaystyle{ (\beta^n) }[/math] spełniają równania rekurencyjne

[math]\displaystyle{ \alpha^{n + 2} = P \alpha^{n + 1} - Q \alpha^n }[/math]

[math]\displaystyle{ \beta^{n + 2} = P \beta^{n + 1} - Q \beta^n }[/math]

Ciągi Lucasa [math]\displaystyle{ (U_n) }[/math] i [math]\displaystyle{ (V_n) }[/math] spełniają identyczne równania rekurencyjne jak ciągi [math]\displaystyle{ (\alpha^n) }[/math] i [math]\displaystyle{ (\beta^n) }[/math]. Istotnie, odejmując i dodając stronami wypisane powyżej równania, otrzymujemy

[math]\displaystyle{ U_{n + 2} = P U_{n + 1} - Q U_n }[/math]

[math]\displaystyle{ V_{n + 2} = P V_{n + 1} - Q V_n }[/math]

Dlatego możemy zdefiniować ciągi Lucasa [math]\displaystyle{ (U_n) }[/math] i [math]\displaystyle{ (V_n) }[/math] w sposób równoważny

Definicja N4
Niech [math]\displaystyle{ P, Q \in \mathbb{Z} \setminus \{0\} }[/math] oraz [math]\displaystyle{ D = P^2 - 4 Q \neq 0 }[/math]. Ciągi Lucasa [math]\displaystyle{ (U_n) }[/math] i [math]\displaystyle{ (V_n) }[/math] określone są następującymi wzorami rekurencyjnymi

[math]\displaystyle{ U_0 = 0 }[/math], [math]\displaystyle{ U_1 = 1 }[/math], [math]\displaystyle{ U_n = P U_{n - 1} - Q U_{n - 2} }[/math]

[math]\displaystyle{ V_0 = 2 }[/math], [math]\displaystyle{ V_1 = P }[/math], [math]\displaystyle{ V_n = P V_{n - 1} - Q V_{n - 2} }[/math]

Przykład N5
Początkowe wyrazy ciągów Lucasa

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ \boldsymbol{U_n (P, Q)} }[/math]	[math]\displaystyle{ \boldsymbol{V_n (P, Q)} }[/math]
[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 2 }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ P }[/math]
[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ P }[/math]	[math]\displaystyle{ P^2 - 2 Q }[/math]
[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ P^2 - Q }[/math]	[math]\displaystyle{ P^3 - 3 P Q }[/math]
[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ P^3 - 2 P Q }[/math]	[math]\displaystyle{ P^4 - 4 P^2 Q + 2 Q^2 }[/math]
[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ P^4 - 3 P^2 Q + Q^2 }[/math]	[math]\displaystyle{ P^5 - 5 P^3 Q + 5 P Q^2 }[/math]
[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ P^5 - 4 P^3 Q + 3 P Q^2 }[/math]	[math]\displaystyle{ P^6 - 6 P^4 Q + 9 P^2 Q^2 - 2 Q^3 }[/math]
[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ P^6 - 5 P^4 Q + 6 P^2 Q^2 - Q^3 }[/math]	[math]\displaystyle{ P^7 - 7 P^5 Q + 14 P^3 Q^2 - 7 P Q^3 }[/math]
[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ P^7 - 6 P^5 Q + 10 P^3 Q^2 - 4 P Q^3 }[/math]	[math]\displaystyle{ P^8 - 8 P^6 Q + 20 P^4 Q^2 - 16 P^2 Q^3 + 2 Q^4 }[/math]
[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ P^8 - 7 P^6 Q + 15 P^4 Q^2 - 10 P^2 Q^3 + Q^4 }[/math]	[math]\displaystyle{ P^9 - 9 P^7 Q + 27 P^5 Q^2 - 30 P^3 Q^3 + 9 P Q^4 }[/math]

Uwaga N6
W PARI/GP możemy napisać prosty kod, który pozwoli obliczyć wartości wyrazów [math]\displaystyle{ U_n (P, Q) }[/math] i [math]\displaystyle{ V_n (P, Q) }[/math]

LucasU(n, P, Q) = if( n == 0, 0, if( n == 1, 1, P*LucasU(n-1, P, Q) - Q*LucasU(n-2, P, Q) ) )

LucasV(n, P, Q) = if( n == 0, 2, if( n == 1, P, P*LucasV(n-1, P, Q) - Q*LucasV(n-2, P, Q) ) )

Twierdzenie N7
Niech [math]\displaystyle{ D = P^2 - 4 Q }[/math]. Wyrazy ciągów Lucasa można przedstawić w postaci sumy

[math]\displaystyle{ 2^{n - 1} U_n = \sum_{k = 0}^{\lfloor (n - 1) / 2 \rfloor} \binom{n}{2 k + 1} P^{n - 2 k - 1} D^k }[/math]

[math]\displaystyle{ 2^{n - 1} V_n = \sum_{k = 0}^{\lfloor n / 2 \rfloor} \binom{n}{2 k} P^{n - 2 k} D^k }[/math]

Dowód

Oznaczmy [math]\displaystyle{ \delta = \sqrt{D} }[/math], zatem [math]\displaystyle{ 2 \alpha = P + \delta }[/math] i [math]\displaystyle{ 2 \beta = P - \delta }[/math]. Ze wzoru dwumianowego, mamy

[math]\displaystyle{ 2^n \alpha^n = (P + \delta)^n = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} \delta^j }[/math]

[math]\displaystyle{ 2^n \beta^n = (P - \delta)^n = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (- \delta)^j }[/math]

Obliczając sumę powyższych wzorów, otrzymujemy

[math]\displaystyle{ 2^n (\alpha^n + \beta^n) = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (\delta^j + (- \delta)^j) }[/math]

[math]\displaystyle{ \quad \: = \sum_{k = 0}^{\lfloor n / 2 \rfloor} \binom{n}{2 k} P^{n - 2 k} \cdot 2 \delta^{2 k} }[/math]

[math]\displaystyle{ \quad \: = 2 \sum_{k = 0}^{\lfloor n / 2 \rfloor} \binom{n}{2 k} P^{n - 2 k} D^k }[/math]

gdzie [math]\displaystyle{ j = 2 k }[/math] i sumowanie przebiega od [math]\displaystyle{ k = 0 }[/math] do [math]\displaystyle{ k = \lfloor n / 2 \rfloor }[/math]

Zatem

[math]\displaystyle{ 2^{n - 1} V_n = \sum_{k = 0}^{\lfloor n / 2 \rfloor} \binom{n}{2 k} P^{n - 2 k} D^k }[/math]

Obliczając różnicę tych wzorów, mamy

[math]\displaystyle{ 2^n (\alpha^n - \beta^n) = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (\delta^j - (- \delta)^j) }[/math]

[math]\displaystyle{ \quad \: = \sum_{k = 0}^{\lfloor (n - 1) / 2 \rfloor} \binom{n}{2 k + 1} P^{n - 2 k - 1} \cdot 2 \delta^{2 k + 1} }[/math]

[math]\displaystyle{ \quad \: = 2 \delta \sum_{k = 0}^{\lfloor (n - 1) / 2 \rfloor} \binom{n}{2 k + 1} P^{n - 2 k - 1} D^k }[/math]

gdzie [math]\displaystyle{ j = 2 k + 1 }[/math] i sumowanie przebiega od [math]\displaystyle{ k = 0 }[/math] do [math]\displaystyle{ k = \lfloor (n - 1) / 2 \rfloor }[/math]

Zatem

[math]\displaystyle{ 2^{n - 1} \cdot {\small\frac{\alpha^n - \beta^n}{\sqrt{D}}} = 2^{n - 1} U_n = \sum_{k = 0}^{\lfloor (n - 1) / 2 \rfloor} \binom{n}{2 k + 1} P^{n - 2 k - 1} D^k }[/math]

Co należało pokazać.
□

Uwaga N8
Korzystając z twierdzenia N7, możemy napisać proste funkcje do znajdowania postaci kolejnych wyrazów [math]\displaystyle{ U_n (P, Q) }[/math] i [math]\displaystyle{ V_n (P, Q) }[/math]

U(n) = 2^(1 - n)*sum(k=0, floor((n-1)/2), binomial(n, 2*k+1) * P^(n-2*k-1) * (P^2-4*Q)^k)

V(n) = 2^(1 - n)*sum(k=0, floor(n/2), binomial(n, 2*k) * P^(n-2*k) * (P^2-4*Q)^k)

Często możemy spotkać założenie [math]\displaystyle{ P \geqslant 1 }[/math]. Poniższe twierdzenie wyjaśnia, dlaczego tak jest.

Twierdzenie N9
Jeżeli [math]\displaystyle{ (U_n) }[/math] i [math]\displaystyle{ (V_n) }[/math] są ciągami Lucasa, to

[math]\displaystyle{ U_n (- P, Q) = (- 1)^{n - 1} U_n (P, Q) }[/math]

[math]\displaystyle{ V_n (- P, Q) = (- 1)^n V_n (P, Q) }[/math]

Dowód

Niech

[math]\displaystyle{ \alpha = \frac{P + \sqrt{D}}{2} \qquad \qquad \;\; \beta = \frac{P - \sqrt{D}}{2} }[/math]

[math]\displaystyle{ a = \frac{- P + \sqrt{D}}{2} \qquad \qquad b = \frac{- P - \sqrt{D}}{2} }[/math]

Liczby [math]\displaystyle{ \alpha, \beta }[/math] oraz [math]\displaystyle{ a, b }[/math] są odpowiednio pierwiastkami równań

[math]\displaystyle{ x^2 - P x + Q = 0 }[/math]

[math]\displaystyle{ x^2 + P x + Q = 0 }[/math]

Zatem definiują one ciągi Lucasa

[math]\displaystyle{ U_n (P, Q) = \frac{\alpha^n - \beta^n}{\alpha - \beta} \qquad \qquad \;\; V_n (P, Q) = \alpha^n + \beta^n }[/math]

[math]\displaystyle{ U_n (- P, Q) = \frac{a^n - b^n}{a - b} \qquad \qquad V_n (- P, Q) = a^n + b^n }[/math]

Zauważmy, że

[math]\displaystyle{ \alpha - \beta = a - b = \sqrt{D} }[/math]

[math]\displaystyle{ \frac{a}{\beta} = \frac{b}{\alpha} = - 1 }[/math]

Łatwo znajdujemy

[math]\displaystyle{ U_n (- P, Q) = \frac{a^n - b^n}{a - b} = \frac{(- \beta)^n - (- \alpha)^n}{\sqrt{D}} = (- 1)^n \cdot \frac{\beta^n - \alpha^n}{\alpha - \beta} = (- 1)^{n - 1} \cdot U_n (P, Q) }[/math]

[math]\displaystyle{ V_n (- P, Q) = a^n + b^n = (- \beta)^n + (- \alpha)^n = (- 1)^n \cdot (\alpha^n + \beta^n) = (- 1)^n \cdot V_n (P, Q) }[/math]

Co należało pokazać.
□

Zadanie N10
Pokazać, że jeżeli [math]\displaystyle{ P, Q \in \mathbb{Z} \setminus \{ 0 \} }[/math] i [math]\displaystyle{ D = P^2 - 4 Q \neq 0 }[/math], to

[math]\displaystyle{ U_n (2 P, 4 Q) = 2^{n - 1} U_n (P, Q) }[/math]

[math]\displaystyle{ V_n (2 P, 4 Q) = 2^n V_n (P, Q) }[/math]

Rozwiązanie

Niech

[math]\displaystyle{ \alpha = {\small\frac{P + \sqrt{D}}{2}} \qquad \qquad \;\; \beta = {\small\frac{P - \sqrt{D}}{2}} }[/math]

[math]\displaystyle{ a = P + \sqrt{D} \qquad \qquad \;\; b = P - \sqrt{D} }[/math]

Liczby [math]\displaystyle{ \alpha, \beta }[/math] oraz [math]\displaystyle{ a, b }[/math] są odpowiednio pierwiastkami równań

[math]\displaystyle{ x^2 - P x + Q = 0 }[/math]

[math]\displaystyle{ x^2 - 2 P x + 4 Q = 0 }[/math]

Zatem definiują one ciągi Lucasa

[math]\displaystyle{ U_n (P, Q) = {\small\frac{\alpha^n - \beta^n}{\alpha - \beta}} \qquad \qquad \;\;\; V_n (P, Q) = \alpha^n + \beta^n }[/math]

[math]\displaystyle{ U_n (2 P, 4 Q) = {\small\frac{a^n - b^n}{a - b}} \qquad \qquad V_n (2 P, 4 Q) = a^n + b^n }[/math]

Zauważmy, że

[math]\displaystyle{ \alpha - \beta = \sqrt{D} }[/math]

[math]\displaystyle{ a - b = 2 \sqrt{D} }[/math]

[math]\displaystyle{ {\small\frac{a}{\alpha}} = {\small\frac{b}{\beta}} = 2 }[/math]

Łatwo znajdujemy

[math]\displaystyle{ U_n (2 P, 4 Q) = {\small\frac{a^n - b^n}{a - b}} = {\small\frac{(2 \alpha)^n - (2 \beta)^n}{2 \sqrt{D}}} = 2^{n - 1} \cdot {\small\frac{\alpha^n - \beta^n}{\alpha - \beta}} = 2^{n - 1} U_n (P, Q) }[/math]

[math]\displaystyle{ V_n (2 P, 4 Q) = a^n + b^n = (2 \alpha)^n + (2 \beta)^n = 2^n (\alpha^n + \beta^n) = 2^n V_n (P, Q) }[/math]

Co należało pokazać.
□

Zadanie N11
Pokazać, że jeżeli [math]\displaystyle{ Q \in \mathbb{Z} \setminus \{ 0 \} }[/math] oraz [math]\displaystyle{ P = 4 Q - 1 }[/math], to

[math]\displaystyle{ U_{2 k} (P, P Q) = - (- P)^k U_{2 k} (1, Q) }[/math]

[math]\displaystyle{ U_{2 k + 1} (P, P Q) = (- P)^k V_{2 k + 1} (1, Q) }[/math]

[math]\displaystyle{ V_{2 k} (P, P Q) = (- P)^k V_{2 k} (1, Q) }[/math]

[math]\displaystyle{ V_{2 k + 1} (P, P Q) = - (- P)^{k + 1} U_{2 k + 1} (1, Q) }[/math]

Rozwiązanie

Niech

[math]\displaystyle{ \alpha = {\small\frac{1 + \sqrt{- P}}{2}} \qquad \qquad \beta = {\small\frac{1 - \sqrt{- P}}{2}} }[/math]

[math]\displaystyle{ a = {\small\frac{P + \sqrt{- P}}{2}} \qquad \qquad b = {\small\frac{P - \sqrt{- P}}{2}} }[/math]

Liczby [math]\displaystyle{ \alpha, \beta }[/math] oraz [math]\displaystyle{ a, b }[/math] są odpowiednio pierwiastkami równań

[math]\displaystyle{ x^2 - x + {\small\frac{P + 1}{4}} = 0 }[/math]

[math]\displaystyle{ x^2 - P x + {\small\frac{P (P + 1)}{4}} = 0 }[/math]

Z założenia [math]\displaystyle{ P = 4 Q - 1 }[/math], zatem

[math]\displaystyle{ x^2 - x + Q = 0 }[/math]

[math]\displaystyle{ x^2 - P x + P Q = 0 }[/math]

Czyli definiują one ciągi Lucasa

[math]\displaystyle{ U_n (1, Q) = {\small\frac{\alpha^n - \beta^n}{\alpha - \beta}} \qquad \qquad \:\:\: V_n (1, Q) = \alpha^n + \beta^n }[/math]

[math]\displaystyle{ U_n (P, P Q) = {\small\frac{a^n - b^n}{a - b}} \qquad \qquad V_n (P, P Q) = a^n + b^n }[/math]

Zauważmy, że

[math]\displaystyle{ \alpha - \beta = a - b = \sqrt{- P} }[/math]

[math]\displaystyle{ {\small\frac{a}{\beta}} = {\small\frac{P + \sqrt{- P}}{1 - \sqrt{- P}}} = \sqrt{- P} }[/math]

[math]\displaystyle{ {\small\frac{b}{\alpha}} = {\small\frac{P - \sqrt{- P}}{1 + \sqrt{- P}}} = - \sqrt{- P} }[/math]

Łatwo znajdujemy

[math]\displaystyle{ U_{2 k} (P, P Q) = \frac{a^{2 k} - b^{2 k}}{a - b} = \frac{\left( \beta \sqrt{- P} \right)^{2 k} - \left( - \alpha \sqrt{- P} \right)^{2 k}}{\sqrt{- P}} = \frac{(- P)^k (\beta^{2 k} - \alpha^{2 k})}{\alpha - \beta} = - (- P)^k U_{2 k} (1, Q) }[/math]

[math]\displaystyle{ U_{2 k + 1} (P, P Q) = \frac{a^{2 k + 1} - b^{2 k + 1}}{a - b} = \frac{\left( \beta \sqrt{- P} \right)^{2 k + 1} - \left( - \alpha \sqrt{- P} \right)^{2 k + 1}}{\sqrt{- P}} = (- P)^k (\beta^{2 k + 1} + \alpha^{2 k + 1}) = (- P)^k V_{2 k + 1} (1, Q) }[/math]

[math]\displaystyle{ V_{2 k} (P, P Q) = a^{2 k} + b^{2 k} = \left( \beta \sqrt{- P} \right)^{2 k} + \left( - \alpha \sqrt{- P} \right)^{2 k} = (- P)^k (\alpha^{2 k} + \beta^{2 k}) = (- P)^k V_{2 k} (1, Q) }[/math]

[math]\displaystyle{ V_{2 k + 1} (P, P Q) = a^{2 k + 1} + b^{2 k + 1} = \left( \beta \sqrt{- P} \right)^{2 k + 1} + \left( - \alpha \sqrt{- P} \right)^{2 k + 1} = (- P)^{k + 1} \cdot \frac{\beta^{2 k + 1} - \alpha^{2 k + 1}}{\sqrt{- P}} = - (- P)^{k + 1} U_{2 k + 1} (1, Q) }[/math]

Co należało pokazać.
□

Zadanie N12
Pokazać, że jeżeli [math]\displaystyle{ Q \in \mathbb{Z} \setminus \{ 0 \} }[/math] oraz [math]\displaystyle{ P = 4 Q + 1 }[/math], to

[math]\displaystyle{ U_{2 k} (P, P Q) = P^k U_{2 k} (1, - Q) }[/math]

[math]\displaystyle{ U_{2 k + 1} (P, P Q) = P^k V_{2 k + 1} (1, - Q) }[/math]

[math]\displaystyle{ V_{2 k} (P, P Q) = P^k V_{2 k} (1, - Q) }[/math]

[math]\displaystyle{ V_{2 k + 1} (P, P Q) = P^{k + 1} U_{2 k + 1} (1, - Q) }[/math]

Rozwiązanie

Niech

[math]\displaystyle{ \alpha = {\small\frac{1 + \sqrt{P}}{2}} \qquad \qquad \beta = {\small\frac{1 - \sqrt{P}}{2}} }[/math]

[math]\displaystyle{ a = {\small\frac{P + \sqrt{P}}{2}} \qquad \qquad b = {\small\frac{P - \sqrt{P}}{2}} }[/math]

Liczby [math]\displaystyle{ \alpha, \beta }[/math] oraz [math]\displaystyle{ a, b }[/math] są odpowiednio pierwiastkami równań

[math]\displaystyle{ x^2 - x - {\small\frac{P - 1}{4}} = 0 }[/math]

[math]\displaystyle{ x^2 - P x + {\small\frac{P (P - 1)}{4}} = 0 }[/math]

Z założenia [math]\displaystyle{ P = 4 Q + 1 }[/math], zatem

[math]\displaystyle{ x^2 - x - Q = 0 }[/math]

[math]\displaystyle{ x^2 - P x + P Q = 0 }[/math]

Czyli definiują one ciągi Lucasa

[math]\displaystyle{ U_n (1, - Q) = {\small\frac{\alpha^n - \beta^n}{\alpha - \beta}} \qquad \qquad V_n (1, - Q) = \alpha^n + \beta^n }[/math]

[math]\displaystyle{ U_n (P, P Q) = {\small\frac{a^n - b^n}{a - b}} \qquad \qquad V_n (P, P Q) = a^n + b^n }[/math]

Zauważmy, że

[math]\displaystyle{ \alpha - \beta = a - b = \sqrt{P} }[/math]

[math]\displaystyle{ {\small\frac{a}{\alpha}} = {\small\frac{P + \sqrt{P}}{1 + \sqrt{P}}} = \sqrt{P} }[/math]

[math]\displaystyle{ {\small\frac{b}{\beta}} = {\small\frac{P - \sqrt{P}}{1 - \sqrt{P}}} = - \sqrt{P} }[/math]

Łatwo znajdujemy

[math]\displaystyle{ U_{2 k} (P, P Q) = \frac{a^{2 k} - b^{2 k}}{a - b} = \frac{\left( \alpha \sqrt{P} \right)^{2 k} - \left( - \beta \sqrt{P} \right)^{2 k}}{\sqrt{P}} = \frac{P^k (\alpha^{2 k} - \beta^{2 k})}{\alpha - \beta} = P^k U_{2 k} (1, - Q) }[/math]

[math]\displaystyle{ U_{2 k + 1} (P, P Q) = \frac{a^{2 k + 1} - b^{2 k + 1}}{a - b} = \frac{\left( \alpha \sqrt{P} \right)^{2 k + 1} - \left( - \beta \sqrt{P} \right)^{2 k + 1}}{\sqrt{P}} = P^k (\alpha^{2 k + 1} + \beta^{2 k + 1}) = P^k V_{2 k + 1} (1, - Q) }[/math]

[math]\displaystyle{ V_{2 k} (P, P Q) = a^{2 k} + b^{2 k} = \left( \alpha \sqrt{P} \right)^{2 k} + \left( - \beta \sqrt{P} \right)^{2 k} = P^k (\alpha^{2 k} + \beta^{2 k}) = P^k V_{2 k} (1, - Q) }[/math]

[math]\displaystyle{ V_{2 k + 1} (P, P Q) = a^{2 k + 1} + b^{2 k + 1} = \left( \alpha \sqrt{P} \right)^{2 k + 1} + \left( - \beta \sqrt{P} \right)^{2 k + 1} = P^{k + 1} \cdot \frac{\alpha^{2 k + 1} - \beta^{2 k + 1}}{\sqrt{P}} = P^{k + 1} U_{2 k + 1} (1, - Q) }[/math]

Co należało pokazać.
□

Twierdzenie N13
Dla wyrazów ciągów Lucasa prawdziwe są wzory

[math]\displaystyle{ 1. }[/math]	[math]\displaystyle{ U_{m + n} = U_m U_{n + 1} - Q U_{m - 1} U_n }[/math]
[math]\displaystyle{ 2. }[/math]	[math]\displaystyle{ V_{m + n} = V_m V_n - Q^n V_{m - n} }[/math]	[math]\displaystyle{ m \geqslant n }[/math]
[math]\displaystyle{ 3. }[/math]	[math]\displaystyle{ U_{m + n} = U_m V_n - Q^n U_{m - n} }[/math]	[math]\displaystyle{ m \geqslant n }[/math]
[math]\displaystyle{ 4. }[/math]	[math]\displaystyle{ V_{m + n} = D U_m U_n + Q^n V_{m - n} }[/math]	[math]\displaystyle{ m \geqslant n }[/math]
[math]\displaystyle{ 5. }[/math]	[math]\displaystyle{ U_m V_n - V_m U_n = 2 Q^n U_{m - n} }[/math]	[math]\displaystyle{ m \geqslant n }[/math]
[math]\displaystyle{ 6. }[/math]	[math]\displaystyle{ U^2_n = U_{n - 1} U_{n + 1} + Q^{n - 1} }[/math]
[math]\displaystyle{ 7. }[/math]	[math]\displaystyle{ V^2_n = V_{n - 1} V_{n + 1} - D Q^{n - 1} }[/math]

[math]\displaystyle{ \;\; 8. }[/math]	[math]\displaystyle{ 2 U_{m + n} = U_m V_n + V_m U_n }[/math]
[math]\displaystyle{ \;\; 9. }[/math]	[math]\displaystyle{ 2 V_{m + n} = V_m V_n + D U_m U_n }[/math]
[math]\displaystyle{ 10. }[/math]	[math]\displaystyle{ V_m V_n - D U_m U_n = 2 Q^n V_{m - n} }[/math]	[math]\displaystyle{ m \geqslant n }[/math]
[math]\displaystyle{ 11. }[/math]	[math]\displaystyle{ U_{2 n} = U_n V_n }[/math]
[math]\displaystyle{ 12. }[/math]	[math]\displaystyle{ V_{2 n} = V^2_n - 2 Q^n }[/math]
[math]\displaystyle{ 13. }[/math]	[math]\displaystyle{ V_{2 n} = D U^2_n + 2 Q^n }[/math]
[math]\displaystyle{ 14. }[/math]	[math]\displaystyle{ V^2_n - D U^2_n = 4 Q^n }[/math]
[math]\displaystyle{ 15. }[/math]	[math]\displaystyle{ D U_n = 2 V_{n + 1} - P V_n }[/math]
[math]\displaystyle{ 16. }[/math]	[math]\displaystyle{ V_n = 2 U_{n + 1} - P U_n }[/math]
[math]\displaystyle{ 17. }[/math]	[math]\displaystyle{ D U_n = V_{n + 1} - Q V_{n - 1} }[/math]	[math]\displaystyle{ n \geqslant 1 }[/math]
[math]\displaystyle{ 18. }[/math]	[math]\displaystyle{ V_n = U_{n + 1} - Q U_{n - 1} }[/math]	[math]\displaystyle{ n \geqslant 1 }[/math]

[math]\displaystyle{ 19. }[/math]	[math]\displaystyle{ U_{2 n} = 2 U_n U_{n + 1} - P U^2_n }[/math]
[math]\displaystyle{ 20. }[/math]	[math]\displaystyle{ U_{2 n + 1} = U^2_{n + 1} - Q U^2_n }[/math]
[math]\displaystyle{ 21. }[/math]	[math]\displaystyle{ U_{2 n + 2} = P U^2_{n + 1} - 2 Q U_n U_{n + 1} }[/math]

Dowód

Wzory 1. - 7. najłatwiej udowodnić korzystając z definicji N1.

Wzór 1.

[math]\displaystyle{ U_{m + n} = {\small\frac{\alpha^{m + n} - \beta^{m + n}}{\alpha - \beta}} }[/math]

[math]\displaystyle{ \quad \: = {\small\frac{\alpha^m - \beta^m}{\alpha - \beta}} \cdot {\small\frac{\alpha^{n + 1} - \beta^{n + 1}}{\alpha - \beta}} - \alpha \beta \cdot {\small\frac{\alpha^{m - 1} - \beta^{m - 1}}{\alpha - \beta}} \cdot {\small\frac{\alpha^n - \beta^n}{\alpha - \beta}} }[/math]

[math]\displaystyle{ \quad \: = U_m U_{n + 1} - Q U_{m - 1} U_n }[/math]

Wzór 2.

[math]\displaystyle{ V_{m + n} = \alpha^{m + n} + \beta^{m + n} }[/math]

[math]\displaystyle{ \quad \;\! = (\alpha^m + \beta^m) (\alpha^n + \beta^n) - \alpha^n \beta^n \cdot (\alpha^{m - n} + \beta^{m - n}) }[/math]

[math]\displaystyle{ \quad \;\! = V_m V_n - Q^n V_{m - n} }[/math]

Wzór 3.

[math]\displaystyle{ U_{m + n} = {\small\frac{\alpha^{m + n} - \beta^{m + n}}{\alpha - \beta}} }[/math]

[math]\displaystyle{ \quad \: = {\small\frac{(\alpha^m - \beta^m) (\alpha^n + \beta^n)}{\alpha - \beta}} - {\small\frac{\alpha^n \beta^n \cdot (\alpha^{m - n} - \beta^{m - n})}{\alpha - \beta}} }[/math]

[math]\displaystyle{ \quad \: = U_m V_n - Q^n U_{m - n} }[/math]

Wzór 4.

[math]\displaystyle{ V_{m + n} = \alpha^{m + n} + \beta^{m + n} }[/math]

[math]\displaystyle{ \quad \;\! = (\alpha - \beta)^2 \cdot {\small\frac{\alpha^m - \beta^m}{\alpha - \beta}} \cdot {\small\frac{\alpha^n - \beta^n}{\alpha - \beta}} + \alpha^n \beta^n \cdot (\alpha^{m - n} + \beta^{m - n}) }[/math]

[math]\displaystyle{ \quad \;\! = D U_m U_n + Q^n V_{m - n} }[/math]

Wzór 5.

[math]\displaystyle{ U_m V_n - V_m U_n = {\small\frac{\alpha^m - \beta^m}{\alpha - \beta}} \cdot (\alpha^n + \beta^n) - (\alpha^m + \beta^m) \cdot {\small\frac{\alpha^n - \beta^n}{\alpha - \beta}} }[/math]

[math]\displaystyle{ \;\;\: = 2 \cdot \alpha^n \beta^n \cdot {\small\frac{\alpha^{m - n} - \beta^{m - n}}{\alpha - \beta}} }[/math]

[math]\displaystyle{ \;\;\: = 2 Q^n U_{m - n} }[/math]

Wzór 6.

[math]\displaystyle{ U^2_n = \left( {\small\frac{\alpha^n - \beta^n}{\alpha - \beta}} \right)^2 }[/math]

[math]\displaystyle{ \;\! = {\small\frac{\alpha^{n - 1} - \beta^{n - 1}}{\alpha - \beta}} \cdot {\small\frac{\alpha^{n + 1} - \beta^{n + 1}}{\alpha - \beta}} + \alpha^{n - 1} \beta^{n - 1} }[/math]

[math]\displaystyle{ \;\! = U_{n - 1} U_{n + 1} + Q^{n - 1} }[/math]

Wzór 7.

[math]\displaystyle{ V^2_n = (\alpha^n + \beta^n)^2 }[/math]

[math]\displaystyle{ \;\! = (\alpha^{n - 1} + \beta^{n - 1}) (\alpha^{n + 1} + \beta^{n + 1}) - (\alpha - \beta)^2 \cdot \alpha^{n - 1} \beta^{n - 1} }[/math]

[math]\displaystyle{ \;\! = V_{n - 1} V_{n + 1} - D Q^{n - 1} }[/math]

Wzory 8. - 18. można łatwo udowodnić, korzystając ze wzorów 1. - 7.

Wzór 8. Policzyć sumę wzoru 3. pomnożonego przez [math]\displaystyle{ 2 }[/math] i wzoru 5.

Wzór 9. Policzyć sumę wzorów 2. i 4.

Wzór 10. Połączyć wzory 2. i 4.

Wzór 11. We wzorze 3. położyć [math]\displaystyle{ m = n }[/math].

Wzór 12. We wzorze 2. położyć [math]\displaystyle{ m = n }[/math].

Wzór 13. We wzorze 4. położyć [math]\displaystyle{ m = n }[/math].

Wzór 14. We wzorze 10. położyć [math]\displaystyle{ m = n }[/math] lub połączyć wzory 12. i 13.

Wzór 15. We wzorze 9. położyć [math]\displaystyle{ m = 1 }[/math].

Wzór 16. We wzorze 8. położyć [math]\displaystyle{ m = 1 }[/math].

Wzór 17. We wzorze 15. położyć [math]\displaystyle{ V_{n + 1} = P V_n - Q V_{n - 1} }[/math].

Wzór 18. We wzorze 16. położyć [math]\displaystyle{ U_{n + 1} = P U_n - Q U_{n - 1} }[/math].

Wzory 19. - 21. to wzory, które wykorzystamy w przyszłości do szybkiego obliczania wartości wyrazów [math]\displaystyle{ U_n }[/math] i [math]\displaystyle{ V_n }[/math] modulo.

Wzór 19. Wystarczy połączyć wzory 11. oraz 16.

Wzór 20. Wystarczy we wzorze 1. położyć [math]\displaystyle{ m = n + 1 }[/math].

Wzór 21. Kładąc we wzorze 19. [math]\displaystyle{ n \rightarrow n + 1 }[/math], otrzymujemy

[math]\displaystyle{ U_{2 n + 2} = 2 U_{n + 1} U_{n + 2} - P U^2_{n + 1} \qquad (*) }[/math]

Kładąc we wzorze 1. [math]\displaystyle{ m = n + 2 }[/math], mamy

[math]\displaystyle{ U_{2 n + 2} = U_{n + 2} U_{n + 1} - Q U_{n + 1} U_n }[/math]

Czyli

[math]\displaystyle{ 2 U_{2 n + 2} = 2 U_{n + 1} U_{n + 2} - 2 Q U_n U_{n + 1} }[/math]

Odejmując od powyższego wzoru wzór [math]\displaystyle{ (*) }[/math], dostajemy wzór 21.

[math]\displaystyle{ U_{2 n + 2} = P U^2_{n + 1} - 2 Q U_n U_{n + 1} }[/math]

Co należało pokazać.
□

Obliczanie wyrazów ciągu Lucasa modulo [math]\displaystyle{ m }[/math]

Przykład N14
Pokażemy, jak wykorzystać podane w twierdzeniu N13 wzory 19, 20, 21 i 16

[math]\displaystyle{ U_{2 n} = 2 U_n U_{n + 1} - P U^2_n }[/math]

[math]\displaystyle{ U_{2 n + 1} = U^2_{n + 1} - Q U^2_n }[/math]

[math]\displaystyle{ U_{2 n + 2} = P U^2_{n + 1} - 2 Q U_n U_{n + 1} }[/math]

[math]\displaystyle{ V_n = 2 U_{n + 1} - P U_n }[/math]

do szybkiego obliczania wyrazów ciągu Lucasa modulo [math]\displaystyle{ m }[/math].

Niech [math]\displaystyle{ P = 3 }[/math], [math]\displaystyle{ Q = 1 }[/math], [math]\displaystyle{ D = P^2 - 4 Q = 5 }[/math], [math]\displaystyle{ n = 22 = (10110)_2 = \sum_{j = 0}^{4} a_j \cdot 2^j }[/math].

W tabeli przedstawione są kolejne kroki, jakie musimy wykonać, aby policzyć [math]\displaystyle{ U_n = U_{22} }[/math] modulo [math]\displaystyle{ m = 23 }[/math].

[math]\displaystyle{ \boldsymbol{j} }[/math]	[math]\displaystyle{ \boldsymbol{a_j} }[/math]	[math]\displaystyle{ \boldsymbol{k_j} }[/math]	[math]\displaystyle{ \boldsymbol{U_{k_j}} }[/math]	[math]\displaystyle{ \boldsymbol{U_{k_j + 1}} }[/math]
[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ (1)_2 = 1 }[/math]	[math]\displaystyle{ U_1 = 1 }[/math]	[math]\displaystyle{ U_2 = P = 3 }[/math]
[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ (10)_2 = 2 }[/math]	[math]\displaystyle{ U_2 = 2 U_1 U_2 - 3 U^2_1 = 6 - 3 = 3 }[/math]	[math]\displaystyle{ U_3 = U^2_2 - 1 = 8 }[/math]
[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ (101)_2 = 5 }[/math]	[math]\displaystyle{ U_5 = U^2_3 - U^2_2 = 64 - 9 = 55 \equiv 9 }[/math]	[math]\displaystyle{ U_6 = 3 U_3^2 - 2 U_2 U_3 = 192 - 48 = 144 \equiv 6 }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ (1011)_2 = 11 }[/math]	[math]\displaystyle{ U_{11} = U^2_6 - U^2_5 \equiv 36 - 81 \equiv - 45 \equiv 1 }[/math]	[math]\displaystyle{ U_{12} = 3 U_6^2 - 2 U_5 U_6 \equiv 108 - 108 \equiv 0 }[/math]
[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ (10110)_2 = 22 }[/math]	[math]\displaystyle{ U_{22} = 2 U_{11} U_{12} - 3 U^2_{11} \equiv 0 - 3 \equiv 20 }[/math]	[math]\displaystyle{ U_{23} = U^2_{12} - U^2_{11} \equiv 0 - 1 \equiv 22 }[/math]

W kolumnie [math]\displaystyle{ a_j }[/math] wypisujemy kolejne cyfry liczby [math]\displaystyle{ n = 22 = (10110)_2 }[/math] zapisanej w układzie dwójkowym. Liczby w kolumnie [math]\displaystyle{ k_j }[/math] tworzymy, biorąc kolejne (od prawej do lewej) cyfry liczby [math]\displaystyle{ n }[/math] w zapisie dwójkowym. Postępując w ten sposób, w ostatnim wierszu mamy [math]\displaystyle{ k_j = n }[/math] i wyliczamy liczby [math]\displaystyle{ U_n }[/math] i [math]\displaystyle{ U_{n + 1} }[/math] modulo [math]\displaystyle{ m }[/math].

Dla uproszczenia zapisu i ułatwienia zrozumienia liczbę [math]\displaystyle{ k_j }[/math] oznaczymy jako [math]\displaystyle{ r }[/math], a [math]\displaystyle{ k_{j + 1} }[/math] jako [math]\displaystyle{ s }[/math]. Zauważmy, że

tabela jest zbudowana tak, że musimy znaleźć wyrazy ciągu Lucasa o indeksie [math]\displaystyle{ r = k_j }[/math] oraz o indeksie o jeden większym: [math]\displaystyle{ r + 1 = k_j + 1 }[/math]
przejście do następnego wiersza (w dół) oznacza, że musimy znaleźć wyrazy o indeksie [math]\displaystyle{ s = k_{j + 1} }[/math] oraz o indeksie o jeden większym: [math]\displaystyle{ s + 1 }[/math]
przechodząc do następnego wiersza, dotychczasowa liczba [math]\displaystyle{ r = k_j }[/math] powiększa się o kolejną cyfrę ( [math]\displaystyle{ 0 }[/math] lub [math]\displaystyle{ 1 }[/math] ), którą dopisujemy z prawej strony
dodanie na końcu liczby [math]\displaystyle{ r = k_j }[/math] zera podwaja liczbę [math]\displaystyle{ r }[/math], czyli [math]\displaystyle{ s = k_{j + 1} = 2 r }[/math] oraz [math]\displaystyle{ s + 1 = 2 r + 1 }[/math]
dodanie na końcu liczby [math]\displaystyle{ r = k_j }[/math] jedynki podwaja liczbę [math]\displaystyle{ r }[/math] i zwiększą ją o jeden, czyli [math]\displaystyle{ s = k_{j + 1} = 2 r + 1 }[/math] oraz [math]\displaystyle{ s + 1 = 2 r + 2 }[/math]

Dlatego, jeżeli kolejną dodaną cyfrą jest zero, to korzystamy ze wzorów

[math]\displaystyle{ U_s = U_{2 r} = 2 U_r U_{r + 1} - P U^2_r }[/math]

[math]\displaystyle{ U_{s + 1} = U_{2 r + 1} = U^2_{r + 1} - Q U^2_r }[/math]

Gdy kolejną dodaną cyfrą jest jeden, to stosujemy wzory

[math]\displaystyle{ U_s = U_{2 r + 1} = U^2_{r + 1} - Q U^2_r }[/math]

[math]\displaystyle{ U_{s + 1} = U_{2 r + 2} = P U^2_{r + 1} - 2 Q U_r U_{r + 1} }[/math]

Korzystając ze wzoru [math]\displaystyle{ V_n = 2 U_{n + 1} - P U_n }[/math], mamy

[math]\displaystyle{ V_{22} = 2 U_{23} - 3 U_{22} \equiv 44 - 60 \equiv - 16 \equiv 7 \pmod{23} }[/math]

Ostatecznie otrzymujemy

[math]\displaystyle{ U_{22} \equiv 20 \pmod{23} \quad }[/math] oraz [math]\displaystyle{ \quad V_{22} \equiv 7 \pmod{23} }[/math]

Uwaga N15
Uogólniając postępowanie przedstawione w przykładzie N14, możemy napisać program w PARI/GP do szybkiego obliczania wyrazów ciągu Lucasa [math]\displaystyle{ U_n (P, Q) }[/math] i [math]\displaystyle{ V_n (P, Q) }[/math] modulo [math]\displaystyle{ m }[/math].

modLucas(n, P, Q, m) =
{
local(A, i, s, U, U2, V, W, W2);
if( m == 1, return([0, 0]) );
if( n == 0, return([0, 2 % m]) );
A = digits(n, 2); \\ otrzymujemy wektor cyfr liczby n w układzie dwójkowym
s = length(A); \\ długość wektora A
U = 1;
W = P;
i = 1;
while( i++ <= s,
       if( A[i] == 0,  U2 = 2*U*W - P*U^2;  W2 = W^2 - Q*U^2 );
       if( A[i] == 1,  U2 = W^2 - Q*U^2;  W2 = P*W^2 - 2*Q*U*W );
       U = U2 % m;
       W = W2 % m;
     );
V = (2*W - P*U) % m;
return([U, V]);
}

Podzielność wyrazów [math]\displaystyle{ U_n (P, Q) }[/math] przez liczbę pierwszą nieparzystą

Uwaga N16
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą. W przypadku, gdy [math]\displaystyle{ p \nmid P Q }[/math] nie możemy nic powiedzieć o podzielności wyrazów [math]\displaystyle{ U_n }[/math] przez [math]\displaystyle{ p }[/math]. Przykładowo, jeżeli [math]\displaystyle{ P \equiv 1 \pmod{p} \; }[/math] [math]\displaystyle{ \text{i} \;\; Q \equiv 1 \pmod{p} }[/math], to modulo [math]\displaystyle{ p }[/math], mamy

[math]\displaystyle{ (U_n) \equiv (0, 1, 1, 0, - 1, - 1, 0, 1, 1, 0, - 1, - 1, 0, 1, 1, 0, - 1, - 1, 0, 1, 1, 0, - 1, - 1, \ldots) }[/math]

W przypadku, gdy [math]\displaystyle{ P \equiv 2 \pmod{p} \; }[/math] [math]\displaystyle{ \text{i} \;\; Q \equiv 1 \pmod{p} }[/math], to modulo [math]\displaystyle{ p }[/math] mamy

[math]\displaystyle{ (U_n) \equiv (0, 1, 2, \ldots, p - 1, 0, 1, 2, \ldots, p - 1, 0, 1, 2, \ldots, p - 1, \ldots) }[/math]

Sytuacja wygląda inaczej, gdy [math]\displaystyle{ p \mid P Q }[/math].

Twierdzenie N17
Niech [math]\displaystyle{ p }[/math] będzie liczbą pierwszą nieparzystą.

● jeżeli [math]\displaystyle{ \; p \mid P \; }[/math] [math]\displaystyle{ \text{i} \;\; p \mid Q , \; }[/math] to [math]\displaystyle{ \; p \mid U_n \; }[/math] dla [math]\displaystyle{ n \geqslant 2 }[/math]

● jeżeli [math]\displaystyle{ \; p \mid P \; }[/math] [math]\displaystyle{ \text{i} \;\; p \nmid Q , \; }[/math] to [math]\displaystyle{ \; p \mid U_{2 n} \; }[/math] i [math]\displaystyle{ \; p \nmid U_{2 n + 1} }[/math]

● jeżeli [math]\displaystyle{ \; p \nmid P \; }[/math] [math]\displaystyle{ \text{i} \;\; p \mid Q , \; }[/math] to [math]\displaystyle{ \; p \nmid U_n \; }[/math] dla [math]\displaystyle{ n \geqslant 1 }[/math]

● jeżeli [math]\displaystyle{ \; p \mid Q , \; }[/math] to [math]\displaystyle{ \; p \mid U_n }[/math], gdzie [math]\displaystyle{ n \geqslant 2 }[/math], wtedy i tylko wtedy, gdy [math]\displaystyle{ \; p \mid P }[/math]

● jeżeli [math]\displaystyle{ \; p \nmid P \; }[/math] [math]\displaystyle{ \text{i} \;\; p \mid D , \; }[/math] to [math]\displaystyle{ \; p \mid U_n \; }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ p \mid n }[/math]

Założenie, że [math]\displaystyle{ p \nmid P }[/math] w ostatnim punkcie jest istotne. Gdy [math]\displaystyle{ \; p \mid P \; }[/math] i [math]\displaystyle{ \; p \mid D , \; }[/math] to [math]\displaystyle{ \; p \mid Q \; }[/math] i otrzymujemy punkt pierwszy.

Dowód

Punkt 1.

Ponieważ [math]\displaystyle{ U_2 = P }[/math], zatem [math]\displaystyle{ p \mid U_2 }[/math]. Dla [math]\displaystyle{ n \geqslant 3 }[/math] wyrażenie [math]\displaystyle{ U_n = P U_{n - 1} - Q U_{n - 2} }[/math] jest podzielne przez [math]\displaystyle{ p }[/math].

Punkt 2.

Indeksy parzyste. Indukcja matematyczna. Mamy [math]\displaystyle{ U_0 = 0 }[/math] i [math]\displaystyle{ U_2 = P }[/math], zatem [math]\displaystyle{ p \mid U_0 }[/math] i [math]\displaystyle{ p \mid U_2 }[/math]. Zakładając, że [math]\displaystyle{ p \mid U_{2 n} }[/math], z definicji ciągu [math]\displaystyle{ (U_k) }[/math], otrzymujemy dla [math]\displaystyle{ U_{2 n + 2} }[/math]

[math]\displaystyle{ U_{2 n + 2} = P U_{2 n - 1} - Q U_{2 n} }[/math]

Z założenia indukcyjnego wynika, że [math]\displaystyle{ p \mid U_{2 n + 2} }[/math], zatem na mocy zasady indukcji matematycznej twierdzenie jest prawdziwe dla wszystkich [math]\displaystyle{ n \geqslant 0 }[/math].

Indeksy nieparzyste. Indukcja matematyczna. Mamy [math]\displaystyle{ U_1 = 1 }[/math] i [math]\displaystyle{ U_3 = P^2 - Q }[/math], zatem [math]\displaystyle{ p \nmid U_1 }[/math] i [math]\displaystyle{ p \nmid U_3 }[/math]. Zakładając, że [math]\displaystyle{ p \nmid U_{2 n - 1} }[/math], z definicji ciągu [math]\displaystyle{ (U_k) }[/math], otrzymujemy dla [math]\displaystyle{ U_{2 n + 1} }[/math]

[math]\displaystyle{ U_{2 n + 1} = P U_{2 n} - Q U_{2 n - 1} }[/math]

Z założenia indukcyjnego wynika, że [math]\displaystyle{ p \nmid U_{2 n + 1} }[/math], zatem na mocy zasady indukcji matematycznej twierdzenie jest prawdziwe dla wszystkich [math]\displaystyle{ n \geqslant 1 }[/math].

Punkt 3.

Indukcja matematyczna. Mamy [math]\displaystyle{ U_1 = 1 }[/math] i [math]\displaystyle{ U_2 = P }[/math], zatem [math]\displaystyle{ p \nmid U_1 }[/math] i [math]\displaystyle{ p \nmid U_2 }[/math]. Zakładając, że [math]\displaystyle{ p \nmid U_n }[/math] zachodzi dla wszystkich liczb całkowitych dodatnich nie większych od [math]\displaystyle{ n }[/math], z definicji ciągu [math]\displaystyle{ (U_n) }[/math] otrzymujemy dla [math]\displaystyle{ n + 1 }[/math]

[math]\displaystyle{ U_{n + 1} = P U_n - Q U_{n - 1} }[/math]

Z założenia indukcyjnego wynika, że [math]\displaystyle{ p \nmid U_{n + 1} }[/math], zatem na mocy zasady indukcji matematycznej twierdzenie jest prawdziwe dla wszystkich liczb [math]\displaystyle{ n \geqslant 1 }[/math].

Punkt 4.

Wynika z punktów pierwszego i trzeciego.

Punkt 5.

Z twierdzenia N7 wiemy, że

[math]\displaystyle{ 2^{n - 1} U_n = \sum_{k = 0}^{\lfloor (n - 1) / 2 \rfloor} \binom{n}{2 k + 1} P^{n - 2 k - 1} D^k }[/math]

[math]\displaystyle{ \;\; = n P^{n - 1} + \binom{n}{3} P^{n - 3} D + \binom{n}{5} P^{n - 5} D^2 + \ldots + \begin{cases} n P D^{(n - 2) / 2} & \text{gdy }n\text{ jest parzyste} \\ D^{(n - 1) / 2} & \text{gdy }n\text{ jest nieparzyste} \\ \end{cases} }[/math]

Z założenia [math]\displaystyle{ p \mid D }[/math], zatem modulo [math]\displaystyle{ p }[/math] dostajemy

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

Ponieważ [math]\displaystyle{ p \nmid P }[/math], zatem [math]\displaystyle{ p \mid U_n }[/math] wtedy i tylko wtedy, gdy [math]\displaystyle{ p \mid n }[/math]. Co należało pokazać.
□

Twierdzenie N18
Jeżeli [math]\displaystyle{ d }[/math] jest nieparzystym dzielnikiem [math]\displaystyle{ Q }[/math], to dla [math]\displaystyle{ n \geqslant 2 }[/math] jest

[math]\displaystyle{ U_n \equiv P^{n - 1} \pmod{d} }[/math]

W szczególności, gdy liczba pierwsza nieparzysta [math]\displaystyle{ p }[/math] jest dzielnikiem [math]\displaystyle{ Q }[/math] i [math]\displaystyle{ p \nmid P }[/math], to

[math]\displaystyle{ U_p \equiv 1 \pmod{p} }[/math]

Dowód

Oznaczmy [math]\displaystyle{ \delta = \sqrt{D} }[/math], zatem [math]\displaystyle{ 2 \alpha = P + \delta }[/math] i [math]\displaystyle{ 2 \beta = P - \delta }[/math]. Ze wzoru dwumianowego, mamy

[math]\displaystyle{ 2^n \alpha^n = (P + \delta)^n = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} \delta^j }[/math]

[math]\displaystyle{ 2^n \beta^n = (P - \delta)^n = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (- \delta)^j }[/math]

Obliczając różnicę wyjściowych wzorów, mamy

[math]\displaystyle{ 2^n (\alpha^n - \beta^n) = \sum_{j = 0}^{n} \binom{n}{j} P^{n - j} (\delta^j - (- \delta)^j) = }[/math]

[math]\displaystyle{ \quad \: = \underset{j \; \text{nieparzyste}}{\sum_{j = 1}^{n}} \binom{n}{j} P^{n - j} \cdot 2 \delta^j }[/math]

[math]\displaystyle{ \quad \: = 2 \underset{j \; \text{nieparzyste}}{\sum_{j = 1}^{n}} \binom{n}{j} P^{n - j} \cdot \delta \cdot D^{(j - 1) / 2} }[/math]

Rozpatrując powyższą równość modulo [math]\displaystyle{ Q }[/math] dostajemy (zobacz N43)

[math]\displaystyle{ 2^{n - 1} \cdot {\small\frac{\alpha^n - \beta^n}{\delta}} = 2^{n - 1} U_n \equiv \underset{j \; \text{nieparzyste}}{\sum_{j = 1}^{n}} \binom{n}{j} P^{n - j} \cdot P^{j - 1} }[/math]

[math]\displaystyle{ \;\:\: \equiv P^{n - 1} \underset{j \; \text{nieparzyste}}{\sum_{j = 1}^{n}} \binom{n}{j} }[/math]

[math]\displaystyle{ \;\:\: \equiv 2^{n - 1} P^{n - 1} }[/math]

Czyli

[math]\displaystyle{ 2^{n - 1} (U_n - P^{n - 1}) \equiv 0 \pmod{Q} }[/math]

Ponieważ [math]\displaystyle{ Q }[/math] dzieli [math]\displaystyle{ 2^{n - 1} (U_n - P^{n - 1}) }[/math], to tym bardziej [math]\displaystyle{ d }[/math] dzieli [math]\displaystyle{ 2^{n - 1} (U_n - P^{n - 1}) }[/math]. Z założenia [math]\displaystyle{ \gcd (d, 2^{n - 1}) = 1 }[/math], zatem [math]\displaystyle{ d }[/math] dzieli [math]\displaystyle{ U_n - P^{n - 1} }[/math] (zobacz C74).

W przypadku szczególnym, gdy [math]\displaystyle{ d = p }[/math], gdzie [math]\displaystyle{ p }[/math] jest nieparzystą liczbą pierwszą i [math]\displaystyle{ p \nmid P }[/math], z twierdzenia Fermata otrzymujemy natychmiast

[math]\displaystyle{ U_p \equiv P^{p - 1} \equiv 1 \pmod{p} }[/math]

Co należało pokazać.
□

Twierdzenie N19
Niech [math]\displaystyle{ D = P^2 - 4 Q }[/math], a [math]\displaystyle{ (D \mid p) }[/math] oznacza symbol Legendre'a, gdzie [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ p \nmid Q }[/math]. Mamy

● [math]\displaystyle{ U_p \equiv (D \mid p) \pmod{p} }[/math]

● jeżeli [math]\displaystyle{ (D \mid p) = - 1 , \; }[/math] to [math]\displaystyle{ \; p \mid U_{p + 1} }[/math]

● jeżeli [math]\displaystyle{ (D \mid p) = 1 , \; }[/math] to [math]\displaystyle{ \; p \mid U_{p - 1} }[/math]

Dowód

Punkt 1.

Zauważmy, że przypadek gdy [math]\displaystyle{ p \mid Q }[/math], omówiliśmy w twierdzeniu poprzednim. Z założenia [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą. Z twierdzenia N7, w przypadku nieparzystego [math]\displaystyle{ n = p }[/math], otrzymujemy

[math]\displaystyle{ 2^{p - 1} U_p = p P^{p - 1} + \binom{p}{3} P^{p - 3} D + \binom{p}{5} P^{p - 5} D^2 + \ldots + \binom{p}{p-2} P^2 D^{(p - 3) / 2} + D^{(p - 1) / 2} }[/math]

Ponieważ dla każdego [math]\displaystyle{ k \in [1, p - 1] }[/math] (zobacz N43)

[math]\displaystyle{ \binom{p}{k} \equiv 0 \pmod{p} }[/math]

to modulo [math]\displaystyle{ p }[/math] dostajemy (zobacz J33)

[math]\displaystyle{ 2^{p - 1} U_p \equiv U_p \equiv D^{(p - 1) / 2} \equiv (D \mid p) \pmod{p} }[/math]

Punkt 2.

Zauważmy, że warunek [math]\displaystyle{ (D \mid p) = - 1 }[/math] nie może być spełniony, gdy [math]\displaystyle{ p \mid Q }[/math]. Istotnie, gdy [math]\displaystyle{ p \mid Q }[/math], to [math]\displaystyle{ D = P^2 - 4 Q \equiv P^2 \pmod{p} }[/math], czyli

[math]\displaystyle{ (D \mid p) = (P^2 \mid p) = (P \mid p)^2 = 0 , \; }[/math] gdy [math]\displaystyle{ p \mid P }[/math]

lub

[math]\displaystyle{ (D \mid p) = (P^2 \mid p) = (P \mid p)^2 = 1 , \; }[/math] gdy [math]\displaystyle{ p \nmid P }[/math]

i nie może być [math]\displaystyle{ (D \mid p) = - 1 }[/math].

Dla parzystego [math]\displaystyle{ n = p + 1 }[/math] otrzymujemy z twierdzenia N7

[math]\displaystyle{ 2^p U_{p + 1} = (p + 1) P^p + \binom{p + 1}{3} P^{p - 2} D + \binom{p + 1}{5} P^{p - 4} D^2 + \ldots + \binom{p + 1}{p - 2} P^3 D^{(p - 3) / 2} + (p + 1) P D^{(p - 1) / 2} }[/math]

Ponieważ dla [math]\displaystyle{ k \in [2, p - 1] }[/math] (zobacz N44)

[math]\displaystyle{ \binom{p + 1}{k} \equiv 0 \pmod{p} }[/math]

to modulo [math]\displaystyle{ p }[/math] dostajemy

[math]\displaystyle{ 2 U_{p + 1} \equiv P + P D^{(p - 1) / 2} \pmod{p} }[/math]

Z założenia [math]\displaystyle{ D }[/math] jest liczbą niekwadratową modulo [math]\displaystyle{ p }[/math], zatem [math]\displaystyle{ D^{(p - 1) / 2} \equiv - 1 \pmod{p} }[/math] (zobacz J31). Skąd wynika natychmiast, że

[math]\displaystyle{ 2 U_{p + 1} \equiv 0 \pmod{p} }[/math]

Czyli [math]\displaystyle{ p \mid U_{p + 1} }[/math].

Punkt 3.

Dla parzystego [math]\displaystyle{ n = p - 1 }[/math] otrzymujemy z twierdzenia N7

[math]\displaystyle{ 2^{p - 2} U_{p - 1} = (p - 1) P^{p - 2} + \binom{p - 1}{3} P^{p - 4} D + \binom{p - 1}{5} P^{p - 6} D^2 + \ldots + \binom{p - 1}{p - 4} P^3 D^{(p - 5) / 2} + (p - 1) P D^{(p - 3) / 2} }[/math]

Ponieważ dla [math]\displaystyle{ k \in [0, p - 1] }[/math] (zobacz N45)

[math]\displaystyle{ \binom{p - 1}{k} \equiv (- 1)^k \pmod{p} }[/math]

to modulo [math]\displaystyle{ p }[/math] mamy

[math]\displaystyle{ 2^{p - 2} U_{p - 1} \equiv - (P^{p - 2} + P^{p - 4} D + P^{p - 6} D^2 + \ldots + P D^{(p - 3) / 2}) \pmod{p} }[/math]

[math]\displaystyle{ \quad \,\, \equiv - P (P^{p - 3} + P^{p - 5} D + P^{p - 7} D^2 + \ldots + D^{(p - 3) / 2}) \pmod{p} }[/math]

Z założenia [math]\displaystyle{ D }[/math] jest liczbą kwadratową modulo [math]\displaystyle{ p }[/math] (zobacz J29), zatem istnieje taka liczba [math]\displaystyle{ R }[/math], że

[math]\displaystyle{ D \equiv R^2 \pmod{p} }[/math]

Ponieważ

[math]\displaystyle{ (D \mid p) = 1 }[/math], to [math]\displaystyle{ p \nmid D }[/math], zatem [math]\displaystyle{ p \nmid R }[/math]
z założenia [math]\displaystyle{ p \nmid Q }[/math], to [math]\displaystyle{ P^2 - R^2 \equiv P^2 - D \equiv 4 Q \not\equiv 0 \pmod{p} }[/math]

Czyli

[math]\displaystyle{ 2^{p - 2} U_{p - 1} \equiv - P (P^{p - 3} + P^{p - 5} R^2 + P^{p - 7} R^4 + \ldots + R^{p - 3}) \pmod{p} }[/math]

Uwzględniając, że [math]\displaystyle{ P^2 - R^2 \not\equiv 0 \pmod{p} }[/math], możemy napisać

[math]\displaystyle{ 2^{p - 2} (P^2 - R^2) U_{p - 1} \equiv - P (P^2 - R^2) (P^{p - 3} + P^{p - 5} R^2 + P^{p - 7} R^4 + \ldots + R^{p - 3}) \pmod{p} }[/math]

[math]\displaystyle{ \equiv - P (P^{p - 1} - R^{p - 1}) \pmod{p} }[/math]

[math]\displaystyle{ \equiv 0 \pmod{p} }[/math]

Zauważmy, że wynik nie zależy od tego, czy [math]\displaystyle{ p \mid P }[/math], czy [math]\displaystyle{ p \nmid P }[/math]. Skąd wynika

[math]\displaystyle{ U_{p - 1} \equiv 0 \pmod{p} }[/math]

Co należało pokazać.
□

Aby zapisać punkty 2. i 3. twierdzenia N19 (i tylko te punkty) w zwartej formie, musimy założyć, że [math]\displaystyle{ \gcd (p, D) = 1 }[/math]. Otrzymujemy
Twierdzenie N20
Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą i [math]\displaystyle{ \gcd (p, Q D) = 1 }[/math], to

[math]\displaystyle{ U_{p - (D \mid p)} \equiv 0 \pmod{p} }[/math]

Liczby pseudopierwsze Lucasa

Uwaga N21
Z twierdzenia N20 wiemy, że liczby pierwsze nieparzyste [math]\displaystyle{ p }[/math] takie, że [math]\displaystyle{ p \nmid Q D }[/math] są dzielnikami wyrazów ciągu Lucasa [math]\displaystyle{ U_{p - (D \mid p)} }[/math], gdzie [math]\displaystyle{ (D \mid p) }[/math] oznacza symbol Legendre'a. Jeśli zastąpimy symbol Legendre'a symbolem Jacobiego, to będziemy mogli badać prawdziwość tego twierdzenia dla liczb złożonych i łatwo przekonamy się, że dla pewnych liczb złożonych [math]\displaystyle{ m }[/math] kongruencja

[math]\displaystyle{ U_{m - (D \mid m)} \equiv 0 \pmod{m} }[/math]

również jest prawdziwa. Prowadzi to definicji liczb pseudopierwszych Lucasa.

Definicja N22
Powiemy, że liczba złożona nieparzysta [math]\displaystyle{ m }[/math] jest liczbą pseudopierwszą Lucasa dla parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math] (symbolicznie: LPSP( [math]\displaystyle{ P, Q }[/math] )), jeżeli [math]\displaystyle{ \gcd (m, Q D) = 1 }[/math] i

[math]\displaystyle{ U_{m - (D \mid m)} \equiv 0 \pmod{m} }[/math]

gdzie [math]\displaystyle{ (D \mid m) }[/math] oznacza symbol Jacobiego.

Twierdzenie N23
Jeżeli liczba złożona nieparzysta [math]\displaystyle{ m }[/math] jest liczbą pseudopierwszą Lucasa dla parametrów [math]\displaystyle{ P = a + 1 }[/math] i [math]\displaystyle{ Q = a }[/math], gdzie [math]\displaystyle{ a \geqslant 2 }[/math], to jest liczbą pseudopierwszą Fermata przy podstawie [math]\displaystyle{ a }[/math].

Dowód

Połóżmy we wzorze definiującym ciąg Lucasa

[math]\displaystyle{ U_m = {\small\frac{\alpha^m - \beta^m}{\alpha - \beta}} }[/math]

[math]\displaystyle{ \alpha = a }[/math] i [math]\displaystyle{ \beta = 1 }[/math]. Odpowiada to parametrom [math]\displaystyle{ P = \alpha + \beta = a + 1 }[/math], [math]\displaystyle{ Q = \alpha \beta = a }[/math], [math]\displaystyle{ D = (\alpha - \beta)^2 = (a - 1)^2 }[/math].

Ponieważ musi być [math]\displaystyle{ \gcd (m, Q D) = 1 }[/math], to mamy [math]\displaystyle{ \gcd (m, (a - 1) a) = 1 }[/math] i wynika stąd, że [math]\displaystyle{ (D \mid m) = 1 }[/math]. Z założenia [math]\displaystyle{ m }[/math] jest liczbą pseudopierwszą Lucasa dla parametrów [math]\displaystyle{ P = a + 1 }[/math] i [math]\displaystyle{ Q = a }[/math], zatem

[math]\displaystyle{ U_{m - 1} (a + 1, a) \equiv 0 \pmod{m} }[/math]

Czyli

[math]\displaystyle{ {\small\frac{a^{m - 1} - 1}{a - 1}} \equiv 0 \pmod{m} }[/math]

Jeżeli [math]\displaystyle{ m \biggr\rvert {\small\frac{a^{m - 1} - 1}{a - 1}} }[/math], to tym bardziej [math]\displaystyle{ m \big\rvert (a^{m - 1} - 1) }[/math] i możemy napisać

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

Zatem [math]\displaystyle{ m }[/math] jest liczbą pseudopierwszą Fermata przy podstawie [math]\displaystyle{ a }[/math]. Co należało pokazać.
□

Uwaga N24
Wykorzystując funkcje jacobi(a, n) i modLucas(n, P, Q, m) (zobacz J48, N15) możemy napisać prosty program, który sprawdza, czy dla liczby nieparzystej [math]\displaystyle{ m }[/math] prawdziwe jest twierdzenie N20.

isPrimeOrLPSP(m, P, Q) = 
{
local(D, js);
D = P^2 - 4*Q;
if( gcd(m, 2*Q*D) > 1, return(0) );
js = jacobi(D, m);
if( modLucas(m - js, P, Q, m)[1] == 0, return(1), return(0) );
}

Przykład N25
Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Lucasa dla różnych parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math]

[math]\displaystyle{ \boldsymbol{P} }[/math] [math]\displaystyle{ \boldsymbol{Q} }[/math]	[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]
[math]\displaystyle{ \boldsymbol{- 5} }[/math]	[math]\displaystyle{ 253 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 57 }[/math]	[math]\displaystyle{ 217 }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 69 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 253 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 143 }[/math]
[math]\displaystyle{ \boldsymbol{- 4} }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 119 }[/math]	[math]\displaystyle{ 57 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]
[math]\displaystyle{ \boldsymbol{- 3} }[/math]	[math]\displaystyle{ 217 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 527 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 65 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 323 }[/math]
[math]\displaystyle{ \boldsymbol{- 2} }[/math]	[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 209 }[/math]	[math]\displaystyle{ 39 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 85 }[/math]
[math]\displaystyle{ \boldsymbol{- 1} }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 119 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 143 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 15 }[/math]
[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ 65 }[/math]	[math]\displaystyle{ 115 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 209 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 35 }[/math]
[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ 1541 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ 85 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 35 }[/math]
[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ 629 }[/math]	[math]\displaystyle{ 559 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 91 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 55 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 35 }[/math]
[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ 119 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 209 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 85 }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ 119 }[/math]	[math]\displaystyle{ 65 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 115 }[/math]
[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 143 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 143 }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 217 }[/math]	[math]\displaystyle{ 39 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]

Pokaż kod

FirstLPSP(Stop) = 
\\ najmniejsze LPSP(P,Q) < Stop;  dla 1<=P<=10 i -5<=Q<=5
{
local(D, m, P, Q);
Q = -6;
while( Q++ <= 5,
       if( Q == 0, next() );
       P = 0;
       while( P++ <= 10,
              D = P^2 - 4*Q;
              if( D == 0, 
                  print("Q= ", Q, "   P= ", P, "   ------------------");
                  next();
                );
              m = 3;
              while( m < Stop,
                     if( isPrimeOrLPSP(m, P, Q)  &&  !isprime(m),
                         print("Q= ", Q, "   P= ", P, "   m= ", m, "   (D|m)= ", jacobi(D, m));
                         break();
                       );
                     m = m + 2;
                   );
            );
     );
}

Żółtym tłem oznaczyliśmy te najmniejsze liczby pseudopierwsze Lucasa, dla których [math]\displaystyle{ (D \mid m) = - 1 }[/math].

Przykład N26
Ilość liczb LPSP([math]\displaystyle{ P, Q }[/math]) mniejszych od [math]\displaystyle{ 10^9 }[/math]

[math]\displaystyle{ \boldsymbol{P} }[/math] [math]\displaystyle{ \boldsymbol{Q} }[/math]	[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]
[math]\displaystyle{ \boldsymbol{- 5} }[/math]	[math]\displaystyle{ 4266 }[/math]	[math]\displaystyle{ 4935 }[/math]	[math]\displaystyle{ 4278 }[/math]	[math]\displaystyle{ 4981 }[/math]	[math]\displaystyle{ 6363 }[/math]	[math]\displaystyle{ 6028 }[/math]	[math]\displaystyle{ 5202 }[/math]	[math]\displaystyle{ 4426 }[/math]	[math]\displaystyle{ 5832 }[/math]	[math]\displaystyle{ 6027 }[/math]
[math]\displaystyle{ \boldsymbol{- 4} }[/math]	[math]\displaystyle{ 4599 }[/math]	[math]\displaystyle{ 4152 }[/math]	[math]\displaystyle{ 9272 }[/math]	[math]\displaystyle{ 5886 }[/math]	[math]\displaystyle{ 6958 }[/math]	[math]\displaystyle{ 4563 }[/math]	[math]\displaystyle{ 5600 }[/math]	[math]\displaystyle{ 9509 }[/math]	[math]\displaystyle{ 7007 }[/math]	[math]\displaystyle{ 4142 }[/math]
[math]\displaystyle{ \boldsymbol{- 3} }[/math]	[math]\displaystyle{ 4265 }[/math]	[math]\displaystyle{ 5767 }[/math]	[math]\displaystyle{ 4241 }[/math]	[math]\displaystyle{ 5114 }[/math]	[math]\displaystyle{ 5859 }[/math]	[math]\displaystyle{ 7669 }[/math]	[math]\displaystyle{ 6083 }[/math]	[math]\displaystyle{ 6120 }[/math]	[math]\displaystyle{ 4420 }[/math]	[math]\displaystyle{ 5096 }[/math]
[math]\displaystyle{ \boldsymbol{- 2} }[/math]	[math]\displaystyle{ 5361 }[/math]	[math]\displaystyle{ 4389 }[/math]	[math]\displaystyle{ 5063 }[/math]	[math]\displaystyle{ 5632 }[/math]	[math]\displaystyle{ 5364 }[/math]	[math]\displaystyle{ 5228 }[/math]	[math]\displaystyle{ 5859 }[/math]	[math]\displaystyle{ 10487 }[/math]	[math]\displaystyle{ 5370 }[/math]	[math]\displaystyle{ 9798 }[/math]
[math]\displaystyle{ \boldsymbol{- 1} }[/math]	[math]\displaystyle{ 4152 }[/math]	[math]\displaystyle{ 5886 }[/math]	[math]\displaystyle{ 4563 }[/math]	[math]\displaystyle{ 9509 }[/math]	[math]\displaystyle{ 4142 }[/math]	[math]\displaystyle{ 6273 }[/math]	[math]\displaystyle{ 5773 }[/math]	[math]\displaystyle{ 4497 }[/math]	[math]\displaystyle{ 5166 }[/math]	[math]\displaystyle{ 5305 }[/math]
[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ 282485800 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 6567 }[/math]	[math]\displaystyle{ 7669 }[/math]	[math]\displaystyle{ 7131 }[/math]	[math]\displaystyle{ 10882 }[/math]	[math]\displaystyle{ 8626 }[/math]	[math]\displaystyle{ 8974 }[/math]	[math]\displaystyle{ 8509 }[/math]	[math]\displaystyle{ 8752 }[/math]
[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ 7803 }[/math]	[math]\displaystyle{ 449152466 }[/math]	[math]\displaystyle{ 5597 }[/math]	[math]\displaystyle{ 5886 }[/math]	[math]\displaystyle{ 6509 }[/math]	[math]\displaystyle{ 5761 }[/math]	[math]\displaystyle{ 8115 }[/math]	[math]\displaystyle{ 6945 }[/math]	[math]\displaystyle{ 8380 }[/math]	[math]\displaystyle{ 7095 }[/math]
[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ 5974 }[/math]	[math]\displaystyle{ 8768 }[/math]	[math]\displaystyle{ 282485800 }[/math]	[math]\displaystyle{ 5767 }[/math]	[math]\displaystyle{ 5651 }[/math]	[math]\displaystyle{ 5632 }[/math]	[math]\displaystyle{ 6640 }[/math]	[math]\displaystyle{ 5725 }[/math]	[math]\displaystyle{ 6058 }[/math]	[math]\displaystyle{ 7050 }[/math]
[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ 10749 }[/math]	[math]\displaystyle{ 282485800 }[/math]	[math]\displaystyle{ 14425 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 9735 }[/math]	[math]\displaystyle{ 6567 }[/math]	[math]\displaystyle{ 8164 }[/math]	[math]\displaystyle{ 7669 }[/math]	[math]\displaystyle{ 7608 }[/math]	[math]\displaystyle{ 7131 }[/math]
[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ 5047 }[/math]	[math]\displaystyle{ 15127 }[/math]	[math]\displaystyle{ 6155 }[/math]	[math]\displaystyle{ 15127 }[/math]	[math]\displaystyle{ 4152 }[/math]	[math]\displaystyle{ 5146 }[/math]	[math]\displaystyle{ 4423 }[/math]	[math]\displaystyle{ 5526 }[/math]	[math]\displaystyle{ 6289 }[/math]	[math]\displaystyle{ 9509 }[/math]

Pokaż kod

NumOfLPSP(Stop) = 
\\ ilość liczb pseudopierwszych Lucasa LPSP(P,Q) < Stop;  dla 1<=P<=10 i -5<=Q<=5
{
local(D, m, P, Q);
Q = -6;
while( Q++ <= 5,
       if( Q == 0, next() );
       P = 0;
       while( P++ <= 10,
              D = P^2 - 4*Q;
              if( D == 0, print("Q= ", Q, "   P= ", P, "   ------------------"); next() );
              s = 0;
              m = 3;
              while( m < Stop,
                     if( isPrimeOrLPSP(m, P, Q)  &&  !isprime(m), s++ );
                     m = m + 2;
                   );
              print("Q= ", Q, "   P= ", P, "   s= ", s);
            );
     );
}

Uwaga N27
Dla [math]\displaystyle{ (P, Q) = (1, 1) }[/math] ciąg Lucasa [math]\displaystyle{ (U_n) }[/math] ma postać

[math]\displaystyle{ (U_n) = (0, 1, 1, 0, - 1, - 1, 0, 1, 1, 0, - 1, - 1, 0, 1, 1, 0, - 1, - 1, 0, 1, 1, \ldots) }[/math]

Stosując indukcję matematyczną, udowodnimy, że [math]\displaystyle{ U_{3 k} = 0 }[/math]. Łatwo sprawdzamy, że dla [math]\displaystyle{ k = 0 }[/math] i [math]\displaystyle{ k = 1 }[/math] wzór jest prawdziwy. Zakładając prawdziwość wzoru dla wszystkich liczb naturalnych nie większych od [math]\displaystyle{ k }[/math], otrzymujemy dla [math]\displaystyle{ k + 1 }[/math] (zobacz N13 p.3)

[math]\displaystyle{ U_{3 (k + 1)} = U_{3 k + 3} = U_{3 k} V_3 - U_{3 (k - 1)} = 0 }[/math]

Co kończy dowód. Zbadajmy liczby pseudopierwsze Lucasa dla [math]\displaystyle{ (P, Q) = (1, 1) }[/math].

Mamy [math]\displaystyle{ D = P^2 - 4 Q = - 3 }[/math]. Wynika stąd, że nie może być [math]\displaystyle{ 3 \mid m }[/math], bo mielibyśmy [math]\displaystyle{ \gcd (m, Q D) = 3 \gt 1 }[/math].

Z zadania J46 wiemy, że

[math]\displaystyle{ (- 3 \mid m) = \begin{cases} \;\;\: 1 & \text{gdy } m = 6 k + 1 \\ \;\;\: 0 & \text{gdy } m = 6 k + 3 \\ - 1 & \text{gdy } m = 6 k + 5 \\ \end{cases} }[/math]

Ponieważ [math]\displaystyle{ 3 \nmid m }[/math], to wystarczy zbadać przypadki [math]\displaystyle{ m = 6 k + 1 }[/math] i [math]\displaystyle{ m = 6 k + 5 }[/math]. W pierwszym przypadku jest

[math]\displaystyle{ U_{m - (- 3 \mid m)} = U_{6 k + 1 - 1} = U_{6 k} = 0 }[/math]

W drugim przypadku, gdy [math]\displaystyle{ m = 6 k + 5 }[/math], dostajemy

[math]\displaystyle{ U_{m - (- 3 \mid m)} = U_{6 k + 5 + 1} = U_{6 (k + 1)} = 0 }[/math]

Zatem dla dowolnej liczby nieparzystej [math]\displaystyle{ m }[/math] niepodzielnej przez [math]\displaystyle{ 3 }[/math] jest

[math]\displaystyle{ U_{m - (- 3 \mid m)} \equiv 0 \pmod{m} }[/math]

Czyli liczbami pseudopierwszymi Lucasa dla parametrów [math]\displaystyle{ (P, Q) = (1, 1) }[/math] będą liczby nieparzyste [math]\displaystyle{ m }[/math], które nie są podzielne przez [math]\displaystyle{ 3 }[/math] i nie są liczbami pierwszymi. Ilość takich liczb nie większych od [math]\displaystyle{ 10^k }[/math] możemy łatwo znaleźć poleceniem

for(k = 1, 9, s = 0; forstep(m = 3, 10^k, 2, if( m%6 <> 3, s = s + !isprime(m) )); print(s))

Zadanie N28
Pokazać, że ilość liczb pseudopierwszych Lucasa dla parametrów [math]\displaystyle{ (P, Q) = (2, 2) }[/math] nie większych od [math]\displaystyle{ 10^k }[/math] możemy znaleźć poleceniem

for(k = 1, 9, s = 0; forstep(m = 3, 10^k, 2, s = s + !isprime(m)); print(s))

Metoda Selfridge'a wyboru parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math]

Uwaga N29
Twierdzenie N20 możemy wykorzystać do testowania pierwszości liczb. Ponieważ musi być spełniony warunek [math]\displaystyle{ \gcd (m, Q D) = 1 }[/math], to nie każda para liczb [math]\displaystyle{ P, Q }[/math] (np. wybrana losowo) nadaje się do przeprowadzenia testu. Zawsze będziemy zmuszeni określić zasadę postępowania, która doprowadzi do wyboru właściwej pary [math]\displaystyle{ P, Q }[/math].

Robert Baillie i Samuel Wagstaff przedstawili^[1] dwie metody wyboru parametrów dla testu Lucasa. Ograniczymy się do omówienia tylko pierwszej z nich (metodę zaproponował John Selfridge).

Rozważmy ciąg [math]\displaystyle{ a_k = (- 1)^k (2 k + 1) }[/math], gdzie [math]\displaystyle{ k \geqslant 2 }[/math], czyli [math]\displaystyle{ a_k = (5, - 7, 9, - 11, 13, - 15, \ldots) }[/math]. Niech [math]\displaystyle{ D }[/math] będzie pierwszym wyrazem ciągu [math]\displaystyle{ (a_k) }[/math], dla którego jest [math]\displaystyle{ (a_k \mid m) = - 1 }[/math]. Dla tak ustalonego [math]\displaystyle{ D }[/math] przyjmujemy [math]\displaystyle{ P = 1 }[/math] i [math]\displaystyle{ Q = (1 - D) / 4 }[/math].

Tabela przedstawia początkowe wartości [math]\displaystyle{ Q }[/math], jakie otrzymamy, stosując tę metodę.

[math]\displaystyle{ \boldsymbol{k} }[/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{ 19 }[/math]	[math]\displaystyle{ 20 }[/math]
[math]\displaystyle{ \boldsymbol{a_k} }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ -7 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ -11 }[/math]	[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ -15 }[/math]	[math]\displaystyle{ 17 }[/math]	[math]\displaystyle{ -19 }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ -23 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ -27 }[/math]	[math]\displaystyle{ 29 }[/math]	[math]\displaystyle{ -31 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ -35 }[/math]	[math]\displaystyle{ 37 }[/math]	[math]\displaystyle{ -39 }[/math]	[math]\displaystyle{ 41 }[/math]
[math]\displaystyle{ \boldsymbol{Q} }[/math]	[math]\displaystyle{ -1 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ -2 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ -3 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ -4 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ -5 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ -6 }[/math]	[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ -7 }[/math]	[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ -8 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ -9 }[/math]	[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ -10 }[/math]

Zauważmy, że

jeżeli liczba nieparzysta [math]\displaystyle{ m }[/math] jest liczbą kwadratową, to wybór [math]\displaystyle{ D }[/math] nie będzie możliwy
w przypadku zastosowania tej metody znajdziemy tylko liczby pierwsze lub pseudopierwsze Lucasa, które spełniają kongruencję [math]\displaystyle{ U_{m + 1} \equiv 0 \pmod{m} }[/math], czyli tylko część liczb pseudopierwszych Lucasa określonych w definicji N22

Ponieważ Baillie i Wagstaff określili metodę zaproponowaną przez Selfridge'a jako metodę A, to pozostaniemy przy tej nazwie. Korzystając ze wzoru rekurencyjnego

[math]\displaystyle{ a_{k+1} = \begin{cases} \qquad \qquad 5 & \text{gdy } k = 1 \\ - a_k - 2 * \mathop{\textnormal{sign}}( a_k ) & \text{gdy } k \geqslant 2 \\ \end{cases} }[/math]

możemy łatwo napisać odpowiednią funkcję znajdującą liczby [math]\displaystyle{ P, Q }[/math] według tej metody.

MethodA(m) = 
{
local(a, js);
a = 5;
while( 1,
       js = jacobi(a, m);
       if( js == 0  &&  a % m <> 0, return([0, 0]) );
       if( js == -1, return([1, (1 - a)/4]) );
       a = -a - 2*sign(a);
     );
}

Wyjaśnienia wymaga druga linia kodu w pętli while. Wiemy, że (zobacz J42)

[math]\displaystyle{ (a \mid m) = 0 \quad \qquad \Longleftrightarrow \quad \qquad \gcd (a, m) \gt 1 }[/math]

Jednak z faktu, że [math]\displaystyle{ \gcd (a, m) \gt 1 }[/math] nie wynika natychmiast, że liczba [math]\displaystyle{ m }[/math] jest liczbą złożoną. Rozważmy dwa przypadki: gdy [math]\displaystyle{ m \mid a }[/math] i [math]\displaystyle{ m \nmid a }[/math].

Gdy [math]\displaystyle{ \gcd (a, m) \gt 1 }[/math] i [math]\displaystyle{ m \mid a }[/math], to [math]\displaystyle{ \gcd (a, m) = \gcd (k \cdot m, m) = m \gt 1 }[/math] i nie jesteśmy w stanie rozstrzygnąć, czy liczba [math]\displaystyle{ m }[/math] jest liczbą pierwszą, czy złożoną. Widać to dobrze na prostych przykładach

[math]\displaystyle{ \gcd (7, 7) = \gcd (14, 7) = 7 \gt 1 }[/math]

[math]\displaystyle{ \gcd (15, 15) = \gcd (30, 15) = 15 \gt 1 }[/math]

Gdy [math]\displaystyle{ \gcd (a, m) \gt 1 }[/math] i [math]\displaystyle{ m \nmid a }[/math], to [math]\displaystyle{ m }[/math] jest liczbą złożoną. Ponieważ [math]\displaystyle{ m \nmid a }[/math], to [math]\displaystyle{ a = k \cdot m + r }[/math], gdzie [math]\displaystyle{ r \in [1, m - 1] }[/math]. Mamy

[math]\displaystyle{ \gcd (a, m) = \gcd (k \cdot m + r, m) = \gcd (r, m) = d }[/math]

Musi być [math]\displaystyle{ d \gt 1 }[/math], bo założyliśmy, że [math]\displaystyle{ \gcd (a, m) \gt 1 }[/math] i musi być [math]\displaystyle{ d \lt m }[/math], bo [math]\displaystyle{ d \leqslant r \leqslant m - 1 }[/math]. Zatem [math]\displaystyle{ d }[/math] jest dzielnikiem nietrywialnym liczby [math]\displaystyle{ m }[/math] i [math]\displaystyle{ m }[/math] jest liczbą złożoną.

Omawiana linia kodu zapewnia wysłanie informacji o tym, że liczba [math]\displaystyle{ m }[/math] jest liczbą złożoną (zwrot wektora [0, 0]). W przypadku, gdy nie mamy takiej pewności, kontynuujemy szukanie liczby [math]\displaystyle{ a }[/math], takiej że [math]\displaystyle{ (a \mid m) = - 1 }[/math], pozostawiając zbadanie pierwszości liczby [math]\displaystyle{ m }[/math] na kolejnym etapie testowania.

Uważny Czytelnik dostrzeże, że nie zbadaliśmy, czy spełniony jest warunek [math]\displaystyle{ \gcd (m, Q) = 1 }[/math]. Nie musimy tego robić, bo zwracana przez funkcję MethodA() liczba [math]\displaystyle{ Q }[/math] jest względnie pierwsza z [math]\displaystyle{ m }[/math]. Omówimy ten problem dokładnie w zadaniu N30. Poniżej pokażemy, że nawet gdyby było [math]\displaystyle{ \gcd (m, Q) \gt 1 }[/math], to złożona liczba [math]\displaystyle{ m }[/math] nie zostanie uznana za liczbę pseudopierwszą Lucasa.

Zauważmy, że jeżeli [math]\displaystyle{ m }[/math] jest liczbą złożoną i ma dzielnik pierwszy [math]\displaystyle{ p \lt m }[/math], który dzieli [math]\displaystyle{ Q }[/math], to [math]\displaystyle{ p \mid Q }[/math] i [math]\displaystyle{ p \nmid P }[/math] (bo [math]\displaystyle{ P = 1 }[/math]), zatem [math]\displaystyle{ p \nmid U_k }[/math] dla [math]\displaystyle{ k \geqslant 1 }[/math] (zobacz N17), czyli nie może być

[math]\displaystyle{ U_{m + 1} (1, Q) \equiv 0 \pmod{m} }[/math]

bo mielibyśmy

[math]\displaystyle{ U_{m + 1} (1, Q) \equiv 0 \pmod{p} }[/math]

a to jest niemożliwe. Zatem program wykorzystujący twierdzenie N20 wykryje złożoność liczby [math]\displaystyle{ m }[/math].

Łatwo pokażemy, że nie jest możliwe, aby liczba [math]\displaystyle{ m }[/math] była liczbą pierwszą i była dzielnikiem [math]\displaystyle{ Q }[/math]. Jeżeli [math]\displaystyle{ m }[/math] jest liczbą pierwszą, to istnieje dokładnie [math]\displaystyle{ \tfrac{m - 1}{2} }[/math] liczb kwadratowych modulo [math]\displaystyle{ p }[/math] i [math]\displaystyle{ \tfrac{m - 1}{2} }[/math] liczb niekwadratowych modulo [math]\displaystyle{ p }[/math], zatem rozpoczynając od wyrazu [math]\displaystyle{ a_2 }[/math] możemy dojść co najwyżej do wyrazu o indeksie [math]\displaystyle{ k = \tfrac{m - 1}{2} + 2 }[/math], czyli

[math]\displaystyle{ | a_k | \leqslant m + 4 }[/math]

Skąd wynika, że

[math]\displaystyle{ | Q | = \left| {\small\frac{1 - a_k}{4}} \right| \leqslant {\small\frac{m + 5}{4}} \lt m }[/math]

Ostatnia nierówność jest prawdziwa dla [math]\displaystyle{ m \gt {\small\frac{5}{3}} }[/math], czyli dla wszystkich liczb pierwszych. Ponieważ [math]\displaystyle{ | Q | \lt m }[/math], w przypadku gdy [math]\displaystyle{ m }[/math] jest liczbą pierwszą, to [math]\displaystyle{ m }[/math] nie może być dzielnikiem liczby [math]\displaystyle{ Q }[/math].

Zadanie N30
Pokazać, że w przypadku, gdy dla kolejnych liczb [math]\displaystyle{ a_k = (- 1)^k (2 k + 1) }[/math] sprawdzamy, czy konsekwencją [math]\displaystyle{ (a_k \mid m) = 0 }[/math] jest złożoność liczby [math]\displaystyle{ m }[/math], to dla każdej liczby [math]\displaystyle{ Q }[/math] wyznaczonej metodą Selfridge'a jest [math]\displaystyle{ \gcd (Q, m) = 1 }[/math].

Rozwiązanie

Niech [math]\displaystyle{ m = 21 }[/math]. Rozpoczniemy od przykładu liczb [math]\displaystyle{ a_k = (- 1)^k (2 k + 1) }[/math] dla [math]\displaystyle{ k = 0, 1, \ldots, m - 1 }[/math].

[math]\displaystyle{ \boldsymbol{k} }[/math]	[math]\displaystyle{ \boldsymbol{0} }[/math]										[math]\displaystyle{ \boldsymbol{(m-1)/2} }[/math]										[math]\displaystyle{ \boldsymbol{m-1} }[/math]
[math]\displaystyle{ \boldsymbol{k} }[/math]	[math]\displaystyle{ 0 }[/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{ 19 }[/math]	[math]\displaystyle{ 20 }[/math]
[math]\displaystyle{ \boldsymbol{a_k} }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ -3 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ -7 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ -11 }[/math]	[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ -15 }[/math]	[math]\displaystyle{ 17 }[/math]	[math]\displaystyle{ -19 }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ -23 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ -27 }[/math]	[math]\displaystyle{ 29 }[/math]	[math]\displaystyle{ -31 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ -35 }[/math]	[math]\displaystyle{ 37 }[/math]	[math]\displaystyle{ -39 }[/math]	[math]\displaystyle{ 41 }[/math]
[math]\displaystyle{ \boldsymbol{R_m(a_k)} }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 18 }[/math]	[math]\displaystyle{ 5 }[/math]	[math]\displaystyle{ 14 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 10 }[/math]	[math]\displaystyle{ 13 }[/math]	[math]\displaystyle{ 6 }[/math]	[math]\displaystyle{ 17 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 19 }[/math]	[math]\displaystyle{ 4 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 8 }[/math]	[math]\displaystyle{ 11 }[/math]	[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 7 }[/math]	[math]\displaystyle{ 16 }[/math]	[math]\displaystyle{ 3 }[/math]	[math]\displaystyle{ 20 }[/math]

Zauważmy, że modulo [math]\displaystyle{ 21 }[/math] ciąg [math]\displaystyle{ (a_k) = (1, - 3, 5, - 7, \ldots, 37, - 39, 41) }[/math] jest identyczny z ciągiem [math]\displaystyle{ (0, 1, 2, \ldots, 19, 20) }[/math], a ciąg [math]\displaystyle{ (| a_k |) }[/math] to kolejne liczby nieparzyste od [math]\displaystyle{ 1 }[/math] do [math]\displaystyle{ 2 m - 1 }[/math].

Poniżej pokażemy, dlaczego musi być [math]\displaystyle{ \gcd (Q, m) = 1 }[/math], gdzie [math]\displaystyle{ Q }[/math] jest liczbą wyznaczoną metodą Selfridge'a (o ile sprawdzana jest złożoność liczby [math]\displaystyle{ m }[/math] przy testowaniu kolejnych liczb [math]\displaystyle{ a_k }[/math]). Pogrubioną czcionką zaznaczone są symbole Jacobiego, które wykryły złożoność liczby [math]\displaystyle{ m }[/math]. Gdyby nie była badana złożoność, to wyliczona zostałaby wartość [math]\displaystyle{ Q }[/math] na podstawie innego wyrazu ciągu [math]\displaystyle{ a_k }[/math] (ten symbol Jacobiego został zapisany zwykłą czcionką).

[math]\displaystyle{ m = 3 , \;\; (5 \mid 3) = - 1 , \;\; Q = - 1 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 5 , \;\; (5 \mid 5) = 0 , \;\; (- 7 \mid 5) = - 1 , \;\; Q = 2 , \;\; \gcd (m, Q) = 1 \;\; }[/math] (zauważmy, że [math]\displaystyle{ (5 \mid 5) = 0 }[/math] nie pozwala wnioskować o złożoności)

[math]\displaystyle{ m = 7 , \;\; (5 \mid 7) = - 1 , \;\; Q = - 1 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 9 , \;\; }[/math] (liczba kwadratowa)

[math]\displaystyle{ m = 11 , \;\; (- 11 \mid 11) = 0 , \;\; (13 \mid 11) = - 1 , \;\; Q = - 3 , \;\; \gcd (m, Q) = 1 \;\; }[/math] (zauważmy, że [math]\displaystyle{ (- 11 \mid 11) = 0 }[/math] nie pozwala wnioskować o złożoności)

[math]\displaystyle{ m = 13 , \;\; (5 \mid 13) = - 1 , \;\; Q = - 1 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 15 , \;\; \boldsymbol{(5 \mid 15) = 0} , \;\; (13 \mid 15) = - 1 , \;\; Q = - 3 , \;\; \gcd (m, Q) = 3 \;\; }[/math] (gdyby nie zbadano złożoności)

[math]\displaystyle{ m = 17 , \;\; (5 \mid 17) = - 1 , \;\; Q = - 1 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 19 , \;\; (- 7 \mid 19) = - 1 , \;\; Q = 2 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 21 , \;\; \boldsymbol{(- 7 \mid 21) = 0} , \;\; (- 11 \mid 21) = - 1 , \;\; Q = 3 , \;\; \gcd (m, Q) = 3 \;\; }[/math] (gdyby nie zbadano złożoności)

Niech [math]\displaystyle{ m \geqslant 23 }[/math]. Wiemy, że w ciągu [math]\displaystyle{ (5, - 7, 9, \ldots, \pm m, \mp (m + 2), \ldots, - (2 m - 3), 2 m - 1) }[/math] wystąpią liczby [math]\displaystyle{ a_k }[/math] takie, że [math]\displaystyle{ (a_k \mid m) = - 1 }[/math]. Warunek [math]\displaystyle{ (a_k \mid m) = 0 }[/math] oznacza, że [math]\displaystyle{ (2 k + 1 \mid m) = 0 }[/math], bo

[math]\displaystyle{ (a_k \mid m) = ((- 1)^k (2 k + 1) \mid m) = ((- 1)^k \mid m) \cdot (2 k + 1 \mid m) = (- 1 \mid m)^k \cdot (2 k + 1 \mid m) = \pm (2 k + 1 \mid m) }[/math]

Jeżeli będą spełnione warunki [math]\displaystyle{ (a_k \mid m) = 0 }[/math] i [math]\displaystyle{ R_m (a_k) \neq 0 }[/math], to liczba [math]\displaystyle{ m }[/math] będzie liczbą złożoną.

Wypiszmy kolejne próby dla [math]\displaystyle{ m \geqslant 23 }[/math]. Liczba [math]\displaystyle{ r }[/math] jest numerem próby.

[math]\displaystyle{ r = 1 , \;\; a_{r + 1} = 5 }[/math]

●	[math]\displaystyle{ (5 \mid m) = 1 }[/math]	[math]\displaystyle{ 5 \nmid m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (5 \mid m) = 0 }[/math]	[math]\displaystyle{ 5 \mid m }[/math]	koniec
●	[math]\displaystyle{ (5 \mid m) = - 1 \quad }[/math]	[math]\displaystyle{ 5 \nmid m }[/math]	[math]\displaystyle{ D = 5 , \;\; Q = - 1 , \;\; \gcd (m, Q) = 1 , \;\; }[/math] koniec

[math]\displaystyle{ r = 2 , \;\; a_{r + 1} = - 7 }[/math]

●	[math]\displaystyle{ (- 7 \mid m) = 1 }[/math]	[math]\displaystyle{ 7 \nmid m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (- 7 \mid m) = 0 }[/math]	[math]\displaystyle{ 7 \mid m }[/math]	koniec
●	[math]\displaystyle{ (- 7 \mid m) = - 1 \quad }[/math]	[math]\displaystyle{ 7 \nmid m }[/math]	[math]\displaystyle{ D = -7 , \;\; Q = 2 , \;\; \gcd (m, Q) = 1 , \;\; }[/math] koniec

[math]\displaystyle{ r = 3 }[/math], [math]\displaystyle{ a_{r + 1} = 9 }[/math]

●	[math]\displaystyle{ (9 \mid m) = 1 }[/math]	[math]\displaystyle{ 3 \nmid m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (9 \mid m) = 0 }[/math]	[math]\displaystyle{ 3 \mid m }[/math]	koniec
●	[math]\displaystyle{ (9 \mid m) \neq - 1 \quad }[/math]	- - - -	bo [math]\displaystyle{ 9 }[/math] jest liczbą kwadratową

Po wykonaniu trzech prób niezakończonych sukcesem (tzn. wykryciem złożoności [math]\displaystyle{ m }[/math] lub ustaleniem wartości liczb [math]\displaystyle{ D }[/math] i [math]\displaystyle{ Q }[/math]) wiemy, że [math]\displaystyle{ m }[/math] nie jest podzielna przez żadną z liczb pierwszych [math]\displaystyle{ p = 3, 5, 7 }[/math].

[math]\displaystyle{ r }[/math]-ta próba, gdzie [math]\displaystyle{ r \geqslant 4 , \;\; }[/math] wyraz [math]\displaystyle{ a_{r + 1} }[/math]

●	[math]\displaystyle{ (a_{r + 1} \mid m) = 1 }[/math]	żadna liczba pierwsza [math]\displaystyle{ p \leqslant \| a_{r + 1} \| = 2 r + 3 }[/math] nie dzieli liczby [math]\displaystyle{ m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (a_{r + 1} \mid m) = 0 }[/math]	A. jeżeli [math]\displaystyle{ m \mid a_{r + 1} }[/math]^{( * )} B. jeżeli [math]\displaystyle{ m \nmid a_{r + 1} }[/math]	A. przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math] B. [math]\displaystyle{ a_{r + 1} \mid m }[/math]^{( )}, koniec**
●	[math]\displaystyle{ (a_{r + 1} \mid m) = - 1 \quad }[/math]	żadna liczba pierwsza [math]\displaystyle{ p \leqslant \| a_{r + 1} \| = 2 r + 3 }[/math] nie dzieli liczby [math]\displaystyle{ m \quad }[/math]	[math]\displaystyle{ D = a_{r + 1} }[/math], [math]\displaystyle{ Q = {\small\frac{1 - a_{r + 1}}{4}} }[/math], koniec

^{( * )} jest to możliwe tylko dla [math]\displaystyle{ a_{r + 1} = a_{(m - 1) / 2} = m }[/math]

^{( ** )} zauważmy, że jeżeli [math]\displaystyle{ m \nmid a_{r + 1} }[/math], to [math]\displaystyle{ \gcd (a_{r + 1}, m) = | a_{r + 1} | }[/math], bo gdyby liczba [math]\displaystyle{ | a_{r + 1} | }[/math] była liczbą złożoną, to żaden z jej dzielników pierwszych nie dzieliłby liczby [math]\displaystyle{ m }[/math]

Jeżeli nie została wykryta złożoność liczby [math]\displaystyle{ m }[/math], to żadna z liczb pierwszych [math]\displaystyle{ p \leqslant | a_{r + 1} | = 2 r + 3 }[/math] nie dzieli liczby [math]\displaystyle{ m }[/math]. Zatem [math]\displaystyle{ \gcd (Q, m) \gt 1 }[/math] może być tylko w przypadku, gdy pewna liczba pierwsza [math]\displaystyle{ q \geqslant 2 r + 5 }[/math] będzie wspólnym dzielnikiem liczb [math]\displaystyle{ Q }[/math] i [math]\displaystyle{ m }[/math], ale jest to niemożliwe, bo

[math]\displaystyle{ | Q | = \left| {\small\frac{1 - a_{r + 1}}{4}} \right| \leqslant {\small\frac{| a_{r + 1} | + 1}{4}} = {\small\frac{2 r + 4}{4}} \lt 2 r + 5 \leqslant q }[/math]

Przedostatnia (ostra) nierówność jest prawdziwa dla wszystkich [math]\displaystyle{ r }[/math] naturalnych.
□

Zadanie N31
Zmodyfikujmy metodę Selfridge'a w taki sposób, że będziemy rozpoczynali próby nie od wyrazu [math]\displaystyle{ a_2 = 5 }[/math], ale od wyrazu [math]\displaystyle{ a_3 = - 7 }[/math]. Pokazać, że w przypadku, gdy dla kolejnych liczb [math]\displaystyle{ a_k = (- 1)^k (2 k + 1) }[/math] sprawdzamy, czy konsekwencją [math]\displaystyle{ (a_k \mid m) = 0 }[/math] jest złożoność liczby [math]\displaystyle{ m }[/math], to dla każdej liczby [math]\displaystyle{ Q }[/math] wyznaczonej tak zmodyfikowaną metodą Selfridge'a jest [math]\displaystyle{ \gcd (Q, m) = 1 }[/math].

Rozwiązanie

Poniżej pokażemy, dlaczego musi być [math]\displaystyle{ \gcd (Q, m) = 1 }[/math], gdzie [math]\displaystyle{ Q }[/math] jest liczbą wyznaczoną zmodyfikowaną metodą Selfridge'a (o ile sprawdzana jest złożoność liczby [math]\displaystyle{ m }[/math] przy testowaniu kolejnych liczb [math]\displaystyle{ a_k }[/math]). Pogrubioną czcionką zaznaczone są symbole Jacobiego, które wykryły złożoność liczby [math]\displaystyle{ m }[/math]. Gdyby nie była badana złożoność, to wyliczona zostałaby wartość [math]\displaystyle{ Q }[/math] na podstawie innego wyrazu ciągu [math]\displaystyle{ a_k }[/math] (ten symbol Jacobiego został zapisany zwykłą czcionką).

[math]\displaystyle{ m = 3 , \;\; (- 7 \mid 3) = - 1 , \;\; Q = 2 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 5 , \;\; (- 7 \mid 5) = - 1 , \;\; Q = 2 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 7 , \;\; (- 7 \mid 7) = 0 , \;\; (- 11 \mid 7) = - 1 , \;\; Q = 3 , \;\; \gcd (m, Q) = 1 }[/math] (zauważmy, że [math]\displaystyle{ (- 7 \mid 7) = 0 }[/math] nie pozwala wnioskować o złożoności)

[math]\displaystyle{ m = 9 , \;\; }[/math] (liczba kwadratowa)

[math]\displaystyle{ m = 11 , \;\; (- 11 \mid 11) = 0 , \;\; (13 \mid 11) = - 1 , \;\; Q = - 3 , \;\; \gcd (m, Q) = 1 \;\; }[/math] (zauważmy, że [math]\displaystyle{ (- 11 \mid 11) = 0 }[/math] nie pozwala wnioskować o złożoności)

[math]\displaystyle{ m = 13 , \;\; (- 7 \mid 13) = - 1 , \;\; Q = 2 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 15 , \;\; \boldsymbol{(9 \mid 15) = 0} , \;\; (13 \mid 15) = - 1 , \;\; Q = - 3 , \;\; \gcd (m, Q) = 3 \;\; }[/math] (gdyby nie zbadano złożoności)

[math]\displaystyle{ m = 17 , \;\; (- 7 \mid 17) = - 1 , \;\; Q = 2 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 19 , \;\; (- 7 \mid 19) = - 1 , \;\; Q = 2 , \;\; \gcd (m, Q) = 1 }[/math]

[math]\displaystyle{ m = 21 , \;\; \boldsymbol{(- 7 \mid 21) = 0} , \;\; (- 11 \mid 21) = - 1 , \;\; Q = 3 , \;\; \gcd (m, Q) = 3 \;\; }[/math] (gdyby nie zbadano złożoności)

Niech [math]\displaystyle{ m \geqslant 23 }[/math]. Wiemy, że w ciągu [math]\displaystyle{ ( - 7, 9, \ldots, \pm m, \mp (m + 2), \ldots, - (2 m - 3), 2 m - 1) }[/math] wystąpią liczby [math]\displaystyle{ a_k }[/math] takie, że [math]\displaystyle{ (a_k \mid m) = - 1 }[/math]. Warunek [math]\displaystyle{ (a_k \mid m) = 0 }[/math] oznacza, że [math]\displaystyle{ (2 k + 1 \mid m) = 0 }[/math], bo

[math]\displaystyle{ (a_k \mid m) = ((- 1)^k (2 k + 1) \mid m) = ((- 1)^k \mid m) \cdot (2 k + 1 \mid m) = (- 1 \mid m)^k \cdot (2 k + 1 \mid m) = \pm (2 k + 1 \mid m) }[/math]

Jeżeli będą spełnione warunki [math]\displaystyle{ (a_k \mid m) = 0 }[/math] i [math]\displaystyle{ R_m (a_k) \neq 0 }[/math], to liczba [math]\displaystyle{ m }[/math] będzie liczbą złożoną.

Wypiszmy kolejne próby dla [math]\displaystyle{ m \geqslant 23 }[/math]. Liczba [math]\displaystyle{ r }[/math] jest numerem próby.

[math]\displaystyle{ r = 1 , \;\; a_{r + 2} = - 7 }[/math]

●	[math]\displaystyle{ (- 7 \mid m) = 1 }[/math]	[math]\displaystyle{ 7 \nmid m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (- 7 \mid m) = 0 }[/math]	[math]\displaystyle{ 7 \mid m }[/math]	koniec
●	[math]\displaystyle{ (- 7 \mid m) = - 1 \quad }[/math]	[math]\displaystyle{ 7 \nmid m }[/math]	[math]\displaystyle{ D = - 7 , \;\; Q = 2 , \;\; \gcd (m, Q) = 1 , \;\; }[/math] koniec

[math]\displaystyle{ r = 2 , \;\; a_{r + 2} = 9 }[/math]

●	[math]\displaystyle{ (9 \mid m) = 1 }[/math]	[math]\displaystyle{ 3 \nmid m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (9 \mid m) = 0 }[/math]	[math]\displaystyle{ 3 \mid m }[/math]	koniec
●	[math]\displaystyle{ (9 \mid m) \neq - 1 \quad }[/math]	- - - -	bo [math]\displaystyle{ 9 }[/math] jest liczbą kwadratową

[math]\displaystyle{ r = 3 , \;\; a_{r + 2} = - 11 }[/math]

●	[math]\displaystyle{ (- 11 \mid m) = 1 }[/math]	[math]\displaystyle{ 11 \nmid m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (- 11 \mid m) = 0 }[/math]	[math]\displaystyle{ 11 \mid m }[/math]	koniec
●	[math]\displaystyle{ (- 11 \mid m) = - 1 \quad }[/math]	[math]\displaystyle{ 11 \nmid m }[/math]	[math]\displaystyle{ D = - 11 , \;\; Q = 3 , \;\; \gcd (m, Q) = 1 , \;\; }[/math] koniec (bo liczby złożone [math]\displaystyle{ m = 3 k }[/math] zostały usunięte w poprzedniej próbie, [math]\displaystyle{ r = 2 }[/math])

[math]\displaystyle{ r = 4 , \;\; a_{r + 2} = 13 }[/math]

●	[math]\displaystyle{ (13 \mid m) = 1 }[/math]	[math]\displaystyle{ 13 \nmid m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (13 \mid m) = 0 }[/math]	[math]\displaystyle{ 13 \mid m }[/math]	koniec
●	[math]\displaystyle{ (13 \mid m) = - 1 \quad }[/math]	[math]\displaystyle{ 13 \nmid m }[/math]	[math]\displaystyle{ D = 13 , \;\; Q = - 3 , \;\; \gcd (m, Q) = 1 , \;\; }[/math] koniec (bo liczby złożone [math]\displaystyle{ m = 3 k }[/math] zostały usunięte w próbie o numerze [math]\displaystyle{ r = 2 }[/math])

[math]\displaystyle{ r = 5 , \;\; a_{r + 2} = - 15 }[/math]

●	[math]\displaystyle{ (- 15 \mid m) = 1 }[/math]	[math]\displaystyle{ 5 \nmid m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (- 15 \mid m) = 0 }[/math]	[math]\displaystyle{ 5 \mid m }[/math]	koniec
●	[math]\displaystyle{ (- 15 \mid m) = - 1 \quad }[/math]	[math]\displaystyle{ 5 \nmid m }[/math]	[math]\displaystyle{ D = - 15 , \;\; Q = 4 , \;\; \gcd (m, Q) = 1 , \;\; }[/math] koniec

Po wykonaniu pięciu prób niezakończonych sukcesem (tzn. wykryciem złożoności [math]\displaystyle{ m }[/math] lub ustaleniem wartości liczb [math]\displaystyle{ D }[/math] i [math]\displaystyle{ Q }[/math]) wiemy, że [math]\displaystyle{ m }[/math] nie jest podzielna przez żadną z liczb pierwszych [math]\displaystyle{ p = 3, 5, 7, 11, 13 }[/math].

[math]\displaystyle{ r }[/math]-ta próba, gdzie [math]\displaystyle{ r \geqslant 6 , \;\; }[/math] wyraz [math]\displaystyle{ a_{r + 2} }[/math]

●	[math]\displaystyle{ (a_{r + 2} \mid m) = 1 }[/math]	żadna liczba pierwsza [math]\displaystyle{ p \leqslant \| a_{r + 2} \| = 2 r + 5 }[/math] nie dzieli liczby [math]\displaystyle{ m \quad }[/math]	przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math]
●	[math]\displaystyle{ (a_{r + 2} \mid m) = 0 }[/math]	A. jeżeli [math]\displaystyle{ m \mid a_{r + 2} }[/math]^{( * )} B. jeżeli [math]\displaystyle{ m \nmid a_{r + 2} }[/math]	A. przechodzimy do kolejnego wyrazu ciągu [math]\displaystyle{ (a_k) }[/math] B. [math]\displaystyle{ a_{r + 1} \mid m }[/math]^{( )}, koniec**
●	[math]\displaystyle{ (a_{r + 2} \mid m) = - 1 \quad }[/math]	żadna liczba pierwsza [math]\displaystyle{ p \leqslant \| a_{r + 2} \| = 2 r + 5 }[/math] nie dzieli liczby [math]\displaystyle{ m \quad }[/math]	[math]\displaystyle{ D = a_{r + 2} }[/math], [math]\displaystyle{ Q = {\small\frac{1 - a_{r + 2}}{4}} }[/math], koniec

^{( * )} jest to możliwe tylko dla [math]\displaystyle{ a_{r + 2} = a_{(m - 1) / 2} = m }[/math]

^{( ** )} zauważmy, że jeżeli [math]\displaystyle{ m \nmid a_{r + 2} }[/math], to [math]\displaystyle{ \gcd (a_{r + 2}, m) = | a_{r + 2} | }[/math], bo gdyby liczba [math]\displaystyle{ | a_{r + 2} | }[/math] była liczbą złożoną, to żaden z jej dzielników pierwszych nie dzieliłby liczby [math]\displaystyle{ m }[/math]

Jeżeli nie została wykryta złożoność liczby [math]\displaystyle{ m }[/math], to żadna z liczb pierwszych [math]\displaystyle{ p \leqslant | a_{r + 2} | = 2 r + 5 }[/math] nie dzieli liczby [math]\displaystyle{ m }[/math]. Zatem [math]\displaystyle{ \gcd (Q, m) \gt 1 }[/math] może być tylko w przypadku, gdy pewna liczba pierwsza [math]\displaystyle{ q \geqslant 2 r + 7 }[/math] będzie wspólnym dzielnikiem liczb [math]\displaystyle{ Q }[/math] i [math]\displaystyle{ m }[/math], ale jest to niemożliwe, bo

[math]\displaystyle{ | Q | = \left| {\small\frac{1 - a_{r + 2}}{4}} \right| \leqslant {\small\frac{| a_{r + 2} | + 1}{4}} = {\small\frac{2 r + 6}{4}} \lt 2 r + 7 \leqslant q }[/math]

Przedostatnia (ostra) nierówność jest prawdziwa dla wszystkich [math]\displaystyle{ r }[/math] naturalnych.
□

Uwaga N32
Przyjmując metodę Selfridge'a wyboru parametrów [math]\displaystyle{ P, Q }[/math] dla testu Lucasa, możemy łatwo napisać odpowiedni program w PARI/GP testujący pierwszość liczb

LucasTest(m) = 
{
local(P, Q, X);
if( m % 2 == 0, return(m == 2) );
if( issquare(m), return(0) ); \\ sprawdzamy, czy m nie jest liczbą kwadratową
X = MethodA(m);
P = X[1];
Q = X[2];
if( P == 0, return(0) ); \\ jeżeli P = 0, to m jest liczbą złożoną
if( modLucas(m + 1, P, Q, m)[1] == 0, return(1), return(0) );
}

Uwaga N33
Najmniejsze liczby pseudopierwsze Lucasa, które pojawiają się przy zastosowaniu metody Selfridge'a wyboru parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math], to

[math]\displaystyle{ 323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179, 10877, 11419, 11663, 13919, 14839, 16109, 16211, 18407, 18971, 19043, 22499, \ldots }[/math]

Pokaż kod

forstep(k=1, 3*10^4, 2, if( LucasTest(k) && !isprime(k), print(k)) )

Tabela przedstawia ilość takich liczb nie większych od [math]\displaystyle{ 10^n }[/math]

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]
#LPSP [math]\displaystyle{ \lt 10^n }[/math] (metoda Selfridge'a)	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 57 }[/math]	[math]\displaystyle{ 219 }[/math]	[math]\displaystyle{ 659 }[/math]	[math]\displaystyle{ 1911 }[/math]	[math]\displaystyle{ 5485 }[/math]

Pokaż kod

for(n=3, 9, s=0; forstep(k = 1, 10^n, 2, if( LucasTest(k) && !isprime(k), s++ ) ); print("n= ", n, "   ", s) )

Liczby silnie pseudopierwsze Lucasa

Twierdzenie N34
Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą taką, że [math]\displaystyle{ \gcd (p, Q D) = 1 }[/math] oraz [math]\displaystyle{ p - (D \mid p) = 2^r w }[/math], gdzie [math]\displaystyle{ w }[/math] jest liczbą nieparzystą, to spełniony jest dokładnie jeden z warunków

[math]\displaystyle{ U_w \equiv 0 \pmod{p} }[/math]

lub

[math]\displaystyle{ V_{2^k w} \equiv 0 \pmod{p} \qquad }[/math] dla pewnego [math]\displaystyle{ k \in [0, r - 1] }[/math]

Dowód

Wiemy (zobacz N20), że jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą taką, że [math]\displaystyle{ \gcd (p, Q D) = 1 }[/math], to [math]\displaystyle{ p \mid U_{p - (D \mid p)} }[/math]. Z założenia jest [math]\displaystyle{ p - (D \mid p) = 2^r w }[/math], zatem [math]\displaystyle{ p \mid U_{2^r w} }[/math]. Ponieważ założyliśmy, że [math]\displaystyle{ p \nmid Q }[/math] i [math]\displaystyle{ p \nmid D }[/math], to ze wzoru [math]\displaystyle{ V^2_n - D U^2_n = 4 Q^n }[/math] (zobacz N13 p.14) wynika natychmiast, że [math]\displaystyle{ p }[/math] nie może dzielić jednocześnie liczb [math]\displaystyle{ U_n }[/math] i [math]\displaystyle{ V_n }[/math].

Korzystając ze wzoru [math]\displaystyle{ U_{2 n} = U_n V_n }[/math] (zobacz N13 p.11), otrzymujemy

●	[math]\displaystyle{ p \mid U_{2^r w} \;\; \Longleftrightarrow \;\; p \mid U_{2^{r - 1} w} \cdot V_{2^{r - 1} w} \quad }[/math]	Jeżeli [math]\displaystyle{ p \mid V_{2^{r - 1} w} }[/math], to twierdzenie jest dowiedzione. Jeżeli [math]\displaystyle{ p \nmid V_{2^{r - 1} w} }[/math], to [math]\displaystyle{ p \mid U_{2^{r - 1} w} }[/math].
●	[math]\displaystyle{ p \mid U_{2^{r - 1} w} \;\; \Longleftrightarrow \;\; p \mid U_{2^{r - 2} w} \cdot V_{2^{r - 2} w} \quad }[/math]	Jeżeli [math]\displaystyle{ p \mid V_{2^{r - 2} w} }[/math], to twierdzenie jest dowiedzione. Jeżeli [math]\displaystyle{ p \nmid V_{2^{r - 2} w} }[/math], to [math]\displaystyle{ p \mid U_{2^{r - 2} w} }[/math].
●	[math]\displaystyle{ ................. }[/math]
●	[math]\displaystyle{ p \mid U_{4 w} \;\; \Longleftrightarrow \;\; p \mid U_{2 w} \cdot V_{2 w} }[/math]	Jeżeli [math]\displaystyle{ p \mid V_{2 w} }[/math], to twierdzenie jest dowiedzione. Jeżeli [math]\displaystyle{ p \nmid V_{2 w} }[/math], to [math]\displaystyle{ p \mid U_{2 w} }[/math].
●	[math]\displaystyle{ p \mid U_{2 w} \;\; \Longleftrightarrow \;\; p \mid U_w \cdot V_w }[/math]	Jeżeli [math]\displaystyle{ p \mid V_w }[/math], to twierdzenie jest dowiedzione. Jeżeli [math]\displaystyle{ p \nmid V_w }[/math], to [math]\displaystyle{ p \mid U_w }[/math].

Z powyższego wynika, że musi być spełniony jeden z wypisanych w twierdzeniu warunków.

Zauważmy teraz, że jeżeli liczba pierwsza [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ V_w }[/math], to [math]\displaystyle{ p \nmid U_w }[/math], bo [math]\displaystyle{ p }[/math] nie może jednocześnie być dzielnikiem liczb [math]\displaystyle{ U_w }[/math] i [math]\displaystyle{ V_w }[/math].

Zauważmy też, że jeżeli dla pewnego [math]\displaystyle{ k \in [1, r - 1] }[/math] liczba pierwsza [math]\displaystyle{ p }[/math] dzieli [math]\displaystyle{ V_{2^k w} }[/math], to [math]\displaystyle{ p }[/math] nie dzieli żadnej liczby [math]\displaystyle{ V_{2^j w} }[/math] dla [math]\displaystyle{ j \in [0, k - 1] \;\; \text{i} \;\; p \nmid U_w }[/math]. Istotnie:

●	jeżeli [math]\displaystyle{ p \mid V_{2^k w} }[/math], to [math]\displaystyle{ p \nmid U_{2^k w} \;\; \text{i} \;\; U_{2^k w} = U_{2^{k - 1} w} V_{2^{k - 1} w} }[/math], zatem [math]\displaystyle{ p }[/math] nie może być dzielnikiem żadnej z liczb [math]\displaystyle{ U_{2^{k - 1} w} \;\; \text{i} \;\; V_{2^{k - 1} w} }[/math]
●	jeżeli [math]\displaystyle{ p \nmid U_{2^{k - 1} w} \;\; \text{i} \;\; U_{2^{k - 1} w} = U_{2^{k - 2} w} V_{2^{k - 2} w} }[/math], to [math]\displaystyle{ p }[/math] nie może być dzielnikiem żadnej z liczb [math]\displaystyle{ U_{2^{k - 2} w} \;\; \text{i} \;\; V_{2^{k - 2} w} }[/math]
●	[math]\displaystyle{ ................. }[/math]
●	jeżeli [math]\displaystyle{ p \nmid U_{4 w} \;\; \text{i} \;\; U_{4 w} = U_{2 w} V_{2 w} }[/math], to [math]\displaystyle{ p }[/math] nie może być dzielnikiem żadnej z liczb [math]\displaystyle{ U_{2 w} \;\; \text{i} \;\; V_{2 w} }[/math]
●	jeżeli [math]\displaystyle{ p \nmid U_{2 w} \;\; \text{i} \;\; U_{2 w} = U_w V_w }[/math], to [math]\displaystyle{ p }[/math] nie może być dzielnikiem żadnej z liczb [math]\displaystyle{ U_w \;\; \text{i} \;\; V_w }[/math]

Co dowodzi, że spełniony jest dokładnie jeden z [math]\displaystyle{ r + 1 }[/math] warunków:

[math]\displaystyle{ U_w \equiv 0 \pmod{p} }[/math]

[math]\displaystyle{ V_{2^k w} \equiv 0 \pmod{p} \qquad }[/math] gdzie [math]\displaystyle{ k \in [0, r - 1] }[/math]

Co należało pokazać.
□

Konsekwentnie definiujemy liczby pseudopierwsze
Definicja N35
Powiemy, że liczba złożona nieparzysta [math]\displaystyle{ m }[/math] jest liczbą silnie pseudopierwszą Lucasa (SLPSP) dla parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math], jeżeli [math]\displaystyle{ \gcd (m, Q D) = 1 }[/math] oraz [math]\displaystyle{ m - (D \mid m) = 2^r w }[/math], gdzie [math]\displaystyle{ w }[/math] jest liczbą nieparzystą i spełniony jest jeden z warunków

[math]\displaystyle{ U_w \equiv 0 \pmod{m} }[/math]

lub

[math]\displaystyle{ V_{2^k w} \equiv 0 \pmod{m} \; }[/math] dla pewnego [math]\displaystyle{ k \in [0, r - 1] }[/math]

Uwaga N36
Każda liczba SLPSP([math]\displaystyle{ P, Q }[/math]) jest LPSP([math]\displaystyle{ P, Q }[/math]). Korzystając ze zdefiniowanych wcześniej funkcji: modPower(a, n, m), jacobi(a, n) i modLucas(n, P, Q, m) (zobacz M2, J48, N15), możemy napisać prosty program, który sprawdza, czy liczba [math]\displaystyle{ m }[/math] spełnia jeden z warunków podanych w twierdzeniu N34.

isPrimeOrSLPSP(m, P, Q) = 
{
local(a, b, c, D, js, k, r, w, X);
D = P^2 - 4*Q;
if( gcd(m, 2*Q*D) > 1, return(0) );
js = jacobi(D, m);
r = valuation(m - js, 2); \\ znajdujemy wykładnik, z jakim liczba 2 występuje w m - js
w = (m - js) / 2^r;
X =  modLucas(w, P, Q, m);
a = X[1]; \\ U_w(P, Q) % m
b = X[2]; \\ V_w(P, Q) % m
if( a == 0 || b == 0, return(1) ); \\ b == 0 to przypadek k == 0
if( r == 1, return(0) ); \\ nie ma dalszych przypadków
c = modPower(Q, w, m); \\ Q^w % m
k = 0;
\\ sprawdzamy warunek V_(2^k * w) % m = 0; korzystamy ze wzoru V_(2*t) = (V_t)^2 - 2*Q^t
while( k++ < r,
       b = (b^2 - 2*c) % m;
       if( b == 0, return(1) );
       c = c^2 % m;
     );
return(0);
}

Przykład N37
Poniższa tabela zawiera najmniejsze liczby silnie pseudopierwsze Lucasa dla różnych parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math]

[math]\displaystyle{ \boldsymbol{P} }[/math] [math]\displaystyle{ \boldsymbol{Q} }[/math]	[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]
[math]\displaystyle{ \boldsymbol{- 5} }[/math]	[math]\displaystyle{ 253 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 143 }[/math]	[math]\displaystyle{ 781 }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 299 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 407 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 143 }[/math]
[math]\displaystyle{ \boldsymbol{- 4} }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 4181 }[/math]	[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 169 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ 119 }[/math]	[math]\displaystyle{ 57 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]
[math]\displaystyle{ \boldsymbol{- 3} }[/math]	[math]\displaystyle{ 799 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 527 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 85 }[/math]	[math]\displaystyle{ 209 }[/math]	[math]\displaystyle{ 55 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 169 }[/math]	[math]\displaystyle{ 529 }[/math]
[math]\displaystyle{ \boldsymbol{- 2} }[/math]	[math]\displaystyle{ 2047 }[/math]	[math]\displaystyle{ 989 }[/math]	[math]\displaystyle{ 161 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 265 }[/math]
[math]\displaystyle{ \boldsymbol{- 1} }[/math]	[math]\displaystyle{ 4181 }[/math]	[math]\displaystyle{ 169 }[/math]	[math]\displaystyle{ 119 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 629 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 33 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 51 }[/math]
[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 209 }[/math]	[math]\displaystyle{ 527 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 559 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 49 }[/math]
[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ 5459 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 2047 }[/math]	[math]\displaystyle{ 169 }[/math]	[math]\displaystyle{ 21 }[/math]	[math]\displaystyle{ 253 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 15 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 49 }[/math]
[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ 899 }[/math]	[math]\displaystyle{ 5983 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 121 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 35 }[/math]	[math]\displaystyle{ 55 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 35 }[/math]
[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ 899 }[/math]	[math]\displaystyle{ 25 }[/math]	[math]\displaystyle{ 1541 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 341 }[/math]	[math]\displaystyle{ 323 }[/math]	[math]\displaystyle{ 377 }[/math]	[math]\displaystyle{ 209 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 527 }[/math]
[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 527 }[/math]	[math]\displaystyle{ 49 }[/math]	[math]\displaystyle{ 527 }[/math]	[math]\displaystyle{ 4181 }[/math]	[math]\displaystyle{ 781 }[/math]	[math]\displaystyle{ 39 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]	[math]\displaystyle{ 9 }[/math]

Pokaż kod

FirstSLPSP(Stop) = 
\\ najmniejsze SLPSP(P,Q) < Stop;  dla 1<=P<=10 i -5<=Q<=5
{
local(D, m, P, Q);
Q = -6;
while( Q++ <= 5,
       if( Q == 0, next() );
       P = 0;
       while( P++ <= 10,
              D = P^2 - 4*Q;
              if( D == 0, 
                  print("Q= ", Q, "   P= ", P, "   ------------------");
                  next();
                );
              m = 3;
              while( m < Stop,
                     if( isPrimeOrSLPSP(m, P, Q)  &&  !isprime(m), 
                         print("Q= ", Q, "   P= ", P, "   m= ", m, "   (D|m)= ", jacobi(D, m));
                         break();
                       );
                     m = m + 2;
                   );
           );
     );
}

Żółtym tłem oznaczyliśmy te najmniejsze liczby pseudopierwsze Lucasa, dla których [math]\displaystyle{ (D \mid m) = - 1 }[/math].

Przykład N38
Ilość liczb SLPSP([math]\displaystyle{ P, Q }[/math]) mniejszych od [math]\displaystyle{ 10^9 }[/math]

[math]\displaystyle{ \boldsymbol{P} }[/math] [math]\displaystyle{ \boldsymbol{Q} }[/math]	[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]	[math]\displaystyle{ \boldsymbol{10} }[/math]
[math]\displaystyle{ \boldsymbol{- 5} }[/math]	[math]\displaystyle{ 1056 }[/math]	[math]\displaystyle{ 1231 }[/math]	[math]\displaystyle{ 1184 }[/math]	[math]\displaystyle{ 1264 }[/math]	[math]\displaystyle{ 2278 }[/math]	[math]\displaystyle{ 1284 }[/math]	[math]\displaystyle{ 1181 }[/math]	[math]\displaystyle{ 1174 }[/math]	[math]\displaystyle{ 1281 }[/math]	[math]\displaystyle{ 1429 }[/math]
[math]\displaystyle{ \boldsymbol{- 4} }[/math]	[math]\displaystyle{ 1043 }[/math]	[math]\displaystyle{ 1165 }[/math]	[math]\displaystyle{ 2139 }[/math]	[math]\displaystyle{ 1316 }[/math]	[math]\displaystyle{ 1151 }[/math]	[math]\displaystyle{ 1079 }[/math]	[math]\displaystyle{ 1112 }[/math]	[math]\displaystyle{ 2377 }[/math]	[math]\displaystyle{ 1197 }[/math]	[math]\displaystyle{ 989 }[/math]
[math]\displaystyle{ \boldsymbol{- 3} }[/math]	[math]\displaystyle{ 952 }[/math]	[math]\displaystyle{ 1514 }[/math]	[math]\displaystyle{ 1055 }[/math]	[math]\displaystyle{ 1153 }[/math]	[math]\displaystyle{ 1135 }[/math]	[math]\displaystyle{ 2057 }[/math]	[math]\displaystyle{ 998 }[/math]	[math]\displaystyle{ 1202 }[/math]	[math]\displaystyle{ 1077 }[/math]	[math]\displaystyle{ 1112 }[/math]
[math]\displaystyle{ \boldsymbol{- 2} }[/math]	[math]\displaystyle{ 1282 }[/math]	[math]\displaystyle{ 1092 }[/math]	[math]\displaystyle{ 1212 }[/math]	[math]\displaystyle{ 1510 }[/math]	[math]\displaystyle{ 1155 }[/math]	[math]\displaystyle{ 1179 }[/math]	[math]\displaystyle{ 1173 }[/math]	[math]\displaystyle{ 2240 }[/math]	[math]\displaystyle{ 1089 }[/math]	[math]\displaystyle{ 2109 }[/math]
[math]\displaystyle{ \boldsymbol{- 1} }[/math]	[math]\displaystyle{ 1165 }[/math]	[math]\displaystyle{ 1316 }[/math]	[math]\displaystyle{ 1079 }[/math]	[math]\displaystyle{ 2377 }[/math]	[math]\displaystyle{ 989 }[/math]	[math]\displaystyle{ 1196 }[/math]	[math]\displaystyle{ 1129 }[/math]	[math]\displaystyle{ 1050 }[/math]	[math]\displaystyle{ 1055 }[/math]	[math]\displaystyle{ 1147 }[/math]
[math]\displaystyle{ \boldsymbol{1} }[/math]	[math]\displaystyle{ 282485800 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 2278 }[/math]	[math]\displaystyle{ 2057 }[/math]	[math]\displaystyle{ 2113 }[/math]	[math]\displaystyle{ 2266 }[/math]	[math]\displaystyle{ 4053 }[/math]	[math]\displaystyle{ 2508 }[/math]	[math]\displaystyle{ 2285 }[/math]	[math]\displaystyle{ 3083 }[/math]
[math]\displaystyle{ \boldsymbol{2} }[/math]	[math]\displaystyle{ 1776 }[/math]	[math]\displaystyle{ 449152466 }[/math]	[math]\displaystyle{ 1282 }[/math]	[math]\displaystyle{ 1316 }[/math]	[math]\displaystyle{ 1645 }[/math]	[math]\displaystyle{ 1413 }[/math]	[math]\displaystyle{ 1564 }[/math]	[math]\displaystyle{ 1595 }[/math]	[math]\displaystyle{ 1683 }[/math]	[math]\displaystyle{ 1435 }[/math]
[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ 1621 }[/math]	[math]\displaystyle{ 1553 }[/math]	[math]\displaystyle{ 282485800 }[/math]	[math]\displaystyle{ 1514 }[/math]	[math]\displaystyle{ 1530 }[/math]	[math]\displaystyle{ 1510 }[/math]	[math]\displaystyle{ 1588 }[/math]	[math]\displaystyle{ 1549 }[/math]	[math]\displaystyle{ 1468 }[/math]	[math]\displaystyle{ 1692 }[/math]
[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ 2760 }[/math]	[math]\displaystyle{ 282485800 }[/math]	[math]\displaystyle{ 2978 }[/math]	[math]\displaystyle{ }[/math]	[math]\displaystyle{ 2137 }[/math]	[math]\displaystyle{ 2278 }[/math]	[math]\displaystyle{ 1995 }[/math]	[math]\displaystyle{ 2057 }[/math]	[math]\displaystyle{ 2260 }[/math]	[math]\displaystyle{ 2113 }[/math]
[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ 1314 }[/math]	[math]\displaystyle{ 2392 }[/math]	[math]\displaystyle{ 1497 }[/math]	[math]\displaystyle{ 2392 }[/math]	[math]\displaystyle{ 1165 }[/math]	[math]\displaystyle{ 1268 }[/math]	[math]\displaystyle{ 1227 }[/math]	[math]\displaystyle{ 1411 }[/math]	[math]\displaystyle{ 1253 }[/math]	[math]\displaystyle{ 2377 }[/math]

Pokaż kod

NumOfSLPSP(Stop) = 
\\ ilość liczb silnie pseudopierwszych Lucasa SLPSP(P,Q) < Stop;  dla 1<=P<=10 i -5<=Q<=5
{
local(D, m, P, Q);
Q = -6;
while( Q++ <= 5,
       if( Q == 0, next() );
       P = 0;
       while( P++ <= 10,
              D = P^2 - 4*Q;
              if( D == 0, print("Q= ", Q, "   P= ", P, "   ------------------"); next() );
              s = 0;
              m = 3;
              while( m < Stop,
                     if( isPrimeOrSLPSP(m, P, Q)  &&  !isprime(m), s++ );
                     m = m + 2;
                   );
              print("Q= ", Q, "   P= ", P, "   s= ", s);
            );
     );
}

Uwaga N39
Można pokazać^[2], że dla liczby złożonej nieparzystej [math]\displaystyle{ m \neq 9 }[/math] i ustalonego [math]\displaystyle{ D }[/math] ilość par [math]\displaystyle{ P, Q }[/math] takich, że

[math]\displaystyle{ 0 \leqslant P, Q \lt m }[/math]
[math]\displaystyle{ \gcd (Q, m) = 1 }[/math]
[math]\displaystyle{ P^2 - 4 Q \equiv D \pmod{m} }[/math]
[math]\displaystyle{ m }[/math] jest SLPSP([math]\displaystyle{ P, Q }[/math])

nie przekracza [math]\displaystyle{ \tfrac{4}{15} n }[/math].

Nie dotyczy to przypadku, gdy [math]\displaystyle{ m = p (p + 2) }[/math] jest iloczynem liczb pierwszych bliźniaczych takich, że [math]\displaystyle{ (D \mid p) = - (D \mid p + 2) = - 1 }[/math], wtedy mamy słabsze oszacowanie: [math]\displaystyle{ \# (P, Q) \leqslant \tfrac{1}{2} n }[/math]. Zauważmy, że taką sytuację łatwo wykryć, bo w tym przypadku [math]\displaystyle{ m + 1 = (p + 1)^2 }[/math] jest liczbą kwadratową.

Uwaga N40
Podobnie jak w przypadku liczb pseudopierwszych Lucasa LPSP([math]\displaystyle{ P, Q }[/math]) tak i w przypadku liczb silnie pseudopierwszych Lucasa SLPSP([math]\displaystyle{ P, Q }[/math]) możemy testować pierwszość liczby [math]\displaystyle{ m }[/math], wybierając liczby [math]\displaystyle{ P, Q }[/math] losowo lub zastosować wybraną metodę postępowania. Przedstawiony poniżej program, to zmodyfikowany kod z uwagi N36. Teraz parametry [math]\displaystyle{ P, Q }[/math] są wybierane metodą Selfridge'a, a symbol Jacobiego [math]\displaystyle{ (D \mid m) }[/math] jest równy [math]\displaystyle{ - 1 }[/math].

StrongLucasTest(m) =
{
local(a, b, c, k, P, Q, r, w, X);
if( m % 2 == 0, return(m == 2) );
if( issquare(m), return(0) ); \\ sprawdzamy, czy liczba m nie jest kwadratowa
X = MethodA(m);
P = X[1];
Q = X[2];
if( P == 0 || gcd(m, 2*Q) > 1, return(0) ); \\ jeżeli P = 0, to m jest liczbą złożoną
r = valuation(m + 1, 2); \\ znajdujemy wykładnik, z jakim liczba 2 występuje w m + 1
w = (m + 1) / 2^r;
X =  modLucas(w, P, Q, m);
a = X[1]; \\ U_w(P, Q) % m
b = X[2]; \\ V_w(P, Q) % m
if( a == 0 || b == 0, return(1) ); \\ b == 0 to przypadek k == 0
if( r == 1, return(0) ); \\ nie ma dalszych przypadków
c = modPower(Q, w, m); \\ Q^w % m
k = 0;
\\ sprawdzamy warunek V_(2^k * w) %m = 0; korzystamy ze wzoru V_(2*w) = (V_w)^2 - 2*Q^w
while( k++ < r,
       b = (b^2 - 2*c) % m;
       if( b == 0, return(1) );
       c = c^2 % m;
     );
return(0);
}

Uwaga N41
Najmniejsze liczby silnie pseudopierwsze Lucasa, które otrzymujemy po zastosowaniu metody Selfridge'a wyboru parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math], to

[math]\displaystyle{ 5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, 58519, 75077, 97439, \ldots }[/math]

Pokaż kod

forstep(k=1, 10^5, 2, if( StrongLucasTest(k) && !isprime(k), print(k)) )

Tabela przedstawia ilość takich liczb nie większych od [math]\displaystyle{ 10^n }[/math]

[math]\displaystyle{ \boldsymbol{n} }[/math]	[math]\displaystyle{ \boldsymbol{3} }[/math]	[math]\displaystyle{ \boldsymbol{4} }[/math]	[math]\displaystyle{ \boldsymbol{5} }[/math]	[math]\displaystyle{ \boldsymbol{6} }[/math]	[math]\displaystyle{ \boldsymbol{7} }[/math]	[math]\displaystyle{ \boldsymbol{8} }[/math]	[math]\displaystyle{ \boldsymbol{9} }[/math]
#SLPSP [math]\displaystyle{ \lt 10^n }[/math] (metoda Selfridge'a)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 2 }[/math]	[math]\displaystyle{ 12 }[/math]	[math]\displaystyle{ 58 }[/math]	[math]\displaystyle{ 178 }[/math]	[math]\displaystyle{ 505 }[/math]	[math]\displaystyle{ 1415 }[/math]

Pokaż kod

for(n=3, 9, s=0; forstep(k = 1, 10^n, 2, if( StrongLucasTest(k) && !isprime(k), s++ ) ); print("n=", n, "   ", s) )

Test BPSW

Uwaga N42
Jest [math]\displaystyle{ 488 }[/math] liczb SPSP([math]\displaystyle{ 2 }[/math]) mniejszych od [math]\displaystyle{ 10^8 }[/math] i są 582 liczby SPSP([math]\displaystyle{ 3 }[/math]) mniejsze od [math]\displaystyle{ 10^8 }[/math] (zobacz M21). Ale jest aż [math]\displaystyle{ 21 }[/math] liczb mniejszych od [math]\displaystyle{ 10^8 }[/math] silnie pseudopierwszych jednocześnie względem podstaw [math]\displaystyle{ 2 }[/math] i [math]\displaystyle{ 3 }[/math]:

[math]\displaystyle{ 1373653, 1530787, 1987021, 2284453, 3116107, 5173601, 6787327, 11541307, 13694761, 15978007, 16070429, }[/math]

[math]\displaystyle{ 16879501, 25326001, 27509653, 27664033, 28527049, 54029741, 61832377, 66096253, 74927161, 80375707 }[/math]

Pokaż kod

forstep(m=3, 10^8, 2, if( isPrimeOrSPSP(m, 2)  &&  isPrimeOrSPSP(m, 3)  &&  !isprime(m), print("m=", m) ) )

Widzimy, że prawdopodobieństwo błędnego rozpoznania pierwszości w przypadku liczb mniejszych od [math]\displaystyle{ 10^8 }[/math] dla podstawy [math]\displaystyle{ 2 }[/math] lub podstawy [math]\displaystyle{ 3 }[/math] jest rzędu kilku milionowych. Gdyby prawdopodobieństwa błędnego rozpoznania pierwszości w przypadku podstawy [math]\displaystyle{ 2 }[/math] lub podstawy [math]\displaystyle{ 3 }[/math] były niezależne, to spodziewalibyśmy się, że nie będzie wcale liczb mniejszych od [math]\displaystyle{ 10^8 }[/math] silnie pseudopierwszych jednocześnie względem podstaw [math]\displaystyle{ 2 }[/math] i [math]\displaystyle{ 3 }[/math], bo prawdopodobieństwo takiego zdarzenia byłoby równe kilkudziesięciu bilonowym. Ale tak nie jest.

Jest to mocny argument za tym, że zastosowanie różnych (niezależnych) testów może być znacznie silniejszym narzędziem do testowania pierwszości liczb, niż wielokrotne stosowanie tego samego testu, gdzie poszczególne próby są tylko pozornie niezależne.

Połączenie znanych nam już testów prowadzi do prostego programu

BPSWtest(m) =
{
forprime(p = 2, 1000, if( m % p > 0, next() ); if( m == p, return(1), return(0) ));
if( !isPrimeOrSPSP(m, 2), return(0) );
if( !StrongLucasTest(m), return(0), return(1) );
}

Funkcja BPSWtest(m) kolejno sprawdza:

czy liczba [math]\displaystyle{ m }[/math] jest podzielna przez niewielkie liczby pierwsze (w naszym przypadku mniejsze od [math]\displaystyle{ 1000 }[/math]); jeśli tak, to sprawdza, czy [math]\displaystyle{ m }[/math] jest liczbą pierwszą, czy złożoną i zwraca odpowiednio [math]\displaystyle{ 1 }[/math] lub [math]\displaystyle{ 0 }[/math]
czy liczba [math]\displaystyle{ m }[/math] przechodzi test Millera-Rabina dla podstawy [math]\displaystyle{ 2 }[/math]; jeśli nie, to zwraca [math]\displaystyle{ 0 }[/math]
czy liczba [math]\displaystyle{ m }[/math] przechodzi silny test Lucasa dla parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math], które wybieramy metodą Selfridge'a; jeśli nie, to zwraca [math]\displaystyle{ 0 }[/math], w przeciwnym wypadku zwraca [math]\displaystyle{ 1 }[/math]

Test w dokładnie takiej postaci zaproponowali Robert Baillie i Samuel Wagstaff^[1]. Nazwa testu to akronim, utworzony od pierwszych liter nazwisk Roberta Bailliego, Carla Pomerance'a, Johna Selfridge'a i Samuela Wagstaffa.

Nie jest znany żaden przykład liczby złożonej [math]\displaystyle{ m }[/math], którą test BPSW^[3]^[4] identyfikowałby jako pierwszą i z pewnością nie ma takich liczb dla [math]\displaystyle{ m \lt 2^{64} \approx 1.844 \cdot 10^{19} }[/math]. Warto przypomnieć: potrzebowaliśmy siedmiu testów Millera-Rabina (dla podstaw [math]\displaystyle{ 2, 3, 5, 7, 11, 13, 17 }[/math]), aby mieć pewność, że dowolna liczba [math]\displaystyle{ m \lt 3.41 \cdot 10^{14} }[/math] jest pierwsza (zobacz M22).

Uzupełnienia

Pewne własności współczynników dwumianowych

Twierdzenie N43
Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą, to

[math]\displaystyle{ \binom{p}{k} \equiv 0 \pmod{p} }[/math]

dla każdego [math]\displaystyle{ k \in [1, p - 1] }[/math].

Dowód

Łatwo zauważamy, że dla [math]\displaystyle{ k \in [1, p - 1] }[/math] liczba pierwsza [math]\displaystyle{ p }[/math] dzieli licznik, ale nie dzieli mianownika współczynnika dwumianowego

[math]\displaystyle{ \binom{p}{k} = {\small\frac{p!}{k! \cdot (p - k)!}} }[/math]

zatem [math]\displaystyle{ p \biggr\rvert \binom{p}{k} }[/math]. Co należało pokazać.
□

Twierdzenie N44
Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą, to

[math]\displaystyle{ \binom{p + 1}{k} \equiv 0 \pmod{p} }[/math]

dla każdego [math]\displaystyle{ k \in [2, p - 1] }[/math].

Dowód

Jeżeli [math]\displaystyle{ k \in [2, p - 1] }[/math], to modulo [math]\displaystyle{ p }[/math] dostajemy

[math]\displaystyle{ \binom{p + 1}{k} = \binom{p}{k} + \binom{p}{k - 1} \equiv 0 \pmod{p} }[/math]

Bo liczba pierwsza [math]\displaystyle{ p }[/math] dzieli licznik, ale nie dzieli mianownika współczynników dwumianowych po prawej stronie. Co należało pokazać.
□

Twierdzenie N45
Jeżeli [math]\displaystyle{ p }[/math] jest liczbą pierwszą, to

[math]\displaystyle{ \binom{p - 1}{k} \equiv (- 1)^k \pmod{p} }[/math]

dla każdego [math]\displaystyle{ k \in [0, p - 1] }[/math].

Dowód

Łatwo sprawdzamy, że twierdzenie jest prawdziwe dla liczby pierwszej parzystej [math]\displaystyle{ p = 2 }[/math]. Załóżmy, że [math]\displaystyle{ p }[/math] jest liczbą pierwszą nieparzystą. Równie łatwo sprawdzamy, że twierdzenie jest prawdziwe dla [math]\displaystyle{ k = 0 }[/math] i [math]\displaystyle{ k = 1 }[/math]. Zauważmy, że dla [math]\displaystyle{ k \in [1, p - 1] }[/math] jest

[math]\displaystyle{ \binom{p - 1}{k} = {\small\frac{(p - 1) !}{k! (p - 1 - k) !}} = {\small\frac{p - k}{k}} \cdot {\small\frac{(p - 1) !}{(k - 1) ! (p - k) !}} = {\small\frac{p - k}{k}} \cdot \binom{p - 1}{k - 1} = {\small\frac{p}{k}} \cdot \binom{p - 1}{k - 1} - \binom{p - 1}{k - 1} }[/math]

Ponieważ współczynniki dwumianowe są liczbami całkowitymi, a liczba [math]\displaystyle{ k \in [2, p - 1] }[/math] nie dzieli liczby pierwszej nieparzystej [math]\displaystyle{ p }[/math], to [math]\displaystyle{ k }[/math] musi dzielić liczbę [math]\displaystyle{ \binom{p - 1}{k - 1} }[/math]. Zatem dla [math]\displaystyle{ k \in [2, p - 1] }[/math] modulo [math]\displaystyle{ p }[/math] mamy

[math]\displaystyle{ \binom{p - 1}{k} \equiv - \binom{p - 1}{k - 1}\pmod{p} }[/math]

Skąd otrzymujemy

[math]\displaystyle{ \binom{p - 1}{k} \equiv (- 1)^1 \binom{p - 1}{k - 1} \equiv (- 1)^2 \binom{p - 1}{k - 2} \equiv \ldots \equiv (- 1)^{k - 2} \binom{p - 1}{2} \equiv (- 1)^{k - 1} \binom{p - 1}{1} \equiv (- 1)^k \pmod{p} }[/math]

Co należało pokazać. Zobacz też zadanie H22.
□

Twierdzenie N46
Dla współczynników dwumianowych prawdziwe są następujące wzory

[math]\displaystyle{ \underset{k \; \text{parzyste}}{\sum_{k = 0}^{n}} \binom{n}{k} = 2^{n - 1} }[/math]

[math]\displaystyle{ \underset{k \; \text{nieparzyste}}{\sum_{k = 1}^{n}} \binom{n}{k} = 2^{n - 1} }[/math]

Dowód

Ze wzoru dwumianowego

[math]\displaystyle{ (a + b)^n = \sum_{k = 0}^{n} \binom{n}{k} a^{n - k} b^k }[/math]

z łatwością otrzymujemy

[math]\displaystyle{ (1 + 1)^n = \sum_{k = 0}^{n} \binom{n}{k} = 2^n }[/math]

[math]\displaystyle{ (1 - 1)^n = \sum_{k = 0}^{n} (- 1)^k \binom{n}{k} = 0 }[/math]

Obliczając sumę i różnicę powyższych wzorów mamy

[math]\displaystyle{ \sum_{k = 0}^{n} \binom{n}{k} (1 + (- 1)^k) = 2 \underset{k \; \text{parzyste}}{\sum^n_{k = 0}} \binom{n}{k} = 2^n }[/math]

[math]\displaystyle{ \sum_{k = 0}^{n} \binom{n}{k} (1 - (- 1)^k) = 2 \underset{k \; \text{nieparzyste}}{\sum_{k = 1}^{n}} \binom{n}{k} = 2^n }[/math]

Skąd natychmiast wynika

[math]\displaystyle{ \underset{k \; \text{parzyste}}{\sum_{k = 0}^{n}} \binom{n}{k} = 2^{n - 1} }[/math]

[math]\displaystyle{ \underset{k \; \text{nieparzyste}}{\sum_{k = 1}^{n}} \binom{n}{k} = 2^{n - 1} }[/math]

Co należało pokazać.
□

Funkcje `digits(m, b)` oraz `issquare(m)`

Uwaga N47
W funkcji modLucas() wykorzystaliśmy zaimplementowaną w PARI/GP funkcję

digits(m, b) – zwraca wektor cyfr liczby [math]\displaystyle{ | m | }[/math] w systemie liczbowym o podstawie [math]\displaystyle{ b }[/math]

W naszym przypadku potrzebowaliśmy uzyskać wektor cyfr liczby [math]\displaystyle{ m }[/math] w układzie dwójkowym, czyli funkcję digits(m, 2) . Wprowadzenie tej funkcji pozwoliło zwiększyć czytelność kodu, ale bez trudu możemy ją sami napisać. Zauważmy, że do zapisania liczby [math]\displaystyle{ m \geqslant 1 }[/math] potrzebujemy [math]\displaystyle{ \log_2 m + 1 }[/math] cyfr. Zastępując funkcję [math]\displaystyle{ \log_2 m }[/math] funkcją [math]\displaystyle{ \left \lfloor \tfrac{\log m}{\log 2} \right \rfloor }[/math] musimy liczyć się z możliwym błędem zaokrąglenia – dlatego w programie deklarujemy wektor V o długości floor( log(m)/log(2) ) + 2. Zwracany wektor W ma już prawidłową długość.

Dec2Bin(m) = 
\\ zwraca wektor cyfr liczby m w układzie dwójkowym
{
local(i, k, V, W);
if( m == 0, return([0]) );
V = vector( floor( log(m)/log(2) ) + 2 ); \\ potrzeba floor( log(m)/log(2) ) + 1, ale błąd zaokrąglenia może zepsuć wynik
k = 0;
while( m > 0,
       V[k++] = m % 2;
       m = floor(m / 2);
     );
W = vector(k);
for(i = 1, k, W[i] = V[k + 1 - i]);
return(W);
}

Uwaga N48
W funkcjach LucasTest() i StrongLucasTest() wykorzystaliśmy zaimplementowaną w PARI/GP funkcję

issquare(m) – sprawdza, czy liczba [math]\displaystyle{ m }[/math] jest liczbą kwadratową

Wprowadzenie tej funkcji pozwoliło zwiększyć czytelność kodu, ale bez trudu możemy ją sami napisać. Potrzebna nam będzie funkcja, która znajduje całość z pierwiastka z liczby [math]\displaystyle{ m }[/math], czyli [math]\displaystyle{ \left\lfloor \sqrt{m} \right\rfloor }[/math]. Wykorzystamy tutaj ciąg

[math]\displaystyle{ a_{k + 1} = \begin{cases} \qquad \;\; 1 & \text{gdy } k = 0 \\ \tfrac{1}{2} \left( a_k + \tfrac{x}{a_k} \right) & \text{gdy } k \gt 0 \\ \end{cases} }[/math]

którego granicą jest [math]\displaystyle{ \sqrt{x} }[/math] ^[5].

Modyfikując powyższą definicję tak, aby operacje były zawsze wykonywane na liczbach całkowitych^[6]

[math]\displaystyle{ a_{k + 1} = \begin{cases} \qquad \quad \; 1 & \text{gdy } k = 0 \\ \left\lfloor \tfrac{1}{2} \left( a_k + \left\lfloor \tfrac{m}{a_k} \right\rfloor \right) \right\rfloor & \text{gdy } k \gt 0 \\ \end{cases} }[/math]

otrzymujemy ciąg, którego wszystkie wyrazy, począwszy od pewnego skończonego [math]\displaystyle{ n_0 }[/math], są równe [math]\displaystyle{ \left\lfloor \sqrt{m} \right\rfloor }[/math]. Nie dotyczy to przypadku, gdy [math]\displaystyle{ m + 1 }[/math] jest liczbą kwadratową, wtedy, począwszy od pewnego skończonego [math]\displaystyle{ n_0 }[/math], wyrazy ciągu przyjmują na zmianę wartości [math]\displaystyle{ \left\lfloor \sqrt{m} \right\rfloor }[/math] oraz [math]\displaystyle{ \left\lfloor \sqrt{m} \right\rfloor + 1 }[/math].

Na tej podstawie możemy w PARI/GP napisać funkcję

intSqrt(m) = 
{
local(a, b);
if( m == 0, return(0) );
a = 2^( floor( log(m)/log(2)/2 ) + 2 ); \\ musi być a > sqrt(m)
b = floor(( a + floor( m/a ) )/2);
while( b < a,
       a = b;
       b = floor( ( a + floor(m/a) )/2 );
     );
return(a);
}

Oczywiście liczba [math]\displaystyle{ m }[/math] jest liczbą kwadratową, wtedy i tylko wtedy, gdy [math]\displaystyle{ m = \left\lfloor \sqrt{m} \right\rfloor^2 }[/math], zatem wystarczy sprawdzić, czy m == intSqrt(m)^2.

Przypisy

↑ ^1,0 ^1,1 Robert Baillie and Samuel S. Wagstaff Jr., Lucas Pseudoprimes, Mathematics of Computation Vol. 35, No. 152 (1980), (LINK)
↑ François Arnault, The Rabin-Monier Theorem for Lucas Pseudoprimes, Mathematics of Computation Vol. 66, No. 218 (1997)
↑ Wikipedia, Baillie–PSW primality test, (Wiki-en)
↑ MathWorld, Baillie-PSW Primality Test, (LINK)
↑ Wikipedia, Pierwiastek kwadratowy, (Wiki-pl), (Wiki-en)
↑ Wikipedia, Integer square root, (Wiki-en)

[BaillieWagstaff1-1] 1,0 ^1,1 Robert Baillie and Samuel S. Wagstaff Jr., Lucas Pseudoprimes, Mathematics of Computation Vol. 35, No. 152 (1980), (LINK)

[Arnault1-2] François Arnault, The Rabin-Monier Theorem for Lucas Pseudoprimes, Mathematics of Computation Vol. 66, No. 218 (1997)

[BPSW1-3] Wikipedia, Baillie–PSW primality test, (Wiki-en)

[BPSW2-4] MathWorld, Baillie-PSW Primality Test, (LINK)

[pierwiastek1-5] Wikipedia, Pierwiastek kwadratowy, (Wiki-pl), (Wiki-en)

[IntegerSquareRoot1-6] Wikipedia, Integer square root, (Wiki-en)

[1]

[2]

[3]

[4]

[5]

[6]

Testy pierwszości. Liczby pseudopierwsze Lucasa i liczby silnie pseudopierwsze Lucasa. Test BPSW: Różnice pomiędzy wersjami

Aktualna wersja na dzień 18:40, 17 mar 2024

Spis treści

Ciągi Lucasa

Obliczanie wyrazów ciągu Lucasa modulo [math]\displaystyle{ m }[/math]

Podzielność wyrazów [math]\displaystyle{ U_n (P, Q) }[/math] przez liczbę pierwszą nieparzystą

Liczby pseudopierwsze Lucasa

Metoda Selfridge'a wyboru parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math]

Liczby silnie pseudopierwsze Lucasa

Test BPSW

Uzupełnienia

Pewne własności współczynników dwumianowych

Funkcje `digits(m, b)` oraz `issquare(m)`

Przypisy

Menu nawigacyjne

Szukaj

@@ Linia 7: / Linia 7: @@
 == Ciągi Lucasa ==
-<span style="font-size: 110%; font-weight: bold;">Definicja L1</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Definicja N1</span><br/>
 Niech <math>P, Q \in \mathbb{Z} \setminus \{0\}</math> oraz <math>D = P^2 - 4 Q \neq 0</math>. Ciągi Lucasa <math>U_n = U_n (P, Q)</math> i <math>V_n = V_n (P, Q)</math> definiujemy następująco
@@ Linia 24: / Linia 24: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L2</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N2</span><br/>
 Zauważmy, że:
@@ Linia 42: / Linia 42: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L3</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N3</span><br/>
 Oczywiście liczby <math>\alpha</math> i <math>\beta</math> są również pierwiastkami równania
@@ Linia 63: / Linia 63: @@
-<span style="font-size: 110%; font-weight: bold;">Definicja L4</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Definicja N4</span><br/>
 Niech <math>P, Q \in \mathbb{Z} \setminus \{0\}</math> oraz <math>D = P^2 - 4 Q \neq 0</math>. Ciągi Lucasa <math>(U_n)</math> i <math>(V_n)</math> określone są następującymi wzorami rekurencyjnymi
@@ Linia 72: / Linia 72: @@
-<span style="font-size: 110%; font-weight: bold;">Przykład L5</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Przykład N5</span><br/>
 Początkowe wyrazy ciągów Lucasa
@@ Linia 102: / Linia 102: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L6</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N6</span><br/>
 W PARI/GP możemy napisać prosty kod, który pozwoli obliczyć wartości wyrazów <math>U_n (P, Q)</math> i <math>V_n (P, Q)</math>
@@ Linia 111: / Linia 111: @@
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L7</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N7</span><br/>
 Niech <math>D = P^2 - 4 Q</math>. Wyrazy ciągów Lucasa można przedstawić w&nbsp;postaci sumy
@@ Linia 161: / Linia 161: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L8</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N8</span><br/>
-Korzystając z&nbsp;twierdzenia L7, możemy napisać proste funkcje do znajdowania postaci kolejnych wyrazów <math>U_n (P, Q)</math> i <math>V_n (P, Q)</math>
+Korzystając z&nbsp;twierdzenia N7, możemy napisać proste funkcje do znajdowania postaci kolejnych wyrazów <math>U_n (P, Q)</math> i <math>V_n (P, Q)</math>
   <span style="font-size: 90%; color:black;">U(n) = 2^(1 - n)*'''sum'''(k=0, '''floor'''((n-1)/2), '''binomial'''(n, 2*k+1) * P^(n-2*k-1) * (P^2-4*Q)^k)</span>
@@ Linia 172: / Linia 172: @@
 Często możemy spotkać założenie <math>P \geqslant 1</math>. Poniższe twierdzenie wyjaśnia, dlaczego tak jest.
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L9</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N9</span><br/>
 Jeżeli <math>(U_n)</math> i <math>(V_n)</math> są ciągami Lucasa, to
@@ Linia 216: / Linia 216: @@
-<span style="font-size: 110%; font-weight: bold;">Zadanie L10</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Zadanie N10</span><br/>
 Pokazać, że jeżeli <math>P, Q \in \mathbb{Z} \setminus \{ 0 \}</math> i <math>D = P^2 - 4 Q \neq 0</math>, to
@@ Linia 262: / Linia 262: @@
-<span style="font-size: 110%; font-weight: bold;">Zadanie L11</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Zadanie N11</span><br/>
 Pokazać, że jeżeli <math>Q \in \mathbb{Z} \setminus \{ 0 \}</math> oraz <math>P = 4 Q - 1</math>, to
@@ Linia 326: / Linia 326: @@
-<span style="font-size: 110%; font-weight: bold;">Zadanie L12</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Zadanie N12</span><br/>
 Pokazać, że jeżeli <math>Q \in \mathbb{Z} \setminus \{ 0 \}</math> oraz <math>P = 4 Q + 1</math>, to
@@ Linia 390: / Linia 390: @@
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L13</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N13</span><br/>
 Dla wyrazów ciągów Lucasa prawdziwe są wzory
@@ Linia 443: / Linia 443: @@
 {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
-'''Wzory 1. - 7. najłatwiej udowodnić korzystając z&nbsp;definicji L1.'''
+'''Wzory 1. - 7. najłatwiej udowodnić korzystając z&nbsp;definicji N1.'''
 Wzór 1.
@@ Linia 565: / Linia 565: @@
 == Obliczanie wyrazów ciągu Lucasa modulo <math>m</math> ==
-<span style="font-size: 110%; font-weight: bold;">Przykład L14</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Przykład N14</span><br/>
-Pokażemy, jak wykorzystać podane w&nbsp;twierdzeniu L13 wzory 19, 20, 21 i 16
+Pokażemy, jak wykorzystać podane w&nbsp;twierdzeniu N13 wzory 19, 20, 21 i 16
 ::<math>U_{2 n} = 2 U_n U_{n + 1} - P U^2_n</math>
@@ Linia 632: / Linia 632: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L15</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N15</span><br/>
-Uogólniając postępowanie przedstawione w&nbsp;przykładzie L14, możemy napisać program w&nbsp;PARI/GP do szybkiego obliczania wyrazów ciągu Lucasa <math>U_n (P, Q)</math> i <math>V_n (P, Q)</math> modulo <math>m</math>.
+Uogólniając postępowanie przedstawione w&nbsp;przykładzie N14, możemy napisać program w&nbsp;PARI/GP do szybkiego obliczania wyrazów ciągu Lucasa <math>U_n (P, Q)</math> i <math>V_n (P, Q)</math> modulo <math>m</math>.
   <span style="font-size: 90%; color:black;">modLucas(n, P, Q, m) =
   {
-  '''local'''(A, i, s, U, U2, V, W, W2);
+  '''local'''(A, i, s, U,&#32;U2, V, W,&#32;W2);
   '''if'''( m == 1, '''return'''([0, 0]) );
   '''if'''( n == 0, '''return'''([0, 2 % m]) );
@@ Linia 661: / Linia 661: @@
 == Podzielność wyrazów <math>U_n (P, Q)</math> przez liczbę pierwszą nieparzystą ==
-<span style="font-size: 110%; font-weight: bold;">Uwaga L16</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N16</span><br/>
 Niech <math>p</math> będzie liczbą pierwszą nieparzystą. W&nbsp;przypadku, gdy <math>p \nmid P Q</math> nie możemy nic powiedzieć o&nbsp;podzielności wyrazów <math>U_n</math> przez <math>p</math>. Przykładowo, jeżeli <math>P \equiv 1 \pmod{p} \;</math> <math>\text{i} \;\; Q \equiv 1 \pmod{p}</math>, to modulo <math>p</math>, mamy
@@ Linia 674: / Linia 674: @@
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L17</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N17</span><br/>
 Niech <math>p</math> będzie liczbą pierwszą nieparzystą.
@@ Linia 726: / Linia 726: @@
 '''Punkt 5.'''
-Z twierdzenia L7 wiemy, że
+Z twierdzenia N7 wiemy, że
 ::<math>2^{n - 1} U_n = \sum_{k = 0}^{\lfloor (n - 1) / 2 \rfloor} \binom{n}{2 k + 1} P^{n - 2 k - 1} D^k</math>
@@ Linia 733: / Linia 733: @@
 \begin{cases}
 n P D^{(n - 2) / 2} & \text{gdy }n\text{ jest parzyste} \\
-D^{(n - 1) / 2} & \text{gdy }n\text{ jest nieparzyste}
+D^{(n - 1) / 2} & \text{gdy }n\text{ jest nieparzyste} \\
 \end{cases}</math>
@@ Linia 747: / Linia 747: @@
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L18</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N18</span><br/>
 Jeżeli <math>d</math> jest nieparzystym dzielnikiem <math>Q</math>, to dla <math>n \geqslant 2</math> jest
@@ Linia 772: / Linia 772: @@
 :::::<math>\quad \: = 2 \underset{j \; \text{nieparzyste}}{\sum_{j = 1}^{n}} \binom{n}{j} P^{n - j} \cdot \delta \cdot D^{(j - 1) / 2}</math>
-Rozpatrując powyższą równość modulo <math>Q</math> dostajemy (zobacz L43)
+Rozpatrując powyższą równość modulo <math>Q</math> dostajemy (zobacz N43)
 ::<math>2^{n - 1} \cdot {\small\frac{\alpha^n - \beta^n}{\delta}} = 2^{n - 1} U_n \equiv \underset{j \; \text{nieparzyste}}{\sum_{j = 1}^{n}} \binom{n}{j} P^{n - j} \cdot P^{j - 1}</math>
@@ Linia 784: / Linia 784: @@
 ::<math>2^{n - 1} (U_n - P^{n - 1}) \equiv 0 \pmod{Q}</math>
-Ponieważ <math>Q</math> dzieli <math>2^{n - 1} (U_n - P^{n - 1})</math>, to tym bardziej <math>d</math> dzieli <math>2^{n - 1} (U_n - P^{n - 1})</math>. Z założenia <math>\gcd (d, 2^{n - 1}) = 1</math>, zatem <math>d</math> dzieli <math>U_n - P^{n - 1}</math> (zobacz C72).
+Ponieważ <math>Q</math> dzieli <math>2^{n - 1} (U_n - P^{n - 1})</math>, to tym bardziej <math>d</math> dzieli <math>2^{n - 1} (U_n - P^{n - 1})</math>. Z założenia <math>\gcd (d, 2^{n - 1}) = 1</math>, zatem <math>d</math> dzieli <math>U_n - P^{n - 1}</math> (zobacz C74).
 W przypadku szczególnym, gdy <math>d = p</math>, gdzie <math>p</math> jest nieparzystą liczbą pierwszą i <math>p \nmid P</math>, z&nbsp;twierdzenia Fermata otrzymujemy natychmiast
@@ Linia 796: / Linia 796: @@
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L19</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N19</span><br/>
 Niech <math>D = P^2 - 4 Q</math>, a <math>(D \mid p)</math> oznacza symbol Legendre'a, gdzie <math>p</math> jest liczbą pierwszą nieparzystą i <math>p \nmid Q</math>. Mamy
@@ Linia 811: / Linia 811: @@
 '''Punkt 1.'''
-Zauważmy, że przypadek gdy <math>p \mid Q</math>, omówiliśmy w&nbsp;twierdzeniu poprzednim. Z&nbsp;założenia <math>p</math> jest liczbą pierwszą nieparzystą. Z&nbsp;twierdzenia L7, w&nbsp;przypadku nieparzystego <math>n = p</math>, otrzymujemy
+Zauważmy, że przypadek gdy <math>p \mid Q</math>, omówiliśmy w&nbsp;twierdzeniu poprzednim. Z&nbsp;założenia <math>p</math> jest liczbą pierwszą nieparzystą. Z&nbsp;twierdzenia N7, w&nbsp;przypadku nieparzystego <math>n = p</math>, otrzymujemy
 ::<math>2^{p - 1} U_p = p P^{p - 1} + \binom{p}{3} P^{p - 3} D + \binom{p}{5} P^{p - 5} D^2 + \ldots + \binom{p}{p-2} P^2 D^{(p - 3) / 2} + D^{(p - 1) / 2}</math>
-Ponieważ dla każdego <math>k \in [1, p - 1]</math> (zobacz L43)
+Ponieważ dla każdego <math>k \in [1, p - 1]</math> (zobacz N43)
 ::<math>\binom{p}{k} \equiv 0 \pmod{p}</math>
-to modulo <math>p</math> dostajemy (zobacz J28)
+to modulo <math>p</math> dostajemy (zobacz J33)
 ::<math>2^{p - 1} U_p \equiv U_p \equiv D^{(p - 1) / 2} \equiv (D \mid p) \pmod{p}</math>
@@ Linia 835: / Linia 835: @@
 i nie może być <math>(D \mid p) = - 1</math>.
-Dla parzystego <math>n = p + 1</math> otrzymujemy z&nbsp;twierdzenia L7
+Dla parzystego <math>n = p + 1</math> otrzymujemy z&nbsp;twierdzenia N7
 ::<math>2^p U_{p + 1} = (p + 1) P^p + \binom{p + 1}{3} P^{p - 2} D + \binom{p + 1}{5} P^{p - 4} D^2 + \ldots + \binom{p + 1}{p - 2} P^3 D^{(p - 3) / 2} + (p + 1) P D^{(p - 1) / 2}</math>
-Ponieważ dla <math>k \in [2, p - 1]</math> (zobacz L44)
+Ponieważ dla <math>k \in [2, p - 1]</math> (zobacz N44)
 ::<math>\binom{p + 1}{k} \equiv 0 \pmod{p}</math>
@@ Linia 848: / Linia 848: @@
-Z założenia <math>D</math> jest liczbą niekwadratową modulo <math>p</math>, zatem <math>D^{(p - 1) / 2} \equiv - 1 \pmod{p}</math> (zobacz J25). Skąd wynika natychmiast, że
+Z założenia <math>D</math> jest liczbą niekwadratową modulo <math>p</math>, zatem <math>D^{(p - 1) / 2} \equiv - 1 \pmod{p}</math> (zobacz J31). Skąd wynika natychmiast, że
 ::<math>2 U_{p + 1} \equiv 0 \pmod{p}</math>
@@ Linia 856: / Linia 856: @@
 '''Punkt 3.'''
-Dla parzystego <math>n = p - 1</math> otrzymujemy z&nbsp;twierdzenia L7
+Dla parzystego <math>n = p - 1</math> otrzymujemy z&nbsp;twierdzenia N7
 ::<math>2^{p - 2} U_{p - 1} = (p - 1) P^{p - 2} + \binom{p - 1}{3} P^{p - 4} D + \binom{p - 1}{5} P^{p - 6} D^2 + \ldots + \binom{p - 1}{p - 4} P^3 D^{(p - 5) / 2} + (p - 1) P D^{(p - 3) / 2}</math>
-Ponieważ dla <math>k \in [0, p - 1]</math> (zobacz L45)
+Ponieważ dla <math>k \in [0, p - 1]</math> (zobacz N45)
 ::<math>\binom{p - 1}{k} \equiv (- 1)^k \pmod{p}</math>
@@ Linia 871: / Linia 871: @@
-Z założenia <math>D</math> jest liczbą kwadratową modulo <math>p</math> (zobacz J23), zatem istnieje taka liczba <math>R</math>, że
+Z założenia <math>D</math> jest liczbą kwadratową modulo <math>p</math> (zobacz J29), zatem istnieje taka liczba <math>R</math>, że
 ::<math>D \equiv R^2 \pmod{p}</math>
@@ Linia 904: / Linia 904: @@
-Aby zapisać punkty 2. i 3. twierdzenia L19 (i tylko te punkty) w&nbsp;zwartej formie, musimy założyć, że <math>\gcd (p, D) = 1</math>. Otrzymujemy<br/>
+Aby zapisać punkty 2. i 3. twierdzenia N19 (i tylko te punkty) w&nbsp;zwartej formie, musimy założyć, że <math>\gcd (p, D) = 1</math>. Otrzymujemy<br/>
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L20</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N20</span><br/>
 Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą i <math>\gcd (p, Q D) = 1</math>, to
@@ Linia 916: / Linia 916: @@
 == Liczby pseudopierwsze Lucasa ==
-<span style="font-size: 110%; font-weight: bold;">Uwaga L21</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N21</span><br/>
-Z twierdzenia L20 wiemy, że liczby pierwsze nieparzyste <math>p</math> takie, że <math>p \nmid Q D</math> są dzielnikami wyrazów ciągu Lucasa <math>U_{p - (D \mid p)}</math>, gdzie <math>(D \mid p)</math> oznacza symbol Legendre'a. Jeśli zastąpimy symbol Legendre'a symbolem Jacobiego, to będziemy mogli badać prawdziwość tego twierdzenia dla liczb złożonych i&nbsp;łatwo przekonamy się, że dla pewnych liczb złożonych <math>m</math> kongruencja
+Z twierdzenia N20 wiemy, że liczby pierwsze nieparzyste <math>p</math> takie, że <math>p \nmid Q D</math> są dzielnikami wyrazów ciągu Lucasa <math>U_{p - (D \mid p)}</math>, gdzie <math>(D \mid p)</math> oznacza symbol Legendre'a. Jeśli zastąpimy symbol Legendre'a symbolem Jacobiego, to będziemy mogli badać prawdziwość tego twierdzenia dla liczb złożonych i&nbsp;łatwo przekonamy się, że dla pewnych liczb złożonych <math>m</math> kongruencja
 ::<math>U_{m - (D \mid m)} \equiv 0 \pmod{m}</math>
@@ Linia 925: / Linia 925: @@
-<span style="font-size: 110%; font-weight: bold;">Definicja L22</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Definicja N22</span><br/>
 Powiemy, że liczba złożona nieparzysta <math>m</math> jest liczbą pseudopierwszą Lucasa dla parametrów <math>P</math> i <math>Q</math> (symbolicznie: LPSP( <math>P, Q</math> )), jeżeli <math>\gcd (m, Q D) = 1</math> i
@@ Linia 934: / Linia 934: @@
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L23</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N23</span><br/>
 Jeżeli liczba złożona nieparzysta <math>m</math> jest liczbą pseudopierwszą Lucasa dla parametrów <math>P = a + 1</math> i <math>Q = a</math>, gdzie <math>a \geqslant 2</math>, to jest liczbą pseudopierwszą Fermata przy podstawie <math>a</math>.
@@ Linia 962: / Linia 962: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L24</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N24</span><br/>
-Wykorzystując funkcje <code>jacobi(a, n)</code> i <code>modLucas(n, P, Q, m)</code> (zobacz J48, L15) możemy napisać prosty program, który sprawdza, czy dla liczby nieparzystej <math>m</math> prawdziwe jest twierdzenie L20.
+Wykorzystując funkcje <code>jacobi(a, n)</code> i <code>modLucas(n, P, Q, m)</code> (zobacz J48, N15) możemy napisać prosty program, który sprawdza, czy dla liczby nieparzystej <math>m</math> prawdziwe jest twierdzenie N20.
   <span style="font-size: 90%; color:black;">isPrimeOr<span style="background-color: #fee481;">LPSP</span>(m, P, Q) =
@@ Linia 976: / Linia 976: @@
-<span style="font-size: 110%; font-weight: bold;">Przykład L25</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Przykład N25</span><br/>
 Poniższa tabela zawiera najmniejsze liczby pseudopierwsze Lucasa dla różnych parametrów <math>P</math> i <math>Q</math>
@@ Linia 1047: / Linia 1047: @@
-<span style="font-size: 110%; font-weight: bold;">Przykład L26</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Przykład N26</span><br/>
 Ilość liczb LPSP(<math>P, Q</math>) mniejszych od <math>10^9</math>
@@ Linia 1112: / Linia 1112: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L27</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N27</span><br/>
 Dla <math>(P, Q) = (1, 1)</math> ciąg Lucasa <math>(U_n)</math> ma postać
 ::<math>(U_n) = (0, 1, 1, 0, - 1, - 1, 0, 1, 1, 0, - 1, - 1, 0, 1, 1, 0, - 1, - 1, 0, 1, 1, \ldots)</math>
-Stosując indukcję matematyczną, udowodnimy, że <math>U_{3 k} = 0</math>. Łatwo sprawdzamy, że dla <math>k = 0</math> i <math>k = 1</math> wzór jest prawdziwy. Zakładając prawdziwość wzoru dla wszystkich liczb naturalnych nie większych od <math>k</math>, otrzymujemy dla <math>k + 1</math> (zobacz L13 p.3)
+Stosując indukcję matematyczną, udowodnimy, że <math>U_{3 k} = 0</math>. Łatwo sprawdzamy, że dla <math>k = 0</math> i <math>k = 1</math> wzór jest prawdziwy. Zakładając prawdziwość wzoru dla wszystkich liczb naturalnych nie większych od <math>k</math>, otrzymujemy dla <math>k + 1</math> (zobacz N13 p.3)
 ::<math>U_{3 (k + 1)} = U_{3 k + 3} = U_{3 k} V_3 - U_{3 (k - 1)} = 0</math>
@@ Linia 1131: / Linia 1131: @@
   \;\;\: 1 & \text{gdy } m = 6 k + 1 \\
   \;\;\: 0 & \text{gdy } m = 6 k + 3 \\
-       - 1 & \text{gdy } m = 6 k + 5
+       - 1 & \text{gdy } m = 6 k + 5 \\
 \end{cases}</math>
@@ Linia 1148: / Linia 1148: @@
 Czyli liczbami pseudopierwszymi Lucasa dla parametrów <math>(P, Q) = (1, 1)</math> będą liczby nieparzyste <math>m</math>, które nie są podzielne przez <math>3</math> i&nbsp;nie są liczbami pierwszymi. Ilość takich liczb nie większych od <math>10^k</math> możemy łatwo znaleźć poleceniem
-  '''for'''(k = 1, 9, s = 0; '''forstep'''(m = 3, 10^k, 2, '''if'''( m%6 <> 3, s = s + !'''isprime'''(m) )); '''print'''(s))
+  <span style="font-size: 90%; color:black;">'''for'''(k = 1, 9, s = 0; '''forstep'''(m = 3, 10^k, 2, '''if'''( m%6 <> 3, s = s + !'''isprime'''(m) )); '''print'''(s))</span>
-<span style="font-size: 110%; font-weight: bold;">Zadanie L28</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Zadanie N28</span><br/>
 Pokazać, że ilość liczb pseudopierwszych Lucasa dla parametrów <math>(P, Q) = (2, 2)</math> nie większych od <math>10^k</math> możemy znaleźć poleceniem
-  '''for'''(k = 1, 9, s = 0; '''forstep'''(m = 3, 10^k, 2, s = s + !'''isprime'''(m)); '''print'''(s))
+  <span style="font-size: 90%; color:black;">'''for'''(k = 1, 9, s = 0; '''forstep'''(m = 3, 10^k, 2, s = s + !'''isprime'''(m)); '''print'''(s))</span>
@@ Linia 1163: / Linia 1163: @@
 == Metoda Selfridge'a wyboru parametrów <math>P</math> i <math>Q</math> ==
-<span style="font-size: 110%; font-weight: bold;">Uwaga L29</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N29</span><br/>
-Twierdzenie L20 możemy wykorzystać do testowania pierwszości liczb. Ponieważ musi być spełniony warunek <math>\gcd (m, Q D) = 1</math>, to nie każda para liczb <math>P, Q</math> (np. wybrana losowo) nadaje się do przeprowadzenia testu. Zawsze będziemy zmuszeni określić zasadę postępowania, która doprowadzi do wyboru właściwej pary <math>P, Q</math>.
+Twierdzenie N20 możemy wykorzystać do testowania pierwszości liczb. Ponieważ musi być spełniony warunek <math>\gcd (m, Q D) = 1</math>, to nie każda para liczb <math>P, Q</math> (np. wybrana losowo) nadaje się do przeprowadzenia testu. Zawsze będziemy zmuszeni określić zasadę postępowania, która doprowadzi do wyboru właściwej pary <math>P, Q</math>.
 Robert Baillie i&nbsp;Samuel Wagstaff przedstawili<ref name="BaillieWagstaff1"/> dwie metody wyboru parametrów dla testu Lucasa. Ograniczymy się do omówienia tylko pierwszej z&nbsp;nich (metodę zaproponował John Selfridge).
@@ Linia 1186: / Linia 1186: @@
 Zauważmy, że
 :* jeżeli liczba nieparzysta <math>m</math> jest liczbą kwadratową, to wybór <math>D</math> nie będzie możliwy
-:* w&nbsp;przypadku zastosowania tej metody znajdziemy tylko liczby pierwsze lub pseudopierwsze Lucasa, które spełniają kongruencję <math>U_{m + 1} \equiv 0 \pmod{m}</math>, czyli tylko część liczb pseudopierwszych Lucasa określonych w&nbsp;definicji L22
+:* w&nbsp;przypadku zastosowania tej metody znajdziemy tylko liczby pierwsze lub pseudopierwsze Lucasa, które spełniają kongruencję <math>U_{m + 1} \equiv 0 \pmod{m}</math>, czyli tylko część liczb pseudopierwszych Lucasa określonych w&nbsp;definicji N22
@@ Linia 1193: / Linia 1193: @@
 ::<math> a_{k+1} =
    \begin{cases}
-   \qquad \qquad 5 & \text{gdy } k = 1\\
+   \qquad \qquad 5 & \text{gdy } k = 1 \\
-       - a_k - 2 * \mathop{\textnormal{sign}}( a_k ) & \text{gdy } k \geqslant 2
+       - a_k - 2 * \mathop{\textnormal{sign}}( a_k ) & \text{gdy } k \geqslant 2 \\
    \end{cases}</math>
@@ Linia 1232: / Linia 1232: @@
-Uważny Czytelnik dostrzeże, że nie zbadaliśmy, czy spełniony jest warunek <math>\gcd (m, Q) = 1</math>. Nie musimy tego robić, bo zwracana przez funkcję <code>MethodA()</code> liczba <math>Q</math> jest względnie pierwsza z <math>m</math>. Omówimy ten problem dokładnie w&nbsp;zadaniu L30. Poniżej pokażemy, że nawet gdyby było <math>\gcd (m, Q) > 1</math>, to złożona liczba <math>m</math> nie zostanie uznana za liczbę pseudopierwszą Lucasa.
+Uważny Czytelnik dostrzeże, że nie zbadaliśmy, czy spełniony jest warunek <math>\gcd (m, Q) = 1</math>. Nie musimy tego robić, bo zwracana przez funkcję <code>MethodA()</code> liczba <math>Q</math> jest względnie pierwsza z <math>m</math>. Omówimy ten problem dokładnie w&nbsp;zadaniu N30. Poniżej pokażemy, że nawet gdyby było <math>\gcd (m, Q) > 1</math>, to złożona liczba <math>m</math> nie zostanie uznana za liczbę pseudopierwszą Lucasa.
-Zauważmy, że jeżeli <math>m</math> jest liczbą złożoną i&nbsp;ma dzielnik pierwszy <math>p < m</math>, który dzieli <math>Q</math>, to <math>p \mid Q</math> i <math>p \nmid P</math> (bo <math>P = 1</math>), zatem <math>p \nmid U_k</math> dla <math>k \geqslant 1</math> (zobacz L17), czyli nie może być
+Zauważmy, że jeżeli <math>m</math> jest liczbą złożoną i&nbsp;ma dzielnik pierwszy <math>p < m</math>, który dzieli <math>Q</math>, to <math>p \mid Q</math> i <math>p \nmid P</math> (bo <math>P = 1</math>), zatem <math>p \nmid U_k</math> dla <math>k \geqslant 1</math> (zobacz N17), czyli nie może być
 ::<math>U_{m + 1} (1, Q) \equiv 0 \pmod{m}</math>
@@ Linia 1242: / Linia 1242: @@
 ::<math>U_{m + 1} (1, Q) \equiv 0 \pmod{p}</math>
-a to jest niemożliwe. Zatem program wykorzystujący twierdzenie L20 wykryje złożoność liczby <math>m</math>.
+a to jest niemożliwe. Zatem program wykorzystujący twierdzenie N20 wykryje złożoność liczby <math>m</math>.
 Łatwo pokażemy, że nie jest możliwe, aby liczba <math>m</math> była liczbą pierwszą i&nbsp;była dzielnikiem <math>Q</math>. Jeżeli <math>m</math> jest liczbą pierwszą, to istnieje dokładnie <math>\tfrac{m - 1}{2}</math> liczb kwadratowych modulo <math>p</math> i <math>\tfrac{m - 1}{2}</math> liczb niekwadratowych modulo <math>p</math>, zatem rozpoczynając od wyrazu <math>a_2</math> możemy dojść co najwyżej do wyrazu o&nbsp;indeksie <math>k = \tfrac{m - 1}{2} + 2</math>, czyli
@@ Linia 1256: / Linia 1256: @@
-<span style="font-size: 110%; font-weight: bold;">Zadanie L30</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Zadanie N30</span><br/>
 Pokazać, że w&nbsp;przypadku, gdy dla kolejnych liczb <math>a_k = (- 1)^k (2 k + 1)</math> sprawdzamy, czy konsekwencją <math>(a_k \mid m) = 0</math> jest złożoność liczby <math>m</math>, to dla każdej liczby <math>Q</math> wyznaczonej metodą Selfridge'a jest <math>\gcd (Q, m) = 1</math>.
@@ Linia 1371: / Linia 1371: @@
-<span style="font-size: 110%; font-weight: bold;">Zadanie L31</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Zadanie N31</span><br/>
 Zmodyfikujmy metodę Selfridge'a w&nbsp;taki sposób, że będziemy rozpoczynali próby nie od wyrazu <math>a_2 = 5</math>, ale od wyrazu <math>a_3 = - 7</math>. Pokazać, że w&nbsp;przypadku, gdy dla kolejnych liczb <math>a_k = (- 1)^k (2 k + 1)</math> sprawdzamy, czy konsekwencją <math>(a_k \mid m) = 0</math> jest złożoność liczby <math>m</math>, to dla każdej liczby <math>Q</math> wyznaczonej tak zmodyfikowaną metodą Selfridge'a jest <math>\gcd (Q, m) = 1</math>.
@@ Linia 1490: / Linia 1490: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L32</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N32</span><br/>
 Przyjmując metodę Selfridge'a wyboru parametrów <math>P, Q</math> dla testu Lucasa, możemy łatwo napisać odpowiedni program w&nbsp;PARI/GP testujący pierwszość liczb
@@ Linia 1507: / Linia 1507: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L33</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N33</span><br/>
 Najmniejsze liczby pseudopierwsze Lucasa, które pojawiają się przy zastosowaniu metody Selfridge'a wyboru parametrów <math>P</math> i <math>Q</math>, to
@@ Linia 1538: / Linia 1538: @@
 == Liczby silnie pseudopierwsze Lucasa ==
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L34</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N34</span><br/>
 Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą taką, że <math>\gcd (p, Q D) = 1</math> oraz <math>p - (D \mid p) = 2^r w</math>, gdzie <math>w</math> jest liczbą nieparzystą, to spełniony jest dokładnie jeden z&nbsp;warunków
@@ Linia 1548: / Linia 1548: @@
 {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
-Wiemy (zobacz L20), że jeżeli <math>p</math> jest liczbą pierwszą nieparzystą taką, że <math>\gcd (p, Q D) = 1</math>, to <math>p \mid U_{p - (D \mid p)}</math>. Z&nbsp;założenia jest <math>p - (D \mid p) = 2^r w</math>, zatem <math>p \mid U_{2^r w}</math>. Ponieważ założyliśmy, że <math>p \nmid Q</math> i <math>p \nmid D</math>, to ze wzoru <math>V^2_n - D U^2_n = 4 Q^n</math> (zobacz L13 p.14) wynika natychmiast, że <math>p</math> nie może dzielić jednocześnie liczb <math>U_n</math> i <math>V_n</math>.
+Wiemy (zobacz N20), że jeżeli <math>p</math> jest liczbą pierwszą nieparzystą taką, że <math>\gcd (p, Q D) = 1</math>, to <math>p \mid U_{p - (D \mid p)}</math>. Z&nbsp;założenia jest <math>p - (D \mid p) = 2^r w</math>, zatem <math>p \mid U_{2^r w}</math>. Ponieważ założyliśmy, że <math>p \nmid Q</math> i <math>p \nmid D</math>, to ze wzoru <math>V^2_n - D U^2_n = 4 Q^n</math> (zobacz N13 p.14) wynika natychmiast, że <math>p</math> nie może dzielić jednocześnie liczb <math>U_n</math> i <math>V_n</math>.
-Korzystając ze wzoru <math>U_{2 n} = U_n V_n</math> (zobacz L13 p.11), otrzymujemy
+Korzystając ze wzoru <math>U_{2 n} = U_n V_n</math> (zobacz N13 p.11), otrzymujemy
 ::{| border="0"
@@ Linia 1599: / Linia 1599: @@
 Konsekwentnie definiujemy liczby pseudopierwsze<br/>
-<span style="font-size: 110%; font-weight: bold;">Definicja L35</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Definicja N35</span><br/>
 Powiemy, że liczba złożona nieparzysta <math>m</math> jest liczbą silnie pseudopierwszą Lucasa (SLPSP) dla parametrów <math>P</math> i <math>Q</math>, jeżeli <math>\gcd (m, Q D) = 1</math> oraz <math>m - (D \mid m) = 2^r w</math>, gdzie <math>w</math> jest liczbą nieparzystą i&nbsp;spełniony jest jeden z&nbsp;warunków
@@ Linia 1610: / Linia 1610: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L36</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N36</span><br/>
-Każda liczba SLPSP(<math>P, Q</math>) jest LPSP(<math>P, Q</math>). Korzystając ze zdefiniowanych wcześniej funkcji: <code>modPower(a, n, m)</code>, <code>jacobi(a, n)</code> i <code>modLucas(n, P, Q, m)</code> (zobacz K2, J48, L15), możemy napisać prosty program, który sprawdza, czy liczba <math>m</math> spełnia jeden z&nbsp;warunków podanych w&nbsp;twierdzeniu L34.
+Każda liczba SLPSP(<math>P, Q</math>) jest LPSP(<math>P, Q</math>). Korzystając ze zdefiniowanych wcześniej funkcji: <code>modPower(a, n, m)</code>, <code>jacobi(a, n)</code> i <code>modLucas(n, P, Q, m)</code> (zobacz M2, J48, N15), możemy napisać prosty program, który sprawdza, czy liczba <math>m</math> spełnia jeden z&nbsp;warunków podanych w&nbsp;twierdzeniu N34.
   <span style="font-size: 90%; color: black;">isPrimeOr<span style="background-color: #fee481;">SLPSP</span>(m, P, Q) =
@@ Linia 1639: / Linia 1639: @@
-<span style="font-size: 110%; font-weight: bold;">Przykład L37</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Przykład N37</span><br/>
 Poniższa tabela zawiera najmniejsze liczby silnie pseudopierwsze Lucasa dla różnych parametrów <math>P</math> i <math>Q</math>
@@ Linia 1710: / Linia 1710: @@
-<span style="font-size: 110%; font-weight: bold;">Przykład L38</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Przykład N38</span><br/>
 Ilość liczb SLPSP(<math>P, Q</math>) mniejszych od <math>10^9</math>
@@ Linia 1777: / Linia 1777: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L39</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N39</span><br/>
 Można pokazać<ref name="Arnault1"/>, że dla liczby złożonej nieparzystej <math>m \neq 9</math> i&nbsp;ustalonego <math>D</math> ilość par <math>P, Q</math> takich, że
@@ Linia 1791: / Linia 1791: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L40</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N40</span><br/>
-Podobnie jak w&nbsp;przypadku liczb pseudopierwszych Lucasa LPSP(<math>P, Q</math>) tak i&nbsp;w&nbsp;przypadku liczb silnie pseudopierwszych Lucasa SLPSP(<math>P, Q</math>) możemy testować pierwszość liczby <math>m</math>, wybierając liczby <math>P, Q</math> losowo lub zastosować wybraną metodę postępowania. Przedstawiony poniżej program, to zmodyfikowany kod z uwagi L36. Teraz parametry <math>P, Q</math> są wybierane metodą Selfridge'a, a symbol Jacobiego <math>(D \mid m)</math> jest równy <math>- 1</math>.
+Podobnie jak w&nbsp;przypadku liczb pseudopierwszych Lucasa LPSP(<math>P, Q</math>) tak i&nbsp;w&nbsp;przypadku liczb silnie pseudopierwszych Lucasa SLPSP(<math>P, Q</math>) możemy testować pierwszość liczby <math>m</math>, wybierając liczby <math>P, Q</math> losowo lub zastosować wybraną metodę postępowania. Przedstawiony poniżej program, to zmodyfikowany kod z uwagi N36. Teraz parametry <math>P, Q</math> są wybierane metodą Selfridge'a, a symbol Jacobiego <math>(D \mid m)</math> jest równy <math>- 1</math>.
   <span style="font-size: 90%; color:black;">StrongLucasTest(m) =
@@ Linia 1823: / Linia 1823: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L41</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N41</span><br/>
 Najmniejsze liczby silnie pseudopierwsze Lucasa, które otrzymujemy po zastosowaniu metody Selfridge'a wyboru parametrów <math>P</math> i <math>Q</math>, to
@@ Linia 1853: / Linia 1853: @@
 == Test BPSW ==
-<span style="font-size: 110%; font-weight: bold;">Uwaga L42</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N42</span><br/>
-Jest <math>488</math> liczb SPSP(<math>2</math>) mniejszych od <math>10^8</math> i są 582 liczby SPSP(<math>3</math>) mniejsze od <math>10^8</math> (zobacz K20). Ale jest aż <math>21</math> liczb mniejszych od <math>10^8</math> silnie pseudopierwszych jednocześnie względem podstaw <math>2</math> i <math>3</math>:
+Jest <math>488</math> liczb SPSP(<math>2</math>) mniejszych od <math>10^8</math> i są 582 liczby SPSP(<math>3</math>) mniejsze od <math>10^8</math> (zobacz M21). Ale jest aż <math>21</math> liczb mniejszych od <math>10^8</math> silnie pseudopierwszych jednocześnie względem podstaw <math>2</math> i <math>3</math>:
 <math>1373653, 1530787, 1987021, 2284453, 3116107, 5173601, 6787327, 11541307, 13694761, 15978007, 16070429,</math>
@@ Linia 1865: / Linia 1865: @@
 {{\Spoiler}}
-Widzimy, że prawdopodobieństwo błędnego rozpoznania pierwszości w&nbsp;przypadku liczb mniejszych od <math>10^8</math> dla podstaw <math>2</math> i <math>3</math> jest rzędu kilku milionowych. Gdyby prawdopodobieństwa błędnego rozpoznania pierwszości w&nbsp;przypadku podstaw <math>2</math> i <math>3</math> były niezależne, to spodziewalibyśmy się, że nie będzie wcale liczb mniejszych od <math>10^8</math> silnie pseudopierwszych jednocześnie względem podstaw <math>2</math> i <math>3</math>, bo prawdopodobieństwo takiego zdarzenia byłoby równe kilkudziesięciu bilonowym. Ale tak nie jest.
+Widzimy, że prawdopodobieństwo błędnego rozpoznania pierwszości w&nbsp;przypadku liczb mniejszych od <math>10^8</math> dla podstawy <math>2</math> lub podstawy <math>3</math> jest rzędu kilku milionowych. Gdyby prawdopodobieństwa błędnego rozpoznania pierwszości w&nbsp;przypadku podstawy <math>2</math> lub podstawy <math>3</math> były niezależne, to spodziewalibyśmy się, że nie będzie wcale liczb mniejszych od <math>10^8</math> silnie pseudopierwszych jednocześnie względem podstaw <math>2</math> i <math>3</math>, bo prawdopodobieństwo takiego zdarzenia byłoby równe kilkudziesięciu bilonowym. Ale tak nie jest.
 Jest to mocny argument za tym, że zastosowanie różnych (niezależnych) testów może być znacznie silniejszym narzędziem do testowania pierwszości liczb, niż wielokrotne stosowanie tego samego testu, gdzie poszczególne próby są tylko pozornie niezależne.
@@ Linia 1889: / Linia 1889: @@
 Test w&nbsp;dokładnie takiej postaci zaproponowali Robert Baillie i&nbsp;Samuel Wagstaff<ref name="BaillieWagstaff1"/>. Nazwa testu to akronim, utworzony od pierwszych liter nazwisk Roberta Bailliego, Carla Pomerance'a, Johna Selfridge'a i&nbsp;Samuela Wagstaffa.
-Nie jest znany żaden przykład liczby złożonej <math>m</math>, którą test BPSW<ref name="BPSW1"/><ref name="BPSW2"/> identyfikowałby jako pierwszą i&nbsp;z&nbsp;pewnością nie ma takich liczb dla <math>m < 2^{64} \approx 1.844 \cdot 10^{19}</math>. Warto przypomnieć: potrzebowaliśmy siedmiu testów Millera-Rabina (dla podstaw <math>2, 3, 5, 7, 11, 13, 17</math>), aby mieć pewność, że dowolna liczba <math>m < 3.41 \cdot 10^{14}</math> jest pierwsza (zobacz K21).
+Nie jest znany żaden przykład liczby złożonej <math>m</math>, którą test BPSW<ref name="BPSW1"/><ref name="BPSW2"/> identyfikowałby jako pierwszą i&nbsp;z&nbsp;pewnością nie ma takich liczb dla <math>m < 2^{64} \approx 1.844 \cdot 10^{19}</math>. Warto przypomnieć: potrzebowaliśmy siedmiu testów Millera-Rabina (dla podstaw <math>2, 3, 5, 7, 11, 13, 17</math>), aby mieć pewność, że dowolna liczba <math>m < 3.41 \cdot 10^{14}</math> jest pierwsza (zobacz M22).
@@ Linia 1903: / Linia 1903: @@
 &nbsp;
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L43</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N43</span><br/>
 Jeżeli <math>p</math> jest liczbą pierwszą, to
@@ Linia 1921: / Linia 1921: @@
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L44</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N44</span><br/>
 Jeżeli <math>p</math> jest liczbą pierwszą nieparzystą, to
@@ Linia 1939: / Linia 1939: @@
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L45</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N45</span><br/>
 Jeżeli <math>p</math> jest liczbą pierwszą, to
@@ Linia 1959: / Linia 1959: @@
 ::<math>\binom{p - 1}{k} \equiv (- 1)^1 \binom{p - 1}{k - 1} \equiv (- 1)^2 \binom{p - 1}{k - 2} \equiv \ldots \equiv (- 1)^{k - 2} \binom{p - 1}{2} \equiv (- 1)^{k - 1} \binom{p - 1}{1} \equiv (- 1)^k \pmod{p}</math>
-Co należało pokazać.<br/>
+Co należało pokazać. Zobacz też zadanie H22.<br/>
 &#9633;
 {{\Spoiler}}
@@ Linia 1965: / Linia 1965: @@
-<span style="font-size: 110%; font-weight: bold;">Twierdzenie L46</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Twierdzenie N46</span><br/>
 Dla współczynników dwumianowych prawdziwe są następujące wzory
@@ Linia 2007: / Linia 2007: @@
 &nbsp;
-<span style="font-size: 110%; font-weight: bold;">Uwaga L47</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N47</span><br/>
 W funkcji <code>modLucas()</code> wykorzystaliśmy zaimplementowaną w&nbsp;PARI/GP funkcję
@@ Linia 2032: / Linia 2032: @@
-<span style="font-size: 110%; font-weight: bold;">Uwaga L48</span><br/>
+<span style="font-size: 110%; font-weight: bold;">Uwaga N48</span><br/>
 W funkcjach <code>LucasTest()</code> i <code>StrongLucasTest()</code> wykorzystaliśmy zaimplementowaną w&nbsp;PARI/GP funkcję
@@ Linia 2042: / Linia 2042: @@
    \begin{cases}
    \qquad \;\; 1 & \text{gdy } k = 0 \\
-       \tfrac{1}{2} \left( a_k + \tfrac{x}{a_k} \right) & \text{gdy } k > 0
+       \tfrac{1}{2} \left( a_k + \tfrac{x}{a_k} \right) & \text{gdy } k > 0 \\
    \end{cases}</math>
@@ Linia 2052: / Linia 2052: @@
    \begin{cases}
    \qquad \quad \; 1 & \text{gdy } k = 0 \\
-       \left\lfloor \tfrac{1}{2} \left( a_k + \left\lfloor \tfrac{m}{a_k} \right\rfloor \right) \right\rfloor & \text{gdy } k > 0
+       \left\lfloor \tfrac{1}{2} \left( a_k + \left\lfloor \tfrac{m}{a_k} \right\rfloor \right) \right\rfloor & \text{gdy } k > 0 \\
    \end{cases}</math>

Testy pierwszości. Liczby pseudopierwsze Lucasa i liczby silnie pseudopierwsze Lucasa. Test BPSW: Różnice pomiędzy wersjami

Aktualna wersja na dzień 18:40, 17 mar 2024

Ciągi Lucasa

Obliczanie wyrazów ciągu Lucasa modulo [math]\displaystyle{ m }[/math]

Podzielność wyrazów [math]\displaystyle{ U_n (P, Q) }[/math] przez liczbę pierwszą nieparzystą

Liczby pseudopierwsze Lucasa

Metoda Selfridge'a wyboru parametrów [math]\displaystyle{ P }[/math] i [math]\displaystyle{ Q }[/math]

Liczby silnie pseudopierwsze Lucasa

Test BPSW

Uzupełnienia

Pewne własności współczynników dwumianowych

Funkcje digits(m, b) oraz issquare(m)

Przypisy

Menu nawigacyjne

Szukaj

Funkcje `digits(m, b)` oraz `issquare(m)`