In this post we take a dive into building a very minimalist toolkit which might be useful for Diophantine Equation problems.

This write-up especially focusses on the easier side of things related to cater Scholarship problems and not Olympiad Problems which may require various additional specialised methods.

We do not illustrate any methods with examples since it is often quite restricting to see a few examples and become limited to one such method, whereas in an exam environment multiple trial with several approaches are almost always necessary.

Methods:⌗

  • $\star$ Parity Case:

  1. Only use parity if it is VERY obvious that some variable is odd or even from the start. Assumptions might lead to false conclusions.

  2. Break into two cases and substitute in the variable with $2x$ or $2x \pm 1$ to see if it gives any clue.

  3. Parity and Sign of R.H.S and L.H.S must remain the same for equality.

$$\dotsb$$

  • Prime Case:
  1. Given equation has some variable as a prime ? Try two cases if the prime equals $2$ or is an odd prime. Is there some important clue that can be obtained from the prime equals $2$ case or the odd prime case ?

$$\dotsb$$

  • Factorization:

  1. Factor the given equation and see if one of the sides can be broken (especially, if it is a constant) to deduce some conclusions.

  2. Sophie Germain Identity: If of the form $a^4 + 4b^4$ then factor as $((a+b)^2 + b^2)((a-b)^2+b^2)$ or the regular version $(a^2 + 2b^2 + 2ab)(a^2 + 2b^2-2ab).$

  3. SFFT : If of the form $xy +x +y$ or $\frac{1}{x} + \frac{1}{y} = \frac{1}{N}$ see - Click Here!

  4. If $a,b,c \in \mathbb{R}$ then $(a+b)(b+c)(c+a) =(a+b+c)(a b+b c+c a)-a b c$

$$\dotsb$$

  • Monotonicity:

  1. Using the fact that $f(x) = x^2$ is monotonous over $\mathbb{Z}^+$, we can deduce things like $a^2 < x < (a+3)^2 \implies x = (a+1)^2$ or $x = (a+2)^2.$ The idea being between two squares, there is another square in between if the original two squares differ by some constant.

  2. There is a $x$ in the power of every constant in the equation ? Take the R.H.S and divide both sides by it, the R.H.S should be $1$ now. Now observe the increasing-decreasing arguments and employ them on this equation to get contradictions or soem useful clue like parity.

  3. Some theorems that are of use if the given equation is assumed to be $f(x)$:

$\qquad$ [I] If the function $y = f(x)$ is continuously increasing or decreasing in set $I$, then the equation $f(x)= 0$ has at most one solution in $I.$

$\qquad$ [II] If the function $y=f(x)$ is increasing (decreasing) over interval $I$, then the function $y=-f(x)$ is decreasing (increasing) on $I$.

$\qquad$ [III] The sum of two increasing functions is an increasing function and the sum of two decreasing functions is a decreasing function.

$\qquad$ [IV] If one of the two functions $f$ and $g$ is increasing and the other is a decreasing function of real variable $x$, then the equation $f(x)=g(x)$ has at most one real zero.

$$\dotsb$$

  • Bounding:

  1. Given equation is symmetric ? Using symmetry (if the equation looks “evenly” divided or, if the equation variables can be rotated and no change occurs) we take a WLOG inequality and then try to bound at least one variabe to generate further cases.

  2. Is the graph simple to visualize ? Try to figure out the graph and extremal points.

  3. Is the maximum and minimum readily available ? Try to use them as bounds

$$\dotsb$$

  • $\star$ Modular Arithmetic:

  1. Need to show that no integer solutions exist ? Modular Arithmetic.

  2. Euler’s Harrow: It can be tricky deciding what modulo to use for unconventional powers hence a useful clue might be using Euler’s Theorem that $a^{\phi(n)} \equiv 1$ $\operatorname{mod} n$ when $\operatorname{gcd}(a,n) = 1$ and working modulo $n$ hereon. Specifically, we check try to find such a $n$ so that Euler’s theorem holds (it makes the RHS under mod $n$ – one) and we do this by first observing the highest power of the given equation (say, $m$) and coming up with $\phi(n) = m.$

  3. Given two equations and both have variables ? Try to write it in the form of a modular equation $f(x) \equiv 0$ $(\operatorname{mod} g(x))$ and try to eliminate the variable and get a constant $k$ to get something like $g(x) \mid k$. This implies $g(x) \leq k$ so we can check finitely many such $k$ that might be valid.

  4. Equation has a square ? Try modulo 3,4,5,8 and 16.

  5. Equation has a cube ? Try modulo 7,9,13.

  6. Squares can only be congruent to 0, 1 or 4 modulo 8.

$$\dotsb$$

  • Quadratic Discriminant:
  1. Given a quadratic and Integer solutions are involved ? Try obtaining the discriminant. Now for integer solutions, the discriminant MUST be perfect square hence we keep chaining discriminants (if the subsequent discriminant is also a quadratic) and lastly assume it to be equal to some $k^2$. In the last step if it happens that with some manipulation the equation is factor-able, and there lies a constant we can check the factors of the constant as such. The last step might vary as it can be that sometimes, instead of factoring we get another quadratic so we take its discriminant and again equate to some $m^2$ and check similarly. Sometimes we might also need modular arithmetic or parity arguments as well.

$$\dotsb$$

  • Variabe Cuts:

  1. Question asks to show infinite number of solutions ? Try reducing the number of variables as much as possible with substitutions (and very rarely, by modular arithmetic) to end up with a dependency on a tertiary variable which can take any value.

  2. Standard substitutions include ($x+s, x, x-s$) or ($x-s,x+s$). The key idea is to cancel out when substituting and if some factorable form is present - then to exploit that.

$$\dotsb$$

  • G.C.D Linking:

  1. This involves the fact that if $\operatorname{gcd}(a,b) = d$ then $a = pd$ and $b = qd$ for some $p,q.$ This susbstitutions might lead to some manage-able divisibility assumptions.

  2. If the gcd happens to be $1$ then a few many clues can be found from the equation by the substitutions.

$$\dotsb$$

For Olympiads:⌗

The listed methods are enough for most questions at the Scholarship level. Olympiad students should look into methods such as Infinite Descent, Zsigmondy’s Theorem, Cyclotomic Recognition and Viete Jumping.

In some instances, more tools like Lifting the Exponent Lemma and p-adic observations are elso employed.

Lastly, it is also advised to add Legendre’s/ de-Polignac Formula and more generally p-adic valuations (2-adic, to be more specific) in the toolkit, they help in some instances as well.

Questions:⌗

1. Show that $$ x^{4}+131 y^{4}=3 z^{4} $$ has no solutions in positive integers.

2. Find all ordered triples of positive integers $(a, b, c)$ such that for all positive integers $t$ $$ \frac{(a t+1)(b t+1)(c t+1)-1}{\operatorname{lcm}(a t, b t, c t)} $$ is also a positive integer.

3. [HMMT Algebra 2005 #2] How many real numbers $x$ are solutions to the following equation? $$ 2003^{x}+2004^{x}=2005^{x} $$

4. Find all triples ($p,x,y$) such that $p^x=y^4+4$, where $p$ is a prime and $x$ and $y$ are natural numbers.

5. Determine all pairs $(m, n)$ of positive integers for which $$ 2^{m}+3^{n} $$ is a perfect square.

6. Show that the equation $$ 5 m^{2}-6 m n+7 n^{2}=1985 $$ has no integer solutions.

7. Show that for natural numbers $x, y, z$ such that $(x, y)=1$ and $x^{2}+y^{2}=z^{4}$, the product $x y$ is always divisible by 7 . Show that this is generally not true without the condition $(x, y)=1$.

Refrences:⌗

[1] Sophie Germain

[2] Problem-Solving Strategies