Diophantine Equations - Solve by Factoring
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.
Contents
Quadratic Diophantine Equations
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 \((x, y)\) to the equation \( (x+2)(y-3)=6?\)
Now we know that \(x\) and \(y\) are integers. So \( (x+2)\) and \((y-3)\) must be integers that multiply to \(6\), i.e. the two factors must be either \( (1,6), (6,1), (3, 2), (2,3), (-1,-6), (-6,-1), (-3,-2)\) or \( (-2,-3) \). This implies that we have the following eight possible systems of linear equations:
\[\begin{align} x+2 &= 1, & y-3&= 6 &\qquad (1) \\ x+2 &=6, & y-3&=1 &\qquad (2) \\ x+2 &= 3, & y-3&= 2 &\qquad (3)\\ x+2 &= 2, & y-3 &= 3 &\qquad (4)\\ x+2 &= -1, & y-3&= -6 &\qquad (5) \\ x+2 &=-6, & y-3&=-1 &\qquad (6) \\ x+2 &= -3, & y-3&= -2 &\qquad (7)\\ x+2 &= -2, & y-3 &= -3. &\qquad (8) \end{align}\]
Thus, the ordered pairs of integers \( (x,y)\) satisfying the given equation are
\[(-1,9), (4,4), (1,5), (0,6) , (-3, -3), (-8, -2), (-5, 1), (-4, 0). \ _\square \]
This is a very powerful tool and can sometimes solve seemingly impossible problems.
How many positive integers \(x\) are there such that both \(x\) and \(x+99\) 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 \(x=r^2\) and \(x+99= m^2\), then \( r^2 +99 = m^2\). Subtracting \(r^2\) from both sides of the equation yields
\[\begin{align} m^2 - r^2 &= 99\\ (m+r)(m-r)&= 99. \end{align}\]
As we did previously, we will consider the factors of \(99\), which are \( (1,99), (9,11)\) and \((3,33)\). In other words, we have the following six pairs of linear equations:
\[\begin{align} m+r&=1, & m-r&=99 &\qquad (1) \\ m+r&=99, & m-r&=1 &\qquad (2) \\ m+r&=9, & m-r&= 11 &\qquad (3) \\ m+r&=11, & m-r&=9 &\qquad (4) \\ m+r&=3, & m-r&=33 &\qquad (5) \\ m+r&= 33, & m-r&=3. &\qquad (6) \end{align}\]
The respective solutions to these systems of linear equations are
\[\begin{align} m&=50, & r&=-49 &\qquad (1)' \\ m&=50, & r&=49 &\qquad (2)' \\ m&=10, & r&= -1 &\qquad (3)' \\ m&=10, & r&=1 &\qquad (4)' \\ m&=18, & r&=-15 &\qquad (5)' \\ m&= 18, & r&=15. &\qquad (6)' \end{align}\]
Then since \(x=r^2\), there are three such \(x\)'s that satisfy the condition:
\[\begin{align} (-1)^2=1^2&=1 \\ (-15)^2=15^2&=225 \\ (-49)^2=49^2&=2401. \ _\square \end{align}\]
Note: The corresponding \(m^2=r^2+99\) are
\[\begin{align} 1+99=100&=10^2 \\ 225+99=324&=18^2 \\ 2401+99=2500&=50^2. \end{align}\]
Solving by Simon's Favorite Factoring Trick
Simon's favorite factoring trick (SFFT), also called completing the rectangle, is a simple but clever factorization of the expressions of the form \(xy+xn+ym+mn,\) where \(x\) and \(y\) are variables (usually integer variables), and \(m\) and \(n\) are integers.
Notice that this can be factorized as
\[xy+xn+ym+mn=x(y+n)+m(y+n)=(x+m)(y+n).\]
Two special cases (and very common) are when \((m,n)=(1,1)\) and \((m,n)=(-1,-1)\). That is,
\[xy+x+y+1=(x+1)(y+1), \quad xy-x-y+1=(x-1)(y-1).\]
Although a basic and easy-to-remember fact, this technique is often useful in solving Diophantine equations.
Find all integral solutions to the equation \(xy+9(x+y)=86\).
Notice the equation can be rewritten as \(xy+9x+9y+81=167\). Now \(167\) is a prime and the left side can be easily factorized by SFFT as \((x+9)(y+9)\). Now since
\[(x+9)(y+9) = 1\times 167 =167\times 1=(-1)\times (-167)=(-167)\times (-1),\]
we get four solutions
\[(x,y)=(-8,158),(158,-8),(-10,-176),(-176,-10). \ _\square\]
Find all integral solutions to the equation \(2b+3c=5bc\).
Perhaps you hoped to write \(5bc-2b-3c\) in the form
\[5bc-2b-3c=(5b+*)(c+*)+*,\]
or something similar, where each \(*\) represents an integer. Unfortunately, this is not possible. The \(5\) gets in the way. We can remove this difficulty by multiplying the whole expression by 5 to get
\[\begin{align} 25bc-10b-15c&=0\\ 25bc-10b-15c+6&=6\\ (5b-3)(5c-2)&=6. \end{align}\]
It only remains to check the pairs of integers that multiply to give 6. We check each of
\[(5b-3, 5c-2) = (-6, -1), (-3, -2), (-2, -3), (-1, -6), (1, 6), (2, 3), (3, 2), (6, 1).\]
Of these, only \((-3, -2)\) and \((2, 3)\) result in \(b\) and \(c\) being integers. These pairs correspond to the solutions \((b, c) = (0, 0)\) or \((b, c) = (1, 1)\). \(_\square\)
This technique was first introduced by AoPS user Simon Rubinstein-Salzedo. That is why it is referenced to as "Simon's Favorite Factoring Trick."
General Diophantine Equations
Find the number of ordered pairs of positive integer solutions \((x, y)\) to \(xy=60\).
Notice that \(x\) is a positive divisor of \(60\), and for every \(x\), there is a unique \(y=\frac{60}{x}\). So the number of ordered pairs of positive integers \((x, y)\) that satisfy our equation is simply equal to the number of positive divisors of \(60\).
Since \(60=2^2\cdot 3\cdot 5\), from the divisor function, \(60\) has \((2+1)(1+1)(1+1)=12\) positive divisors.
Hence, \(12\) is the answer to our question. \(_\square\)
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 \(f(x_1, x_2, x_3, \cdots x_n)=0\) and you are able to factor and rewrite it in the equivalent form
\[f_1(x_1, x_2, x_3, \ldots, x_n) f_2(x_1, x_2, x_3, \ldots, x_n)\cdots f_k(x_1, x_2, x_3, \ldots, x_n)=c,\]
where \(c\) is an integer, all you have to do is to consider the divisors of \(c\) 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 \(x-y^4=4\), where \(x\) 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
\[x=y^4+4=(y^2)^2+2^2=(y^2+2)^2-2\cdot y^2\cdot 2=(y^2+2)^2-(2y)^2.\]
Now using the difference-of-squares identity, we can factorize the right hand side completely:
\[x=(y^2+2y+2)(y^2-2y+2)=\big((y+1)^2+1\big)\big((y-1)^2+1\big).\]
Now how does this help us?
Remember that \(x\) is a prime number. So if \(x\) can be expressed as the product of two numbers, one of them has to be equal to \(1\). Fortunately, the way we have expressed the right-hand side immediately tells us that if \(|y|\neq1\), then \(x\) will be the product of two integers greater than \(1\), which cannot be a prime.
So, the only possible values of \(y\) are \(1\) and \(-1\). If we plug these in our equation, we get \(x=5\). That means the only solutions to this are \((5, 1)\) and \((5, -1)\). \(_\square\)
Tip: \(a^4+4b^4\) can be factorized as \((a^2-2ab+2b^2)(a^2+2ab+2b^2)\), known as the Sophie Germain identity.
Let's take a look at another example.
Find the number of ordered pairs of integers \((a, b)\) that satisfy \(\frac{1}{a}+\frac{1}{b}=\frac{1}{n},\) where \(n\) is a fixed integer.
The first natural response is clearing the denominators. Let's do that, and we get
\[ab-an-bn=0.\]
Let's try to factorize it and see what happens:
\[a(b-n)-bn=0.\]
If only we had another \(n^2\) term... Wait! If we want an \(n^2\) term, why not introduce it? Then we'll have something like
\[a(b-n)-bn+n^2=n^2.\]
Now we can factor it as follows:
\[a(b-n)-n(b-n)=(a-n)(b-n)=n^2. \qquad (1)\]
This means \((a-n)\) is a divisor of \(n^2\). 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 \(\tau(n^2)\) be the number of positive divisors of \(n^2\). So the total number of divisors (positive and negative) of \(n^2\) is equal to \(2\tau(n^2)\). This should be the answer to our question, right? Wait! Notice that \((0, 0)\) satisfies \((1)\), but does not satisfy the original equation. So we have to subtract this from our count.
Therefore, our final count is \(2\tau(n^2)-1\). \(_\square\)