Problem
NT-B1-M07-P020 A Short Cycle Modulo \(31\)
#20
★★★☆☆ Level 3 of 5
Find the remainder of \(2^{1000}\) modulo \(31\).
Notice that \(2^5\equiv1\pmod{31}\).
\(2^5=32\equiv1\pmod{31}\). Since \(1000\) is divisible by \(5\), \(2^{1000}=(2^5)^{200}\equiv1\pmod{31}\).
Good habit: look for a small period before using Fermat.