威尔逊定理


定义

对于非负整数 p 来说,其是质数的充要条件为 $(p-1)!\equiv -1\ (\ mod\ p)$

证明

y 一定在剩余系中

$\because$ x 的逆元不可能大于 p-1 ,即 $ y \leq p-1 $

又$\because $ x 的逆元不可能是 p-1,所以 y$\in(2,p-2)$​

应用

1.寻找素数

通过威尔逊定理我们可以构造出质数分布的函数曲线(结合sin函数的性质): $f(n)=sin(\frac{π∗((n−1)!+1)}{n})$ ,当函数值为0时,就可以得出一个质数(非常鸡肋)。虽然可以用来判断是否为质数,但是由于阶乘的爆炸性增长,所以在当前计算机硬件限制下并不好用。

题目推荐

UVA1434 YAPTCHA

本题应用到 $\frac{(p-1)!+1}{p}$ 必定为整数的二级结论

特别感谢

威尔逊定理 —— 数论四大定理之一

威尔逊定理及其证明


如果本文帮助到了你,帮我点个广告可以咩(o′┏▽┓`o)


文章作者: Anubis
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Anubis !
评论
 上一篇
Syncthing+tailscale 组建私人文件同步服务 Syncthing+tailscale 组建私人文件同步服务
Syncthing 是一个开源的 P2P 文件同步工具。它可以在多个平台(Windows、Mac、Linux)上使用,并且不需要云端服务器。设备之间可以直接连接同步。本文介绍了如何在 Windows、Mac 和 Linux 系统上安装 Syncthing,以及如何配置和一些进阶技巧。Syncthing 使用 MIT 协议开源发布。
2023-04-19
下一篇 
第16周刊 第16周刊
2023-04-17 至 2023-04-17 周刊
2023-04-17
  目录