Number Theory — Primes, Divisibility & Modular Arithmetic

Why does adding a number's digits tell you whether it splits evenly by $3$? Answering that pulls together the three pillars of number theory — primes, divisibility, and modular arithmetic — and shows they are really one idea seen from different angles.

The three ideas and how they connect

Number theory is the study of whole numbers. Three definitions anchor it:

• A prime number is an integer greater than $1$ with exactly two positive divisors, $1$ and itself. Primes are the basic building blocks of positive integers.
• Divisibility asks whether one integer goes into another with no remainder — when one integer fits exactly into another.
• Modular arithmetic tracks remainders, which is why it is called clock arithmetic; it rewrites divisibility questions as remainder questions.

The bridge between them: saying "$a$ is divisible by $n$" is the same as

$$a \equiv 0 \pmod n$$

So a divisibility question can be rewritten as a remainder question.

Why the digit-sum rule holds — the key derivation

Each pillar contributes a piece, so set up the symbols first.

Primes. They begin $2, 3, 5, 7, 11, 13, \dots$. The number $2$ is the only even prime, since every other even number is divisible by $2$. A non-prime integer greater than $1$ is composite; for example $21 = 3 \cdot 7$. Every integer greater than $1$ can be written as a product of primes, up to order — the idea behind prime factorization.

Divisibility. For integers $a$ and $b$ with $b \ne 0$, "$b$ divides $a$" means there is an integer $k$ with $a = bk$, written $b \mid a$. So $4 \mid 20$ because $20 = 4 \cdot 5$, but $4 \nmid 22$. This is the language behind factors, multiples, GCDs, and LCMs — and behind familiar tests like "divisible by $2$ if the last digit is even" or "by $5$ if it ends in $0$ or $5$."

Modular arithmetic. When two integers leave the same remainder on division by $n$, they are congruent modulo $n$:

$$a \equiv b \pmod n$$

meaning $n$ divides $a-b$. For example $17 \equiv 5 \pmod{12}$ because both leave remainder $5$, and $12$ divides $17 - 5 = 12$. The payoff is replacement: on a $12$-hour clock, adding $15$ hours equals adding $3$ because $15 \equiv 3 \pmod{12}$.

The digit-sum rule for $3$ falls out of this: in base $10$, each power of $10$ is congruent to $1$ modulo $3$, so a number has the same remainder as the sum of its digits. The worked example makes it concrete.

Worked example: why is $231$ divisible by $3$?

Write $231$ in place-value form:

$$231 = 2 \cdot 100 + 3 \cdot 10 + 1$$

Work modulo $3$. Since

$$10 \equiv 1 \pmod 3$$

it follows that

$$100 = 10^2 \equiv 1^2 \equiv 1 \pmod 3$$

So

$$231 \equiv 2 \cdot 1 + 3 \cdot 1 + 1 \equiv 2 + 3 + 1 = 6 \equiv 0 \pmod 3$$

Because $231 \equiv 0 \pmod 3$, the number is divisible by $3$. And once you divide,

$$231 = 3 \cdot 77 = 3 \cdot 7 \cdot 11$$

so $231$ is composite, not prime.

Practice, then check your method

Run the same reasoning on $462$: use its digit sum to test divisibility by $3$, then factor it enough to decide whether it is prime or composite. Verify by confirming $3$ divides $462$ and that your factorization multiplies back to $462$.

Common traps in number theory

• Treating $1$ as prime. A prime needs exactly two positive divisors; $1$ has only one.
• Forgetting the divisibility condition. $b \mid a$ only makes sense with $b \ne 0$ — division by zero is not allowed.
• Mixing up equality and congruence. $17 \equiv 5 \pmod{12}$ does not mean $17 = 5$; they differ by a multiple of $12$.
• Overusing divisibility rules. Some tests are quick because base-$10$ arithmetic happens to cooperate; not every divisor has a simple digit rule.

Where number theory shows up

At school level: factorization, remainder problems, divisibility proofs, and clock-style questions, plus reducing fractions and finding common factors. At a deeper level, primes and modular arithmetic are central to cryptography and computer science — you do not need that background to use the ideas, but it explains why number theory keeps reappearing in applied settings.