Competitive Mathematics — Factorization (incomplete)

Note: This article draws heavily on the content from 《数学奥林匹克小丛书》 and incorporates some personal insights and reorganization. Therefore, it can be regarded as a set of notes rather than an entirely original work.

Basics

Definition

The definition of “factorize” is: To write a mathematical object as the product of several factors, and every factor in this expression cannot be further factorized over the specified field.

And we can do the factorization over the rational numbers field, real numbers field, complex numbers field… etc, all in all, it depends on the goals you that want to approach. But in this article, we would mainly discuss the factorization over the integer field, because it’s relatively easy for humans to solve..

Here is some examples of factorizations:

So how can you do the factorizations like above? Don’t worry, that’s what you are going to learn later in this article.

Fundamentals

Before we moving on to the following parts, I think it’s necessary to introduce the basic concepts and the fundamentals of factorizations first…

Please consider this factorization over the real numbers field:

Student A:

Student B:

We can see that student A and B both get the same result, though they are using different approaching methods to factorize.

But here is the question, how can we be sure that even if we use different approaching methods to factorize, we are still going to get the same factorization result?

In other words, is the factorization unique over the real numbers field?

The answer is yes, the factorization over the real numbers field is unique.

And here is a brief informal reasoning which we won’t discuss the details further, because these mathematical concepts are way more beyond the contents that we are focusing on currently.

Based on the fundamental theorem of algebra, its direct inference and the complex conjugate root theorem, we are able to conclude that:

(Assume $P(x)$ and $p(x)$ to be any polynomial of 1 variable $x$ with real coefficients)

1. $\forall \ P(x)$ can always be factorized to the product form of several $p(x)$ of 1st degree and 2nd degree.

2. The factorization of $\forall \ P(x)$ over the real numbers field is unique.

It is essential to understand the two fundamental properties of factorization as we will encounter various factorization problems. Thus, I would like to claim these two conclusions at this point. Please keep them in mind to aid your comprehension of factorization.

Formulas

The listed factorization formulas above are so important that you should master. And all these formulas are easy to prove except the last 2, which requires you to apply the polynomial remainder theorem (which we will discuss later).

Strategies

MUC

Method of undetermined coefficients

It is an approach that does the factorization reversely through assuming the factors expressions and then expand forwardly.

Problem: Please factorize

over the integer numbers field.

First, let’s be clear that when we are talking about the factorization of a polynomial, it means we are trying to find its polynomial factors. So a polynomial won’t have some factors like $(ax^{0.5}+b)$ or $(ax^{-1}+b)$ according to the definition of the polynomial.

If $Ax^2+Bx+C$ can be factored over the integers, it must have 2 factors polynomial of 1st degree in the form of $ax+b$, since it is a 2nd degree polynomial. If it cannot be factored in this way, then it can only have factors of 2nd or higher degree, which would imply that the polynomial cannot be factored over the integer numbers field or even over the real numbers field.

Now, assume $\exists \ a,b,c,d \in \mathbb{Q}, \quad c,d \ne 0$ such that:

Then we have:

Substitute $(1), (3)$ into $(2)$ get:

Now the question has changed to factorize $Ad^2-Bcd+Cc^2$ over the integer numbers field, but it is even more complicated than the original problem $Ax^2+Bx+C$ …

So that indicates, maybe we should change the way we think.

Let’s solve the following problem first.

Problem: Please factorize

over the integer numbers field.

Assume $\exists \ a,b,c,d \in \mathbb{Q}$ such that:

Then we have:

Since attempting to solve the entire system of equations would be difficult, it may be more effective to use a different approach. One possible method is to find integer solutions by substituting numbers into the equations system first… and we luckily got:

Therefore $x^2+x-6=(ax+b)(cx+d)=(x+3)(x-2)$

Now, let’s think about how to make this problem harder by doing some tiny modifications:

Here it is! Then let’s try to solve them.

Problem: Please factorize

over the integer numbers field.

Are you going to apply the previous solving method? Yes, you can, but this time, you’ll definitely need to deal with fractions (because integer $\times$ integer $\ne$ fraction… etc). Since the polynomial in the problem contains fractions, it may be more convenient to eliminate them at first. Therefore, transform:

Then we can focus on solving $x^2+x-6$ first, then times the result with $\dfrac{1}{3}$ . So $\dfrac{x^2}{3}+\dfrac{x}{3}-2=\dfrac{1}{3}(x+3)(x-2)$, accordingly the answer is $\dfrac{x^2}{3}+\dfrac{x}{3}-2$ cannot be factorized over the integer numbers field because its factors contain non-integer coefficients.

Similarly…

Problem: Please factorize

over the integer numbers field.

Using the same approach, we can get the answer: $7x^2+7x-42= 7(x+3)(x-2)$

How about this…

Problem: Please factorize

over the integer numbers field.

We can still apply the MUC for this problem, but please make sure that you set up $(ax+by)(cx+dy)$ instead of some others factors like $(ax+b)(cx+dy^2)$, because that product cannot produce the term of $xy$. Furthermore, it is important to note that any factors polynomials of a polynomial cannot have a degree higher than the degree of the polynomial itself (you can try to prove it using the MUC, it is quite easy).

So the result is: $x^2+xy-6y^2= (x+3y)(x-2y)$

Keep modifying the problem…

Problem: Please factorize

over the integer numbers field.

For this problem, maybe you will not know how to set up the factors with undetermined coefficients unless you saw the process how I derive it. Then what should you do to develop your “MUC” ability effectively? One word, practicing.

For $x^2 – 3xy – 10y^2 + x – 19y – 6$, we can notice that the there are terms of 2nd , 1st and 0 degree, so we should set up the factors polynomials with the max degree of 1st in the form of $(ax+by+c)(dx+ey+f)$ , though you can also try to set up the factors polynomials in the form of $(ax+c)(by+d)$ , this would tell “no solution” instead, and it’s not because $x^2 – 3xy – 10y^2 + x – 19y – 6$ cannot be factorized over the integer numbers fields, it’s due to your wrong factors form setting at the beginning.

Therefore, by processing the right factors form setting, we can get $x^2 – 3xy – 10y^2 + x – 19y – 6 = (x+2y+3)(x-5y-2)$ through testing the integers substitutions finitely.

Problem: Please factorize

over the integer numbers field.

Similarly, we have:

However, through setting up the right form of factors and testing the integers substitutions finitely, we discovered that the problem can only have the answer: $x^2+x-7=x^2+x-7$, because the equations system fails to satisfy all the integer substitution, in other words, this equations system has no integer solutions. However, it can be factorized over the real numbers field:

Method of substitutions

MS is a powerful technique for factorizing polynomials with high degrees. By using MS, we can simplify the original polynomial by reducing its degree or creating the symmetric situation. This approach can greatly simplify the process of factoring complicated polynomials.

Now, let me set up a problem first.

Problem: Please factorize

over the integer numbers field.

Assume $y=x^2$, then

Similarly…

Problem: Please factorize

over the integer numbers field.

Assume $y=x^2+5x-6$, then

What if I expend the question:

Since in this form, the problem won’t provide you any hint to set up the substitution $y=x^2+5x-6$ directly, you need to discover that hidden property yourself instead, but it is very hard to notice that \((x^2+5x-6)^2+5(x^2+5x-6)-6 = x^4+10 x^3+18 x^2-35 x\) reversely… So, is there a better method except MS to solve this problem? Luckily, yes, and we will discuss later.

How about this…

Problem: Please factorize

over the integer numbers field.

Assume $y=x^2+5x-6$, then

Problem: Please prove that the product of (any 4 consecutive positive integers) plus 1 can become a perfect square number.

$\forall \ x \in \mathbb{Z^+}$, we have:

Assume $y=x^2+3x+1$, then we derive the answer

It’s time to explain my motivation:

Our primary goal is to factorize $x(x+1)(x+2)(x+3)+1$ and satisfy

And according to the 2 fundamental properties of factorizations:

1. $\forall \ P(x)$ can always be factorized to the product form of several $p(x)$ of 1st degree and with 2nd degree.

2. The factorization of $\forall \ P(x)$ over the real numbers field is unique.

We know that the polynomial $x(x+1)(x+2)(x+3)+1$ must be factorable over the integer field since this problem is solvable, and also using different approaches won’t affect the result of the factorization over the integer field of this polynomial.

However, expending the polynomial directly may be not a good approach, unless you’ve discovered that there is no other way. So then I have:

But why didn’t I factorize $x(x+1)(x+2)(x+3)$ in this way:

Because $(x^2+3x)(x^2+3x+2)+1$ indicates the hidden identity of $x^2+3x$, and then I could apply the substitution easily to replace $x^2+3x$, but for $(x^2+x)(x^2+5x+6) +1$, you cannot do so.

Then why did I set up $y=x^2+3x+1$ instead of $y=x^2+3x$, though both of them contain $x^2+3x$ ? It is because the former could reveal the hidden symmetry property of $(x^2+3x)(x^2+3x+2)+1$ and then I can naturally apply the formula $(y-1)(y+1)=y^2-1$ and derive the perfect square after adding 1, but the latter cannot.

Problem: Please factorize

over the integer numbers field.

If you know the binomial theorem, you can expand the polynomial $x^4+(x-8)^4=2 x^4-32 x^3+384 x^2-2048 x+4096$ and then do the factorization. However, it is not recommended, want to know why? Here is the answer:

Assume $y=(x-4)$ and $z=y^2$, then we rewrite the express as

When comparing $2z^2+192z+512$ and $2x^4-32x^3+384x^2-2048x+4096$, it is evident that factoring $2z^2+192z+512$ is a much simpler task than factoring the latter polynomial. The reason is because the substitution of $y=(x-4)$ what we were using could reveal the symmetry property of the polynomial and this property can provide a significant advantage in problem-solving, for this problem, it helped us eliminate the odd degree terms and accordingly decrease the complexity of the factorization.

Now, how should we factorize $2z^2+192z+512$ ? Applying MUC? Yes, it is a valid approach, but not efficient enough for this case, we will discuss it later.

Polynomial remainder theorem

Assume $P(x)$ is a polynomial and $\exists \ P(x)=Q(x)D(x)+R(x)$, where $Q(x), D(x), R(x)$ are polynomials and $\deg(P(x))\ge \deg(D(x))\ge\deg(R(x))$ or $\deg(D(x))=\deg(R(x))=0$ (This can be proved by induction). Then $\exists \ P(x)=Q(x)(x-r)+R(x)$, accordingly we have $P(r)=Q(r)\times 0+R(r)=R(r)$ . If $P(r)=R(r)=0$, then $P(x)=Q(x)(x-r)$ . In other words, if $P(r)=0$ , then $(x-r)$ must be one of its factors.

Problem: Please factorize

over the integer numbers field.

Through substituting some small integers, we found that $P(1)=0$ , therefore $(x-1)$ must be one of its factors. Then applying the polynomial division and MUC:

Problem: Please factorize

over the real numbers field.

$2z^2+192z+512=2(z^2+96z+256)$, for this problem, applying the MUC is definitely not a good idea since the coefficients are too large. Besides, substituting random real numbers to test is also not an efficient approach… Therefore, we can try to solve the equation $P(z)=z^2+96z+256=0$ directly to find the $r$ that let $P(r)=0$ through applying the quadratic formula $z=\dfrac{-b\pm \sqrt{b^2-4ac}}{2a}=-48\pm 32\sqrt{2}$ , so the solution is:

It’s time to introduce a corollary of PRT — RRT (Rational Roots Theorem) (it is not hard to prove):

For a polynomial equation $P(x)=\displaystyle \sum_{i=0}^{i=n}\left ( a_{i}x^{i}\right )=0$ with $a_{i}\in \mathbb{Z}$ and $a_{n} \ne 0$ , then every rational solution $x=\dfrac{m}{n}$ which this equation has satisfies: $m$ is the factor of $a_{0}$ and $n$ is the factor of $a_{n}$ .

SYS Polynomials

Symmetric polynomials

Method of observations and transformations

It is generally recommended to avoid immediately applying formulaic solutions without even thinking when encountering a problem, as taking some time to conduct initial observations can often lead to more effective problem-solving outcomes.

If I have a question like factorize $x^2+x-6$ over the integer numbers field, will you consider applying the quadric formula $x=\dfrac{-b \pm \sqrt{b^2-4 a c}}{2 a}$ first?

No (I mean, you can, but, it’s strongly not recommended to do that). Instead, we can do some simple transformations to generate the result easily:

Or for this problem: Factorize $x^2-28x+195$ over the integer numbers field.

Probably this one is not as simple as the previous one, because it contains larger numbers and is not obvious to observe anything… But, really?

As long as you noticed $195=196-1$ and you are familiar with $196=14^2$, then you are able to solve this problem within 10 seconds, look:

Factorize $x^2-28x+195$ over the integer numbers field.

We can also apply the similar method: $0=8\times2a^2-8\times2a^2$

Upon reflection, you may be curious about how I was able to recognize the approach needed to solve these problems. The truth is, I wasn’t born with the knowledge. Rather, I have spent countless hours practicing and mastering various problem-solving techniques, which has allowed me to develop my mathematical intuition. What I want to emphasize is that humans have the ability to cultivate and refine their mathematical intuition (expanding your Maths database) through sufficient training and exposure, because this skill is about memorization and recognition (automatically retrieving or invoking a corresponding frame to solve the problem), etc… Just like developing a specific skill of a neural network through billions of training data… But for humans, the mechanized training process is a tedious and non-efficient process comparatively, since we are not as powerful as computers… However, we still need to practice as long as we aspire to participate in the Mathematical Olympiad or Putnam Maths Competition, these designed competitive mathematics for humans…

So MOT is a purposeful approach that requires your powerful (trained) intuition for mathematics.

Method of trials and errors

Have you ever encountered a math problem that left you stumped, unable to even begin solving it? Chances are, you will at some point. But why does this happen?

In competitive mathematics contests, problem setters strive to challenge well-prepared participants who have practiced typical problems extensively. To accomplish this, they must devise “good problems” that are difficult enough to separate the exceptional from the merely competent. These problems often require discovering a clever trick that is not immediately apparent.

For instance, a problem like $64a^4+1=(64a^4 + 16a^2 +1) – 16a^2$ may have been considered challenging in the past, but it has become too familiar to many participants. Therefore, problem setters must continue to raise the bar by increasing the difficulty of their problems.

However, it’s important to remember that even the most challenging problems in a Mathematics contest are designed to be solved by humans within a limited time frame, so there’s no need to panic. Rest assured, you won’t encounter a problem as difficult as Goldbach’s conjecture, which is a extremely hard question that is yet to be proven, during the contest.

Now, let’s delve into the Method of Trials and Errors (MTE):

This approach is useful when your maths knowledge database is not sufficient to cover the problem directly, and you cannot call any existing methods from your database to solve the problem effectively. In such cases, try MTE. As we’ve mentioned earlier, even the most challenging problems in a Mathematics contest are designed to be solved by humans within a limited time frame. The difficulty of a problem may stem from the fact that you haven’t discovered the clever trick or technique that could solve it easily. It’s possible that a simple transformation to your approach could lead to a sudden insight or revelation from your observations that makes the solution obvious.

Practice

Answers

$$

64a^4+1 =(8^2a^4 + 8\times2a^2 +1) – 8\times2a^2 = (8a^2+1)^2 – (4a)^2=(8a^2-4a+1)(8a^2+4a+1)

$$