Chapter

Diophantine Equations

Integer solutions, linear Diophantine equations, factorisation, modular obstructions, and positivity constraints.

Back to Course Practice Ladders
Theory Examples Practice Ladders

Theory

1. What Is a Diophantine Equation?

A Diophantine equation is an equation where the required solutions are integers, or sometimes positive integers. For example,

\[ 3x+5y=17 \]

is not just an equation in real numbers. In number theory, we ask for integer pairs \((x,y)\).

2. Linear Diophantine Equations

The equation

\[ ax+by=c \]

has integer solutions if and only if

\[ \gcd(a,b)\mid c. \]

This condition is necessary because every common divisor of \(a\) and \(b\) divides \(ax+by\). It is also sufficient because the Euclidean algorithm can write \(\gcd(a,b)\) as a linear combination of \(a\) and \(b\).

3. General Solutions

If \((x_0,y_0)\) is one solution of \(ax+by=c\), and \(g=\gcd(a,b)\), then all integer solutions are

\[ x=x_0+\frac{b}{g}t,\qquad y=y_0-\frac{a}{g}t, \]

where \(t\) is an integer.

4. Factorisation Method

Many Diophantine equations become easier after factorisation:

\[ xy+x+y=11 \]

can be rewritten as

\[ (x+1)(y+1)=12. \]

Then integer factors of \(12\) give the solutions.

5. Modular Obstructions

Sometimes an equation has no integer solutions because of remainders. For example, \(x^2=3y+2\) has no solution if \(x^2\) cannot be congruent to \(2\pmod3\). Modular arithmetic can prove impossibility quickly.

6. Nonnegative and Positive Solutions

Olympiad problems often ask for positive or nonnegative solutions. After finding a parametric form, the inequalities restrict the parameter.

Examples

Example 1. Integer Solution Check

This is the first obstruction: the GCD must divide the constant.

Problem. Decide whether \(6x+10y=15\) has integer solutions.
Solution. \(\gcd(6,10)=2\). The left side is always even, but \(15\) is odd. Therefore there are no integer solutions.

Example 2. One Bezout Solution

Connect directly to the Euclidean algorithm from Module 2.

Problem. Find one integer solution of \(3x+5y=1\).
Solution. Since \(2\cdot3-1\cdot5=1\), one solution is \((x,y)=(2,-1)\).

Example 3. All Linear Solutions

Stress that the parameter moves along the line without changing the value.

Problem. Find all integer solutions of \(3x+5y=17\).
Solution. One solution is \((4,1)\), because \(3\cdot4+5\cdot1=17\). Since \(\gcd(3,5)=1\), all solutions are \(x=4+5t\), \(y=1-3t\), where \(t\in\mathbb Z\).

Example 4. A Factor Pair Equation

Factor-pair problems train completeness.

Problem. Solve \(xy=18\) in positive integers.
Solution. The positive factor pairs are \((1,18),(2,9),(3,6),(6,3),(9,2),(18,1)\).

Example 5. Complete the Product

This is a central olympiad factorisation trick.

Problem. Solve \(xy+x+y=11\) in positive integers.
Solution. We rewrite as \((x+1)(y+1)=12\). Since \(x,y>0\), both factors are at least \(2\). The factor pairs are \((2,6),(3,4),(4,3),(6,2)\), giving \((x,y)=(1,5),(2,3),(3,2),(5,1)\).

Example 6. Difference of Squares

Watch for missing negative factor pairs.

Problem. Find all integer solutions of \(x^2-y^2=15\).
Solution. Let \(a=x-y\), \(b=x+y\). Then \(ab=15\), and \(a,b\) have the same parity. Since \(15\) is odd, factor pairs are odd: \((1,15),(3,5),(5,3),(15,1)\) and their negatives. From \(x=(a+b)/2\), \(y=(b-a)/2\), we get \((8,7),(4,1),(4,-1),(8,-7)\) and the four corresponding negative pairs \((-8,-7),(-4,-1),(-4,1),(-8,7)\).

Example 7. Modulo Obstruction

This problem links Module 4 to Diophantine equations.

Problem. Prove that \(x^2+y^2=4z+3\) has no integer solutions.
Solution. Squares are \(0\) or \(1\pmod4\). Therefore \(x^2+y^2\) can be \(0,1,\) or \(2\pmod4\), but \(4z+3\equiv3\pmod4\). Contradiction.

Example 8. A Product Plus Sum

Students may need help choosing the shifted factors.

Problem. Find all integer solutions of \(xy-2x+3y=7\).
Solution. We have \((x+3)(y-2)=xy-2x+3y-6\). Since \(xy-2x+3y=7\), this gives \((x+3)(y-2)=1\). Thus \((x+3,y-2)=(1,1)\) or \((-1,-1)\). The solutions are \((-2,3)\) and \((-4,1)\).

Problems

Problems

No published problems are available yet.

Ladders

No published ladders were found.
Previous Chapter
Next Chapter