Permutations & Combinations
Factorial and Highest Power of a Prime
Grade None
Question:
<p>With normal method, find the highest power of 5 in 137!.</p>
<p>29</p>
<p>33</p>
<p>35</p>
<p>84</p>
Step-by-Step Solution
Key Concept: Use Legendre's formula: the highest power of prime p dividing n! is ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ... Stop when p^k > n.
<p><strong>Step 1:</strong> Apply Legendre's formula to find the highest power of 5 in 137!</p><p>Power of 5 = ⌊137/5⌋ + ⌊137/5²⌋ + ⌊137/5³⌋ + ⌊137/5⁴⌋ + ...</p><p><strong>Step 2:</strong> Calculate each term:</p><p>⌊137/5⌋ = ⌊27.4⌋ = 27</p><p>⌊137/25⌋ = ⌊5.48⌋ = 5</p><p>⌊137/125⌋ = ⌊1.096⌋ = 1</p><p>⌊137/625⌋ = ⌊0.219⌋ = 0 (stop here)</p><p><strong>Step 3:</strong> Add the results:</p><p>27 + 5 + 1 = 33</p><p>∴ The highest power of 5 in 137! is <strong>33</strong></p>
Correct Answer: C