Divisibility and Prime Numbers

A prime is simply a whole number bigger than 1 that you can't split into a product of smaller whole numbers: 7 is prime, but $6 = 2 \cdot 3$ isn't. The name comes from the Latin primus, "first," because primes come first: every other number is built by multiplying them. They're good for far more than puzzles, too; the security of internet encryption rests on them, as you'll see at the end of this unit. The notation $a \mid b$ (a goes into b with nothing left over) is just a short way to write that. And $n = p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}$ looks heavy, but it only says: write $n$ as primes multiplied together, with $p_1, p_2, \dots$ (the different primes) and $e_1, e_2, \dots$ (how many times each one shows up). For example, $12 = 2^2 \cdot 3$. That's all the notation there is.

Division with remainder. You've done this since grade school: 17 divided by 5 is 3 with 2 left over. In general, for any integer $b$ and positive $a$ there are unique $q$ and $r$ with $b = qa + r$ and $0 \le r < a$. Then $a \mid b$ exactly when the leftover $r$ is $0$.

Primes are the building blocks: $2, 3, 5, 7, 11, \dots$ (1 is not prime, since it has only one divisor). To test whether $n$ is prime, you only need to try divisors up to $\sqrt n$. Why? If $n = ab$ and both factors were above $\sqrt n$, their product would be bigger than $n$. So any factorization has at least one factor at or below $\sqrt n$, and that's the one you'll find. The sieve of Eratosthenes finds all primes up to $N$ by crossing out multiples of each prime in turn.

Unique factorization. $360 = 2^3 \cdot 3^2 \cdot 5$, and no other product of primes equals 360. This is the fundamental theorem of arithmetic, and it's more useful than it sounds. Think about what a divisor of 360 looks like: it can only be built from the same primes, using no more of each than 360 has. So a divisor chooses an exponent from 0 to 3 for 2, from 0 to 2 for 3 and 0 or 1 for 5, and 360 has $4 \cdot 3 \cdot 2 = 24$ divisors.

How many primes? Infinitely many, as Euclid proved; we'll see his proof in the unit on proofs. They do thin out, but slowly: the prime number theorem says the number of primes up to $x$, written $\pi(x)$, is roughly $x / \ln x$.

The security of everyday internet encryption rests on how hard it is to factor the product of two very large primes.