2021-03-29-数论笔记
参考的基本资料为《数论讲义》上下册+《初等数论》，最后群环域的部分打算看《代数》(《Algebra》by Michael Artin).
《数论讲义》上册笔记
第一章 整数的唯一分解定理
1 整除性
定理1：设a,b是两个整数，其中b>0，则存在两个唯一的整数q和r，使得$a=bq+r，0<= r<b$，我们一般称q为不完全商，r为a除b得到的余数，也叫作非负最小剩余，常记做$_b=r$，不过b常常省略掉。
2 最大公因数和辗转相除法
定理1：设a,b,c是三个整数，其中b>0，则存在两个唯一的整数q和r，使得$a=bq+c$，q为整数，则$(a,b) = (b,c)$
3 整数的唯一分解定理
先定义复数的定义，然后给出其他定理。
引理1：设a是任一大于1的整数，则a的除1之外的最小正因数q是素数，而且$q<=\sqrt{a}$
| 引理2：设p是一个素数，a是任一整数，择有$p | a$或$(p,a)=1$ |
| 引理3：设p是素数，则$p | ab$，则$p | a$或$p | b$ |
定理1：任一大于1的整数能表示为素数的乘积，即对于任一整数a>1，有$a=p_1p_2…p_n, p_1<= p_2 <= … <= p_n$。其中p_1p_2…p_n都是素数，并且若$a=q_1q_2…q_m, q_1<= q_2 <= … <= q_m$必然有$m=n,q_i==p_i,(i=1,2,…n)$
证明：定理1的证明是非常明显的使用数学归纳法的证明方式，将数字a拆成b*c，然后b和c都满足归纳。证明m=n只需要利用引理3，且素数互质即可。
实际上之所以辗转相除方法是个优秀的方法，是因为效率高。将数字展开为唯一分解式是一种很麻烦再计算gcd很麻烦。
此外还有一个要注意的地方是，如果素数定义变了那么唯一分解定理不再适用。
5 素数
厄拉多塞筛法，利用第一章第三节的引理1，厄拉多塞筛法列出从2到$\sqrt{n}$的素数，然后划去从$p_1$到$p_{\sqrt{n}}$所有素数的倍数，剩下的就都是素数了。近代素数表都是由此得出的。
定理1：素数的个数是无穷的
定理2：存在无穷多个形如4n-1的素数
证明：假设4n-1的素数是有限的，p是最大的。那么设$N=435…*p -1$，N必然是合数，且所有的素数因子都大于p。首先N必然是奇数，其因子要么是4N+1/4N-1的形式(这两个数字都是奇数的表示法，换言之奇数要么是4N+1要么是4N-1），而两个4N+1乘法是得不到4N-1的，因此必然有个4N-1的因子是素数
定理3：存在无穷多个形如kn+l的素数，其中(k,n)=1
这个证明很麻烦，先略过。
结尾
唉，尴尬
