This is a problem we ran over in class, but I don't fully understand it.

Find remainder when $\displaystyle 3^{1000000}$ is divided by 26.

Solution:

$\displaystyle 1000000 = (3)(333333)+1$, therefore $\displaystyle 3^{1000000} = 3^{(333333)(3)+1} = 3^{333333}(3)$

By using the congruence theorem, we know that if a congruence b, mod n, then a and b would have the same remainder upon being divided by n.

Then it goes that the remainder is 3, but how do you get that?