不定方程与中国剩余定理详解

定理1　设二元一次不定方程为ax＋by＝c，其中a，b，c都是整数且a，b都不是0，有一组整数解x＝x0，y＝y0；又设（a，b）＝d，a＝a1d，b＝b1d，则ax＋by＝c的一切解可以表示成：x＝x0-b1t，y＝y0＋a1t，其中t＝0，±1，±2，….

定理2　二元一次不定方程ax＋by＝c有整数解的充分与必要条件是（a，b）｜c.

二元一次不定方程ax＋by＝1，（a，b）＝1的一个特殊解可以表示为

x＝（-1）n-1Qn，y＝（-1）nPn，其中

P0＝1，P1＝q1，…，Pk＝qkPk-1＋Pk-2，Q0＝0，Q1＝1，…，Qk＝qkQk-1＋Qk-2，k＝2，3，…，n.

定理3　多元一次不定方程a1x1＋a2x2＋…＋anxn＝N有整数解的充分必要条件是（a1，a2，…，an）｜N.

定理4（孙子定理）　设m1，m2，…，mk是k个两两互质的正整数，m＝m1m2…mk，m＝miMi，i＝1，2，…，k，则同余式组x≡b1（modm1），x≡b2（modm2），…，x≡bk（modmk）的解是，其中(www.xing528.com)

韩信点兵问题：有兵一队，若列成五行纵队，则末行一人；成六行纵队，则末行五人；成七行纵队，则末行四人；成十一行纵队，则末行十人，求兵数.

解：此时m＝5×6×7×11＝2310，M1＝6×7×11＝462，

M2＝5×7×11＝385，M3＝5×6×11＝330，M4＝5×6×7＝210.

解

得

故x≡3×462＋385×5＋330×4＋210×10（mod2310）≡6731≡2111（mod2310）即为所求.