1. 同余
运算性质
如果$a_1 \equiv a_2 \pmod p$ 则余保持加减乘运算:
\[a_1+a_2 \equiv b_1 +b_2 \pmod p \tag1\] \[a_1a_2 \equiv b_1b_2 \pmod p \tag2\]一个例子：将一个整数十进制多项式展开后，其 $10^{i} \pmod 3\ or\ 10^{i} \pmod 9$ 时该项均为$1$，即取模这些数的情况下结果相当于$\sum_{i=0}^n a_i \pmod {3\ or\ 9}$。该计算方法在符合情况下可推广。
设 $ad \equiv bd \pmod p$，若 $\gcd (d,m)=1$，则 $a \equiv b \pmod m$。注意 $p$ 一般为大质数，便容易满足 $\gcd (d,p)=1$，否则不完全成立。
设 $a \equiv b \pmod p$，若 $d \vert\gcd (a,d,p)$，则$\cfrac ad \equiv \cfrac bd \pmod {\cfrac pd}$。下面给出证明：
\[d \vert\gcd (a,d,p) \Rightarrow a=a'd,b=b'd,p=p'd \tag 1\] \[a \equiv b \pmod p \Rightarrow a=b+pk,\ da'=db'+dp'k \tag 2\] \[da'=db'+dp'k \Rightarrow a'=b'+kp' \Rightarrow a'\equiv b'\pmod {p'} \tag 3\] \[a'\equiv b'\pmod {p'} \Rightarrow \frac ad \equiv \frac bd \pmod {\cfrac pd} \tag 4\]设 $a \equiv b \pmod p$，如果 $d \vert p$，则 $a \equiv b \pmod d$。下面给出证明：
\[p = qd,\ a=b+pd=b+kqd \tag1\] \[t= kq,\ a=b+kqd=b+td \Rightarrow a \equiv b \pmod d\tag2\]设 $a \equiv b \pmod {m_i}$，则$ a \equiv b \pmod {lcm(m_0,m_1,\cdots,m_n)}$。下面给出证明:
\[a \equiv b \pmod {m_i} \rightarrow m_i\vert (a-b) \tag1\] \[{lcm(m_0,m_1,\cdots,m_n)}\vert(a-b) \tag2\]设 $a \equiv b \pmod m$，则$\gcd(a,m) = \gcd(b,m)$。下面给出证明：
\[a \equiv b \pmod m \rightarrow a=b+km \tag1\] \[a=km+b \rightarrow \gcd(a,m) = \gcd(m,b) \tag2\]
完全剩余系
- 设 $\gcd (a,m)=1$，$b$是任意整数，若$X$是一个模$m$的完全剩余系，则$aX+b$也是。下面给出证明:
- 需证明 $ax_0+b,ax_1+b,\cdots,ax_{m-1}+b$ 模 $m$ 的值均不相同
- 反证法，假设 $ax_i+b \equiv ax_j+b \pmod m$，则$m \vert (a(x_i-x_j)))$
- 由于 $\gcd(a,m)=1$，所以$m \vert(x_i-x_j)$，说明 $x_i,x_j$ 模 $m$同余，与假设矛盾，故结论成立
- 设 $\gcd(m1,m2)=1$，若 $X,Y$分别是模 $m_1$和 模 $m_2$的完全剩余系，则 $m_2X+m_1Y$为模 $m_1m_2$的完全剩余系。下面给出证明:
- 同上证明，假设 $m_2x_i+m_1y_j \equiv m_2x_l+m_1y_k \pmod{m_1m_2}$
- 则 $m_2x_i+m_1y_j \equiv m_2x_l+m_1y_k \pmod{m_1}$，即$m_2x_i\equiv m_2x_l \pmod{m_1}$，$x_i\equiv x_l \pmod{m_1}$
- 同理得$y_j\equiv y_k \pmod{m_2}$，但是 $x_i\equiv x_l \pmod{m_1}$ 与 $y_j\equiv y_k \pmod{m_2}$ 不能同时成立，否则$m_2x_i+m_1y_j$ 与 $m_2x_l+m_1y_k$为同一项，与假设矛盾，故结论成立
- 设 $p,q$是不同的素数，$n=pq$。则对于任意 $c$，$qx+py \equiv c \pmod n$，$0 \le x< p,\ 0 \le y< q$的解唯一。根据第$2$点的性质即可证明，其中 $p=m_1,q=m_2,n=m_1m_2,qx+py=m_2x+m_1y$。限制 $x,y$的范围目的是使得$X,Y$恰好在一个完全剩余系，$qx+py$正好有 $pq$个完全不同的值，与$n$的完全剩余系一一对应。
2. 简化剩余与欧拉函数
简化剩余类
假设一个剩余类中存在一个与 $m$互素的元素，则该类称为简化剩余类。
简化剩余系
所有的不同的简化剩余类的集合，数量即为与 $m$互素的整数个数 $(x < m)$。
- 设 $\gcd(a,m)=1$，当 $X$ 为完全简化剩余系时，$aX$ 同样为完全简化剩余系。证明如下：
- 因为 $\gcd(a,b)=1,\gcd(x,m)=1$，所以 $\gcd(ax,m)=1$，这说明 $aX$符合简化剩余的基本条件
- 又 $ax_1 \equiv ax_2 \pmod m$ 时有 $x_1 \equiv x_2 \pmod m$，所以 $aX$ 中可不能存在相同的两个元素，故结果成立。
- 设 $\gcd(a,m)=1$，则存在整数$a’$，$1\le a’< m$，使得 $aa’ \equiv 1 \pmod m$
- 因为 $\gcd(a,m)=1$，当 $X$ 为最小简化剩余系时，$aX$ 同样为简化剩余系，必然存在 $aa’\equiv1 \pmod m$
- 求解方法使用扩欧即可
- 设 $\gcd(m1,m2)=1$，若 $X,Y$分别是模 $m_1$和 模 $m_2$的简化剩余系，则 $m_2X+m_1Y$为模 $m_1m_2$的简化剩余系。证明同完全剩余系，本质相同。
欧拉函数
$m,n$互素时，$\varphi(mn)=\varphi(m)\varphi(n)$，没有公共的因子计算时独立再相乘即可。证明基于简约剩余系的第 $3$ 点。若 $X,Y$分别是模 $m$和 模 $n$的简化剩余系，则 $nX+mY$为模 $mn$的简化剩余系，$nX+mY$ 有 $\varphi(m)\varphi(n)$ 个不同的结果。
- 设 $n$ 有标准因数分解式 $n=\prod_{p\vert n} p^a=p_0^{a_0}\cdot p_1^{a_1}\cdot \cdots p_k^{a_k}$，其中 $p_i$为素因子，$a_i$为该因子的出现次数。
- 由于 $p_i$ 之间没有公因子，所以有 $\varphi(n)= \varphi(p_0^{a_0})\varphi(p_1^{a_1})\cdots \varphi(p_n^{a_n})$
- $\varphi(p_i^{a_i})$实质上表示的是比$p_i^{a_i}$小，且不含 $p_i$ 因子的数，故$\varphi(p_i^{a_i})=p_i^{a_i}-p_i^{a_i-1}$
- $\varphi(n)=(p_0^{a_0}-p_0^{a_0-1})(p_1^{a_1}-p_1^{a_1-1})\cdots(p_k^{a_k}-p_i^{a_k-1})$
- $\varphi(n)=(p_0^{a_0}(1-\frac1{p_0}))(p_1^{a_1}(1-\frac1{p_1}))\cdots(p_k^{a_k}(1-\frac1{p_k}))$
- $\varphi(n)= n\prod_{i=0}^k (1-\frac1{p_i})$
设 $p,q$ 是不同的素数，则 $\varphi(pq)=pq-p-q+1$。若已知$n$且其是两个不同素数的乘积和$\varphi(n)$。根据根与系数的关系，可求出 $n$ 的因数分解式。
\[\begin{align} p+q&=n+1-\varphi(n) \\ pq&=n\end{align}\]- 若 $n$ 是一个正整数，则 $\sum_{d\vert n} \varphi(d)=n$。下面进行证明
- $ C_d = \lbrace m \vert \ 1\le m \le n,\ \gcd(m,n)=d \rbrace$
- $\gcd(m,n)=d$ 成立的充要条件为 $\gcd(\frac md,\frac nd)=1$
- 可得到 $C_d = \lbrace m=dk \vert \ 1\le k \le \frac nd,\ \gcd(k,\frac nd)=1 \rbrace$，$\lbrace 1\le k \le \frac nd,\ \gcd(k,\frac nd)=1 \rbrace$ 表示的即是$\varphi(\frac nd)$，所以 $\varphi(\frac nd) = \vert C_d\vert$
- 又因为对于每一个 $n$，$\gcd(m,n)=d$ 是存在且唯一的，所以每个 $n$ 值都只会在一个 $C_d$ 中。
- 故 $\sum_{d\vert n} \varphi(\frac qd)=\sum_{d’\vert n} \varphi(d’)=n$
3. 欧拉定理与费马小定理
欧拉定理
如果 $\gcd(a,m)=1$，则$a^{\varphi(m)} \equiv1\pmod m$，证明如下:
- 假设 $R$ 为模 $m$ 的最小简化剩余系，故 $aR$ 也是模 $m$ 最小简化剩余系。即 $R$ 和 $aR$ 包含元素相同，仅顺序不同
- $(ar_1)(ar_2)\cdots(ar_{\varphi(m)})\equiv r_1r_2\cdots r_{\varphi_m} \pmod m$
- 消除 $R$ 的部分，得到 $a^{\varphi(m)} \equiv 1 \pmod m$
费马小定理
当 $p$ 为素数时，$a^p \equiv a \pmod p$。证明如下，当 $p$ 为素数时，$\varphi(p)=p-1$，根据欧拉定理得:
\[\begin{align} a^{p-1} &\equiv 1 \pmod m \tag1 \\ a^{p} &\equiv a \pmod m \end{align}\]4. 蒙哥马利算法（Montgomery Algorithm）
其目的在于计算机运算中，快速进行大数模乘。即求 $A\cdot B \pmod N$，考虑 $r$ 进制情况，需满足 $gcd(r,N)=1$，思路如下。
考虑将 $B$ 二进制分解，即$A\cdot B \pmod N= A \sum_{i=0}^kb_i2^i \pmod N$
$A \sum_{i=0}^kb_ir^i \pmod N = Ab_0r^0+r(Ab_1+r(Ab_2+\cdots r(Ab_k)\cdots)) \pmod N$，该式子的本质是构造了一个从高次到低次的求解过程。
Input: A,B Output: A*B mod N d = 0 for i in range(k-1,-1,-1): ans = (A * b[i] + r * d) % N return d令 $Z=Ab_i+rd$，直接计算 $Z\pmod N$代价较大，考虑计算 $Zr^{-1} \pmod N$，最终得到的结果为 $ABr^{-k} \pmod N $。
Input: A,B Output: A*B*r^(-k) mod N d = 0 for i in range(k-1,-1,-1): ans = (A * b[i] + r * d)/r % N return d这样处理的目的在于，当 $Z$ 恰好是 $r$ 的倍数时，只需讲式子右移一位即可。如果 $r\vert Z$，则 $Z+kN \equiv 0\pmod r$，$k \equiv -ZN^{-1} \pmod r$。
根据欧拉定理，由于 $gcd(r,N)=1$，故$N^{-1}\equiv N^{\varphi(r)-1} \pmod r$，$r$ 一般为 $2^t$，即 $\varphi(r)=2^{t-1}$，可以通过快速幂计算。由此 $N^{-1}$可以快速被计算，从而 $k$ 也可以得出。
随后可知$Z+kN \equiv Z\pmod N$，$Zr^{-1} \equiv (Z+kN)/r \pmod N$。关键之处就在于 $/r$ 的计算只要讲式子进行移位即可，因为 $r \vert (Z+kN)$。
Input: A,B Output: A*B*r^(-k) mod N d = 0 p = N^(-1) % r for i in range(k-1,-1,-1): = -d * p % r ans = (A * b[i] + r * d - kN)/r % N return d- 实际应用时 $r^k$ 应该满足 $r^{k-1}\le N<r^k$。在这种情况下，$(Z+kN)/r $的值仅会在$[0,2N)$之间，大大优化了取模的运算。下面进行归纳法证明：
- 初始时 $d$ 显然成立
- 任意时候 $a<N,b_i<r,k<r$，因此 $Z+kN=ab_i+d+kN<(r-1)N+2N+(r-1)N=2rN$，从而$(Z+kN)/r<2N$
- 具体计算流程 $XY \pmod N$。
- 确定 $r$ 并找到相应的 $k$ 满足 $r^{k-1}\le N<r^k$
- 计算 $\rho = r^{2k}$
- $A = MontMul(X,\rho) =X\cdot r^k \pmod N$
- $B = MontMul(Y,\rho) =Y\cdot r^k \pmod N$
- $C = MontMul(A,B) =X\cdot Y\cdot r^k \pmod N$
- $D = MontMul(D,1) =X\cdot Y\pmod N$