Number Theory

写一些不是很熟识的东西。

约定：一般情况下 \(p\) 是质数。

Theorems

Wilson's theorem

\((p-1)!\equiv -1 \pmod p\)，等价于 \(p\) 是素数。

\(\text{proof.}\)

原式等价于方程 \(px+(p-1)!y=-1\)，方程显然有解，且若 \(p\) 不是质数则方程无解。\(\text{Q.E.D.}\)

Fermat's little theorem

若 \(p\) 为素数，\(\gcd(a,p)=1\)，则 \(a^{p-1}\equiv1\pmod p\).

另外一种更常用的表示是 \(a^{p-2}\equiv a^{-1}\pmod p\).

\(\text{proof.}\)

归。可知 \(1^p\equiv1\pmod p\) 显然成立，若 \(a^p\equiv a\pmod p\) 成立，则

\[(a+1)^p=\sum_{i=0}^p \dbinom{p}{p-i} a^i \]

由于 \(\dbinom{p}{k}=\frac{p(p-1)(p-2)\dots(p-k+1)}{k!}\)，于是 \(\forall k\in [1\dots n),\dbinom{p}{k}\equiv 0\pmod p\)，于是 \((a+1)^p\equiv a^p+1\equiv a+1\)，由归纳定理，可知所证成立。\(\text{Q.E.D.}\)

Euler's theorem

若 \(\gcd(a,m)=1\)，则 \(a^{\varphi(m)}\equiv 1\pmod m\).

\(\text{proof.}\)

设 \(r_1,r_2,\dots,r_{\varphi(m)}\) 是 \(m\) 的一个简化剩余系，那么 \(ar_1,ar_2,\dots,ar_{\varphi(m)}\) 也是 \(m\) 的一个简化剩余系，于是

\[\prod_{i=1}^{\varphi(m)} r_i\equiv \prod_{i=1}^{\varphi(m)}ar_i\pmod m \]

\(\prod_{i=1}^{\varphi(m)} r_i\) 可约去，于是命题得证。\(\square\)

当 \(m\) 为质数时，\(\varphi(m)=m-1\)，于是得到 Fermat's little theorem。

extend Euler's theorem

\[a^b\equiv \begin{cases} a^{b\bmod \varphi(m)}& \gcd(a,m)=1 \\a^b& \gcd(a,m)\not =1,b<\varphi(m) \\a^{(b\bmod \varphi(m))+\varphi(m)} & \text{otherwise} \end{cases} \pmod m \]

Chinese Remainder Theorem,CRT

一元线性同余方程组

\[\begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ \dots\\ x\equiv a_n\pmod{m_n} \end{cases} \]

有解，并且解可以被构造。其中 \(n\) 两两互质。

构造方式是:

记 \(M=\prod_{i=1}^n m_i\)，以及 \(M_i=M/m_i\)，设 \(t_i\) 使得 \(t_iM_i\equiv 1\pmod{m_i}\)。于是通解形式为

\[x_0=\sum_{i=1}^na_it_iM_i \]

所有解是 \(\{kM+x_0;k\in \mathbb Z\}\)。

这个东西很漂亮，难的是把构造想出来。

exCRT

如果 \(m_i\) 并不一一互质，exCRT 告诉我们这种情况下仍然有解且给出了构造方式。

我们发现所有闪光的点子在这里似乎都失效了，于是考虑朴素一点的方法。一个同余方程我们会解，于是考虑把多个同余方程合并成一个。先考虑两个。

\[\begin{cases} x\equiv a_i\pmod{m_i}\\ x\equiv a_j\pmod{m_j} \end{cases} \]

先将其转化为不定方程的形式

\[x=a_ip+m_i=a_jq+m_j(p,q\in \mathbb Z) \\ \iff a_ip-a_jq=m_j-m_i \]

如果 \((a_i,a_j)\not | (m_j-m_i)\)，那么无解，否则可以拿扩欧算。整个过程朴素到没有亮点。

Lucas' theorem

用途是求很大的 \(\dbinom{n}{k}\pmod p\)。

引理1：若 \(n\not=0,p\)，则 \(\dbinom{p}{n}\equiv 0\pmod p\)

拿阶乘表示出来就行了。

引理 2：设 \(f(x)=ax^n+bx^m\)，则有

\[f^p(x)\equiv f(x^p) \pmod p \]

\(\text{proof.}\)

\[f^p(x)=(ax^n+bx_m)^p \\=\sum_{k=0}^p \dbinom{p}{k}(ax^n)^k(bx^m)^{p-k} \\\equiv a^px^{pn}+b^px^{pm} \\ \equiv a(x^p)^n+b(x^p)^m=f(x^p) \]

\[\text{Q.E.D.} \]

Lucas 定理： $$\dbinom{n}{k}\equiv \dbinom{\lfloor n/p\rfloor}{\lfloor k/p \rfloor}\dbinom{n\bmod p}{k\bmod p} \pmod p$$

\(\text{proof.}\)

考察 \(\dbinom{n}{k}\) 的生成函数 \((1+x)^n\)。

\[(1+x)^n=(1+x)^{p\lfloor n/p\rfloor}(1+x)^{n\bmod p} \]

由引理 2，可知

\[(1+x)^n\equiv(1+x^p)^{\lfloor n/p\rfloor}(1+x)^{n\bmod p}\pmod p \]

\(x^k\) 的系数就是 \(\dbinom{n}{k}\bmod p\)，并且把 \(k\) 拆在两边的方式是唯一的，也即

\[k=p\lfloor\frac{n}{p}\rfloor+(n\bmod p) \]

于是定理得证。\(\square\)

exLucas Theorem

如果模数 \(m\) 不是质数怎么办？

把 \(m\) 质因数分解，设

\[m=\prod_{i=1}^s p_i^{\alpha_i} \]

分别计算 \(\dbinom{n}{k}\bmod p_i^{\alpha_i}\)，得到 \(s\) 个同余方程，然后就可以使用 CRT 直接算。

Technologies