Week 10 · Part 1 — Powers, Cycles & Fast Exponentiation0%
STEP 1 OF 23 · Lesson Opening
Today: Powers, Cycles, Fast Exponentiation & the Square-mod-8 Filter
Four atomic skills that turn any "find \(a^n \pmod m\)" or "is this number a perfect square?" question into a one-line trick: cycle detection, period reduction, repeated squaring, and the square-mod-8 constraint. This is the Pass-2 deepening of Week 3's modular foundations.
What you will learn today
Topic
Modular arithmetic with powers — finding the period of \(a^n \pmod m\), reducing massive exponents, fast exponentiation by repeated squaring, and using the fact that \(n^2 \pmod 8 \in \{0,1,4\}\) to reject square candidates.
Category
Number Theory II (N1) — sub-topic Powers, Cycles & Fast Exponentiation.
Solves these AIMO problems
2002 Q32013 Q42005 Q5
Three real past papers — modular reasoning + prime enumeration, prime modular elimination, and last-three-digits via inverses.
AoPS Reference
Introduction to Number Theory by Mathew Crawford, Chapters 11-13 — Modular Arithmetic, Modular Powers, and Fermat / Euler theorems. Also AoPS Wiki "Modular Exponentiation".
Why this matters
In Week 3 you learned how arithmetic behaves modulo \(m\). Today you weaponise it: any "what is \(7^{123}\) mod 100?" or "show 1234567 is not a square" reduces to a 30-second mechanical procedure. The square-mod-8 filter alone solves an entire class of olympiad problems on the first line.
Time required
About 90-110 minutes for the full lesson, plus 30 minutes practising the AIMO past papers afterwards.
Bridge from Week 3: In W3 you proved that \((a+b) \bmod n\) and \((ab) \bmod n\) factor through the residue, that \(\gcd\) survives subtraction, and that the Chinese Remainder Theorem stitches mod-5 and mod-7 together. Today we go one Pass deeper: instead of single operations, we iterate \(a^n\) and use the fact that residues cycle. Same modulus, sharper tool.
Phase 0 (Step 3): Pass-2 prerequisites — modular equality, Fermat's Little Theorem, gcd as period gate.
Phase 1 (Steps 4-5): Visual intuition — the clock-arrow picture of \(3^n \bmod 7\), the period wheel, and "last \(k\) digits = mod \(10^k\)".
Phase 1.5 (Step 6): Formula handbook — period reduction, repeated squaring, 1000 = 8·125 split, square-mod-8 filter.
Phase 2 (Steps 7-8): Two derivations — why \(a^n\) eventually cycles, and why \(n^2 \bmod 8 \in \{0,1,4\}\).
Phase 3 (Steps 9-13): Five Worked Examples (⭐⭐ → ⭐⭐⭐⭐⭐).
Phase 4 (Step 14): Five practice problems P1-P5 with hints and answer reveals.
Phase 5 (Steps 15-17): Three real AIMO past papers — 2002 Q3, 2013 Q4, 2005 Q5 — in exam format with the 5-step Observe / Strategy / Hint / answer-input / Show-full framework.
Phase 5.5 (Step 18): Synthesis — \(2^{2026} \bmod 100\) using period + CRT.
Phase 6 (Steps 19-20): Atomic-skill matrix + four micro-validation drills.
Step 21: Cheat sheet.
Step 22: Atomic-skill self-rating.
Step 23: Bridge to Part 2 (CRT, Fermat & Inverses).
Pedagogical note: Most students panic when they see "\(7^{123}\)" — but the cycle is always tiny (often \(\le \varphi(m)\)). The mantra is: compute the first few powers, spot the period, reduce the exponent. That sequence solves 80% of olympiad modular-power questions.
STEP 2 OF 23 · Phase 0.5 · Week 3 Skill Drill
Phase 0.5 — Recall drill from Week 3
Ten rapid-fire questions on the Number Theory I atomic skills you need today. Aim for ≥ 7 / 10 before moving on. Wrong answers feed your error-book automatically.
Drill — recall from Number Theory I (Week 3)
Each card targets one atomic skill from the W3 modular-arithmetic roster. Type a number, click Check. The summary at the bottom updates live.
D1 · N1-A1 mod sum
\((17 + 25) \bmod 7 = ?\)
D2 · N1-A1 mod product
\((7 \times 8) \bmod 5 = ?\)
D3 · N1-A2 digit-sum mod 9
\(100 \bmod 9 = ?\) (hint: digit sum)
D4 · N1-A4 small power
\(2^{10} \bmod 11 = ?\) (Fermat)
D5 · N1-A3 large mod
\(113744 \bmod 1125 = ?\)
D6 · N1-A5 gcd via subtraction
\(\gcd(113744 - 119,\ 109417 - 292) = ?\)
D7 · N1-A6 factorial mod
\(5! \bmod 7 = ?\) (\(5! = 120\))
D8 · N1-A7 CRT pair
Smallest \(a > 0\) with \(a \equiv 3 \pmod 5\) and \(a \equiv 2 \pmod 7\). \(a = ?\)
D9 · N1-A1 sum then mod
\((57 + 86) \bmod 13 = ?\)
D10 · N1-A4 strategy
For \(a^k \bmod m\), the first thing you compute is the period. Period of \(2^n \bmod 7\) (smallest \(d>0\) with \(2^d \equiv 1\)). \(d = ?\)
Score: 0 / 10 — answer the cards above.
STEP 3 OF 23 · Phase 0 · Pass-2 Prerequisites
Phase 0 — Three ideas you must own before powers
Three prerequisites: (1) modular equality is an equivalence relation, (2) Fermat's Little Theorem (FLT), (3) a "period" is the smallest exponent that returns to 1.
Prereq 1 — Modular equality and substitution
If \(a \equiv a' \pmod m\) and \(b \equiv b' \pmod m\), then:
\(a + b \equiv a' + b' \pmod m\)
\(a \cdot b \equiv a' \cdot b' \pmod m\)
\(a^k \equiv (a')^k \pmod m\) for any \(k \in \mathbb{Z}_{\ge 0}\)
This is what lets you replace a giant number by its tiny residue before raising to a power. Example: \(123^5 \bmod 7\). Since \(123 = 17 \cdot 7 + 4\), \(123 \equiv 4\). So \(123^5 \equiv 4^5 = 1024 \equiv 2 \pmod 7\).
Prereq 2 — Fermat's Little Theorem (FLT)
If \(p\) is prime and \(\gcd(a, p) = 1\):
\(a^{p-1} \equiv 1 \pmod p\)
Equivalently \(a^p \equiv a \pmod p\) for all integers \(a\). This is the fast lane: any prime modulus has period dividing \(p-1\).
Example: \(2^{10} \equiv 1 \pmod{11}\) because \(11\) is prime. So \(2^{2024} \equiv 2^{2024 \bmod 10} = 2^4 = 16 \equiv 5 \pmod{11}\).
Prereq 3 — The period (multiplicative order)
For \(\gcd(a, m) = 1\), the period of \(a\) modulo \(m\) is the smallest positive \(d\) such that \(a^d \equiv 1 \pmod m\). Notation: \(\operatorname{ord}_m(a) = d\).
The sequence \(a^0, a^1, a^2, \dots\) cycles with period \(d\): \(a^n \equiv a^{n \bmod d} \pmod m\).
Key takeaway: "Find the period first" — once you know \(d\), the giant exponent \(n\) becomes the tiny remainder \(n \bmod d\). Every power-mod problem is "find \(d\), then reduce".
STEP 4 OF 23 · Phase 1 · Visual Intuition (1/2)
Phase 1 — The clock-arrow picture of \(3^n \bmod 7\)
Watch how successive powers of 3 cycle through the residues \(\{1,2,3,4,5,6\}\) modulo 7. The arrow lands on each residue exactly once before returning home.
The residues of \(3^n \bmod 7\) cycle: \(1 \to 3 \to 2 \to 6 \to 4 \to 5 \to 1\). Six distinct residues, then repeat — the period is \(d = 6 = \varphi(7) = 7 - 1\). So \(3\) is a primitive root mod 7.
Read this picture: Each step multiplies by 3 and reduces mod 7. After 6 steps you are back to 1. So \(3^{100} \equiv 3^{100 \bmod 6} = 3^4 \equiv 4 \pmod 7\). The exponent 100 collapses to 4 — that is the entire trick.
STEP 5 OF 23 · Phase 1 · Visual Intuition (2/2)
Period wheel and "last \(k\) digits = mod \(10^k\)"
Two more visuals: a period-wheel showing how \(7^n \bmod 10\) repeats every 4 steps, and the bookkeeping picture that "the last \(k\) digits of \(N\)" equals \(N \bmod 10^k\).
The last digit of \(7^n\) cycles through \(7, 9, 3, 1\) with period 4. So the last digit of \(7^{100}\) is the last digit of \(7^{100 \bmod 4} = 7^0\)? Careful: the cycle starts at \(n=1\), and \(7^4 \equiv 1\), so \(7^{100} = 7^{4 \cdot 25} \equiv 1^{25} = 1\). Last digit = 1.
"What are the last \(k\) digits of \(7^{123}\)?" is exactly the same question as "compute \(7^{123} \bmod 10^k\)". Choose the right modulus and the question becomes mechanical.
STEP 6 OF 23 · Phase 1.5 · Formula Handbook
Phase 1.5 — The five-formula handbook
Memorise these five lines. Every problem in today's set reduces to one (or a combination) of them.
So squares hit only 3 of the 8 residues — five are forbidden. Compute \(N \bmod 8\) FIRST, before any other approach.
STEP 7 OF 23 · Phase 2 · Derivation 1
Why \(a^n \bmod m\) eventually cycles
A pigeonhole argument plus an invertibility check. This is the proof you should be able to write in 60 seconds.
Setup
Fix \(a\) and \(m\) with \(\gcd(a,m)=1\). Consider the infinite sequence of residues:
\(a^0,\ a^1,\ a^2,\ a^3,\ \dots \pmod m\).
Each entry is one of the \(m\) possible residues \(\{0, 1, \dots, m-1\}\). So among the first \(m+1\) entries, by the pigeonhole principle, two must agree:
\(a^i \equiv a^j \pmod m\), with \(0 \le i < j \le m\).
Cancel \(a^i\) using invertibility
Because \(\gcd(a,m)=1\), \(a\) has a multiplicative inverse mod \(m\). Multiply both sides by \(a^{-i}\):
\(1 \equiv a^{j-i} \pmod m\).
Set \(d = j - i > 0\). Then \(a^d \equiv 1\), and the smallest such \(d\) is the period \(\operatorname{ord}_m(a)\).
Why the cycle has length exactly \(d\)
For any \(n \ge 0\), write \(n = qd + r\) with \(0 \le r < d\). Then:
So the sequence is periodic with period dividing \(d\); minimality of \(d\) gives equality.
Take-away: The sequence \(a^n \bmod m\) is eventually (in fact, immediately, when \(\gcd(a,m)=1\)) periodic, and the period \(d\) divides \(\varphi(m)\). Computing the first \(d \le \varphi(m)\) powers always finds it.
STEP 8 OF 23 · Phase 2 · Derivation 2
Why \(n^2 \bmod 8 \in \{0, 1, 4\}\)
A two-case proof. Memorise the cases — this single fact rejects the majority of "is it a square?" candidates instantly.
Case 1 · \(n\) is even
Write \(n = 2k\). Then:
\(n^2 = 4k^2.\)
Sub-case 1a: \(k\) is even, \(k = 2\ell\). Then \(n^2 = 16\ell^2 \equiv 0 \pmod 8\).
Sub-case 1b: \(k\) is odd. Then \(k^2\) is odd, so \(4k^2 \equiv 4 \pmod 8\).
Case 2 · \(n\) is odd
Write \(n = 2k+1\). Then:
\(n^2 = 4k^2 + 4k + 1 = 4k(k+1) + 1.\)
Now \(k(k+1)\) is the product of consecutive integers, so it is even. Therefore \(4k(k+1) \equiv 0 \pmod 8\), and:
\(n^2 \equiv 1 \pmod 8.\)
Conclusion
\(n^2 \bmod 8 \in \{0,\ 1,\ 4\}\)
Forbidden residues: 2, 3, 5, 6, 7
Common slip: Don't confuse with \(\bmod 4\), where squares are \(\{0, 1\}\). The mod-8 filter is strictly sharper — it rejects more candidates. Always go to mod 8 first.
Pattern: If a problem asks "is \(N\) a square?" or "find squares with property X", compute \(N \bmod 8\) on line 1. If the residue is in \(\{2,3,5,6,7\}\), you are done — no further work.
STEP 9 OF 23 · Phase 3 · Worked Example 1
WE 1 — Last digit of \(7^{100}\)
⭐⭐ — Direct application of period reduction. Find the period of 7 mod 10, then reduce the exponent.
WE 1 · ⭐⭐ · M1-A1 + M1-A2
Question. What is the last digit of \(7^{100}\)?
Try it first. Compute the first few powers of 7 mod 10, spot the period, then reduce 100.
"Last digit" = "mod 10". So compute \(7 \bmod 10, 7^2 \bmod 10, 7^3 \bmod 10, \dots\) until you return to the start.
The sequence is \(7, 9, 3, 1, 7, 9, 3, 1, \dots\) — period 4. Now use \(100 \bmod 4\).
Your answer (last digit)
Answer: 1
Strategy
Reduce the exponent using the period of \(7 \bmod 10\).
Notice the trap: \(100 \bmod 4 = 0\) does not mean exponent 0; it means we landed back on \(7^4 \equiv 1\). Either reading gives the right answer here, but in general "exponent 0" should be replaced with "exponent \(d\)" (= 1 by definition).
STEP 10 OF 23 · Phase 3 · Worked Example 2
WE 2 — \(3^{200} \bmod 7\)
⭐⭐⭐ — Combine FLT with the period-reduction recipe.
WE 2 · ⭐⭐⭐ · M1-A1 + M1-A2 (with FLT)
Question. Compute \(3^{200} \bmod 7\).
Use Fermat's Little Theorem to find the period, then reduce 200.
Since 7 is prime and \(\gcd(3,7)=1\), FLT gives \(3^6 \equiv 1 \pmod 7\). So the period divides 6.
Compute \(200 \bmod 6 = ?\). Then square that small power.
Your answer (residue 0-6)
Answer: 2
Strategy
FLT gives \(3^6 \equiv 1\). Reduce 200 modulo 6, then compute the small power.
Step 1 — Apply FLT
\(7\) prime, \(\gcd(3,7)=1 \implies 3^6 \equiv 1 \pmod 7\) (period \(d \mid 6\)).From the cycle \(3,2,6,4,5,1\) we confirm \(d = 6\) (3 is a primitive root mod 7).
When the modulus is prime, FLT gives the period for free as a divisor of \(p-1\). The actual period might be smaller — but reducing modulo \(p-1\) is always safe.
STEP 11 OF 23 · Phase 3 · Worked Example 3
WE 3 — \(7^{123} \bmod 100\) by fast exponentiation
⭐⭐⭐⭐ — A demonstration of repeated squaring. The exponent doubles each step until you cover 123.
WE 3 · ⭐⭐⭐⭐ · M1-A3 fast exponentiation
Question. Compute \(7^{123} \bmod 100\) (i.e. the last two digits of \(7^{123}\)).
Square repeatedly. Compute \(7^2, 7^4, 7^8, \dots\) until you can build 123 from these blocks.
Whenever you spot \(a^k \equiv 1\) for a small \(k\), you have the period — stop squaring and reduce. Repeated squaring is the engine; period detection is the steering wheel.
STEP 12 OF 23 · Phase 3 · Worked Example 4
WE 4 — Show 1234567 is not a perfect square
⭐⭐⭐⭐ — The square-mod-8 filter. One line of work.
WE 4 · ⭐⭐⭐⭐ · M1-A4 square-mod-8
Question. Prove that \(N = 1{,}234{,}567\) is not a perfect square.
Compute \(N \bmod 8\) and compare to \(\{0, 1, 4\}\).
You only need the last 3 digits to find \(N \bmod 8\), since \(1000 \equiv 0 \pmod 8\). So \(N \equiv 567 \pmod 8\).
\(567 = 8 \cdot 70 + 7\), so \(N \equiv 7 \pmod 8\). Is 7 in \(\{0,1,4\}\)?
Type the value of \(N \bmod 8\)
Answer: \(N \bmod 8 = \mathbf{7}\). Since \(7 \notin \{0,1,4\}\), \(N\) is not a square.
Strategy
Use the fact \(n^2 \bmod 8 \in \{0,1,4\}\). If \(N \bmod 8\) is anything else, \(N\) is not a square.
None of \(2^1, 2^2, 2^4, 2^5, 2^{10}\) are \(\equiv 1\). So \(d = 20\).
\(\operatorname{ord}_{25}(2) = 20\)
The trick \(2^{10} \equiv -1\) is gold: it instantly tells you the period is exactly twice 10. Whenever you find \(a^k \equiv -1\), the period is exactly \(2k\).
STEP 14 OF 23 · Phase 4 · Practice P1-P5
Practice — five problems mixing M1-A1 to M1-A4
Try each on paper first. Hints, then answer, then full solution.
P1 · M1-A1 last digit ⭐⭐
P1. What is the last digit of \(3^{2024}\)?
Period of \(3 \bmod 10\) is 4 (cycle \(3, 9, 7, 1\)). Reduce 2024 mod 4.
1
\(3^1=3, 3^2=9, 3^3=27\equiv 7, 3^4=81\equiv 1\). Period 4. \(2024 = 4 \cdot 506\), so \(2024 \bmod 4 = 0\). \(3^{2024} = (3^4)^{506} \equiv 1\). Last digit = 1.
P2 · M1-A2 large exponent reduction ⭐⭐⭐
P2. Compute \(5^{1000} \bmod 13\).
FLT: \(5^{12} \equiv 1 \pmod{13}\). Reduce 1000 mod 12.
P3. Find \(11^{50} \bmod 100\) (last two digits of \(11^{50}\)).
Use the binomial expansion: \(11 = 10 + 1\), so \(11^{50} = (1+10)^{50}\). Only terms with \(10^0\) and \(10^1\) survive mod 100.
01
By the binomial theorem, \((1+10)^{50} = \sum \binom{50}{k} 10^k\). Mod 100, only \(k=0\) (giving 1) and \(k=1\) (giving \(50 \cdot 10 = 500 \equiv 0\)) survive (\(k\ge 2\) contribute multiples of 100). So \(11^{50} \equiv 1 + 0 \equiv 1 \pmod{100}\). Last two digits: 01.
P4 · M1-A4 square-mod-8 ⭐⭐⭐
P4. Show that no perfect square ends in the digits \(\dots\,38\).
If \(N\) ends in 38, then \(N \equiv 38 \pmod{100}\), so \(N \bmod 8\) depends on \(38 \bmod 8\). Compute it.
\(38 \equiv 6 \pmod 8 \notin \{0,1,4\}\), so impossible.
Since \(100 \equiv 4 \pmod 8\), we have \(N \equiv 38 \pmod{100} \implies N \equiv 38 \pmod 4 \equiv 2 \pmod 4\). For mod 8: \(38 = 4 \cdot 8 + 6\), and we need to check whether \(N\) could equal \(100k + 38\) for some \(k\). \(100k + 38 \equiv 4k + 6 \pmod 8\), which is \(6, 2, 6, 2, \dots\) — always in \(\{2, 6\}\). Neither is in \(\{0,1,4\}\). So no perfect square ends in 38. ✓
P5 · combined ⭐⭐⭐⭐⭐
P5. Find the last two digits of \(7^{2026}\).
From WE 3, \(7^4 \equiv 1 \pmod{100}\). Reduce 2026 mod 4.
49
Period of \(7 \bmod 100\) is 4 (since \(7^4 = 2401 \equiv 1\)). \(2026 = 4 \cdot 506 + 2\), so \(2026 \bmod 4 = 2\). \(7^{2026} \equiv 7^2 = 49 \pmod{100}\). Last two digits: 49.
STEP 15 OF 23 · Phase 5 · AIMO Past Paper 1
AIMO 2002 Q3 — Three consecutive integers, geometric progression
3 marks · ⭐⭐⭐ · Tests M1-A1 (modular reasoning) + prime enumeration / divisor walk.
AIMO 2002 · Q3 · 3 marks
Start with three consecutive positive integers. Leave the first unchanged, add 10 to the second, and add a prime to the third. The three numbers are now in geometric progression, i.e. they are of the form \(a,\ ar,\ ar^2\). What was the prime number added to the third of the consecutive integers?
Step 1 · Observe (5 sub-steps)
关键词识别 · Keywords
"Three consecutive integers", "geometric progression", "prime". GP means middle² = first · third.
已知量 · Knowns
First integer \(n\); second \(n+1\); third \(n+2\). After modification: \(n,\ n+11,\ n+2+p\) form a GP, with \(p\) prime.
未知量 · Unknown
The prime \(p\). (Bonus: the integer \(n\), but the question only asks for \(p\).)
中间量 · Middle quantity
The GP equation \((n+11)^2 = n(n+2+p)\) — a single equation in two unknowns, but constrained by \(p\) being prime.
隐藏约束 · Hidden constraint
\(n\) must be a positive integer; \(p\) must be prime; the algebra forces \(n \mid 121\), giving only three candidates.
Step 2 · Strategy
Plan
Write the GP condition algebraically. Simplify until one variable is expressible in terms of the other. Then enumerate divisors and test primality.
Why-general · Pattern
The recipe
"GP condition + divisibility = small finite list of candidates" — same trick whenever you have \(b^2 = ac\) plus integer/prime constraints. Always rearrange to p = (linear expr)/n, then \(n\) divides the constant term.
Your answer (the prime)
Hints (use only when stuck)
Hint 1 · Set up the GP equation
Let the original three be \(n, n+1, n+2\). After: \(n, n+11, n+2+p\). GP \(\Rightarrow (n+11)^2 = n(n+2+p)\).
For \(p\) to be a positive integer we need \(n \mid 121 = 11^2\). So \(n \in \{1, 11, 121\}\):
\(n = 1: p = 20 + 121 = 141 = 3 \cdot 47\) — not prime.\(n = 11: p = 20 + 11 = 31\) — prime ✓\(n = 121: p = 20 + 1 = 21 = 3 \cdot 7\) — not prime.
Verification with \(n = 11\): the three numbers are \(11, 22, 44\), with common ratio \(r = 2\). Indeed \(22 = 12 + 10\) and \(44 = 13 + 31\). ✓
\(p = 31\)
Why this question? It rewards two atomic skills: the algebraic manipulation that produces \(p = 20 + 121/n\) (a "divisor walk" set-up), and the disciplined enumeration of three cases. Modular reasoning sits in the background — \(n \mid 121\) is exactly "the residue of \(121\) mod \(n\) is zero".
STEP 16 OF 23 · Phase 5 · AIMO Past Paper 2
AIMO 2013 Q4 — Three primes \(p, q, r\) satisfying two equations
3 marks · ⭐⭐⭐ · Prime modular elimination + system reduction.
AIMO 2013 · Q4 · 3 marks
The prime numbers \(p, q, r\) satisfy the equations \(pq + pr = 80\) and \(pq + qr = 425\). Find the value of \(p + q + r\).
Step 1 · Observe (5 sub-steps)
关键词识别 · Keywords
"Prime numbers" — small, tightly constrained. Two linear equations in three unknowns, but with primality the system is over-determined.
The three primes \(p, q, r\), and ultimately their sum.
中间量 · Middle quantity
Divisibility constraints: \(p \mid 80\) and \(q \mid 425\). Since \(p, q\) are prime, this gives a tiny candidate list.
隐藏约束 · Hidden constraint
\(r\) must also be prime (and positive). After fixing \(p, q\), check \(r\) directly.
Step 2 · Strategy
Plan
Factor the LHS of each equation. The divisibility \(p \mid 80\) and \(q \mid 425\) forces \(p \in \{2, 5\}\) and \(q \in \{5, 17\}\). Test the four pairs, solve for \(r\), check primality.
Why-general · Pattern
The recipe
"Prime + divisibility = enumerate". Whenever a prime divides a small number, it is one of a handful of primes — list them.
Your answer (\(p + q + r\))
Hints (use only when stuck)
Hint 1 · Factor the LHS
\(p(q+r) = 80\) and \(q(p+r) = 425\). Read off the divisibility: \(p \mid 80\) and \(q \mid 425\).
Hint 2 · Prime divisors
Primes dividing 80 = \(2^4 \cdot 5\): only 2 and 5. Primes dividing 425 = \(5^2 \cdot 17\): only 5 and 17.
Hint 3 · Test the four pairs
Try \((p, q) \in \{(2,5), (2,17), (5,5), (5,17)\}\). Solve for \(r\) from the first equation, check the second + primality of \(r\).
Method check:
Full Solution
Factor: \(p(q+r) = 80\) and \(q(p+r) = 425\). Hence \(p \mid 80\) and \(q \mid 425\). Since \(p, q\) are prime:
\((p,q)=(2,5):\) \(2(5+r)=80 \Rightarrow r = 35 = 5 \cdot 7\), not prime. ✗\((p,q)=(2,17):\) \(2(17+r)=80 \Rightarrow r = 23\), prime. Check: \(17(2+23)=17\cdot 25 = 425\) ✓\((p,q)=(5,5):\) \(5(5+r)=80 \Rightarrow r = 11\). Check: \(5(5+11) = 80 \neq 425\). ✗\((p,q)=(5,17):\) \(5(17+r)=80 \Rightarrow r = -1\), not prime. ✗
Only \((p,q,r) = (2, 17, 23)\) works. Sum:
\(p + q + r = 2 + 17 + 23 = 42\)
Why this question? The algebraic move is just factoring out \(p\) and \(q\). The real work is the disciplined enumeration of \(2 \times 2 = 4\) cases — checking primality each time. This is the modular-arithmetic mindset applied to a system: every constraint shrinks the candidate list.
STEP 17 OF 23 · Phase 5 · AIMO Past Paper 3
AIMO 2005 Q5 — All-3 number divisible by 383
3 marks · ⭐⭐⭐ · Modular inverse + last-3-digits via mod-1000.
AIMO 2005 · Q5 · 3 marks
A positive integer \(n\) is such that its only digits are 3s, and such that \(383 \mid n\). When \(n / 383\) is divided by 1000, what is the remainder?
Step 1 · Observe (5 sub-steps)
关键词识别 · Keywords
"Only digits are 3s" — repunit times 3. "Divided by 1000" — last three digits.
已知量 · Knowns
\(n = \underbrace{33\dots3}_{k\text{ threes}} = 3 \cdot \dfrac{10^k - 1}{9} = \dfrac{10^k - 1}{3}\). Also 383 is prime.
未知量 · Unknown
\((n / 383) \bmod 1000\). Note we do NOT need to find \(k\) or compute \(n/383\) directly.
中间量 · Middle quantity
Let \(m = n/383\). Then \(383 \cdot m = n\), so \(383 m \equiv n \pmod{1000}\). And \(n \bmod 1000 = 333\) (last three digits are 333 once \(n\) has \(\ge 3\) digits).
隐藏约束 · Hidden constraint
\(\gcd(383, 1000) = 1\), so 383 has a multiplicative inverse mod 1000. Find it.
Step 2 · Strategy
Plan
(1) Recognise \(n \equiv 333 \pmod{1000}\). (2) Solve the congruence \(383 m \equiv 333 \pmod{1000}\) by computing \(383^{-1} \bmod 1000\). (3) Multiply.
Why-general · Pattern
The recipe
"Last \(k\) digits of a quotient = (last \(k\) digits of dividend) × (inverse of divisor) mod \(10^k\)". Whenever you need the tail of \(N/d\) without computing \(N\), invert \(d\) modulo \(10^k\).
Your answer (remainder, 0-999)
Hints (use only when stuck)
Hint 1 · Last three digits of \(n\)
Since \(n\) is at least a 3-digit number of all 3s, \(n \equiv 333 \pmod{1000}\).
Hint 2 · Set up a congruence
Let \(m = n/383\). Then \(383 m \equiv 333 \pmod{1000}\). Solve for \(m \bmod 1000\).
Hint 3 · Invert 383 mod 1000
Find \(x\) with \(383 x \equiv 1 \pmod{1000}\). Try \(x = 47\): \(383 \cdot 47 = 18001 = 18 \cdot 1000 + 1\). ✓ So \(383^{-1} \equiv 47\).
\(n = \underbrace{333\dots 3}_{k}\) consists only of 3s. For any \(k \ge 3\), the last three digits are \(333\), so \(n \equiv 333 \pmod{1000}\). (Such \(k\) exists because some power \(10^k \equiv 1 \pmod{383}\) by Fermat, then \(n = (10^k - 1)/3\) is divisible by 383 since \(\gcd(383, 3) = 1\).)
Step 2 — Set up the congruence.
Let \(m = n/383\). Then \(n = 383 m\), so:
\(383 m \equiv n \equiv 333 \pmod{1000}\).
Step 3 — Find \(383^{-1} \bmod 1000\).
We need \(x\) with \(383 x \equiv 1 \pmod{1000}\). Try \(x = 47\):
Why this question? A beautiful demonstration that you never need the explicit value of \(n\) — only its residue. Modular arithmetic short-circuits a problem that looks like it requires a 100+ digit computation.
STEP 18 OF 23 · Phase 5.5 · Synthesis
Synthesis — Compute \(2^{2026} \bmod 100\)
A combined exercise: \(\gcd(2, 100) \neq 1\) blocks the direct-period approach. Use the CRT split \(100 = 4 \cdot 25\), then invoke Euler.
SYN · ⭐⭐⭐⭐⭐ · M1-A1 + M1-A2 + CRT
Question. Find the last two digits of \(2^{2026}\) (i.e. \(2^{2026} \bmod 100\)).
The naive "find period of 2 mod 100" runs into trouble because \(\gcd(2, 100) = 2\). Use \(100 = 4 \cdot 25\) (CRT) — handle each prime power separately, then stitch.
Compute \(2^{2026} \bmod 4\) directly: for any \(n \ge 2\), \(2^n \equiv 0 \pmod 4\).
For \(\bmod 25\): \(\gcd(2, 25) = 1\), so Euler gives \(2^{20} \equiv 1\). Reduce \(2026 \bmod 20\).
Combine via CRT: find \(x\) with \(x \equiv 0 \pmod 4\) and \(x \equiv 14 \pmod{25}\). Try \(x = 14, 39, 64, 89\) and find the one divisible by 4.
Your answer (last two digits, 0-99)
Answer: 64
Strategy
Split \(100 = 4 \cdot 25\). Compute \(2^{2026} \bmod 4\) and \(2^{2026} \bmod 25\) separately, then stitch by CRT.
Step 1 — Mod 4 part (trivial)
For \(n \ge 2\), \(2^n \equiv 0 \pmod 4\). Since \(2026 \ge 2\):\(2^{2026} \equiv 0 \pmod 4\). CRT condition #1
\(2^{2026} \equiv 64 \pmod{100}\) — last two digits = 64
CRT lets you ignore the gcd issue. Whenever \(\gcd(a, m) \ne 1\), split \(m\) into prime powers, treat each separately, then stitch. The mod-25 Euler step is doing all the heavy lifting.
STEP 19 OF 23 · Phase 6 · Atomic Skill Matrix
The four atomic skills, mapped
Each skill has a one-line trigger phrase, a one-line method, and a worked-example pointer.
ID
Skill
Trigger
Method
WE / AIMO
M1-A1
Find period of \(a^n \bmod m\)
"\(a^n\)" with \(\gcd(a,m)=1\)
Compute \(a, a^2, \dots\) until you hit 1; period \(d \mid \varphi(m)\).
WE 1, WE 2, WE 5, AIMO 2002 Q3
M1-A2
Reduce large exponent
"\(a^{N}\)" with \(N\) huge
Once period \(d\) known: \(a^N \equiv a^{N \bmod d}\).
WE 1, WE 2, P5, Synthesis
M1-A3
Fast exponentiation by squaring
No obvious period; \(N\) large
Compute \(a^2, a^4, a^8, \dots\) mod \(m\); combine using binary expansion of \(N\).
WE 3, P3
M1-A4
Square-mod-8 filter
"Is \(N\) a square?"
Compute \(N \bmod 8\); if \(\notin \{0,1,4\}\), reject.
WE 4, P4
How they chain: Real problems use 2-3 of these in sequence. AIMO 2005 Q5 = M1-A2 + modular inverse. Synthesis = M1-A1 + M1-A2 + CRT. Build the chain by asking: "do I have a period? do I need it? am I screening squares?"
STEP 20 OF 23 · Phase 6 · Micro-Validation Drills
Four micro-validations — one per atomic skill
Tiny questions that confirm you can fire each atomic skill in isolation. Each is one numeric input.
MV1 · M1-A1 (period)
Find the period of \(2^n \bmod 9\). (i.e. smallest \(d > 0\) with \(2^d \equiv 1\).)
MV2 · M1-A2 (reduce)
Given that \(3^4 \equiv 1 \pmod{10}\), compute \(3^{2025} \bmod 10\).
MV3 · M1-A3 (squaring)
Compute \(13^2 \bmod 100\). (One step of repeated squaring.)
MV4 · M1-A4 (square filter)
Compute \(2{,}013{,}013 \bmod 8\). (If not in \(\{0,1,4\}\) it cannot be a perfect square.)
Your error book — Week 10 Part 1
Your wrong answers from drills, micro-validations, WEs, and AIMO problems will appear here. Use it for tomorrow's revision.
STEP 21 OF 23 · Cheat Sheet
One-page cheat sheet — Modular Powers
Print or screenshot this card. Take it into your next practice session.
Period reduction (M1-A1, M1-A2)
If \(\operatorname{ord}_m(a) = d\), then \(a^n \equiv a^{n \bmod d} \pmod m\).
Find \(d\) by computing the first \(\le \varphi(m)\) powers, or by knowing \(d \mid \varphi(m)\). For prime \(p\): use FLT, \(a^{p-1} \equiv 1\).
Fast exponentiation (M1-A3)
\(a^{2k} = (a^k)^2,\quad a^{2k+1} = a \cdot (a^k)^2\) — reduce mod \(m\) at every step.
Convert \(n\) to binary, square through, multiply at every 1-bit. Cost: \(O(\log n)\) multiplications.
Last digits
last \(k\) digits of \(N\) = \(N \bmod 10^k\).
Last 1: mod 10. Last 2: mod 100. Last 3: mod 1000. Combine with period reduction.
You now own four mechanical tools for any "compute \(a^n \bmod m\)" or "is this a square" question. Part 2 turns these into the deeper structural theorems.
Coming up — Part 2 (CRT + Inverses + Wilson): we generalise today's "1000 = 8 × 125" trick to the full Chinese Remainder Theorem (any two coprime moduli stitch into a unique answer). We then prove and apply Wilson's theorem (\((p-1)! \equiv -1 \pmod p\)) and build the modular-inverse algorithm via Extended Euclidean. By end of Part 2 you can solve any AIMO-level Diophantine system mod \(N\) in under 5 minutes.
Today's takeaways — one paragraph each
Period detection (M1-A1). Every \(a^n \bmod m\) (with \(\gcd(a,m)=1\)) cycles. Compute the first few powers; the moment you see 1, you have the period \(d\). \(d\) always divides \(\varphi(m)\) (FLT/Euler upper bound).
Period reduction (M1-A2). A massive exponent \(N\) becomes the tiny remainder \(N \bmod d\). This is the single most useful collapse in all of competition number theory.
Fast squaring (M1-A3). When the period is unhelpful (e.g. you don't know it), squaring halves the exponent each step. Always reduce mod \(m\) after every multiplication.
Square-mod-8 (M1-A4). The filter \(n^2 \bmod 8 \in \{0, 1, 4\}\) reject 5 out of 8 residue classes instantly. Always run this on line 1 of a "is N a square" question.
Practice plan tonight: Re-do the three AIMO problems (Q3 / Q4 / Q5) cold, no hints. Aim for under 4 minutes each. Tomorrow we open Part 2.
AIMO Tutor — Modular Powers (Week 10 Part 1)
Quick reminders: The mantra is "find period \(d\), then reduce exponent". For prime modulus \(p\): \(d \mid (p-1)\) by FLT. For prime power \(p^k\): \(d \mid \varphi(p^k) = p^{k-1}(p-1)\). For square detection: compute \(N \bmod 8\) on line 1.
Stuck on an AIMO problem? Open the right-column hints in order — Hint 1 is usually the algebraic set-up, Hint 2 is the divisibility/period, Hint 3 is the finish. Reveal the full solution only after writing something on paper.