Learn the idea. Try it yourself.
Read the explanation or try 6 questions with hints. Free, untimed and no sign-in needed.
All lessons · South Korea’s Olympiad route
Your goal: use the possible remainders of squares to reject impossible integer equations, shorten a bounded search and explain why your final answer is complete.
Preparation context: selected foundations for Korean Mathematical Olympiad (KMO) middle-division first-round reasoning. Under the 2026 first-round regulations, both the middle and high divisions have 20 short-answer problems in 150 minutes. This lesson is not a full paper, a complete syllabus or a claim of exact official difficulty. Its optional multiple-choice checks support learning and do not reproduce that short-answer format.
Later proof extension: Problems 8–9 develop written reasoning beyond the short numerical checks. The 2026 second-round regulations specify eight written-response/proof problems, seven marks each, across two three-hour sittings. These two extension tasks introduce proof methods; they are not a second-round mock or evidence of full second-round readiness. Check the current official notice for your division and year.
Before you start: integer squares, odd and even numbers, remainders and congruences, and expanding brackets. For the final two problems, also use proof by contradiction and construction. The descent idea is introduced before it is used.
Use three sittings: the starting check and Examples 1–2; Examples 3–4 and Problems 1–6; then Problems 7–9 and a written proof. Allow about 25–40 minutes per sitting and extra time for the final proofs. A foundation question here checks a prerequisite; it does not certify contest readiness.
A three-minute starting check
Try these on paper. This unsaved diagnostic is separate from the adaptive practice session.
- What are the remainders of 17 and −7 on division by 4? Use a remainder from 0 to 3.
- Let k be an integer. Expand (2k + 1)². Which part is visibly divisible by 4?
- Could an integer square lie strictly between 64 and 81? Explain without testing many integers.
Explained answers and a repair route
- Both remainders are 1: 17 = 4 × 4 + 1 and −7 = 4 × (−2) + 1. If negative remainders were confusing, return to remainders. The quotient may be negative, but the chosen remainder remains in the stated range.
- (2k + 1)² = 4k² + 4k + 1 = 4(k² + k) + 1. Thus an odd integer square has remainder 1 modulo 4. If the middle term was missing, revisit squaring a binomial.
- No. Since 64 = 8² and 81 = 9², a nonnegative integer square root would have to lie strictly between 8 and 9. No integer does. A negative root has the same square as its positive opposite, so allowing negatives adds no square values.
If the first two checks were difficult, repair them before the examples. If only the third was difficult, read the square-gap explanation before Example 4.
A square cannot have every remainder
perfect square is n² for an integer n. It is nonnegative; when recovering a square root of a nonnegative value, we may first choose the nonnegative root and then apply the sign conditions of the problem.
The equation x² = 3y + 2 offers infinitely many integers to try. A more useful question is: what remainder would the square x² have on division by 3? If that remainder is impossible, no search is needed.
For a positive integer m, write n = mq + r, where q is an integer and 0 ≤ r < m. Then n² = m²q² + 2mqr + r². The first two terms are multiples of m, so n² and r² have the same remainder modulo m. Consequently, squaring just the m possible input remainders examines every integer n, including negative integers. A complete remainder table is a proof about all integers, not a collection of lucky examples.
The notation a ≡ b (mod m) means that m divides a − b: a and b have the same remainder on division by m. It does not mean that a = b. A square residue modulo m is a remainder that an integer square can have. We include the remainder 0.
Build three small tables
Read each row as “if the input has this remainder, its square has that remainder”. The tables are deliberately narrow so that every row remains readable on a phone.
| Input remainder r | Remainder of r² |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| Input remainder r | Remainder of r² |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 0 |
| 3 | 1 |
| Input remainder r | Remainder of r² |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 4 |
| 3 | 1 |
| 4 | 0 |
| 5 | 1 |
| 6 | 4 |
| 7 | 1 |
Modulo 3, an integer square has remainder 0 or 1. The table also proves that if 3 divides n², then 3 divides n: input remainders 1 and 2 both produce square remainder 1. Modulo 4, the square remainders are again 0 and 1. This recalls the parity proof in the prerequisite lesson.
Why modulo 8 sees more than parity alone
Modulo 8 the complete square list is 0, 1, 4. Every odd integer has square remainder 1. To see why without memorising eight rows, write n = 2k + 1. Then n² = 4k(k + 1) + 1. One of the consecutive integers k and k + 1 is even, so k(k + 1) is even and 4k(k + 1) is divisible by 8.
For an even integer n = 2k, we have n² = 4k². If k is even this is divisible by 8; if k is odd it has remainder 4. Thus an even square can be 0 or 4 modulo 8. Do not replace both possibilities by 0.
Add, subtract and multiply the permitted remainders
When an equation has two squares, combine their allowed remainders. Modulo 4 each square is 0 or 1, so a sum of two squares can have remainder 0, 1 or 2, but never 3. A difference of two squares can have remainder 0, 1 or 3, but never 2, because −1 ≡ 3 (mod 4).
Coefficients matter. Modulo 8, the values of 2y² are 0, 2, 0 when y² has remainder 0, 1, 4. Therefore 2y² has only remainders 0 and 2. Reduce the complete expression, keeping its coefficients; do not treat 2y² as though it were an arbitrary square.
A practical choice: try modulo 3 when a coefficient is divisible by 3; modulo 4 for a sum or difference of two squares; and modulo 8 when odd squares or a coefficient 2 remain after a parity check. These are starting suggestions. If one modulus gives no contradiction, it has simply left possibilities open.
An allowed remainder is permission to investigate, not proof of a solution
A necessary condition is a condition every solution must satisfy. For example, every square is 0 or 1 modulo 4. But 33 has remainder 1 modulo 4 and modulo 8 and remainder 0 modulo 3, yet 5² < 33 < 6². It is not a square.
modular obstruction is a contradiction between the remainders that the two sides of an equation would need. It proves impossibility. If every modular test passes, you still need something else: an explicit solution, a complete bounded search, or a construction for every allowed case. A sufficient argument proves that the candidate actually works.
Four connected worked examples
Example 1 · Remove an infinite search with one modulus
Prove that x² = 6y + 5 has no integer solutions.
- The coefficient 6 is divisible by 3. Modulo 3, the right side has remainder 2 for every integer y.
- An integer square has remainder 0 or 1 modulo 3, never 2.
- If the equation held, its two equal sides would have equal remainders. They cannot, so there are no integer solutions, whether positive, negative or zero.
The contradiction is complete. Trying a long list of values for y would not have proved the same statement.
Your turn 1 · Change the expression
Prove that x² = 9y + 8 has no integer solutions.
Hint 1
Choose a modulus dividing the coefficient of y.
Hint 2
Modulo 3, the right side always has remainder 2.
Full solution
Since 9y is divisible by 3 and 8 ≡ 2 (mod 3), the equation would force x² ≡ 2 (mod 3). The complete square table allows only 0 and 1. Therefore no integers x,y satisfy the equation.
Example 2 · Strengthen a parity restriction
Prove that x² = 2y² + 5 has no integer solutions.
- First try modulo 4. If y were odd, then y² ≡ 1, so x² ≡ 2 + 1 ≡ 3 (mod 4), impossible. Thus any solution would need y even.
- Write y = 2k with k an integer. Then 2y² = 8k², so the equation becomes x² = 8k² + 5.
- Now work modulo 8. It would require x² ≡ 5 (mod 8), but the square remainders modulo 8 are only 0, 1 and 4. Hence no solution exists.
The first test was useful without being decisive: it removed odd y. The second test excluded the remaining even case. Alternatively, testing y² ≡ 0,1,4 directly modulo 8 makes 2y² + 5 have remainder 5,7,5, none a square residue.
Your turn 2 · A surviving condition needs a check
Let x and y be integers satisfying x² = 2y² + 7. Prove that y must be odd and give one integer solution. Do not claim that every odd y works.
Hint 1
What remainder would the right side have if y were even?
Hint 2
An even y makes 2y² divisible by 8. For existence, test y = 1.
Full solution
If y is even, then 2y² ≡ 0 (mod 8), forcing x² ≡ 7, impossible. Thus y is odd. Then x² ≡ 2 + 7 ≡ 1 (mod 8), which is allowed. Choosing y = 1 gives x² = 9, so (x,y) = (3,1) is an actual solution. The odd value y = 3 instead gives x² = 25, also a square, but y = 5 gives 57, not a square. Parity is a necessary condition, not a full classification.
Example 3 · Filter, bound and check every survivor
Find all ordered pairs of nonnegative integers (x,y) satisfying x² + 2y² = 57.
- Because x² ≥ 0, we have 2y² ≤ 57. Hence 0 ≤ y ≤ 5; at y = 6 the term 2y² is already 72.
- Modulo 8, 57 has remainder 1. An odd y would give 2y² ≡ 2, forcing x² ≡ 7, impossible. Therefore y must be even.
- Only y = 0,2,4 remain. Their required x² values are 57,49,25. The number 57 is not a square because 7² < 57 < 8². The other two give x = 7 and x = 5 respectively.
- The candidates are (7,2) and (5,4). They work: 49 + 8 = 57 and 25 + 32 = 57. The bound and parity test leave no other y, and x is restricted to its nonnegative root. This proves the list is complete.
Notice the three separate jobs: the inequality made the search finite, the residue test shortened it, and substitution verified the surviving pairs.
Your turn 3 · Keep the zero endpoint in the search
Find all ordered pairs of nonnegative integers with x² + 2y² = 33.
Hint 1
Use the same bound-and-parity sequence. Do not start your list at y = 1.
Hint 2
We have y ≤ 4, and modulo 8 again forces y even.
Full solution
The inequality 2y² ≤ 33 gives 0 ≤ y ≤ 4. If y were odd, reducing modulo 8 would force x² ≡ 7, impossible. For y = 0,2,4, the required values x² are 33,25,1. The first is between 5² and 6²; the others give (x,y) = (5,2) and (1,4). They check as 25 + 8 = 33 and 1 + 32 = 33. All possible y were examined.
Example 4 · Prove that only a small range needs checking
Find all positive integers n for which n² + 2n + 20 is a perfect square.
The expression is (n + 1)² + 19. This suggests comparing it with the next square (n + 2)². Consecutive squares have a growing gap: (t + 1)² − t² = 2t + 1.
- For n ≥ 9, the gap from (n + 1)² to (n + 2)² is 2n + 3 ≥ 21. Our added 19 is positive and smaller than that gap. Therefore (n + 1)² < n² + 2n + 20 < (n + 2)², so the expression cannot be a square.
- It remains to check 1 ≤ n ≤ 8. Modulo 3, the expression equals (n + 1)² + 1. If 3 does not divide n + 1, its square has remainder 1, so the whole expression has forbidden square remainder 2. Thus n + 1 must be divisible by 3.
- The surviving values are n = 2,5,8. Substitution gives 28,55,100. The first two lie between 5² and 6², and between 7² and 8², respectively. The last is 10².
- Thus n = 8 is the only positive solution. The large-range argument and the complete small-range check establish uniqueness.
Your turn 4 · Explain the inequality
Prove that n² + 2n + 14 is not a perfect square when n is an integer with n ≥ 6.
Hint 1
Write it as a square plus a constant.
Hint 2
The expression is (n + 1)² + 13. Compare 13 with 2n + 3.
Full solution
For n ≥ 6, the gap (n + 2)² − (n + 1)² = 2n + 3 is at least 15. Since 0 < 13 < 15, the expression (n + 1)² + 13 lies strictly between the consecutive squares (n + 1)² and (n + 2)². Hence it is not a square in the stated range. This argument makes no claim about n < 6.
Before the final problems: two ways to finish a proof
Use an order condition as a bound
If 1 ≤ a ≤ b ≤ c and a² + b² + c² = T, then T ≤ 3c² because each square is at most c². Also c² ≤ T − 2 because a² and b² are each at least 1. These inequalities can leave very few values of c. For a fixed c, the condition a ≤ b gives 2a² ≤ T − c². This bounds the smaller coordinate before you test its values. Keep the order condition throughout, so that permutations are not counted as new triples.
When a contradiction needs a second round
A residue argument can force every variable to be divisible by 3 without immediately being impossible. For example, being divisible by 3 is entirely possible for a nonzero integer. The next question is whether dividing all the variables by 3 produces a smaller nonzero solution of the same equation.
This is the idea of infinite descent. Suppose a nonzero integer solution existed. Measure its size by the positive integer |x| + |y| + |z|, where |x| is x if x ≥ 0 and −x if x < 0. Among all hypothetical nonzero solutions, choose one with the smallest size; a nonempty set of positive integers has a smallest member. If your argument then constructs another nonzero integer solution of the same equation with one-third the size, you have a contradiction. The new size cannot be both smaller and at least the chosen minimum.
In Problem 8 you will supply the missing algebra. Check three points explicitly: division leaves integers; the transformed equation is the original equation again; and the new triple remains nonzero. Without those checks, a “keep dividing” argument has a gap.
Common mistakes and their repairs
- Checking examples instead of all remainders: a few squares may suggest a pattern. List every input remainder or write the general even/odd form to prove it.
- Calling every even square 0 modulo 8: 2² has remainder 4. Keep both 0 and 4.
- Ignoring a coefficient: combine the possible values of 2y² or 3y², not just those of y².
- Reversing a necessary condition: “a square has this remainder” does not imply “every number with this remainder is a square”. Test the actual candidates or give a construction.
- Losing zero, signs or order: “integer”, “positive integer” and “nonnegative integer” are different domains. In a sum of squares, opposite signs give the same value but may be different ordered solutions.
- Claiming completeness after finding one pair: state the bound or obstruction that excludes everything else.
- Making descent circular: first assume a smallest nonzero solution, then prove a smaller one exists. Do not assume at the outset that all variables are zero.
Start a short practice session
The adaptive session selects six checks from the nine below. Choose a starting level, read the feedback and use the linked explanation if a step is unclear. You can work through every written problem afterwards. Foundation checks the tools; Core combines them; Stretch requires a proof idea as well as a result.
What is checked: the interactive questions check a numerical answer or a precise conclusion. They do not grade your written proofs, the completeness of your search or your explanation of descent. A completed session means six responses, including any requested solutions; it is not a certificate of mastery or six independently correct answers.
Interactive practice loads here. You can also use the complete question set below.
Nine original problems, hints and full solutions
Keep the optional choices closed for an answer-only attempt. Write the reason as well as the answer; reveal one hint at a time. The interactive check for each problem asks only the stated short-answer part, while the written task may require a full argument.
Foundation
1. Combine two different parity conditions
An odd integer a and an integer b with b ≡ 2 (mod 4) are given. Find the remainder of a² + b² on division by 8. Explain why your answer is independent of the particular integers chosen.
Optional choices for the adaptive check
If a is odd and b ≡ 2 (mod 4), what is the remainder of a² + b² on division by 8?
- 1
- 4
- 5
- 0
Hint 1
Treat the two squares separately. An odd square has a fixed remainder modulo 8.
Hint 2
Write b = 4k + 2 and expand its square. Then add the two square remainders.
Answer and complete solution
Because a is odd, a² ≡ 1 (mod 8). Write b = 4k + 2 for an integer k. Then b² = 16k² + 16k + 4, which has remainder 4 modulo 8.
Adding gives a² + b² ≡ 1 + 4 ≡ 5 (mod 8). The argument works for every integer k and every odd a, including negative values, so the required remainder is always 5.
Watch out: An even square is not always 0 modulo 8. A number congruent to 2 modulo 4 has square remainder 4.
Foundation
2. A square can have more than one root remainder
List all integers r in the range 0 ≤ r ≤ 7 for which r² ≡ 4 (mod 8). How many are there?
Optional choices for the adaptive check
How many integers r with 0 ≤ r ≤ 7 satisfy r² ≡ 4 (mod 8)?
- 0
- 4
- 8
- 2
Hint 1
Use the complete table modulo 8, not just the positive square root of 4.
Hint 2
Compare the squares of 2 and 6. Check all eight input remainders to prove your list is complete.
Answer and complete solution
For r = 0,1,2,3,4,5,6,7, the respective square remainders modulo 8 are 0,1,4,1,0,1,4,1.
The required inputs are exactly r = 2 and r = 6, so the count is 2. The table checks every allowed r. These are two input remainders producing the same square remainder.
Watch out: Taking an ordinary square root of a congruence can lose valid residue classes.
Foundation
3. Pass the tests, then check the number
Which of 49, 73 and 97 are perfect squares? All three have remainder 1 modulo 3, modulo 4 and modulo 8. Explain why those three remainder tests do not settle the question.
Optional choices for the adaptive check
How many of 49, 73 and 97 are perfect squares?
- 1
- 0
- 2
- 3
Hint 1
Passing a residue test means “not ruled out by this test”. Compare each number with consecutive squares.
Hint 2
Use 7², 8², 9² and 10². Where do 73 and 97 lie?
Answer and complete solution
We have 49 = 7², so 49 is a perfect square. Also 8² = 64 < 73 < 81 = 9², and 9² = 81 < 97 < 100 = 10². No integer square lies strictly between two consecutive nonnegative integer squares. Thus neither 73 nor 97 is a square.
Exactly one of the three numbers is a square. Each number has remainder 1 modulo 24 and therefore remainder 1 modulo 3, 4 and 8. Those remainders are allowed for a square, but allowed remainders do not supply an integer square root.
Watch out: Necessary conditions eliminate candidates; they do not automatically prove that a surviving candidate works.
Core
4. An equation with an immediate obstruction
Find the number of ordered integer pairs (x, y) satisfying x² + y² = 4xy + 39. Integers may be negative or zero.
Optional choices for the adaptive check
How many ordered integer pairs (x,y) satisfy x² + y² = 4xy + 39?
- 1
- 0
- 2
- Infinitely many
Hint 1
The coefficient 4 suggests reducing the whole equation modulo 4.
Hint 2
A sum of two square remainders modulo 4 can be 0, 1 or 2. What remainder does the right side have?
Answer and complete solution
For every integer t, t² has remainder 0 or 1 modulo 4. Hence x² + y² can have only remainder 0, 1 or 2.
The right side 4xy + 39 has remainder 3 modulo 4 for every integer pair, since 4xy is divisible by 4 and 39 ≡ 3 (mod 4). Equal integers must have equal remainders. This is impossible, so there are no ordered integer pairs. The answer is 0, regardless of signs or order.
Watch out: There is no need to bound x and y when a valid modular contradiction already excludes every pair.
Core
5. Filter before completing a finite search
Find all ordered pairs of nonnegative integers (x, y) satisfying x² + 2y² = 81. Nonnegative means that zero is allowed.
Optional choices for the adaptive check
How many ordered pairs of nonnegative integers (x,y) satisfy x² + 2y² = 81?
- 1
- 2
- 4
- 3
Hint 1
First bound y. Then use modulo 8 to eliminate one parity of y.
Hint 2
If y were odd, 2y² would have remainder 2 modulo 8. For even y, test only y = 0, 2, 4, 6.
Answer and complete solution
Since x² ≥ 0, we have 2y² ≤ 81. Thus 0 ≤ y ≤ 6: y = 7 already gives 2y² = 98 > 81.
Modulo 8 the right side is 1. If y were odd, y² ≡ 1, so x² ≡ 1 − 2 ≡ 7 (mod 8), impossible for a square. Therefore y is even.
For y = 0, 2, 4, 6, the required values x² = 81 − 2y² are respectively 81, 73, 49, 9. These give x = 9, no nonnegative integer x, x = 7 and x = 3. The value 73 lies strictly between 8² and 9².
The complete list is (9,0), (7,4), (3,6). Substitution gives 81 + 0 = 81, 49 + 32 = 81 and 9 + 72 = 81. The bound and parity restriction exhausted all possible y, and nonnegativity chooses only the nonnegative square roots. There are 3 pairs.
Watch out: Do not discard y = 0 or add negative square roots when the problem says nonnegative.
Core
6. Use order to keep a three-variable search short
Find all triples of positive integers (a, b, c) with a ≤ b ≤ c and a² + b² + c² = 54.
Optional choices for the adaptive check
How many triples of positive integers (a,b,c) with a ≤ b ≤ c satisfy a² + b² + c² = 54?
- 2
- 3
- 4
- 5
Hint 1
Because c is the largest coordinate, compare 54 with 3c². Because a and b are positive, compare c² with 52.
Hint 2
These bounds give c = 5, 6 or 7. For each, solve a² + b² = 54 − c² with 1 ≤ a ≤ b ≤ c. Modulo 4, exactly two of the three coordinates must be odd.
Answer and complete solution
Since a ≤ b ≤ c, we have 54 = a² + b² + c² ≤ 3c². If c ≤ 4, the right side is at most 48, impossible. Thus c ≥ 5. Since a² + b² ≥ 2, we also have c² ≤ 52, so c ≤ 7. Only c = 5, 6, 7 remain.
As 54 ≡ 2 (mod 4) and each square contributes 0 for an even coordinate or 1 for an odd coordinate, exactly two coordinates are odd. This is a useful check, but we still complete the bounded search.
For c = 5, a² + b² = 29. The condition a ≤ b gives 2a² ≤ 29, so a can be 1, 2 or 3. The corresponding b² values are 28, 25, 20. Only 25 is a square, giving (a,b,c) = (2,5,5).
For c = 6, a² + b² = 18 and 2a² ≤ 18, so a = 1, 2 or 3. The b² values are 17, 14, 9. Only 9 is a square, giving (3,3,6).
For c = 7, a² + b² = 5 and 2a² ≤ 5, so a = 1. Then b² = 4, giving (1,2,7).
The triples are (2,5,5), (3,3,6), (1,2,7). Their square sums are 4 + 25 + 25, 9 + 9 + 36 and 1 + 4 + 49, all 54. Each has the required order. All possible c and a were checked, so the list is complete and the count is 3.
Watch out: The order restriction prevents extra counts from permutations. A parity check alone does not enumerate all triples.
Stretch
7. Combine a square gap with a residue filter
Find all positive integers n for which n² + n + 7 is a perfect square. Give their sum.
Optional choices for the adaptive check
What is the sum of all positive integers n for which n² + n + 7 is a perfect square?
- 1
- 6
- 7
- 8
Hint 1
For large n, compare the expression with n² and (n + 1)². Determine exactly when the upper inequality is strict.
Hint 2
For n ≥ 7 the expression lies strictly between those consecutive squares. For 1 ≤ n ≤ 6, work modulo 4 before substituting.
Answer and complete solution
The expression exceeds n² for every positive n. It is smaller than (n + 1)² exactly when n + 7 < 2n + 1, which is equivalent to n > 6. Therefore no n ≥ 7 works. Equality at n = 6 must not be discarded.
For n ≡ 0, 1, 2, 3 (mod 4), the expression n² + n + 7 has respective remainders 3, 1, 1, 3. A square cannot have remainder 3, so among 1 ≤ n ≤ 6 only n = 1, 2, 5, 6 remain.
Their values are respectively 9, 13, 37, 49. The numbers 9 = 3² and 49 = 7² are squares. Also 3² < 13 < 4² and 6² < 37 < 7², so the other two are not.
Thus exactly n = 1 and n = 6 work, and their sum is 1 + 6 = 7. The large-n bound and the complete small list justify “all”.
Watch out: A strict-between-squares argument does not exclude an endpoint where equality holds.
Stretch · proof extension
8. When a residue argument starts a descent
Prove that the only integer triple (x, y, z) satisfying x² + y² = 3z² is (0,0,0). You must exclude negative as well as positive nonzero values.
Optional choices for the adaptive check
What is the complete integer solution set of x² + y² = 3z²?
- Only (0,0,0)
- No triples, including zero
- Exactly two triples
- Infinitely many nonzero triples
Hint 1
Modulo 3, how can a sum of two square remainders be 0? After writing x = 3a and y = 3b, inspect z².
Hint 2
Show that all three coordinates are divisible by 3, and that dividing all three by 3 gives another solution. Use the smallest positive value of |x| + |y| + |z| among hypothetical nonzero solutions.
Answer and complete solution
The triple (0,0,0) works. Suppose a nonzero integer solution also exists. For such a solution, S = |x| + |y| + |z| is a positive integer. Choose a nonzero solution with the smallest possible S. Here |x| means the nonnegative size of x, so signs cause no difficulty.
Reducing modulo 3 gives x² + y² ≡ 0. Each square remainder is 0 or 1; the only way their sum is 0 modulo 3 is 0 + 0. Thus 3 divides both x and y. Write x = 3a and y = 3b with a,b integers.
Substitution gives 9a² + 9b² = 3z², hence z² = 3(a² + b²). Thus z² is divisible by 3. The square table modulo 3 shows that its root z must also be divisible by 3; write z = 3c.
Now divide the original equation by 9 to obtain a² + b² = 3c². Therefore (a,b,c) is another integer solution. It is nonzero because the original triple was nonzero, and its size is |a| + |b| + |c| = S/3 < S. This contradicts the choice of S.
No nonzero integer solution exists. Together with the checked zero triple, this proves the complete solution set is exactly {(0,0,0)}.
Watch out: Showing divisibility by 3 once is not a contradiction. The contradiction comes from a smaller nonzero solution to the same equation.
Stretch · proof extension
9. Turn a necessary condition into a complete classification
Determine exactly which integers N can be written as N = x² − y² with integers x and y. Then count such N in the range 1 ≤ N ≤ 60. There is no positivity or order restriction on x and y.
Optional choices for the adaptive check
How many integers N with 1 ≤ N ≤ 60 can be written as x² − y² for integers x,y?
- 30
- 46
- 60
- 45
Hint 1
First list the possible differences of two square remainders modulo 4. That gives a necessary condition, but not yet a classification.
Hint 2
Construct x and y for each allowed type: N odd, or N = 4k. Use consecutive integers in the odd case and numbers differing by 2 in the multiple-of-4 case.
Answer and complete solution
Squares have remainders 0 or 1 modulo 4. Their differences therefore have remainders 0, 1 or −1, the last being 3 modulo 4. Remainder 2 is impossible. Thus N must not be congruent to 2 modulo 4.
Every odd integer N does work. To construct x and y, factor x² − y² as (x − y)(x + y). Choose the factors x − y = 1 and x + y = N; their product is N. Adding these equations gives 2x = N + 1, and subtracting the first from the second gives 2y = N − 1. Hence x = (N + 1)/2 and y = (N − 1)/2. They are integers because N is odd. Substitution gives x² − y² = 1 × N = N. This also covers negative odd N.
Every integer N = 4k also works, with k an integer. In (x − y)(x + y), choose x − y = 2 and x + y = 2k; their product is 4k = N. Adding gives 2x = 2k + 2, while subtracting the first equation from the second gives 2y = 2k − 2. Thus x = k + 1 and y = k − 1, both integers. Checking gives x² − y² = (k + 1)² − (k − 1)² = 4k = N. There is no requirement that x or y be positive, so this construction includes zero and negative multiples of 4.
Necessity and the two constructions prove the classification: exactly the integers N not congruent to 2 modulo 4 are differences of two integer squares.
Among 1 through 60, there are 15 numbers congruent to 2 modulo 4: one in each block 1–4, 5–8, …, 57–60. Excluding them leaves 60 − 15 = 45 allowed integers.
Watch out: An allowed remainder proves only necessity until you give a construction for every surviving type of N.
Exit task: explain both directions
Without reopening Problem 9, write its classification proof: exactly which integers are differences of two integer squares? State the impossible remainder, then give constructions covering every other case. Finally explain why allowing negative or zero values matters to your constructions.
Planning hint
A complete “exactly which” answer needs necessity and sufficiency. The residue table supplies the first. Separate odd integers from multiples of 4 for the second.
Compare with a full proof
If N = x² − y², reducing modulo 4 shows N has remainder 0,1 or 3, never 2. Conversely, write x² − y² = (x − y)(x + y). For odd N, choose x − y = 1 and x + y = N. Adding and subtracting give 2x = N + 1 and 2y = N − 1, hence the integers x = (N + 1)/2 and y = (N − 1)/2. Their square difference is 1 × N = N. For N = 4k with k an integer, choose x − y = 2 and x + y = 2k. Adding and subtracting give 2x = 2k + 2 and 2y = 2k − 2, so x = k + 1 and y = k − 1. Their square difference is 2 × 2k = N. These constructions cover all integers not congruent to 2 modulo 4, including zero and negatives, because neither x nor y must be positive. Therefore precisely those integers are representable.
A proof checklist you can use yourself
This is a self-review guide, not an official marking scheme. Award yourself one point for each item you can point to in your written solution.
- Domain: I state which variables are integers, whether zero or negatives are allowed, and any order restrictions.
- Remainder evidence: I justify the complete square-residue list or a general parity form, then reduce both sides consistently.
- Logical conclusion: I explain either the incompatible remainders or what possibilities survive. I do not turn a necessary condition into sufficiency without proof.
- Completeness: my bound exhausts every candidate, my construction covers every permitted type, or my descent creates a smaller nonzero integer solution of the same equation.
- Verification: I substitute claimed solutions, check endpoints and finish with the exact answer requested.
For an impossibility proof, verification means checking that the contradiction covers every allowed case; you do not need to invent a candidate solution. For Problem 8, include why a smallest positive size exists and why dividing by 3 leaves a smaller nonzero solution. For Problem 9, explicitly label the necessity and sufficiency directions.
My proof notebook
Use paper, or the optional browser notebook. Compare your work with the full solution after a real attempt. The notebook is not an automatic proof marker.
Choose what to do next
- If the tables were difficult, revisit modular arithmetic and reattempt Problems 1–3.
- If you found candidates but could not prove the list complete, reread the bounded search and reattempt Problems 5–6.
- If the final proofs needed hints, return another day and write one independently. For another method, study integer equations by factorisation.
- Return to South Korea’s study route, or open your optional local revision list. If you came from a paper, use the return-to-paper option when available.
Contest context and originality
For official KMO notices and released materials, use the Korean Mathematical Olympiad website, the official released-paper archive, and the first- and second-round notices linked above. The 2026 middle first-round paper supports this topic selection through its integer/perfect-square and bounded-divisibility tasks; this is an editorial topic connection, not an official promise of topic frequency or difficulty. Check the current notice for your division, stage and year; a topic lesson does not replace those instructions. These explanations, worked examples, practice tasks and tables are original AI-assisted editorial teaching material using standard mathematical ideas. They are not reproduced or translated contest questions, and no organiser affiliation or endorsement is claimed.
Prepared for IMOolympiad.com. Report a specific unclear step or correction. Optional progress stays in this browser; the written proofs are for your own review.