Notes on Math Theory
Lucas
$n=(a_ka_{k-1}a_{k-2}\ldots a_0)_p, \ m=(b_kb_{k-1}b_{k-2}\ldots b_0)_p, \ {n \choose m} \equiv \prod_{i=0}^k {a_i \choose b_i} \pmod p$.
$n!$中$p$的次数$=\sum_{i=1}^{\infty} [{n \over p^i}]={n-S_p(n) \over p-1}$
${n \choose m}$中$p$的次数$p^\alpha \mid \mid {n \choose m} \Leftrightarrow p^\alpha \mid {n \choose m} \land p^{\alpha+1} \not \mid {n \choose m}$.
${n \choose m} \rightarrow p \not \mid {n \choose m} \Leftrightarrow {n-S_p(n) \over p-1}={m-S_p(m) \over p-1}+{n-m-S_(n-m) \over p-1} \Leftrightarrow m+(n-m)$在$p$进制下无进位。
$(1+x)^n \rightarrow x^m$系数${n \choose m}$.
$(1+x)^{p^k} \equiv 1+x^{p^k} \pmod p$.
$(1+x)^{a_kp^k+ \cdots +a_1p+a_0}=(1+x)^{a_kp^k} \cdots (1+x)^{a_1p}(1+x)^{a_0}$.
$\equiv (1+x^{p^k})^{a_k} \cdots (1+x^p)^{a_1}(1+x)^{a_0} \pmod p$.
$n!!=1 \times 3 \times 5 \times \cdots \times n$.
证明${n \choose k} (0 \le k \le n)$为奇数的个数是$2$的幂次。
Euler
$x^{\varphi(n)} \equiv 1 \pmod n, (x, n)=1$.
$x^n \equiv x^{n-\varphi(n)} \pmod n$.
$\bmod n$缩系.
$a_1 \times a_2 \times \cdots \times a_{\varphi(n)} \equiv a_1x \times a_2x \times \cdots \times a_{\varphi(n)}x \pmod n$.
$n$为素数，$x^{p-1} \equiv 1 \pmod p, p \not \mid x$.
$x^p \equiv x \pmod p$.
$\sum_{d \mid n} \varphi(d)=n$.
$\varphi(p^{\alpha})=p^{\alpha}-p^{\alpha-1}$.
$n=p_1^{\alpha_1} \cdots p_k^{\alpha_k}$.
$\sum_{\beta_i \le \alpha_i} \varphi(p_1^{\beta_1} \cdots p_k^{\beta_k})=\sum_{\beta_i \le \alpha_i} \prod_{i=1}^k \varphi(p_i^{\beta_i})=\prod_{i=1}^k \sum_{\beta_i \le \alpha_i} \varphi(p_i^{\beta_i})=\prod p_i^{\alpha_i}$.
求满足$n \mid 2^n-1$的$n$的个数。
$n=1$成立。
$n>1$时，设$p$为$n$最小的素因子。
满足$p \mid 2^{d_0}-1$的最小的$d_0$，$\forall p \mid 2^n-1, \ d_0 \mid n$.
$\begin{cases} p \mid 2^n-1\\ p \mid 2^{p-1}-1\\ p \mid 2^d-1 \end{cases} \Rightarrow \begin{cases} d \mid n\\ d \mid p-1 \end{cases} \Rightarrow d=1 \Rightarrow p \mid 1 \Rightarrow n=1$.
$ax+by=(a, b)$.
$nx+(p-1)y=(n, p-1)$.
$p \mid 2^{(n, p-1)}-1$.
∵$(n, p-1)=1$.
∴$p \mid 1$.
$1, x, x^2, \ldots, x^{\varphi(n)-1}$构成$\bmod n$的缩系，则称$x$为$n$的原根，记作$g$。
$p$是素数时，${g, g^2, \ldots, g^{p-1}} \equiv {1, 2, \ldots, p-1} \pmod p$.
$n$的原根有$\varphi(\varphi(n))$个。
给定$k$，求$\sum_{i=1}^{p-1} i^k \pmod p$。
${1, 2, \ldots, p-1} \Rightarrow {a, 2a, \ldots, (p-1)a}$.
$\sum i^k \equiv \sum (a_i)^k \Rightarrow (a^k-1) \sum i^k \equiv 0 \pmod p$.
二项同余式
$x^k \equiv n \pmod p$无解或有$(k, p-1)$个解。
$f(x) \equiv 0 \pmod p$.
$x^k \equiv 1 \pmod 1$有$d$个解，$d=(k, p-1)=ak+b(p-1)$。
$\begin{cases} x^{p-1} \equiv 1 \pmod p\\ x^k \equiv 1 \pmod 1 \end{cases} \Rightarrow x^{(k, p-1)} \equiv 1 \pmod p$至多$d$个解。
${x^{p-1}-1 \over x^d-1}=x^{p-1-d}+x^{p-1-2d}+ \cdots +x^d+1 \equiv 1 \pmod p$至多$p-1-d$个解。
$x^k \equiv 1 \pmod 1$恰有$d$个解。
$x \rightarrow p$的缩系，$x^k$有${p-1 \over (k, p-1)}$个不同的取值。
$x^{p-1} \equiv 1 \pmod p$且$x^d \not \equiv 1 \pmod p, d \lt p-1$，$x$是原根。
令$\gamma(n)$表示次数为$n$的数的个数。$p-1=q_1^{\alpha_1} \cdots q_k^{\alpha_k}, \gamma(q^{\alpha})=q^{\alpha}-q^{\alpha-1}$，且$\gamma$是积性函数。
$x^{q^{\alpha}} \equiv 1 \pmod p$.
$x^{q^{\alpha-1}} \not \equiv 1 \Leftrightarrow \forall d \lt q^{alpha}, \ x^d \not \equiv 1 \pmod p$.
$x^{(q^{\alpha}, d)} \equiv 1 \Leftrightarrow x^{q^{\beta}} \equiv 1 \pmod p$.
$\gamma(l_1l_2)=\gamma(l_1)\gamma(l_2)$.
$h_1$次数是$l_1$，$h_2$次数是$l_2 \Rightarrow h_1h_2$的次数是$l_1l_2$。
$x$次数是$l_1l_2 \Rightarrow x_1$次数是$l_1$，$x_2$次数是$l_2$。
Prime
$\lim \sum_{p=1}^{\infty} (1-{1 \over p})=0$.
$f(x) \equiv 0 \pmod {p^{\alpha}}$的解数$=f(x) \equiv 0 \pmod p$的解数$\Leftarrow \begin{cases} f(x) \equiv 0\\ f’(x) \equiv 0 \end{cases} \pmod p$无解。
$x^2+1 \equiv 0 \pmod {p^{\alpha}}, p \ge 3$无解或恰有$2$解。
勾股数的通式
$a^2+b^2=c^2 (a, b, c \gt 0)$.
$(a, b, c)=1$本原。
$a^2+b^2=c^2 \Rightarrow b^2=c^2-a^2=(c-a)(c+a)$.
$(c-a, c+a)=(2c, c-a)=(2, c-a)=1$.
$2 \not \mid c-a$.
设$b$为偶数，$a$为奇数，则$c$为奇数。
$\begin{cases} {c-a \over 2}=m^2\\ {c+a \over 2}=n^2 \end{cases}$.
$\begin{cases} b=2mn\\ a=n^2-m^2\\ c=n^2+m^2 \end{cases}$.
多项式
拉格朗日差值公式：$f(x)=\sum_{i=1}^n \prod_{j \neq i} {(x-x_j) \over (x_i-x_j)}f(x_i)$.
牛顿差值公式：$f(x)=a_0+a_1(x-x_1)+a_2(x-x_1)(x-x_2)+ \cdots +a_n \prod_{i=1}^n (x-x_i)$.
有理根 Eisenstein
$f \in Z[x], f(x)=a_nx^n+ \cdots +a_1x+a_0$.
$\pm {p \over q} \Rightarrow p \mid a_n, q \mid a_0$.
$f(x)=c_nx^n+c_{n-1}x^{n-1}+ \cdots +c_1x+c_0$可约$\Leftarrow p \mid c_0, p \mid c_1, \ldots, p \mid c_{n-1}, p \not \mid c_n, p^2 \not \mid c_0$.
$f(x)=c_nx^n+c_{n-1}x^{n-1}+ \cdots +c_1x+c_0$可约$\Leftarrow p \mid (c_0, c_1, \ldots, c_{n-1}), p \not \mid c_n, p^2 \not \mid c_0$.
$f(x)=x^{p-1}+x^{p-2}+ \cdots +x+1={x^p-1 \over {x-1}}$.
令$y=x-1$，$f(x)=g(y)={(y+1)^p-1 \over y}=y^{p-1}+{p \choose 1}y^{p-2}+ \cdots +{p \choose p-1}$.
升幂定理
令$V_p(n)$表示$n$中$p$的次数。
$5^{210000}-2^{210000}$里有多少$3$的幂次。$2$次。
$(1+p)^k-1$里有多少$p$的幂次。$1+V_p(k)$次。
$5^{33333}+1$里有多少$3$的幂次。$2$次。
$p^{\alpha} \mid \mid a-b, (a, p)=1, (b, p)=1, p \ge 3$.
$V_p(a^m-b^m)=\alpha+V_p(m)$.
设$p^{\alpha} \mid \mid a^n-b^n$.
$p^{\alpha} \mid \mid a^{pn}-b^{pn}$.
$p^{\alpha} \mid \mid a^{kn}-b^{kn}, (k, p)=1$.
二次剩余
$ax^2+bx+c \equiv 0 \pmod p$.
$x^2 \equiv a \pmod p$.
勒让德符号：$({a \over p})=\begin{cases} 0 & p \mid a\\ 1 & a是p的二次剩余\\ -1 & a不是p的二次剩余 \end{cases}$.
${p-1 \over (2, p-1)}={p-1 \over 2}$.
$1^2, 2^2, 3^2, \ldots, ({p-1 \over 2})^2$.
二次剩余数量$=$非二次剩余数量$={p-1 \over 2}$。
Euler 判别法：$n^{p-1 \over 2} \equiv ({n \over p}) \pmod p, (n, p)=1$.
Gauss Lama：$n, 2n, 3n, \ldots, {p-1 \over 2}n \pmod p$的最小正剩余中大于${p-1 \over 2}$的个数为$m$，则$({n \over p})=(-1)^m$。
$({2 \over p})=(-1)^{p^2-1 \over 8}=(-1)^{[{p \over 2}]-[{p \over 4}]}$.
二次互反：$({q \over p})({p \over q})=(-1)^{ {p-1 \over 2}{q-1 \over 2}}$.
Summary
$n=(a_ka_{k-1}a_{k-2}\ldots a_0)_p, m=(b_kb_{k-1}b_{k-2}\ldots b_0)_p, {n \choose m} \equiv \prod_{i=0}^k {a_i \choose b_i} \pmod p$.
$x^{\varphi(n)} \equiv 1 \pmod n, (x, n)=1$.
$x^n \equiv x^{n-\varphi(n)} \pmod n$.
$n$为素数，$x^{p-1} \equiv 1 \pmod p, p \not \mid x$.
$x^p \equiv x \pmod p$.
$x^k \equiv n \pmod p$无解或有$(k, p-1)$个解。
$x^k \equiv 1 \pmod 1$有$d$个解，$d=(k, p-1)=ak+b(p-1)$。
$x \Rightarrow p$的缩系，$x^k$有${p-1 \over (k, p-1)}$个不同的取值。
$\bmod p$的原根有$\varphi(p-1)$个。
$\lim \sum_{p=1}^{\infty} (1-{1 \over p})=0$.
$f(x) \equiv 0 \pmod {p^{\alpha}}$的解数$=f(x) \equiv 0 \pmod p$的解数$\Leftarrow \begin{cases} f(x) \equiv 0\\ f’(x) \equiv 0 \end{cases} \pmod p$无解。
$\begin{cases} b=2mn\\ a=n^2-m^2\\ c=n^2+m^2 \end{cases}$.
拉格朗日差值公式$f(x)=\sum_{i=1}^n \prod_{j \neq i} {(x-x_j) \over (x_i-x_j)}f(x_i)$.
牛顿差值公式$f(x)=a_0+a_1(x-x_1)+a_2(x-x_1)(x-x_2)+ \cdots +a_n \prod_{i=1}^n (x-x_i)$.
$f(x)=c_nx^n+c_{n-1}x^{n-1}+ \cdots +c_1x+c_0$可约$\Leftarrow p \mid c_0, p \mid c_1, \ldots, p \mid c_{n-1}, p \not \mid c_n, p^2 \not \mid c_0$.
$f(x)=c_nx^n+c_{n-1}x^{n-1}+ \cdots +c_1x+c_0$可约$\Leftarrow p \mid (c_0, c_1, \ldots, c_{n-1}), p \not \mid c_n, p^2 \not \mid c_0$.
$p^{\alpha} \mid \mid a-b, (a, p)=1, (b, p)=1, p \ge 3$.
$V_p(a^m-b^m)=\alpha+V_p(m)$.