2
$\begingroup$

Can you provide a proof or a counterexample for the claim given below ?

Inspired by Theorem 4 in this paper I have formulated the following claim :

Let $P_n^{(a)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+a}\right)^n+\left(x+\sqrt{x^2+a}\right)^n\right)$ . Given an odd integer $ n$ ($ \geq 3 $) and integer $ a$ coprime to $ n$ , $ n$ is prime if and only if $ P_n^{(a)}(x) \equiv x^n \pmod{n} $ holds .

You can run this test here .

$\endgroup$
1
  • 1
    $\begingroup$ Apparently, you are looking for many primality tests. A motivation to prove or disprove them woule be to show that they would be efficient in practice. $\endgroup$ – Peter Mar 31 '18 at 11:04
1
+50
$\begingroup$

It holds true. The proof is much the same, with minor changes due to $$ P_n^{(a)}(x) = \frac{n}{2} \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k} \frac{a^k(2x)^{n-2k}}{n-k}.$$ For odd prime $n$, we see that the coefficient of $x^n$ is $2^{n-1}$, and others are divisible by $n$. For odd composite $n$, we take a prime $p$ dividing $n$ and show that $n$ doesn't divide the coefficient of $x^p$.

$\endgroup$
0
$\begingroup$

I fear this is not true.$$P_n^{(5)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+5}\right)^9+\left(x+\sqrt{x^2+5}\right)^9\right)$$One has $$P_n^{(5)}(4)=126336484=9(14037387)+1\\4^9=262144=9(29127)+1$$Therefore $$P_n^{(5)}(4)\equiv 4^9\pmod9\space\space\text{but $9$ is not prime. }$$

$\endgroup$
2
  • $\begingroup$ Put this code into WolframAlpha : a=5;n=9;SameQ[PolynomialMod[(1/2)*((x-Sqrt[x^2+a])^n+(x+Sqrt[x^2+a])^n),n],x^n] $\endgroup$ – Peđa Terzić Mar 31 '18 at 15:02
  • 3
    $\begingroup$ The question is about a polynomial identity, and not about specific values of 'x'. $\endgroup$ – metamorphy Apr 1 '18 at 21:43

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.