I am trying to prove that
$2^{700} \equiv 1 \mod 3625$
and I am supposed to use the Chinese Remainder Theorem as part of my proof.
I know that the Chinese Remainder Theorem tells me that a solution to the system
$x = a_1 \mod 29$
$x = a_2 \mod 5^3$
exists because $29$ and $5^3$ multiplied together form $3625$, but I don't see how this helps me prove the original equation. Could someone point me in the right direction?
By CRT you just have to prove:
$2^{700}\equiv 1 \bmod 29$
$2^{700}\equiv 1 \bmod 5^3$
But using Euler's theorem:
$2^{700}=(2^{\varphi(29)})^{25}\equiv 1 \bmod 29$
$2^{700}\equiv (2^{\varphi(5^3)})^7\equiv 1 \bmod 5^3$.
So the result holds. In fact this argument is a big part of the idea behind Carmichael's lambda, which is the smallest integer $k$ such that $a^k\equiv 1 \bmod n$ for all $a$.