Skip to content
Number Theory · Chapter 26

Diophantine Equations

Equations where only whole-number answers count: factor them, bound them, or take a mod to prove that no solution can exist.

You'll need
open on YouTube
26.00%

Strategies for Integer Equations

In this section you will be able to solve equations in integers by factoring, bounding and taking mods, and prove when no solution exists.

A right triangle has legs aa and bb and hypotenuse b+1b + 1. Then a2=2b+1a^2 = 2b + 1, so any odd aa works. With b<100b < 100, how many are there?

A Diophantine equation only allows whole-number answers. That restriction is a weapon: integers factor, they have remainders, and they can’t hide between two consecutive values.

Three moves solve most contest problems. Factor (SFFT, difference of squares) and list the factor pairs. Bound the variables so only a few cases are left. Take a mod to show some cases are impossible.

Look:

A square is always 00 or 11 mod 44. So x2+y2=2023x^2 + y^2 = 2023 has no solutions: 20232023 leaves remainder 33.

Exploreplay first, formulas later

Fourth powers mod 16 can only leave {0, 1}

power k4
mod m16

Fourth powers mod 16 can only leave

  • 0 ✓
  • 1 ✓
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

14 residues never show up.

{0, 1}

Fourth powers mod 16 leave {0, 1}

Name it

Definition 26.0.1 · Diophantine Equation

A Diophantine equation is a polynomial equation where we only look for integer solutions (every variable must be an integer).

Concept 26.0.2 · Strategies to Solve Diophantine Equations

Here are some ideas for solving Diophantine equations.

  • Take mods of different numbers. This is useful when you want to
    1. show there are no solutions, or
    2. show the solutions must be of a specific type.
  • Bound the possible values of different terms. This helps when there are only finitely many solutions.
  • Factor, using the factorizations from the algebra chapters (SFFT, difference of squares, sums and differences of cubes), to find all the solutions.
  • Substitute to simplify the equation.
  • Look for what must be a multiple or divisor of your variables, and rewrite the equation with that. For example, if aa is a multiple of 66, substitute a=6ka = 6k.

Watch itpredict, then reveal

Example 26.1

AMC 10

How many right triangles have integer leg lengths aa and bb and a hypotenuse of length b+1b + 1, where b<100b < 100?

  1. 1

    Write the Pythagorean theorem and expand (b+1)2(b + 1)^2. What is a2a^2 in terms of bb?

    Predict first:
open on YouTube

Example 26.2

AIME

There exist unique positive integers xx and yy that satisfy the equation x2+84x+2008=y2x^2 + 84x + 2008 = y^2. Find x+yx + y.

Factor pairs and SFFT (its total is revealed at the end of the example)

shift of y0
shift of x42
right side244
y2−(x+42)2=244y^2 - (x + 42)^2 = 244

y^2 − (x + 42)^2 = 244. Factor the left side as a difference of squares.

  1. 1

    Complete the square: x2+84x+□=(x+42)2x^2 + 84x + \square = (x + 42)^2. What goes in the box?

    Predict first:
open on YouTube

Example 26.3

AIME

Assume that aa, bb, cc, and dd are positive integers such that a5=b4a^5 = b^4, c3=d2c^3 = d^2, and c−a=19c - a = 19. Determine d−bd - b.

  1. 1

    a5=b4a^5 = b^4. Every prime exponent in a5a^5 must be a multiple of 44, so aa is a perfect fourth power: a=t4a = t^4. Then b=?b = ?

    Predict first:
open on YouTube

Try it

Problem 26.1.1

AMC 12

Integers xx and yy with x>y>0x > y > 0 satisfy x+y+xy=80x + y + xy = 80. What is xx?

Problem 26.1.2

AMC 10

How many ordered pairs of integers (x,y)(x, y) satisfy the equation

x2020+y2=2y?x^{2020} + y^2 = 2y?

Problem 26.1.9

AIME

This problem also appears in the book as 21.3.17.

There is a prime number pp such that 16p+116p + 1 is the cube of a positive integer. Find pp.

Contest cornerreal contest problems

Problem 26.1.4

AIME

Find 3x2y23x^2y^2 if xx and yy are integers such that y2+3x2y2=30x2+517y^2 + 3x^2y^2 = 30x^2 + 517.

Problem 26.1.5

AMC 10

If the positive integer cc has positive integer divisors aa and bb with c=abc = ab, then aa and bb are said to be complementary divisors of cc. Suppose that NN is a positive integer that has one complementary pair of divisors that differ by 2020 and another pair of complementary divisors that differ by 2323. What is the sum of the digits of NN?

Problem 26.1.6

AMC 10

How many ordered pairs of integers (m,n)(m, n) satisfy the equation m2+mn+n2=m2n2m^2 + mn + n^2 = m^2n^2?

Problem 26.1.10

USAMO

Determine all non-negative integral solutions (n1,n2,…,n14)(n_1, n_2, \dots, n_{14}) if any, apart from permutations, of the Diophantine Equation

n14+n24+⋯+n144=1599.n_1^4 + n_2^4 + \cdots + n_{14}^4 = 1599.
Click a choice or type its letter (A–E).

Problem 26.1.16(additional)

AMC 10

Two farmers agree that pigs are worth 300300 dollars and that goats are worth 210210 dollars. When one farmer owes the other money, he pays the debt in pigs or goats, with "change" received in the form of goats or pigs as necessary. (For example, a 390390 dollar debt could be paid with two pigs, with one goat received in change.) What is the amount of the smallest positive debt that can be resolved in this way?

Steps 300 and 210: x·300 + y·210 reaches exactly the multiples of gcd = 30

−900−600−30003006009003900
0·300 + 0·210 = 0

Target 390: can you land on it?

The token is at 0·300 + 0·210 = 0. Target 390: can you land on it?

Checkpoint for section 26.0

Get 2 of 3 right to master this section. One try each, no hints.
1

How many ordered pairs of positive integers (x,y)(x, y) satisfy xy+x+y=35xy + x + y = 35?

2

Which remainders can a perfect square leave when divided by 44?

Click a choice or type its letter (A–E).
3

How many ordered pairs of positive integers (x,y)(x, y) satisfy x2−y2=15x^2 - y^2 = 15?

26.1

Practice Problems

In this section you will be able to combine factoring, bounding and mods on harder integer equations.

Time to mix the strategies. Each problem below hides an integer equation: find it, then factor, bound or take a mod. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Mixed practice

Problem 26.1.3

AMC 10

Let aa and bb be relatively prime positive integers with a>b>0a > b > 0 and a3−b3(a−b)3=733\dfrac{a^3 - b^3}{(a - b)^3} = \dfrac{73}{3}. What is a−ba - b?

Problem 26.1.12

AMC 12

Two distinct numbers are selected from the set {1,2,3,4,…,36,37}\{1, 2, 3, 4, \dots, 36, 37\} so that the sum of the remaining 3535 numbers is the product of these two numbers. What is the difference of these two numbers?

Problem 26.1.17(additional)

AHSME

How many triples (a,b,c)(a, b, c) of positive integers satisfy the simultaneous equations

ab+bc=44ab + bc = 44
ac+bc=23?ac + bc = 23?

Contest cornerreal contest problems

Problem 26.1.7

AMC 10

An arithmetic sequence (of positive integers) has n≥3n \ge 3 terms, initial term aa and common difference d>1d > 1. Carl wrote down all the terms in this sequence correctly except for one term which was off by 11. The sum of the terms was 222222. What was a+d+na + d + n?

Problem 26.1.8

AMC 12

How many ordered pairs of positive integers (b,c)(b, c) exist where both x2+bx+c=0x^2 + bx + c = 0 and x2+cx+b=0x^2 + cx + b = 0 do not have distinct, real solutions?

Problem 26.1.11

AMC 10A

A four-term sequence is formed by adding each term of a four-term arithmetic sequence of positive integers to the corresponding term of a four-term geometric sequence of positive integers. The first three terms of the resulting four-term sequence are 5757, 6060, and 9191. What is the fourth term of this sequence?

Click a choice or type its letter (A–E).

Problem 26.1.13

AMC 12

There is a unique ordered triple (a,k,m)(a, k, m) of nonnegative integers such that

4a+4a+k+4a+2k+⋯+4a+mk2a+2a+k+2a+2k+⋯+2a+mk=964.\frac{4^a + 4^{a+k} + 4^{a+2k} + \cdots + 4^{a+mk}}{2^a + 2^{a+k} + 2^{a+2k} + \cdots + 2^{a+mk}} = 964.

What is a+k+ma + k + m?

Problem 26.1.14

AMC 10/12

A rectangular grid of squares has 141141 rows and 9191 columns. Each square has room for two numbers. Horace and Vera each fill in the grid by putting the numbers from 11 through 141×91=12,831141 \times 91 = 12{,}831 into the squares. Horace fills the grid horizontally: he puts 11 through 9191 in order from left to right into row 11, puts 9292 through 182182 into row 22 in order from left to right, and continues similarly through row 141141. Vera fills the grid vertically: she puts 11 through 141141 in order from top to bottom into column 11, then 142142 through 282282 into column 22 in order from top to bottom, and continues similarly through column 9191. How many squares get two copies of the same number?

Problem 26.1.15

AMC 10

Hiram's algebra notes are 5050 pages long and are printed on 2525 sheets of paper; the first sheet contains pages 11 and 22, the second sheet contains pages 33 and 44, and so on. One day he leaves his notes on the table before leaving for lunch, and his roommate decides to borrow some pages from the middle of the notes. When Hiram comes back, he discovers that his roommate has taken a consecutive set of sheets from the notes and that the average (mean) of the page numbers on all remaining sheets is exactly 1919. How many sheets were borrowed?

Problem 26.1.18(additional)

AIME

One of Euler's conjectures was disproved in the 1960s by three American mathematicians when they showed there was a positive integer such that

1335+1105+845+275=n5.133^5 + 110^5 + 84^5 + 27^5 = n^5.

Find the value of nn.

Fifth powers mod 10 can only leave {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

power k5
mod m10

Fifth powers mod 10 can only leave

  • 0 ✓
  • 1 ✓
  • 2 ✓
  • 3 ✓
  • 4 ✓
  • 5 ✓
  • 6 ✓
  • 7 ✓
  • 8 ✓
  • 9 ✓
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Fifth powers mod 10 leave {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

Problem 26.1.19(additional)

AIMEChallenge

Find the largest possible value of kk for which 3113^{11} is expressible as the sum of kk consecutive positive integers.

Problem 26.1.20(additional)

AIMEChallenge

For some integer mm, the polynomial x3−2011x+mx^3 - 2011x + m has the three integer roots aa, bb, and cc. Find ∣a∣+∣b∣+∣c∣|a| + |b| + |c|.

Problem 26.1.21(additional)

AMC 12Challenge

Let m≥5m \ge 5 be an odd integer, and let D(m)D(m) denote the number of quadruples (a1,a2,a3,a4)(a_1, a_2, a_3, a_4) of distinct integers with 1≤ai≤m1 \le a_i \le m for all ii such that mm divides a1+a2+a3+a4a_1 + a_2 + a_3 + a_4. There is a polynomial

q(x)=c3x3+c2x2+c1x+c0q(x) = c_3x^3 + c_2x^2 + c_1x + c_0

such that D(m)=q(m)D(m) = q(m) for all odd integers m≥5m \ge 5. What is c1c_1?