Key Concept: The Binomial Theorem and Modular Arithmetic

The Binomial Theorem states that for any non-negative integer $n$, the expansion of $(a+b)^n$ is given by: $(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k = \binom{n}{0}a^n + \binom{n}{1}a^{n-1}b + \binom{n}{2}a^{n-2}b^2 + \dots + \binom{n}{n}b^n$ When dealing with remainders (modular arithmetic), we often express the base number in the form $(M \pm x)^n$, where $M$ is a multiple of the divisor or shares a common factor with it. This allows many terms in the binomial expansion to become multiples of the divisor, simplifying the calculation.

A particularly useful property for sums of powers is: $(X+Y)^n + (X-Y)^n = 2 \left[ \binom{n}{0}X^n Y^0 + \binom{n}{2}X^{n-2}Y^2 + \binom{n}{4}X^{n-4}Y^4 + \dots \right]$ This identity shows that terms with odd powers of $Y$ cancel out, and terms with even powers of $Y$ are doubled.

Step 1: Expressing the Base Numbers Relative to the Divisor's Factors

We need to find the remainder when $19^{200}+23^{200}$ is divided by 49. The divisor is 49. We observe that $49 = 7^2$. Our strategy is to express the base numbers, 19 and 23, in terms of a multiple of 7, which is 21. This is because $21 = 3 \times 7$, and more importantly, $21^2 = 441 = 9 \times 49$. Any term in the binomial expansion containing $21^k$ for $k \ge 2$ will be a multiple of 49.

We can write: $19 = 21 - 2$ $23 = 21 + 2$

Now, the expression becomes: $19^{200}+23^{200} = (21-2)^{200}+(21+2)^{200}$

Step 2: Applying the Binomial Theorem and Simplifying Modulo 49

Let's expand $(21-2)^{200}$ and $(21+2)^{200}$ using the Binomial Theorem and sum them up. For $(21-2)^{200}$: $(21-2)^{200} = \binom{200}{0}(21)^0(-2)^{200} + \binom{200}{1}(21)^1(-2)^{199} + \binom{200}{2}(21)^2(-2)^{198} + \dots$ For $(21+2)^{200}$: $(21+2)^{200} = \binom{200}{0}(21)^0(2)^{200} + \binom{200}{1}(21)^1(2)^{199} + \binom{200}{2}(21)^2(2)^{198} + \dots$

Now, let's sum these two expressions modulo 49. Notice that any term containing $(21)^k$ where $k \ge 2$ will be a multiple of $21^2 = 441$, which is $9 \times 49$. Therefore, these terms will be $\equiv 0 \pmod{49}$.

So, we only need to consider the first two terms (for $k=0$ and $k=1$) from each expansion: $(21-2)^{200} \equiv \binom{200}{0}(-2)^{200} + \binom{200}{1}(21)(-2)^{199} \pmod{49}$ $(21+2)^{200} \equiv \binom{200}{0}(2)^{200} + \binom{200}{1}(21)(2)^{199} \pmod{49}$

Adding these congruences: $19^{200}+23^{200} \equiv \left[ \binom{200}{0}(-2)^{200} + \binom{200}{1}(21)(-2)^{199} \right] + \left[ \binom{200}{0}(2)^{200} + \binom{200}{1}(21)(2)^{199} \right] \pmod{49}$ $19^{200}+23^{200} \equiv \binom{200}{0} \left( (-2)^{200} + (2)^{200} \right) + \binom{200}{1}(21) \left( (-2)^{199} + (2)^{199} \right) \pmod{49}$

Let's evaluate the terms in the parentheses:

1. For the first term, since 200 is an even power, $(-2)^{200} = 2^{200}$. So, $((-2)^{200} + (2)^{200}) = (2^{200} + 2^{200}) = 2 \cdot 2^{200} = 2^{201}$.
2. For the second term, since 199 is an odd power, $(-2)^{199} = -2^{199}$. So, $((-2)^{199} + (2)^{199}) = (-2^{199} + 2^{199}) = 0$.

Substituting these back: $19^{200}+23^{200} \equiv \binom{200}{0} (2^{201}) + \binom{200}{1}(21) (0) \pmod{49}$ Since $\binom{200}{0}=1$: $19^{200}+23^{200} \equiv 1 \cdot 2^{201} + 0 \pmod{49}$ $19^{200}+23^{200} \equiv 2^{201} \pmod{49}$

Step 3: Simplifying the Remaining Power Modulo 49

Now we need to find the remainder of $2^{201}$ when divided by 49. We rewrite $2^{201}$ to involve a factor of 7, which is related to our divisor 49. $2^{201} = (2^3)^{67} = 8^{67}$ Now we express 8 as $(7+1)$, as 7 is a factor of 49: $8^{67} = (7+1)^{67}$ Again, we apply the Binomial Theorem: $(7+1)^{67} = \binom{67}{0}7^0 1^{67} + \binom{67}{1}7^1 1^{66} + \binom{67}{2}7^2 1^{65} + \dots$ Modulo 49, all terms containing $7^k$ where $k \ge 2$ will be multiples of $7^2=49$, and thus will be $\equiv 0 \pmod{49}$. So, we only need to consider the first two terms: $(7+1)^{67} \equiv \binom{67}{0}1^{67} + \binom{67}{1}7^1 \pmod{49}$ $(7+1)^{67} \equiv 1 + 67 \times 7 \pmod{49}$ Now we simplify $67 \times 7 \pmod{49}$. First, reduce 67 modulo 49: $67 = 1 \times 49 + 18 \implies 67 \equiv 18 \pmod{49}$ So, $67 \times 7 \equiv 18 \times 7 \pmod{49}$ $18 \times 7 = 126$ Now, reduce 126 modulo 49: $126 = 2 \times 49 + 28 \implies 126 \equiv 28 \pmod{49}$ Substituting this back into our expression for $(7+1)^{67}$: $(7+1)^{67} \equiv 1 + 28 \pmod{49}$ $(7+1)^{67} \equiv 29 \pmod{49}$ Therefore, $2^{201} \equiv 29 \pmod{49}$.

Tips for Success and Common Mistakes

• Choose the right base: When working modulo $N$, try to express the bases as $(kN \pm x)$ or $(k \cdot \text{factor of } N \pm x)$ to simplify expansions. Here, $21$ was chosen because $21^2$ is a multiple of $49$.
• Identify relevant terms: In binomial expansions modulo $M$, often only the first few terms (or even just one) contribute to the remainder, as higher power terms become multiples of $M$.
• Parity is crucial: For expressions like $(X+Y)^n + (X-Y)^n$, terms might cancel out due to parity of exponents. Always check if the exponent makes $(-Y)^{\text{exponent}}$ equal to $Y^{\text{exponent}}$ or $-Y^{\text{exponent}}$.
• Intermediate Reduction: Continuously reduce numbers modulo the divisor in intermediate steps to keep calculations manageable. For example, reducing 67 to 18 before multiplying by 7.

Summary

By strategically applying the Binomial Theorem and carefully using modular arithmetic, we first transformed the original expression into a simpler form $2^{201} \pmod{49}$. Then, by rewriting $2^{201}$ as $8^{67} = (7+1)^{67}$, we applied the Binomial Theorem again to efficiently calculate the remainder. The final remainder when $19^{200}+23^{200}$ is divided by 49 is $\boxed{29}$. This problem effectively demonstrates how the Binomial Theorem is a powerful tool for solving problems involving large powers and modular arithmetic.