Return to Answer

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. (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 that computes them.

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$.

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 \equiv x^n\pmod{x^5-1,\ 3}\quad&\Longleftrightarrow\quad n\equiv 0,\ 1,\ 3,\ 9,\ 27,\ 38,\ 81,\ 114,\text{ or } 137\pmod{205}\\ T_n \equiv x^n\pmod{x^5-1,\ 7}\quad&\Longleftrightarrow\quad n\equiv 0,\ 1,\ 7,\ 49,\ 343,\ 858,\ 2401,\ 3554,\text{ or } 4797\pmod{6005}\\ T_n \equiv x^n\pmod{x^5-1,\ 13}\quad&\Longleftrightarrow\quad n\equiv 0,\ 1,\ 13,\ 169,\ 2197,\ 14268,\ 28561,\ 42674,\text{ or } 54927\pmod{71405} \end{split} and so on. (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 that computes them.

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. (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 that computes them.

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 prme $p\mid n$. At the same time, it can be seen that \begin{split} T_n \equiv x^n\pmod{x^5-1,\ 3}\quad&\Longleftrightarrow\quad n\equiv 3,\ 27,\ 243,\text{ or } 342\pmod{625}\\ T_n \equiv x^n\pmod{x^5-1,\ 7}\quad&\Longleftrightarrow\quad n\equiv 7,\ 343,\ 16807,\text{ or } 24878\pmod{42035}\\ T_n \equiv x^n\pmod{x^5-1,\ 13}\quad&\Longleftrightarrow\quad n\equiv 13,\ 2197,\ 371293,\text{ or } 554762\pmod{928265} \end{split} and so on. (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.

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 \equiv x^n\pmod{x^5-1,\ 3}\quad&\Longleftrightarrow\quad n\equiv 0,\ 1,\ 3,\ 9,\ 27,\ 38,\ 81,\ 114,\text{ or } 137\pmod{205}\\ T_n \equiv x^n\pmod{x^5-1,\ 7}\quad&\Longleftrightarrow\quad n\equiv 0,\ 1,\ 7,\ 49,\ 343,\ 858,\ 2401,\ 3554,\text{ or } 4797\pmod{6005}\\ T_n \equiv x^n\pmod{x^5-1,\ 13}\quad&\Longleftrightarrow\quad n\equiv 0,\ 1,\ 13,\ 169,\ 2197,\ 14268,\ 28561,\ 42674,\text{ or } 54927\pmod{71405} \end{split} and so on. (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 that computes them.