Have given below two
questions on Number Theory, focusing on factorial.
Questions
1. How many trailing
zeroes (zeroes at the end of the number) does 60! have?
2. What is the highest
power of 12 that divides 54! ?
Correct
Answers
Question 1: 14 zeroes
Question 2: 25
Explanatory
Answers
1. How many trailing
zeroes (zeroes at the end of the number) does 60! have?
To
start with, the number of trailing zeroes in the decimal representation of a
number = highest power of 10 that can divide the number.
For
instance,
3600
= 36 * 102
45000
= 45 * 103
In
order to approach this question, let us first see the smallest factorial that
ends in a zero.
1!
= 1
2!
= 2
3!
= 6
4!
= 24
5!
= 120
Now,
5! ends in a zero as we have get a product of 10 when we compute 1 * 2 * 3 * 4
* 5
10
is 2*5, so we get a factor of 10 every time we get a 2 and a 5 in the
factorial.
So,
5! has 1 zero. The factorial that ends with 2 zeroes is 10!
15!
has 3 zeroes.
20!
has 4 zeroes and so on.
An
extra zero is created every time a 2 and 5 combine. Every even number gives a
two, while every fifth number gives us a 5.
Now,
the critical point here is that since every even number contributes at least a
2 to the factorial, 2 occurs way more frequently than 5. So, in order to find
the highest power of 10 that can divide a number, we need to count the highest
power of 5 that can divide that number. We do not need to count the number of
2’s in the system as there will be more than 2’s than 5’s in any factorial.
Now,
every multiple of 5 will add a zero to the factorial. 1 * 2 * 3 *…..59 * 60 has
twelve multiples of 5. So, it looks like 60! will end in 12 zeroes. But we need
to make one more adjustment here.
25
is 52, so 25 alone will contribute two 5’s, and therefore add two
zeroes to the system. Likewise, any multiple of 25 will contribute an
additional zero.
So,
20! has 4 zeroes, 25! has 6 zeroes.
60!
will have [60/5] zeroes arising due to the
multiples of and an additional [60/25] due to the presence of 25 and 50. {We
retain only the integer component of 60/25 as the decimal part has no value}
So,
60! will end with 12 + 2 zeros. = 14 zeros.
In
general, any n! will end with [n/5] + [n/25] + [n/125] + [n/625] …… zeroes.
Generalizing
further, in case we want to find the highest power of 3 that divides n!, this
is nothing but [n/3] + [n/9] + [n/27] + [n/81] ……
The
highest power of 7 that divides n! is [n/7] + [n/49] + [n/343] ……
In
case of a composite number, we need to break into the constituent primes and
compute the highest power that divides the number.
For
instance, if we want to find the largest power of 15 that divides n!, this will
be driven by the highest powers of 3 and 5 that divide n!. Similar to the
scenario we saw with trailing zeroes, we can observe that there will definitely
be at least as many 3’s than 5’s in any factorial. So, the highest power of 15
that divides n! is simply [n/5] + [n/25] + [n/125] + [n/625] ……
2.
What is the highest power of 12 that divides 54! ?
12
= 22 * 3, so we need to count the highest power of 2 and highest
power of 3 that will divide 54! and then we can use this to find the highest
power of 12.
The
method to find highest powers of 2 and 3 are similar to the one outlined in the
previous question.
Highest
power of 2 that divides 54! = [54/2] + [54/4] + [54/8] + [54/16] + [54/32] = 27
+ 13 + 6 + 3 + 1 = 50
Highest
power of 3 that divides 54! = [54/3] + [54/9] + [54/27] = 18 + 6 + 2 = 26
Or
54! is a multiple of 250 * 326. Importantly, these are
the highest powers of 2 and 3 that divide 54!.
22
* 3 = 12. We need to see what is the highest power of 22 * 3 that we can
accommodate within 54!
In
other words, what is the highest n such that (22*3)n can
be accommodated within 250* 326
Let
us try some numbers, say, 10, 20, 30
(22
*3)10 = 220 * 310, this is within 250
* 326
(22
*3)20 = 240 * 320, this is within 250
* 326
(22
*3)30 = 260 * 330, this is not within 250
* 326
The
highest number possible for n is 25.
(22
*3)25 = 250 * 325, this is within 250
* 326, but (22 *3)26 = 252 * 326,
this is not within 250 * 326
So,
54! can be said to be a multiple of (22 * 3)25. Or, the
highest power of 12 that can divide 54! is 25.
Note:
For most numbers, we should be able to find the limiting prime. As in, to find
the highest power of 10, we need to count 5s. For the highest power of 6, we
count 3s. For 15, we count 5s. For 21, we count 7’s. However, for 12, the
limiting prime could be 2 or 3, so we need to check both primes and then verify
this.
Rajesh
Director,
2IIM
CAT
classroom course in Chennai, Bangalore and Mumbai