factorizing a polynomial

[PG1995]

Hi

Q1: A polynomial of the type x^2+7x-6 is not factorable over real numbers. I have always thought whenever there is such a case that a polynomial is factorable 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 real numbers, the coefficient of 'x' term is going to be a prime. Do I have it correct? Please let me know. Thank you.

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

Regards
PG

 

[MrAl]

Hi,

Did you every try the method of "Completing the square" ?

Remember that the quadratic formula is:

(-b+/-sqrt(b^2-4ac))/2a

and what determines the real solutions is the discriminant b^2-4ac.
If b^2-4ac is negative then the root solutions are not real.

Solving the inequality:
b^2-4ac<0

we get:
b^2<4ac

so if b^2 is less than 4ac we have non real solutions which means it cant be factored with real numbers.

 

[PG1995]

Thank you, MrAl.

In the polynomial x^2+7x-6, we have 7^2-4(1)(-6)=73, so the discriminant is not negative but it still can't be factored. Where do I have it wrong? Please let me know. Thanks.

Regards
PG

 

[MrAl]

Hi,

x^2+7*x-6

The two roots are:

r1=(sqrt(73)-7)/2

and

r2=(-sqrt(73)-7)/2

so that factors into:

(x-r1)*(x-r2)=(x-(sqrt(73)-7)/2)*(x+(sqrt(73)+7)/2)

 

[PG1995]

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.

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

Please help me. Thanks.

Regards
PG

 

[steveB]

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.

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

Please help me. Thanks.

Regards
PG

You are posing an interesting mathematical question, but I think you need to clarify the mathematical statement better. Are you talking about polynomials of the form ax^2+bx+c where a, b and c are integers? And, if so, are you trying determine when you can factor this into a product (dx+e)(fx+g), where d, e, f and g are integers? Or, is it something a little different than that?

 

[PG1995]

Thank you, Steve.

You are posing an interesting mathematical question, but I think you need to clarify the mathematical statement better. Are you talking about polynomials of the form ax^2+bx+c where a, b and c are integers? And, if so, are you trying determine when you can factor this into a product (dx+e)(fx+g), where d, e, f and g are integers? Or, is it something a little different than that?

I had quadratic polynomial in mind with integral coefficients, and yes, I'm trying to determine when I can factor it into a product (dx+e)(fx+g), where d, e, f and g are integers.

Regards
PG

 

[MrAl]

Hello again,

<still editing>

Here's what it looks like:

D=sqrt(b^2-4*a*c)
N1=c/a
N2=D/a

If D is real and N1 is an integer and N2 is an integer then it factors into two factors that contain only integers.

I havent checked this out yet but you can do that if you like.

But then again if we have to calculate the discriminate then we might as well calculate the two roots and get it over with

On the other hand the two factors:
(x-R1) and (x-R2) expand into;
x^2-x(R1+R2)+R1*R2

so we can divided all the coeff's by a first:
ax^2+bx+c
x^2+x*b/a+c/a

then look to see if the product of two integer numbers equals c/a and the sum equals b/a:
R1*R2=c/a
R1+R2=b/a

We do have to be careful here though because either root or both could be negative too.

PS.
I've read that knowing if b is prime and a is positive we can tell right away, but the problem here is that knowing if b is prime might be a little complicated in itself if we are dealing with larger numbers for b.

 

[steveB]

It's not clear that there is practical value in finding an answer to this question, but one can study mathematical questions even if there is no practical use.

One thing we can say about this is that any expression of the form (dx+e)(fx+g), where d, e, f and g are integers, will always generate a polynomial of the form ax^2+bx+c, where a, b and c are integers. This is because the set of integers is closed under the operations of multiplication and addition and expanding the product gives the following relations ...

a=df
b=dg+ef
c=eg

Hence, it is much easier to think in this direction, rather than trying to determine if ax^2+bx+c is factorable into the form (dx+e)(fx+g), where d, e, f and g are integers. That is, all possible integer values of d, e, f and g, generate a quadratic that can be factored into the form with integer coefficients.

So, my guess is that there is not a general and simple way to look at the a, b and c coefficients and know that the polynomial is factorable in the form you specified. I think one needs to be very gifted to look at integers a, b and c and know that there is exists other integers d, e, f and g that satisfy the above constraints. I'm not aware that any characterization of the integers as prime or not prime helps too much; although, I'm sure one can identify special cases (as MrAl just did) where a, b and/or c are prime and then a simple check is possible. For example, if I note that a and c are prime numbers, then i can derive that if b=a+c or b=ac+1, the polynomial is factorable in the way you specified.

A follow on question would be whether you can devise simple checking algorithms that tell you the answer for any and all cases, not just special cases. I think that, if this is possible, it is not a trivial thing to derive the algorithm.

 

[steveB]

Here is just an observation of caution.

We need to be careful when we look at the roots of a polynomial ax^2+bx+c and try to make any conclusion about the factorizing question. Polynomials ax^2+bx+c and x^2+(b/a)x+c/a have exactly the same roots, but they are not the same polynomial. This is why I wanted PG to clarify the exact question.

When we use the roots to say something about d, e, f and g, we need to remember that ...

ax^2+bx+c=(r1 x - r1 x1)(r2 x - r2 x2)

where r1 r2=a and x1 and x2 are the two roots

only when a=1 does ax^2+bx+c=(x-x1)(x-x2)

From this fact we can see that if "a" does not equal 1, then even if the roots are not integers, it is still possible that the actual polynomial specified is still factorable in the "integer-coefficient" way.

 

[MrAl]

Hi Steve,


I think it would be very easy to make an algorithm2 to check to see if a given algorithm1 is correct for integers. That's because we would end up being limited in what the average person can evaluate anyway as far as integers. An example would be an algo2 to check the algo1 that involves the prime number b and a being positive (assuming i have that theory correct for now and those are the two required knowns). That's because the average person would only bother to memorize primes up to maybe 997, and it's not easy to tell if the larger number is prime or not. So this greatly reduces the global numerical space we have to fact check.
I think i can come up with one in about five minutes

 

[steveB]

I think i can come up with one in about five minutes

Are you talking about a general algorithm, or one specific involving prime numbers or other restrictions? I'm not following what you mean by algorithm1 and algorithm2.

I'm talking about a general algorithm, and one for a person to use directly without computer. If you can find a general algorithm in 5 minutes, then this will be the answer PG is looking for, i think.

Without restrictions (other than being integers) what "test" or "algorithm" can we do on a, b and c to know that integer values of d,e,f and g can be found.

 

[The Electrician]

The standard way often taught:

http://www.mathguide.com/lessons/Factoring.html

A bit more to say on the subject:

http://jamesbrennan.org/algebra/polynomials/factoring_by_grouping_.htm

Some trial and error (testing of possible factors of numbers) is inevitable.

 

[MrAl]

Are you talking about a general algorithm, or one specific involving prime numbers or other restrictions? I'm not following what you mean by algorithm1 and algorithm2.

I'm talking about a general algorithm, and one for a person to use directly without computer. If you can find a general algorithm in 5 minutes, then this will be the answer PG is looking for, i think.

Without restrictions (other than being integers) what "test" or "algorithm" can we do on a, b and c to know that integer values of d,e,f and g can be found.

Hi,

I was talking about an algorithm2 that checks algorithm1 to make sure algorithm1 really works. This is where algorithm1 is the one where we determine if it is possible for an integer factorization. Algorithm2 can be on a computer just to make sure algo1 works all the time.

 

[steveB]

Hi,

I was talking about an algorithm2 that checks algorithm1 to make sure algorithm1 really works. This is where algorithm1 is the one where we determine if it is possible for an integer factorization. Algorithm2 can be on a computer just to make sure algo1 works all the time.

OK, so algorithm1 should be a test that gives PG ... " a simple way to tell if a quadratic polynomial is not factorable (in the way defined in posts 6 and 7) over integers by just looking at the coefficients?", based on his question.

I can see what PG is thinking here. If he tries to do such a factorization, and succeeds, then he knows it is possible for the example and he knows the answer. But, what if he fails to find the answer? Then, he would like to know if he should keep searching. Hence, if there is a simple way to tell that it is NOT factorable, then he doesn't waste his time searching.

I still think this is a difficult thing to find, but if you know of a way, please post it, as it will be very interesting to both PG and me.

Let me be more clear about what is needed here, by way of a modified example. What if PG modified the questions and added the constraint that both "a" and "c" are prime numbers? Well, I would submit the following test.

if "b" is not equal to a+b or ab+1, then it is not possible to factor it.

So, for example if i see the polynomial 29x^2+899x+31, then I quickly know that it is not factorable because 29*31+1=900 and 29+31=60. Hence, if "b" is not 900 or 60, it is not possible.

Note that if a and c are very large numbers, knowing they are primes is not necessarily easy. But practically speaking tables of primes are available, so this is a feasible thing for most problems we might run in to.

However, this is a very specific case. To answer PGs questions we must find tests for all other cases as follows.

a, b and c are all not prime numbers
only a is prime
only b is prime
only c is prime
only b and c are prime
only a and b are prime

My rule covers the two cases

a and c are prime
a, b and c are prime

I'm guessing that the case where a b and c are not prime is the hardest case, but it might be possible to break this category down based on other characteristics (e.g. even versus odd integers).

The case where only a is prime can be described by the following rule ...

find all integer permutations of e and g such that c=eg and then check each one to see if b=ag+e. If no valid case can be found, it is not factorable. However, one can already see that this rule, although simple, has already become unwieldy because if c is a large number, we need to find all possible eg factors and test each one. That's fine for a computer, but not for a person. Still, many real examples will be feasible with this rule.

And, I guess we can keep going till we have covered all cases, but I would be curious to see an effective "simple" test for the case where a, b and c are not prime and are reasonably large. If we extend the method above and look for all df permutations that yield a=df, and then proceed to test each case, I feel this is just too complicated and does not meet PG's request.

 

[MrAl]

Hello again,

Anyone that can pick up a calculator can solve this immediately by using the quadratic formula, so i dont see why we just dont do that. If we need to carry around a handbook for mathematics we havent gained much, even if that handbook is in ebook form because then we have to look it up.
We could look for shortcuts all day long, but in the end we'll forget how to apply them. Pull out a calculator, do the math

Another interesting fact:
(R2+R1)/(R1*R2)=-b/c

 

[steveB]

Hello again,

Anyone that can pick up a calculator can solve this immediately by using the quadratic formula, so i dont see why we just dont do that.

Can you explain how to do that? Despite the fact that you think anyone can do it, it's still not clear to me what the method is you are suggesting. Let me give an example to clarify my confusion.

Take the example 31x^2+900x+29. How do you apply the quadratic formula to determine if this is factorable or not? By my method, i note that a and c are prime numbers; hence, if b is 60 or 900, I quickly know it is factorable, as I explained above. In this case b=900, and it is factorable The answer is, of course (31x+1)(x+29)

If i apply the quadratic formula, I will find the roots are -29 and -0.032258064516129. These are not both integers, so there is still more work to be done. So, what are the final steps to determine if this is factorable or not? Once you explain this, PG will have his answer.

 

[MrAl]

Hello Steve,

I think the way this works is if the coefficient of x^2 is 1 then we just find the roots r1 and r2 and the factorization is then:
(x-r1)*(x-r2)

but if the coefficient of x^2 is not 1 then we find two roots r1 and r2 but only one of them is valid, and to get the remaining root we divide c by that root.
So for example, your good example (very happy you brought this up):
31*x^2+900*x+29

we get two roots as you noted, one is very small and one is -29, so we know one factor is:
x-(-29)=x+29

Next we divide c by -29 and we get:
29/-29=-1

so the next factor is:
a*x-(-1)=a*x+1

So the final set would look like this:
(31*x+1)*(x+29)

Unfortunately i cant remember all the details for this method now that you mention it so we should look at this some more. If you'd like to play around with it a little and see if you can find any exceptions we can look at them and see if something is still missing.

I tried another equation with more obscure roots:
x^2+345*x+23

and a direct quadratic formula works there too,

and also with obscure roots:
25*x^2+499*x+12
(x+19.93592286028774)*(25*x+0.60192849280652)
where we can see one of the roots found with the quadratic formula is the one on the left, -19.93592286028774.

I didnt realize that the quadratic formula was going to be such a strong contender as i thought we wanted something we could do quickly without a calculator.

Here's what the 'Law' would read in full:

a*x^2+b*x+c

factors into:
(x-(sqrt(b^2-4*a*c)-b)/(2*a))*(a*x-(2*a*c)/(sqrt(b^2-4*a*c)-b))

(but there may be another solution we need to complete this...we'll have to check that out next)

In Latex for the squeamish:
[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]

and this probably works also:
[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]

or maybe just one or the other, or we may have to adjust the sign of one or two factors (although the sign does seem to be carried by b or c or a).

LATER:
In fact, there may be another simple approach:
For r1 and r2 found using the quadratic formula, one root is valid and the other root is r/a, so one root needs to be multiplied by a. This leads to:
(x-r1)*(a*x-r2*a)
where we might have to try this with roots swapped.

 

[steveB]

I need to go through this carefully. Today the wife and I took our niece by train to New York City and went to the park and zoo. So, I'm just drawing on a napkin and sending this by cell phone.

I think one common thing I see in several examples is that factorable quadratics have integer values of sqrt(b^2-4ac). However, I'm not sure that this is a guarantee, but it is worth checking this out.

I do agree that if a=1 finding roots works. However I don't think that one root is always useful when a is not equal to one.

Here is another test quadratic to consider

6144x^2+3904x+312=(96x+52)(64x+6)

 

[The Electrician]

Here is another test quadratic to consider

6144x^2+3904x+312=(96x+52)(64x+6)

Note that if the coefficients a, b and c have any integer factors in common, the factorization will not be unique:

6144x^2+3904x+312=(96x+52)(64x+6)
6144x^2+3904x+312=(48x+26)(128x+12)
6144x^2+3904x+312=(24x+13)(256x+24)

This common factor may be removed by the method I'm going to describe.

If the quantity [latex]\sqrt{b^2 - 4 a c}}[/latex] is an integer then the quadratic trinomial ax^2+bx+c (where a, b and c are integers) is factorable over the integers.

Evaluate the expressions [latex]\frac { \sqrt{b^2 - 4 a c}-b}{2a}[/latex]

and [latex]\frac {-\sqrt{b^2 - 4 a c}-b}{2a}[/latex]

If the trinomial is factorable over the integers, these two expressions will evaluate to rational numbers.

If two rational numbers are obtained above, they can be represented as e/d and g/f, and if we take (x-e/d) and (x-g/f) as factors, we can multiply those two factors and obtain a monic trinomial with the same roots as our starting trinomial. Then (dx-e)(fx-g) is the desired factorization with any common factor among a, b and c possibly removed.

The common factor (if any) may be given by a/(d*f).

For example, start with [latex]6144x^2+3904x+312[/latex]

The expressions [latex]\frac { \sqrt{b^2 - 4 a c}-b}{2a}[/latex] and [latex]\frac { -\sqrt{b^2 - 4 a c}-b}{2a}[/latex] evaluate to -3/32 and -13/24. Then our factorization (without any common factor among a, b and c) is (32x + 3)(24x + 13). Evaluating a/(d*f) we get 6144/768 = 8, the common factor among a, b and c (the GCD of a,b,c).

We need to multiply our derived factors by 8 to get a factorization of the original trinomial. Since 8 = 2*2*2, we see that the three factors of 8 can be distributed over our two factors (32x + 3) and (24x + 13) in more than one way. With the common factor removed from a, b and c, the factorization is unique.

The reason for the ambiguity about a common factor is that if some of these calculations are done on a calculator such as an HP49G+, the calculator removes common factors from the numerator and denominator of a rational number (fraction).