Question

Last two digits of the number $19^{94}$ is (for example, if last two digits are 06 report 6 and if last two digits are 23 report 23 as answer)

Answer 1

21

Answer 2

Solution:

We need to find $19^{94} \mod 100$.

1. Modulo 4:

   $$19 \equiv 3 \pmod{4} \quad \Rightarrow \quad 19^{94} \equiv 3^{94} \equiv (-1)^{94} \equiv 1 \pmod{4}.$$

2. Modulo 25: $\phi(25)=20$, so $19^{20} \equiv 1 \pmod{25}$. Reduce the exponent:

   $$94 \mod 20 = 14 \quad \Rightarrow \quad 19^{94} \equiv 19^{14} \pmod{25}.$$

   Write $19^{14} = (19^2)^7$. Calculate:

   $$19^2 = 361 \equiv 11 \pmod{25}.$$

   Thus, we need $11^7 \mod 25$:

   $$11^2 \equiv 121 \equiv 21 \pmod{25},$$ $$11^3 \equiv 11 \cdot 21 = 231 \equiv 6 \pmod{25},$$ $$11^4 \equiv 6 \cdot 11 = 66 \equiv 16 \pmod{25},$$ $$11^5 \equiv 16 \cdot 11 = 176 \equiv 1 \pmod{25}.$$

   Hence,

   $$11^7 \equiv 11^5 \cdot 11^2 \equiv 1 \cdot 21 \equiv 21 \pmod{25}.$$

3. Using the Chinese Remainder Theorem (CRT): We have:

   $$x \equiv 21 \pmod{25} \quad \text{and} \quad x \equiv 1 \pmod{4}.$$

   Write $x = 21 + 25k$. Then:

   $$21 + 25k \equiv 1 \pmod{4}.$$

   Since $21 \equiv 1 \pmod{4}$ and $25 \equiv 1 \pmod{4}$, it follows:

   $$1 + k \equiv 1 \pmod{4} \quad \Rightarrow \quad k \equiv 0 \pmod{4}.$$

   Hence, $k = 0$ gives:

   $$x = 21.$$

Therefore, the last two digits of $19^{94}$ are 21.

---

Core Explanation (Minimal):

1. $19^{94} \mod 4=1$.
2. $19^{94} \mod 25 \equiv 19^{14} \equiv (19^2)^7$, where $19^2 \equiv 11$ and $11^7 \equiv 21$.
3. Using CRT: $x \equiv 21 \pmod{25}$ and $x \equiv 1 \pmod{4}$ gives $x = 21$.