"Converse" to Chinese Remainder Theorem

85 Views Asked by At

There are lots of posts on MSE and the web titled "converse to CRT" but this is not the same. The following is from "Multiplicative number theory I: Classical theory" by Hugh L. Montgomery, Robert C. Vaughan:

enter image description here

In Chinese Remainder Theorem direction is to go from two numbers moduli $q_1$ and $q_2$ to a unique number modulus $q_1q_2$. But this claim of the book is a kind of converse to that. Also it is not of the form $a_1q_2m_1+a_2q_1m_2$ ($m_i$ being reciprocal to $a_i$). I search Internet and worked on it a lot but I can't reach a satisfactory proof for the claim. Anyone knows how $a \mod q_1q_2$ can be written uniquely as $a_1q_2+a_2q_1$?

1

There are 1 best solutions below

7
On BEST ANSWER

First, this is only true because $q_1$ and $q_2$ are coprime $\iff (q_1,q_2)=1$: Suppose $\color{red}a \equiv \color{blue}{a_1}q_2+\color{green}{a_2}q_1\equiv \color{blue}{a_3}q_2+\color{green}{a_4}q_1 \pmod{\color{red}{q_1q_2}}$
Then, $\color{red}a \equiv \color{blue}{a_1}q_2\equiv \color{blue}{a_3}q_2 \pmod{\color{red}{q_1}}$ Due to the coprime condition, we have a unique inverse of $q_2$ modulo $q_1$. In other words, $\color{blue}{a_1} \equiv \color{blue}{a_3} \pmod {q_1}$. But since $1\le a_1,a_3\le q_1$, they are equal. Similar argument for $a_2$ and $a_4$.