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 \(x^2+y^2=z!\) and \(2^n-7=x^2\) 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 everyone of us can put some variables together and say, "We have a Diophantine problem like \(a^3+a+1=3^b!\)" 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 \((m, n)\), which make \[\frac{m^3+n^3}{m^2+n^2+mn}\] an integer.
We always start by examining a few trivial cases. Here, let \(m=n\), then the given fraction reduces to \(\frac{2m}{3}\) and it’s obvious that \(m\) must be a multiple of \(3\). The expression is asymmetric, so WLOG suppose that \(m>n\). There is a positive integer \(k\) such that \[m^3+n^3=k(m^2+n^2+mn).\] Let \(d=\gcd(m, n)\), then there are relatively prime numbers \(a\) and \(b\) such that \(m=ad\) and \(n=bd\). We have \(a>b\) and the equation becomes \[d(a^3+b^3)=k(a^2+b^2+ab)\] or \[d(a+b)\big(a^2+b^2-ab\big)=k\big( (a+b)^2-ab\big). \qquad (1)\] 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 \(a\) and \(b\) from \(3\) to \(2\). The LHS of equation \((1)\) is divisible by \(a+b\), and so is the RHS. But note that \[\gcd\big(a+b, (a+b)^2-ab\big)=\gcd\big(a+b, (a+b)^2-(a+b)^2+ab\big)=\gcd(a+b, ab).\] If \(a+b\) and \(ab\) are not relatively prime, there is a prime number \(p\) such that \(p|ab\) and \(p|a+b\). Hence \(p\) divides one of \(a\) or \(b\). For example, if \(p|a\), then \(p|a+b\) forces \(p|b\), which contradicts \(\gcd(a, b)=1\). Hence \(\gcd(a+b, ab)=1\) and consequently \(a+b\) and \((a+b)^2-ab\) are relatively prime. Then, from equation \((1),\) we have \(a+b|k\) and there is a positive integer \(c\) such that \(k=c(a+b),\) and the equation becomes \[d\big(a^2+b^2-ab\big) =c\big( a^2+b^2+ab\big) . \qquad (2)\] It is clear that \(c<d\). Now we can rearrange this equation as a quadratic in \(a:\) \[(d-c)a^2-b(d+c)a+b^2(d-c)=0. \qquad (3)\] The discriminant of this quadratic must be a square and that is \[\Delta =b^2(d+c)^2-4b^2(d-c)^2=b^2\big((d+c)^2-4(d-c)^2\big).\] Therefore, there is a non-negative integer \(e\) such that \((d+c)^2-4(d-c)^2=e^2\). Setting \(e=0\) results in \(a=b\), which is a contradiction. Hence \(e\) is positive and the following equation must be solved: \[(d+c)^2=4(d-c)^2+e^2.\] But this is Pythagorean equation and its solutions for this case are as follows: \[\text{(a)} \begin{cases} d+c&=f\big(p^2+q^2\big) \\ 2(d-c)&=2fpq \\ e&=f\big(p^2-q^2\big) \end{cases}\qquad \text{(b)} \begin{cases} d+c&=f\big(p^2+q^2\big) \\ 2(d-c)&=f\big(p^2-q^2\big) \\ e&=2fpq, \end{cases}\] where positive integers \(p>q\) have different parity and are relatively prime, and \(f\) is an arbitrary positive integer. In case \((a),\) \[\begin{cases} d&=\frac{1}{2}f\big(p^2+q^2+pq\big) \\ c&=\frac{1}{2}f\big(p^2+q^2-pq\big) \\ e&=f\big(p^2-q^2\big), \end{cases}\] and since \(p^2+q^2+pq\) and \( p^2+q^2-pq\) are both odd, we must have \(f=2g\) for a positive integer \(g.\) Thus \[\begin{cases} d&=g(p^2+q^2+pq) \\ c&=g(p^2+q^2-pq) \\ e&=2g(p^2-q^2), \end{cases}\] and from equatin \((3)\) \[a=\frac{b(d+c)+be}{2(d-c)}=b\frac{p}{q}.\] Note that a negative sign of quadratic formula is not acceptable, because it leads to \(a<b\). Hence \(aq=bp,\) and since \(\gcd(a, b)=\gcd(p, q)=1\), we get \(a=p\) and \(b=q\) and finally \[(m, n)=(ad, bd)=\big(gp(p^2+q^2+pq), gq(p^2+q^2+pq)\big).\] In case \((b),\) \[\begin{cases} d&=\frac{1}{4}f(3p^2+q^2) \\ c&=\frac{1}{4}f(p^2+3q^2) \\ e&=2fpq. \end{cases}\] Since \(3p^2+q^2\) and \( p^2+3q^2\) are both odd, we must have \(f=4g\) for a positive integer \(g\), and hence \[\begin{cases} d&=g(3p^2+q^2) \\ c&=g(p^2+3q^2) \\ e&=8gpq. \end{cases}\] We get from equation \((3)\) \[a=\frac{b(d+c)+be}{2(d-c)}=b\frac{p+q}{p-q}.\] Hence \(a(p-q)=b(p+q)\) and since \(\gcd(a, b)=\gcd(p+q, p-q)=1\), we get \(a=p+q\) and \(b=p-q\) and finally \[(m, n)=(ad, bd)=\big(g(p+q)(3p^2+q^2), g(p-q)(3p^2+q^2)\big).\] Therefore, we have three family of solutions in general \[\begin{cases} (m, n)=(3g, 3g) \\ (m, n)=\big(gp(p^2+q^2+pq), gq(p^2+q^2+pq)\big) \\ (m ,n)=\big(g(p+q)(3p^2+q^2), g(p-q)(3p^2+q^2)\big), \end{cases}\] where positive integers \(p>q\) have different parity and are relatively prime, and \(g\) is an arbitrary positive integer. \(_\square\)