Understanding the Problem: Finding the Highest Power of a Prime in a Factorial

The problem asks for the largest integer $n$ such that $3^n$ divides $50!$. This is equivalent to finding the exponent of the prime number 3 in the prime factorization of 50!. In number theory, this is often denoted as $E_3(50!)$.

Key Concept: Legendre's Formula

To find the exponent of a prime number $p$ in the prime factorization of $n!$ (denoted as $E_p(n!)$), we use Legendre's Formula: $E_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor$ This formula can be expanded as: $E_p(n!) = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \dots$ The sum continues as long as $\frac{n}{p^k} \ge 1$. Once $p^k > n$, the term $\left\lfloor \frac{n}{p^k} \right\rfloor$ becomes 0, and all subsequent terms will also be 0.

Why Legendre's Formula Works

Let's understand the intuition behind this formula:

1. $\left\lfloor \frac{n}{p} \right\rfloor$: This term counts how many multiples of $p$ are there up to $n$. Each of these numbers contributes at least one factor of $p$ to $n!$.
2. $\left\lfloor \frac{n}{p^2} \right\rfloor$: This term counts how many multiples of $p^2$ are there up to $n$. Each of these numbers contributes an additional factor of $p$ (beyond the one already counted in $\lfloor n/p \rfloor$). For example, a number like $2p^2$ contributes two factors of $p$. It was counted once in $\lfloor n/p \rfloor$ and is counted again in $\lfloor n/p^2 \rfloor$, correctly accounting for two factors.
3. $\left\lfloor \frac{n}{p^k} \right\rfloor$: This term counts multiples of $p^k$. These numbers contribute an additional factor of $p$ for their $k$-th power. By summing these terms, we correctly account for all factors of $p$ contributed by each number from $1$ to $n$. A number that is divisible by $p^k$ but not $p^{k+1}$ will be counted exactly $k$ times in the sum (once for $p$, once for $p^2$, ..., once for $p^k$), which is precisely the number of factors of $p$ it contributes.

Step-by-Step Calculation

In our problem, $n=50$ and the prime $p=3$. We need to calculate $E_3(50!)$.

1. First term: Multiples of $3^1 = 3$ We find the number of multiples of 3 up to 50: $\left\lfloor \frac{50}{3} \right\rfloor = \lfloor 16.66\dots \rfloor = 16$ This means numbers like 3, 6, 9, ..., 48 contribute at least one factor of 3.

2. Second term: Multiples of $3^2 = 9$ We find the number of multiples of 9 up to 50: $\left\lfloor \frac{50}{9} \right\rfloor = \lfloor 5.55\dots \rfloor = 5$ These numbers (9, 18, 27, 36, 45) contribute an additional factor of 3. For instance, 9 contributes two factors of 3 in total (one counted from the $\lfloor 50/3 \rfloor$ term, and one from this term).

3. Third term: Multiples of $3^3 = 27$ We find the number of multiples of 27 up to 50: $\left\lfloor \frac{50}{27} \right\rfloor = \lfloor 1.85\dots \rfloor = 1$ The number 27 contributes an additional factor of 3. It has three factors of 3 ($3^3=27$). It was counted in $\lfloor 50/3 \rfloor$, then in $\lfloor 50/9 \rfloor$, and now in $\lfloor 50/27 \rfloor$, correctly summing to three factors.

4. Fourth term: Multiples of $3^4 = 81$ We find the number of multiples of 81 up to 50: $\left\lfloor \frac{50}{81} \right\rfloor = \lfloor 0.61\dots \rfloor = 0$ Since $3^4 = 81 > 50$, there are no multiples of 81 less than or equal to 50. All subsequent terms for higher powers of 3 will also be 0.

Summing the contributions:

Now, we sum all the calculated terms to find $E_3(50!)$: $E_3(50!) = 16 + 5 + 1 + 0 = 22$ Therefore, the largest $n$ such that $3^n$ divides $50!$ is 22.

Relevant Tips and Common Mistakes

• Prime Base Only: Legendre's Formula directly applies only when the base is a prime number. If you need to find the exponent of a composite number (e.g., $6^n$ divides $50!$), first factorize the composite number into its prime factors ($6 = 2 \times 3$). Then, find the exponent for each prime factor separately ($E_2(50!)$ and $E_3(50!)$). The final answer will be the minimum of these exponents, because you can only form as many $6$'s as you have pairs of $2$s and $3$s.
• Floor Function Accuracy: Ensure correct calculation of the floor function $\lfloor x \rfloor$, which gives the greatest integer less than or equal to $x$.
• Don't Stop Early: Make sure to continue calculating terms until $\left\lfloor \frac{n}{p^k} \right\rfloor$ becomes 0. Missing higher power terms is a common error.
• Understanding vs. Memorizing: While memorizing the formula is useful, understanding why it works helps in avoiding mistakes and applying it to variations of the problem.

Conclusion

By applying Legendre's Formula, we systematically counted all factors of 3 within the product $50!$. The total count is 22. This means $3^{22}$ is the highest power of 3 that can divide $50!$.

The final answer is $\boxed{\text{22}}$.