视频字幕
同余是数论中的重要概念。我们说a同余于b模m，记作a≡b(mod m)，当且仅当m整除a减b的差。换句话说，a和b除以m的余数相同。例如，17≡5(mod 12)，因为17减5等于12，12能被12整除。在数轴上，同余关系表现为周期性：相差m的倍数的数都是同余的。同余关系具有反射性、对称性和传递性，这些性质使得同余成为一种等价关系。
线性同余方程是形如ax≡b(mod m)的方程，其中a、b、m是已知整数，x是未知数。这类方程有解的充要条件是gcd(a,m)能整除b。判断过程很简单：首先计算a和m的最大公约数，然后检查这个最大公约数是否能整除b。如果能整除则方程有解，否则无解。让我们看几个例子：对于3x≡6(mod 9)，gcd(3,9)=3，而3能整除6，所以有解。对于5x≡7(mod 12)，gcd(5,12)=1，1能整除任何整数，所以有解。但对于6x≡4(mod 9)，gcd(6,9)=3，而3不能整除4，所以无解。
扩展欧几里得算法是求解线性同余方程的核心工具。它的目标是找到整数x和y，使得ax加by等于a和b的最大公约数。算法分为两个阶段：首先用标准欧几里得算法求出最大公约数，然后逆向推导求出x和y的值。让我们通过例子25x加9y等于gcd(25,9)来演示。首先计算：25等于9乘2加7，9等于7乘1加2，7等于2乘3加1，2等于1乘2加0，所以gcd等于1。然后逆向推导：1等于7减2乘3，将2用9减7替换，得到1等于7乘4减9乘3，再将7用25减9乘2替换，最终得到1等于25乘4减9乘11。因此x等于4，y等于负11。
现在我们来完整求解一个线性同余方程：17x≡5(mod 43)。首先检查有解条件，计算gcd(17,43)。通过欧几里得算法：43等于17乘2加9，17等于9乘1加8，9等于8乘1加1，所以gcd(17,43)等于1，方程有解。接下来应用扩展欧几里得算法求17的模43逆元。逆向推导：1等于9减8，等于9减括号17减9括号，等于9乘2减17，等于括号43减17乘2括号乘2减17，最终得到1等于43乘2减17乘5。所以17乘负5模43同余于1，即17的逆元是负5，也就是38。因此特解为x同余于5乘负5同余于负25同余于18模43。验证：17乘18等于306，306除以43余5，正确。所以通解为x同余于18模43。
中国剩余定理是解决同余方程组的强大工具。当我们有多个同余方程，且模数两两互质时，方程组有唯一解。定理提供了构造解的方法：首先计算所有模数的乘积M，然后对每个方程计算Mᵢ等于M除以mᵢ，接着求逆元yᵢ使得Mᵢyᵢ同余于1模mᵢ，最后解为各项aᵢMᵢyᵢ的和模M。让我们看经典的韩信点兵问题：x同余于2模3，x同余于3模5，x同余于2模7。首先M等于3乘5乘7等于105。然后M₁等于35，M₂等于21，M₃等于15。求逆元：35同余于2模3，所以y₁等于2；21同余于1模5，所以y₂等于1；15同余于1模7，所以y₃等于1。因此x同余于2乘35乘2加3乘21乘1加2乘15乘1，等于140加63加30等于233，同余于23模105。验证正确，答案是23。