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:
where the brackets symbolize the floor operator.
The floor of a real number is the largest integer smaller than it.
What is the number of multiples of 5 that are smaller than 137?
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.
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:
The number of numbers that are multiples of 5 but not of 3 that are smaller than 137:
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:
However, there is one additional factor of 3 in any multiple of 9:
and another additional factor of 3 in any multiple of 27:
and of of 81:
to a total number of factors of 3 equal to the sum:
and the largest power of 6 that divides 110! is:
In general, the number of factors of a prime p in a factorial N! is: