Let $n = 20^{26}$. What is the remainder when $49^n + 41^n + 10n$ is divided by 100?
Show Hint
To find the remainder modulo 100, always compute $\phi(100) = 40$ first.
If the exponent is a multiple of 40 and the base is coprime to 100, the term simply becomes 1.
Step 1: Understanding the Question:
We need to find the remainder when the expression $E = 49^n + 41^n + 10n$ is divided by 100, where $n = 20^{26}$.
This is equivalent to evaluating $E \pmod{100}$. Step 2: Key Formula or Approach:
We will use modular arithmetic and Euler's totient theorem.
Euler's totient function for 100 is:
\[ \phi(100) = 100 \left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{5}\right) = 40 \]
Since $\gcd(49, 100) = 1$ and $\gcd(41, 100) = 1$, Euler's theorem states that:
\[ a^{\phi(100)} \equiv 1 \pmod{100} \implies a^{40} \equiv 1 \pmod{100} \]
Thus, we need to analyze $n \pmod{40}$. Step 3: Detailed Explanation:
• Let us first compute $n \pmod{40}$ for $n = 20^{26}$:
\[ n = 20^{26} = 20^2 \cdot 20^{24} = 400 \cdot 20^{24} \]
Since $400$ is a multiple of $40$, $n$ is a multiple of $40$.
Thus, we can write $n = 40k$ for some positive integer $k$.
• Using Euler's theorem:
\[ 49^n = 49^{40k} = (49^{40})^k \equiv 1^k \equiv 1 \pmod{100} \]
\[ 41^n = 41^{40k} = (41^{40})^k \equiv 1^k \equiv 1 \pmod{100} \]
• Now, let us analyze the third term, $10n$:
Since $n = 20^{26}$, it is a multiple of $10$.
In fact, $n = 20^{26} = 2^{26} \times 10^{26}$, which is highly divisible by 10.
So, $10n = 10 \times 20^{26}$ is a multiple of 100.
Thus:
\[ 10n \equiv 0 \pmod{100} \]
• Combining all three parts:
\[ 49^n + 41^n + 10n \equiv 1 + 1 + 0 \equiv 2 \pmod{100} \]
Step 4: Final Answer:
The remainder when $49^n + 41^n + 10n$ is divided by 100 is 2.
