What is the largest value for n (natural number) such that 6^n divides the product of the first 100 natural numbers?
– 6 = 2 * 3. The highest power of 6 in 100! is limited by the highest power of the less frequent prime factor, which is 3.
– The highest power of a prime p dividing n! is given by Legendre’s formula: floor(n/p) + floor(n/p^2) + floor(n/p^3) + …
– For p=3 and n=100:
Power of 3 in 100! = floor(100/3) + floor(100/9) + floor(100/27) + floor(100/81)
= 33 + 11 + 3 + 1 = 48.
– For p=2 and n=100:
Power of 2 in 100! = floor(100/2) + floor(100/4) + floor(100/8) + floor(100/16) + floor(100/32) + floor(100/64)
= 50 + 25 + 12 + 6 + 3 + 1 = 97.
– So, 100! contains 2^97 * 3^48 * …
– For 6^n = (2*3)^n = 2^n * 3^n to divide 100!, we must have n ≤ 97 and n ≤ 48.
– The largest integer n satisfying both conditions is n = 48.