Сравнение по модулю

[mmol]

Нетрудно проверить, что $2^{100} = 1\ (mod\ 125)$. Подскажите, пожалуйста, как
из этого получить остаток от деления $2^{100}$ на 1000? Наверное, нужно использовать то, что
$2^{100}$ делится на 8, но не очень понимаю.

[Sonic86]

$1000=125\cdot 8; \ \text{НОД}(125;8)=1$, значит используем китайскую теорему об остатках. В принципе, сразу очевидно, что $2^{100}\equiv 8x\pmod{1000}$. Теперь ищем $x$ очень простым способом.