Specific steps in applying the Chinese Remainder Theorem to solve modular problem splitting modulus I am trying to get an idea of how the Chinese Remainder Theorem (CRT) can be used to finish up this problem, in which the problem
$$7^{30}\equiv x\pmod{ 100}$$
is attempted by splitting the modulus into relatively prime factors $25$ and $4,$ arriving at
$$\begin{align}
7^{30}&\equiv1\pmod4\\
7^{30}&\equiv-1\pmod{25}
\end{align}$$ 
I understand that the CRT may be called upon because $m=\prod m_i,$ and we have the same $7^{30}$ value on the LHS, but I don't know how to carry it out.
The question was touched upon in this post as the second entry:

How do I efficiently compute  $a^b \pmod c$ when $b$ is less than $c.$ For instance $5^{69}\,\bmod 101.$

However, I don't see this particular point clearly worked out, perhaps because it is a multi-pronged question.

Following this presentation online, this seems to be the verbatim application of the CRT without any added concepts or shortcuts:
From @gimusi's answer (upvoted):
$$\begin{cases}
x \equiv 7^{30} \pmod4\\
x\equiv 7^{30} \pmod{25}
\end{cases}$$
rearranged into
\begin{cases}
x \equiv 1 \pmod4\\
x\equiv -1 \pmod{25}
\end{cases}
Given the general form of the equations above as $x\equiv a_i \pmod {m_i},$ the CRT states $x\equiv a_1 b_1 \frac{M}{m_1}+a_2 b_2 \frac{M}{m_2}\pmod M$ with $M=\prod m_i,$ and with 
$$b_i =\left(\frac{M}{m_i}\right)^{-1}\pmod {m_i}.$$
The inverse of $\frac{M}{m_i}$ is such that $\frac{M}{m_i}\left(\frac{M}{m_i}\right)^{-1}\pmod {m_i}\equiv 1.$ 
Calculating the components:
$$\begin{align}
a_1&=1\\
a_2&=-1\\
M&=4\times 25 =100\\
\frac{M}{m_1} &= \frac{100}{4}=25\\
\frac{M}{m_2} &= \frac{100}{25}=4\\
b_1 &= \left(\frac{M}{m_1}\right)^{-1} \pmod 4 = (25)^{-1}\pmod 4 =1\\
b_2 &= \left(\frac{M}{m_2}\right)^{-1} \pmod {25}= (4)^{-1} \pmod{25}=19
\end{align}$$
Hence,
$$x=1\cdot 25 \cdot 1 + (-1)\cdot 4 \cdot 19 = -51 \pmod{100}\equiv 49.$$
 A: Welcome to Math SX! You have to use Euler's theorem as $\varphi(4)=2$, $\;\varphi(25)=20$ we have
$$ 7^{30}\equiv7^{30\bmod2}=1\mod 4,\qquad 7^{30}\equiv7^{30\bmod20}=7^{10}\mod 25$$
To find the latter power, you can use the modular fast exponentiation algorithm, but here, it will be simpler: modulo $25$,
$$7^2\equiv -1\enspace\text{so}\enspace 7^4=1,\enspace\text{hence } \;7^{30}\equiv 7^{30\bmod 4}=7^2\equiv -1.$$
Finally, since $\;25-6\cdot 4=1$ (Bézout's identity),
$$7\equiv \begin{cases}\phantom{-}1\mod4\\-1\mod 25\end{cases}\iff 7\equiv 1\cdot 25-(-1)\cdot 6\cdot 4=49\mod 100.$$
A: $$7^{30}\equiv x\pmod{ 100}$$
Could be solved easily without Chinese Remainder Theorem. Note that $7^4=2401 \equiv 1\pmod {100} $   Thus $$ 7^{30} = 7^{28}\times 49 \equiv 49 \pmod {100}$$
Solving the system with Chinese Remainder Theorem requires finding a linear combination of $25$ and $4$ to equal 1.
Such a combination is $$ 1= 1(25) -6(4) $$
Therefore the answer to the system is $$ x\equiv (1)(1)(25) +(-1)(-6)(4) \pmod {100}$$ 
That is    $$ x\equiv 49 \pmod {100}$$ 
A: From here
$$\begin{cases}
x \equiv 7^{30} \pmod4\\
x\equiv 7^{30} \pmod{25}
\end{cases}$$
by CRT we know that solutions exist $\pmod{100}$.
Then note that since $7^2=49\equiv 1 \pmod4$
$$x\equiv7^{30} \implies x\equiv 49^{15} \equiv 1\pmod4$$
and since $7^2=49\equiv -1 \pmod{25}$
$$x\equiv7^{30} \implies x\equiv 49^{15} \equiv -1\pmod{25}$$
Thus the system becomes
$$\begin{cases}
x \equiv 1 \pmod4\\
x\equiv -1 \pmod{25}
\end{cases}$$
Note that CRT guarantees that the solutions exist $\pmod{100}$ but doesn't give special shortcut to find the solution.
When you can't by inspection (in this case you can easily find $x=49$), in general to find the solution you can follow the procedure indicated here CRT -Case of two moduli
A: Chinese Remainder Theorem says:
$$\mathbb{Z}/100 \simeq \mathbb{Z}/25 \times \mathbb{Z}/4$$
where the isomorphism is given by mapping $x \pmod {100}$ to $(x \pmod {25}, x \pmod {4})$. Thus, the class of $x$ is a number from $0$ to $99$ that congruence to $1 \bmod 4$ and $24 \bmod 25$. The numbers $0 \le x \le 99$ and $x \equiv 24 \pmod {25}$ are: $24, 49, 74, 99$. Now which one is congruence to $1 \bmod 4$?
