第二章同余

我感觉我已经快学到去世了，呜呜呜

同余的定义

如果a - b 被 m 整除，或 m｜a - b，就记作 $a \equiv b(mod\ n)$ 叫做a，b摸n同余。

a，b模n同余的意思翻译过来其实就是a-b可以被n整除；

同余的判断

如何判断两个数是否同余呢？`》判断是否存在一个整数q使得：
$a = b + q \cdot m$
其一点从定义中就很容易的可以推出来；

模同余的等价关系（自反性，对称性，传递性）可以用来快速的判断a和b是否模m同余；

（1）对于任意整数a 都有 $a \equiv a(mod\ m)$

（2）若 $a \equiv b(mod \ n)$ ；这个做题有时候还是会遇到的，需要注意一下；

（3）若 $a \equiv b(mod \ m)$

由最小非负余数来判断同余

a，b模m同余的充分必要条件是a，b被m除的余数相同；其实我感觉这条性质是最接近同余这个名字的了，同余同余，两个数的余数相同不就叫做同余吗？
通过整数a，b模m的加法运算和乘法运算的性质来判断a，b模m是否同余

如果 $a_1 \equiv b_1(mod \ m)$ 则：

（1） $a_1+a_2 \equiv b_1 + b_2(mod \ m)$

（2） $a_1 \cdot a_2 \equiv b_1 \cdot b_2(mod \ m)$

如何便捷的判断n是否可以被3或者9整除？（可以用于判断大数时候可以被3和9整除）

假设 m 是 n 各位数字的合，则：

（i）3｜n的充分必要条件是`》3 ｜ m

（ii）9｜n的充分必要条件是=〉 9｜m

如何便捷的判断大数能否被11、13、7整除？

7可以整除n的充分必要条件就是7可以整除整数:

$(a_0+a_2+ \cdot \cdot \cdot)-(a_1 + a_3 + \cdot \cdot \cdot)$

$a_0 - a_n$ 就是数字n各位上的数字；

同余的性质

设m是一个正整数，设 $d \cdot a \equiv d \cdot b(mod \ m)$ . 如果(d,m) = 1即d和m互素，则

$a \equiv b(mod \ m)$

这一点类似于同余的消去律？

还有一条类似的性质：设 $a \equiv b(mod \ m)$ ,则

$\frac{a}{d} \equiv \frac{b}{d}(mod \ \frac{m}{d})$

如果a，b关于 $m_i$ （i从1到k）同余，那么a，b关于这一堆数的最大公倍数n同余；
设 $a \equiv b(mod \ p \cdot q)$ ,则：

$(a,m)=(b,m)$

如果 $a \equiv b (mod \ c)$ ，则：

$a \equiv b(mod \ [c,d])$

剩余类和完全剩余系

剩余类和剩余

由于同余是一种等价关系，对于整数m，可以把所有的整数分成m类，每一类对于m都同余；每一类都叫做m的一个剩余类；一般用 $C_a$ 是非空集合；

可以发现剩余类其实就是等价关系中的一个等价类；又扯到离散上去了，裂开；

设m是一个正整数，则

任何一个整数包含在一个 $C_r$
$C_a = C_b$
$C_a与C_b$

一个剩余类中的任一个数都叫做该类的剩余，或者代表元

完全剩余系

对于一个数m，现在有m个数，每一个都来自于不同的剩余类，那么这m个数就叫做模m的一个剩余系；记作 $Z/mZ$

m个整数构成一个完全剩余系的条件：其实在定义中也就可以发现了，m个整数 $r_0,r_1,r_2, \cdot \cdot \cdot ,r_{m-1}$ 为模m的一个完成剩余系的充分必要条件是他们模m两两不同余；
设m是正整数，a是满足（a，m）=1的整数，b是任意整数，若k遍历模m的一个完全剩余系，则： $a \cdot k+ b$ 也遍历模m的一个完全剩余系；
完全剩余系的加法原则？

如果 $k_1,k_2$ 的完全剩余系. 这条规则还可以拓展到多个模的情况；

简化剩余类与欧拉函数

欧拉函数

一个正整数m，1到m-1中与m互素的整数的个数记作 $\phi(x)$ ,通常叫做欧拉函数；

一个素数p， $\phi(p)=p-1$
对于素数幂 $m=p^{\alpha}$

简化剩余类

如果剩余类中存在一个剩余与m互素，那么这个剩余类就叫做简化剩余类，简化剩余类中的剩余叫做简化剩余；

简化剩余类的这个定义与剩余的选取无关；
两个简化剩余的乘积仍然是简化剩余；
类比剩余系的概念，我们可以理解简化剩余系， $|(Z/mZ)^*|=\phi(m)$
设m是一个整数数，若 $r_1,r_2, \cdot \cdot \cdot r_{\phi(m)}$ 是模m的一个简化剩余系。
对于正整数m，若整数a满足(a,m)=1,如果k遍历模m的一个简化剩余系则 $a \cdot k$ 也遍历模m的一个简化剩余系。
对于正整数m，a是满足(a,m)=1的整数，则存在唯一的整数a‘，1 <= a’ < m 使得：

$a \cdot a' \equiv 1(mod \ m)$

a’就叫做模m的逆元；

两个模的简化剩余系：

设m1，m2是互素的两个正整数，如果k1，k2分别遍历模m1和模m2的简化剩余系，则：
$m_2 \cdot k_1 + m_1 \cdot k_2 $遍历模$ m_1 \cdot m_2$的简化剩余系.

欧拉函数的性质

如何快速的求出欧拉函数值？

设m，n是互素的两个正整数，则

$\phi(m \cdot n)=\phi(m) \cdot \phi(n)$

而且这个公式可以无限套娃，也就是说 $\phi(m)和\phi(n)$ 还可以继续往下分；

幂次方的乘积应该如何求它的欧拉函数呢？

$m =p_1^{\alpha_1} \cdot \cdot \cdot p_2^{\alpha_s }$

则：

$\phi(x) = m(1-\frac{1}{p_1}) \cdot \cdot \cdot (1-\frac{1}{p_k})$

设p，q是不同的素数，则

$\phi(p \cdot q) = p \cdot q - p -q +1$

欧拉定理、费马小定理和Wilson定理

欧拉定理

设m数大于1的整数，如果是a满足（a，m）= 1的整数，则

$a^{\phi(m)} \equiv 1(mod \ m)$

费马小定理

研究模m=p为素数时候，整数 $a^k(mod \ p)$ 的性质.

设p是一个素数，则对任意整数a，有

$a^p \equiv a(mod \ p)$

应用：当p为素数的时候，费马小定理可以快速的求出a (mod p)

Wilson定理

设p是一个素数，则
$(p-1)! \equiv -1(mod \ p)$

看到数字连乘的时候可以考虑使用Wilson定理

模重复平方法

用于求大数平方的模

"""
模重复平方法
"""

# 求解一个数的n次方的模
# 比如12996的227次方模37909同余的结果
a = 1
num = 12996
n = 227
c = 37909
while n:
    if n % 2 == 1:
        a = a * num % c
    num = (num ** 2) % c
    n //= 2
print(a)

重要知识点：

判断两个数是否同余？

根据定理：m｜(a-b) ,则 $a \equiv (mod \ m)$
$a \equiv b(mod \ m)$
a,b对于m除的余数相同；

判断一个数n能否被3，7，9，11，13整除 => P57

（1）对于3和9

将n转化为10进制的科学记数法， $n=a_k \cdot 10^k + ... + a_0$

（i）3｜n的充分必要条件是`》3 ｜ $a_i$

（ii）9｜n的充分必要条件是=〉 9｜ $a_i$

（2）如何便捷的判断大数能否被11、13、7整除？

7可以整除n的充分必要条件就是7可以整除整数:
$(a_0+a_2+ \cdot \cdot \cdot)-(a_1 + a_3 + \cdot \cdot \cdot)$
$a_0 - a_n$ 就是数字n各位上的数字；

如何求模m的完全剩余系？ ==> P64

（1）直接取得0，…，m-1即是一个完全剩余系
（2）对于从0到m-1的这个完全剩余系，可以对于某部分数再加上m的倍数;
（3）如果已知一个完全剩余系 $k_i$ 也是一个完全剩余系
（4）如果 $m_1 \cdot m_2 = m$ 则遍历模m的完全剩余系；

如何求一个数的欧拉函数？ ==> P70

(1)设m，n是互素的两个正整数，则

$\phi(m \cdot n)=\phi(m) \cdot \phi(n)$

而且这个公式可以无限套娃，也就是说 $\phi(m)和\phi(n)$ 还可以继续往下分；

(2)对于任意的整数m：

$\phi(m)=m \cdot (1-\frac{1}{p_1})(1-\frac{1}{p_2}) \cdot \cdot \cdot$

p的来源是标准分解式 ==> P70

如何求模m的简化剩余系 ==> P70

(1) 按照定义来，在最小非负完全剩余系中暴力判断每一个代表元是否与m互素，是的话保存；最后剩的就是一个最为简单的简化剩余系

(2) 同求完全剩余的第（3），如若已知 $k_i$ 也遍历模m的一个简化剩余系

(3) 同求完全剩余的第（4），如果 $m_1 \cdot m_2 = m$ 则遍历模m的简化剩余系；

(4) 如若a是模m的原根，则m的简化剩余系就是 $a^0,a^1,...,a^{\phi(m)-1}$ P169

如何快速计算 $b^n$ P80

采用模重复平凡计算法（也叫快速幂 ACM经典算法）：
对于 $b^n$ 次，时间复杂度大大减少；

C实现：

int fastpow(int base,int n,int mod){
	int ans=1;
	while(n){
		if(n&1) ans*=base%mod;
		base*=base;
		n>>=1;
	}
	return ans%mod;
}

如何求解一个数的逆元？

枚举法：对于比较小的数可以通过肉眼 “看” 的方式直接口算出他的逆元
费马小定理：如果m为素数则逆元可以表达为： $a^{m-2} \ mod \ m$
拓展欧几里得算法：

x是a的逆元可以表示为： $ax=1(mod \ n)$ ；

然后可以得到： $ax-ny = 1$ ;

之后运用拓展欧几里得算法求得： $ax+ny=1$ 的解即可

注意逆元存在的条件为（a，n）= 1