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.
Best Answer
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.