威尔逊定理

Wilson 定理

内容

对于素数 有 。

证明：我们知道在模奇素数 意义下， 都存在逆元且唯一，那么只需要将一个数与其逆元配对发现其乘积均为（同余意义下），但前提是这个数的逆元不等于自身。那么很显然 就是逆元等于其自身的数的乘积，这两个数为 。在 为 时单独讨论即可。

对于整数 ，令 表示所有小于等于 但不能被 整除的正整数的乘积，即 。

Wilson 定理指出 且可被推广至模素数 的幂次。

推论

对于素数 和正整数 有 。

依然考虑配对一个数与其逆元，也就是考虑关于 的同余方程 的根的乘积，当 时方程仅有一根，当 且 时有四根为 其他时候则有两根为 。

至此我们对 Wilson 定理的推广中的 有了详细的定义即

下文两个推论中的 ，均特指这样的定义：当模数 取 及以上的 的幂时取 ，其余取 。

推论 1

对于素数 、正整数 、非负整数 和 有 。

证明：令 表示不能被 整除的数的乘积，有

将 记为 就得到了上述第二行。

至此得到了

推论 2

对于素数 和正整数 和非负整数 有

其中 而 与上述相同。

记 且 有

右边的分母中括号内的项均在模 意义下均存在逆元，可直接计算，而 的与上述相同。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#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;
  }
}

build本页面最近更新：2022/6/12 11:34:34，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Early0v0, Enter-tainer, Great-designer, Tiphereth-A
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论