Number Theory · Chapter 22

Divisibility & Legendre's Formula

Test divisibility from the digits alone, fill in missing digits, and count the factors of a prime inside a factorial without multiplying anything out.

What's this chapter about?

22.0a Divisibility Rules
22.0b Legendre's Formula
22.1 Practice Problems

You'll need

21.0 Primes and prime factorization

open on YouTube

22.0a0%

Divisibility Rules

In this section you will be able to test whether a number is divisible by 2–12 or 15 from its digits alone, and use the rules to find missing digits.

Find the smallest number made only of 4s and 9s that is divisible by 36. You never need to divide: the rule for 4 decides the ending, and the rule for 9 decides how many 4s you need.

Each rule looks at only part of the number. For $2$ , $4$ , $5$ , $8$ and $10$ you check the last few digits, because $10$ , $100$ and $1000$ are already multiples of those divisors. For $3$ and $9$ you check the digit sum, because $10 \equiv 1$ (mod $9$ ).

For $11$ , add the digits in the odd positions and the digits in the even positions separately. Look: $10 \equiv -1$ (mod $11$ ), so the place values alternate between $+1$ and $-1$ .

The rules for $6$ , $12$ and $15$ just combine two simpler rules. A missing digit becomes an unknown in the rule, and the rule turns into a small equation.

Exploreplay first, formulas later

Try this: Type a number made only of 4s and 9s and keep ÷9 on. Change the number of 4s. How many 4s do you need for the digit sum to be a multiple of 9?
Try this: Switch to ÷4. Which digits light up? Why can't a 4s-and-9s number divisible by 4 end in 9?
Try this: Switch to ÷11 and tap a digit. Which positions count toward O and which toward E? What happens to O − E?

Name it

Concept 22.0.1 · Divisibility Rules

Divisor	Rule
$2$	Last digit is even
$3$	Sum of digits is divisible by $3$
$4$	Last $2$ digits divisible by $4$
$5$	Last digit is $0$ or $5$
$6$	Divisible by $2$ and $3$
$7$	Take out multiples of $7$ until you reach a small number that is either divisible or not divisible by $7$
$8$	Last $3$ digits are divisible by $8$
$9$	Sum of digits is divisible by $9$
$10$	Last digit is $0$
$11$	Add the digits in the odd positions ( $O$ ) and the digits in the even positions ( $E$ ). If $\lvert O - E \rvert$ is divisible by $11$ , then the number is also divisible by $11$
$12$	Divisible by $3$ and $4$
$15$	Divisible by $3$ and $5$

Watch itpredict, then reveal

Example 22.1

AMC 10

Let $n$ denote the smallest positive integer that is divisible by both $4$ and $9$ , and whose base-10 representation consists of only $4$ 's and $9$ 's, with at least one of each. What are the last four digits of $n$ ?

1
Start with $4$ . Only the last two digits matter. Which ending made of $4$ s and $9$ s is a multiple of $4$ ?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Try it

Problem 22.1.2

AMC 12

This problem also appears in the book as 21.3.15.

How many odd positive $3$ -digit integers are divisible by $3$ but do not contain the digit $3$ ?

Problem 22.1.6

AMC 10

Call a positive integer an uphill integer if every digit is strictly greater than the previous digit. For example, $1357$ , $89$ , $5$ are all uphill integers but $32$ , $1240$ , $466$ are not. How many uphill integers are divisible by $15$ ?

Contest cornerreal contest problems

Problem 22.1.5

AIME

What is the largest positive integer $n$ for which $n^3 + 100$ is divisible by $n + 10$ ?

Problem 22.1.7(additional)

AMC 10

What is the largest integer that is a divisor of

(n + 1)(n + 3)(n + 5)(n + 7)(n + 9)

for all positive even integers $n$ ?

Problem 22.1.13(additional)

AMC 10

For how many positive integers $n \le 1000$ is

\left\lfloor \frac{998}{n} \right\rfloor + \left\lfloor \frac{999}{n} \right\rfloor + \left\lfloor \frac{1000}{n} \right\rfloor

not divisible by $3$ ? (Recall that $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$ .)

Checkpoint for section 22.0a

Get 2 of 3 right to master this section. One try each, no hints.

22.0b0%

Legendre's Formula

In this section you will be able to count the factors of a prime p in n! with Legendre's formula, and use it to count the zeros at the end of a factorial.

How many zeros are at the end of $100!$ ? You don’t need a single one of its $158$ digits. Just count the $5$ s.

A zero at the end is a factor of $10 = 2 \times 5$ . A factorial always has more $2$ s than $5$ s, so the number of zeros is the number of $5$ s.

To count the $5$ s in $100!$ , count the multiples of $5$ (each gives one $5$ ), then the multiples of $25$ (each gives a second one), and so on. That is Legendre’s formula.

Exploreplay first, formulas later

Try this: Set n = 100 with p = 5 and add the layers one at a time. Why does the column for 25 get a second block?
Try this: Go back to n = 19 and switch between p = 2 and p = 5. The 2-stack is taller than the 5-stack, so how many zeros end 19!?
Try this: Switch to 1!·2!·…·n! and add the layers. Why does each layer look like a staircase?

Name it

Theorem 22.0.2 · Legendre's Theorem

For a prime $p$ , the number of factors of $p$ in $n!$ is

v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots

The sum stops once $p^k > n$ , because every later term is $0$ .

Watch itpredict, then reveal

Example 22.2

AIME

Let $N$ be the number of consecutive $0$ 's at the right end of the decimal representation of the product $1!\,2!\,3!\,4! \cdots 99!\,100!$ . Find the remainder when $N$ is divided by $1000$ .

1
Each zero at the end is a factor of $10 = 2 \times 5$ . Which prime runs out first in $1!\,2!\cdots100!$ , so it decides $N$ ?

Predict first:
Click a choice or type its letter (A–E).

open on YouTube

Example 22.3

AMC 10

The base-ten representation for $19!$ is $121{,}6T5{,}100{,}40M{,}832{,}H00$ , where $T$ , $M$ , and $H$ denote digits that are not given. What is $T + M + H$ ?

Tap a letter to try a digit for it.

Digit sum 1 + 2 + 1 + 6 + T + 5 + 1 + 0 + 0 + 4 + 0 + M + 8 + 3 + 2 + H + 0 + 0 = 33 + T + M + H must be a multiple of 9.

Is 1216T510040M832H00 divisible by 9? It depends on T, M and H

Digits for T, M and H that make it divisible by 9:

1
Start with $H$ . How many factors of $5$ does $19!$ have?

Predict first:
Your prediction

open on YouTube

Try it

Problem 22.1.3

AMC 10

For all integers $n \ge 9$ , the value of

\frac{(n + 2)! - (n + 1)!}{n!}

is always which of the following?

Contest cornerreal contest problems

Problem 22.1.8(additional)

AMC 12

The number $21! = 51{,}090{,}942{,}171{,}709{,}440{,}000$ has over $60{,}000$ positive integer divisors. One of them is chosen at random. What is the probability that it is odd?

Problem 22.1.15(additional)

AIME

Define $n!!$ to be $n(n - 2)(n - 4) \cdots 3 \cdot 1$ for $n$ odd and $n(n - 2)(n - 4) \cdots 4 \cdot 2$ for $n$ even. When

\sum_{i=1}^{2009} \frac{(2i - 1)!!}{(2i)!!}

is expressed as a fraction in lowest terms, its denominator is $2^a b$ with $b$ odd. Find $\dfrac{ab}{10}$ .

Checkpoint for section 22.0b

Get 2 of 3 right to master this section. One try each, no hints.

22.1

Practice Problems

In this section you will be able to mix every tool from this chapter: grid crossings, gcds, remainders mod 99 and the digit-sum trick.

These problems mix the rules. Some are repeats from earlier in the book: if you solved them there, try a different route here.

Contest cornerreal contest problems

Problem 22.1.1

AMC 10

A rectangular floor that is $10$ feet wide and $17$ feet long is tiled with $170$ one-foot square tiles. A bug walks from one corner to the opposite corner in a straight line. Including the first and the last tile, how many tiles does the bug visit?

Problem 22.1.4

IMO

Prove that the fraction $\frac{21n + 4}{14n + 3}$ is irreducible for every natural number $n$ .

This one asks for a proof. Write yours on paper, use the hints if you need them, then compare it with the written proof.

Problem 22.1.9(additional)

AMC 10

This problem also appears in the book as 22.1.6.

Call a positive integer an uphill integer if every digit is strictly greater than the previous digit. For example, $1357$ , $89$ , and $5$ are all uphill integers, but $32$ , $1240$ , and $466$ are not. How many uphill integers are divisible by $15$ ?

Problem 22.1.10(additional)

AMC 10

This problem also appears in the book as 21.3.20.

Let $N = 123456789101112 \dots 4344$ be the $79$ -digit number that is formed by writing the integers from $1$ to $44$ in order, one after the other. What is the remainder when $N$ is divided by $45$ ?

Problem 22.1.11(additional)

AMC 10

This problem also appears in the book as 22.1.

Problem 22.1.12(additional)

AMC 10

A finite sequence of three-digit integers has the property that the tens and units digits of each term are, respectively, the hundreds and tens digits of the next term, and the tens and units digits of the last term are, respectively, the hundreds and tens digits of the first term. For example, such a sequence might begin with the terms $247$ , $475$ , and $756$ and end with the term $824$ . Let $S$ be the sum of all the terms in the sequence. What is the largest prime factor that always divides $S$ ?

Problem 22.1.14(additional)

AIME

Let $a_{10} = 10$ , and for each positive integer $n > 10$ let $a_n = 100a_{n-1} + n$ . Find the least positive $n > 10$ such that $a_n$ is a multiple of $99$ .

Formula cards

Concept 22.0.1 · Divisibility Rules

Divisor	Rule
$2$	Last digit is even
$3$	Sum of digits is divisible by $3$
$4$	Last $2$ digits divisible by $4$
$5$	Last digit is $0$ or $5$
$6$	Divisible by $2$ and $3$
$7$	Take out multiples of $7$ until you reach a small number that is either divisible or not divisible by $7$
$8$	Last $3$ digits are divisible by $8$
$9$	Sum of digits is divisible by $9$
$10$	Last digit is $0$
$11$	Add the digits in the odd positions ( $O$ ) and the digits in the even positions ( $E$ ). If $\lvert O - E \rvert$ is divisible by $11$ , then the number is also divisible by $11$
$12$	Divisible by $3$ and $4$
$15$	Divisible by $3$ and $5$

Theorem 22.0.2 · Legendre's Theorem

For a prime $p$ , the number of factors of $p$ in $n!$ is

v_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \cdots

The sum stops once $p^k > n$ , because every later term is $0$ .

All formulas →