Finding the Maximum Power of a Prime Dividing a Sum of Factorials

The question asks for the maximum value of a natural number 'n' such that \(5^n\) divides the sum of factorials, \(30! + 35!\). To solve this, we need to determine the highest power of 5 that divides the given expression.

Understanding Legendre's Formula for Prime Factorials

We use Legendre's Formula to find the exponent of a prime 'p' in the prime factorization of \(k!\). The formula is given by:

\( E_p(k!) = \sum_{i=1}^{\infty} \lfloor \frac{k}{p^i} \rfloor = \lfloor \frac{k}{p} \rfloor + \lfloor \frac{k}{p^2} \rfloor + \lfloor \frac{k}{p^3} \rfloor + \dots \)

This sum is finite because the terms become zero when \(p^i > k\).

Calculating the Power of 5 in 30!

Let's find the highest power of 5 that divides \(30!\). Using Legendre's formula with \(p=5\) and \(k=30\):

\( E_5(30!) = \lfloor \frac{30}{5} \rfloor + \lfloor \frac{30}{5^2} \rfloor + \lfloor \frac{30}{5^3} \rfloor + \dots \)

\( E_5(30!) = \lfloor 6 \rfloor + \lfloor \frac{30}{25} \rfloor + \lfloor \frac{30}{125} \rfloor + \dots \)

\( E_5(30!) = 6 + \lfloor 1.2 \rfloor + 0 + \dots \)

\( E_5(30!) = 6 + 1 = 7 \)

So, \(30!\) is divisible by \(5^7\), but not by \(5^8\). We can write \(30! = 5^7 \times m\), where \(m\) is an integer not divisible by 5.

Calculating the Power of 5 in 35!

Now, let's find the highest power of 5 that divides \(35!\). Using Legendre's formula with \(p=5\) and \(k=35\):

\( E_5(35!) = \lfloor \frac{35}{5} \rfloor + \lfloor \frac{35}{5^2} \rfloor + \lfloor \frac{35}{5^3} \rfloor + \dots \)

\( E_5(35!) = \lfloor 7 \rfloor + \lfloor \frac{35}{25} \rfloor + \lfloor \frac{35}{125} \rfloor + \dots \)

\( E_5(35!) = 7 + \lfloor 1.4 \rfloor + 0 + \dots \)

\( E_5(35!) = 7 + 1 = 8 \)

Thus, \(35!\) is divisible by \(5^8\), but not by \(5^9\).

Analyzing the Sum \(30! + 35!\)

We want to find the highest power of 5 that divides \(30! + 35!\). We can factor the expression:

\( 30! + 35! = 30! + 35 \times 34 \times 33 \times 32 \times 31 \times 30! \)

\( 30! + 35! = 30! (1 + 35 \times 34 \times 33 \times 32 \times 31) \)

Let \(V_p(N)\) denote the exponent of the highest power of prime \(p\) dividing \(N\). We are looking for \(V_5(30! + 35!)\).

\( V_5(30! + 35!) = V_5(30! (1 + 35 \times 34 \times 33 \times 32 \times 31)) \)

Using the property \(V_p(ab) = V_p(a) + V_p(b)\), we have:

\( V_5(30! + 35!) = V_5(30!) + V_5(1 + 35 \times 34 \times 33 \times 32 \times 31) \)

We already found \(V_5(30!) = 7\). Now, let's analyze the term \(1 + 35 \times 34 \times 33 \times 32 \times 31\).

The term \(35 \times 34 \times 33 \times 32 \times 31\) contains 35 as a factor. Since 35 is divisible by 5, the entire product \(35 \times 34 \times 33 \times 32 \times 31\) is divisible by 5.

Let \(X = 35 \times 34 \times 33 \times 32 \times 31\). Since \(X\) is divisible by 5, we can write \(X = 5k\) for some integer \(k\).

Now consider \(1 + X = 1 + 5k\).

To check if \(1 + 5k\) is divisible by 5, we look at its remainder when divided by 5:

\( (1 + 5k) \pmod 5 = (1 \pmod 5) + (5k \pmod 5) \)

\( (1 + 5k) \pmod 5 = 1 + 0 \)

\( (1 + 5k) \pmod 5 = 1 \)

Since the remainder is 1, \(1 + 35 \times 34 \times 33 \times 32 \times 31\) is not divisible by 5.

Therefore, \(V_5(1 + 35 \times 34 \times 33 \times 32 \times 31) = 0\).

Substituting this back into the expression for \(V_5(30! + 35!)\):

\( V_5(30! + 35!) = V_5(30!) + V_5(1 + 35 \times 34 \times 33 \times 32 \times 31) = 7 + 0 = 7 \)

Alternatively, we can write \(30! = 5^7 m\) (where \(5 \nmid m\)) and \(35! = 5^8 k'\) for some integer \(k'\).

\( 30! + 35! = 5^7 m + 5^8 k' = 5^7 (m + 5k') \)

Since \(5 \nmid m\), the term \(m + 5k'\) is not divisible by 5 (because \(5k'\) is divisible by 5, and the sum of an integer not divisible by 5 and an integer divisible by 5 is not divisible by 5).

Thus, the highest power of 5 that divides \(30! + 35!\) is \(5^7\).

The maximum value of \(n\) such that \(5^n\) divides \(30! + 35!\) is 7.

Summary of Calculation

Therefore, the maximum value of n is 7.

Revision Table: Understanding Factorials and Prime Powers

Additional Information: Properties of Prime Powers in Sums

When dealing with the highest power of a prime \(p\) that divides a sum or difference of two integers, say \(a\) and \(b\), where you know \(V_p(a) = \alpha\) and \(V_p(b) = \beta\):

• If \(\alpha \neq \beta\), then \(V_p(a+b) = V_p(a-b) = \min(\alpha, \beta)\). The term with the lower power of \(p\) dictates the lowest power that can be factored out of the sum/difference.
• If \(\alpha = \beta\), then \(V_p(a+b) \ge \alpha\) and \(V_p(a-b) \ge \alpha\). The exact value of \(V_p(a+b)\) or \(V_p(a-b)\) depends on whether the remaining factor (after pulling out \(p^\alpha\)) is divisible by \(p\). For example, if \(a = p^\alpha m\) and \(b = p^\beta k\) with \(p \nmid m\) and \(p \nmid k\). If \(\alpha = \beta\), then \(a+b = p^\alpha(m+k)\). \(V_p(a+b) = \alpha + V_p(m+k)\). \(V_p(m+k)\) is 0 if \(p \nmid (m+k)\), or greater than 0 if \(p \mid (m+k)\).

In this problem, we had \(V_5(30!) = 7\) and \(V_5(35!) = 8\). Since the powers (7 and 8) are different, the highest power of 5 dividing the sum \(30! + 35!\) is \(\min(7, 8) = 7\). This aligns with our detailed calculation.