|
|
指着太阳曰日
| 来自北京
我不知道你有没有数论的基础，就从头讲起了。
Def.1 设a，b是整数，我们称b是a的倍数，当且仅当存在整数c，使得ac=b。记作a｜b，对于这件事的另外几种说法，就是a是b的因数，a整除b。
Def. 2设a，b，c是整数，我们称a和b模c同余，当且仅当c｜(a-b)，记作a≡b(mod c)。直观上，你可以当成是a除以c的余数和b除以c的余数相等。
现在我们可以叙述数论版本的中国剩余定理了。
假设我们有2n个整数，记作a1，a2……an，b1，b2，……bn。
我们考虑方程组：
x≡a1(mod b1)
x≡a2(mod b2)
……
x≡an(mod bn)
中国剩余定理其实就是告诉我们这个方程组怎么解，什么时候有解，什么时候无解，有解的时候，解集是什么样的。
我们来看看怎么解决这个问题。
为了解这个方程，我们得先准备一些工具。
Def. 3设a，b是不全为零的两个整数，c为整数，若c｜a且c｜b，称c是a，b的公因数。可以证明，两个整数a，b的公因数中有最大的一个，称为最大公因数，记作(a，b)。
贝祖定理：设a，b，c是三个整数，方程ax+by=c有整数解的充要条件是(a，b)｜c。
我们来证明这个定理，首先注意到a，b都是(a，b)倍数，故c=ax+by是(a，b)的倍数。故必要性得证。
我们现在来证明充分性。我们令A=｛ax+by｜x, y是整数，且ax+by＞0｝，我们断言minA=(a，b)。要证明这个这个断言，我们只要证明minA是a和b的公因数，且a和b的所有公因数都是minA的因数就可以了。
我们先来证明minA是a，b的公因数。因为minA∈A，故∃x₀，y₀，ax₀+by₀=minA，我们用ax+by除以minA，商为q，余数为r。
即ax+by=minA×q+r，
ax+by=(ax₀+by₀)q+r，
r=a(x-x₀q)+b(y-y₀q)
而余数r满足0≤r≤minA，故r不可能属于A，于是r≤0，于是r=0。
于是所有形如ax+by的数都是minA的倍数，于是a和b都是minA的倍数，即minA是a，b的公倍数。
我们再来证明a和b的所有公因数都是minA的因数。由于minA=ax₀+by₀，而a，b的公因数是ax₀和by₀的因数，故minA是a，b公因数的倍数。
综上minA=(a，b)，故ax+by=(a，b)有解，故ax+by=c=m(a，b)有解。充分性得证。
故贝祖定理得证。
这件事有个推论：若a，b互质，那么存在整数x，y，ax+by=1。
我们现在再回到同余。
设a≡b(mod c)，e≡f(mod c)，那么有a±e≡b±f(mod c)，ae≡bf(mod c)。
即同余是保持加减法和乘法运算的。那么关键的问题又来了，除法呢？或者说同余下有没有消去律呢？
这个问题就涉及到同余下什么元素有倒数呢？
即对于整数a，c，什么时候存在整数b，使得ab≡1(mod c)，答案是(a，c)=1，即a，c互质时。
我们来证明这件事。
ab≡1(mod c)⇔c｜(ab-1)⇔∃整数m，mc=ab-1⇔ab-mc=1⇔(a，c)=1
好了，现在所有准备都做完了，让我们来解决一开始的问题吧。
假设我们有2n个整数，记作a1，a2……an，b1，b2，……bn。
x≡a1(mod b1)
x≡a2(mod b2)
……
x≡an(mod bn)
我们先考虑最简单的情况，就是a1，a2，……an都为0的情况，这就是说x是b1，b2，……bn的倍数，也就是x是b1，b2，……bn的公倍数。
我们再考虑次简单的问题，即a1=1，a2=a3=……an=0的情况。那么后面n-1个式子显然可以合并。设b是b2，b3，……bn的最小公倍数。
那原方程组等价于
x≡1(mod b1)，①
x≡0(mod b)，②
①有解等价于x与b1互质，所以所有b的倍数里与b1互质的数就是方程组的解。
同理，a2=1，a1，a3……an等于0的情况也可以同样处理，a3=1，a1，a2……an=0的情况同理。
假如我们把这n中a里面有一个等于1，其他等于0的情况处理了。设这n种方法情况的解分别为x1，x2……xn，那么，
令x=a1x1+a2x2+……anxn，就有
x≡a1(mod b1)
x≡a2(mod b2)
……
x≡an(mod bn)
这个方程组就解出来啦。
这是数论版本的中国剩余定理。它告诉了我们如何去解一个同余方程组。但实际上我们注意到全体整数集是一个环，所以我们可以把这个定理推广到环上。但这需要抽象代数的学习，这已经不是一篇短短的回答能够将清楚的了。如果题主感兴趣可以自行学习。
最后，放一个参考资料：【【数学科普向】数学潜水艇：初等数论、初等群论-哔哩哔哩】 https://b23.tv/NGrugKz |
|
用Deepseek满血版问问看
