Question

Find thhe remainder when 7^203 is divided by 4

Answer 1

Using the square-and-multiply approach, we have


`7^(203)=7*(7^(101))^2`

`7^(101)=7*(7^(50))^2`

`7^(50)=(7^(25))^2`

`7^(25)=7*(7^(12))^2`

`7^(12)=(7^6)^2`

`7^6=(7^3)^2`

`7^3=7*7^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*1\equiv7\equiv3\mod4`

`7^6\equiv9\equiv1\mod4`

`7^(12)\equiv1\mod4`

`7^(25)\equiv7*1\equiv7\equiv3\mod4`

`7^(50)\equiv9\equiv1\mod4`

`7^(101)\equiv7*1\equiv7\equiv3\mod4`

`7^(203)\equiv7*9\equiv3*1\equiv3\mod4`