0
$\begingroup$

Can you prove or disprove the claims given below?

Inspired by generalization of Lucas-Lehmer test I have formulated the following claims:

Claim 1 Let $M_p=2^p-1$ where $p$ is an odd prime number , let $S_k=3S_{k-1}-5S_{k-2}+3S_{k-3}$ with $S_0=0 , S_1=1 , S_2=2$ , then $$M_p \text{ is prime iff } \operatorname{GCD}\left(S_{(M_p+1)/2},M_p\right)=1 \text{ and } S_{M_p+1} \equiv 0 \pmod{M_p}$$

You can run this test here.

Claim 2 Let $F_n=2^{2^n}+1$ where $n>1$ , let $S_k=3S_{k-1}-5S_{k-2}+3S_{k-3}$ with $S_0=0 , S_1=1 , S_2=2$ , then $$F_n \text{ is prime iff } \operatorname{GCD}\left(S_{(F_n-1)/2},F_n\right)=1 \text{ and } S_{F_n-1} \equiv 0 \pmod{F_n}$$

You can run this test here.

Note that I verified these claims only for small values of $M_p$ and $F_n$ because computation of $\operatorname{GCD}$ takes a lot of time.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Notice that $\gcd(a,b) = \gcd(a\bmod b,b)$. That is, you can restrict computation of $S_k$ only to modulo $M_p$ (or $F_n$) and still compute the gcd. $\endgroup$
    – Max Alekseyev
    Commented Aug 18, 2020 at 12:16
  • $\begingroup$ @MaxAlekseyev Thanks! $\endgroup$
    – Pedja
    Commented Aug 19, 2020 at 2:10
  • $\begingroup$ In fact, the sequence $S_k$ satisfy a second-order recurrence: $$S_k = 2S_{k-1} - 3S_{k-2}.$$ $\endgroup$
    – Max Alekseyev
    Commented Aug 19, 2020 at 14:22

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .