Try to find conditions to prove the Mandarin's lemma (basic case).

75 Views Asked by At

We know that according to the CRT if we have $m,n\in \mathbb{Z}$ and $\gcd(m,n)=1$ then the system

\begin{cases} x\equiv a \pmod m \\ x \equiv b \pmod n \end{cases}

has an unique $x \pmod{mn}$ for solution.

I try to copy the proof of that statement to prove that if we have $m,n\in \mathbb{Z}$ and $1\ne d=\gcd(m,n)$ then the system

\begin{cases} x\equiv a \pmod m \\ x \equiv b \pmod n \end{cases} has (an unique ?) solution $x \pmod{lcm(m,n)}$.

Here is my attempt :

By Bachet-Bézout's identity we can claim that there exists $u,v\in \mathbb{Z}$ such that $um+vn=d$.

Multiplying this equation by $x$ : $uxm+vxn=dx$ and using the fact that $x=km+a=ln+b,\ l,k\in \mathbb{Z}$ we obtain : $ubm+van\equiv dx \pmod{lcm(m,n)}$

But we want to build $x$ and the problem is that $d$ in not invertible in $(\mathbb{Z}/lcm(m,n)\mathbb{Z})^{\times}$ (by definition).

Thanks in advance !

1

There are 1 best solutions below

6
On BEST ANSWER

Here are some details on how it goes: as said in comments, there can be a solution only if $a\equiv b \pmod{ d=\gcd(m,n)}$.

So suppose this condition is satisfied, and set $m'=\dfrac md$, $n'=\dfrac nd$, $b=a+rd\;$ and $X=\dfrac{x-a}d$. The system of congruences can be rewritten as $$\begin{cases}x-a\equiv 0&\!\!\pmod{m'd}\\ x-a\equiv rd&\!\!\pmod{n'd}\end{cases} \iff\begin{cases}X\equiv 0&\!\!\pmod{m'}\\ X\equiv r&\!\!\pmod{n'}\end{cases} $$ As $m',n'$ are coprime, this system has a unique solution modulo $m'n'$, obtained from a Bézout's relation between $m$ and $n$: $um+vn=d$: $$X\equiv rum'+0vn' \pmod{m'n'}\quad\text{whence}\quad x\equiv a+rum \pmod{dm'n'=\operatorname{lcm}(m,n)}. $$