factorizing a polynomial

[steveB]

Very interesting. I'm coming home on the train now, so I'll need to read this more carefully later.

However, you also commented about the sqrt(b^2-4ac) being an integer. Let me ask, is this the key test that PG is looking for? If it is an integer, is it necessarily factorable, and if not an integer, is it not factorable?

 

[The Electrician]

I would think so. If it's an integer then the roots are rational, and the trinomial will be factorable. I think the procedure I gave is what the mathematicians would call a constructive proof.

 

[MrAl]

Hi,

Im not sure about the sqrt(b^2-4*a*c) being an integer helps because some values of a,b,c might still evaluate to an integer. Maybe that's too shallow of a view though.

But anyway, here's what i found. Using the previous formula repeated here:
[LATEX]\[\left( x-\frac{\sqrt{{b}^{2}-4\,a\,c}-b}{2\,a}\right) \,\left( a\,x-\frac{2\,a\,c}{\sqrt{{b}^{2}-4\,a\,c}-b}\right) \][/LATEX]

which by the way can be written a little differently to make it a little simpler, i got for Steve's new example:
(x+3/32)*(6144*x+3328)

which clearly contains two integers and one non integer. Now to get an all-integer solution, that 3/32 would have to be made an integer. To make that an integer we can multiply that first factor on the left by 32 (super obvious). This gives the first factor:
(32*x+3)

but to maintain equality we have to divide the second factor by the same integer (32) and we get:
192*x+104

so the resulting factorization is:
(32*x+3)*(192*x+104)=6144*x^2+3904*x+312

This is definitely an integer factorization.

 

[The Electrician]

Im not sure about the sqrt(b^2-4*a*c) being an integer helps because some values of a,b,c might still evaluate to an integer.

What do you mean by this? Are you considering the possibility that sqrt(b^2-4*a*c) might be an integer if a, b and c are not integers?

I'm only dealing with the case where a, b and c are integers. I assumed that was what the OP was considering, and that's what I specified.

 

[MrAl]

Hi there Electrician,

Yes that makes sense. Maybe i was thinking about all the possibilities of a,b,c instead of just integers, but yes we're talking about them all being integers for the most part. So probably the discriminant can be a 'first test' so to speak.

In any case, it looks like the formula i presented earlier:
[LATEX]\[\left( x-\frac{\sqrt{{b}^{2}-4\,a\,c}-b}{2\,a}\right) \,\left( a\,x-\frac{2\,a\,c}{\sqrt{{b}^{2}-4\,a\,c}-b}\right) \][/LATEX]

does in fact work to factorize the quadratic:
a*x^2+b*x+c

for any combination of a,b,c integers where a is not equal to zero and c is not equal to zero (which case it degenerates to a simpler case anyway). The formula above appears to work regardless what we throw at it. It has been checked for these sets:
-199*x^2-199*x-199
to
+199*x^2+199*x+199

for all but a=0 and/or c=0 and for only a real discriminant. That means 63044792 or more combinations of a,b,c have been checked (39534846 real), which means really any coefficient a,b,c can take on values from -199 to +199 and we still get a valid factorization. The validity was checked down to an error limit of 0.0001 percent.

So at least it looks like we have a way to factorize at least into the form:
(x-r1)*(a*x-r2)

(where r1 and r2 are calculated by the constant terms in the formula)

and then we can examine it and determine if this can be made into an integer factorization by multiplying one factor by a number N and then dividing the other factor by N.

There's a different formula that works the same way where we multiply one of the roots by a, but the results will come out the same or similar. These probably also work for non integer coefficients and possibly even for non real discriminant.

I suppose i could apply a more rigorous mathematical proof but i just dont feel the need, but comments welcome

It looks like this may work too but i havent tested it very well yet:
[LATEX]\[\left( x+\frac{\sqrt{{b}^{2}-4\,a\,c}+b}{2\,a}\right) \,\left( a\,x-\frac{\sqrt{{b}^{2}-4\,a\,c}-b}{2}\right) \][/LATEX]

 

[steveB]

In any case, it looks like the formula i presented earlier:
[LATEX]\[\left( x-\frac{\sqrt{{b}^{2}-4\,a\,c}-b}{2\,a}\right) \,\left( a\,x-\frac{2\,a\,c}{\sqrt{{b}^{2}-4\,a\,c}-b}\right) \][/LATEX]

does in fact work to factorize the quadratic:
a*x^2+b*x+c

for any combination of a,b,c integers where a is not equal to zero and c is not equal to zero (which case it degenerates to a simpler case anyway). The formula above appears to work regardless what we throw at it. It has been checked for these sets:
-199*x^2-199*x-199
to
+199*x^2+199*x+199

I"m having a hard time with this. You say you checked it for all these cases, but what about this example ...

(3x+4)(2x+5)=6x^23x+20

???

It seems to me that there is no assurance that "a" will be prime, so forcing the condition at either "d" or "f" must be 1, does not seem correct.

Your formula gives the factorization (x+4/3)(6x+15)=6x^23x+20 which is a valid factorization, but does not give integers for all d, e, f and g.

 

[The Electrician]

It looks like this may work too but i havent tested it very well yet:
[LATEX]\[\left( x+\frac{\sqrt{{b}^{2}-4\,a\,c}+b}{2\,a}\right) \,\left( a\,x-\frac{\sqrt{{b}^{2}-4\,a\,c}-b}{2}\right) \][/LATEX]

It won't always give an integer factorization because [LATEX]\frac{\sqrt{{b}^{2}-4\,a\,c}+b}{2\,a}[/LATEX] may not be an integer. If not, then the final step you described ("and then we can examine it and determine if this can be made into an integer factorization by multiplying one factor by a number N and then dividing the other factor by N.") will have to be applied in those cases.

You seem to be trying to obtain a formula that will give the desired final result all at once. I think it may be necessary for the human operator to make some decisions in some cases to get a result in a desired form.

If [latex]\sqrt{b^2 - 4 a c}}[/latex] is an integer, the roots of the trinomial can be expressed as rational numbers e/d and g/f. Those fractions can always be represented in lowest terms, where any of d, e, f or g can be 1; the pairs (e,d) and (g,f) will be relatively prime. If a, b and c are relatively prime, then the factorization of the original trinomial will be given by (dx-e)(fx-g); problem solved.

In case a, b and c are not relatively prime, the factors (dx-e)(fx-g) must be multiplied by a/(d*f). If a/(d*f) is composite (not prime), there will be more than one way to distribute the factors of a/(d*f) over the two trinomial factors (dx-e)(fx-g). If we wanted to avoid the necessity of a human having to make a decision about how to distribute those factors, we could just multiply the (dx-e) factor by a/(d*f).

Interestingly, concerning the question of obtaining the rational roots in lowest terms, my calculator won't let me show a fraction that is NOT in lowest terms. As soon as I type in a fraction, the calculator reduces it. Mathematica does the same thing. A person could determine a rational root of a quadratic trinomial by hand, and have it not be in lowest terms. That's what the quadratic formula will usually give you. Using such non-reduced rational roots can give a factorization of a trinomial with the same roots as the original, factors which are within a multiple of the desired factorization.

 

[The Electrician]

The OP asked a couple of questions.

Thank you, MrAl.

So I think I had it wrong from the start. Actually the polynomial x^2+7x-6 is not factorable over integers but it is factorable over real numbers. And whether a polynomial is factorable over real numbers (which also include integers) is determined by the discriminant b^2-4ac; if the discriminant is negative then the polynomial is not factorable over real numbers.

Now I must rephrase what I said earlier.

Q1: A polynomial of the type x^2+7x-6 is not factorable over integers. I have always thought whenever there is such a case that a polynomial is not factorable over integers then the coefficient of the 'x' term would be a prime number but still that does not mean whenever the coefficient of 'x' term is a prime, it's not factorable. For instance, the coefficient of 'x' term in the polynomial, x^2+3x+2, is prime but it's still factorable. But still whenever a polynomial is not factorable over integers, the coefficient of 'x' term is going to be a prime. Do I have it correct? Please let me know. Thank you.

No. Obviously, if you have a quadratic trinomial that is not factorable over the integers, and whose coefficient "a" is prime, you need only multiply the whole thing by 2 and now you have a trinomial with a composite "a" which is not factorable over the integers.

Q2: Is there a simple way to tell if a quadratic polynomial is not factorable over integers by just looking at the coefficients?

Yes. If [latex]\sqrt{b^2 - 4 a c}}[/latex] is not an integer, the trinomial is not factorable over the integers.

 

[MrAl]

I"m having a hard time with this. You say you checked it for all these cases, but what about this example ...

(3x+4)(2x+5)=6x^23x+20

???

It seems to me that there is no assurance that "a" will be prime, so forcing the condition at either "d" or "f" must be 1, does not seem correct.

Your formula gives the factorization (x+4/3)(6x+15)=6x^23x+20 which is a valid factorization, but does not give integers for all d, e, f and g.

Hi there Steve and Electrician,

Steve:
What i proved (for a limited but very varied range of integers for the constants) was that the formula i provided does provide a factorization. But i didnt say it provided an integer factorization. But i explained what to do in that case in post #23, and in post #25 i generalized a little more. If we end up with a non integer constant after using that formula then we multiply that by another constant to make it integer (and it must be an integer too) and that gives us the first factor, then we divide the second factor by that same constant and that gives us the second factor.

So if we do 6x^2+23x+20 and we get (x+4/3)*(6x+15) using the formula, then we look at it and see that we need to multiply 4/3 by 3 to get an integer, and doing that we get the first factor (3x+4), but to maintain equality we must then divide the second factor by the same constant (3) and doing that we get (2x+5) so the integer factorization is:
(3x+4)*(2x+5)=6x^2+23x+20

Does that make more sense now?

The 'formula' was checked just to make sure it could actually factor the quadratic. Once we have any valid factorization i think we should be able to find an integer factorization if one exists. We might look into this more also, such as the case when we get 1.33333333 instead of the nice and neat 4/3. I have a feeling that we can find a way to automate that process too.

Also, 'forcing' one of the coefficients of x in one factor to be 1 is not a problem, because obviously the factors themselves factor. Once we find the correct one for the integer factorization, we're done. So the final step only involves finding the correct coefficient of x for (say) the first factor. It's got to be simple enough right?


Electrician:
Yes more or less i am looking for an automated solution, which looks more and more promising. The fact that we can find a factorization for ANY trinomial has got to be valuable one way or another.

There's always the chance that we'll find more than one way of solving the main topic of this thread too

 

[steveB]

MrAl,

Thank you. I think I follow it now.

The Electrician,

Thank you. Very nice summary and answers for PG.

There is quite a bit of material from both of you, so I'll take the time to read it carefully over the next few days. I've been very busy lately and was not able to read it in the level of detail it deserves.