Remainders, Primes, and Hidden Patterns: Number Theory’s Greatest Hits

Number theory is the study of whole numbers-integers-and the surprising patterns hiding inside them. It’s the branch of math where questions can sound like playground dares (“Can you split this number into primes in only one way?”) and end up powering modern cryptography. But you don’t need to be a specialist to enjoy it. All you need is curiosity and a willingness to follow a few examples.

Let’s take a walk through some of the greatest “characters” in number theory: primes, remainders, modular arithmetic, and a few classic theorems that feel like magic the first time you see them.

1) Primes: the “atoms” of arithmetic

A prime number is an integer greater than $1$ whose only positive divisors are $1$ and itself:

$2, 3, 5, 7, 11, 13, 17, …$

Why do primes matter? Because every integer bigger than $1$ can be built from them.

Example: prime factorization

Take $360$. Divide by primes:

• $360 = 2 \cdot 180$

• $180 = 2 \cdot 90$

• $90 = 2 \cdot 45$

• $45 = 3 \cdot 15$

• $15 = 3 \cdot 5$

So:

$360 = 2^3 \cdot 3^2 \cdot 5$

This is not just a trick-it’s a theorem.

The Fundamental Theorem of Arithmetic

Every integer $n>1$ can be written as a product of primes uniquely (ignoring order).

That “uniquely” is huge. It means integers have a stable “DNA”.

2) A proof that never gets old: infinitely many primes

Here’s a classic argument, going back over two thousand years.

Assume (for contradiction) there are only finitely many primes:

$p_1, p_2, \dots, p_k$

Now build this number:

$N = p_1p_2\cdots p_k + 1$

When you divide $N$ by any prime $p_i$, you get a remainder of $1$. So none of the listed primes divides $N$. Therefore, $N$ is either prime itself, or divisible by a prime not in the list-either way, we found a new prime. Contradiction.

So, primes never end. The list goes on forever, like a cosmic spreadsheet you can scroll forever without reaching the bottom.

3) Remainders as a superpower: modular arithmetic

When we say:

$a \equiv b \pmod{m}$

we mean a and b leave the same remainder when divided by m, i.e. $m\mid(a-b)$.

Example: clock arithmetic

A clock is arithmetic mod $12$.

If it’s 10 o’clock and you wait 5 hours:

$10 + 5 = 15 \equiv 3 \pmod{12}$

So it’s 3 o’clock.

Modular arithmetic turns messy problems into tidy ones because it lets you ignore everything except remainders.

4) A “remainder trick” for divisibility

You’ve probably seen rules like “a number is divisible by $3$ if the sum of its digits is divisible by $3$.” That’s modular arithmetic in disguise.

Why does it work? Because:

$10 \equiv 1 \pmod{3}$

So:

$10^k \equiv 1^k = 1 \pmod{3}$

That means a number like $528$ behaves like:

$528 = 5\cdot 10^2 + 2\cdot 10^1 + 8 \equiv 5 + 2 + 8 = 15 \equiv 0 \pmod{3}$

So $528$ is divisible by $3$. Nice and clean.

5) The Euclidean Algorithm: the fastest way to find a GCD

The greatest common divisor $\gcd(a,b)$ is the biggest integer dividing both a and b.

The Euclidean algorithm says:

$\gcd(a,b) = \gcd(b, a \bmod b)$

Repeat until the remainder is $0$.

Example: $\gcd(252, 198)$

Compute remainders:

• $252 = 198\cdot 1 + 54$

• $198 = 54\cdot 3 + 36$

• $54 = 36\cdot 1 + 18$

• $36 = 18\cdot 2 + 0$

So:

$\gcd(252,198) = 18$

This is one of the most practical number theory tools ever invented. It’s also the engine behind modular inverses (which we’ll use soon).

6) When division does work: modular inverses

In ordinary arithmetic, dividing by a means multiplying by $1/a$. In modular arithmetic, division is trickier—but sometimes it works.

A number $x$ is the modular inverse of a $\pmod{m}$ if:

$ax \equiv 1 \pmod{m}$

This exists only if $\gcd(a,m)=1$.

Example: inverse of $3$ mod $7$

We want $3x \equiv 1 \pmod{7}$. Try values:

• $3\cdot 1 = 3$

• $3\cdot 2 = 6$

• $3\cdot 3 = 9 \equiv 2$

• $3\cdot 4 = 12 \equiv 5$

• $3\cdot 5 = 15 \equiv 1$

So $x=5$.

$3^{-1} \equiv 5 \pmod{7}$

This concept-multiplying by inverses mod a large number-is a backbone of cryptography.

7) Fermat’s Little Theorem: a tiny sentence with huge consequences

If $p$ is prime and $a$ is not divisible by $p$, then:

$a^{p-1} \equiv 1 \pmod{p}$

Example: $2^{10} \mod 11$

Since $11$ is prime:

$2^{11-1} = 2^{10} \equiv 1 \pmod{11}$

So the remainder is $1$ immediately-no need to compute $1024$.

You can also use this to find inverses:

$a^{-1} \equiv a^{p-2} \pmod{p}$

For instance, mod $11$:

$2^{-1} \equiv 2^9 \pmod{11}$

(There are faster ways to compute, but the theorem guarantees it.)

8) The Chinese Remainder Theorem: solving “remainder puzzles”

CRT says: if moduli are coprime, systems of congruences have a unique solution modulo their product.

Example: find $x$ such that

$x \equiv 2 \pmod{3}, \quad x \equiv 3 \pmod{5}$

Let’s list numbers $\equiv 2 \pmod{3}$:

$2,5,8,11,14,17,\dots$

Which of these is $\equiv 3 \pmod{5}$?

Check remainders mod $5$:

• $2 → 2$

• $5 → 0$

• $8 → 3$

So $x=8$. And all solutions are:

$x \equiv 8 \pmod{15}$

CRT is like a lockpick for remainder constraints. It appears in scheduling problems, hashing, coding theory, and cryptography.

9) A famous unsolved feeling (but solvable) problem: sums of squares

Here’s a classic question: which numbers can be written as a sum of two squares?

$n = a^2 + b^2$

Examples:

• $5 = 1^2 + 2^2$

• $10 = 1^2 + 3^2$

• $25 = 0^2 + 5^2 = 3^2 + 4^2$

A deep theorem says (roughly): in the prime factorization of $n$, any prime congruent to $3 \pmod{4}$ must appear with an even exponent for $n$ to be a sum of two squares.

Example: is $45$ a sum of two squares?

$45 = 3^2 \cdot 5$

Here $3 \equiv 3 \pmod{4}$, and it appears with exponent $2$ (even). Good sign. Indeed:

$45 = 3^2 + 6^2$

Example: is $21$ a sum of two squares?

$21 = 3\cdot 7$

Prime $3 \equiv 3 \pmod{4}$ appears with exponent $1$ (odd). That blocks it. And indeed, you won’t find integers $a,b$ with $a^2+b^2=21$.

This is a beautiful example of number theory’s style: prime remainders mod $4$ decide geometry.

10) Why this matters (even if you don’t “need” it)

Number theory has a unique vibe: simple rules, unexpected depth. You can understand the questions quickly, but the answers can be profoundly non-obvious. And it’s not just aesthetic-these ideas power real systems:

• Cryptography uses modular arithmetic and primes to secure communication.

• Error-correcting codes use arithmetic structure to fix corrupted data.

• Computer algorithms rely on gcds, modular inverses, and prime testing.

But even outside applications, number theory is satisfying because it feels like uncovering hidden laws in a world you thought you already understood. Integers look plain. Then you learn they have social patterns, secret relationships, and entire ecosystems built out of remainders.