# Understanding a proof from Rotman's “Advanced Modern Algebra”(Chinese Remainder Theorem)

Please, read this post. I don't need to find any proof of the theorem, a I need to understand a specific step in a stecific proof. This is the proof from J.Rotman's book "Advanced Modern Algebra" 3rd edition (p.27, Theorem A-2.35). The statement of the theorem is

If $\gcd(m,m') = 1$, then the two congruences

$x \equiv b \mod{m}$

$x \equiv b' \mod{m'}$

have a common solution, and any two solutions are congruent $\mod{mm'}$

The proof of it(the part, the existence)

By Theorem A-2.34, $x = sb + km, s \equiv 1 \mod{m}, k \in \mathbb{Z}$. Substitute this into the second congruence and solve for $k$. Alternatively, there are integers $s$ and $s'$ with $1 = sm + s'm'$, and a common solution is

$x = b'ms + bm's'$

I need to understand how can you "solve for $k$" and how do you get $x = b'ms + bm's'$. The next thing I would like to understand is why $s$ in $x = sb + km$ which we got from Theorem A-2.34(read below for the statement of the theorem) and $1 = sm + s'm'$ are the same.

Theorem A-2.34

If $\gcd(a,m) = 1$, then, for every integer $b$ the congruence

$ax \equiv b \mod{m}$

can be solved for $x$; in fact, $x = sb$, where $sa \equiv 1 \mod{m}$ is one solution. Moreover, any two solutions are congruent $\mod{m}$

The two approaches given by Rotman to demonstrate the existence of a solution to the simultaneous congruences will not, in general, yield the same value for $x.$ So, solving for $k$ to get $x=sb+km$ in the first approach will not necessarily produce the same solution as $x=b'ms+bm's'$ in the second approach, and the value for $s$ in the first approach will not necessarily be the same as the value for $s$ in the second. You can easily convince yourself of this by trying out a small example.
In the second approach, Rotman just presents a solution $x=b'ms+bm's'$ given $s$ and $s'$ satisfying $1=sm+s'm'.$ This solution clearly satisfies both congruences. In the first approach, one can solve for $k$ by making the following observations.
Substitution of $x$ into the second equation gives $(sb + km) \equiv b'\bmod m',$ or equivalently, $sb+km- b'=rm'$ for some integer $r.$ This can be rewritten as $km-rm'=b'-sb.$ But since we know that $\gcd (m,m') = 1$, there exist integers $u$ and $v$ such that $um+vm'=1.$ Scaling this up, we then have $(b'-sb)um+(b'-sb)vm'=(b'-sb).$ So, we can just read off the value for $k$ as $(b'-sb)u,$ and our solution can then be written down as $x= sb+(b'-sb)um.$
That’s all there is to it, but as a sanity check, to make sure we didn’t make a mistake, we can confirm that the solution we’ve written down really does satisfy the second congruence. Using our scaled up equation and substituting in $r=-(b'-sb)v$ to clean things up, we have that $x= sb+(b'-sb)um=sb+[(b'-sb)+rm']= b'+rm'\equiv b'\bmod m'.$