Euclidean Algorithm is the habit of repeatedly replacing pairs by remainders to compute gcds and solve linear combinations. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.
$$\gcd(a, b) = \gcd(b, \; a \bmod b) \quad (b \neq 0)$$
Replacing the larger number by its remainder against the smaller one preserves the gcd, so repeating the step quickly drives the pair down to the answer.
Why It Works
1
Write $a = qb + r$ where $r = a \bmod b$, so $r = a - qb$.
2
Any common divisor of $a$ and $b$ divides $r = a - qb$, and any common divisor of $b$ and $r$ divides $a = qb + r$.
3
Thus the pairs $(a,b)$ and $(b,r)$ share exactly the same common divisors, hence the same gcd.
4
Each step strictly shrinks the remainder, so the process ends when the remainder is $0$; the last nonzero remainder is the gcd.
$462 = 3 \cdot 147 + 21$, so this equals $\gcd(147, 21)$.
3
$147 = 7 \cdot 21 + 0$; the remainder is $0$.
4
The last nonzero remainder is $21$.
Answer:
$21$
Contest level
Prove that $\gcd(n^2 + 1,\ (n+1)^2 + 1)$ divides $5$ for every positive integer $n$, and find an $n$ achieving gcd $5$.
1
Let $d = \gcd(n^2 + 1,\ (n+1)^2 + 1)$. Then $d$ divides the difference $(n+1)^2 + 1 - (n^2 + 1) = 2n + 1$.
2
$d$ also divides $n^2 + 1$, so it divides $4(n^2 + 1) - (2n+1)(2n - 1) = 4n^2 + 4 - (4n^2 - 1) = 5$.
3
Hence $d \mid 5$, so $d \in \{1, 5\}$.
4
To hit $5$, need $5 \mid n^2 + 1$, i.e. $n^2 \equiv -1 \equiv 4 \pmod 5$, so $n \equiv 2 \pmod 5$. Take $n = 2$: $n^2 + 1 = 5$ and $(n+1)^2 + 1 = 10$, and $\gcd(5, 10) = 5$.
Answer:
The gcd divides $5$; it equals $5$ when $n \equiv 2 \pmod 5$ (e.g. $n = 2$).
Olympiad / Challenge
The Fibonacci numbers are $F_1 = F_2 = 1$ and $F_{n} = F_{n-1} + F_{n-2}$. Prove that $\gcd(F_m, F_n) = F_{\gcd(m, n)}$.
1
Use the identity $F_{m} = F_{k+1} F_{m-k} + F_k F_{m-k-1}$; taking $k = n$ gives $F_m = F_{n+1}F_{m-n} + F_n F_{m-n-1}$ when $m > n$.
2
Since $F_n$ divides the term $F_n F_{m-n-1}$, we get $F_m \equiv F_{n+1} F_{m-n} \pmod{F_n}$, and $\gcd(F_{n+1}, F_n) = 1$ (consecutive Fibonacci numbers are coprime). So $\gcd(F_m, F_n) = \gcd(F_{m-n}, F_n)$.
3
This is exactly a Euclidean step on the indices: subtracting $n$ from $m$ inside the gcd. Repeating mirrors the algorithm $\gcd(m, n) \to \gcd(m \bmod n, n)$ on the subscripts.
4
The index recursion terminates at $\gcd(m, n)$ and the other index at $0$ (with $F_0 = 0$), so $\gcd(F_m, F_n) = F_{\gcd(m,n)}$.
Answer:
$\gcd(F_m, F_n) = F_{\gcd(m, n)}$.
Going Deeper
Generalization: the algorithm works because $\gcd(a, b) = \gcd(b, a - qb)$ for any integer $q$ — subtracting a multiple of one argument from the other preserves the gcd. The same 'subtract and recurse on the index' pattern powers the Mersenne identity $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$ and the Fibonacci identity above.
Where it appears: it is the engine behind the extended Euclidean algorithm (modular inverses, Bézout, CRT), it bounds the number of steps (worst case is consecutive Fibonacci numbers, the basis of Lamé's theorem), and it appears in continued-fraction expansions.
Pitfall: the recursion must use the remainder $a \bmod b \in [0, b)$, not just any difference, to guarantee the values strictly decrease and the process terminates. Forgetting the $b \neq 0$ base case, or stopping at the wrong (zero) remainder instead of the last nonzero one, are the usual slips.
Spot the Signal
Look for problems where the key step is repeatedly replacing pairs by remainders to compute gcds and solve linear combinations.
You can describe the hard part as repeatedly replacing pairs by remainders to compute gcds and solve linear combinations, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.
Learn the Move
Start by identify the integer constraint that calls for euclidean algorithm, then rewrite the givens around it.
Name the relation that makes Euclidean Algorithm legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.
Avoid These Traps
Do not use Euclidean Algorithm just because the surface looks familiar; verify the required condition first.
Applying Euclidean Algorithm because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.
MathGrit Coach Note
Let euclidean algorithm reveal the integer structure; then compute only what remains.
Try it on:
Practice a contest problem where the key step is repeatedly replacing pairs by remainders to compute gcds and solve linear combinations.