Math Core

Every whole number greater than $1$ is built from primes in exactly one way, the way a molecule is built from atoms. Once you write a number as a product of primes, many contest questions become bookkeeping: perfect squares, factors of factorials, and "what must divide this?"

Primes and how to test them

Definition

Prime number

A prime is a whole number greater than $1$ whose only positive divisors are $1$ and itself. A whole number greater than $1$ that is not prime is composite. The number $1$ is neither.

The primes below $50$ are worth memorizing: $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47$ .

Notice that $2$ is the only even prime. This one fact solves a surprising number of problems: if two primes add to an odd number, one of them must be $2$ .

Testing a number for primality. If $n$ is composite, it can be written as $a \times b$ with $a \le b$ . Then $a \times a \le n$ , so $a \le \sqrt{n}$ . That means you only need to check primes up to $\sqrt{n}$ .

Worked example: Is 221 prime?

$\sqrt{221}$ is a bit less than $15$ (since $15^2 = 225$ ), so test the primes $2, 3, 5, 7, 11, 13$ .

$221$ is odd, its digit sum is $5$ , and it doesn't end in $0$ or $5$ . Try $7$ : $7 \times 31 = 217$ , remainder $4$ . Try $11$ : alternating sum $2 - 2 + 1 = 1$ , no. Try $13$ : $13 \times 17 = 221$ . So $221$ is composite.

Common mistake

Numbers like $91 = 7 \cdot 13$ , $119 = 7 \cdot 17$ , $133 = 7 \cdot 19$ , $143 = 11 \cdot 13$ and $221 = 13 \cdot 17$ "look prime" and trap students every year. Always finish the check up to $\sqrt{n}$ .

Prime factorization

Fundamental Theorem of Arithmetic

Every whole number greater than $1$ can be written as a product of primes in exactly one way (ignoring order). For example, $540 = 2^2 \cdot 3^3 \cdot 5$ .

To find it, divide out small primes one at a time: $540 \to 270 \to 135 \to 45 \to 15 \to 5 \to 1$ , dividing by $2, 2, 3, 3, 3, 5$ .

Perfect powers. A number is a perfect square exactly when every exponent in its factorization is even, and a perfect cube when every exponent is a multiple of $3$ .

Worked example: Make a perfect square

What is the smallest positive integer $n$ such that $540n$ is a perfect square?

$540 = 2^2 \cdot 3^3 \cdot 5$ . The exponent of $3$ is odd and the exponent of $5$ is odd. Multiply by one more $3$ and one more $5$ : $n = 15$ . Then $540 \cdot 15 = 8100 = 90^2$ .

Worked example: What must divide it?

A six-digit number has the form $\underline{A}\,\underline{B}\,\underline{A}\,\underline{B}\,\underline{A}\,\underline{B}$ , like $272727$ . Which prime greater than $30$ must divide every such number?

$\underline{A}\,\underline{B}\,\underline{A}\,\underline{B}\,\underline{A}\,\underline{B} = \underline{A}\,\underline{B} \times 10101$ , and $10101 = 3 \cdot 7 \cdot 13 \cdot 37$ . So every such number is divisible by $3, 7, 13$ and $37$ . The prime greater than $30$ is 37.

Primes inside factorials

How many times does the prime $p$ divide $n!$ ? Count the multiples of $p$ up to $n$ , then add the multiples of $p^2$ (each contributes an extra factor), then $p^3$ , and so on:

\left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots

Here $\lfloor x \rfloor$ means "round down to a whole number."

Worked example: Trailing zeros

How many zeros are at the end of $100!$ ?

Each trailing zero is a factor of $10 = 2 \cdot 5$ . There are far more $2$ s than $5$ s, so count the $5$ s: $\left\lfloor \dfrac{100}{5} \right\rfloor + \left\lfloor \dfrac{100}{25} \right\rfloor = 20 + 4 = 24$ .

So $100!$ ends in 24 zeros. The numbers $25, 50, 75, 100$ each contribute two $5$ s, which the second term counts.