# A congruence involving Chebyshev polynomials

Can you provide a proof or a counterexample to the following claim :

Let $n$ be a natural number greater than one and let $T_{n}(x)$ be Chebyshev polynomial of the first kind , then $n$ is prime if and only if :$\displaystyle\sum_{k=0}^{n-1}2T_{n-1}\left(\frac{k}{2}\right) \equiv -1 \pmod n$ .

You can run this test here .

I have tested this claim up to 10000 .

I was searching for counterexample using the following two Pari/GP codes :

Chebyshev1(lb,ub)={
forprime(n=lb,ub,
if(!(Mod(sum(k=0,n-1,2*polchebyshev(n-1,1,k/2)),n)==n-1),print(n)))
}

Chebyshev2(lb,ub)={
forcomposite(n=lb,ub,
if((Mod(sum(k=0,n-1,2*polchebyshev(n-1,1,k/2)),n)==n-1),print(n)))
}

• Mathematica code: n = 2; While[PrimeQ[n]==(Mod[Sum[2ChebyshevT[n-1,k/2],{k,0,n-1}],n]==n-1),n++]. It will only halt if it founds a counter-example. None was found for $2\le n\le 10784$. Jan 29, 2018 at 21:58
• Note that $-1\equiv p-1 \mod p$ which is equal the Euler function $\varphi(p)$ for prime $p$. Here's a bit wider guess checked for $n\le 5000$: $\mathrm{lhs}(n)\mod n=\varphi(n)$ iff $n=2^k$ or $n=p^{2k-1}$, $k\in \mathbb N$ for prime $p\ge3$. Jan 30, 2018 at 9:51
• On the other hand, there are many $n$ such that lhs($n$) $\mod n = 0$. This seems to occur for about $1/4$ of all integers, e.g. 499 times for $n \le 2000$. Jan 30, 2018 at 14:21

This answer proves that if $n$ is prime, then $$\sum_{k=0}^{n-1}2T_{n-1}\left(\frac{k}{2}\right) \equiv -1 \pmod n\tag1$$

For $n=2$, $(1)$ holds since $$\sum_{k=0}^{1}2T_{1}\left(\frac{k}{2}\right)=2T_1(0)+2T_1\left(\frac 12\right)=2\cdot 0+2\cdot\frac 12\equiv -1\pmod 2$$

For $n=3$, $(1)$ holds since $$\small\sum_{k=0}^{2}2T_{2}\left(\frac{k}{2}\right)=2T_2(0)+2T_2\left(\frac 12\right)+2T_2(1)=2\cdot (-1)+2\cdot\left(-\frac 12\right)+2\cdot 1\equiv -1\pmod 3$$

In the following, $n$ is prime greater than three.

For $2\le k\le n-1$, using that $\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)=1$, we have \small\begin{align}&T_{n-1}\left(\frac{k}{2}\right)\\\\&=\frac 12\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}+\frac 12\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}\\\\&=\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac 12\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}+\frac 12\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n-1}\right)\\\\&=\frac 12\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^n+\frac 12\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^n\\\\&=\frac k4\left(\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}+\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}\right)\\\\&\qquad\quad +\frac 12\sqrt{\left(\frac{k}{2}\right)^2-1}\ \left(\left(\frac{k}{2}-\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}-\left(\frac{k}{2}+\sqrt{\left(\frac{k}{2}\right)^2-1}\right)^{n}\right)\end{align}

By the binomial theorem, \small\begin{align}T_{n-1}\left(\frac{k}{2}\right)&=\frac 12\cdot \frac k2\sum_{i=0}^{n}\binom ni\cdot \left(\frac k2\right)^{n-i}\left(\left(-\sqrt{\left(\frac k2\right)^2-1}\right)^i+\left(\sqrt{\left(\frac k2\right)^2-1}\right)^i\right)\\\\&\qquad\quad +\frac 12\sqrt{\left(\frac k2\right)^2-1}\ \sum_{i=0}^{n}\binom ni\cdot \left(\frac k2\right)^{n-i}\left(\left(-\sqrt{\left(\frac k2\right)^2-1}\right)^i-\left(\sqrt{\left(\frac k2\right)k^2-1}\right)^i\right)\\\\&=\frac 12\cdot \frac k2\sum_{j=0}^{(n-1)/2}\binom{n}{2j}\cdot \left(\frac k2\right)^{n-2j}\cdot 2\left(\sqrt{\left(\frac k2\right)^2-1}\right)^{2j}\\\\&\qquad\quad +\frac 12\sqrt{\left(\frac k2\right)^2-1}\ \sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}\cdot \left(\frac k2\right)^{n-(2j-1)}\cdot (-2)\left(\sqrt{\left(\frac k2\right)^2-1}\right)^{2j-1}\\\\&=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}\cdot \left(\frac k2\right)^{n-2j+1}\left(\left(\frac k2\right)^2-1\right)^{j}-\sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}\cdot \left(\frac k2\right)^{n-(2j-1)}\left(\left(\frac k2\right)^2-1\right)^{j}\end{align}

Multiplying the both sides by $2^{n+1}$, we get $$2^{n+1}T_{n-1}\left(\frac{k}{2}\right)=\sum_{j=0}^{(n-1)/2}\binom{n}{2j}\cdot k^{n-2j+1}\left(k^2-4\right)^{j}-\sum_{j=1}^{(n+1)/2}\binom{n}{2j-1}\cdot k^{n-(2j-1)}\left(k^2-4\right)^{j}$$ Since $k^{n+1}=k^2\cdot k^{n-1}\equiv k^2\cdot 1\equiv k^2\pmod n$ for $2\le k\le n-1$ by Fermat's little theorem, and $\binom nj\equiv 0\pmod n$ for $1\le j\le n-1$, we have, for $2\le k\le n-1$, $$4T_{n-1}\left(\frac{k}{2}\right)\equiv k^{n+1}-(k^2-4)^{(n+1)/2}\equiv k^2-(k^2-4)^{(n+1)/2}\pmod n$$

Since this holds for $k=0,1$ as well, we have, letting $N:=\frac{n+1}{2}$, \begin{align}\sum_{k=0}^{n-1}4T_{n-1}\left(\frac k2\right)&\equiv \sum_{k=0}^{n-1}\left(k^2-(k^2-4)^{N}\right)\equiv \frac{(n-1)n(2n-1)}{6}-\sum_{k=0}^{n-1}(k^2-4)^{N}\pmod n\\\\&\stackrel{*}\equiv -\sum_{k=0}^{n-1}(k^2-4)^{N}\equiv -(-4)^N-\sum_{k=1}^{n-1}(k^2-4)^{N}\pmod n\\\\&\equiv (-1)^{N+1}\cdot 2^{n+1}-\sum_{k=1}^{n-1}\sum_{j=0}^{N}\binom Nj(k^2)^{j}\cdot (-4)^{N-j}\pmod n\\\\&\equiv (-1)^{N+1}\cdot 4-\sum_{j=0}^{N}\binom Nj(-4)^{N-j}S_{2j}\pmod n\tag2\end{align} where $\stackrel{*}\equiv$ comes from that $(n-1)(2n-1)\equiv 0\pmod 6$, and we defined $S_i$ as $\displaystyle\sum_{k=1}^{n-1}k^i$.

Now, we use the following lemma :

Lemma : $S_0\equiv S_{n-1}\equiv -1\pmod n, S_{n+1}\equiv 0\pmod n$ and $S_i\equiv 0\pmod n$ for $1\le i\le n-2$.

Proof for the lemma :

We have $S_0\equiv \displaystyle\sum_{k=1}^{n-1}1\equiv -1\pmod n$. By Fermat's little theorem, $S_{n-1}\equiv S_0\equiv -1\pmod n$.

Next, let us prove $S_i\equiv 0\pmod n$ for $1\le i\le n-2$ by induction.

The base case : $S_1\equiv \displaystyle\sum_{k=1}^{n-1}k^1\equiv \frac{(n-1)n}{2}\equiv 0\pmod n$.

Suppose that $S_i\equiv 0\pmod n$ for $1\le i\le j$. Since we have $$2^{j+2}-1^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}1^i$$ $$3^{j+2}-2^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}2^i$$ $$\vdots$$ $$n^{j+2}-(n-1)^{j+2}=\sum_{i=0}^{j+1}\binom{j+2}{i}(n-1)^i$$ adding these, we get $$n^{j+2}-1=\sum_{k=1}^{n-1}\sum_{i=0}^{j+1}\binom{j+2}{i}k^i=\sum_{i=0}^{j+1}\binom{j+2}{i}S_i=n-1+(j+2)S_{j+1}+\sum_{i=1}^{j}\binom{j+2}{i}S_i$$ from which we have $$S_{j+1}=\frac{1}{j+2}\left(n^{j+2}-n-\sum_{i=1}^{j}\binom{j+2}{i}S_i\right)$$ By the inductive hypothesis, we see that $S_{j+1}\equiv 0\pmod n$ if $j\le n-3$.

Finally, by Fermat's little theorem, $S_{n+1}\equiv \displaystyle\sum_{k=1}^{n-1}k^{n+1}\equiv \displaystyle\sum_{k=1}^{n-1}k^{2}\equiv S_2\equiv 0\pmod n.\qquad\blacksquare$

Using the lemma, we have, from $(2)$,

\begin{align}\sum_{k=0}^{n-1}4T_{n-1}&\equiv (-1)^{N+1}\cdot 4-\sum_{j=0}^{N}\binom Nj(-4)^{N-j}S_{2j}\pmod n\\\\&\equiv (-1)^{N+1}\cdot 4-(-4)^{N}\cdot (-1)-\binom{N}{(n-1)/2}(-4)^{N-(n-1)/2}(-1)\pmod n\\\\&\equiv -\frac{n+1}{2}\cdot (-4)\cdot (-1)\equiv -2\pmod n\end{align} It follows from $\gcd(n,2)=1$ that $$\sum_{k=0}^{n-1}2T_{n-1}\left(\frac k2\right)\equiv -1\pmod n$$

• Stupid question. How is in the case of $n=2$, $1\equiv -1\ (\text{mod} 2)$? Thanks. Jan 30, 2018 at 22:19
• @pisoir: $a\equiv b\pmod 2$ means that $a-b$ is divisible by $2$. You might want to see here. Jan 31, 2018 at 3:42
• This direction follows from the simple fact that the polynomial $2T_n(x/2)$ is monic and the coefficients are integers... Jan 31, 2018 at 8:10