中国の古典「孫子算経」（４〜５世紀）の中に、次のような問題がある。
ある数を、３で割ると２余り、５で割ると３余り、７で割ると２余るという。ある数は何か。
この問題は、合同式の記号（≡）を用いて、次のように書き直すことができる。
（合同式については、こちらを参照）
ある数を Ｘ として、 Ｘ≡２ （ｍｏｄ ３）
Ｘ≡３ （ｍｏｄ ５）
Ｘ≡２ （ｍｏｄ ７）
の３式を同時に満たす Ｘ を求めよ。これは、連立合同式の問題である。
この連立合同式の解法については、Ｇａｕｓｓ の方法が知られている。
Ｇａｕｓｓ の方法がいかにエレガントな解法であるかを理解するために、まず、高校生的
解法を眺めてみよう。
Ｘ≡２ （ｍｏｄ ３）から、Ｘ＝３ｐ＋２ （ｐ は整数）とかける。
さらに、Ｘ≡３ （ｍｏｄ ５）から、Ｘ＝３ｐ＋２＝５ｑ＋３ （ｑ は整数）とかける。
よって、３ｐ＋２＝５ｑ＋３ から、３ｐ＝５ｑ＋１＝６ｑ＋１−ｑ より、１−ｑ は、３の倍数。
そこで、１−ｑ＝−３ｒ （ｒ は整数）とおいて、もとの式に代入すると、
Ｘ＝５（３ｒ＋１）＋３＝１５ｒ＋８ となる。また、Ｘ≡２ （ｍｏｄ ７）なので、
Ｘ＝１５ｒ＋８＝７ｓ＋２ （ｓ は整数）とかける。
よって、１５ｒ＋８＝７ｓ＋２ から、７ｓ＝１５ｒ＋６＝１４ｒ＋ｒ＋６ より、ｒ＋６ は、７の倍数。
そこで、ｒ＋６＝７ｔ （ｔ は整数）とおいて、もとの式に代入すると、
Ｘ＝１５（７ｔ−６）＋８＝１０５ｔ−８２ （ｔ は整数） ・・・（答）
（ある数として、最小の自然数を想定すれば、上式に ｔ＝１ を代入して、２３ を得る。）
それでは、いよいよ、このページの眼目であるＧａｕｓｓ の方法を説明しよう。
Ｇａｕｓｓ の方法 （以下で、３個の連立合同式で説明しているが、何個でも成立する。）
ｐ、ｑ、ｒ が２つずつ互いに素で、ａ、ｂ、ｃ は任意の整数とする。このとき、
連立合同式 Ｘ≡ａ （ｍｏｄ ｐ）
Ｘ≡b （ｍｏｄ q）
Ｘ≡c （ｍｏｄ r）
の解は、次のようにして求められる。
ｍ＝ｐ・ｑ・ｒ とし、ｍ＝ｐ・Ｐ＝ｑ・Ｑ＝ｒ・Ｒ とおく。このとき、
Ｐ・Ａ≡１ （ｍｏｄ ｐ）
Ｑ・Ｂ≡１ （ｍｏｄ q）
Ｒ・Ｃ≡１ （ｍｏｄ r）
となる Ａ、Ｂ、Ｃ を求めれば、連立合同式の解は、
Ｘ≡ａ・Ｐ・Ａ＋b・Ｑ・Ｂ＋c・Ｒ・Ｃ （ｍｏｄ ｍ）
で与えられる。
このような解法の手順は、孫子にちなんで、孫子の剰余定理（または、中国剰余定理）と
も呼ばれる。（Ｇａｕｓｓ の方法の証明は、上の高校生的解法と同様になされる。）
実際に、冒頭の問題に対して、Ｇａｕｓｓ の方法を適用してみよう。
連立合同式
Ｘ≡２ （ｍｏｄ ３）
Ｘ≡３ （ｍｏｄ ５）
Ｘ≡２ （ｍｏｄ ７）
において、
ｍ＝３・５・７＝１０５ で、
３５・Ａ≡１ （ｍｏｄ ３）を満たすＡとして、Ａ＝２
２１・Ｂ≡１ （ｍｏｄ ５）を満たすＢとして、Ｂ＝１
１５・Ｃ≡１ （ｍｏｄ ７）を満たすＣとして、Ｃ＝１
よって、求める解は、
Ｘ≡２・３５・２＋３・２１・１＋２・１５・１
＝１４０＋６３＋３０
＝２３３ （ｍｏｄ １０５）
≡２３ （ｍｏｄ １０５）
Ｇａｕｓｓ の方法はまた、分数を部分分数に分解する問題に対しても有効である。
