8
$\begingroup$

Can you provide a proof or counterexample for the following claim?

Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $N= 4kp^{n}+1 $ where $k$ is a positive natural number , $ 4k<2^n$ , $p$ is a prime number and $n\ge3$ . Let $a$ be a natural number greater than two such that $\left(\frac{a-2}{N}\right)=-1$ and $\left(\frac{a+2}{N}\right)=-1$ where $\left(\frac{}{}\right)$ denotes Jacobi symbol. Let $S_i=P_p(S_{i-1})$ with $S_0$ equal to the modular $P_{kp^2}(a)\phantom{5} \text{mod} \phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} \equiv 0 \pmod{N}$ .

You can run this test here.

I have verified this claim for $k \in [1,500]$ with $p \leq 97$ and $n \in [3,50]$ .

Further generalization of the claim

A

Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $N= 2kp^{n} + 1 $ where $k$ is a positive natural number , $ 2k<2^n$ , $p$ is a prime number and $n\ge3$ . Let $a$ be a natural number greater than two such that $\left(\frac{a-2}{N}\right)=-1$ and $\left(\frac{a+2}{N}\right)=-1$ where $\left(\frac{}{}\right)$ denotes Jacobi symbol. Let $S_i=P_p(S_{i-1})$ with $S_0$ equal to the modular $P_{kp^2}(a)\phantom{5} \text{mod} \phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} \equiv -2 \pmod{N}$ .

You can run this test here.

B

Let $P_m(x)=2^{-m}\cdot((x-\sqrt{x^2-4})^m+(x+\sqrt{x^2-4})^m)$ . Let $N= 2kp^{n} - 1 $ where $k$ is a positive natural number , $ 2k<2^n$ , $p$ is a prime number and $n\ge3$ . Let $a$ be a natural number greater than two such that $\left(\frac{a-2}{N}\right)=1$ and $\left(\frac{a+2}{N}\right)=-1$ where $\left(\frac{}{}\right)$ denotes Jacobi symbol. Let $S_i=P_p(S_{i-1})$ with $S_0$ equal to the modular $P_{kp^2}(a)\phantom{5} \text{mod} \phantom{5} N$. Then $N$ is prime if and only if $S_{n-2} \equiv -2 \pmod{N}$ .

You can run this test here.

$\endgroup$
7
$\begingroup$

The "if and only if" statement fails for $$[p,n,k,a] \in \{ [3, 4, 1, 100], [3, 4, 1, 225], [3, 6, 13, 2901] \}$$ and many others. In these cases, $N$ is not prime, but the congruence $S_{n-2}\equiv 0\pmod{N}$ still holds.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.