同余基础概念
同余是一个在数学中非常重要的概念。当两个数之间的差是另一个数的倍数时，我们称这两个数对于给定的模数模同余。因此，同余是模运算的基本概念之一。
对于整数a，b和模数n，如果a-b能够整除n，则我们可以表示为a≡b(mod n)，读作“a与b在模n下同余”。其中“≡”表示同余的符号。
同余有几种性质：
- 自反性：a≡a(mod n)
- 对称性：如果a≡b(mod n)，那么b≡a(mod n)
- 传递性：如果a≡b(mod n)，b≡c(mod n)，那么a≡c(mod n)
- 加法性：如果a≡b(mod n)，c≡d(mod n)，那么a+c≡b+d(mod n)
- 减法性：如果a≡b(mod n)，c≡d(mod n)，那么a-c≡b-d(mod n)
- 乘法性：如果a≡b(mod n)，c≡d(mod n)，那么a×c≡b×d(mod n)
这些性质使同余成为数学中非常有用的工具，可以在很多数学问题中使用，例如解决线性同余方程和计算模数的倒数等。
同余的应用
同余的应用非常广泛，比如：
- 在密码学中，同余被广泛用于公钥密码的生成。RSA算法就是一种利用同余的加密算法。
- 在计算机科学中，同余被用于研究哈希函数和随机数生成器。大多数哈希函数都是利用同余的方式来计算指纹，并且同余的随机数生成器也广泛用于计算机科学中的模拟和仿真。
- 在数学证明中，同余可以被用于构造等效的数学形式。例如，同余可以用于证明在一个单位圆中的所有平方数均为1模4同余的事实。
同余的计算
计算同余需要对模数的基本运算，例如加法、减法和乘法具有以下一个或多个性质：
- 闭合性：对于所有a、b∈Z，a+bmod n∈Z，a-bmod n∈Z，a×b mod n ∈Z。
- 归纳性：对于任何a∈Z，a+1 mod n=a mod n +1，a-1 mod n=a mod n-1。
- 可逆性：对于所有a∈Z，存在一个数-b∈Z，使得a+b mod n=0。
- 传递性：如果a mod n=b mod n，那么a±c mod n=b±c mod n，a×c mod n=b×c mod n。
基于这些性质，我们可以进行同余的计算。下面是一些例子：
同余计算1
用同余来计算3^100 mod 7。
因为3 mod 7 = 3，我们可以开始计算3^2 mod 7=2×3 mod 7=6。然后，我们可以继续计算3^4 mod 7 = 6² mod 7 = 1 mod 7。这随后就会导致我们得到3^8 mod 7 = 1² mod 7 = 1。因此，我们可以继续计算3^10 mod 7 = 3^8×3² mod 7 = 1×9 mod 7=2。最后，我们可以继续计算3^100 mod 7 = (3^10)^10 mod 7 = 2^10 mod 7 = 5。
同余计算2
我们可以使用同余来计算一个大数的立方和。例如：1^3+2^3+3^3+…+10^3 mod 7。
第一步是计算1³、2³、3³等的余数。这些余数是1、1、6、1、1、6、1、1、6和5. 然后，我们可以将它们相加得到22。 那么：1^3+2^3+3^3+…+10^3 mod 7 = 22 mod 7 = 1。
同余的验证
同余也可以用于验证其他的计算。例如假设我们要计算：
(a+b)² mod n = (a²+2ab+b²) mod n
我们可以证明这个等式是正确的，通过使用同余：
(a + b)² mod n
= (a + b)(a + b) mod n
= [(a mod n) + (b mod n)] [(a mod n) + (b mod n)] mod n
= (a mod n)(a mod n) mod n + (a mod n)(b mod n) mod n + (b mod n)(a mod n) mod n + (b mod n)(b mod n) mod n
= (a² mod n) + (2ab mod n) + (b² mod n) mod n
= (a² + 2ab + b²) mod n
这就证明了上述等式。
同余方程
同余方程是指形如**ax ≡ b (mod n)**这样的方程，其中a、b、n是整数，x是我们要求解的未知数。这种方程可以用来解决很多问题，例如计算模数的倒数、计算线性同余方程等问题。
在同余方程中，我们会把模数n称为模数，系数a称为系数，方程右侧的b值称为余数。
同余方程有很多种不同的类型和形式，例如简单同余方程、一次同余方程和多项式同余方程等
简单同余方程
简单同余方程是指形如x ≡ a (mod n)的方程，其中a和n都是整数，x是未知数。这种方程有一个很显然的解，即x = a + nk (k是整数)。我们可以通过这个公式来计算简单同余方程的所有解。
下面步骤性的介绍如何计算简单同余方程：
- 步骤1：找到任意一个x的解
我们可以通过代入k=0、1、2…等方式来找到任意一个x的解。例如，x=a (mod n)有一个显然的解，即x=a+0n=a。
- 步骤2：通过x的解计算所有解
我们可以通过公式x=a+nk(k∈Z)求出所有满足条件的解，将n代入整数集合Z中，得到所有的解。
例如，如果我们已经找到了一个解x=a，那么所有的解都可以表示成x=a+nk，其中k∈Z。另外，也可以表示成x≡a(mod n)，其中n是模数。
注：在实际应用中，我们通常只关注简单同余方程的最小非负整数解，即0⇐x<n之间的最小非负整数解。
现在我们用一个例子来说明如何计算简单同余方程。
计算x ≡ 4 (mod 7)的所有解。
- 找到一个解
我们可以代入k=0，求得一个解：x=4。
- 计算所有解
我们使用公式x=4+7k，其中k∈Z，得到所有的解。
x=4+7×0=4 x=4+7×1=11 x=4+7×2=18 x=4+7×3=25 …
这些方程的解可以表示成模数n下的等价类，即x≡4(mod 7)的解是0和7和14和21和…
一次同余方程
一次同余方程是指形如ax ≡ b (mod n)的方程，其中a、b、n都是整数，且a和n互质。这种方程的解可以用扩展欧几里得算法来求解。
解决一次同余方程
- 步骤1：确定a的逆元
由于a与n互质，所以一定存在a的乘法逆元a’，满足a×a’≡1(mod n)。我们可以利用扩展欧几里得算法来寻找a’。
- 步骤2：计算解x
将两边乘以a’，得到x≡ba’ (mod n)。我们可以利用扩展欧几里得算法计算a’和b的乘法逆元，然后将其代入到方程中计算出x。
- 步骤3：验证解x
将求出的解x代入原方程，验证是否是正确的解。
例子
现在我们用一个例子来说明如何解决一次同余方程。
计算2x ≡ 6 (mod 5)的解。
- 确定a的逆元
由于2与5互质，所以可以使用扩展欧几里得算法来求2的逆元，如下所示：
5 = 2 × 2 + 1
1 = 5 - 2 × 2
因此，2的逆元为-2（mod 5），即2×(-2)≡1(mod 5)。
- 计算解x
将两边乘以a’，得到x≡ba’ (mod n)，所以x≡6×(-2) (mod 5)，即x≡3 (mod 5)。
- 验证解x
将求得的解x=3代入原方程，验证等式是否成立：
2x ≡ 6 (mod 5)
2×3 ≡ 6 (mod 5)
6 ≡ 6 (mod 5)
因此，x=3是原方程的一个解。
总结
同余是数学中的一个基本概念，广泛应用于各个领域。同余的应用非常广泛，比如在密码学、计算机科学、数学证明等领域有着重要的作用。同时，在计算同余时我们还需要遵循基本的同余性质，以此进行正确的计算和验证。