1
$\begingroup$

Prove that if a solution exists to the congruences $x \equiv a$ (mod $n_1$), $x \equiv b$ (mod $n_2$), then it is unique modulo lcm($n_1, n_2$)

I'm having a trouble showing this. I think I need to show that if $x_1, x_2$ are simultaneous solutions to the congruences, then $x_1 \equiv x_2$ modulo lcm($n_1,n_2$). However, my efforts have been unsuccessful so far. I would greatly appreciate any help.

$\endgroup$
2
  • $\begingroup$ Let $x=a+r_1n_1=b+r_2n_2$ where $r_1,r_2$ are integers So, $a-b=r_2n_2-r_1n_1$ Now if $\dfrac{n_1}{N_1}=\dfrac{n_2}{N_2}=d=(n_1,n_2)\implies(N_1,N_2)=1$ $\implies a-b=d(r_2N_2-r_1N_1)$ For the existence of the solution $d$ must divide $a-b$ $\endgroup$ Commented Jan 24, 2015 at 12:35
  • $\begingroup$ @labbhattacharjee You've shown that the solution exists if $gcd(n_1,n_2) | a-b$, but I'm not asking for that question... $\endgroup$ Commented Jan 24, 2015 at 12:43

1 Answer 1

3
$\begingroup$

Suppose you have two solutions $x_1$ and $x_2$ since $x_1 \equiv a \equiv x_2 \mod n_1$ and $x_1 \equiv b \equiv x_2 \mod n_2$ you have $x_1 \equiv x_2 \mod n_1$ and $x_1 \equiv x_2 \mod n_2$.

This means that $n_1 \mid x_1 -x_2$ and $n_2 \mid x_1 - x_2$. Therefore $x_1 - x_2$ is a multiple of both $n_1$ and $n_2$. So, it is a multiple of the least common multiple of $n_1$ and $n_2$ by the very definition of that notion. Yet, going back to congruences this means $x_1 - x_2$ is $0$ modulo $\operatorname{lcm} (n_1,n_2)$, that is it is $x_1 \equiv x_2$ modulo $\operatorname{lcm} (n_1,n_2)$, as we want.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .