Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Factoring Polynomials

  1. Apr 22, 2007 #1
    Hey everyone,

    I was looking at another thread about factoring polynomials, and now I'm wondering if anyone knows any unusual or cool ways to factor them (i.e. not using numerical techniques such as Newton's Method). Unfortunately the only one I do know is the rational root theorem...
     
  2. jcsd
  3. Apr 22, 2007 #2
    look up pascal's triangle.
     
  4. Apr 22, 2007 #3
    I do know what Pascal's Triangle is, but I'm not seeing how it would help me factor a polynomial. Unless I happen to notice it's coefficients are the binomial coefficients. Am I missing something here?
     
  5. Apr 22, 2007 #4

    Gib Z

    User Avatar
    Homework Helper

    You not missing anything there, thats exactly what he meant. Sure its not the most general method, but it works on rare occasions.

    Check out https://www.physicsforums.com/showthread.php?t=166834, post 7, to see how I factored that polynomial. It works everytime, its just that when the first and last terms aren't perfect squares like in that case, its harder to solve.
     
  6. Apr 22, 2007 #5

    Gib Z

    User Avatar
    Homework Helper

    O And heres One I thought of thats not going to apply that often, but it could.

    I know that If we have a polynomial and we know one of the roots is repeated twice, like in (x-1)^2, then the derivative of the polynomial will have the same root.

    So reversing that, if you find a polynomial whose integral is a polynomial you know how to factorize, bingo.
     
  7. Apr 22, 2007 #6
    There's no general way to factor polynomials since this would go against Galois's theory.
     
  8. Apr 22, 2007 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    That's certainly not true. If that were so, then how could computers factor? :wink:

    Two general methods I know off the top of my head for factoring polynomials over the integers in one variable are:
    (1) Numerically obtain a complex root with enough accuracy, then use lattice techniques to find the minimal polynomial of that root, which is then a factor of your polynomial.
    (2) Factor your polynomial modulo p for enough small primes p, then use the Chinese Remainder Theorem (and a small search) to construct factors of your integer polynomial.
     
  9. Apr 22, 2007 #8

    Gib Z

    User Avatar
    Homework Helper

    No Algebraic Method Werg22 should have said then :)
     
  10. Apr 22, 2007 #9

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    there is an algebraic method for factoring polyn omials over say the integers, or rationals.

    notice that if f = gh, then for every a, f(a) = g(a)h(a), i.e. every value of f is factored by the correponding values of g and h.

    moreover a polynomial of degree n is determined by the values at n+1 integers.

    so if f has degree n take any n+1 integers, and evaluate f at all of them,. that gives you n+1 values of f.

    for each of these values take all of its possible integer factorizations. this gives you all possible values of both g and h at all these n+1 integers. then use lagrange interpolation to construct all possible pairs g,h having these values.

    then try them all to see if any of these factorizations work.

    if none of these work, then f is irreducible.

    yes it is a lengthy and tedious method, but it IS algebaric and does always work,

    this crude method is due to kronecker. and appears in van der waerden, and the harvard notes of richard brauer.

    obviously improvements are possible, but this shows it is possible to factor polynomials over any ring of coefficients in which one can already factor.
     
    Last edited: Apr 22, 2007
  11. Apr 23, 2007 #10

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    let me give an example. suppose you have a quartic polynomial f over Z you wish to factor. if it has non constant factors over Q then it has non constant factors over Z.

    the root factor theorem suffices to find all linear factors, as they correspond to rational roots which correspond to quotients of integer factors of the constant term and lead term.

    so we seek quadratic factors g,h such that f = gh. such a factor is determined by its values at any three distinct points, so choose three distinct integers and evaluate the original polynomial f at those points.

    assume for extreme simplicity that you always get the value 1. then both factors g,h must have value 1 or -1 at each point, and thus in fact g =h.

    so there are 8 possibilities for g=h, namely it haS EITHER VALUES 1,1,1 or -1,-1,-1, or 1,-1,-1, or -1,1,1, or 1,1,-1, or -1,-1,1, or 1,-1,1, or -1,1,-1,

    at those three points. this gives by lagrange interpolation, only 8 possible pairs of factors. either they work or they do not. thats it.

    what do you think of this?
     
    Last edited: Apr 23, 2007
  12. Apr 24, 2007 #11

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    since the method above is very old, does anyone have any newer versions to report? ones which perhaps are actually in use by computer factoring programs?
     
  13. Apr 24, 2007 #12
    For univariate polynomials, Mathematica uses a variant of the Cantor‐Zassenhaus algorithm to factor modulo a prime, then uses Hensel lifting and recombination to build up factors over the integers.

    Factoring over algebraic number fields is done by finding a primitive element over the rationals and then using Trager's algorithm.

    For multivariate polynomials Mathematica works by substituting appropriate choices of integers for all but one variable, then factoring the resulting univariate polynomials, and reconstructing multivariate factors using Wang's algorithm.
     
  14. Apr 24, 2007 #13

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Galois theory states that there is no way to write down the *roots* of an arbitrary poly as certain functions of its coefficients.
     
  15. Apr 24, 2007 #14

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    crosson, your explanations leave a bit to be desired, in the details. can you be a bit more self contained?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Factoring Polynomials
  1. Factors of a polynomial (Replies: 15)

  2. Polynomial Factors (Replies: 1)

  3. Factoring polynomials (Replies: 6)

Loading...