About a variant of the Chinese Remainder Theorem

[steenis]

Let $m$ and $m'$ be positive integers, and $d=gcm(m,m')$.
(i) The system:

$x \equiv b (mod \ m)$
$x \equiv b' (mod \ m')$

has a solution if and only if $b \equiv b' (mod \ d)$

(ii) two solutions of the system are congruent $mod \ l$, where $l = lcm(m,m')$.

I can prove part (i), but can anyone help me with part (ii) ?

Remember $gcd(a,b) \cdot lcm(a,b) = a \cdot b$

See, for instance: "Cuoco - Learning Modern Algebra (2013)", p.145 and p.148

Example:
$x \equiv 1 (mod \ 6)$ and $x \equiv 4 (mod \ 15)$
Then $m=6$, $m'=15$, $d=3$, $b=1$, $b'=4$, and $1 \equiv 4 (mod \ 3)$, so (i) applies:
$19 \equiv 1 (mod \ 6)$ and $19 \equiv 4 (mod \ 15)$.
$lcm(6,15)=30$ and all the solutions are: $\cdots \ -41,-11,19,49,79 \ \cdots$.

 

[GJA]

Hi, steenis.

Start with two solutions, say $x$ and $y$, to the system. We want to show that $l$ divides $x-y$. Since $x$ and $y$ solve the system of congruences, we have that $m$ and $m'$ divide $x-y$, which can be seen by writing $x-y = (x-b)-(y-b)$. Since $m$ and $m'$ both divide $x-y$, so too must their least common multiple, $l$, which can be proved by considering the prime factorizations of $m$ and $m'$.

 

[I like Serena]

Let $m$ and $m'$ be positive integers, and $d=gcm(m,m')$.
(i) The system:

$x \equiv b (mod \ m)$
$x \equiv b' (mod \ m')$

has a solution if and only if $b \equiv b' (mod \ d)$

(ii) two solutions of the system are congruent $mod \ l$, where $l = lcm(m,m')$.

I can prove part (i), but can anyone help me with part (ii) ?

Hi steenis,

Suppose $\gcd(m,m')=d$, then we can write $m=qd$ and $m'=q'd$ with $\gcd(q,q')=1$.
And suppose $b\equiv b' \pmod d$, so that $\frac{b'-b}d$ is an integer.

Then we have:
$$x = b + km = b' + k'm' \quad\Rightarrow\quad
b + kqd = b' + k'q'd \quad\Rightarrow\quad
kq = \frac{b'-b}d + k'q' \\ \quad\Rightarrow\quad
kq \equiv \frac{b'-b}d \pmod {q'} \quad\Rightarrow\quad
k \equiv [q]_{q'}^{-1} \frac{b'-b}d \pmod {q'} \quad\Rightarrow\quad
k = [q]_{q'}^{-1} \frac{b'-b}d + k''q' \\ \quad\Rightarrow\quad
x= b + km= b + \left([q]_{q'}^{-1} \frac{b'-b}d + k''q'\right)qd = b + [q]_{q'}^{-1}q (b'-b) + k''qq'd
$$

Thus:
$$x \equiv b + [q]_{q'}^{-1}q (b'-b) \pmod{\text{lcm}(m,m')}$$

Btw, note that in the second step we have $b + kqd = b' + k'q'd \quad\Rightarrow\quad (b-b') = (k'q' - kq)d$.
Since the right hand side is divisible by $d$, so must the left hand side be divisible by $d$, proving (i).

 

[steenis]

Thank you, both, very helpful.
However, what does $[q]_{q'}^{-1}$ mean?

 

[I like Serena]

Thank you, both, very helpful.
However, what does $[q]_{q'}^{-1}$ mean?

The multiplicative inverse of q with respect to q'.
That is, it is such that:
$$[q]_{q'}^{-1} \cdot q \equiv 1 \pmod {q'}$$
And since $q$ and $q'$ are co-prime that inverse is guaranteed to exist and to be unique.

As an example $[2]_5^{-1} = [3]_5$ because $3\cdot 2 \equiv 1 \pmod 5$.

It's a common notation to express solutions that make use of the Chinese Remainder Theorem.
Note that the general solution of $x\equiv a_i \pmod{m_i}$ with $m_i$ pairwise coprime, is $x\equiv\sum a_i \left[\frac M{m_i}\right]_{m_i}^{-1} \frac M{m_i} \pmod M$, where $M=\prod m_i$.

 

[steenis]

Clear, thank you.
I think my texts are too introductory to come across this notation.