Topics / Number Theory
Diophantine Equations
Integer solutions of equations, bounding, factoring integer equations
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: becomes ; then list factor pairs of the right side.
- Linear equations have integer solutions iff ; once one solution is found, all others are .
- Difference of squares: means with both factors of the same parity.
- Bounding: if the variables are ordered (), the smallest one is bounded, e.g., forces .
- Perfect powers are rare: means 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: with nonnegative integers; count solutions or find a maximum/minimum.
- "For how many is (or a similar fraction) an integer?" Rewrite as and count divisors.
- Express 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
- Isolate one variable; if it appears as a fraction, demand the denominator divide the numerator.
- Try to factor: SFFT, difference of squares, or completing the square on both variables.
- Bound a variable using ordering or size, then run small cases.
- Take the equation modulo a small number to rule out solutions or force parity.
- For linear equations, find one solution and step by and ; count how many steps stay in range.
Worked example
How many ordered pairs of positive integers satisfy ?
(A) (B) (C) (D) (E)
Add to both sides: , which factors as . Both factors are integers with product . If both are positive, can be any of the divisors , each giving positive and ; for example gives . If both are negative, we need and , so and , and their product is at most : no solutions. The answer is .
Pitfalls
- Forgetting negative factor pairs, or failing to check that they still yield positive variables.
- Dropping the "same parity" requirement in ; if 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
For how many positive integers does there exist at least one positive integer n such that ?
How many ordered pairs of integers satisfy the equation
A class collects to buy flowers for a classmate who is in the hospital. Roses cost each, and carnations cost each. No other flowers are to be used. How many different bouquets could be purchased for exactly ?
How many ordered pairs of integers satisfy ?
Let be the greatest integer such that both and are perfect squares. What is the units digit of ?
Suzanne went to the bank and withdrew . The teller gave her this amount using bills, bills, and bills, with at least one of each denomination. How many different collections of bills could Suzanne have received?
How many ordered pairs of integers satisfy the equation ?
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 …
How many ways are there to write as the sum of twos and threes, ignoring order? (For example, and are two such ways.)
The town of Hamlet has people for each horse, sheep for each cow, and ducks for each person. Which of the following could not possibly be the total number of people, horses, sheep, cows, and ducks in Hamlet?
Consider the set of all fractions where and are relatively prime positive integers. How many of these fractions have the property that if both numerator and denominator are increased by , the value of the fraction is increased by ?
Positive integers and are such that the graphs of and intersect the -axis at the same point. What is the sum of all possible -coordinates of these points of intersection?
How many right triangles have integer leg lengths and and a hypotenuse of length , where ?
For how many integers is the square of an integer?
A charity sells benefit tickets for a total of . 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?
A rectangular grid of squares has rows and columns. Each square has room for two numbers. Horace and Vera each fill in the grid by putting the numbers from through into the squares. Horace fills the grid horizontally: he puts through in order from left to right into …
If the positive integer has positive integer divisors and with , then and are said to be divisors of . Suppose that is a positive integer that has one complementary pair of divisors that differ by and another pair of complementary divisors that differ …
Hiram's algebra notes are pages long and are printed on sheets of paper; the first sheet contains pages and , the second sheet contains pages and , 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 …
A rectangular box measures , where and are integers and . The volume and surface area of the box are numerically equal. How many ordered triples are possible?
For some positive integers , there is a quadrilateral with positive integer side lengths, perimeter , right angles at and , , and . How many different values of are possible?
The sum of the first positive odd integers is more than the sum of the first positive even integers. What is the sum of all possible values of ?
A rectangular floor measures by feet, where and are positive integers with . 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 …
How many ordered pairs of positive integers, with , have the property that their squares differ by ?
Elmo makes sandwiches for a fundraiser. For each sandwich he uses globs of peanut butter at per glob and blobs of jam at per blob. The cost of the peanut butter and jam to make all the sandwiches is . Assume that , , and are positive integers with $N>1 …
Two farmers agree that pigs are worth dollars and that goats are worth 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 dollar debt could be paid with two pigs, with one goat received in …
Let and be two-digit integers such that is obtained by reversing the digits of . The integers and satisfy for some positive integer . What is ?
How many pairs of positive integers are there such that and have no common factors greater than and: is an integer?