视频字幕
我们来看一个小学六年级奥数中的经典问题。某数除以5余2,除以6余4,除以7余3。问题是,这个数最小是多少?这就是著名的中国剩余定理问题。
我们先从第一个条件开始分析:除以5余2。满足这个条件的数有哪些呢?我们可以列出这些数:2、7、12、17、22、27等等。这些数在数轴上用红点表示。
现在我们加入第二个条件:除以6余4。满足这个条件的数有:4、10、16、22、28等等,用蓝点表示。我们发现,22这个数既是红点又是蓝点,它同时满足两个条件。
最后我们加入第三个条件:除以7余3。满足这个条件的数有:3、10、17、24、31、38、45、52等等,用黄点表示。我们发现,52这个数同时是红点、蓝点和黄点,它满足所有三个条件。所以答案是52。
中国剩余定理提供了一种系统性的解法。对于一般性的同余方程组:x同余a1模m1,x同余a2模m2,x同余a3模m3,我们可以用一个公式来求解。这个公式是:x等于a1乘以M1乘以y1,加上a2乘以M2乘以y2,加上a3乘以M3乘以y3。
我们来逐步计算这个问题。首先计算大M,它是所有模数的乘积:5乘以6乘以7等于210。然后计算各小M:M1等于M除以m1,也就是210除以5等于42;M2等于210除以6等于35;M3等于210除以7等于30。
接下来计算各y值,它们是对应M值的模逆元。y1是42在模5下的逆元。因为42同余2模5,所以我们需要解2y1同余1模5,得到y1等于3。y2是35在模6下的逆元。因为35同余5模6,所以我们需要解5y2同余1模6,得到y2等于5。
最后计算y3,它是30在模7下的逆元。因为30同余2模7,所以我们需要解2y3同余1模7。通过尝试,我们发现2乘以4等于8,8同余1模7,所以y3等于4。
现在我们将所有值代入公式:x等于2乘以42乘以3,加上4乘以35乘以5,再加上3乘以30乘以4。计算得到:x等于252加700加360,等于1312。由于我们要求的是最小正整数解,所以对1312取模210,得到最终答案52。
我们来验证答案52是否正确。52除以5等于10余2,满足第一个条件。52除以6等于8余4,满足第二个条件。52除以7等于7余3,满足第三个条件。所以答案正确,最小的满足条件的数是52。