3
$\begingroup$

Here's the question: How many trailing zeros are there in 100! (factorial of 100)?

Here's the solution: This is an easy problem. We know that each pair of 2 and 5 will give a trailing zero. If we perform prime number decomposition on all the numbers in 100!, it is obvious that the frequency of 2 will far outnumber of the frequency of 5. So the frequency of 5 determines the number of trailing zeros. Among numbers 1,2,....,99, and 100, 20 numbers are divisible by 5 (5, 10, ...., 100). Among these 20 numbers, 4 are divisible by 5^2 (25, 50, 75, 100). So the total frequency of 5 is 24 and there are 24 trailing zeros.

What I don't understand is... what is trailing zero? And how did the author use 2 and 5? (2 and 5 seem pretty random to me).

$\endgroup$
6
$\begingroup$

One thing is clear. $2 \times 5 = 10$ and there is no other way to get 10 out of 2 prime numbers.

"trailing zeros" are the zeros at the end of the number.
For example: 3200 has 2 trailing zeros. The units and the tenths position.

One other thing is clear.
Multiplying a number by 10 adds a trailing zero to that number.

So in order to find the number of zeros at the tail of a number, you need to split that number into prime factors and see how many pairs (2, 5) you can form.

For example:

300 has 2 trailing zeros. Why?
because $300 = 3 \times 2 ^ 2 \times 5^2$.
So you get 2 pairs of (5, 2).

An other example:

$4000 = 2^5 \times 5 ^3 = 2 ^2 \times (2 \times 5) ^ 3$
Hence, 3 trailing zeros.

EDIT:

For your specific question. 100!.

$100! = 1 \times 2 \times 3 \times .... \times 100$.

Which is equivalent to splitting every number into prime factors like this:

$100! = 1 \times 2 \times 3 \times 2^2 \times 5 \times (3\times 2) .... \times (2 \times 5)^2$

You need to count how many 10's you can make out of these prime numbers.
As explained above, the only way to get a 10 is $2 \times 5$.
So you need to count how many 2's and how many 5s are among the prime factors above.

The 5s can appear only in numbers that are divisible by 5.

5, 10, 20, 25, 30, 35, 40, 45, 50 , 55, 60 , 65, 70, 75, 80, 85, 90, 95, 100

and the number of 5s in the numbers above are

1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2  

Because for example

$15 = 3 \times 5$ so one single 5.
$50 = 2 \times 5 ^2$ so 2 fives.

Add them all up and you get 24 occurrences of 5.

Now you need to see if there are at least 24 occurrences of 2.
And they are because form 1 to 100 you have 50 even numbers (they all contain at least one 2).

This means that 100! can be written as

$2 ^ {50} \times 5 ^ {24} \times$ (some other factors that are never going to multiply to get to a multiple of 10 so we can ignore them).

We can split the line above (ignoring the factors that cannot multiply to reach a multiple of 10) to

$2 ^ {24} \times 2 ^{26} \times 5^{24} = (2 \times 5) ^{24} \times 2 ^{26}$

We can ignore again $2^{26}$ because that never ends with zeros (it ends with a 4 if I'm not mistaken)

Now you can see that 100! is basically a very large number that does not end with a 0 multiplied by $10 ^ {24}$. So you get 24 trailing zeros.

$\endgroup$
  • $\begingroup$ Thank you very much for your comment. I definitely understand it better. There are two questions: 1. How can this concept be applied to a factorial? 2. Why does the statement 'the frequency of 2 will far outnumber the frequency of 5' matter? $\endgroup$ – Jun Jang Sep 4 '17 at 15:23
  • $\begingroup$ See my edit. I added a few explanations for your specific case. $\endgroup$ – Marius Sep 4 '17 at 15:37
1
$\begingroup$

Trailing zeroes are as the name points zeroes in the end of the number. So 10 has 1 trailing zero. And because this is a question regarding base10 numbers, this is how you can represent any number with trailing zero - number0 = number x 10. And because 10 is actually 2 x 5 you need 2s and 5s. One 2 is enough to 'turn' all fives into zeroes. And you already have posted the number of 5s.

$\endgroup$
  • $\begingroup$ Thank you very much for your comment. I definitely understand it better. There are two questions: 1. How can this concept be applied to a factorial? 2. Why does the statement 'the frequency of 2 will far outnumber the frequency of 5' matter? $\endgroup$ – Jun Jang Sep 4 '17 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.