Number Theory Basics

1. Introduction

Number theory is the study of the integers, and on the AMC 8 it shows up constantly: counting divisors, finding the greatest common divisor of two numbers, deciding whether a big number is divisible by $9$, or hunting for the smallest integer with a special property. Almost every one of these problems becomes easy once you can do one thing well — break a number into its prime factorization.

The reason primes matter so much is that they are the atoms of multiplication. Every whole number bigger than $1$ is either prime itself or can be built by multiplying primes together, and there is essentially only one way to do it. Once you see a number like $360$ as $2^3 \cdot 3^2 \cdot 5$, questions like "how many divisors does it have?" or "what is its GCD with $84$?" turn into quick exponent bookkeeping instead of guesswork.

In this article you will learn the divisibility rules and why they work, the Fundamental Theorem of Arithmetic, how to count divisors and sum them, how to compute the GCD and LCM both by factoring and by the lightning-fast Euclidean algorithm, modular thinking for digit puzzles, and how all of these combine in real contest problems. Master this material and a large slice of the AMC 8 number-theory questions become routine.

2. Core Concepts

Concept 1 — Divisibility and Factors

We say an integer $d$ divides $n$, written $d \mid n$, if $n = dq$ for some integer $q$ — that is, $n$ divided by $d$ leaves no remainder. Then $d$ is a divisor (or factor) of $n$, and $n$ is a multiple of $d$. For example $7 \mid 56$ because $56 = 7 \cdot 8$, but $7 \nmid 50$.

Every positive integer $n$ has at least two divisors, $1$ and $n$ itself. A prime is an integer greater than $1$ whose only divisors are $1$ and itself: $2, 3, 5, 7, 11, 13, \dots$. A composite is an integer greater than $1$ that is not prime. The number $1$ is special: it is neither prime nor composite.

Concept 2 — The Fundamental Theorem of Arithmetic

Fundamental Theorem of Arithmetic. Every integer $n > 1$ can be written as a product of primes, and this factorization is unique up to the order of the factors. We collect repeated primes into powers: $n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k},$ where the $p_i$ are distinct primes and each exponent $e_i \geq 1$. For instance $360 = 2^3 \cdot 3^2 \cdot 5$ and $1000 = 2^3 \cdot 5^3$.

This uniqueness is the engine behind nearly every technique below. To factor a number by hand, repeatedly divide out the smallest prime that fits: $360 \to 180 \to 90 \to 45 \to 15 \to 5 \to 1$, recording $2, 2, 2, 3, 3, 5$.

Concept 3 — Why Divisibility Rules Work

Divisibility rules come from the place-value structure of base ten. Since $10 \equiv 1 \pmod 3$ and $10 \equiv 1 \pmod 9$, every power of $10$ leaves remainder $1$, so a number is congruent to its digit sum modulo $3$ and modulo $9$. Since $10 \equiv -1 \pmod{11}$, powers of $10$ alternate $+1, -1, +1, \dots$, which is why the alternating digit sum controls divisibility by $11$. And because $100$ is a multiple of $4$ (and $1000$ a multiple of $8$), only the last two digits matter for $4$ and the last three for $8$.

Concept 4 — Divisibility by 2, 5, and 10

A number is divisible by $2$ when its last digit is even ($0, 2, 4, 6, 8$). It is divisible by $5$ when its last digit is $0$ or $5$. It is divisible by $10$ when its last digit is $0$. These follow because $10 = 2 \cdot 5$ and $10 \mid 10^k$ for every $k \geq 1$, so only the units digit of $n$ matters for divisibility by $2$ or $5$.

Concept 5 — Divisibility by 3 and 9

Theorem (digit-sum test). An integer $n$ is divisible by $3$ (resp. $9$) if and only if the sum of its decimal digits is divisible by $3$ (resp. $9$).

Example: $1{,}234{,}567$ has digit sum $1+2+3+4+5+6+7 = 28$. Since $28 \not\equiv 0 \pmod 3$, the number is not divisible by $3$. For $9$, note $28 \equiv 1 \pmod 9$, so it is not divisible by $9$ either.

Concept 6 — Divisibility by 4, 8, and 11

• By $4$: check whether the number formed by the last two digits is a multiple of $4$. Example: $123{,}456$ ends in $56$, and $56 = 4 \cdot 14$, so $4 \mid 123{,}456$.
• By $8$: check the last three digits. Example: $7{,}024$ ends in $024 = 8 \cdot 3$, so $8 \mid 7{,}024$.
• By $11$: form the alternating sum of digits from the right: $d_0 - d_1 + d_2 - d_3 + \cdots$. The number is divisible by $11$ iff this alternating sum is divisible by $11$. Example: $91{,}819$ gives $9 - 1 + 8 - 1 + 9 = 24$, not divisible by $11$.

Concept 7 — GCD and LCM

The greatest common divisor $\gcd(a,b)$ is the largest integer dividing both $a$ and $b$. The least common multiple $\operatorname{lcm}(a,b)$ is the smallest positive integer that both $a$ and $b$ divide. Two integers with $\gcd(a,b)=1$ are called relatively prime or coprime.

In terms of prime factorizations, the GCD takes the minimum exponent of each shared prime and the LCM takes the maximum exponent of every prime that appears in either number.

Concept 8 — The GCD–LCM Identity

Theorem. For any positive integers $a$ and $b$, $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b.$ Knowing any three of these four quantities gives the fourth instantly. This identity is one of the fastest sanity checks on contest problems.

Concept 9 — The Euclidean Algorithm

When numbers are large or awkward to factor, use the Euclidean algorithm: $\gcd(a,b) = \gcd(b, a \bmod b)$, repeating until the remainder is $0$. The last nonzero remainder is the GCD. This algorithm is guaranteed to terminate and is far faster than factoring for large integers.

Concept 10 — Counting Divisors

If $n = p_1^{e_1} \cdots p_k^{e_k}$, each divisor is built by choosing an exponent from $0$ to $e_i$ for each prime $p_i$. Hence the divisor-count formula: $d(n) = (e_1+1)(e_2+1)\cdots(e_k+1).$ A perfect square is exactly the positive integer whose divisor count is odd, because one exponent can be chosen in only one way to pair with itself (the middle exponent when all exponents are even).

Concept 11 — Sum of Divisors

The sum-of-divisors function $\sigma(n)$ adds every positive divisor of $n$. From the prime factorization, $\sigma(n) = \prod_{i=1}^{k} \left(1 + p_i + p_i^2 + \cdots + p_i^{e_i}\right) = \prod_{i=1}^{k}\frac{p_i^{e_i+1}-1}{p_i-1}.$ This appears when a problem asks for "the sum of all factors" or "the sum of proper divisors."

Concept 12 — Trailing Zeros and Prime Powers in Factorials

The number of trailing zeros in $n!$ equals the number of factors of $5$ in $n!$, because factors of $2$ are always more plentiful: $\nu_5(n!) = \left\lfloor \frac{n}{5} \right\rfloor + \left\lfloor \frac{n}{25} \right\rfloor + \left\lfloor \frac{n}{125} \right\rfloor + \cdots.$ More generally, the exponent of a prime $p$ in $n!$ is $\lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \cdots$.