Divisibility & Primes

The division algorithm, primality, and counting divisors.

The idea

Divisibility is the basic relation of number theory. For integers $a$ and $b$, we write $a \mid b$, read as $a$ divides $b$, when $b = ak$ for some integer $k$.

Most divisions are not exact, and the division algorithm says precisely what is left: for any integer $a$ and any positive integer $b$ there is exactly one pair of integers $q$ and $r$ with $a = bq + r, \qquad 0 \le r < b.$ The quotient $q$ counts how many whole copies of $b$ fit into $a$, and the remainder $r$ is what remains — less than $b$, since otherwise another copy would fit. Divisibility is the case $r = 0$.

An integer greater than $1$ is prime when its only positive divisors are $1$ and itself, and composite when it has others. The integer $1$ is neither: it has one positive divisor, not two. A composite number breaks into smaller factors; a prime does not.

Ways to work on it

• Walkthrough. Division algorithm, what counts as prime, and trial division.
• Practice. Find a remainder or a smallest prime factor.
• Hardest. Count divisors from a prime factorization.

Not sure where to start? Take the ten-question placement test.