AMC 10 Step by Step

Topics / Number Theory

Diophantine Equations

Integer solutions of equations, bounding, factoring integer equations

27
primary-topic problems (2.1% of all)
26
more as a secondary topic
Where it appears
3
P1-10
10
P11-15
1
P16-20
13
P21-25

What you need to know

  • A Diophantine equation asks for integer (often positive integer) solutions. The key extra tool is divisibility: both sides must have the same factors, parity, and residues.
  • Simon's Favorite Factoring Trick: xy+ax+by=cxy + ax + by = c becomes (x+b)(y+a)=c+ab(x + b)(y + a) = c + ab; then list factor pairs of the right side.
  • Linear equations ax+by=cax + by = c have integer solutions iff gcd(a,b)c\gcd(a,b) \mid c; once one solution (x0,y0)(x_0, y_0) is found, all others are (x0+bgt, y0agt)\left(x_0 + \tfrac{b}{g}t,\ y_0 - \tfrac{a}{g}t\right).
  • Difference of squares: x2y2=nx^2 - y^2 = n means (xy)(x+y)=n(x-y)(x+y) = n with both factors of the same parity.
  • Bounding: if the variables are ordered (xyzx \le y \le z), the smallest one is bounded, e.g., 1x+1y+1z=1\frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1 forces x3x \le 3.
  • Perfect powers are rare: n2<k<(n+1)2n^2 < k < (n+1)^2 means kk is not a square.

How AMC 10 tests it

  • "How many ordered pairs of positive integers satisfy ...?" with a product-plus-linear-terms equation: SFFT, then count factor pairs (problems 12–20).
  • Coin, stamp, or ticket problems: ax+by=cax + by = c with nonnegative integers; count solutions or find a maximum/minimum.
  • "For how many nn is n+kn1\frac{n + k}{n - 1} (or a similar fraction) an integer?" Rewrite as 1+k+1n11 + \frac{k+1}{n-1} and count divisors.
  • Express NN as a sum of consecutive integers or as a difference of squares; count representations via factor pairs.
  • Late problems (20–25) combine bounding and casework: three variables with a symmetric constraint.

Standard approaches

  1. Isolate one variable; if it appears as a fraction, demand the denominator divide the numerator.
  2. Try to factor: SFFT, difference of squares, or completing the square on both variables.
  3. Bound a variable using ordering or size, then run small cases.
  4. Take the equation modulo a small number to rule out solutions or force parity.
  5. For linear equations, find one solution and step by b/gb/g and a/ga/g; count how many steps stay in range.

Worked example

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

(A) 44 (B) 66 (C) 88 (D) 1010 (E) 1616

Add 2424 to both sides: xy4x6y+24=30xy - 4x - 6y + 24 = 30, which factors as (x6)(y4)=30(x - 6)(y - 4) = 30. Both factors are integers with product 3030. If both are positive, x6x - 6 can be any of the 88 divisors 1,2,3,5,6,10,15,301, 2, 3, 5, 6, 10, 15, 30, each giving positive xx and yy; for example x6=1x - 6 = 1 gives (7,34)(7, 34). If both are negative, we need x65x - 6 \ge -5 and y43y - 4 \ge -3, so x65|x - 6| \le 5 and y43|y - 4| \le 3, and their product is at most 15<3015 < 30: no solutions. The answer is (C) 8\boxed{\textbf{(C)}\ 8}.

Pitfalls

  • Forgetting negative factor pairs, or failing to check that they still yield positive variables.
  • Dropping the "same parity" requirement in (xy)(x+y)=n(x-y)(x+y) = n; if n2(mod4)n \equiv 2 \pmod 4 there are no solutions.
  • Counting unordered pairs when the problem says ordered (or vice versa).
  • Stopping after finding one solution of a linear equation instead of generating the full family.

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)

Problems, easiest first

2002 AMC 10A · #4Diophantine Equations

For how many positive integers mm does there exist at least one positive integer n such that mnm+nm \cdot n \le m + n ?

2020 AMC 10B · #9Diophantine Equations

How many ordered pairs of integers (x,y)(x,y) satisfy the equation x2020+y2=2y?x^{2020} + y^2 = 2y?

2008 AMC 10B · #8Diophantine Equations

A class collects $50\$50 to buy flowers for a classmate who is in the hospital. Roses cost $3\$3 each, and carnations cost $2\$2 each. No other flowers are to be used. How many different bouquets could be purchased for exactly $50\$50 ?

2024 AMC 10A · #11Diophantine Equations

How many ordered pairs of integers (m,n)(m, n) satisfy n249=m\sqrt{n^2 - 49} = m ?

2024 AMC 10A · #15Diophantine Equations

Let MM be the greatest integer such that both M+1213M+1213 and M+3773M+3773 are perfect squares. What is the units digit of MM ?

2023 AMC 10B · #11Diophantine Equations

Suzanne went to the bank and withdrew $800\$800 . The teller gave her this amount using $20\$20 bills, $50\$50 bills, and $100\$100 bills, with at least one of each denomination. How many different collections of bills could Suzanne have received?

2023 AMC 10B · #14Diophantine Equations

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

2021 AMC 10B · #11Diophantine Equations

Grandma has just finished baking a large rectangular pan of brownies. She is planning to make rectangular pieces of equal size and shape, with straight cuts parallel to the sides of the pan. Each cut must be made entirely across the pan. Grandma wants to make the same number of interior pieces as pieces along the …

2016 AMC 10A · #14Diophantine Equations

How many ways are there to write 20162016 as the sum of twos and threes, ignoring order? (For example, 10082+031008\cdot 2 + 0\cdot 3 and 4022+4043402\cdot 2 + 404\cdot 3 are two such ways.)

2015 AMC 10B · #15Diophantine Equations

The town of Hamlet has 33 people for each horse, 44 sheep for each cow, and 33 ducks for each person. Which of the following could not possibly be the total number of people, horses, sheep, cows, and ducks in Hamlet?

2015 AMC 10A · #15Diophantine Equations

Consider the set of all fractions xy,\tfrac{x}{y}, where xx and yy are relatively prime positive integers. How many of these fractions have the property that if both numerator and denominator are increased by 11 , the value of the fraction is increased by 10%10\% ?

2014 AMC 10A · #21Diophantine Equations

Positive integers aa and bb are such that the graphs of y=ax+5y=ax+5 and y=3x+by=3x+b intersect the xx -axis at the same point. What is the sum of all possible xx -coordinates of these points of intersection?

2008 AMC 10B · #15Diophantine Equations

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

2002 AMC 10B · #16Diophantine Equations

For how many integers nn is n20n\dfrac n{20-n} the square of an integer?

2001 AMC 10 · #14Diophantine Equations

A charity sells 140140 benefit tickets for a total of $2001\$2001 . Some tickets sell for full price (a whole dollar amount), and the rest sells for half price. How much money is raised by the full-price tickets?

2025 AMC 10B · #23Diophantine Equations

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 …

2023 AMC 10A · #23Diophantine Equations

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\textit{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 …

2021 AMC 10A · #22Diophantine Equations

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 …

2015 AMC 10B · #25Diophantine Equations

A rectangular box measures a×b×ca \times b \times c , where a,a, b,b, and cc are integers and 1abc1 \leq a \leq b \leq c . The volume and surface area of the box are numerically equal. How many ordered triples (a,b,c)(a,b,c) are possible?

2015 AMC 10A · #24Diophantine Equations

For some positive integers pp , there is a quadrilateral ABCDABCD with positive integer side lengths, perimeter pp , right angles at BB and CC , AB=2AB=2 , and CD=ADCD=AD . How many different values of p<2015p<2015 are possible?

2012 AMC 10A · #22Diophantine Equations

The sum of the first mm positive odd integers is 212212 more than the sum of the first nn positive even integers. What is the sum of all possible values of nn ?

2008 AMC 10B · #23Diophantine Equations

A rectangular floor measures aa by bb feet, where aa and bb are positive integers with b>ab > a . An artist paints a rectangle on the floor with the sides of the rectangle parallel to the sides of the floor. The unpainted part of the floor forms a border of width 1 foot around the painted rectangle and occupies half …

2007 AMC 10A · #23Diophantine Equations

How many ordered pairs (m,n)(m,n) of positive integers, with mnm \ge n , have the property that their squares differ by 9696 ?

2006 AMC 10B · #22Diophantine Equations

Elmo makes NN sandwiches for a fundraiser. For each sandwich he uses BB globs of peanut butter at 4¢4\cent per glob and JJ blobs of jam at 5¢5\cent per blob. The cost of the peanut butter and jam to make all the sandwiches is $2.53\$ 2.53 . Assume that BB , JJ , and NN are positive integers with $N>1 …

2006 AMC 10A · #22Diophantine Equations

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 …

2005 AMC 10B · #24Diophantine Equations

Let xx and yy be two-digit integers such that yy is obtained by reversing the digits of xx . The integers xx and yy satisfy x2y2=m2x^2 - y^2 = m^2 for some positive integer mm . What is x+y+mx + y + m ?

2007 AMC 10B · #25Diophantine Equations

How many pairs of positive integers (a,b)(a,b) are there such that aa and bb have no common factors greater than 11 and: ab+14b9a\frac{a}{b} + \frac{14b}{9a} is an integer?