11
$\begingroup$

I am writing a paper on the topology of the Golomb space and need a good (standard) reference to the following

General Chinese Remainder Theorem. For integer numbers $a_1,\dots,a_n$ and positive integers $b_1,\dots,b_n$ the intersection $\bigcap_{i=1}^n(a_i+b_i\mathbb Z)$ is not empty if and only if $a_i-a_j\in d_{i,j}\mathbb Z$ for any $1\le i<j\le n$, where $d_{ij}$ denotes the largest common divisor of the numbers $b_i,b_j$.

Looking at the internet, I found this paper in which the General Chinese Remainder Theorem is formulated as an exercise and another paper in which this theorem is proved.

But I am suspecting that such General Chinese Remainder Theorem should be proved in some standard (undergraduate) textbook in Number Theory. I need it for a proper reference. Please help!

I understand that this is rather a reference request and not a problem of research level. In case of downvotes I will delete it as soon as will get a proper answer from experts.

$\endgroup$
  • 7
    $\begingroup$ I wouldn't call this the general Chinese Remainder Theorem. The general CRT is stated for an arbitrary commutative ring and coprime ideals (and your version directly follows from it), hence you should be able to find it in any book on general abstract algebra. Off top of my head, there is a short proof in the first chapter in Atiyah and MacDonald's Commutative Algebra (which I guess is a little more specialized book), but really any general book on abstract algebra should do. $\endgroup$ – M.G. Nov 21 '17 at 11:01
  • 6
    $\begingroup$ @July The statement in the question is generalised in a different direction from the usual one, because the relevant ideals are not required to be coprime. So it does not follow from the statement in Atiyah and MacDonald. $\endgroup$ – Neil Strickland Nov 21 '17 at 11:40
  • 2
    $\begingroup$ If it helps clarifying what you are after - the version of CRT stated in this post - Chinese Remainder theorem with non-pairwise coprime moduli - is the version you need, right? And you're looking for a textbook reference for this. Here is another post about the same result: Chinese Remainder theorem with non-pairwise coprime moduli proof. $\endgroup$ – Martin Sleziak Nov 21 '17 at 11:50
  • 2
    $\begingroup$ As an historical remark, this topic is discussed in Gauss' Disquisitiones Arithmeticae, n°34. $\endgroup$ – François Brunault Nov 21 '17 at 12:13
  • $\begingroup$ @NeilStrickland: You are right, I was too hasty, this is a different generalization of CRT which does not follow immediately from the usual 'algebraic' CRT. My apologies. $\endgroup$ – M.G. Nov 21 '17 at 13:33
21
$\begingroup$

It seems that you are after this result which can be found, for example, as Theorem 3.12 in Gareth A. Jones, Josephine M. Jones: Elementary Number Theory, Springer-Verlag, London, 1998. Springer Undergraduate Mathematics Series. (It is in the section 3.5 entitled An extension of the Chinese Remainder Theorem.)

Theorem 3.12. Let $n_1,\ldots,n_k$ be positive integers and let $a_1,\ldots,a_k$ be any integers. Then the simultaneous congruences $$x\equiv a_1 \pmod{n_1}, \ldots, x\equiv a_k \pmod{n_k}$$ have a solution $x$ if and only if $\gcd(n_i,n_j)$ divides $a_i-a_j$ whenever $i\ne j$. When this condition is satisfied, the general solution forms a single congruence class $\bmod n$, where $n$ is the least common multiple of $n_1,\ldots,n_k$.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.