Overview

Number sense is the backbone of contest math. You should be comfortable with divisibility tests, prime factorizations, and the Euclidean algorithm. Many problems reduce to checking a remainder or rewriting a number in prime powers.

This module covers divisibility, primes, gcd/lcm, and modular arithmetic with simple but powerful tools.

Key Ideas

• If $a \mid b$ and $a \mid c$, then $a \mid (bx + cy)$ for any integers $x, y$.
• The Euclidean algorithm computes $\gcd(a, b)$ quickly by repeated remainders.
• Working modulo $n$ lets you replace numbers by their remainders without changing divisibility information.
• Prime factorization turns lcm/gcd questions into exponent comparisons.
• Parity and mod 2/3/5/9 are quick sanity checks.

Core Tools

Divisibility

• If $a\mid b$ and $a\mid c$, then $a\mid (bx+cy)$ for any integers $x,y$.
• If $a\mid b$ and $b\mid c$, then $a\mid c$.

GCD and LCM

• $\gcd(a,b)\cdot\operatorname{lcm}(a,b)=|ab|$.
• Use prime factorization: gcd uses min exponents, lcm uses max exponents.

Euclidean Algorithm

Compute $\gcd(a,b)$ by repeated remainders:

$a=bq+r,\quad \gcd(a,b)=\gcd(b,r).$

Modular Arithmetic

You can add, subtract, and multiply residues:

$a\equiv b\pmod n \Rightarrow a+c\equiv b+c,\; ac\equiv bc\pmod n.$

If $a\equiv b\pmod n$, then $a^k\equiv b^k\pmod n$.

Worked Example

Find the remainder of $7^{2026}$ when divided by $9$.

Because $7 \equiv -2 \pmod 9$, we have $7^{2026} \equiv (-2)^{2026}$. Since $2026$ is even, $(-2)^{2026} = 2^{2026}$. We can use the cycle $2^1, 2^2, 2^3, 2^4 \equiv 2, 4, 8, 7 \pmod 9$ with period $6$. Compute $2026 \equiv 2026 - 6 \cdot 337 = 4 \pmod 6$, so the remainder is $2^4 \equiv 7$.

More Examples

Example 1: GCD via Euclid

Compute $\gcd(84,54)$.

$84=54\cdot1+30$, $54=30\cdot1+24$, $30=24\cdot1+6$, $24=6\cdot4+0$. So $\gcd=6$.

Example 2: LCM from Prime Factors

Find $\operatorname{lcm}(12,18)$.

$12=2^2\cdot3$, $18=2\cdot3^2$, so lcm is $2^2\cdot3^2=36$.

Example 3: Quick Divisibility

Is $7344$ divisible by $9$? Sum of digits is $7+3+4+4=18$, divisible by $9$, so $7344$ is divisible by $9$.

Strategy Checklist

• Can you reduce the problem to prime factorization?
• Is Euclid faster than factoring?
• Can a small modulus simplify the expression?
• Does parity or a digit test give a quick answer?

Common Pitfalls

• Forgetting that congruence only preserves addition and multiplication.
• Mixing up $\gcd$ and $\operatorname{lcm}$ relationships.
• Treating $a/b$ as valid in modular arithmetic when $b$ is not invertible.

Practice Problems