For natural numbers $n$ and $x,$ the number of $n^{th}$ roots that have $x$ in the whole numbers place can be represented as $(x+1)^{n}-x^{n}.$ For $p$ prime,

$(x+1)^{n}-x^{n}-1\equiv0\bmod p$ iff $n=p^{k}.$

The AKS test uses this identity at $k=1$ giving,

$(x+1)^{n}-x^{n}-1\equiv0\bmod n$ iff $n$ is prime.

I have found that it is also interesting if we evaluate the exponent at only the even numbers $2n,$ meaning in this form,


In this form, the smallest number $m$ that will not divide each and every coefficient of the expansion seems to be the greatest prime factor of $2n+1.$ In other words, If you choose $2n=32$ then dividing by $2,3,4,5,6,7,8,9$and $10$ will give some integer coefficients, but when you divide by the greatest prime factor of $33$ which is $11$, there are none. This is also the smallest number for which that occurs. So this can be used as a test.

Now to determine what this greatest prime factor is it seems that you would have to check every term, or at least half of them, so I'm not sure if it can be afforded the same computation simplification as the AKS test, but this still may be a polynomial time test for greatest prime factor of $2n+1.$

So my question is, does this idea afford a polynomial time test for this or is it a useless idea?

To my best knowledge, this is unknown. But, I of course could be wrong.

  • $\begingroup$ Is the question, whether the prime-number-test can be used to factor an arbitary odd number in polynomial time ? Then, the answer is : no, since no polynomial time algorithm for factoring is known. $\endgroup$ – Peter May 17 '16 at 12:34
  • $\begingroup$ @Peter No. not factoring, just to identify the greatest prime factor. The AKS test uses that only a prime will divide. The test I'm talking about specifically identifies the greatest prime factor because it is the minimal number such that there are no integer coefficients. $\endgroup$ – e2theipi2026 May 17 '16 at 15:20
  • $\begingroup$ If this would work for every composite number, we would have an efficient method to factor any number. $\endgroup$ – Peter May 17 '16 at 15:28
  • 1
    $\begingroup$ If you can find any one factor in polynomial time then you can find all of them in polynomial time, because at worst you have to do your procedure $\log_2(N)$ times. $\endgroup$ – Ian May 17 '16 at 15:34
  • 2
    $\begingroup$ Perhaps I misunderstand, but $(x+1)^{2n} - x^{2n}$ has almost $2n$ non-zero coefficients, almost all of which are much much larger than $2n + 1$. How is finding the smallest prime not dividing any of these $2n$ big numbers easier than say finding the smallest prime dividing $2n+1$ by trial divison? At least using trial divison one only has to check up to $\sqrt{2n+1}$ or so. $\endgroup$ – Marc Paul May 17 '16 at 17:03

It seems this question was answered in the comments, so I'm using an answer to my own question to close the question. If anyone has an answer to give they are welcome to do so and I will probably accept it.


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.