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'.$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.