Suggest an algorithm for factorizing an integer such that each of its factor is square-free.


  • 6
    $\begingroup$ Googling around I found the claim "Squarefree factorization of integers is presently as difficult as complete factorization" in the paper A FAST ALGORITHM TO COMPUTE CUBIC FIELDS by K. BELABAS (MATHEMATICS OF COMPUTATION Volume 66, Number 219, July 1997, Pages 1213-1237) $\endgroup$ – j.p. Dec 17 '10 at 13:33

It's trivial given the complete factorization into primes. Currently we do not know any other way to compute squarefree parts and it is widely suspected that it cannot be computed in any simpler way.

This problem is important because one of the main tasks of computational algebraic number theory reduces to it (in deterministic polynomial time). Namely the problem of computing the ring of integers of an algebraic number field depends upon the square-free decomposition of the polynomial discriminant when computing an integral basis.

Contrast this difficulty with the trivial squarefree decomposition of polynomials by way of gcd with its derivative. The availability of derivatives for polynomials opens up a powerful toolbox that is not available for integers. For example once derivatives are available so are Wronskians - which provide powerful measures of dependence in transcendence theory and diophantine approximation. A simple yet stunning example is the elementary proof of the polynomial case of Mason's ABC theorem, which yields as a very special case a high-school-level proof of FLT for polynomials.

For references see my post here.

  • $\begingroup$ Bill, can you please look at this post and leave a comment. math.stackexchange.com/questions/3064068/… $\endgroup$ – user25406 Jan 10 at 0:40
  • 1
    $\begingroup$ @user25406 You can find discussion of the classical results mentioned by jyrki in Weil's book on the history of number theory. They are also implicit in the modern ideal theoretic approach, but I don't recall a reference at the moment. $\endgroup$ – Bill Dubuque Jan 10 at 1:09

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.