Question:

Step 1: Simplify the exponents using Euler's Totient Theorem. The modulus is $n=49$. First, we calculate Euler's totient function $\phi(49)$. Since $49 = 7^2$, we have: $$ \phi(49) = 49 \left(1 - \frac{1}{7}\right) = 49 \times \frac{6}{7} = 7 \times 6 = 42 $$ By Euler's Totient Theorem, if $\gcd(a, 49) = 1$, then $a^{42} \equiv 1 \pmod{49}$. Both 19 and 23 are coprime to 49. We can reduce the exponent 200 modulo 42: $$ 200 = 4 \times 42 + 32 $$ Therefore, $$ 19^{200} \equiv 19^{4 \times 42 + 32} \equiv (19^{42})^4 \cdot 19^{32} \equiv 1^4 \cdot 19^{32} \equiv 19^{32} \pmod{49} $$ $$ 23^{200} \equiv 23^{4 \times 42 + 32} \equiv (23^{42})^4 \cdot 23^{32} \equiv 1^4 \cdot 23^{32} \equiv 23^{32} \pmod{49} $$ We need to find the remainder of $19^{32} + 23^{32}$ when divided by 49. Step 2: Simplify the bases $19^2$ and $23^2$ modulo 49. We calculate the squares of the bases: $$ 19^2 = 361 $$ Dividing 361 by 49: $361 = 7 \times 49 + 18$. So, $19^2 \equiv 18 \pmod{49}$. $$ 23^2 = 529 $$ Dividing 529 by 49: $529 = 10 \times 49 + 39$. So, $23^2 \equiv 39 \pmod{49}$. We can also write $39 \equiv -10 \pmod{49}$. Step 3: Substitute the simplified bases into the expression. Using the results from Step 2, we can rewrite $19^{32}$ and $23^{32}$: $$ 19^{32} = (19^2)^{16} \equiv 18^{16} \pmod{49} $$ $$ 23^{32} = (23^2)^{16} \equiv 39^{16} \equiv (-10)^{16} \equiv 10^{16} \pmod{49} $$ Now we need to calculate $18^{16} + 10^{16} \pmod{49}$. Step 4: Calculate $18^{16} \pmod{49}$. Let's find the powers of 18 modulo 49: $$ 18^1 \equiv 18 \pmod{49} $$ $$ 18^2 \equiv 18 \times 18 = 324 \equiv 6 \times 49 + 30 \equiv 30 \pmod{49} $$ $$ 18^3 \equiv 18^2 \times 18 \equiv 30 \times 18 = 540 \equiv 11 \times 49 + 1 \equiv 1 \pmod{49} $$ Since $18^3 \equiv 1 \pmod{49}$, we can use this to simplify $18^{16}$: $$ 18^{16} = (18^3)^5 \cdot 18^1 \equiv 1^5 \cdot 18 \equiv 18 \pmod{49} $$ Step 5: Calculate $10^{16} \pmod{49}$. We calculate the powers of 10 modulo 49 using repeated squaring: $$ 10^1 \equiv 10 \pmod{49} $$ $$ 10^2 \equiv 10 \times 10 = 100 \equiv 2 \times 49 + 2 \equiv 2 \pmod{49} $$ $$ 10^4 \equiv (10^2)^2 \equiv 2^2 = 4 \pmod{49} $$ $$ 10^8 \equiv (10^4)^2 \equiv 4^2 = 16 \pmod{49} $$ $$ 10^{16} \equiv (10^8)^2 \equiv 16^2 = 256 \pmod{49} $$ Dividing 256 by 49: $256 = 5 \times 49 + 11$. So, $10^{16} \equiv 11 \pmod{49}$. Step 6: Combine the results to find the final remainder. From Step 4, we have $19^{200} \equiv 18^{16} \equiv 18 \pmod{49}$. From Step 5, we have $23^{200} \equiv 10^{16} \equiv 11 \pmod{49}$. Adding these two congruences: $$ 19^{200} + 23^{200} \equiv 18 + 11 \pmod{49} $$ $$ 19^{200} + 23^{200} \equiv 29 \pmod{49} $$ The remainder when $19^{200}+23^{200}$ is divided by 49 is 29. The final answer is $\boxed{29}$.