Diophantine Equations

What you need to know

• A Diophantine equation asks for integer solutions, often positive ones. That gives an extra tool, divisibility: both sides must have the same factors, the same parity (odd or even), and the same remainders. Example: $2x+4y = 7$ has no integer solutions, since the left side is even and $7$ is odd.
• Simon's Favorite Factoring Trick. Adding $ab$ to both sides turns $xy+ax+by = c$ into $(x+b)(y+a) = c+ab$. Then list the factor pairs of the right side. Example: $xy+2x+3y = 18$ becomes $(x+3)(y+2) = 24$.
• Linear equations. Let $a$, $b$, $c$ be integers and $g = \gcd(a,b)$. Then $ax+by = c$ has integer solutions exactly when $g$ divides $c$. Example: $4x+6y = 9$ has none, because $2$ does not divide $9$.
• All solutions from one. If $(x_0, y_0)$ is one solution, the others are $\left(x_0+\tfrac{b}{g}t,\ y_0-\tfrac{a}{g}t\right)$ for every integer $t$: $x$ moves in steps of $\frac{b}{g}$ while $y$ moves the other way in steps of $\frac{a}{g}$. Example: $3x+5y = 22$ has $(4, 2)$, and also $(9, -1)$, $(-1, 5)$, and so on.
• Difference of squares. $x^2-y^2 = n$ means $(x-y)(x+y) = n$. The two factors are both even or both odd, since they differ by $2y$. Example: for $x^2-y^2 = 15$, the pairs $1\cdot15$ and $3\cdot5$ give $(x,y) = (8,7)$ and $(4,1)$.
• Bounding. If we may assume $x \le y \le z$, the smallest variable can't be too big. Example: in $\frac1x+\frac1y+\frac1z = 1$, the fraction $\frac1x$ is the biggest of the three, so it is at least $\frac13$, which forces $x \le 3$.
• Perfect squares (and other perfect powers) are rare. If $n^2 < k < (n+1)^2$, then $k$ is not a perfect square. Example: for positive $n$, $n^2+n$ is never a square, since $n^2 < n^2+n < (n+1)^2$.

How AMC 10 tests it

• "How many ordered pairs of positive integers satisfy …?" with an $xy$ term plus terms in $x$ and $y$. Use Simon's Favorite Factoring Trick, then count factor pairs (problems 12–20).
• Coin, stamp, or ticket problems: $ax+by = c$ where $x$ and $y$ are zero or positive. Count the solutions, or find the largest or smallest value.
• "For how many $n$ is $\frac{n+k}{n-1}$ (or a similar fraction) an integer?" Rewrite it as $1+\frac{k+1}{n-1}$, so $n-1$ must divide $k+1$, and count divisors.
• Write $N$ as a sum of consecutive integers or a difference of squares; count the ways using factor pairs.
• Late problems (20–25) combine bounding and casework, such as three variables in an equation that stays the same when you swap them.

Standard approaches

1. Get one variable by itself. If it lands in a fraction, the denominator must divide the numerator.
2. Try to factor: Simon's Favorite Factoring Trick, difference of squares, or completing the square in both variables.
3. Limit a variable using the order of the variables or the size of the terms, then try the small cases.
4. Compare remainders of both sides after dividing by a small number (work mod that number). This can rule out solutions or force odd or even.
5. For a linear equation, find one solution, then step by $\frac{b}{g}$ and $\frac{a}{g}$. Count the steps that stay in range.

Worked example

How many ordered pairs of positive integers $(x, y)$ satisfy $xy - 4x - 6y = 6$?

(A) $4$ (B) $6$ (C) $8$ (D) $10$ (E) $16$

Step 1: factor. $(x-6)(y-4)$ multiplies out to $xy-4x-6y+24$. So add $24$ to both sides:
$$(x-6)(y-4) = 30.$$

Step 2: both factors positive. Then $x-6$ can be any of the $8$ positive divisors of $30$: $1, 2, 3, 5, 6, 10, 15, 30$. Each gives positive $x$ and $y$. For example, $x-6 = 1$ and $y-4 = 30$ give $(7, 34)$. Check: $7\cdot34-4\cdot7-6\cdot34 = 238-28-204 = 6$.

Step 3: both factors negative. Since $x \ge 1$ and $y \ge 1$, we have $x-6 \ge -5$ and $y-4 \ge -3$. So if both factors are negative, $x-6$ is between $-5$ and $-1$ and $y-4$ is between $-3$ and $-1$. Their product is at most $5\cdot3 = 15$, less than $30$, so there are no solutions here.

Step 4: total. Only the $8$ pairs from Step 2 work.

The answer is $\boxed{\textbf{(C)}\ 8}$.

Pitfalls

• Forgetting the negative factor pairs, or not checking whether they still give positive values. Example: above, $(-5)\cdot(-6) = 30$ gives $x = 1$ but $y = -2$.
• Dropping the "same parity" rule for $(x-y)(x+y) = n$. If $n$ leaves remainder $2$ when divided by $4$ ($n \equiv 2 \pmod 4$), there are no solutions. Example: $x^2-y^2 = 6$ has none: $1\cdot6$ and $2\cdot3$ each pair an odd factor with an even one.
• Counting unordered pairs when the problem says ordered, or the other way round. Ordered pairs count $(2,5)$ and $(5,2)$ separately.
• Stopping after one solution of a linear equation instead of finding the whole family. Example: $3x+5y = 52$ has three positive solutions: $(4, 8)$, $(9, 5)$, $(14, 2)$.

Traps that recur

• Only using b | 9 and a | 14 (twelve candidate pairs) without checking the full divisibility, or overlooking that 9 must divide 14b^2. (2007 AMC 10B #25)
• Listing c = 1, 10, 19, ..., 91 and then counting the gaps rather than the terms, which gives the 10 in (B). (2025 AMC 10B #23)
• Trying to guess N by testing small products, or accepting the factorization 3 times 43 that leads to N = 0. (2023 AMC 10A #23)
• Mixing pages and sheets (c sheets removed means 2c pages, and the removed pages run from 2b+1 to 2b+2c). (2021 AMC 10A #22)