The user-friendly version of this content is available here.

The following content is copyright (c) 2009-2013 by Goods of the Mind, LLC.

This essential trains for: SAT-I, AMC-8, AMC-10, AMC-12, Math Kangaroo 7-8, Math Kangaroo 5-6, Math Kangaroo 9-10.

Example: Count how many of the numbers from 1 to N that are divisible by d.

Since a multiple of d occurs every d numbers, the number of multiples is equal to:

equation

where the brackets symbolize the floor operator.

The floor of a real number is the largest integer smaller than it.

For example:

equation

equation

equation

Problem:

What is the number of multiples of 5 that are smaller than 137?

equation

Sometimes, these problems are combined with set theory, more specifically with various cases of computing the cardinality (i.e. number of elements) of a finite set.

Problem:

What is the number of multiples of 5 but not of 3 that are smaller than 137?

The set of multiples of 5 that are smaller than 137 has cardinality 27.

The set of numbers that are simultaneously multiples of 5 and of 3 that are smaller than 137 has cardinality:

equation

The number of numbers that are multiples of 5 but not of 3 that are smaller than 137:

equation

Example:

What is the maximum power of 6 that divides 110!?

We have to count how many factors of 6 there are in 110!. A factor of 6 is equivalent to a pair of factors of 2 and 3. Since in any factorial, there will be a lot more factors of 2 than of 3, it is sufficient to count the number of factors of 3.

The number of multiples of 3 is:

equation

However, there is one additional factor of 3 in any multiple of 9:

equation

and another additional factor of 3 in any multiple of 27:

equation

and of of 81:

equation

to a total number of factors of 3 equal to the sum:

equation

and the largest power of 6 that divides 110! is:

equation

In general, the number of factors of a prime p in a factorial N! is:

equation