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

Inspired by Agrawal's conjecture in this paper and by Theorem 4 in this paper I have formulated 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 $T_n(x)$ be Chebyshev polynomial of the first kind , then $n$ is a prime number if and only if $T_n(x) \equiv x^n \pmod {x^r-1,n}$ .

You can run this test here .

I have tested this claim up to $5 \cdot 10^4$ and there were no counterexamples .


Algorithm implementation in Sage without directly computing $T_n(x)$ .

Python script that implements this test can be found here.

The Android app that implements this test can be found on Google Play.


I offer $100$ € for a proof of this claim. The proof must be published in one of the following journals: Journal of Number Theory , Algebra & Number Theory , Moscow Journal of Combinatorics and Number Theory .

  • 4
    $\begingroup$ @მამუკა ჯიბლაძე A stack overflow error has occurred . $\endgroup$
    – Pedja
    Nov 17, 2017 at 16:04
  • 4
    $\begingroup$ This is very cool, but, if true, can it be made into a useful algorithm? As stated it is about an $O(n^2)$ algorithm to determine primality of $n$ $\endgroup$
    – Igor Rivin
    Nov 17, 2017 at 17:07
  • 3
    $\begingroup$ @IgorRivin Seems that it depends on how fast one can find $T_n(x)\mod x^r-1$ (for very small $r$, about $\log n$) without computing $T_n(x)$ itself completely. The way it is implemented now, the whole $T_n(x)$ is found first, and I think it is worse than polynomial then. $\endgroup$ Nov 21, 2017 at 12:29
  • 3
    $\begingroup$ I've now posted a separate question about that $\endgroup$ Nov 21, 2017 at 13:38
  • 8
    $\begingroup$ Not that I think I am going to earn the reward, but could you please choose a non-Elsevier journal? Algebra and Number Theory is an open journal whose standards are at least as high. $\endgroup$ Nov 6, 2019 at 16:26

3 Answers 3


Wow. This deserves a separate answer.

As I mentioned in a comment, motivated by the question, in a previous comment, by Igor Rivin whether an efficient primality test can be made if the statement in the question is true, I asked a separate question about whether one could efficiently compute $T_n(x)$ modulo $x^r-1,n$. That question got a brilliant answer by Lucia, which enables to really demonstrate that if the statement in the question is true, one indeed obtains a very efficient primality test based on it.

I made this quick-and-dirty Mathematica code

polmul[f_, g_, r_, n_] := Mod[f.NestList[RotateRight, g, r - 1], n]

matmul[a_, b_, r_, n_] :=  Mod[
 {{polmul[a[[1, 1]], b[[1, 1]], r, n] + polmul[a[[1, 2]], b[[2, 1]], r, n], 
   polmul[a[[1, 1]], b[[1, 2]], r, n] + polmul[a[[1, 2]], b[[2, 2]], r, n]}, 
  {polmul[a[[2, 1]], b[[1, 1]], r, n] + polmul[a[[2, 2]], b[[2, 1]], r, n], 
   polmul[a[[2, 1]], b[[1, 2]], r, n] + polmul[a[[2, 2]], b[[2, 2]], r, n]}}, n]

matsq[a_, r_, n_] := matmul[a, a, r, n]

matpow[a_, k_, r_, n_] := If[k == 1, a,
  matpow[matsq[a, r, n], k/2, r, n], 
  matmul[a, matpow[matsq[a, r, n], (k - 1)/2, r, n], r, n]

xmat[r_, n_] :=
 {{PadRight[{0, 2}, r], PadRight[{n - 1}, r]},
  {PadRight[{1}, r], ConstantArray[0, r]}}

isprime[n_] := With[{r = smallestr[n]}, 
 If[r == 0, n == 2,
  With[{xp = matpow[xmat[r, n], n - 1, r, n]},
   Mod[RotateRight[xp[[1, 1]]] + xp[[1, 2]], n]
    === PadRight[Append[ConstantArray[0, Mod[n, r]], 1], r]

where smallestr is as in my other answer.

Running this on $n$ up to 100000 (all answers correct) gives the following timing:

enter image description here

Seems that it is of at worst logarithmic order (as that answer by Lucia suggests) - actually the graph of $\log(\operatorname{time}(n))/\log\log(n)$ looks almost like going to be bounded above:

enter image description here

Since the algorithm involves a recursive procedure for matrix powers, in principle one also has to check memory use. Here I must confess results are strange, maybe it is something hardware-specific. $$ \begin{array}{r|l} \text{amount of memory}&\text{number of cases (out of 100000)}\\ \hline 32&1407\\ 64&94408\\ 80&1\\ 288&1\\ 320&42\\ 352&3\\ 392&8\\ 424&2316\\ 456&1812\\ 3452552&1 \end{array} $$ This last amount 3452552 corresponds to $n=65969$, I have no idea why it needed so much memory. As I said this might be something machine specific - maybe some garbage collection occurred at that point or something like that. Anyway, as opposed to memory measurement timing data seem to be very accurate, I used the Mathematica command AbsoluteTiming and documentation says it gives actual processor time used for the calculation with quite high precision.

  • 3
    $\begingroup$ That IS amazing, thanks for investigating! $\endgroup$
    – Igor Rivin
    Nov 21, 2017 at 19:39
  • 1
    $\begingroup$ Looks like using the FFT method to multiply polynomials, and assuming r = O(log n), the whole algorithm takes O(log^3 n) time (times some polyloglogs, depending on your exact model of computation). $\endgroup$ Nov 22, 2017 at 3:24
  • 5
    $\begingroup$ @RyanO'Donnell Which is the same complexity as in the Agrawal et al. paper. I don't understand what, if anything, was gained by using Čebyšev's polynomials. $\endgroup$ Nov 22, 2017 at 13:48
  • 2
    $\begingroup$ @VítTuček You are right, that one is in fact simpler: have to find $n-1$st power of $x+a$ modulo $x^r-1$ instead of $n-1$st power of a 2$\times$2 matrix. On the other hand, in their case $r$ is larger and one has to test for several $a$s. $\endgroup$ Nov 23, 2017 at 8:13
  • 4
    $\begingroup$ @მამუკაჯიბლაძე Look at their conjecture in section six -- the one mentioned by the OP. I mean, it's great that this conjecture seems plausible also for $T_n$ and not only for $(x-1)^n$. Maybe it could be worthwhile to to try to find some large class of polynomials with this property. $\endgroup$ Nov 23, 2017 at 15:06

Decided to make a cw answer with an illustration of time growth.

I've tried on Mathematica this:

isprime[n_] := 
 With[{r = smallestr[n]}, 
  If[r == 0, n == 2, 
   PolynomialMod[PolynomialRemainder[ChebyshevT[n, t] - t^n, t^r - 1, t], n] === 0


smallestr[n_] := Module[{r},
  If[n==1 \[Or] EvenQ[n], Return[0]];
  For[r = 3, MemberQ[{0, 1, r - 1}, Mod[n, r]], r = NextPrime[r + 1],
   If[r < n \[And] Mod[n, r] == 0, Return[0]]

I've run it on $n$ up to about 31000 (all answers are correct); here is the graph of time needed as a function of $n$.

enter image description here

Growth looks like faster than polynomial - the graph of $\log(\text{time}(n))/\log(n)$ does not seem to stabilize:

enter image description here

On the other hand a rough upper bound on growth can be deduced from the fact that $\log(\text{time}(n))/(n\log(n))$ seems to go down:

enter image description here

Some additional remarks.


Datapoints are only for those $n$ which have positive value of smallestr, i. e. such that the corresponding $r$ is smaller than any nontrivial divisor of $n$. Understandably, for other $n$ calculation is qualitatively quicker.


Finding $r$ is very efficient: $$ \begin{array}{c|c} r&\text{smallest $n$ that requires this $r$}\\ \hline 11&29\\ 13&419\\ 19&1429\\ 23&315589\\ 29&734161\\ 31&1456729 \end{array} $$


Seems like $n$ is prime iff all coefficients of $T_n(x)-x^n$ are divisible by $n$. If true, this must be well known of course, but I don't know. Should be provable from the explicit form of coefficients of $T_n$.


Given (2), it is obvious that at prime $n$ the algorithm gives correct answer. To also prove that it detects composite $n$ one has to show the following. Denote by $a_0$, ..., $a_n$ the coefficients of $T_n(x)-x^n$. Then, if some of the $a_i$ is not divisible by $n$, then also one of the sums $s_j:=a_j+a_{j+r}+a_{j+2r}+...$, $j=0,...,r-1$ is not divisible by $n$. Seemingly if $a_j$ is not divisible by $n$ then $j$ is not coprime to $n$; maybe this can help.

  • $\begingroup$ It is clear that n is prime implies the desired mod n congruence. What results do you get for composite n? In particular, are there any composite n for which the mod n congruence hold and the x^r-1 congruence fails? Gerhard "Bidirectionals Are Not Always Symmetric" Paseman, 2017.11.19. $\endgroup$ Nov 20, 2017 at 5:41
  • 1
    $\begingroup$ @GerhardPaseman Experimentally, the mod n congruence holds iff n is prime. I believe it is not difficult to show using explicit expressions for coefficients of $T_n$,$$a_{n-2k}=(-1)^k2^{n-2k}\frac n2\frac{(n-k-1)!}{k!(n-2k)!},$$$k=0,1,...$ (all others zero). $\endgroup$ Nov 20, 2017 at 5:49
  • $\begingroup$ But you probably wanted to ask the opposite, right? Because if the mod n congruence holds, it will also hold mod x^r-1. The nontrivial fact to prove is that if mod n fails then it will also fail mod x^r-1. $\endgroup$ Nov 20, 2017 at 6:03
  • $\begingroup$ I probably did mean the opposite. Yes, if n is composite, then both congruences should fail. Gerhard "Doesn't Work With Ideals Ideally" Paseman, 2017.11.19. $\endgroup$ Nov 20, 2017 at 6:19

I do not share excitement about this test and believe it admits false positives (i.e., pseudoprimes). Here are some supporting arguments.

Assuming that $n\equiv 2\text{ or }3\pmod{5}$, we will have $r=5$. A square-free composite integer $n$ will pass the test for $r=5$ if $T_n(x)\equiv x^n\pmod{x^5-1,p}$ for every prime $p\mid n$. At the same time, it can be seen that \begin{split} T_n(x) \equiv x^n\pmod{x^5-1,\ 3}\quad&\Longleftrightarrow\quad n\equiv 3,\ 27,\ 38,\text{ or } 137\pmod{205}\\ T_n(x) \equiv x^n\pmod{x^5-1,\ 7}\quad&\Longleftrightarrow\quad n\equiv 7,\ 343,\ 858,\text{ or } 4797\pmod{6005}\\ T_n(x) \equiv x^n\pmod{x^5-1,\ 13}\quad&\Longleftrightarrow\quad n\equiv 13,\ 2197,\ 14268,\text{ or } 54927\pmod{71405} \end{split} and so on. In general, for a prime $p\equiv 2,3\pmod5$ $$T_n(x) \equiv x^n\pmod{x^5-1,\ p}\quad\Longleftrightarrow\quad n\equiv p,\ p^3,\ p^5,\text{ or } p^7\pmod{5q_p},$$ where $q_p$ is the period of $T_n(x)\pmod{x^5-1,\ p}$. (Similar congruences hold for $r=7$.)

It is not clear why certain $n$ cannot satisfy such congruences modulo every $p\mid n$. I do not say that it is easy to find such $n$, but its existence seems quite plausible.

P.S. Also, notice that in the AKS test the value of $r$ is taken satisfying $r>\log(n)^2$ (in fact, even the order $o_r(n)>\log(n)^2$), and this makes huge difference. Perhaps, the present test can be saved from pseudoprimes as well by requiring $r$ be of the magnitude of $\log(n)$ or so.

UPDATE (2021-10-02). Congruences above have been corrected. Here is a Sage code for computing $q_p$.

  • $\begingroup$ Have any pseudoprimes been found? $\endgroup$
    – Simd
    Jun 6, 2020 at 4:47
  • $\begingroup$ @Anush: No, but I did not search much. $\endgroup$ Jun 6, 2020 at 14:53
  • $\begingroup$ That's really exciting if this is still potentially the fastest primality testing algorithm. $\endgroup$
    – Simd
    Jun 6, 2020 at 14:54
  • $\begingroup$ I know this is an old answer, but are you sure about those congruences for $p=3$? I believe the modulus is $410$, not $625$. Note for example that $T_{628}\not\equiv x^{628}\pmod {x^5-1,3}$. $\endgroup$
    – Mastrem
    Oct 2, 2021 at 9:17
  • $\begingroup$ @Mastrem: Thanks for checking this. I've corrected the congruences and added a Sage code that computes them. $\endgroup$ Oct 2, 2021 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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