Problem
NT-B2-M04-P019 Two Theorems in One Remainder
#19
★★★★★ Level 5 of 5
Find the remainder of \(11^{2026}\) modulo \(72\).
Use \(\varphi(72)=24\), or split \(72=8\cdot9\).
\(\gcd(11,72)=1\), \(\varphi(72)=72(1-1/2)(1-1/3)=24\). Thus \(11^{24}\equiv1\pmod{72}\). Since \(2026\equiv10\pmod{24}\), we need \(11^{10}\pmod{72}\). Now \(11^2=121\equiv49\), \(11^4\equiv49^2=2401\equiv25\), \(11^8\equiv25^2=625\equiv49\). Hence \(11^{10}=11^8\cdot11^2\equiv49\cdot49=2401\equiv25\pmod{72}\).
Higher level due to composite modulus and remaining computation.