Number Theory — Primes, Divisibility & Modular Arithmetic

Number theory is the study of whole numbers. If you want to understand prime numbers, divisibility, or modular arithmetic, you are already looking at the core of number theory.

A prime number is an integer greater than $1$ with exactly two positive divisors: $1$ and itself. Divisibility asks whether one integer goes into another with no remainder. Modular arithmetic tracks remainders, which is why people often call it clock arithmetic.

What Number Theory Covers

These three ideas fit together:

• Primes are the basic building blocks of positive integers.
• Divisibility tells you when one integer fits exactly into another.
• Modular arithmetic rewrites divisibility questions as remainder questions.

For example, saying "$a$ is divisible by $n$" is the same as saying

$$a \equiv 0 \pmod n$$

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

Prime Numbers: The Building Blocks

Prime numbers begin

$$2, 3, 5, 7, 11, 13, \dots$$

The number $2$ is the only even prime. Every other even number is divisible by $2$, so it cannot be prime.

If a positive integer greater than $1$ is not prime, it is called composite. For example, $21$ is composite because

$$21 = 3 \cdot 7$$

Primes matter because every integer greater than $1$ can be written as a product of primes, up to the order of the factors. That is the idea behind prime factorization.

Divisibility: When One Number Fits Exactly

If $a$ and $b$ are integers with $b \ne 0$, then "$b$ divides $a$" means there is an integer $k$ such that

$$a = bk$$

This is written as

$$b \mid a$$

For instance, $4 \mid 20$ because $20 = 4 \cdot 5$. But $4 \nmid 22$ because dividing $22$ by $4$ leaves a remainder.

Divisibility is the language behind factors, multiples, greatest common divisors, and least common multiples. It also explains familiar tests:

• A number is divisible by $2$ if its last digit is even.
• A number is divisible by $5$ if its last digit is $0$ or $5$.
• A number is divisible by $3$ if the sum of its digits is divisible by $3$.

That last rule is not a trick. It comes from modular arithmetic.

Modular Arithmetic: Working With Remainders

When two integers leave the same remainder when divided by $n$, they are called congruent modulo $n$. We write

$$a \equiv b \pmod n$$

This means $n$ divides $a-b$.

For example,

$$17 \equiv 5 \pmod{12}$$

because $17$ and $5$ both leave remainder $5$ when divided by $12$, and also because $12$ divides $17 - 5 = 12$.

This is useful because you can replace a number with a simpler congruent number. On a $12$-hour clock, adding $15$ hours has the same effect as adding $3$ hours because

$$15 \equiv 3 \pmod{12}$$

Worked Example: Why Is $231$ Divisible by $3$?

Take the number $231$.

First, write it in place-value form:

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

Now 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$.

This explains the digit-sum rule: in base $10$, each power of $10$ is congruent to $1$ modulo $3$, so the whole number has the same remainder as the sum of its digits.

And once you divide,

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

so $231$ is composite, not prime.

Common Mistakes In Number Theory

Treating $1$ As Prime

$1$ is not prime. A prime must have exactly two positive divisors, and $1$ has only one.

Forgetting The Condition In Divisibility

The statement $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$. It means they differ by a multiple of $12$.

Overusing Divisibility Rules

Some tests are quick because base-$10$ arithmetic makes them work nicely. That does not mean every divisor has a simple digit rule.

Where Number Theory Shows Up

At school level, number theory appears in factorization, remainder problems, divisibility proofs, and clock-style questions. It also shows up when you reduce fractions, look for common factors, or solve problems with repeating cycles.

At a deeper level, primes and modular arithmetic are also central in cryptography and computer science. You do not need that background to use the ideas, but it helps explain why number theory keeps reappearing in applied settings.

Try Your Own Version

Try the same reasoning with $462$. First use its digit sum to test divisibility by $3$, then factor it enough to decide whether it is prime or composite.

If you want to check your method, solve a similar divisibility or remainder problem in a math solver and compare the modular arithmetic steps with your own.