Question

last 2 digits of 19^36

Answer 1

81

Answer 2

We need to find the last two digits of $19^{36}$, i.e., compute $19^{36} \mod 100$.

1. Modulo 4 Calculation:

   Since $19 \equiv 3 \pmod{4}$ and $3 \equiv -1 \pmod{4}$, we have:

   $$19^{36} \equiv 3^{36} \equiv (-1)^{36} \equiv 1 \pmod{4}.$$

2. Modulo 25 Calculation:

   Using Euler’s Totient Theorem, note that $\phi(25) = 20$ so that:

   $$19^{20} \equiv 1 \pmod{25}.$$

   Reduce the exponent:

   $$36 \mod 20 = 16 \quad \Rightarrow \quad 19^{36} \equiv 19^{16} \pmod{25}.$$

   Write $19^{16}$ as:

   $$19^{16} = (19^2)^8.$$

   Now, calculate:

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

   So,

   $$19^{36} \equiv 11^8 \pmod{25}.$$

   Next, compute $11^8$ using successive squaring:

   $$11^2 \equiv 121 \equiv 21 \pmod{25},$$ $$11^4 \equiv 21^2 = 441 \equiv 16 \pmod{25},$$ $$11^8 \equiv 16^2 = 256 \equiv 6 \pmod{25}.$$

   Thus,

   $$19^{36} \equiv 6 \pmod{25}.$$

3. Using the Chinese Remainder Theorem (CRT):

   We have the system:

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

   Write $x = 6 + 25k$ for some integer $k$. Now, substitute into the first congruence:

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

   As $6 \equiv 2 \pmod{4}$ and $25 \equiv 1 \pmod{4}$, we simplify:

   $$2 + k \equiv 1 \pmod{4} \quad \Rightarrow \quad k \equiv -1 \equiv 3 \pmod{4}.$$

   So, let $k = 3$ (the smallest positive solution). Then:

   $$x = 6 + 25(3) = 6 + 75 = 81.$$

Thus, the last two digits of $19^{36}$ are 81.