The largest n ∈ ℕ, for which 7ⁿ divides 101!, is

In number theory, Legendre’s formula gives an expression for the exponent of the largest power of a prime number $p$ that divides the factorial $n!$. This is a fundamental concept used in combinatorics, algebra, and competitive exams like JEE Main. The logic stems from counting how many numbers from $1$ to $n$ are multiples of $p$, how many are multiples of $p^2$, and so on. Every multiple of $p$ contributes at least one factor of $p$. Multiples of $p^2$ contribute an additional factor, and this pattern continues.

For any prime number $p$ and any positive integer $n$, the exponent of the highest power of $p$ dividing $n!$ is: The summation is finite because for sufficiently large $k$, $p^k > n$, making the floor function zero.

The floor function $\lfloor x \rfloor$ (also called the Greatest Integer Function) is essential because it counts how many integers within the range $[1, n]$ are divisible by a specific power of $p$. For example, if we want to find how many multiples of 7 are in 101, we divide 101 by 7. The result is 14.42, but since we only care about full multiples (7, 14, 21…98), we take the floor value, which is 14.

Important: Legendre’s formula applies directly only to prime numbers. If you need to find the power of a composite number, say $10^n$ in $n!$, you must:
1. Prime factorize the composite number: $10 = 2 \times 5$.
2. Find the exponent of each prime factor in $n!$.
3. The answer will be the minimum of the exponents (constrained by the limiting factor). In the case of $10!$, 5 is less frequent than 2, so the power of 5 determines the power of 10 (the number of trailing zeros).

The general version of this concept is often called De Polignac’s formula. It describes the prime factorization of $n!$ as: $$n! = \prod_{p \le n, p \in \text{prime}} p^{E_p(n!)}$$ This allows mathematicians to break down massive factorials into their constituent prime parts, which is useful for checking divisibility or finding the number of divisors of $n!$.

A common JEE question is “Find the number of trailing zeros in $n!$”. This is equivalent to finding the largest $k$ such that $10^k$ divides $n!$. Since $10 = 2 \times 5$, and the power of 2 in a factorial is always greater than or equal to the power of 5, the number of trailing zeros is simply $E_5(n!)$.

Example: Trailing zeros in $100!$:
$\lfloor 100/5 \rfloor + \lfloor 100/25 \rfloor = 20 + 4 = 24$.

Instead of calculating $p^k$ every time, you can use a recursive division method:
1. Divide $n$ by $p$ to get $q_1$.
2. Divide $q_1$ by $p$ to get $q_2$.
3. Divide $q_2$ by $p$ to get $q_3$… and so on.
4. Sum all $q_i$.
For $101!$ and $p=7$: $101/7 \to 14$; $14/7 \to 2$; $2/7 \to 0$. Sum = $14+2 = 16$.

Legendre’s Formula Prime Power Divisibility Floor Function Trailing Zeros Factorial Factorization