Lucasian Pseudoprimality Hypothesis for Specific Class of k 2^n-1
 

Please delete this post if this generalization is already known .

[B]Definition[/B]

Let [TEX]P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)[/TEX] , where [TEX]m[/TEX] and[TEX] x[/TEX] are nonnegative integers .

[B]Corollary[/B]

Let [TEX]N=k\cdot 2^n-1[/TEX] such that [TEX]n>2[/TEX] , [TEX]k>0[/TEX] , [TEX]3 \mid k [/TEX], [TEX]k<2^n [/TEX]and

[TEX]\begin{cases}
k \equiv 1 \pmod{10} ~ \text{with }~ n \equiv 2,3 \pmod{4} \\
k \equiv 3 \pmod{10} ~ \text{with } ~ n \equiv 0,3 \pmod{4} \\
k \equiv 7 \pmod{10} ~ \text{with } ~ n \equiv 1,2 \pmod{4} \\
k \equiv 9 \pmod{10} ~\text{ with }~ n \equiv 0,1 \pmod{4}
\end{cases} [/TEX]

Let [TEX]S_i=P_2(S_{i-1}) [/TEX]with [TEX]S_0=P_k(18) [/TEX], thus

[TEX]N[/TEX] is prime iff [TEX]S_{n-2} \equiv 0 \pmod{N}[/TEX]

[QUOTE=primus;389597]Please delete this post if this generalization is already known .

[B]Definition[/B]

Let [TEX]P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)[/TEX] , where [TEX]m[/TEX] and[TEX] x[/TEX] are nonnegative integers .

[B]Corollary[/B]

Let [TEX]N=k\cdot 2^n-1[/TEX] such that [TEX]n>2[/TEX] , [TEX]k>0[/TEX] , [TEX]3 \mid k [/TEX], [TEX]k<2^n [/TEX]and

[TEX]\begin{cases}
k \equiv 1 \pmod{10} ~ \text{with }~ n \equiv 2,3 \pmod{4} \\
k \equiv 3 \pmod{10} ~ \text{with } ~ n \equiv 0,3 \pmod{4} \\
k \equiv 7 \pmod{10} ~ \text{with } ~ n \equiv 1,2 \pmod{4} \\
k \equiv 9 \pmod{10} ~\text{ with }~ n \equiv 0,1 \pmod{4}
\end{cases} [/TEX]

Let [TEX]S_i=P_2(S_{i-1}) [/TEX]with [TEX]S_0=P_k(18) [/TEX], thus

[TEX]N[/TEX] is prime iff [TEX]S_{n-2} \equiv 0 \pmod{N}[/TEX][/QUOTE]

What does the initializer 18 indicate (as opposed to the 4 in LLT) ?
IOW how does the initiator determine the algorithm, rather than the other way around?

[URL="http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer%E2%80%93Riesel_test#Finding_the_starting_value"]Finding the starting value .[/URL]

In deriving this algorithm, how was the initial value (18) determined?
How was 4 (or 10) determined to initiate LLT?

The correctness of the algorithm depends on the math proof that
uses or determines the correct initial value. How is the initial value
related to the moduli?

I'd be interested to know if and how this generalization can be further
generalized, say to numbers of the form k*a^m - 1,
with say k >= 1 and a >= 2 and m >= 2.

[QUOTE=davar55;390025]In deriving this algorithm, how was the initial value (18) determined?
[/QUOTE]

[TEX]P_3(x)=5778[/TEX]
Find [TEX]x[/TEX] ?

You can find more informations in [URL="http://en.wikipedia.org/wiki/Talk:Lucas%E2%80%93Lehmer%E2%80%93Riesel_test"]this article [/URL].

Where does 5778 come from as initiator?

How is the fact that 5778 = 76^2 + 2 relevant?

[QUOTE=davar55;390041]Where does 5778 come from as initiator?[/QUOTE]

Reference :

D. H. Lehmer, "An extended theory of Lucas' functions," Ann. of Math., v. 31, 1930, pp.419-448.

[QUOTE=primus;390210]Reference :

D. H. Lehmer, "An extended theory of Lucas' functions," Ann. of Math., v. 31, 1930, pp.419-448.[/QUOTE]

OK Thanks.

[QUOTE=davar55;390025]

I'd be interested to know if and how this generalization can be further
generalized, say to numbers of the form k*a^m - 1,
with say k >= 1 and a >= 2 and m >= 2.[/QUOTE]

Let [TEX]P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right) [/TEX], where [TEX]m [/TEX]and [TEX]x [/TEX]are nonnegative integers .

Let [TEX]N=k\cdot b^n-1[/TEX] such that [TEX]n>2[/TEX] , [TEX]k<b^n [/TEX]and

[TEX]\begin{cases}
k\equiv 3 \pmod{30}\text{~ with ~} b \equiv 2 \pmod{10}\text{~ and ~ }n \equiv 0,3 \pmod{4} \\
k\equiv 3 \pmod{30}\text{~ with ~} b \equiv 4 \pmod{10}\text{~ and ~ } n \equiv 0,2 \pmod{4} \\
k\equiv 3 \pmod{30}\text{~ with ~}b \equiv 6 \pmod{10}\text{~ and ~ }n \equiv 0,1,2,3 \pmod{4} \\
k\equiv 3 \pmod{30}\text{~ with ~}b \equiv 8 \pmod{10}\text{~ and ~ }n \equiv 0,1 \pmod{4}
\end{cases}[/TEX]

Let [TEX]S_i=P_b(S_{i-1})[/TEX] with [TEX]S_0=P_{bk/2}(P_{b/2}(18)) [/TEX], then

[TEX]N[/TEX] is prime iff [TEX]S_{n-2} \equiv 0 \pmod{N}[/TEX]

[QUOTE=primus;397999][TEX]...{~ and ~ }n \equiv 0,1,2,3 \pmod{4} [/TEX][/QUOTE]
A very important condition, that one.

[QUOTE=Batalov;398011]A very important condition, that one.[/QUOTE]

Really winnows the possibilities, don't it?