同余定理的经典例题及解答

同余定理是一个关于整数除法的基本定理，它表明两个整数a和b，如果它们除以同一个正整数m得到的余数相等，那么a和b的差值是m的倍数。

经典例题：证明同余定理：

证明：

设a和b是两个整数，m是一个正整数。

假设a ≡ b (mod m)，也就是说，a和b除以m的余数相等。

那么，我们可以写出下面的等式：

a = qm + r （1）

b = sm + r （2）

在这里，q和s是整数，且0 ≤ r < m。

从等式（1）和（2）中，我们可以得到：

a - b = (qm + r) - (sm + r)

经过简化，我们得到：

a - b = (q - s)m

根据等式（1）和（2），我们可以知道r = a mod m = b mod m，所以有：

a - b = (q - s)m ≡ 0 (mod m)

从上面的推导我们可以得出结论，如果a ≡ b (mod m)，那么a - b一定是m的倍数。这证明了同余定理。

这个例题通过直观的推导，展示了同余定理的证明过程。