Prove that the congruences admit a simultaneous solution

[Math100]

Homework Statement

Prove that the congruences $x\equiv a\pmod {n}$ and $x\equiv b\pmod {m}$ admit a simultaneous solution if and only if $gcd(n, m)\mid (a-b);$ if a solution exists, confirm that it is unique modulo $lcm(n, m)$.

Relevant Equations

None.

Proof:

Consider the congruences $x\equiv a\pmod {n}$ and $x\equiv b\pmod {m}$.
Suppose $\exists$ a solution for $x$.
Let $d=gcd(n, m)$.
This means $\exists r, s\in\mathbb{Z}$ such that $n=dr$ and $m=ds$.
Then $x\equiv a\pmod {n}\implies x=a+nt, t\in\mathbb{Z}, x\equiv b\pmod {m}\implies x=b+mk, k\in\mathbb{Z}$.
Now we have $a+nt=b+mk\implies nt-mk=b-a$.
Observe that substituting for $m, n$ produces:
$d(sk-rt)=a-b$.
Thus, $d=gcd(n, m)\mid (a-b)$.
Conversely, suppose $gcd(n, m)\mid (a-b)$.
Then $d=gcd(m, n)$ and $d\mid (a-b)$.
This means $dt=a-b$ for some $t\in\mathbb{Z}$ such that $d=nx_{0}+my_{0}$.
Observe that $dt=nx_{0}t+my_{0}t=a-b\implies my_{0}t+b=a-nx_{0}t$.
Let $x\equiv a\pmod {n}, x\equiv b\pmod {m}$ and $y$ be any other solution.
Since $y\equiv a\pmod {n}$ and $y\equiv b\pmod {m}$,
it follows that $x\equiv y\pmod {n}$ and $x\equiv y\pmod {m}$.
Thus, $\exists$ a simultaneous solution.
Therefore, the congruences $x\equiv a\pmod {n}$ and $x\equiv b\pmod {m}$ admit a simultaneous solution
if and only if $gcd(n, m)\mid (a-b);$ and a solution exists, hence, $x\equiv y\pmod {lcm(m, n)}$.

 

[fresh_42]

Homework Statement:: Prove that the congruences $x\equiv a\pmod {n}$ and $x\equiv b\pmod {m}$ admit a simultaneous solution if and only if $gcd(n, m)\mid (a-b);$ if a solution exists, confirm that it is unique modulo $lcm(n, m)$.
Relevant Equations:: None.

Proof:

Consider the congruences $x\equiv a\pmod {n}$ and $x\equiv b\pmod {m}$.
Suppose $\exists$ a solution for $x$.
Let $d=gcd(n, m)$.
This means $\exists r, s\in\mathbb{Z}$ such that $n=dr$ and $m=ds$.
Then $x\equiv a\pmod {n}\implies x=a+nt, t\in\mathbb{Z}, x\equiv b\pmod {m}\implies x=b+mk, k\in\mathbb{Z}$.
Now we have $a+nt=b+mk\implies nt-mk=b-a$.
Observe that substituting for $m, n$ produces:
$d(sk-rt)=a-b$.
Thus, $d=gcd(n, m)\mid (a-b)$.
Conversely, suppose $gcd(n, m)\mid (a-b)$.
Then $d=gcd(m, n)$ and $d\mid (a-b)$.
This means $dt=a-b$ for some $t\in\mathbb{Z}$ such that $d=nx_{0}+my_{0}$.
Observe that $dt=nx_{0}t+my_{0}t=a-b\implies my_{0}t+b=a-nx_{0}t$.
Let $x\equiv a\pmod {n}, x\equiv b\pmod {m}$ and $y$ be any other solution.
Since $y\equiv a\pmod {n}$ and $y\equiv b\pmod {m}$,
it follows that $x\equiv y\pmod {n}$ and $x\equiv y\pmod {m}$.
Thus, $\exists$ a simultaneous solution.
Therefore, the congruences $x\equiv a\pmod {n}$ and $x\equiv b\pmod {m}$ admit a simultaneous solution
if and only if $gcd(n, m)\mid (a-b);$ and a solution exists, hence, $x\equiv y\pmod {lcm(m, n)}$.

The equivalence proof is correct, a bit confusing, but correct. I am a little bit lost in the uniqueness part.

Let me suggest a hopefully slimmer version:

Consider the congruences $x\equiv a\pmod {n}$ and $x\equiv b\pmod {m}$.

(a) Let $x$ be such a solution.
Then $n\,|\,(x-a)$ and $m\,|\,(x-b).$
Moreover, $\operatorname{gcd}(n,m)\,|\,n \wedge \operatorname{gcd}(n,m\,|\,m.$
Thus $\operatorname{gcd}(n,m)\,|\,(x-a)\wedge \operatorname{gcd}(n,m)\,|\,(x-b).$
Finally, $\operatorname{gcd}(n,m)\,|\,[(x-b)-(x-a)]=a-b.$

It follows your proof, only without the many parameters that are necessary to establish equations. The divisibility properties are sufficient.

(b) Conversely, suppose $\operatorname{gcd}(n, m)\,|\, (a-b),$ i.e. $\operatorname{gcd}(n, m)\cdot t=a-b$ for some $t\in \mathbb{Z}.$
Bézout's identity guarantees the existence of $x_0,y_0\in \mathbb{Z}$ such that $\operatorname{gcd}(n, m)=x_0n+y_0m.$ Hence
\begin{align*}
x&:=a-nx_0t=\operatorname{gcd}(n,m)\cdot t+b - nx_0t\\&\phantom{:}
=\operatorname{gcd}(n,m)\cdot t +b - \operatorname{gcd}(n,m)\cdot t +y_0m\cdot t=b +my_0t
\end{align*}
is a solution to $x\equiv a \pmod n$ and $x\equiv b \pmod m$ what had to be shown.

This uses again your ideas, only that I name Bézout's identity and save a few parameters. It is easier to read with fewer variables.

(c) Let $x,y$ be two solutions.
Then $x-y \equiv 0=a-a \pmod n$ and $x-y \equiv 0=b-b \pmod m.$ Thus $n\,|\,(x-y)$ and $m\,|\,(x-y)$. Therefore $\operatorname{lcm}(n,m)\,|\,(x-y)$ or $x=y+ s\cdot \operatorname{lcm}(n,m).$

Maybe this was what you meant. I just wasn't sure.

 

[WWGD]

Isn't this given by the Chinese Remainder Theorem? You only need to prove the remainder is Chinese ;).

 

[fresh_42]

Isn't this given by the Chinese Remainder Theorem? You only need to prove the remainder is Chinese ;).

Yes, it is. But the question asked for a proof.

 

[WWGD]

Yes, it is. But the question asked for a proof.

Doesn't CRT provide conditions on the uniqueness of solutions?

 

[fresh_42]

Doesn't CRT provide conditions on the uniqueness of solutions?

According to Wikipedia, the above exercise is basically the CRT, not the algorithmic version, but the theoretical.