Key Concepts and Formulas Used

1. Sum of a Geometric Progression (GP): For a GP with first term $a$, common ratio $r$, and $n$ terms, the sum $S_n$ is given by $S_n = \frac{a(r^n - 1)}{r - 1}$, provided $r \neq 1$.
2. Difference of Squares Factorization: A fundamental algebraic identity, $a^2 - b^2 = (a - b)(a + b)$. This is often useful for simplifying expressions involving powers.
3. Divisibility Property of $x^N - 1$ by $x+1$: For an integer $x$ and positive integer $N$, $x^N - 1$ is divisible by $x+1$ if and only if $N$ is an even integer. This can be understood by evaluating $x^N - 1$ at $x=-1$; if $N$ is even, $(-1)^N - 1 = 1 - 1 = 0$, implying $(x - (-1))$, i.e., $x+1$, is a factor.
4. Binomial Theorem: $(A + B)^n = \binom{n}{0}A^n B^0 + \binom{n}{1}A^{n-1}B^1 + \dots + \binom{n}{n}A^0 B^n$. This theorem is powerful for expanding powers of binomials and often used to prove divisibility properties.

---

Step-by-Step Solution

Step 1: Express the given sum as a Geometric Progression

The given sum is $S = 1 + 49 + 49^2 + \dots + 49^{125}$. We recognize this as a geometric progression (GP).

• The first term is $a = 1$.
• The common ratio is $r = 49$ (each term is 49 times the previous term).
• The number of terms $n$ is $126$ (since the powers of 49 range from $49^0$ to $49^{125}$, which is $125 - 0 + 1 = 126$ terms).

Using the formula for the sum of a GP, $S_n = \frac{a(r^n - 1)}{r - 1}$: $S = \frac{1 \cdot (49^{126} - 1)}{49 - 1}$ $S = \frac{49^{126} - 1}{48}$ Explanation: We apply the standard GP sum formula to simplify the given series into a more compact form, which is essential for further algebraic manipulation and identifying factors.

Step 2: Factorize the numerator using the Difference of Squares Identity

We are looking for the greatest positive integer $k$ such that $49^k + 1$ is a factor of $S$. Let's focus on the numerator $49^{126} - 1$. We can rewrite $49^{126}$ as $(49^{63})^2$. Applying the difference of squares identity, $a^2 - b^2 = (a - b)(a + b)$, where $a = 49^{63}$ and $b = 1$: $49^{126} - 1 = (49^{63})^2 - 1^2 = (49^{63} - 1)(49^{63} + 1)$ Now, substitute this back into the expression for $S$: $S = \frac{(49^{63} - 1)(49^{63} + 1)}{48}$ Explanation: By factoring the numerator, we've explicitly introduced a term $49^{63} + 1$. For this term to be a factor of $S$, the remaining part of the expression, $\frac{49^{63} - 1}{48}$, must evaluate to an integer. This step directly connects the problem's requirement to a potential value of $k$.

Step 3: Prove that $\frac{49^{63} - 1}{48}$ is an integer using the Binomial Theorem

To show that $49^{63} + 1$ is indeed a factor of $S$, we must demonstrate that $49^{63} - 1$ is divisible by 48. We can express $49$ as $(1 + 48)$. Now, let's expand $(1 + 48)^{63}$ using the Binomial Theorem: $(1 + 48)^{63} = \binom{63}{0}1^{63} + \binom{63}{1}1^{62}(48) + \binom{63}{2}1^{61}(48)^2 + \dots + \binom{63}{63}(48)^{63}$ $(1 + 48)^{63} = 1 + 63 \cdot 48 + \binom{63}{2}(48)^2 + \dots + (48)^{63}$ Now, subtract 1 from both sides to get $49^{63} - 1$: $49^{63} - 1 = (1 + 63 \cdot 48 + \binom{63}{2}(48)^2 + \dots + (48)^{63}) - 1$ $49^{63} - 1 = 63 \cdot 48 + \binom{63}{2}(48)^2 + \dots + (48)^{63}$ Notice that every term on the right-hand side has a factor of 48. We can factor out 48: $49^{63} - 1 = 48 \left( 63 + \binom{63}{2}(48) + \dots + (48)^{62} \right)$ Let $M = 63 + \binom{63}{2}(48) + \dots + (48)^{62}$. Since $M$ is a sum of integers, $M$ is also an integer. Therefore, $49^{63} - 1 = 48 \cdot M$. This proves that $49^{63} - 1$ is divisible by 48. Consequently, $\frac{49^{63} - 1}{48}$ is an integer. Explanation: This step is crucial. By showing that the "remaining" part of the expression is an integer, we confirm that $49^{63}+1$ is indeed a factor of the original sum $S$. The Binomial Theorem provides a systematic way to expand $(1+X)^n$ and clearly demonstrate divisibility by $X$.

Step 4: Determine the greatest positive integer $k$

From Step 2 and 3, we have shown that: $S = (49^{63} + 1) \cdot \left( \frac{49^{63} - 1}{48} \right) = (49^{63} + 1) \cdot (\text{an integer})$ This confirms that $49^{63} + 1$ is a factor of $S$, so $k=63$ is a possible value.

To find the greatest positive integer $k$ for which $49^k + 1$ is a factor of $S = \frac{49^{126} - 1}{48}$, we first need $49^k + 1$ to be a factor of the numerator $49^{126} - 1$. Let $x = 49^k$. We need $x+1$ to be a factor of $49^{126} - 1$. This can be written as $x+1$ being a factor of $(49^k)^{126/k} - 1$, i.e., $x^{126/k} - 1$. From the divisibility property (Key Concept 3), $x^N - 1$ is divisible by $x+1$ if and only if $N$ is an even integer. Here, $N = \frac{126}{k}$. So, $\frac{126}{k}$ must be an even integer.

To find the greatest possible value of $k$, we need to make the quotient $\frac{126}{k}$ the smallest possible even integer. The smallest positive even integer is 2. Setting $\frac{126}{k} = 2$: $k = \frac{126}{2}$ $k = 63$ Thus, $k=63$ is the greatest positive integer for which $49^k + 1$ is a factor of $49^{126} - 1$. Since we have already shown that $\frac{49^{63} - 1}{48}$ is an integer, $49^{63} + 1$ is indeed a factor of $S$. Explanation: We leverage a powerful divisibility rule that relates $x+1$ to $x^N-1$. By requiring $126/k$ to be even, and then finding the largest $k$ that satisfies this (by setting $126/k$ to its minimum even value, 2), we mathematically determine the maximum possible value for $k$.

---

Tips and Common Mistakes

• Recognizing GP: Always be on the lookout for series that form a Geometric Progression, as the sum formula simplifies calculations significantly.
• Factorization: Algebraic identities like Difference of Squares are extremely useful. Practice recognizing patterns that allow their application.
• Divisibility Rules: Understanding when $a^n \pm b^n$ is divisible by $a \pm b$ is critical in number theory problems. Remember that $a^n - b^n$ is always divisible by $a-b$. It's divisible by $a+b$ if $n$ is even. And $a^n+b^n$ is divisible by $a+b$ if $n$ is odd.
• Binomial Theorem for Divisibility: The Binomial Theorem is a powerful tool to prove divisibility by rewriting terms like $X$ as $(1+D)$ or $(D-1)$ to reveal factors of $D$.
• "Greatest Positive Integer": When asked for the greatest value, ensure your reasoning systematically explores all possibilities or uses properties that directly lead to the maximum. Don't just find one possible value and assume it's the greatest.

---

Summary and Key Takeaway

This problem beautifully combines concepts from geometric progressions, algebraic factorization, and divisibility rules, specifically employing the Binomial Theorem. The core idea is to first simplify the sum, then factorize it strategically to reveal the desired term, and finally use divisibility properties to confirm that the remaining part is an integer. The critical step for finding the greatest $k$ was the application of the rule that $x^N-1$ is divisible by $x+1$ if and only if $N$ is even.```json [ {"description": "Express the given sum as a Geometric Progression.", "status": "completed"}, {"description": "Factorize the numerator using the Difference of Squares identity.", "status": "completed"}, {"description": "Prove that (49^63 - 1) / 48 is an integer using the Binomial Theorem.", "status": "completed"}, {"description": "Determine the greatest positive integer k using divisibility rules.", "status": "completed"} ]