数论学习笔记
记录的侧重点为一些个人认为需要证明的性质定理，所以概念可能不成体系且跳跃
P:质数集
取模
-
取模的定义：
\(a \bmod b = a - \lfloor \frac{a}{b} \rfloor b\)
但是注意c++的
%的除法并不是向下取整，而是向零取整，这就会导致负数取模完还是负数，如：-6%5=-6-(-6/5)*5=-1所以代码中对整数集Z取模我们一般会写成：
(a%b+b)%b -
取模的性质：
\((a + b) \bmod m = ((a \bmod m) + (b \bmod m)) \bmod m\)
\((a \times b) \bmod m = ((a \bmod m) \times (b \bmod m)) \bmod m\)
非常有用也非常好理解，证明直接代入定义化简即可：
\[\begin{align} & ((a \bmod m) + (b \bmod m)) \bmod m \\ = & (a + b - (\lfloor \frac{a}{m} \rfloor + \lfloor \frac{b}{m} \rfloor)m) \bmod m \\ = & a + b - (\lfloor \frac{a}{m} \rfloor + \lfloor \frac{b}{m} \rfloor)m - \lfloor \frac{a + b - (\lfloor \frac{a}{m} \rfloor + \lfloor \frac{b}{m} \rfloor)m}{m} \rfloor m \\ = & a + b - \lfloor \frac{a + b}{m} \rfloor m \\ = & (a + b) \bmod m \end{align} \]乘法同理，但除法不具有这种形式的性质，需要求解分母的逆元将其转化为乘法
整除和同余
-
整除：
\(a|b\)表示a是b的约数，b是a的倍数
-
同余：
\(a \equiv b \pmod m \iff a \bmod m = b \bmod m\)
但如果再展开就会出现一大堆除法和下取整，不便于推式子，所以一般从整除的角度理解同余会更好：
\(a \equiv b \pmod m \iff a - b \equiv 0 \pmod m \iff m|a-b\)
然后就可以用约数倍数的那些结论来处理同余问题了
-
剩余系：
涉及到群论概念所以我也不是很清楚
大概就是对m取模以后，整个整数集Z会被映射到{0,1,...,m-1}上来，得到的这个新的集合就叫剩余系
欧几里得定理
-
引理：
\(\forall a,b \in Z,g | a,g|b \implies \forall x,y \in Z,c=ax+by,g|c\)
即若g是a、b的公约数，则g也是a、b线性组合的约数
证明：
令 \(a=pg,b=qg\) ，则有 \(c=ax+by=(px+qy)g\) ，因此 \(g|c\)
-
欧几里得定理：
\(\forall a,b \in Z,\gcd(a,b)=\gcd(b,a \bmod b)\)
证明：
只需证： \(\gcd(a,b)|\gcd(b,a \bmod b)\) 且 \(\gcd(b,a \bmod b)|\gcd(a,b)\)
对于前式，令 \(g=\gcd(a,b)\) ，则 \(g|a,g|b\)
由于 \(a \bmod b\) 可以写成a、b线性组合的形式，即 \(a \bmod b = a-\lfloor \frac{a}{b} \rfloor b\)
由引理得 \(g | a \bmod b\) ，又因为 \(g | b\)
所以 \(g | \gcd(b,a \bmod b)\) ，即 \(\gcd(a,b) | \gcd(b,a \bmod b)\)
对于后式，取线性组合为 \(a=a \bmod b + \lfloor \frac{a}{b} \rfloor b\)，其它过程同理
综合前后两式可得 \(\gcd(a,b)=\gcd(b,a \bmod b)\)
欧拉定理
-
费马小定理：
\(\forall p \in P,a \in N^*,a<p,a^{p-1} \equiv 1 \pmod p\)
-
欧拉定理：
\(\forall p \in N^*,a \in N^*,a<p,a \perp p,a^{\phi(p)} \equiv 1 \pmod p\)
其中\(\perp\)表示互质，\(\phi\)为欧拉函数，显然费马小定理是欧拉定理在p为质数时的特例，那就只证欧拉定理好咯
证明：
取集合\(A=\{x_1,x_2,...,x_{\phi(p)}\}\)为与p互质的正整数
令\(B=\{ax_1,ax_2,...,ax_{\phi(p)}\}\)，我们有\(A=B\)，理由如下：
-
\(a \perp p,x_i \perp p \implies ax_i \perp p\)
-
\(\forall i \ne j,a \perp p,x_i-x_j \perp p \implies p \perp a(x_i-x_j) \iff p \not | a(x_i-x_j)\)
写成同余形式即有\(a(x_i-x_j) \not \equiv 0 \pmod p \iff ax_i \not \equiv ax_j \pmod p\)
然后各自把A和B里面的所有元素乘起来
\(a^{\phi(p)}\prod x_i \equiv \prod x_i \pmod p \iff a^{\phi(p)} \equiv 1 \pmod p\)
-
威尔逊定理
用于判定素数的定理，OI中不常用
对于\(p \in N^*,p>1\)，有\((p-1)! \equiv -1 \pmod p \iff p \in P\)
证明：
\(p \le 4\)时代入特判，其中p=4时结果为2
\(p>4\)时，取集合\(\{1,...,p-1\}\)，分类讨论：
-
如果p是质数：
\(x^2 \equiv 1 \pmod p \iff x \equiv \pm 1 \pmod p\)，即有且仅有1和p-1的逆元是它们自己
那么集合中其余数（共偶数个）都能通过找逆元两两配对，因为它们的逆元不为\(\pm 1\)也不为它们自己，而且形成的是双射，然后又因为一对逆元相乘后得1
于是\((p-1)! \equiv 1 \times (p-1) \equiv -1 \pmod p\)
-
如果p是合数：
若p不是完全平方数，一定能找到\(1<q<p\)使得\(1<\frac{p}{q}<p,q \ne \frac{p}{q}\)
于是\(q \times \frac{p}{q} \equiv 0 \pmod p\)，故\((p-1)! \equiv 0 \pmod p\)
若p是完全平方数，令\(p=k^2\)，由于\(k>2\)，我们可以取k和2k
于是\(k \times 2k \equiv 0 \pmod p\)，故\((p-1)! \equiv 0 \pmod p\)
一个无聊的结论：对于\(p\in N^*,p>1\),有$(p-1)! \equiv 0 \pmod p \iff p \not\in P,p>4 $