《初等数论》期末复习
Readme
总体考的还行吧，和样题题型完全一样。四道计算题，其他的证明题一道样题的原题，一道样题修改版本，剩下的没什么印象了）
可惜的是样题我看的还是没有那么认真，第一题样题原题就卡了呜呜呜，希望后来看到这篇笔记的同学吸取我的教训
期末考试内容
初等数论（第四版）潘承洞、潘承彪著，第一章、第二章（除2.2节）、第三章、第四章（除第9节）、第五章（除第3节、第4节）
复习提示
请同学们重点复习课堂上的例题、作业题、第一章到第四章第四节重要定理的证明
第一章 整除理论
自然数与整数
Peana公理：
- 一个集合N，其中任意一个元素n，都有唯一的后继n+（换句话说，每个除e以外的元素都是一个元素的后继）
- 集合N中存在一个不是任何元素后继的元素e
- 由a+ = b+可以推出a = b
- 归纳原理：S是N的一个子集，如果n属于S，则必有n+属于S，则S=N
性质：
- 对集合N中任意元素n，n≠n+
- 证明：将满足的元素构造一个含于N的子集，找到一个特例使子集不为空(通常是e)，然后再一般证明(如n属于子集S，则满足条件的n+也属于S)
最小自然数原理：
整除的基本性质
性质3常用于证明
利用条件证明某个数整除某个数，常常把被整除的数写成表达式(利用条件里的常数1构造)
素数
注意符号：斜杠与竖线的区别，斜杠(/)是除法，竖线(|)是整除
- 每个合数都会被一个素数整除（筛法：p|a, p<=\sqrt a）
- 每个≥2的整数都能表示为素数的乘积
公因子
最大公因子：d = (a, b)或d = gcd(a, b)
求最大公因子的基本方法：两者相加/相减，从而将大数变小
素数和其他数的最大公因子一般是1，如果素数整除其他数，则最大公因子为素数本身
两个数互素：它们的最大公因子为1
任意两个不同的费马数互素：主要证明(F_m, F_n) | 2
上面这个定理前半部分的证明是构造(a1/m, …, a_k/m)的公因数，然后分别证明大于和小于
m(b_1, b_2, …, b_i) = (mb_1, mb_2, …mb_i)
公倍数
最小公倍数：b = [a1, a2]
公因子可以移进去，公倍数可以移出来也可以移进去：[ma_1, ma_2, …, ma_k] = m[a_1, a_2, …, a_k]
m(a_1, a_2, …, a_k) = (ma_1, ma_2, …, ma_k)
两个数的公因数与公倍数相乘结果为两个数乘积的绝对值（一种求最小公倍数的方法）
带余除法
？
整数分类（模）:
j mod a：整数除a后余j
？
进制
进制每一位上的数其实是带余除法式子中的r，且r是”倒过来的”：
应用
特殊的整数或者特殊的整数列被一个固定的正整数 a 除法后所得的最小非负余数具有特殊的性质
求最大公因子方法
基本方法
求最大公因子的基本方法：两者相加/相减，从而将大数变小
更相减损术
欧几里得算法——辗转相除法
a = qb+r：
(a, b) = (b, r)将求a b最大公因子转换为求b r最大公因子
若r=0，则(a, b) = b
具体算法：
a = q_0 b + r_0
b = q_1 r_0 + r_1
直到r_i = 0
则(a, b) = r_k
存在x_0, x_1使(a, b) = ax_0 + bx_1 （依次往前倒推）
第二个定理有一个推论！
整数的素分解
算术基本定理：一个正整数可以唯一分解为素数的乘积
由两个数的素分解得到它们的最大公因子和最小公倍数（常用来证明同时出现公因数和公倍数的式子的相等）：
多个数取素分解它们用的素数是一样的！如上述的a和b，都是p_1到p_s
除数函数：
n! 素因子分解表达式
整数部分小数部分
整数部分：[x]，[x]<=x<[x]+1
小数部分：{x} = x - [x]，0<={x}<1
b = qa+r，则q=[b/a]
取整函数中的整数可以提出来：任意整数m，[x+m] = [x] + m，{x+m} = {x}
[x]+[y]<=[x+y]<=[x]+[y]+1，等号仅有一个成立
n! 素因子分解
例题？
所以求n!的素因子分解，取<=n-1以内的素数p，逐个计算$$\alpha(p, n)$$，$$\alpha(p, n)$$为p的指数
第二章 不定方程
一次不定方程
k元一次不定方程有解条件
不定方程(1)有解的充要条件：(a1, a2, …, a_k) | c
二元一次不定方程求解算法
法一：找特解（一般系数比较明显）
具体算法：
- 看是否有解：验证(a_1, a_2) | c是否成立
- 若上式成立，找出特解，再利用方程得到通解
法二：辗转相除法思想（一般系数较大，不容易找到特解时）
利用等式，令分数的分母始终的较小的系数，这样不断降低变量的系数
直到某个变量的系数为±1，此时将式子中的另一个变量作为t，反推回去
一元多次不定方程的也可以这样求解
多元一次不定方程求解
将前两个变量与系数进行换元
定理：
具体过程：
二元一次不定方程的非负解和正解
结论：
不定方程x^2+y^2=z^2及其应用
$$x^2+y^2=z^2$$
满足xyz=0的为显然解
满足xyz≠0的为非显然解
本原解：x, y, z>0，(x, y, z) = 1
方程所有的本原解满足：
- x y z两两互质：(x, y) = (y, z) = (x, z) = 1
- x y必为一奇一偶：2 不整除 x+y（x+y为奇数，z为奇数）
$$x = r^2-s^2, y=2rs, z=r^2+s^2$$
求上述不定方程的解时别忘了显然解！（x或y等于0）
第三章 同余
同余的定义及基本性质
两个多项式的同余：多项式的每个系数都同余
两个数的乘法模m余1，则两个数互逆：
用来求一个模数所有可逆元的逆元，取模数的一个既约剩余系，然后计算
这个性质可以用来进行模的分解，如m=m1 x m2，(m1, m2) = 1，则由$$a = b mod m_1, a=b mod m_2 \rightarrow a = b mod m_1m_2$$
如可以用来求一个数模100的余数，找到一个模4和模25都余1的数
剩余类与剩余系
判定问题
如何判断给定的一组数是否构成一个完全剩余系、既约剩余系?
构造问题
如何构造一个完全剩余系、既约剩余系?（前提是已经有了一个完全/既约剩余系）
法一
法二
用小的剩余系构造大的剩余系
一般情况：
也可以乘个系数：
$$a_1M_1 =1 mod m_1, a_2M_2 = 1 mod m_2, …$$
法三
当m1和m2不满足互素关系时（不加限制），怎么构造：
同样可以乘个系数：
但是若m1和m有相同的素因子，则当x^(1)遍历模m_1的完全/既约剩余系，其他的x^(i)遍历模m_i的完全剩余系，则x遍历模m的完全/既约剩余系
Euler定理
欧拉函数性质：
n的所有因子的欧拉函数的和等于n
与欧拉函数有关的证明一般用整数的素分解来写
模 m 的既约剩余系可以取种种不同的形式*,* 但是每个既约剩余系中所有数的乘积模 m 是不变的
欧拉定理：
可以用欧拉定理计算a对模m的逆$$a^{-1}$$
费马小定理
Wilson定理
其他模数时不变量：
小结
第四章 同余方程
同余方程的概念
同余方程：$$f(x)=0(modm)$$
同余方程的解整数c：$$f(c)=0(mod m)$$，则c的同余类c mod m都是这个同余方程的一个解
求一个同余方程的解，可以取模m的绝对最小完全剩余系：
由费马小定理：对于素数n，$$x^n-x = 0(mod n)$$，且这个同余方程的解数为n
将一个同余方程中系数为模的倍数的项去掉后，同余方程的解不变（利用下面这个等价变形来简化方程式）：
等价变形2：等价两边同时加上整系数多项式s(x)
等价变形3：(a, m) = 1，则 af(x) = 0 mod m
等价变形4可以降低同余方程次数，常用上述费马小定理$$x^n-x = 0(mod n)$$找到恒等同余式h(x)
（一般f(x)次数大于模m的话，先用h(x)乘上a_0x^?消掉f(x)的最大次数项，再慢慢消，直到得到的r(x)的次数小于m停止）
快速判断同余方程有无解：取模m的一个小因子代替模m，看这个新的同余方程有没有解
一元一次同余方程
解模数较大的同余方程：换模，将模数换小，解出最底层的解后再逐步往上迭代
一元一次同余方程组——孙子定理
同余方程组定义
只需在模m的完全剩余系中找同余方程组的解即可，解数至多m个
如同余方程组 (38) 中某个方程无解，则整个同余方程组无解.
孙子定理
如果模数两两互素，则同余方程组一定有解：
求M_j的逆元可以用枚举法，枚举到m_j-1
孙子定理就是给出了解的一个形式与计算方法
一元同余方程的一般解法
讨论高次同余方程的解法
提供了另一个求解同余方程 f (x) ≡ 0(modm) 的方法
\1. 找到较小的 d|m，求解 f (x) ≡ 0(modd), 得到解 x ≡ c1*, · · · , cs* (modd)
\2. 解 f (ci + dy) ≡ 0(modm) (1 ≤ i ≤ s)
一个trick：一个解满足两个同余方程，求这个解实际上是求这两个同余方程的解
上述定理3的证明相当于求61和62这个同余方程组的解，将解带入61，经过多项式化简后得63
定理3的公式要背！！！应用熟练！！！
一般的求解方式：
$$f(x)=0 mod m \ 对m进行素因数分解 \ \rightarrow f(x)=0 mod p_j^{a_j} \ 从而转为求f(x)=0 mod p$$
模为素数的二次剩余
定义
模p为素数，p不整除d。式子有解，则d为模p的二次剩余；反之，d为模p的二次非剩余
求给定常数的模p的二次剩余
由下面这个定理及证明，取0-p-1/2，平方，模p后所得到的数即为d
快速判断d是否为模p的二次剩余：欧拉判定法
推论4：两个模p的二次剩余相乘仍然是模p的二次剩余，两个模p的二次非剩余相乘是模p的二次剩余，其他情况相乘都是模p的二次非剩余（类似正正得正，负负得正）
Gauss二次互反律
引入勒让德符号：
计算勒让德符号方法：
Jacobi符号
定义
相比勒让德符号，Jacobi符号的分母可以分解为素数的乘积。所以当N为奇素数时，二者相等
性质
与勒让德符号区别
模为素数的一元高次同余方程
一些定理
不知道这节可以怎么出题，感觉都是一些不熟悉的定理推论…
两个整系数多项式等价：$$任意x, f_1(x)=f_2(x) (mod p)$$
两个整系数多项式同余：每个系数都模p同余
定理1和定理2其实是等价的
定理5可以用来判断同余方程多项式f(x)的解数是否等于它的次数
定理6(1)用来判断同余方程多项式f(x)的解数是否等于模数
模p的n次剩余
将二次剩余的2换成了n
利用定理8(1)可以减小次数
第五章 指数与原根
指数
概念
指数和原根针对的对象不一样，指数指$$a^d$$的指数，而原根指$$a^d$$的底数
性质
性质1：b和a模m同余，(a, m) = 1，则b对模m的指数$$\delta_m(b)$$等于a对模m的指数$$\delta_m(a)$$
由性质2可知，如果想证明模m的指数整除某个数d，则只需要证明a^d = 1(mod m)，如性质3的第二条
证明两个数模m同余，只需证明两个数的差被m整除即可
性质5给出了一种取既约剩余系的方法
可以利用性质11，找到最大的指数$$\delta_m(c)$$，如果其等于m的欧拉函数，则c为模m的原根
原根及其性质
定理3的例子和定理4 5的例子要再看一下
作业题
- 反证法与第二归纳法
- 证明最大公约数的大小利用“最大”定义，以及整除关系
- 如果一些数互素，且它们均独自整除m，则它们的乘积整除m
- 多考虑模与同余的思想（相邻的几个数常用模x余-1来构造）
- 证明无限个除了反证还可以尝试构造
- 解不定方程组之前先判断一下是否有解
- $$x^2+y^2=z^2$$的全部解=本原解+显然解，所以求全部解时别忘了显然解！
- 求本原解一般是根据条件枚举r和s的值，求全部解在这个基础上加上k的枚举值
- 解一元一次同余方程时常使用换模的做法（但也可以拆分为同余方程组来解）
- 证明同余方程是否有解可以用Jacobi符号，两边：(系数/模)若相等，则有解
