General Diophantine Equations - Problem Solving
As you know, a polynomial equation with two or more unknowns, where the unknowns are integers, is called a Diophantine equation. In 1900, David Hilbert proposed his tenth fundamental problem: Find an algorithm to determine whether a given polynomial Diophantine equation with integer coefficients has an integer solution. In 1970, Yuri Matiyasevich proved that such a general algorithm cannot exist. Diophantine equations are equations between polynomials. That is the context of Hilbert's tenth problem and the proof by Matiyasevich et al.
How about factorials and exponentiation? Are equations like and called Diophantine equations? There are different opinions about what a Diophantine equation is. But in a broad sense, operations on integers (or even rationals), in the format of any equation, can be called a Diophantine problem.
Now every one of us can put some variables together and say, "We have a Diophantine problem like " Then probably we waste a lot of time on it, learning a few things, but we cannot solve it. Because there are no routine methods for solving Diophantine problems, and most of them are unsolvable via known methods. If a Diophantine problem is made intelligently (variations of known equations or generalizations of them), working on it can greatly improve our Diophantine problem-solving skills and our knowledge about them. We need to see, seek and solve many problems to be able to make such problems and solve newly introduced ones.
Therefore, when a general Diophantine equation is given, we must return to our gained knowledge from solving previous Diophantine problems and break the problem into smaller parts. Each part can be turned to known equations like Pythagorean, Pell or Mordell; or it can be solved by familiar techniques like divisibility rules, modular arithmetic, completing the square, discriminant of quadratic, factoring, bounding by inequalities, etc. Let’s see some examples:
Determine all pairs of positive integers , which make an integer.
We always start by examining a few trivial cases. Here, let , then the given fraction reduces to and it’s obvious that must be a multiple of . The expression is symmetric, so WLOG suppose that . There is a positive integer such that Let , then there are relatively prime numbers and such that and . We have and the equation becomes or Now I want to use a technique, which is very effective in solving polynomial Diophantine equations and I call it “lowering the degree.” In this method we try to reduce the degree of the main variables of the equation. Here we try to lower degree of and from to . The LHS of equation is divisible by , and so is the RHS. But note that If and are not relatively prime, there is a prime number such that and . Hence divides one of or . For example, if , then forces , which contradicts . Hence and consequently and are relatively prime. Then, from equation we have and there is a positive integer such that and the equation becomes It is clear that . Now we can rearrange this equation as a quadratic in The discriminant of this quadratic must be a square and that is Therefore, there is a non-negative integer such that . Setting results in , which is a contradiction. Hence is positive and the following equation must be solved: But this is Pythagorean equation and its solutions for this case are as follows: where positive integers have different parity and are relatively prime, and is an arbitrary positive integer. In case and since and are both odd, we must have for a positive integer Thus and from equatin Note that a negative sign of quadratic formula is not acceptable, because it leads to . Hence and since , we get and and finally In case Since and are both odd, we must have for a positive integer , and hence We get from equation Hence and since , we get and and finally Therefore, we have three family of solutions in general where positive integers have different parity and are relatively prime, and is an arbitrary positive integer.