Number Theory · Chapter 17

Primes and Divisibility

Spot primes, test divisibility in your head, break numbers into primes, and count the zeros at the end of a factorial.

What's this chapter about?

17.1 Primes
17.2 Divisibility Rules
17.3 Prime Factorization
17.4 Legendre’s Formula
17.5 Practice Problems

You'll need

1.2 Factorials

open on YouTube

17.10%

Primes

In this section you will be able to spot prime numbers and test whether a number is prime using only primes up to its square root.

Try to split 12 cookies into equal rows. You can make rows of 2, 3, 4 or 6. Now try 13 cookies. Only one long row works! Numbers like 13 are called primes.

A prime can’t be split into a product of smaller numbers. Every other number bigger than 1 can.

The sieve finds primes by crossing out multiples. Look: once you have swept every prime up to the square root of the biggest number, nothing new gets crossed out.

Exploreplay first, formulas later

Try this: Press Sweep 2. Which numbers get crossed out? Why does 2 itself survive?
Try this: Keep sweeping: 3, 5, 7. Now press Sweep 11. What new numbers get crossed out?
Try this: Turn on Test a number and try 91. Which primes do you need to test? Why stop at 9?

Name it

Definition 17.1.1 · Primes

Primes are numbers that have exactly two factors: $1$ and the number itself.

Example: $2, 3, 5, 7, 11, 13, 17, 19, 23$ are all primes.

Note: $1$ is not a prime (it has only one factor), and $2$ is the only even prime.

Remark 17.1.2

It's highly recommended to memorize the first few primes, as this can save some time during the contest:

2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29,\ 31,\ 37

Remark 17.1.3

To check whether a number $n$ is prime, you only need to check whether it can be divided by the primes that are less than or equal to $\sqrt{n}$ .

For example, $\sqrt{91} \approx 9.5$ , so you test $2, 3, 5, 7$ . And $91 = 7 \times 13$ , so $91$ is not prime.

Try it

Problem 17.5.1

AMC 8

Which of the following numbers has the smallest prime factor?

(A) 55 (B) 57 (C) 58 (D) 59 (E) 61

Problem 17.5.4

AMC 8

The sum of two prime numbers is 85. What is the product of these two prime numbers?

Contest cornerreal contest problems

Problem 17.5.7

AMC 8

What is the smallest positive integer that is neither prime nor square and that has no prime factor less than 50?

Problem 17.5.10

AMC 8

Three members of the Euclid Middle School girls' softball team had the following conversation.

Ashley: I just realized that our uniform numbers are all 2-digit primes.

Brittany: And the sum of your two uniform numbers is the date of my birthday earlier this month.

Caitlin: That's funny. The sum of your two uniform numbers is the date of my birthday later this month.

Ashley: And the sum of your two uniform numbers is today's date.

What number does Caitlin wear?

Checkpoint for section 17.1

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

17.20%

Divisibility Rules

In this section you will be able to decide whether a number is divisible by 2 through 12 or 15 without doing the long division.

Is 4,827,676 divisible by 8? You could do a long division. Or you could look at just three digits and know in a few seconds.

Each rule only looks at part of the number: the last digit, the last few digits, or the digit sum. The rest of the number is a multiple of 10, 100 or 1000 and never changes the answer.

For 6, 12 and 15, check two simpler rules. A number divisible by 3 and by 4 is divisible by 12.

Exploreplay first, formulas later

Try this: Pick ÷4. Which digits light up? Tap the last digit until the number becomes divisible by 4.
Try this: Pick ÷3, then ÷9. Tap any digit. Does it matter which digit you change?
Try this: Pick ÷11 for 629321. What are O and E? Now try 1331.
Try this: Pick ÷12. Which two smaller rules does it use, and why those two?

Name it

Concept 17.2.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 odd positions ( $O$ ) and in even positions ( $E$ ). If $\lvert O - E \rvert$ is divisible by 11, so is the number
12	Divisible by 3 and 4
15	Divisible by 3 and 5

Remark 17.2.2

In general, if a number is divisible by 2 different primes or prime powers (numbers that are powers of a prime, like $3^5$ or $2^4$ ), then it is also divisible by their product.

For example, to find whether a number is divisible by $30 = 2 \times 3 \times 5$ , you just check whether it's divisible by each of $2$ , $3$ and $5$ using the divisibility rules.

Try it

Problem 17.5.3

AMC 8

How many three-digit numbers are divisible by 13?

Problem 17.5.17(additional)

AMC 8

The number 64 has the property that it is divisible by its units digit. How many whole numbers between 10 and 50 have this property?

Problem 17.5.6

AMC 8

The 5-digit number $\underline{2}\,\underline{0}\,\underline{1}\,\underline{8}\,\underline{U}$ is divisible by 9. What is the remainder when this number is divided by 8?

Contest cornerreal contest problems

Problem 17.5.5

The 7-digit numbers 74A52B1 and 326AB4C are each multiples of 3. Which of the following could be the value of C?

(A) 1 (B) 2 (C) 3 (D) 5 (E) 8

Problem 17.5.12

AMC 8

The digits 1, 2, 3, 4, and 5 are each used once to write a five-digit number PQRST. The three-digit number PQR is divisible by 4, the three-digit number QRS is divisible by 5, and the three-digit number RST is divisible by 3. What is P?

Problem 17.5.14

AMC 10

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 17.5.19(additional)

MATHCOUNTS

Ayasha, Beshkno, and Chenoa were all born after 2000. Each of them was born in a year after 2000 that is divisible by exactly one of the prime numbers 2, 3 or 5. Each of these primes is a divisor of one of the birth years. What is the least possible sum of their birth years?

Checkpoint for section 17.2

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

17.30%

Prime Factorization

In this section you will be able to write any number as a product of primes, and use that to break hard divisibility problems into easy rules.

Every number is built from primes, like a house from bricks. 60 is 2 × 2 × 3 × 5, and no other set of primes makes 60.

A prime factorization writes a number as a product of primes, like $60 = 2^2 \times 3 \times 5$ . However you split, you end with the same primes.

To test divisibility by a big number like 264, factor it first: $264 = 8 \times 3 \times 11$ . Then use the rules for 8, 3 and 11.

Exploreplay first, formulas later

Try this: 60 is waiting to be split. Choose 6 × 10, then keep splitting. What primes are left at the bottom?
Try this: Type 60 again and split it as 2 × 30 instead. Do you end with the same primes?
Try this: Turn on Repeated division and try 264. How does the ladder match the tree?

Name it

Remark 17.3.1

In these types of problems, it's almost always best to first find the prime factorization of the number, and then use the divisibility rules for each of the primes or prime powers in the prime factorization.

Watch itpredict, then reveal

Example 17.1

Find the prime factorization of 117.

1
Is 117 divisible by 2?

Predict first:

Example 17.2

AMC 8

Let $Z$ be a 6-digit positive integer, such as 247247, whose first three digits are the same as its last three digits taken in the same order. Which of the following numbers must also be a factor of $Z$ ?

(A) 11 (B) 19 (C) 101 (D) 111 (E) 1111

1
Split $247247$ into $247 \times 1000 + 247$ . What is $247247 \div 247$ ?

Predict first:
Your prediction

open on YouTube

Example 17.3

MATHCOUNTS

What four-digit number has tens digit 2 and units digit 8, is a multiple of 16, and when its digits are reversed the result is also a multiple of 16?

1
Call the number $ab28$ . Every multiple of 16 is a multiple of 8. What does the rule for 8 say about the last three digits $b28$ ?

Predict first:

open on YouTube

Example 17.4

AMC 8

A number is called flippy if its digits alternate between two distinct digits. For example, 2020 and 37373 are flippy, but 3883 and 123123 are not. How many five-digit flippy numbers are divisible by 15?

1
Divisible by 15 means divisible by which two numbers?

Predict first:
Your prediction

open on YouTube

Example 17.5

Omega Learn

The 3 digit number A3B is divisible by 15. What is the sum of all such possible numbers?

1
For a number to be divisible by 15, what other numbers must it be divisible by?

Predict first:
Your prediction

Example 17.6

Omega Learn

The number 3AB76 is divisible by 264, where A and B are digits. Find A + B.

1
For a number to be divisible by 264, what other numbers must it be divisible by?

Predict first:
Your prediction

Try it

Problem 17.5.2

AMC 8

What is the sum of the two smallest prime factors of 250?

Problem 17.5.15(additional)

What is the prime factorization of 420?

Problem 17.5.16(additional)

What is the prime factorization of 1001?

Problem 17.5.8

AMC 8

If $3^p + 3^4 = 90$ , $2^r + 44 = 76$ , and $5^3 + 6^s = 1421$ , what is the product of $p$ , $r$ , and $s$ ?

Contest cornerreal contest problems

Problem 17.5.11

Omega Learn Math Contest

The number AB962C is divisible by 792 where A, B, C are digits. What is the value of A?

Problem 17.5.18(additional)

Omega Learn

The number 8173ABC is divisible by 165. What is the average of all such 3 digit numbers ABC that satisfy this condition?

Problem 17.5.20(additional)

Omega Learn

Sohil is thinking of a 5 digit number such that the first 3 digits are divisible by 63, the middle 3 digits are divisible by 8, and the last 3 digits are divisible by 11. What is the largest possible number he can be thinking of?

Checkpoint for section 17.3

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

17.40%

Legendre’s Formula

In this section you will be able to count how many times a prime divides n!, and how many zeros n! ends with.

10! = 3,628,800 ends in two zeros. How many zeros does 100! end with? It has 158 digits, so you’ll want a shortcut!

Each multiple of $p$ gives one factor of $p$ . Multiples of $p^2$ hide a second one, multiples of $p^3$ a third. Count them layer by layer.

Exploreplay first, formulas later

Try this: Each column is a multiple of 2 up to 10. Press Add next layer. Which numbers grow taller, and why?
Try this: Keep adding layers until the button stops. Count the blocks. Do you get 5 + 2 + 1?
Try this: Pick p = 5 and set n to 100. Why do the zeros at the end of 100! come from the 5s?

Name it

Theorem 17.4.1 · Legendre's Theorem

The number of factors of a prime $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

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

Watch itpredict, then reveal

Example 17.7

Find the number of 0's at the end of 100!.

1
Each 0 at the end comes from a factor of $10 = 2 \times 5$ . Which factor is rarer in $100!$ , 2 or 5?

Predict first:

open on YouTube

Contest cornerreal contest problems

Problem 17.5.9

AMC 8

For any positive integer $M$ , the notation $M!$ denotes the product of the integers 1 through $M$ . What is the largest integer $n$ for which $5^n$ is a factor of the sum $98! + 99! + 100!$ ?

Problem 17.5.13

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$ ?

Checkpoint for section 17.4

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

17.5

Practice Problems

In this section you will be able to mix primes, divisibility rules and factorizations on contest problems.

One last puzzle that uses the rules for 2, 3, 4, 5 and 6 all at once. Every problem has three hints if you get stuck.

Want every problem from this chapter on one page? Open the problem set.

Contest cornerreal contest problems

Problem 17.5.21(additional)

BmMT

How many permutations of 123456 are divisible by their last digit? For instance, 123456 is divisible by 6, but 561234 is not divisible by 4.

Formula cards

Concept 17.2.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 odd positions ( $O$ ) and in even positions ( $E$ ). If $\lvert O - E \rvert$ is divisible by 11, so is the number
12	Divisible by 3 and 4
15	Divisible by 3 and 5

Theorem 17.4.1 · Legendre's Theorem

The number of factors of a prime $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

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

All formulas →