Integers, divisibility and primes

Factors, multiples and divisibility

An integer $d$ divides $n$ when $n = dk$ for some integer $k$. Then $d$ is a factor (or divisor) of $n$, and $n$ is a multiple of $d$. The words describe one relationship from two sides: 6 is a factor of 42, and 42 is a multiple of 6.

Two edge cases are worth fixing in memory. Every integer divides 0, because $0 = d \times 0$. And 1 divides everything, while every non-zero integer divides itself. Questions about factors usually mean positive factors, but read the stem: negative integers are factors too, since $42 = (-6)(-7)$.

Divisibility rules worth knowing

Divisor	Test
2	last digit even
3	sum of digits divisible by 3
4	last two digits form a multiple of 4
5	last digit 0 or 5
6	divisible by both 2 and 3
8	last three digits form a multiple of 8
9	sum of digits divisible by 9
10	last digit 0

The rules for 3 and 9 work because $10 \equiv 1$ when you divide by 3 or 9: every power of 10 leaves remainder 1, so a number leaves the same remainder as the sum of its digits. For example, 7,128 has digit sum 18, so it is divisible by 9 (and by 3); its last two digits, 28, make it divisible by 4.

Primes and prime factorisation

A prime is an integer greater than 1 whose only positive divisors are 1 and itself: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … Two facts trip people up. 1 is not prime, and 2 is the only even prime.

Every integer greater than 1 can be written as a product of primes in exactly one way, apart from order. Build the factorisation with a factor tree, splitting off small primes first:

$$360 = 36 \times 10 = (2^2 \times 3^2)(2 \times 5) = 2^3 \times 3^2 \times 5$$

To check whether a number is prime, you only need to try primes up to its square root. For 151, $\sqrt{151}$ is a little above 12, so you try 2, 3, 5, 7 and 11; none divides 151, so 151 is prime.

Reading the factorisation

The factorisation is a complete description of the number, and most integer questions are answered by reading it.

Divisors. A positive divisor of $2^3 \times 3^2 \times 5$ chooses an exponent for each prime: 0 to 3 for the 2, 0 to 2 for the 3, 0 to 1 for the 5. That gives $(3+1)(2+1)(1+1) = 24$ divisors. In general, if $n = p^a q^b r^c$, then $n$ has $(a+1)(b+1)(c+1)$ positive divisors. The "+1" counts the choice of leaving that prime out.

Divides. $d$ divides $n$ exactly when every prime in $d$ appears in $n$ at least as many times. So $12 = 2^2 \times 3$ divides 360, but $27 = 3^3$ does not, because 360 has only two 3s.

Perfect squares and cubes. A perfect square has every exponent even; a perfect cube has every exponent a multiple of 3.

Greatest common divisor and least common multiple

Line the two factorisations up prime by prime.

• The GCD takes each shared prime with the smaller exponent.
• The LCM takes every prime that appears in either number, with the larger exponent.

For two positive integers, $\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b$, which gives a quick check on your work.

The LCM answers a whole family of questions: if $n$ is divisible by both $a$ and $b$, then $n$ is divisible by $\operatorname{lcm}(a, b)$, and by nothing larger that you can be sure of. Divisible by 4 and by 6 guarantees divisibility by 12, not by 24, because 4 and 6 share a factor of 2 that the product counts twice.

Testing "must be" claims

Many integer questions ask what must be true. Prove a "must" with the factorisation; disprove it with one counterexample, usually the smallest number that fits the facts. For "divisible by 4 and 6", try $n = 12$: anything that fails for 12 is not a "must".