Finding The Last Two Digits

Relevant wiki: Finding the last few digits of a power

Method 1 :

Let us try to find the last two digits of small powers of 6 first, and see whether we can spot a pattern or not.

$\begin{array} { r c r } 6^1 &=& \underline{06} \\ 6^2 &=& \underline{\color{#D61F06}{36}}\\ 6^3 &=& 2\underline{\color{#3D99F6}{16}} \\ 6^4 &=& 12\underline{\color{#20A900}{96}} \\ 6^5 &=& 77\underline{\color{#624F41}{76}} \\ 6^6 &=& 466\underline{\color{grey}{56}} \\ 6^7 &=& 2799\underline{\color{#D61F06}{36}} \\ 6^8 &=& 16796\underline{\color{#3D99F6}{16}} \\ \end{array}$

Did you notice that starting from $6^2$ , an increment of a power of 4 (or more precisely, by multiplying the same number by $6^5$ ) gives us the same last two digits? So the last two digits of $6^{100}$ is equals to the last two digits of all the following numbers

$6^{95}, 6^{90}, 6^{85} , \ldots , 6^{10}, 6^5$

Since we already know that $6^5 = 7776$ , and its last two digits is 76. Then the last two digits of $6^{100}$ is also $\boxed{76}$ .

---

Method 2 :

Let us solve this using a systematic approach via modular arithmetic.

This is equivalent to finding $6^{100} \bmod{100}$ .

Since $\gcd(6,100) \ne 1$ , we can't apply euler's totient function , so let us break up $100$ into product of coprime positive integers, $100 = 4\times 25$ .

So we want to find $6^{100} \bmod 4$ and $6^{100} \bmod {25}$ , and with these two remainders, we can find $6^{100} \bmod{100}$ .

It is obvious that $6^{100} \bmod 4 =0$ because $6^{100} = 6 \times 6 \times \cdots \times 6$ and the first two terms being multiplied is already divisible by 4.

Now let us evaluate $6^{100} \bmod{25}$ , notice that $\gcd(6,25) = 1$ , so we can now apply Euler's totient function to get

$6^{100} \bmod{25} = 6^{100 \pmod{\phi(25)}} \bmod {25}$

Using the properties of Euler's totient function, we have $\phi(25) = \phi(5^2) = 25 \left( 1 - \dfrac15 \right) = 20$ , by continuing the working above, we have

$6^{100} \bmod{25} = 6^{100 \bmod{\phi(25)}} \bmod {25} = 6^{100 \bmod{20}} \bmod{25}= 6^0 \bmod{25} = 1 \bmod{25}$

This leaves us with finding the smallest positive integer $x$ such that $x \equiv 0 \pmod4, x \equiv 1 \pmod {25}$ . The second congruence gives us $x = 1, 26, 51, 76, \ldots$ , for all of these numbers, the smallest number that is also divisible by 4 is 76. Thus the smallest positive integer $x$ satisfying these two congruences is $\boxed{76}$ and so is our answer.