NT5

From Exampleproblems

Find the remainder when $451000$ is divided by 31.

$45^{1000}\equiv 14^{1000}\equiv 196^{500}\equiv 10^{500}\equiv 100^{250}(mod31)\,$

$\equiv 7^{250}\equiv (7^3)^{83}\times 7\equiv 343^{83}\times 7\equiv 2^{83}\times 7(mod31)\,$

$\equiv (2^5)^{16}\times 56\equiv 32^{16}\times 25\equiv 1^{16}\times 25\equiv 25(mod31)\,$

Main Page : Number Theory

NT5

From Exampleproblems

Views

Personal tools

Example problems .com

Search

Toolbox