---
title: Notes on Math Theory
tags:
  - Lagrange Interpolation Polynomial
  - Lucas's Theorem
  - Note
  - Prime
id: "991"
categories:
  - - OI
    - Number Theory
date: 2017-07-04 10:00:35
---

### 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)$.