NT4

From Exampleproblems

Jump to: navigation, search

Find the remainder when $37100$ is divided by 29.

$37^{100} \equiv 8^{100} (\mathrm{mod} 29)$

$= (8^2)^{50} = 64^{50} \equiv 6^{50} = (6^2)^{25} = 36^{25} (\mathrm{mod} 29)$

$\equiv 7^{25} = (7^5)^5 \equiv 16^5 = 2^{20} = (2^5)^4 = 32^4 \equiv 3^4 \equiv 23 (\mathrm{mod} 29)$

Main Page : Number Theory

Retrieved from "http://www.exampleproblems.com/wiki/index.php/NT4"

Views

Personal tools

Log in

Search

Toolbox

Get A Wifi Network Switcher Widget for Android