Learn a method, then use it in a proof. This beginner sequence develops remainders, greatest common divisors, power cycles and integer equations. It is preparation for proof-based national Olympiads, not an official syllabus for every country.
Start with the notation · Try nine exercises · See the complete topic map
Before you start
You should be able to expand (a + b)², factor a difference of squares, divide with a remainder and use prime factorisation. If these are unfamiliar, begin with the foundations guide. The congruence notation used below is introduced here.
Use three sessions: remainders and gcd first; power cycles and integer equations next; then the exercises with your notes closed. Write an attempt before opening a hint. These are teaching examples and explanations prepared for this guide, not questions attributed to a past contest. Familiar elementary problems can occur in many books.
What does “modulo” mean?
For a positive integer m, division with remainder writes any integer a as a = mq + r, where q is an integer and 0 ≤ r < m. The number r is the remainder. For example, 17 = 5 × 3 + 2, so the remainder on division by 5 is 2. Negative integers follow the same rule: −1 = 5 × (−1) + 4, so its remainder is 4.
The statement a ≡ b (mod m), read “a is congruent to b modulo m”, means that m divides a − b. Equivalently, a and b have the same remainder. Thus 17 ≡ 2 (mod 5), but 17 and 2 are not equal. We write m ∣ a to mean that a = mk for some integer k. In particular, every positive integer divides 0.
You may add or multiply congruences with the same modulus. To see why, write a = b + mu and c = d + mv for integers u and v. Both (a + c) − (b + d) and ac − bd = m(bv + du + muv) are multiples of m. Repeated multiplication also permits positive integer powers. Division needs extra care; exercise 7 shows what can go wrong.
Worked example 1: which remainders can a square have?
Prove that a square cannot leave remainder 2 modulo 4. There are infinitely many integers, but only two parity cases: even and odd.
If n is even, write n = 2k for an integer k. Then n² = 4k², so the remainder is 0. If n is odd, write n = 2k + 1. Expanding gives n² = 4k² + 4k + 1 = 4k(k + 1) + 1, so the remainder is 1. Every integer belongs to one of these cases; no square can have remainder 2 or 3.
| Remainder of n modulo 4 | Remainder of n² modulo 4 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 0 |
| 3 | 1 |
This table covers whole remainder classes, not just the four numbers 0, 1, 2 and 3. If n ≡ r (mod 4), the multiplication rule gives n² ≡ r² (mod 4).
Use the obstruction. The equation x² = 4y + 2 has no integer solution: its left side has remainder 0 or 1, while its right side has remainder 2. A mismatch of necessary remainders is enough to prove impossibility. Matching remainders alone would not prove that a solution exists.
Worked example 2: Euclid’s algorithm, with its reason
The greatest common divisor, gcd(a,b), is the largest positive integer dividing both numbers, provided they are not both zero. For positive a and b, divide the larger by the smaller and repeat with the remainder.
To find gcd(252,198), use the following divisions:
- 252 = 1 × 198 + 54.
- 198 = 3 × 54 + 36.
- 54 = 1 × 36 + 18.
- 36 = 2 × 18 + 0.
The last nonzero remainder is 18, so the gcd is 18. Each nonzero remainder is smaller than the previous divisor, which is why the process eventually stops.
Why the gcd stays the same. If a = qb + r, every common divisor of a and b divides r = a − qb. Conversely, every common divisor of b and r divides a = qb + r. The pairs (a,b) and (b,r) therefore have exactly the same common divisors. At the last step, gcd(18,0) = 18.
Two integers are called coprime when their gcd is 1. If coprime positive integers a and b both divide a nonnegative integer N, then ab divides N. For N > 0, their prime factors do not overlap, and all the prime-power factors of both must occur in N. For N = 0, the conclusion follows from 0 = ab × 0. Without coprimality this can fail: 12 is divisible by 4 and 6, but not by 24.
Worked example 3: find the last digit without finding the power
Find the last digit of 72026. Last digits are remainders modulo 10. The first powers of 7 have last digits 7, 9, 3 and 1. More importantly, 7⁴ ≡ 1 (mod 10), so each further block of four factors contributes another factor congruent to 1.
Since 2026 = 4 × 506 + 2,
72026 = (7⁴)506 × 7² ≡ 1506 × 49 ≡ 9 (mod 10).
The last digit is therefore 9. We reduced the exponent using the proved cycle length 4, not the modulus 10. Writing down a few last digits becomes a proof only after explaining why the pattern repeats.
Worked example 4: find every allowed integer pair
Find all nonnegative integer pairs (x,y) satisfying 6x + 9y = 30. “Nonnegative” means x ≥ 0 and y ≥ 0, so zero is allowed.
First divide the equation by 3 to obtain 2x + 3y = 10. Reducing modulo 3 gives 2x ≡ 1 (mod 3). Multiplying both sides by 2 gives 4x ≡ 2 (mod 3), and 4 ≡ 1, so x ≡ 2 (mod 3).
Consequently x = 2 + 3t for some integer t. Substitute this into 2x + 3y = 10:
4 + 6t + 3y = 10, so y = 2 − 2t.
The condition x ≥ 0 requires t ≥ 0: any integer t ≤ −1 would make 2 + 3t negative. The condition y ≥ 0 requires t ≤ 1. Thus t is 0 or 1, giving (x,y) = (2,2) or (5,0). Both pairs satisfy the original equation: 12 + 18 = 30 and 30 + 0 = 30. Every possible solution led to one of these two values of t, so the list is complete.
If the problem had required positive integers, (5,0) would be excluded. State the domain before searching for solutions.
Nine exercises, from a single step to a combined proof
Exercises 1–4 practise one method. Exercises 5–7 ask you to choose or repair a method. Exercises 8–9 combine ideas. A correct numerical answer is not a substitute for a proof where the question asks for one.
1. A negative remainder
Find the remainder when −23 is divided by 5.
Hint for exercise 1
Write −23 = 5q + r with 0 ≤ r < 5.
Full solution to exercise 1
−23 = 5 × (−5) + 2. Since 0 ≤ 2 < 5, the remainder is 2. The expression 5 × (−4) − 3 equals −23 too, but −3 is not in the allowed remainder range.
Check your reasoning: The remainder is nonnegative even when the original integer is negative.
2. Add two square remainders
Prove that x² + y² = 4z + 3 has no integer solution.
Hint for exercise 2
Use the complete square-remainder list from worked example 1.
Full solution to exercise 2
Each of x² and y² has remainder 0 or 1 modulo 4. Their possible remainder sums are 0 + 0, 0 + 1, 1 + 0 and 1 + 1: these give only 0, 1 or 2. However, 4z + 3 always has remainder 3. The two sides cannot be equal, so there is no integer solution.
Check your reasoning: The list of cases covers all integers, including zero and negative integers.
3. Calculate a gcd
Find gcd(391,299), showing your divisions.
Hint for exercise 3
Continue Euclid’s algorithm until a remainder is zero.
Full solution to exercise 3
391 = 1 × 299 + 92; then 299 = 3 × 92 + 23; finally 92 = 4 × 23 + 0. The last nonzero remainder is 23. The common-divisor argument in worked example 2 gives gcd(391,299) = gcd(299,92) = gcd(92,23) = 23.
Check your reasoning: Do not stop after the first remainder; it need not divide both original numbers.
4. A stronger fact about odd squares
Prove that every odd integer n satisfies n² ≡ 1 (mod 8).
Hint for exercise 4
Write n = 2k + 1. After expanding, use the parity of k(k + 1).
Full solution to exercise 4
For an integer k, write n = 2k + 1. Then n² − 1 = 4k(k + 1). Of the consecutive integers k and k + 1, one is even. Thus k(k + 1) = 2s for an integer s, and n² − 1 = 8s. This proves n² ≡ 1 (mod 8).
Check your reasoning: Being divisible by 4 is not enough; the extra factor 2 comes from consecutive integers.
5. A power with a different cycle
Find the remainder when 32026 is divided by 7.
Hint for exercise 5
Find a positive power of 3 that is congruent to 1 modulo 7, then split the exponent into blocks.
Full solution to exercise 5
The remainders of 3¹, 3², 3³, 3⁴, 3⁵ and 3⁶ modulo 7 are 3, 2, 6, 4, 5 and 1. Since 2026 = 6 × 337 + 4, we have 32026 = (3⁶)337 × 3⁴ ≡ 1337 × 81 ≡ 4 (mod 7). The factor 3⁶ ≡ 1 justifies repeating the block.
Check your reasoning: Reduce the exponent modulo the verified cycle length, not automatically modulo 7.
6. A gcd for every n
For every positive integer n, prove gcd(5n + 2, 3n + 1) = 1.
Hint for exercise 6
Find an integer combination of the two expressions in which the n terms cancel.
Full solution to exercise 6
Let d be the positive gcd. Because d divides both expressions, it divides 3(5n + 2) − 5(3n + 1). Expanding gives 15n + 6 − 15n − 5 = 1. The only positive divisor of 1 is 1, so d = 1.
Check your reasoning: This argument rules out every common divisor greater than 1; a list of small n values would not.
7. Repair an invalid cancellation
A student cancels 2 in 2x ≡ 2 (mod 6) and concludes x ≡ 1 (mod 6). Give a counterexample and find all possible remainders of the integer x modulo 6.
Hint for exercise 7
Rewrite the original congruence as 6 ∣ 2(x − 1).
Full solution to exercise 7
Take x = 4. Then 2x = 8 ≡ 2 (mod 6), but 4 is not congruent to 1 modulo 6, so the proposed cancellation is invalid.
The original statement means 2(x − 1) = 6k for some integer k. Dividing this ordinary equality by 2 gives x − 1 = 3k. Thus x = 1 + 3k. If k is even, x has remainder 1 modulo 6; if k is odd, it has remainder 4. Both remainders work. The answer is 1 or 4, equivalently x ≡ 1 (mod 3).
Check your reasoning: Dividing the equality also divided the modulus. You cannot silently retain modulus 6.
8. A finite search from factorisation
Find all nonnegative integer pairs (x,y) satisfying x² − y² = 21.
Hint for exercise 8
Factorise the left side. What restrictions must x − y and x + y satisfy?
Full solution to exercise 8
Since the difference of squares is positive and x,y are nonnegative, x > y. Put u = x − y and v = x + y. Then u and v are positive integers, u ≤ v, and uv = 21. They also have the same parity, because v − u = 2y.
The positive factor pairs with u ≤ v are (1,21) and (3,7); both are odd pairs. Recover x = (u + v)/2 and y = (v − u)/2. This gives (x,y) = (11,10) or (5,2). Checking: 121 − 100 = 21 and 25 − 4 = 21. Every solution gives one of the listed factor pairs, so there are no others in the stated domain.
Check your reasoning: Factor pairs, sign restrictions and parity must all be checked before claiming a complete list.
9. Combine parity, remainders and coprimality
For a positive integer n, prove that 24 divides n² − 1 if and only if gcd(n,6) = 1.
Hint for exercise 9
For one direction, use exercise 4 and square remainders modulo 3. For the other, rule out factors 2 and 3 in n.
Full solution to exercise 9
First suppose gcd(n,6) = 1. Then n is odd and is not divisible by 3. Exercise 4 gives 8 ∣ (n² − 1). Modulo 3, the only possible remainders of n are 1 and 2, and both have square remainder 1. Thus 3 ∣ (n² − 1). Since 8 and 3 are coprime, their product 24 divides n² − 1.
Conversely, suppose 24 ∣ (n² − 1). If n were even, n² − 1 would be odd and could not be divisible by 24. If 3 divided n, then n² − 1 would have remainder 2 modulo 3, again impossible. So neither 2 nor 3 divides n. As these are the only prime factors of 6, gcd(n,6) = 1. Both directions are proved. The value n = 1 is included: 24 divides 0.
Check your reasoning: An “if and only if” statement needs both directions; the coprimality condition also matters when combining divisors.
Use your mistakes to choose the next lesson
- If exercise 1 was difficult, return to the definition and range of a remainder.
- If you could list examples but not prove exercises 2 or 4, revisit the exhaustive square-remainder argument.
- If exercises 3 or 6 stalled, review why common divisors survive an integer combination.
- If exercise 5 stalled, first prove the repeating block in the power-cycle example.
- If you found some answers but could not exclude others in exercise 8, review the parameter bounds in worked example 4.
- If exercise 9 had only one direction, use the proof-writing guide to separate what is assumed from what must be shown.
After reading a solution, close it and rewrite the reasoning. When you can explain the steps, continue to the three number-theory problems in the first proof plan, which introduce a divisibility proof, a variable gcd and descent. A short lesson does not establish readiness for a national final or the IMO.
Lesson expanded 24 September 2026. The topic map below separates core study from optional advanced methods.
Topic map and learning goals
| Unit | Core content | Advanced or extension content |
|---|---|---|
| Divisibility | Division algorithm, divisors, multiples, gcd and lcm | Useful divisibility lemmas and gcd manipulations |
| Primes and factorisation | Unique prime factorisation, coprimality, prime exponents | Valuations, factorial prime exponents and perfect-power arguments |
| Euclidean algorithm | Gcd calculation, Bézout identity | Linear Diophantine equations and parameterisation of solutions |
| Modular arithmetic | Congruences, residues, modular arithmetic operations, parity | Modular inverses, linear congruences and the Chinese remainder theorem |
| Powers modulo integers | Residue cycles, Fermat’s little theorem, Euler’s theorem | Multiplicative order and selected applications of primitive roots |
| Arithmetic functions | Divisor count and sum, Euler’s totient function | Multiplicativity and structured divisor problems |
| Diophantine equations | Factorisation, parity, modular obstructions, bounding | Infinite descent, Vieta jumping and selected Pell-type equations |
| Classical integer configurations | Pythagorean triples, squares and perfect powers | Parametrisation, coprimality restrictions and simultaneous constraints |
| Prime-exponent techniques | Comparing exponents in products and powers | Lifting the exponent in appropriate cases; careful attention to hypotheses |
| Digits and representation | Place value, digit sums, last digits, different bases | Constructing numbers with prescribed divisibility properties |
Learning outcomes: prove impossibility, find every integer solution, and account for positivity, zero, negative values and common factors. Congruence is not ordinary equality: cancellation modulo a composite number requires justification.
Suggested order: divisibility → gcd → prime factorisation → congruences → modular powers → Diophantine equations → advanced tools. Wilson’s theorem is useful knowledge, but repeated application of gcd and modular reasoning is usually a better first priority than collecting named theorems.