To solve the two modular exponentiation problems efficiently without directly calculating large powers, we can apply modular arithmetic principles such as modular reduction and the properties of exponents under modulus.

1. Evaluate $11^{49} \mod 21$:

Using modular reduction:

• $11 \mod 21 = 11$. Thus, $11^{49} \mod 21 = (11 \mod 21)^{49} \mod 21 = 11^{49} \mod 21$.

Next, reduce powers using properties of modular arithmetic:

• Note that $11^2 \mod 21 = 121 \mod 21 = 16$,
• $11^3 \mod 21 = (11 \cdot 16) \mod 21 = 176 \mod 21 = 8$,
• $11^4 \mod 21 = (11 \cdot 8) \mod 21 = 88 \mod 21 = 4$.

We observe a repeating cycle: $11, 16, 8, 4$. The length of the cycle is 4. Thus:

• $49 \mod 4 = 1$, so $11^{49} \mod 21 = 11^1 \mod 21 = 11$.

Result: $11^{49} \mod 21 = 11$.

2. Evaluate $139^{112} \mod 27$:

Using modular reduction:

• $139 \mod 27 = 4$. Thus, $139^{112} \mod 27 = (4 \mod 27)^{112} \mod 27 = 4^{112} \mod 27$.

Next, reduce powers using properties of modular arithmetic:

• $4^2 \mod 27 = 16$,
• $4^3 \mod 27 = (4 \cdot 16) \mod 27 = 64 \mod 27 = 10$,
• $4^4 \mod 27 = (4 \cdot 10) \mod 27 = 40 \mod 27 = 13$,
• $4^5 \mod 27 = (4 \cdot 13) \mod 27 = 52 \mod 27 = 25$,
• $4^6 \mod 27 = (4 \cdot 25) \mod 27 = 100 \mod 27 = 19$,
• $4^7 \mod 27 = (4 \cdot 19) \mod 27 = 76 \mod 27 = 1$.

We observe a repeating cycle after $4^7$: $4, 16, 10, 13, 25, 19, 1$. The length of the cycle is 7. Thus:

• $112 \mod 7 = 0$, so $4^{112} \mod 27 = 4^0 \mod 27 = 1$.

Result: $139^{112} \mod 27 = 1$.

Final Answers:

1. $11^{49} \mod 21 = 11$,
2. $139^{112} \mod 27 = 1$.

Let me know if you'd like detailed explanations for the steps or have any further questions! Here are some related questions:

1. How can modular exponentiation be computed efficiently using the "exponentiation by squaring" method?
2. What are the practical applications of modular arithmetic in cryptography?
3. How can we find the cycle length in modular exponentiation problems?
4. What is the Chinese Remainder Theorem, and how does it relate to modular arithmetic?
5. Can modular arithmetic be extended to handle negative exponents? If so, how?

Tip: Modular arithmetic often involves recognizing patterns or cycles in computations. Identifying these cycles can save significant time in solving problems!