A Gentle Introduction to Number Theory

Number theory gets called “the queen of mathematics” sometimes, which sounds fancy, but honestly? It’s just about whole numbers. The ones you learned to count with. That’s it.

But here’s the thing: those simple numbers hide some of the deepest mysteries in math. Problems that look easy can take centuries to solve. Questions a kid could ask might stump the smartest mathematicians alive.

We’re going to talk about four ideas that show up everywhere: divisibility, prime numbers, greatest common divisors, and modular arithmetic. Nothing too fancy. Just the basics that make everything else possible.

Divisibility: When One Number Fits Into Another

You know this already, even if you don’t think about it. Twelve divided by three is four, so three “divides” twelve. We write that as $3 \mid 12$ .

Formally, $a$ divides $b$ if you can find some number $k$ where $b = ak$ . That’s it. Simple.

Some quick examples: $3 \mid 12$ because $12 = 3 \cdot 4$ . $5 \mid 20$ because $20 = 5 \cdot 4$ . But $7 \nmid 20$ because there’s no whole number you can multiply by 7 to get 20.

The Rules That Save Time

There are shortcuts for checking divisibility, and they’re actually useful. Like, really useful.

Divisible by 2? Check the last digit. If it’s even (0, 2, 4, 6, 8), you’re good.

Divisible by 3? Add up all the digits. If that sum is divisible by 3, so is the original number. Try it: $123456$ . Add them up: $1+2+3+4+5+6 = 21$ . Since 21 is divisible by 3, so is 123456.

Divisible by 9? Same trick—add the digits. If the sum is divisible by 9, you’re done.

Divisible by 11? This one’s weird. Take the alternating sum of digits. For 121, that’s $1-2+1 = 0$ , and since 0 is divisible by 11, so is 121.

These rules aren’t magic—they’re just patterns that fall out of how our number system works. But they’re incredibly handy.

Prime Numbers: The Atoms of Math

Primes are numbers greater than 1 that can only be divided by 1 and themselves. That’s it. No other divisors.

The first few: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47…

Notice something? 2 is the only even prime. Every other even number is divisible by 2, so they can’t be prime. It’s the odd one out, literally.

Why Primes Matter

Here’s the big idea: every number can be broken down into primes, and there’s only one way to do it (if you ignore the order).

Take 84. You can write it as $2 \times 2 \times 3 \times 7$ , or $2^2 \times 3 \times 7$ . However you write it, you need two 2’s, one 3, and one 7. That’s the only way.

This is called the Fundamental Theorem of Arithmetic, and it’s huge. It means primes are like atoms—the building blocks everything else is made from.

Want to find all the divisors of 12? Write it as $2^2 \times 3$ . Then every divisor is of the form $2^a \times 3^b$ where $a$ is 0, 1, or 2, and $b$ is 0 or 1. That gives you: 1, 2, 3, 4, 6, 12. All of them.

The Infinite Mystery

Euclid proved over 2000 years ago that there are infinitely many primes. His proof is beautiful and simple.

Suppose there are only finitely many primes. List them all: $p_1, p_2, \ldots, p_n$ . Now consider the number $N = p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$ .

This number can’t be divisible by any of our primes (they all leave remainder 1). So either $N$ is prime itself (contradiction!), or it has a prime factor we didn’t list (also contradiction!). Therefore, there must be infinitely many primes.

It’s elegant. It’s ancient. And it still works.

The GCD of two numbers is the biggest number that divides both of them. Simple concept, incredibly useful.

For example, what’s the GCD of 12 and 18? The divisors of 12 are 1, 2, 3, 4, 6, 12. The divisors of 18 are 1, 2, 3, 6, 9, 18. The common ones are 1, 2, 3, 6. The biggest is 6, so $\gcd(12, 18) = 6$ .

When the GCD is 1, we say the numbers are “coprime” or “relatively prime.” They share no common factors except 1.

The Euclidean Algorithm

Here’s the cool part: there’s a fast way to find GCDs. It’s called the Euclidean algorithm, and it’s been around for over 2000 years.

The key insight: $\gcd(a, b) = \gcd(b, a \bmod b)$ . That’s it. Just keep applying this until you get to 0.

Let’s find $\gcd(48, 18)$ :

$\gcd(48, 18) = \gcd(18, 48 \bmod 18) = \gcd(18, 12)$
$\gcd(18, 12) = \gcd(12, 18 \bmod 12) = \gcd(12, 6)$
$\gcd(12, 6) = \gcd(6, 12 \bmod 6) = \gcd(6, 0)$
When the second number is 0, the GCD is the first number: 6

It’s fast. It’s efficient. And it’s the foundation of a lot of number theory.

Modular Arithmetic: Clock Math

This is where it gets fun. Modular arithmetic is like clock arithmetic. On a 12-hour clock, 13 o’clock is the same as 1 o’clock. That’s because $13 \equiv 1 \pmod{12}$ .

We say $a \equiv b \pmod{n}$ if $a$ and $b$ have the same remainder when divided by $n$ . Or equivalently, if $n$ divides $(a - b)$ .

Examples: $17 \equiv 2 \pmod{5}$ because both leave remainder 2. $23 \equiv 3 \pmod{10}$ because both leave remainder 3.

Why It’s Useful

Modular arithmetic makes a lot of problems easier. Want to find the last digit of $7^{2025}$ ? You don’t need to compute the whole number—just work modulo 10.

Let’s find the pattern:

$7^1 \equiv 7 \pmod{10}$
$7^2 = 49 \equiv 9 \pmod{10}$
$7^3 = 343 \equiv 3 \pmod{10}$
$7^4 = 2401 \equiv 1 \pmod{10}$
$7^5 = 7^4 \cdot 7 \equiv 1 \cdot 7 \equiv 7 \pmod{10}$

The pattern repeats every 4. Since $2025 = 4 \cdot 506 + 1$ , we have: $7^{2025} = 7^{4 \cdot 506 + 1} = (7^4)^{506} \cdot 7^1 \equiv 1^{506} \cdot 7 \equiv 7 \pmod{10}$

So the last digit is 7. No giant number needed.

Fermat’s Little Theorem

Here’s a powerful shortcut: if $p$ is prime and $a$ isn’t divisible by $p$ , then $a^{p-1} \equiv 1 \pmod{p}$ .

This makes computing powers modulo primes way easier. Want $5^{100} \bmod 7$ ? Since 7 is prime and 5 isn’t divisible by 7, we know $5^6 \equiv 1 \pmod{7}$ . Since $100 = 6 \cdot 16 + 4$ , we get $5^{100} = (5^6)^{16} \cdot 5^4 \equiv 1^{16} \cdot 5^4 \equiv 625 \equiv 2 \pmod{7}$ .

Done. No massive calculations.

Why This All Matters

Number theory shows up everywhere. Cryptography uses it to keep your data safe. Computer science uses it for hash functions and algorithms. Competition math is full of it.

But more than that, it’s beautiful. Simple questions about whole numbers lead to deep insights. Patterns emerge from chaos. Structure appears where you least expect it.

The integers might seem basic, but they’re hiding incredible depth. And once you start seeing the patterns, you can’t unsee them.

Try This

Here’s something to play with: prove that for any integer $n$ , the number $n^2$ is either 0 or 1 modulo 4.

Hint: what are the possible remainders when you divide $n$ by 4? Try each case and see what happens when you square it.

You’ll find that $n^2$ is always 0 or 1 mod 4, never 2 or 3. This simple fact shows up in all sorts of places—like proving that certain equations have no integer solutions.

That’s number theory in a nutshell: simple questions, surprising answers, infinite connections.