# Find remainder with congruence theorem

Printable View

• Feb 6th 2008, 02:09 PM
tttcomrader
Find remainder with congruence theorem
This is a problem we ran over in class, but I don't fully understand it.

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

Solution:

$1000000 = (3)(333333)+1$, therefore $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?
• Feb 6th 2008, 03:51 PM
ThePerfectHacker
Quote:

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

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

Solution:

$1000000 = (3)(333333)+1$, therefore $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?

Note that $3^3 = 27$ this means that $3^3 \equiv 27 \equiv 1(\bmod 26)$.
Thus, $(3^3)^{333333} \equiv 1^{333333} (\bmod 26)$.
Thus, $3^{999999}\equiv 1(\bmod 26)$
Multiply both sides by $3$ to get your answer.