Question

Let $n = 20^{26}$. What is the remainder when $49^n + 41^n + 10n$ is divided by 100?

• A. 2
• B. 1
• C. 90
• D. 49

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.

Answer 1

The Correct Option is A

Step 1: Understanding the Concept:
This is a modular arithmetic problem. We need to find \( (49^{n} + 41^{n} + 10n) \pmod{100} \).
Key Formula or Approach:
Use Euler's Totient Theorem: \( a^{\phi(m)} \equiv 1 \pmod{m} \) if \( \gcd(a, m) = 1 \).
For \( m = 100 \), \( \phi(100) = 100(1-1/2)(1-1/5) = 40 \).

Step 2: Detailed Explanation:
1. Evaluate \( n \pmod{40} \):
\( n = 20^{26} = 20^{2} \times 20^{24} = 400 \times 20^{24} \).
Since 400 is a multiple of 40, \( n \equiv 0 \pmod{40} \). Thus \( n = 40k \).
2. Evaluate \( 49^{n} \pmod{100} \):
Since \( \gcd(49, 100) = 1 \), by Euler's theorem:
\[ 49^{40} \equiv 1 \pmod{100} \implies 49^{40k} \equiv (49^{40})^{k} \equiv 1^{k} \equiv 1 \pmod{100} \]
3. Evaluate \( 41^{n} \pmod{100} \):
Similarly, \( \gcd(41, 100) = 1 \):
\[ 41^{n} = 41^{40k} \equiv 1 \pmod{100} \]
4. Evaluate \( 10n \pmod{100} \):
\( 10n = 10 \times 20^{26} = 10 \times (20^{2} \times 20^{24}) = 4000 \times 20^{24} \).
Since 4000 is a multiple of 100, \( 10n \equiv 0 \pmod{100} \).
5. Total Remainder:
\[ 1 + 1 + 0 = 2 \]

Step 3: Final Answer:
The remainder is 2.