Question

Find thhe remainder when 7^203 is divided by 4

Answer 1

Using the square-and-multiply approach, we have

$7^{203}=7\times(7^{101})^2$
$7^{101}=7\times(7^{50})^2$
$7^{50}=(7^{25})^2$
$7^{25}=7\times(7^{12})^2$
$7^{12}=(7^6)^2$
$7^6=(7^3)^2$
$7^3=7\times7^2$

and so, using the property that, if $a_1\equiv b_1\mod n$ and $a_2\equiv b_2\mod n$, then $a_1a_2\equiv b_1b_2\mod n$, we get

$7\equiv3\mod4$
$7^2\equiv9\equiv1\mod4$
$7^3\equiv7\times1\equiv7\equiv3\mod4$
$7^6\equiv9\equiv1\mod4$
$7^{12}\equiv1\mod4$
$7^{25}\equiv7\times1\equiv7\equiv3\mod4$
$7^{50}\equiv9\equiv1\mod4$
$7^{101}\equiv7\times1\equiv7\equiv3\mod4$
$7^{203}\equiv7\times9\equiv3\times1\equiv3\mod4$