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

 2014-12-09, 11:00 #1 primus   Jul 2014 Montenegro 1A16 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

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

1A16 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

100110100010002 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

112×97 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 07:42.

Wed Jul 6 07:42:02 UTC 2022 up 83 days, 5:43, 0 users, load averages: 1.18, 1.13, 1.17

Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔