mersenneforum.org Lucasian Pseudoprimality Hypothesis for Specific Class of k 2^n-1
 Register FAQ Search Today's Posts Mark Forums Read

 2014-12-09, 11:00 #1 primus   Jul 2014 Montenegro 2·13 Posts Lucasian Pseudoprimality Hypothesis for Specific Class of k 2^n-1 Please delete this post if this generalization is already known . Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and$x$ are nonnegative integers . Corollary Let $N=k\cdot 2^n-1$ such that $n>2$ , $k>0$ , $3 \mid k$, $k<2^n$and $\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}$ Let $S_i=P_2(S_{i-1})$with $S_0=P_k(18)$, thus $N$ is prime iff $S_{n-2} \equiv 0 \pmod{N}$
2014-12-14, 11:22   #2
davar55

May 2004
New York City

108B16 Posts

Quote:
 Originally Posted by primus Please delete this post if this generalization is already known . Definition Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$ , where $m$ and$x$ are nonnegative integers . Corollary Let $N=k\cdot 2^n-1$ such that $n>2$ , $k>0$ , $3 \mid k$, $k<2^n$and $\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}$ Let $S_i=P_2(S_{i-1})$with $S_0=P_k(18)$, thus $N$ is prime iff $S_{n-2} \equiv 0 \pmod{N}$
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?

 2014-12-14, 14:24 #3 primus   Jul 2014 Montenegro 2×13 Posts
 2014-12-14, 15:53 #4 davar55     May 2004 New York City 5·7·112 Posts 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.
2014-12-14, 17:28   #5
primus

Jul 2014
Montenegro

2·13 Posts

Quote:
 Originally Posted by davar55 In deriving this algorithm, how was the initial value (18) determined?
$P_3(x)=5778$
Find $x$ ?

 2014-12-14, 19:02 #6 davar55     May 2004 New York City 108B16 Posts Where does 5778 come from as initiator? How is the fact that 5778 = 76^2 + 2 relevant?
2014-12-16, 08:54   #7
primus

Jul 2014
Montenegro

2·13 Posts

Quote:
 Originally Posted by davar55 Where does 5778 come from as initiator?
Reference :

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

2014-12-16, 16:11   #8
davar55

May 2004
New York City

5·7·112 Posts

Quote:
 Originally Posted by primus Reference : D. H. Lehmer, "An extended theory of Lucas' functions," Ann. of Math., v. 31, 1930, pp.419-448.
OK Thanks.

2015-03-18, 13:06   #9
primus

Jul 2014
Montenegro

2610 Posts

Quote:
 Originally Posted by davar55 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.
Let $P_m(x)=2^{-m}\cdot \left(\left(x-\sqrt{x^2-4}\right)^{m}+\left(x+\sqrt{x^2-4}\right)^{m}\right)$, where $m$and $x$are nonnegative integers .

Let $N=k\cdot b^n-1$ such that $n>2$ , $kand

$\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}$

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

$N$ is prime iff $S_{n-2} \equiv 0 \pmod{N}$

2015-03-18, 16:20   #10
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

960810 Posts

Quote:
 Originally Posted by primus $...{~ and ~ }n \equiv 0,1,2,3 \pmod{4}$
A very important condition, that one.

2015-03-18, 21:45   #11
ewmayer
2ω=0

Sep 2002
República de California

32·1,297 Posts

Quote:
 Originally Posted by Batalov A very important condition, that one.
Really winnows the possibilities, don't it?

 Similar Threads Thread Thread Starter Forum Replies Last Post primus Miscellaneous Math 1 2015-03-25 22:18 primus Miscellaneous Math 1 2014-10-12 09:25 primus Computer Science & Computational Number Theory 8 2014-08-21 15:16 primus Computer Science & Computational Number Theory 16 2014-08-15 01:15 princeps Math 4 2012-04-10 20:08

All times are UTC. The time now is 09:10.

Sun Nov 28 09:10:45 UTC 2021 up 128 days, 3:39, 0 users, load averages: 0.74, 0.92, 0.90