带余除法：\(a = bq + r\)
1. 带余除法基本概念
带余除法定义：
对于任意整数\(a\)和正整数\(b\)，存在唯一的整数\(q\)（商）和\(r\)（余数），使得
\(a = bq + r\)，其中\(0\leq r < b\)。
例如，当\(a = 19\)，\(b = 5\)时，\(19 = 5\times3+4\)，这里\(q = 3\)，\(r = 4\)。
整除情况：当\(r = 0\)时，我们称\(b\)整除\(a\)，记作\(b\mid a\)。
例如，\(10 = 2\times5\)，此时余数为\(0\)，所以\(2\mid10\)。
2. 带余除法重要性质
余数范围：余数\(r\)满足\(0\leq r < b\)。这是带余除法的一个基本性质，它保证了余数在一个特定的区间内。
例如，\(7\div3 = 2\cdots\cdots1\)，余数\(1\)满足\(0\leq1 < 3\)。
余数的运算性质
可加性：若\(a_1 = bq_1 + r_1\)，\(a_2 = bq_2 + r_2\)，则\((a_1 + a_2)=b(q_1 + q_2)+(r_1 + r_2)\)。
这里需要注意，如果\(r_1 + r_2\geq b\)，则需要对\((r_1 + r_2)\)再次进行带余除法，得到新的余数。
例如
\(13 = 3\times4+1\)
\(14 = 3\times4 + 2\)
\((13 + 14)=(3\times4+1)+(3\times4 + 2)=3\times(4 + 4)+(1 + 2)=3\times8 + 3\)
这里\(3\div3 = 1\cdots\cdots0\)，最终余数为\(0\)。
可乘性：若\(a_1 = bq_1 + r_1\)，\(a_2 = bq_2 + r_2\)，则
\(a_1\times a_2=(bq_1 + r_1)\times(bq_2 + r_2)=b(bq_1q_2+q_1r_2 + q_2r_1)+r_1r_2\)
同样，如果\(r_1r_2\geq b\)，需要对\(r_1r_2\)进行处理。
例如
\(5 = 3\times1+2\)
\(7 = 3\times2+1\)
\((5\times7)=(3\times1 + 2)\times(3\times2+1)\)
\(=3\times(3\times1\times2 + 1\times1+2\times2)+(2\times1)=3\times(6 + 1+4)+2 = 3\times11+2\)
3. 带余除法应用场景
求解同余方程：同余方程是数论中的重要内容。
例如，求解同余方程\(3x\equiv2\pmod{5}\)，可以通过带余除法的思路来解决。根据定义，\(3x = 5q + 2\)，尝试不同的整数\(x\)，当\(x = 4\)时，\(3\times4 = 12 = 5\times2+2\)，所以\(x = 4\)是方程的一个解。
判断整数的性质：通过带余除法可以判断一个数是否为另一个数的倍数等性质。
例如，判断\(123\)是否能被\(7\)整除，计算\(123\div7 = 17\cdots\cdots4\)，因为余数不为\(0\)，所以\(7\nmid123\)。
中国剩余定理相关问题：中国剩余定理是用于求解一组同余方程的定理。
例如，有同余方程组\(\begin{cases}x\equiv2\pmod{3}\\x\equiv3\pmod{5}\end{cases}\)
利用带余除法和中国剩余定理的方法，先找到\(3\)和\(5\)的最小公倍数\(15\)，再通过计算找到满足条件的\(x\)的值，具体计算过程为：
设\(x = 3a + 2 = 5b+3\)，从\(b = 1\)开始尝试，当\(b = 1\)时，\(5\times1+3 = 8\)，\(8\div3 = 2\cdots\cdots2\)，满足条件，所以\(x = 8\)是一个解，所有解为\(x = 8 + 15k\)（\(k\in Z\)）。
