2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hint: $ab = \gcd(a,b) \times \mbox{lcm}(a,b)$. Also, $\gcd( \frac{a}{\gcd(a,b) } , \frac{b}{\gcd(a,b)} ) = 1$. $\endgroup$ – Calvin Lin May 28 '13 at 18:06
  • $\begingroup$ @CalvinLin, the second statement does not hold, think $a = 12$, $b = 18$. $\endgroup$ – Andreas Caranti May 28 '13 at 18:08
  • $\begingroup$ @AndreasCaranti Indeed. I've corrected it. He needs to use $x\equiv y $ to use the second hint. $\endgroup$ – Calvin Lin May 28 '13 at 18:10
  • $\begingroup$ @crf You want the CRT with non-coprime moduli. Try reading this other question. $\endgroup$ – Calvin Lin May 28 '13 at 18:18
  • 2
    $\begingroup$ @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'. $\endgroup$ – Calvin Lin May 28 '13 at 18:25
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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)} $$

| cite | improve this answer | |
$\endgroup$

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.