# If $x\equiv y \pmod{\gcd(a,b)}$, show that there is a unique $z\pmod{\text{lcm}(a,b)}$ with $z\equiv x\pmod a$ and $z\equiv y\pmod b$

If $x\equiv y \pmod{\gcd(a,b)}$, show that there is a unique $z\pmod{\text{lcm}(a,b)}$ with $z\equiv x\pmod{a}$ and $z\equiv y\pmod{b}$

What I have so far:

Let $z \equiv x\pmod{\frac{a}{\gcd(a,b)}}$ and $z \equiv y\pmod b$. Then by the chinese remainder theorem there is a unique $z\pmod{\text{lcm}(a,b)}$ which satisfies this...

Is this the right approach here? I can't figure out how to get from $$z \equiv x\pmod{\frac{a}{\gcd(a,b)}}$$ what I need.

• Hint: $ab = \gcd(a,b) \times \mbox{lcm}(a,b)$. Also, $\gcd( \frac{a}{\gcd(a,b) } , \frac{b}{\gcd(a,b)} ) = 1$. – Calvin Lin May 28 '13 at 18:06
• @CalvinLin, the second statement does not hold, think $a = 12$, $b = 18$. – Andreas Caranti May 28 '13 at 18:08
• @AndreasCaranti Indeed. I've corrected it. He needs to use $x\equiv y$ to use the second hint. – Calvin Lin May 28 '13 at 18:10
• @crf You want the CRT with non-coprime moduli. Try reading this other question. – Calvin Lin May 28 '13 at 18:18
• @robjohn I believe that it is sufficiently different, as this is the 2-variable version with explicit accounting of the values, as opposed to the 'generalized n-variable version'. – Calvin Lin May 28 '13 at 18:25

Put $d=\gcd(a,b)$ and $\delta=x\bmod d=y\bmod d$ (here "mod" is the remainder operation). Then the numbers $x'=x-\delta$, $y'=y-\delta$ are both divisible by$~d$. In terms of a new variable $z'=z-\delta$ we need to solve the system \begin{align}z'&\equiv x'\pmod a,\\z'&\equiv y'\pmod b.\end{align} Since $x',y',a,b$ are all divisible by $d$, any solution $z'$ will have to be as well; therefore we can divide everything by$~d$, and the system is equivalent to \begin{align}\frac{z'}d&\equiv \frac{x'}d\pmod{\frac ad},\\ \frac{z'}d&\equiv \frac{y'}d\pmod{\frac bd}.\end{align} Here the moduli $\frac ad,\frac bd$ are relatively prime, so by the Chinese remainder theorem there is a solution $\frac{z'}d\in\mathbf Z$, and it is unique modulo $\frac ad\times\frac bd$. Then the solutions for $z'$ will then form a single class modulo $\frac ad\times\frac bd\times d=\frac{ab}d=\operatorname{lcm}(a,b)$, and so will the solutions for $z=z'+\delta$.

Existence: $\, x\!+\!ja = z = y\!+\!kb\, \Rightarrow\, (a,b)\mid ja\!-\!kb = y-x,\,$ so $\, y-x = e(a,b)\,$ for some $\,e.$

Bezout $\Rightarrow\exists\, c,d\!:\, ac\!-\!bd = (a,b),\,$ so $\,ace\!-\!bde = e(a,b) = y\!-\!x\,$ so $\, x \!+\! (ce)a = z = y\!+\!(de) b$

Uniqueness:  mod $\, a,b\!:\ z'\equiv z\,\Rightarrow\, a,b\mid z'-z\,\Rightarrow\ {\rm lcm}(a,b)\mid z'-z$

Existence

Bezout's Identity says that we have $g_a,g_b$ so that $$g_aa+g_bb=\gcd(a,b)\tag{1}$$ Thus, \begin{align} g_bb&\equiv\gcd(a,b)&\pmod{a}\\ g_bb&\equiv0&\pmod{b} \end{align}\tag{2} Since $x\equiv y\pmod{\gcd(a,b)}$, we have $\gcd(a,b)\mid x{-}y$. Multiplying $(2)$ by $\frac{x-y}{\gcd(a,b)}$ gives \begin{align} \frac{x-y}{\gcd(a,b)}g_bb&\equiv\frac{x-y}{\gcd(a,b)}\gcd(a,b)=x-y&\pmod{a}\\[6pt] \frac{x-y}{\gcd(a,b)}g_bb&\equiv\frac{x-y}{\gcd(a,b)}0=0&\pmod{b} \end{align}\tag{3} Adding $y$ to $(3)$ and setting $z=\frac{x-y}{\gcd(a,b)}g_bb+y$, we have \begin{align} z&\equiv x&\pmod{a}\\ z&\equiv y&\pmod{b} \end{align}

Uniquenes

Suppose that $z_1\equiv x\pmod{a}$ and $z_2\equiv x\pmod{a}$. Then $z_1\equiv z_2\pmod{a}$.

Suppose that $z_1\equiv y\pmod{b}$ and $z_2\equiv y\pmod{b}$. Then $z_1\equiv z_2\pmod{b}$.

Therefore, we have $z_a,z_b$ so that $$z_1-z_2=z_aa=z_bb\tag{4}$$ Multiplying $(1)$ by $(4)$ yields \begin{align} g_aa\color{#C00000}{z_bb}+g_bb\color{#C00000}{z_aa}&=\gcd(a,b)\color{#C00000}{(z_1-z_2)}\\ (g_az_b+g_bz_a)\frac{ab}{\gcd(a,b)}&=z_1-z_2 \end{align} Therefore, since $\gcd(a,b)\,\mathrm{lcm}(a,b)=ab$, we have $$z_1\equiv z_2\pmod{\mathrm{lcm}(a,b)}$$