威爾遜定理

內容

Wilson 定理

對於素數 \(p\) 有 \((p-1)!\equiv -1\pmod p\).

證明

我們可以利用同餘方程或原根得到兩種簡潔的證明，此處略去不表。

我們選擇介紹前置知識較少的一種證明方法：

當 \(p=2\) 時，命題顯然成立。

以下設 \(p\geq 3\)，此時我們要證 \(\mathbf{Z}_p\) 中所有非零元素的積為 \(\overline{-1}\).

我們知道 \(\mathbf{Z}_p\) 中所有非零元素 \(a\) 都有逆元 \(a^{-1}\)，於是 \(\mathbf{Z}_p\) 中彼此互逆的元素乘積為 \(\overline{1}\).

但是要注意 \(a\) 和 \(a^{-1}\) 可能相等。若 \(a=a^{-1}\)，則 \(a^2\equiv 1\pmod p\)，即

\[ 0\equiv a^2-1\equiv (a+1)(a-1)\pmod p \]

從而 \(a\equiv 1\pmod p\) 或 \(a\equiv -1\pmod p\).

這説明 \(\mathbf{Z}_p\setminus\{\overline{0},\overline{1},\overline{-1}\}\) 中所有元素的乘積為 \(\overline{1}\), 進而 \(\mathbf{Z}_p\) 中所有非零元素的積為 \(\overline{-1}\).

對於整數 \(n\)，令 \((n!)_p\) 表示所有小於等於 \(n\) 但不能被 \(p\) 整除的正整數的乘積，即 \((n!)_p=n!/(\lfloor n/p\rfloor !p^{\lfloor n/p\rfloor})\).

Wilson 定理指出 \((p!)_p=(p-1)!\equiv -1\pmod p\) 且可被推廣至模素數 \(p\) 的冪次。

應用

階乘與素數

在某些情況下，有必要考慮以某個素數 \(p\) 為模的公式，包含分子和分母中的階乘，就像在二項式係數公式中遇到的那樣。

只有當階乘同時出現在分數的分子和分母中時，這個問題才有意義。否則，後續項 \(p!\) 將減少為零。但在分數中，因子 \(p\) 可以抵消，結果將是非零。

因此，要計算 \(n! \bmod p\)，而不考慮階乘中出現因數 \(p\)。寫下素因子分解，去掉所有因子 \(p\)，並計算乘積模。

用 \((n!)_p\) 表示這個修改的因子。例如：

\[ (7!)_p \equiv 1 \cdot 2 \cdot \underbrace{1}_{3} \cdot 4 \cdot 5 \underbrace{2}_{6} \cdot 7 \equiv 2 \bmod 3 \]

這種修正的階乘，可用於快速計算各種帶取模和組合數的公式的值。

計算餘數的算法

計算上述去掉因子 \(p\) 的階乘模 \(p\) 的餘數。

\[ \begin{aligned} (n!)_p &= 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot (p+1) \cdot (p+2) \cdot \ldots \cdot (2p-1) \cdot \underbrace{2}_{2p} \\\ &\quad \cdot (2p+1) \cdot \ldots \cdot (p^2-1) \cdot \underbrace{1}_{p^2} \cdot (p^2 +1) \cdot \ldots \cdot n \pmod{p} \\\\ &= 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot 1 \cdot 2 \cdot \ldots \cdot (p-1) \cdot \underbrace{2}_{2p} \cdot 1 \cdot 2 \\\ &\quad \cdot \ldots \cdot (p-1) \cdot \underbrace{1}_{p^2} \cdot 1 \cdot 2 \cdot \ldots \cdot (n \bmod p) \pmod{p} \end{aligned} \]

可以清楚地看到，除了最後一個塊外，階乘被劃分為幾個長度相同的塊。

\[ \begin{aligned} (n!)_p&= \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{1\text{st}} \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 2}_{2\text{nd}} \cdot \ldots \\\\ & \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{p\text{th}} \cdot \ldots \cdot \quad \underbrace{1 \cdot 2 \cdot \cdot \ldots \cdot (n \bmod p)}_{\text{tail}} \pmod{p}. \end{aligned} \]

塊的主要部分 \((p-1)!\ \mathrm{mod}\ p\) 很容易計算，可以應用 Wilson 定理：

\[ (p-1)!\equiv -1\pmod p \]

總共有 \(\lfloor \frac{n}{p} \rfloor\) 個塊，因此需要將 \(\lfloor \frac{n}{p} \rfloor\) 寫到 \(-1\) 的指數上。可以注意到結果在 \(-1\) 和 \(1\) 之間切換，因此只需要查看指數的奇偶性，如果是奇數，則乘以 \(-1\)。除了使用乘法，也可以從結果中減去 \(p\).

最後一個部分塊的值可以在 \(O(p)\) 的時間複雜度單獨計算。

這隻留下每個塊的最後一個元素。如果隱藏已處理的元素，可以看到以下模式：

\[ (n!)_p = \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 2} \cdot \ldots \cdot \underbrace{ \ldots \cdot (p-1)} \cdot \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 1} \cdot \underbrace{ \ldots \cdot 2} \cdots \]

這也是一個修正的階乘，只是維數小得多。它是：

\[ \left(\left\lfloor \frac{n}{p} \right\rfloor !\right)_p \]

因此，在計算修改的階乘 \((n!)_p\) 中，執行了 \(O(p)\) 個操作，剩下的是計算 \((\lfloor \frac{n}{p} \rfloor !)_p\)，於是有了遞歸，遞歸深度為 \(O(\log_p n)\)，因此算法的總時間複雜度為 \(O(p \log_p n)\).

如果預先計算階乘 \(0!, 1!, 2!, \dots, (p-1)!\) 模 \(p\)，那麼時間複雜度為 \(O(\log_p n)\).

計算餘數算法的實現

具體實現不需要遞歸，因為這是尾部遞歸的情況，因此可以使用迭代輕鬆實現。在下面的實現中預計算了階乘 \(0!, 1!, \dots, (p-1)!\).

因此時間複雜度為 \(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;
}

如果空間有限，無法存儲所有階乘，也可以只存儲需要的階乘，對它們進行排序，然後計算階乘 \(0!,~ 1!,~ 2!,~ \dots,~ (p-1)!\) 而不顯式存儲它們。

Legendre 公式

如果想計算二項式係數模 \(p\)，那麼還需要考慮在 \(n\) 的階乘的素因子分解中 \(p\) 出現的次數，或在計算修改因子時刪除因子 \(p\) 的個數。

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)\)

證明

將 \(n!\) 記為 \(1\times 2\times \cdots \times p\times \cdots \times 2p\times \cdots \times \lfloor n/p\rfloor p\times \cdots \times n\) 那麼其中 \(p\) 的倍數有 \(p\times 2p\times \cdots \times \lfloor n/p\rfloor p=p^{\lfloor n/p\rfloor }\lfloor n/p\rfloor !\) 然後在 \(\lfloor n/p\rfloor !\) 中繼續尋找 \(p\) 的倍數即可，這是一個遞歸的過程。

第二個等號與等比數列求和公式很相似。由於涉及各位數字和，利用數學歸納法可以輕鬆證明。

實現

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

時間複雜度 \(O(\log n)\)

以下記 \(\nu(n!)=\sum_{j\geq 1}\lfloor n/p^j\rfloor\).

Kummer 定理

組合數對一個數取模的結果，往往構成分形結構，例如謝爾賓斯基三角形就可以通過組合數模 2 得到。

如果仔細分析，\(p\) 是否整除組合數其實和上下標在 \(p\) 進制下減法是否需要借位有關。這就有了 Kummer 定理。

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)\).

Wilson 定理的推廣

對於素數 \(p\) 和正整數 \(q\) 有 \((p^q!)_p\equiv \pm 1\pmod{p^q}\).

證明

依然考慮配對一個數與其逆元，也就是考慮關於 \(m\) 的同餘方程 \(m^2\equiv 1\pmod{p^q}\) 的根的乘積，當 \(p^q=2\) 時方程僅有一根，當 \(p=2\) 且 \(q\geq 3\) 時有四根為 \(\pm 1,2^{q-1}\pm 1\) 其他時候則有兩根為 \(\pm 1\).

至此我們對 Wilson 定理的推廣中的 \(\pm 1\) 有了詳細的定義，即

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

下文兩個推論中的 \(\pm 1\)，均特指這樣的定義：當模數 \(p^q\) 取 \(8\) 及以上的 \(2\) 的冪時取 \(1\)，其餘取 \(-1\).

推論 1

對於素數 \(p\)、正整數 \(q\)、非負整數 \(n\) 和 \(N_0=n\bmod{p^q}\) 有

\[ (n!)_p\equiv (\pm 1)^{\lfloor n/{p^q}\rfloor}(N_0!)_p\pmod{p^q} \]

證明

令 \(\displaystyle \prod '\) 表示不能被 \(p\) 整除的數的乘積，有

\[ \begin{aligned} (n!)_p&=\prod_{1\leq r\leq n}'r\\ &=\left(\prod_{i=0}^{\lfloor n/p^q \rfloor -1}\prod_{1\leq j\leq p^q}'(ip^q+j)\right)\left(\prod_{1\leq j\leq N_0}'(\lfloor n/p^q\rfloor p^q+j)\right)\\ &\equiv ((p^q!)_p)^{\lfloor n/p^q\rfloor}(N_0!)_p\\ &\equiv (\pm 1)^{\lfloor n/p^q\rfloor}(N_0!)_p\pmod{p^q} \end{aligned} \]

將 \(1\times 2\times 3\times \cdots \times n\) 記為 \((0\times p^q+1)\times (0\times p^q+2)\times \cdots \times (\lfloor n/p^q\rfloor p^q+N_0)\) 就得到了上述第二行。

至此得到了：

推論 2

對於素數 \(p\) 和正整數 \(q\) 和非負整數 \(n\) 有

\[ \frac{n!}{p^{\sum_{j\geq 1}\lfloor \frac{n}{p^j}\rfloor}}\equiv (\pm 1)^{\sum_{j\geq q}\lfloor \frac{n}{p^j}\rfloor}\prod_{j\geq 0}(N_j!)_p\pmod{p^q} \]

其中 \(N_j=\lfloor n/p^j\rfloor \bmod{p^q}\) 而 \(\pm 1\) 與上述相同。

記 \(r=n-m\) 且 \(n > m\) 有

\[ \frac{(\pm 1)^{\sum_{j\geq q}\left(\lfloor n/p^j\rfloor -\lfloor m/p^j\rfloor -\lfloor r/p^j\rfloor\right)}}{p^{\nu(n!)-\nu(m!)-\nu(r!)}}\binom{n}{m}\equiv \frac{n!/p^{\nu(n!)}}{(m!/p^{\nu(m!)})(r!/p^{\nu(r!)})}\pmod{p^q} \]

右邊的分母中括號內的項均在模 \(p^q\) 意義下均存在逆元，可直接計算，而 \(\pm 1\) 的與上述相同。

例題

例題 HDU 2973 - YAPTCHA

給定 \(n\), 計算

\[ \sum_{k=1}^n\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor \]

解題思路

若 \(3k+7\) 是質數，則

\[ (3k+6)!\equiv-1\pmod{3k+7} \]

設 \((3k+6)!+1=k(3k+7)\)

則

\[ \left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor=\left\lfloor k-\left\lfloor k-\frac{1}{3k+7}\right\rfloor\right\rfloor=1 \]

若 \(3k+7\) 不是質數，則有 \((3k+7)\mid(3k+6)!\)，即

\[ (3k+6)!\equiv 0\pmod{3k+7} \]

設 \((3k+6)!=k(3k+7)\)，則

\[ \left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor=\left\lfloor k+\frac{1}{3k+7}-k\right\rfloor=0 \]

因此

\[ \sum_{k=1}^n\left\lfloor\frac{(3k+6)!+1}{3k+7}-\left\lfloor\frac{(3k+6)!}{3k+7}\right\rfloor\right\rfloor=\sum_{k=1}^n[3k+7\text{ is prime}] \]

參考代碼

#include <iostream>

const int M = 1e6 + 5, N = 3 * M + 7;

bool not_prime[N];
int sum[M];

int main() {
  for (int i = 2; i < N; ++i)
    if (!not_prime[i])
      for (int j = 2; j * i < N; ++j) not_prime[j * i] = 1;
  for (int i = 1; i < M; ++i) sum[i] = sum[i - 1] + !not_prime[3 * i + 7];

  int t;
  std::cin >> t;
  while (t--) {
    int n;
    std::cin >> n;
    std::cout << sum[n] << std::endl;
  }
}

本頁面主要譯自博文 Вычисление факториала по модулю 與其英文翻譯版 Factorial modulo p。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

參考資料

馮克勤。初等數論及其應用。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用