This is a generalization of this claim .

Can you provide a counterexample to the following claim?

Let $n$ be a natural number greater than two . Let $r$ be the smallest odd prime number such that $r \nmid n$ and $n^2 \not\equiv 1 \pmod r$ . 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)$ , where $a$ is an integer coprime to $n$ . Then $n$ is a prime number if and only if $P_n^{(a)}(x) \equiv x^n \pmod {x^r-1,n}$ .

You can run this test here.

I have tested this claim for many random values of $n$ and $a$ and there were no counterexamples .


Algorithm implementation in PARI/GP without directly computing $P_n^{(a)}(x)$.

  • $\begingroup$ The question above indicates $a$ is an integer coprime to $n$, whereas the Sage code uses $a=1$, so is $a=1$ sufficient? The question above indicates $n^2\not\equiv 1\,(mod\, r)$, whereas the Sage code uses "lift(Mod(n,r)^2)==1" as a condition for continuing the search for a suitable value of $r$. I'm not familary with Sage, but is the lift function really necessary? $\endgroup$ – Steven Clark Jun 23 at 15:22
  • $\begingroup$ @StevenClark You can use any other value of $a$ which is coprime to $n$ . I put $a=1$ because condition $\operatorname{gcd}(a,n)=1$ is always fulfilled for that value of $a$. In PARI/GP powermod is implemented via lift function, i.e. powermod(n,2,r)=lift(Mod(n,r)^2) . $\endgroup$ – Peđa Terzić Jun 23 at 16:23

The claim is true.

It is true that if $n$ is a prime number, then $P_n^{(a)}(x)\equiv x^n\pmod{x^r-1,n}$.

Proof :

We have, by the binomial theorem, $$\begin{align}P_n^{(a)}(x)&=\frac 12\left(\left(x-\sqrt{x^2+a}\right)^n+\left(x+\sqrt{x^2+a}\right)^n\right) \\\\&=\frac 12\sum_{i=0}^{n}\binom nix^{n-i}\bigg(\bigg(-\sqrt{x^2+a}\bigg)^i+\bigg(\sqrt{x^2+a}\bigg)^i\bigg) \\\\&=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}x^{n-2j}(x^2+a)^j \\\\&=x^n+\sum_{j=1}^{(n-1)/2}\binom{n}{2j}x^{n-2j}(x^2+a)^j\end{align}$$ Since $\binom nm\equiv 0\pmod n$ for $1\le m\le n-1$, there exists a polynomial $f$ with integer coefficients such that $$P_n^{(a)}(x)=x^n+0\times (x^r-1)+nf$$ from which $$P_n^{(a)}(x)\equiv x^n\pmod{x^r-1,n}$$ follows.$\quad\blacksquare$

It is true that if $P_n^{(a)}(x)\equiv x^n\pmod{x^r-1,n}$, then $n$ is a prime number.

Proof :

Suppose that $n$ is an even number. Then, there exist a polynomial $f$ with integer coefficients and an integer $s$ such that$$P_n^{(a)}(x)=\sum_{i=0}^{n/2}\binom{n}{2i}x^{n-2i}(x^2+a)^i=x^n+s(x^r-1)+nf$$ Considering $[x^{n}]$ where $[x^k]$ denotes the coefficient of $x^k$ in $P_n^{(a)}(x)$, we get $$\sum_{i=0}^{n/2}\binom{n}{2i}\equiv 1\pmod n,$$ i.e. $$2^{n-1}\equiv 1\pmod n$$which is impossible.

So, $n$ has to be an odd number.

There exist a polynomial $\displaystyle g=\sum_{i=0}^{n}a_ix^i$ where $a_i$ are integers and an integer $t$ such that

$$P_n^{(a)}(x)=\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}(x^2+a)^j=x^n+t(x^r-1)+ng$$

Considering $[x^0]$, we have $$0=-t+na_0\implies t=na_0$$ So, we see that there exists a polynomial $h$ with integer coefficients such that $$P_n^{(a)}(x)=\sum_{j=0}^{(n-1)/2}\binom n{2j}x^{n-2j}(x^2+a)^j=x^n+nh\tag1$$

It follows that $[x^k]\equiv 0\pmod n$ for all $k$ such that $0\le k\le n-1$.

Now, $(1)$ can be written as

$$P_n^{(a)}(x)=\sum_{j=0}^{(n-1)/2}\sum_{k=0}^{j}\binom n{2j}\binom jkx^{n-2(j-k)}a^{j-k}=x^n+nh$$

So, we see that $$\begin{align}&[x^3]\equiv 0\pmod n \\\\&\implies \left(\binom n{n-3}\binom {(n-3)/2}0+\binom n{n-1}\binom {(n-1)/2}1\right)a^{(n-3)/2}\equiv 0\pmod n \\\\&\implies \binom n{n-3}\equiv 0\pmod n\end{align}$$ since $\gcd(a,n)=1$.

Also, we have $$\begin{align}&[x^5]\equiv 0\pmod n \\\\&\implies \bigg(\binom n{n-5}\binom {(n-5)/2}0+\binom n{n-3}\binom {(n-3)/2}1 \\&\qquad\qquad+\binom n{n-1}\binom {(n-1)/2}2\bigg)a^{(n-5)/2}\equiv 0\pmod n \\\\&\implies \binom n{n-5}\equiv 0\pmod n\end{align}$$ So, we can get (one can prove by induction) $$\begin{align}&[x^3]\equiv [x^5]\equiv [x^7]\equiv\cdots\equiv [x^{n-2}]\equiv 0\pmod n \\\\&\implies\binom n{n-3}\equiv\binom n{n-5}\equiv\binom n{n-7}\equiv\cdots\equiv\binom{n}{2}\equiv 0\pmod n \\\\&\implies\binom{n}{2}\equiv \binom{n}{3}\equiv \binom n4\cdots \equiv\binom n{n-2}\equiv 0\pmod n\tag2\end{align}$$

Suppose here that $\displaystyle n=\prod_{i=1}^mp_i^{b_i}$ is a composite number where $p_1\lt p_2\lt\cdots\lt p_m$ are primes and $b_i$ are positive integers.

Let $[[N]]$ be the number of prime factor $p_i$ in $N$.

Then, we have the followings :

  • $[[1!]]=[[2!]]=\cdots =[[(p_i-1)!]]=0$

  • $[[p_i!]]=1$

  • $[[(n-1)!]]=[[(n-2)!]]=\cdots =[[(n-p_i)!]]$

Using these, we see that $$\binom n1=\frac{n!}{1!(n-1)!}=n,\binom n2=\frac{n!}{2!(n-2)!},\cdots, \binom{n}{p_i-1}=\frac{n!}{(p_i-1)!(n-(p_i-1))!}$$ are divisible by $p_i^{b_i}$, and that $$\binom n{p_i}=\frac{n!}{p_i!(n-p_i)!}$$ is not divisible by $p_i^{b_i}$.

Therefore, we see that $$\binom n1=\frac{n!}{1!(n-1)!}=n,\binom n2=\frac{n!}{2!(n-2)!},\cdots, \binom{n}{p_1-1}=\frac{n!}{(p_1-1)!(n-(p_1-1))!}$$ are divisible by $n$, and that $$\binom{n}{p_1}=\frac{n}{p_1!(n-p_1)!}$$ is not divisible by $n$, which contradicts $(2)$.

It follows that $n$ is a prime number.$\quad\blacksquare$

  • $\begingroup$ If the proof you gave were correct that would be a significant breakthrough in theory of primality testing. $\endgroup$ – Peđa Terzić Jun 30 at 12:55
  • $\begingroup$ I have uploaded a preprint containing my question and your answer to viXra. Would you like me to add your name as a co-author ? $\endgroup$ – Peđa Terzić Jul 13 at 13:49
  • $\begingroup$ @PeđaTerzić: This answer is too elementary. To be honest, I began to think that I am missing something important. That's all I can say to you now. $\endgroup$ – mathlove Jul 13 at 15:53
  • $\begingroup$ ibb.co/hLf8jkr $\endgroup$ – Peđa Terzić Jul 13 at 17:42
  • 1
    $\begingroup$ In $P_n^{(a)}(x)=x^n+s(x^r-1)+nf$, why is $s$ necessarily an integer and not a polynomial of higher degree? $\endgroup$ – Peter Taylor Sep 12 at 13:24

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.