威尔逊定理

1 威尔逊定理

内容： 对于素数 $p$ 有 $(p-1)!\equiv -1\pmod p.$

推论： $(p-1)!\equiv0(mod$ $p),(p>4\land p$ 为合数$ )$

计算余数算法:

实现 $n!$ % $p$.

时间复杂度： 时间复杂度为 $O(p + \log_p n)$. 如果需要多次调用函数，则可以在函数外部进行预计算，于是计算 $(n!)_p$ 的时间复杂度为 $O(\log_p n).$

int factmod(int n, int p) {
  vector<int> f(p);
  f[0] = 1;
  for (int i = 1; i < p; i++) f[i] = f[i - 1] * i % p;
  int res = 1;
  while (n > 1) {
    if ((n / p) % 2) res = p - res;
    res = res * f[n % p] % p;
    n /= p;
  }
  return res;
}

2 $Legendre$ 公式:

$n!$ 中含有的素数 $p$ 的幂次 $v_p(n!)$ 为：

$v_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor = \frac{n-S_p(n)}{p-1}$ 其中 $S_p(n)$ 为 $p$ 进制下 $n$ 的各个数位的和。

特别地，阶乘中 2 的幂次是 $v_2(n!)=n-S_2(n).$

$O(logn)$ 实现：

int multiplicity_factorial(int n, int p) {
  int count = 0;
  do {
    n /= p;
    count += n;
  } while (n);
  return count;
}

3 $Kummer$ 定理:

$p$ 在组合数 $\dbinom{m}{n}$ 中的幂次，恰好是 $p$ 进制下 $m$ 减掉 $n$ 需要借位的次数。

即 $v_p\left(\dbinom{m}{n}\right)=\frac{S_p(n)+S_p(m-n)-S_p(m)}{p-1}$

特别地，组合数中 2 的幂次是 $v_2\left(\dbinom{m}{n}\right)=S_2(n)+S_2(m-n)-S_2(m).$

4 $Wilson$ 定理的推广:

对于素数 $p$和正整数 $q$ 有 $(p^q!)_p\equiv \pm 1\pmod{p^q}.$

\[(p^q!)_p\equiv \begin{cases} 1, & (p=2) \land (q\geq 3),\\ -1, & \text{otherwise}. \end{cases}\]

FXJFXJ

威尔逊定理

1 威尔逊定理

2 \(Legendre\) 公式:

3 \(Kummer\) 定理:

4 \(Wilson\) 定理的推广: