NT-B2-M04-P019 Две теоремы в одном остатке

Используйте \(\varphi(72)=24\) или разложите \(72=8\cdot9\).

\(\gcd(11,72)=1\), \(\varphi(72)=72(1-1/2)(1-1/3)=24\). Поэтому \(11^{24}\equiv1\pmod{72}\). Так как \(2026\equiv10\pmod{24}\), нужно найти \(11^{10}\pmod{72}\). \(11^2=121\equiv49\), \(11^4\equiv49^2=2401\equiv25\), \(11^8\equiv25^2=625\equiv49\). Тогда \(11^{10}=11^8\cdot11^2\equiv49\cdot49=2401\equiv25\pmod{72}\).

Уровень выше из-за составного модуля и досчёта степени.