NT4

From Example Problems
Jump to: navigation, search

Find the remainder when 37^{{100}} 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