dxd终于讲了

数论笔记：整除与求余

整除和余数是数论的基础概念，涉及整数除法的性质、表示和应用。

1. ‌整除概念与性质‌

整除指整数除法结果无余数，例如10÷2=5是整除，而10÷3≈3.333余数为2则不整除

关键性质包括：

‌传递性‌：若b整除c（记为b|c），且c整除a，则b整除a（即若b|c且c|a，则b|a）

‌加减封闭性‌：整数的倍数集对加减运算封闭，即若a和b是某整数的倍数，则a±b也是其倍数

‌与除尽的区别‌：整除要求商为整数，而除尽允许结果为有限小数（如10÷4=2.5可除尽但不是整除）

2. ‌余数的表示与计算‌

余数是除法后的剩余部分，范围在0到除数减1之间。常用表示法为：

被除数=除数×商+余数（例如364÷37：37×9=333，余数=364−333=31）

通式表达：被d除余r的数可写为d·k+r（k为整数），如被5除余4的数为5k+4（k=0时值为4，k=1时值为9）

实际计算需先估算最大商，再用减法求余（如127÷8：8×15=120≤127，余数=127−120=7）

3. ‌余数的性质与定理‌

余数具有代数性质，简化复杂计算：

‌可加性‌：a和b的和除以c的余数，等于a、b分别除以c的余数之和再取余（例如(23+16)÷5余4，因23÷5余3、16÷5余1，3+1=4）

‌可乘性‌：a和b的积除以c的余数，等于a、b分别除以c的余数之积再取余（如23×16÷5余3，因3×1=3）

‌同余定理‌：若a和b对模m同余（记为a≡b mod m），则a−b被m整除；该定理在求解如“物不知数”问题时关键

4. ‌应用实例与方法‌

余数问题常见于优化求解：

‌最小公倍数法‌：例如一篮水果3个3个数余2个、4个4个数余3个、5个5个数缺1个（即余4）。列表找公倍数：满足前两条件的数序列为11,23,35,...，验证得59（59+1=60被5整除）

‌弃九法‌：求大数除以9的余数时，抛弃和为9的数字（如数字中9、4+5、2+7舍弃），剩余数字求和再除9取余；例如某大数弃九后剩8和4，8+4=12÷9余3，即原数余3