When a BMO number theory problem asks you to prove that an equation has no integer solutions, modular arithmetic is often the fastest weapon—provided you choose the right modulus. The technique is simple in principle: find a modulus m such that the two sides of your equation can never be congruent modulo m. The difficulty lies in selecting m efficiently rather than testing values blindly. This article gives a clean decision method, works through a verified example and a genuine contrasting failure, and ends with a diagnostic you can apply immediately.
The Core Principle: When a Modulus Proves Impossibility
Suppose we want to show that a Diophantine equation has no integer solutions. If we can find a modulus m where the set of possible residues for the left-hand side and the set of possible residues for the right-hand side are disjoint, then no integer solution can exist. The equation fails in ℤ/mℤ, so it fails in ℤ.
The art is choosing m so that this disjointness is easy to verify. A poor choice leaves overlapping residue sets and gives no information. A well-chosen modulus collapses the equation to a visible contradiction.
Teaching Illustration: Proving x² + y² = 3 Has No Integer Solutions
Step 1: Try modulus 2. If x and y have opposite parities, then x² + y² ≡ 0 + 1 ≡ 1 (mod 2). If both are even or both odd, x² + y² ≡ 0 + 0 ≡ 0 or 1 + 1 ≡ 0 (mod 2). Since 3 ≡ 1 (mod 2), the equation is satisfiable in principle. Modulus 2 is inconclusive—it allows solutions and does not rule them out.
Step 2: Try modulus 4. This is the decisive choice. Compute squares modulo 4:
| n (mod 4) | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| n² (mod 4) | 0 | 1 | 0 | 1 |
So n² ≡ {0, 1} (mod 4) for any integer n.
Step 3: Check all possible sums. The possible values of x² + y² (mod 4) are:
| + | 0 | 1 |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 2 |
Thus x² + y² ≡ {0, 1, 2} (mod 4).
Conclusion: The right-hand side is 3 ≡ 3 (mod 4), which never appears in {0, 1, 2}. Therefore x² + y² = 3 has no integer solutions.
The Contrasting Case: Why Passing a Modulus Test Does Not Prove Existence
Consider the superficially similar equation x² + y² = 5. The same modulus 4 analysis gives x² + y² ≡ {0, 1, 2} (mod 4), and since 5 ≡ 1 (mod 4), the modular test does not rule out solutions. But this is not enough to conclude solutions exist.
Here, we must actually find a solution: x = 1, y = 2 gives 1² + 2² = 1 + 4 = 5. The pairs (±1, ±2) and (±2, ±1) provide all integer solutions.
The critical lesson: The fact that an equation passes several small modulus tests never proves it has solutions. Only a constructive argument—a found pair or an existence theorem—can do that. Conversely, a single modulus that creates a contradiction definitively proves non-existence. Modular arithmetic is a one-way tool for proving impossibility, not a two-way tool for proving existence.
Why Finite Examples Are Not Proof
A common student error is to test x² + y² = 3 for several small values, find no solutions, and claim “therefore no solutions exist.” This is invalid reasoning. Testing finitely many cases only shows those particular cases fail; it cannot cover all integers.
The modulus argument succeeds because it simultaneously handles all integers by grouping them into residue classes. When we prove no residue class works modulo 4, we have checked infinitely many cases at once. This is why modular arithmetic replaces exhaustive search with structural reasoning.
Diagnostic Application: x² + 1 = 3y²
Problem: Prove that x² + 1 = 3y² has no integer solutions.
Step 1: Choose modulus 3. The coefficient 3y² suggests this modulus, as 3y² ≡ 0 (mod 3).
Step 2: Compute residues. Squares modulo 3:
| n (mod 3) | 0 | 1 | 2 |
|---|---|---|---|
| n² (mod 3) | 0 | 1 | 1 |
So x² ≡ {0, 1} (mod 3), and thus x² + 1 ≡ {1, 2} (mod 3).
Step 3: Compare. The right-hand side 3y² ≡ 0 (mod 3).
Conclusion: LHS ∈ {1, 2} and RHS ≡ 0 (mod 3). These sets are disjoint. Therefore x² + 1 = 3y² has no integer solutions.
A Brief Counterexample Lesson
Some equations that look similar do have solutions, which shows why careful analysis matters:
- x² + x + 1 = y³ has solutions including (0, 1) and (18, 7)
- x² + x + 2 = y³ has solution (2, 2)
These examples remind us that superficial similarity in form does not predict solvability. Each equation requires its own analysis.
Systematic Modulus Selection: A Three-Step Decision
Here is a systematic way to choose a modulus without guessing:
Step 1: Inspect coefficients and constant terms. Look for moduli that simplify the equation by making terms vanish. If a term has coefficient divisible by m, that term disappears modulo m. In x² + 3y² = 2, choosing m = 3 would eliminate 3y².
Step 2: Test small prime moduli first, then composites. Check 2, 3, 5, 7, 11 and their higher powers such as 4, 8, 9, 16. The computation is fast: for each, enumerate residues of the relevant powers (squares, cubes) and check for disjointness. In BMO problems, the right modulus is usually small; if none work quickly, reconsider your approach.
Step 3: Verify or pivot. If a modulus gives disjoint residue sets, write the proof cleanly. If several small moduli fail to give a contradiction, switch to constructive methods, bounding, or infinite descent. The failure of several small moduli to contradict does not prove existence; it merely fails to prove non-existence.
What Your Diagnostic Result Means for Next Steps
| Level | Indicator | Next Step |
|---|---|---|
| Foundational | Can compute residues correctly for small moduli | Drill speed and accuracy with Which BMO Past Paper Should You Sit Today? A Stage-Matched Practice Ladder |
| Intermediate | Can identify promising moduli but sometimes picks ineffective ones | Study The BMO1 Number Theory and Combinatorics Toolkit: Parity, Invariants, Pigeonhole and the Right Modulus for pattern recognition |
| Advanced | Can combine modular arguments with descent or bounding | Work through BMO Infinite Descent: How to Write a Complete Proof to integrate techniques |
For students preparing for BMO1, modular arithmetic is a core topic, with congruence theory and Diophantine equations forming key strands. Knowing when a modulus works—and when to abandon it—is as important as the computation itself.
Preparing for Your BMO Path
If you are deciding how to fit modular arithmetic into your BMO preparation, a focused discussion can clarify your starting point. Before reaching out, note: your current competition mathematics background, your confidence with proof writing versus calculation, and your weekly preparation time. This helps identify whether your immediate priority is building modular fluency, transitioning from multiple-choice to proof-based problems, or integrating BMO preparation with other commitments. The BMO Registration China: Direct Entry Rules, Centre Finding, and Deadline Planning for 2026 article covers practical entry details separately.
Extending the Diagnostic: When One Modulus Fails, Try a Composite
The previous section demonstrated that modulus 3 definitively rules out integer solutions for x² + 1 = 3y². However, students often encounter equations where small prime moduli fail to produce disjoint residue sets, leading to frustration and incorrect assumptions about solvability. A critical gap in standard modular arithmetic instruction is the strategic use of composite moduli when primes are inconclusive.
Consider the equation x² + y² = 7. Testing modulus 4 (the standard tool for sums of two squares) yields x² + y² ≡ {0, 1, 2} (mod 4). Since 7 ≡ 3 (mod 4), this works immediately. But not all equations are so cooperative. To illustrate the need for composites, we must look at an equation where small primes overlap but a larger structure reveals the contradiction.
Take x² + y² = 6. Modulus 4 gives possible sums {0, 1, 2}. Since 6 ≡ 2 (mod 4), the test is inconclusive; it allows solutions. Modulus 3 gives squares {0, 1}, so sums are {0, 1, 2}. Since 6 ≡ 0 (mod 3), this is also inconclusive. We must try a composite modulus, such as 8.
Squares modulo 8 are restricted more tightly than modulo 4. For any integer n, if n is even, n² ≡ 0 or 4 (mod 8); if n is odd, n² ≡ 1 (mod 8). Thus, the set of quadratic residues modulo 8 is {0, 1, 4}. The possible sums of two squares modulo 8 are:
- 0+0=0, 0+1=1, 0+4=4
- 1+1=2, 1+4=5
- 4+4=0 (since 8≡0)
The set of achievable values for x² + y² modulo 8 is {0, 1, 2, 4, 5}. The right-hand side is 6. Since 6 is not in this set, x² + y² = 6 has no integer solutions. This conclusion was invisible using only moduli 2, 3, or 4.
This teaching illustration highlights a vital decision rule: if small prime moduli yield overlapping residue sets, do not assume solvability. Instead, escalate to higher powers of those primes (like 8 instead of 2 or 4) or other composites. The structure of quadratic residues becomes sparser as the modulus increases, often revealing contradictions that smaller moduli miss. Always verify your final residue calculation carefully, as errors in listing quadratic residues are common under time pressure.
Frequently Asked Questions
Why does the same modulus work for some equations but not others?
A modulus eliminates solutions only when the sets of possible residues for each side of the equation do not overlap. Changing the equation changes these residue sets, so a modulus that creates a contradiction for one equation may permit solutions for another. There is no universal modulus that works for all equations.
How do I know when to stop trying moduli and use a different method?
If several promising moduli give no contradiction, consider factorisation, bounds or infinite descent rather than trying moduli without a reason. No fixed list of failed tests proves that solutions exist or that modular methods cannot work; a modulus suggested by the equation may still be decisive.
Is modular arithmetic enough for BMO1 number theory problems?
Modular arithmetic is a powerful tool but rarely the entire solution. BMO1 problems often require combining it with other techniques such as bounding, factorisation, or infinite descent. Congruence theory sits alongside Euclidean algorithms and Diophantine methods as complementary topics in standard preparation.