数论基础
整除性与约数
整除的定义：设 \(a,b\in\mathbf{Z}，a\ne 0\)。如果$ \exists q\in\mathbf{Z}\(，使得 \(b=aq\)，那么就说\) b\(可被\)a$ 整除，记作\(a\mid b\)，\(b\)不被\(a\)整除记作\(a\nmid b\)
如果\(d\mid a\)，且\(d\ge0\)，则\(d\)是\(a\)的约数。任何正整数\(a\)均可被平凡约数\(1\)和其自身\(a\)所整除，整数\(a\)的非平凡约束称为\(a\)的因子。\(eg：20\)的因子为2、4、5、10$
素数与合数
如果一个整数\(a>0\)且只能被平凡约数和其自身所整除，，则这个数是素数。一个整数\(a>1\)且不是素数，那么它就是合数。称整数为基本单位，并且它既不是素数也不是合数。
除法定理、余数和等模
除法定理：对于任意整数\(a\)和任意正整数\(n\)，存在唯一整数\(q\)和\(r\)，满足\(0\le r<n\)且\(a=qn+r\)。 称\(q=\left \lfloor a/n \right \rfloor\)为除法的商，值\(r=a\space mod \space b\)为除法的余数。 我们根据整数模\(n\)的余数，我们可以将所有整数划分成\(n\)个等价类。包含整数\(a\)模\(n\)等价类为
例如，\([3]_7=\{\dots ,-11,-4,3,10,17,\dots\}\)，这个集合同时可以表示为\([-4]_7\)和\([10]_7\),\(a \in [b]_n\)和\(a\equiv b(mod\space n)\)，是等价的。所有这类等价类的集合是：
公约数和最大公约数
如果\(d\)是\(a\)的约数并且也是\(b\)的约数，则\(d\)是\(a、b\)的公约数。 公约数的一条重要性质是：
更一般的对任意整数\(x\)和\(y\)，有：
并且如果\(a\mid b\)，那么\(\left | a \right |\le \left | b \right |\)，或者\(b=0\),而这说明：
公约数中最大的称为最大公约数，记作\(gcd(a,b)\).定义\(gcd(0,0)=0\)，那么\(gcd\)函数有以下性质： - \(gcd(a,b)=gcd(b,a)\) - \(gcd(a,b)=gcd(-a,b)\) - \(gcd(a,b)=gcd(|a|,|b|)\) - \(gcd(a,0)=|a|\) - \(gcd(a,ka)=|a|\)
定理1
如果任意整数\(a\)和\(b\)步都为\(0\)，则\(gcd(a,b)\)是\(a\)与\(b\)的线性组合集\(\{ax+by：x,y\in Z\}\)中的最小正元素。
定理2
对任意整数\(a\)和\(b\)，如果\(d\mid a且d\mid b，则d\mid gcd(a,b)\)
定理3
对所有整数\(a\)和\(b\)以及任意非负整数\(n\)，有
互质数
如果两个整数\(a\)和\(b\)只有公约数\(1\)，即\(gcd(a,b)=1\)，则\(a、b\)称为互质数.
定理4
对任意整数 \(a、b\) 和\(p\)，如果\(gcd(a,p)=1\)且\(gcd(b,p)=1\)，则\(gcd(ab,p)=1\)
由此可得，对于任意整数\(n_1,n_2,n_3\dots n_k\) ，如果对任意\(i\ne j\)，都有\(gcd(n_i,n_j)=1\)，则称整数 \(n_1,n_2,n_3\dots n_k\)两两互质。
唯一因子分解定理
合数 \(a\) 仅能以一种方式写成如下乘积形式：
其中 \(P_i\) 为素数，\(P_1<P_2<P_3\cdots <P_r\)，且 \(e_i\) 为正整数。
模运算
定义：设 \(a,b\in Z\) 且 \(b>0\),如果 \(q,r\in Z\) 满足 \(a=qb+r\) 且 \(0\le r<b\) ，\(a\) 模 \(b\) 等于 \(r\) 记作
- 负数取模：将 \(a\) 不断的加上 \(b\) 直到结果大于 \(0\) ，这个结果就是模运算的结果
模运算的性质
- \(b\mid a\Leftrightarrow a\space mod\space b=0\)
- \((a+b)mod\space n=(a\space mod \space n+b\space mod\space n)mod\space n\)
- \((a-b)mod\space n=(a\space mod \space n-b\space mod\space n)mod\space n\)
- \((a\times b)mod\space n=(a\space mod \space n\times b\space mod\space n)mod\space n\)
- 除法不具有这样的性质
积性函数
定义
数论函数：指定义域为正整数的函数。数论函数也可以视作一个数列。
若函数 \(f(n)\) 满足 \(f(1) = 1\) 且对于任意两个互质的整数 \(a,b\)，有 \(f(ab) = f(a)f(b)\)，则 \(f(n)\) 为积性函数。
若函数 \(f(n)\) 满足 \(f(1) = 1\) 且对于任意两个整数 \(a,b\)，有 \(f(ab) = f(a)f(b)\)，则 \(f(n)\) 为完全积性函数。
性质
若 \(f(x)\) 和 \(g(x)\) 都是积性函数，则一下函数 \(h(x)\) 也是积性函数：