整除和同余

整除

定义

b整除a，或a被b整除：$b|a$（如：9|36）
- b是a的因子，a是b的倍数．
- 是任意整数的倍数

性质

如果$b|a$且$a|b$，则$b=a$或$b=-a$．
整除性质1证明

(传递性) 如果$a|b$且$b|c$，则$a|c$．
(能够整除线性组合) 如果$c|a$且$c|b$，则$c|ua+vb$，其中u，v是整数．

整除性质3证明

（负号可转移）$a|b <=> -a|b <=> a|-b <=> -a|-b <=> |a| | |b|$
（大小比较）$b≠0且a|b =>|a|≤|b|$
(单向可乘整除) $c|b,c|a =>c|ab$

带余除法：

【定义】

对于a，b两个整数，其中$b\neq 0$，则存在唯一 $q，r$使得：$a = bq+r$，$0 ≤ r < |b|$．

r称为a被b除得到的余数．q称为不完全商. 显然当r = 0时，b|a．

【例子】a = –37， b= 5，则 –37 = (-8)* 5+3，q=-8, r = 3

【证明】

带余除法地证明

最大公因子

c|a且c|b，则c称为a，b的公因子

最大公因子，记为$c= (a，b)$．

最大公因子前提：c>0 + 2个不全为零的整数a，b

【例如】 36和24地最大公因子是12

性质

（负号公因子不变）(a,b)=(-a,b)=(a,-b)=(-a,-b)=(|a|, |b|)

证明
(a,b)=(-a,b) (a,b)|-a, (a,b)|b→(a,b)|(-a,b)
(-a,b)|-a|a, (-a,b)|b →(-a,b)|(a,b)

(0和任何数地最大公因子是本身正数)(0,a)=|a|

求解：辗转相除法

辗转相除法示例

定理：最大公因子定理

ab不全为0整数，uv为整数

$(a,b)= ua+vb．$

ab的公因子能表示为ab的组合。

最大公因子定理（实例）

【证明】
证明最大公因子定理

互素

【定义】ab不全为0，(a，b) = 1，则ab互素

【推论】
$a，b互素 <=>存在u，v，使ua+vb = 1$

证：
必要条件（$a，b互素 =>存在u，v，使ua+vb = 1$）是最大公因子定理$(a，b)= ua+vb．$的特例
证充分条件：如果存在u，v，使 ua+vb = 1．则由(a，b)|(ua+vb)，得(a，b)|1，所以(a，b) = 1．

【性质】

如果c|ab且(c，a) = 1，则c|b．
- 因为(c，a) = 1所以ua+vc = 1，同乘以b，uab+vcb = b．c| ab所以c| uab，c | c所以c| vcb，所以c|uab+vcb，替换uab+vcb = b，得证
如果a|c，b|c，且(a，b) = 1，则ab|c．
- 因为(a，b) = 1，存在u，v，使 ua+vb = 1，两端乘c得 uac+vbc = c．由 b|c，a|c，得ab|uac，ab|vbc，故ab|c
如果(a，c) = 1，(b，c) = 1，则(ab，c) =1．
- 因为(a，c) = 1，存在u，v，使 ua+vc = 1，因为(b，c) = 1，存在r，s，使 rb+sc = 1，于是 (ua+vc)( rb+sc) = 【(ur)】ab+【(usa+vrb+vsc)】c = 1．故(ab，c) = 1．

最小公倍数

$[a，b]$
ab均不为零,正公倍数

公倍数可以是负数

【性质】

$a|[a,b]$
负号$[a，b] = [–a，b] = [a，–b] = [–a，–b] =[|a|，|b|]．$
- 证明：(夹逼)$[a，b] = [–a，b] -a|[a, b], b|[a, b]→[-a, b]≤[a, b] a|[-a, b], b|[-a, b] →[a, b]≤[-a, b]$
$[a,b]|ab任意公倍数$
$[a,b]=\frac{|ab|}{(a,b)}$

素数

除±1和±p外无其他因子

若p不整除a，则(p,a)=1
如果p|ab，则p|a或p|b．
每个大于1的整数a都可以分解为有限个素数的乘积（可以重复）：
- 该分解除素数因子的排列是唯一的．
- $a=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$(2100=$2^2\times 3^1\times 5^2\times 7^1$)

Eratosthenes筛法
(筛选哪些是素数数)
设a是任意大于1的整数，则a的除1外最小正因子q是一素数，并且当a是一合数时，$q\leq a$

目标100以内素数

第一步：找$\leq \sqrt{100}=10$的全部素数：2、3、5、7

第二步：划去2、3、5、7的倍数

素数无穷个

同余

$a \equiv b \quad(mod\quad m)$

充分必要条件

整数a，b对模m同余的充分必要条件是： $m|(a-b)$，即a = b+mt，t是整数．

同余充分必要条件的证明

$a \equiv \ b (mod\ m)↔ m|(a-b) ↔ a = b+mt$

同余性质

自反性、对称性、传递性

如果$a_1 \equiv b_1 (mod\ m)，a_2\equiv b_2 (mod\ m)$，则
1）$a1+a2 \equiv b1+b2 (mod\ m$)，
利用充分必要条件：$m|( a1-b1)+(a2-b2) = (a1+a2)-(b1+b2)$，得证
2）$a1-a2 \equiv b1-b2 (mod\ m)$
3）$a1a2 \equiv b1b2 (mod\ m)$
4）如果$ac \equiv bc (mod\ m)$，且(c，m) = 1，则$a \equiv b(mod\ m)$，
得$m|ac-bc = c(a-b)$，因为$(c，m) = 1$，则$m|(a-b)$，
5）如果$a \equiv b(mod\ m)$，且d|m，d是正整数，则$a \equiv b (mod\ d)$．

同余推论

如果$a_1 \equiv b_1 (mod\ m)，a_2\equiv b_2 (mod\ m)$，则

$a1x+a2y \equiv b1x+b2y (mod\ m)$,xy是任意整数
$a1^n \equiv b1^n (mod\ m)$,n是任意整数
$f(a1) \equiv f(b1) (mod\ m)$,f是任一给定的整系数多项式（$f(x)=c_0+c_1x+\cdots +c_kx^k$）

同余应用

已知“$2^{16}=65536\equiv 154(mod\ 641)$”,求$2^{64} (mod 641)$

模重复平方计算法:
$2^{32}=2^{16\times 2}\equiv 154^2(即2^{16}的余的平方)=23716\equiv 640 \equiv -1(mod \641)$
$2^{64}=2^{32\times 2}\equiv (-1)^2(即2^{32}的余的平方)\equiv 1(mod \ 641)$

2004年9月8 日星期三，问22005天后是星期几？问题可以转化为$2^{2005}$模7余几的问题。$2^{2005}=2^{3\times 668+1}=(2^3)^{668}\times 2\equiv 1\times 2(mod\ 7)$.1是$2^3 mod\ 7 =1$。所以余2，为周五。

剩余系

剩余类和剩余系

模m同余的全体整数集合是一个模m剩余类
- 剩余类中的每个数都称为该类的代表
- $a=qm+r$ r称为该类的最小非负剩余，该类剩余类可以记为$[r]$
- 模m剩余类共有m个

在数轴上，一个剩余类做任意整数间隔的平移仍然是一个剩余类/另一个剩余类/它自己

从模m剩余类中各取一个代表，代表的集合为模m的一个完全剩余系．
- {0，1，2，…，m-1}称为模m的最小非负完全剩余系
- 模m的绝对值最小完全剩余系．
  - 当m是偶数时，为$\{\frac{-m}{2},\frac{-m}{2}+1，…，-1，0，1，…，\frac{m}{2}-1 \}$或$\{\frac{-m}{2}+1，…，-1，0，1，…，\frac{m}{2}-1, \frac{m}{2} \}$
  - 当m是奇数时， $\{-\frac{m-1}{2}，…，-1，0，1，…，\frac{m-1}{2} \}$
    
    举例：
    模32的最小非负完全剩余系： $\{0，1，2，…，31\}$．
    模32的绝对值最小完全剩余系： $\{-16，-15，…，-1，0，1，…，14，15\}$ 或 $\{-15，-14，…，-1，0，1，…，15，16\}$．
    模31的绝对值最小完全剩余系：$\{-15，-14，…，-1，0，1，…，14，15\}．$

一个完全剩余系在数轴上的任意整数间隔的平移都是一个完全剩余系。

剩余系的性质

a是一个整数且(a，m) =1，b是任意整数，如果$\{x_0，x_1，…，x_{m-1}\}$ 是模m的一个完全剩余系，则$\{ax_0+b，ax_1+b，…，ax_{m-1}+b \}$ 也是模m的完全剩余系．
- 这种说法常常用遍历来说，即“如果x遍历模m的一个完全剩余系，则ax+b也遍历模m的完全剩余系”
如果x1，x2分别遍历模m1和模m2的完全剩余系，且(m1，m2) = 1，则$m_2x_1+ m_1x_2$遍历模m1m2的完全剩余系．

简化剩余系

如果一个模m的剩余类里面的数与m互素，则称它为与模m互素的剩余类．
从与模m互素的每个剩余类中各取一个数构成的集合称为模m的一个简化剩余系．

例如：模16的2个简化剩余系为：
{1，3，5，7，9，11，13，15}
{17，19，21，23，25，27，29，31}

设a是一个整数且(a，m) =1．如果x遍历模m的一个简化剩余系，则ax也遍历模m的简化剩余系．
如果x1，x2分别遍历模m1和模m2的简化剩余系，且(m1，m2) = 1，则m2x1+ m1x2 遍历模m1m2的简化剩余系．
如果m1，m2是两个互素的整数，则$\phi( m1m2) = \phi( m1)\phi( m2)．$
- $\phi(X)$是模X的一个简化剩余系的元素个数，也称欧拉函数
- 若X为素数，那么$\phi(X)=X-1$
若$m=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$,则$\phi(m)=m\Pi_{i=1}^k(1-\frac{1}{p_i})$(p是素数)

乘法逆元

r,m是互素的正整数，存在正整数s使得$rs\equiv 1(mod \ m)$,s为乘法逆元。

【如何求】用前面的最大公因子定理
乘法逆元求解例题

注意，如果最后求出来是负数，需要+m转为正数

如果r，m互素，则r在模m下必存在逆元s

几个定理

欧拉定理：r,m是互素的正整数,$r^{\phi(m)}\equiv 1(mod \ m)$
费马小定理：$a^p\equiv a(mod \ p)$

群

认识群

群的定义

G是非空集合，代数运算ab （不一定专指乘法） 满足以下性质
1）G对于乘法是封闭，即对于G中任意元素a，b，有$ab\in G$；
2）【类比结合律】对于G中任意元素a，b，c，有(ab)c = a(bc) ；
3）【类比1】在G中有一个元素e，对于G中任意元素a，有 ea = a；
4）【类比倒数】对于G中任一元素a都存在G中的一个元素b，使 ba = e．

群的定义可以简单的归结为带有运算的集合，在集合上的运算满足 1）封闭性； 2）结合性； 3）左单位元； 4）左逆元

典型的群

整数加法群、有理数加法群

自然数，不存在单位元和逆元，因此自然数加法群（$1\times 0=0$，所有1不是单位元）

集合$\{0，1\}$对于模2加法“$\oplus$”（或称异或）是一个群
- 单位元为0，逆元是其本身

集合元素可以是任意事物，其中的运算也可以是任意定义的．

群的性质

左逆元同时也是右逆元
- 对于$a，b\in G$，如果$ba = e$，则$ab = e$．
左单位元同时也是右单位元
单位元是唯一的．逆元是唯一的．
如果群中的运算满足交换律，则这个群称为交换群或阿贝尔（Abel）群.
群的乘法满足消去律（包括左消去和右消去）

群的阶、元素和幂次方

群的阶

即元素个数，记为$|G|$
无限个即为无限群

群的幂次方

因为满足结合率，所以连乘有意义。

n个连乘$a^n$
n个逆元连乘$a^{-n}$
${(a^{-1})}^{-1}=a$

$a^{-n}\times a^{n}=e$
$a^ma^n=a^{m+n}$
$(a^n)^m=a^{nm}$

群的等价性

如果G一个非空集合，则它是一个群的充分必要条件是：
（1） G中的运算封闭且满足结合律 （2）$\forall a,b\in G$，方程 ax = b，ya = b 有解．

如果G一个非空有限集合，则它是一个群的充分必要条件：
（1） G中的运算封闭且满足结合律（2）满足消去律

子群

子群定义

一个群G的一个子集H如果对于G的乘法 （不专指乘法，而是同一类代数运算） 构成一个群，则称H为G的子群，记作$H≤G$．

一个群G至少有两个子群：G本身；只包含单位元的子集{e}
它们称为G的平凡子群，其他子群成为真子群(H＜G)．

举例：整数加群的子群可以是元素m的倍数

子群性质

G的单位元和H的单位元是同一的；
如果$a\in H$，$a^{-1}$是a在G中的逆元，则$a^{-1}\in H$．

子群判定

下列的$ab$都是代表一个运算，而不是乘法！
三个判定定理任意使用一个

一个群G的一个非空子集H构成一个子群的充分必要条件是： 1) $\forall a,b\in H$，有$ab\in H$； 2) $\forall a\in H$，有$a^{-1}\in H$．

一个群G的一个非空子集H构成一个子群的充分必要条件是：$\forall a,b\in H$，有$ab^{-1} \in H$；【最常用】
一个群G的一个非空有限子集H构成一个子群的充要条件是：$\forall a,b\in H$，有$ab \in H$；

一个群的一个非空有限子集是一个群的充要条件是：只要它满足封闭性．

判定例题

例判断mZ是Z的加法子群． (运用定理2)
证明：设$\forall a，b\in mZ$，则有$t_1，t_2\in Z$，使 $a = mt_1，b = mt_2$．
b在Z中的加法逆元是$-b$，于是$a+(-b) = mt_1+(-mt2) = m(t1-t2)$
由于$t_3 = (t_1-t_2)\in Z$，所以$a+(-b) = mt_3\in mZ$则mZ是子群