【acm】【数论】阶和原根
阶
定义
设\(m > 1\) 且 \((a, m) = 1\)，则使得
\[a^t \equiv 1 \pmod m\]
成立的最小的正整数\(t\)称为 \(a\)对模\(m\)的阶，记为\(\delta_m(a)\)。
定理
定理1 若\(m>1\)且\((a, m) = 1\)，且\(a^n \equiv 1 \pmod m\), n > 0，则有
\[\delta_m(a)\,|\, n\]
定理2 由定理1和欧拉定理易知
\[\delta_m(a)\,|\, \phi(m)\]
推论
推论1 若\(p\)和\(q\)为奇素数，且\(q\,|\,(a^p-1)\)，则或有\(q\,|\,(a-1)\)，或有\(q = 2kp+1\), 其中k为某整数。
推论2 \(2^p-1\)的任何因子必取\(2kp+1\)的形式。
原根
定义
如果\(a\)的阶(mod m)为\(\phi(m)\)，则称\(a\)为\(m\)的一个原根。 即若\(\delta_m(a)=\phi(m)\)，则称\(a\)为\(m\)的一个原根。
定理
定理1 若\(g\)是\(m\)的一个原根，则 \[g, g^2, \cdots, g^{\phi(m)}\] 各数对模m的最小剩余，恰是小于\(m\)且与\(m\)互素的\(\phi(m)\)个正整数的一个排列。
定理2 每一个素数\(p\)都有\(\phi(p-1)\)个原根。事实上，每一个数\(m\)都有\(\phi(\phi(m))\)个原根(如果有的话)。
定理3 一个数\(m\)有原根的充要条件是\(m = 1, 2, 4, p^e, 2p^e\), 其中\(p\)为奇素数， \(e\)为正整数。
推论
推论1 若\(d\,|\,(p-1)\)，则\(x^d \equiv 1 \pmod p\)恰有\(d\)个解。
推论2 若\(p\)为素数，\(d\,|\,(p-1)\)，则阶为\(d\)的最小剩余(mod p)的个数为\(\phi(d)\)。
原根的求法
求一个数\(m\)的原根，先求\(\phi(m)\)的素幂分解式，即
\[\phi(m)= p_1^{e_1}p_2^{e_2} \cdots p_k^{e_k}\]
然后枚举\(g\)，若\(g\)满足恒有
\[g^{\frac{\phi(m)}{p_i}} \not = 1 \pmod m,\qquad i = 1, 2, \cdots, k\]
则\(g\)为\(m\)的一个原根。
tips
数据不大的时候枚举所有\(\phi(m)\)的因子(除本身)也可。
练手题
【acm】【数论】欧拉定理与欧拉函数
欧拉定理
定义
设\(m >= 2, (a, m) = 1\)。若\(\phi (m)\)表示小于\(m\)且与\(m\)互素的正整数的个数，则有
\[a^{\phi(m)} \equiv 1 \pmod m \tag{1.1}\]
tips
其中\(m\)不一定为素数。
若\(m\)为素数，则\(\phi(m) = m-1\), 上式变为费马小定理，即
\[a^{m-1} \equiv 1 \pmod m\]
证明
欧拉定理的证明与费马小定理的证明类似，需要以下引理。
引理1 若\((a, m ) = 1, r_1, r_2, \cdots, r_{\phi(m)}\)是小于\(m\)且与\(m\)互素的正整数，则
\[ ar_1, ar_2, \cdots, ar_{\phi(m)}\]
的最小剩余(mod m)是
\[r_1, r_2, \cdots, r_{\phi(m)}\]
的一排列。
tips
此引理的证明使用反证法即可。
下证欧拉定理。
由引理1可得
\[r_1* r_2*\cdots*r_{\phi(m)} \equiv (ar_1)*(ar_2)* \cdots*ar_{\phi(m)} \pmod m\]
即
\[r_1* r_2*\cdots*r_{\phi(m)} \equiv a^{\phi(m)}*(r_1* r_2*\cdots*r_{\phi(m)}) \pmod m\]
由于\(r_1, r_2, \cdots, r_{\phi(m)}\)每一个都与\(m\)互素，所以可消去，得
\[1 \equiv a^{\phi(m)} \pmod m\]
得证。
欧拉函数
定义
上面所提及的\(\phi(m)\)即为欧拉函数，表示小于m且与m互素的正整数的个数。
其有以下计算公式。
若n的素幂分解式为\(n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\)，则有
\[\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k}) \tag{2.1}\]
另一种形式为
\[\phi(n) = p_1^{e_1-1}(p_1-1)p_2^{e_2-1}(p_2-1)\cdots p_k^{e_k-1}(p_k-1) \tag{2.2}\]
显然二者是等价的。
证明
欧拉函数可由由积性函数的性质得出。
证明所需要引理。
引理2 对一切正整数\(n\), 有
\[\phi(p^n) = p^{n-1}(p-1)\]
引理3 若\(r_1, r_2, \cdots, r_{\phi(m)}\)的最小剩余(mod m)是\(0, 1, 2, \cdots, m-1\)的一个排列，则
\[r_1, r_2, \cdots, r_{\phi(m)}\]
中恰有\(\phi(m)\)个元素与\(m\)互素。
引理3可证\(\phi(m)\)为积性函数，而积性函数具有以下性质。
若\(f\)是一个积性函数，\(n\)的素幂分解式为\(n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\)，则
\[f(n) = f(p_1^{e_1})f(p_2^{e_2})\cdots f(p_k^{e_k})\]
再由引理2求得的素数幂项，即可求得正整数范围内的\(\phi(n)\)。
实现
给定整数\(n\)，求得其欧拉函数的一个实现如下。
1 | // 求单个整数的欧拉函数 |
应用
降幂。 如果模不为素数，就不能用前面讲过的费马小定理来降幂了。
此时可以用欧拉定理降幂，降幂公式如下。
\[a^n \mod p = a^{n \mod \phi(p) + \phi(p)} \mod p, \quad n > \phi(p) \tag{3.1}\]
tips
\(n < \phi(p)\)的时候不用降幂。
注意此时\(p\)不一定为素数。
而且a和p也不一定互素。 所以此式又称广义欧拉定理。
补一个推论
若n>= 1，则
\[\sum_{d|n} \phi(d) = n \tag{4.1}\]
例题
Colossal Fibonacci Numbers! UVA - 11582
除此之外，还可以求有关阶，原根，指数相关的问题。有些题目也需要转化为带有欧拉函数的公式。
【acm】【数论】威尔逊定理：素数的充要条件
定义
\(p\)为素数的充要条件为
\[(p-1)! \equiv -1 \equiv p-1 \pmod p \tag{1.1}\]
也可以说是
\[p\quad|\quad{ (p-1)!+1 } \tag{1.2}\]
证明
百度百科的证明特别简明易懂。
应用
可以将一些与阶乘有关的同余式和素数联系起来，以解决某些特定的问题。
【acm】【数论】费马小定理：求逆元与降幂
定义
若p为素数， (a, p) = 1, 则\[a^{p-1} \equiv 1 \pmod p \tag{1.1}\]
证明
引理1 若(a, m) = 1, 则\[a, 2a, 3a, ..., (m-1)a\] 的最小剩余(mod m) 按某种次序排列后为\[1, 2, 3, ..., m-1\]
tips
关于引理1的证明不作赘述，主要是证明两两的最小剩余不重复，使用反证法即可。
有了引理1，即可证明费马小定理，证明如下。
由引理1易知 \[a*2a*3a*\cdots*(p-1)a \equiv 1*2*3*\cdots*(p-1) \pmod p\]
即
\[a^{p-1}(p-1)! \equiv (p-1)! \pmod p\]
又\((p, (p-1)!) = 1\)，即\(p\)与\((p-1)!\)互素，则有
\[a^{p-1} \equiv 1 \pmod p\]
得证。
求逆元
见 乘法逆元: 扩展欧几里德 费马小定理 递推 带余数同余式的一般解法
降幂
推论 若\(p\)为素数， 则对一切\(a\)，都有 \[a^p \equiv a \pmod p \tag{3.1}\]
tips
注意这里是一切\(a\)，即\(a\)和\(p\)不一定互素。
当指数比较大的时候，可以使用下面的公式进行降幂。
若\(p\)为素数，且\(p\)不能整除\(a\)(或能整除则结果为0)，有
\[a^n \equiv a^{n \ mod {(p-1)}} \pmod p \tag{3.2}\]
下证此式。
设如下变量:
\[ \left\{ \begin{array}{l} k = \frac{n}{p-1} \\ b = n \pmod{ p-1 } \\ \end{array} \right. \]
即 \[ n = k \cdot (p-1) + b \]
则有
\[a^n \equiv a^{k * (p-1) + b} \pmod p\]
即 \[a^n \equiv (a^k)^{p-1}*a^b \pmod p\]
又
\[ (a^k)^{p-1} \equiv 1 \pmod p\]
所以
\[a^n \equiv a^b \pmod p\]
得证。