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

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.