NT5

From Example Problems
Jump to: navigation, search

Find the remainder when 45^{{1000}} is divided by 31.

45^{{1000}}\equiv 14^{{1000}}\equiv 196^{{500}}\equiv 10^{{500}}\equiv 100^{{250}}\mod 31\,

\equiv 7^{{250}}\equiv (7^{3})^{{83}}\times 7\equiv 343^{{83}}\times 7\equiv 2^{{83}}\times 7\mod 31\,

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


Main Page : Number Theory