05 March 2008

A factoring trick

I came across the polynomial f(x) = 2x2 + 3x - 5 during a calculation I was doing a few days ago. I wanted to factor it. Sure, I could have done it the usual way. But I have a better intuition for factoring numbers than I do for factoring polynomials. So I plug in x = 10; then f(10) = 225.225 factors into 9 times 25. Perhaps this reflects a factorization f(x) = g(x) h(x), where g(10) = 9, h(10) = 25.

Indeed, it does: 2x2 + 3x - 5 = (x-1)(2x+5). Of course, this gives a whole family of integer factorizations, plugging in different integers for x.

Of course, this doesn't work in general; consider for example 2x2 + 2x + 5, which doesn't factor at all. And when the trick is spelled out explicitly it seems to be irredeemably flawed -- how did I know to take (x-1)(2x+5), say, and not (x-1)(3x-5)? (More importantly, can this be explained without reference to the original polynomial?) One could perhaps point out that, say, 184 = (8)(23), which is just f(9) = g(9) h(9), and so on; from a family of such facts it might be possible to deduce the polynomial factorization, but at that point it's just not worth the trouble. These sorts of tricks, like jokes, rarely stand up to explanation.


Unknown said...

This is how computer algebra systems factor multivariate polynomials: substitute values for the variables to get a univariate or bivariate polynomial, factor that, then "lift" the factors back to the original polynomial.

Aaron said...

Carl -- cool! I'll have to find out how that works sometime...

Anonymous said...

yes cool.

Anonymous said...

This is Kronecker's algorithm for factoring polynomials. The beauty of it is that, although it is terribly inefficient, it at least always reduces the problem to a finite calculation. Given a polynomial of degree n with integral coefficients, compute n+1 values at integers. If are are zero, you immediately get a factor. If they are all nonzero, then each has only finitely many factorizations, and considering each possibility will lead to all possible factorizations of the original polynomial.

Lattice basis reduction methods can factor polynomials over Q in polynomial time, so Kronecker's method is only of historical interest in the univariate case, but it is still by far the easiest algorithm to explain from scratch.

Anonymous said...

I can barely do my invoice factoring, let alone polynomial factoring! pass me a calculator!

Anonymous said...

Online Casino Gambling tyuueooru
Free Casino Play
Reliable Online Casinos
Get free welcome bonus when depositing for the first time! You'll get 100% free with your first deposit or up to $20.
[url=http://www.nhgaa.org/]Casino Bonus[/url]
In fact, there is no risk at all.
http://www.nhgaa.org/ - Internet Casino

Also, check out whether or not their customer service is available 24/7.