Factoring is a very powerful tool while solving Diophantine equations. Sometimes factoring can crack a Diophantine equation wide open. Instead of talking about how good and powerful it is, let's see a demonstration of how factoring can help solving certain Diophantine equations. We're going to start off with quadratic equations, which we already know how to factorize.
This is just a fancy way of considering the factors of a particular number in order to find the integer solutions to an equation.
What are the integer solutions to the equation
Now we know that and are integers. So and must be integers that multiply to , i.e. the two factors must be either or . This implies that we have the following eight possible systems of linear equations:
Thus, the ordered pairs of integers satisfying the given equation are
This is a very powerful tool and can sometimes solve seemingly impossible problems.
How many positive integers are there such that both and are perfect squares?
This problem does not require the solutions but only the number of solutions. However, for the sake of explanation, I will find them.
Let's start by the obvious: let and , then . Subtracting from both sides of the equation yields
As we did previously, we will consider the factors of , which are and . In other words, we have the following six pairs of linear equations:
The respective solutions to these systems of linear equations are
Then since , there are three such 's that satisfy the condition:
Note: The corresponding are
Simon's favorite factoring trick (SFFT), also called completing the rectangle, is a simple but clever factorization of the expressions of the form where and are variables (usually integer variables), and and are integers.
Notice that this can be factorized as
Two special cases (and very common) are when and . That is,
Although a basic and easy-to-remember fact, this technique is often useful in solving Diophantine equations.
Find all integral solutions to the equation .
Notice the equation can be rewritten as . Now is a prime and the left side can be easily factorized by SFFT as . Now since
we get four solutions
Find all integral solutions to the equation .
Perhaps you hoped to write in the form
or something similar, where each represents an integer. Unfortunately, this is not possible. The gets in the way. We can remove this difficulty by multiplying the whole expression by 5 to get
It only remains to check the pairs of integers that multiply to give 6. We check each of
Of these, only and result in and being integers. These pairs correspond to the solutions or .
This technique was first introduced by AoPS user Simon Rubinstein-Salzedo. That is why it is referenced to as "Simon's Favorite Factoring Trick."
Find the number of ordered pairs of positive integer solutions to .
Notice that is a positive divisor of , and for every , there is a unique . So the number of ordered pairs of positive integers that satisfy our equation is simply equal to the number of positive divisors of .
Since , from the divisor function, has positive divisors.
Hence, is the answer to our question.
See how easy that was? Even though it was really easy, this problem demonstrates the motivation behind factoring when you're solving Diophantine equations.
If you have a Diophantine equation and you are able to factor and rewrite it in the equivalent form
where is an integer, all you have to do is to consider the divisors of and check cases.
Sometimes there are a lot of cases to check and you can do certain things to reduce the amount of casework.
That's basically the gist of factoring. Rewrite the original equation in such a way that on one side you have an integer and on the other side you have a product of terms. This will help you solve a lot of Diophantine equations.
The factoring technique is best understood with lots of examples. So on to some examples!
Solve the Diophantine equation , where is a prime.
Since we were talking about factoring, let's see if there's any way to rearrange the terms and factor this.
Rearranging gives us
Now using the difference-of-squares identity, we can factorize the right hand side completely:
Now how does this help us?
Remember that is a prime number. So if can be expressed as the product of two numbers, one of them has to be equal to . Fortunately, the way we have expressed the right-hand side immediately tells us that if , then will be the product of two integers greater than , which cannot be a prime.
So, the only possible values of are and . If we plug these in our equation, we get . That means the only solutions to this are and .
Tip: can be factorized as , known as the Sophie Germain identity.
Let's take a look at another example.
Find the number of ordered pairs of integers that satisfy where is a fixed integer.
The first natural response is clearing the denominators. Let's do that, and we get
Let's try to factorize it and see what happens:
If only we had another term... Wait! If we want an term, why not introduce it? Then we'll have something like
Now we can factor it as follows:
This means is a divisor of . Remember the first problem? This is very similar to that one now. But now we have to deal with the negative divisors as well. This actually makes our jobs easier.
Let be the number of positive divisors of . So the total number of divisors (positive and negative) of is equal to . This should be the answer to our question, right? Wait! Notice that satisfies , but does not satisfy the original equation. So we have to subtract this from our count.
Therefore, our final count is .