I would like to factor the polynomial $p(x,y)=x^p-y^p$ for some small prime $p$ $(p=3,5,\text{or } 7)$ and for all values of $p(x,y)$ with $1 < x < 1000$ and $1 < y < x$.

There is a similar post, but the answers just indicate that you can factor out $(x-y)$. I am aware of this, but I still cannot find a fast way to factor to rest of the polynomial efficiently. In a previous post I learnt quick ways to factor the polynomial $(x-y)$ using a sieve and I am hoping that there is a similar and efficient way to factor this polynomial.

  • $\begingroup$ over which field? oh, and please see math.meta.stackexchange.com/questions/5020 $\endgroup$ – Lord Shark the Unknown Jul 8 at 18:04
  • $\begingroup$ @LordSharktheUnknown just over the integers. And thank you! Sometimes I forget to type in Latex haha $\endgroup$ – sqrt-3299 Jul 8 at 18:05
  • 2
    $\begingroup$ I want to point out that you're not asking to factor a polynomial, you're asking to factor the outputs of the polynomial for a range of values. That is a different question. $\endgroup$ – runway44 Jul 11 at 20:45
  • $\begingroup$ @runway44 yes you are correct $\endgroup$ – sqrt-3299 Jul 11 at 21:17
  • $\begingroup$ Related question; math.stackexchange.com/questions/3268069/… $\endgroup$ – Servaes Jul 11 at 22:25

Apply $$x=(x-y)+y$$ and expand the binomial and cancel and you get :$$(x-y)((x-y)^{p-1}+p(x-y)^{p-2}y+\cdots+py^{p-1})$$ The factorization is conditional. It has the gcd of $x-y$ and $y$ raised to $p-1$ as a factor if p is in their gcd, that means $p$ can be raised to at least the $p$ power.


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.