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

作者: M_lear | 来源:发表于2019-02-03 12:00 被阅读0次

数论四大定理之威尔逊定理
数论四大定理
Python解中国剩余定理（孙子定理）
数论四大定理之欧拉定理
LUCAS（数论定理）
2019-04-09
产品经理数学课（3）
2020-01-22（学习笔记附录）
自学Python:验证四方定理
代数数论：孙子定理

威尔逊定理

p 为质数 $\Longleftrightarrow(p-1)!\equiv -1(\mod p)$

证明：

必要性：
$(p-1)!\equiv -1(\mod p)\Longleftrightarrow p|(p-1)!+1$
假设 p 不是质数，且 a 是 p 的质因子。
易知 $a|(p-1)!$ ，则 $a\nmid(p-1)!+1$
$而p|(p-1)!+1\Longrightarrow a|(p-1)!+1$ ，前后矛盾！
故 p 一定为质数。
充分性：
$当 p = 2 时$ ， $(p-1)!\equiv -1(\mod p)$ 显然成立。
$当 p = 3 时$ ， $(p-1)!\equiv -1(\mod p)$ 显然成立。
$当p\ge5时$ ，令 $M=\{2,3,\cdots,p-2\},N=\{1,2,\cdots,p-1\}$ $\forall a\in M$ ，令 $S=a\cdot N=\{a,2a,\cdots,(p-1)a\}$ $注意\forall t\in S,p\nmid t$
$\therefore\forall t_1,t_2\in S,t_1<t_2\Longrightarrow t_2-t_1\in S\Longrightarrow p\nmid(t_2-t_1)$
$根据同余的定义可知，S中所有元素模p都不同余$
$\therefore S\mod p=N$
也就是说 $\forall a\in M,\exists x\in N$ ，一定有 $ax\equiv1(\mod p)$
$若x=1，则ax\%p=a\%p=a,\therefore x\ne1$
$若x=p-1$ ，则
$ax\%p=(ap-a)\%p=[(a-1)p+p-a]\%p=p-a,\therefore x\ne p-1$
$若x=a$ ，则
$a^2\equiv1(\mod p)\Longrightarrow(a+1)(a-1)\equiv0(\mod p)$ $\Longrightarrow a=1或a=p-1\therefore x\ne a$
综上所述， $\forall a\in M,\exists x\in M,且a\ne x,有ax\equiv1(\mod p)$
所以 $(p-1)!\equiv1\cdot(p-1)\equiv-1(\mod p)$

证毕！

数论四大定理之威尔逊定理
威尔逊定理 p 为质数证明：必要性：假设 p 不是质数，且 a 是 p 的质因子。易知，则，前后矛盾！故 p ...
数论四大定理
威尔逊定理、欧拉定理、孙子定理、费马小定理
Python解中国剩余定理（孙子定理）
中国剩余定理（Chinese Remainder Theorem，CRT）又称孙子定理，是数论中的一个定理。古典数...
数论四大定理之欧拉定理
本文分为两个部分，第一部分介绍欧拉定理的证明，第二部分介绍欧拉函数的求法。欧拉函数欧拉函数是小于等于 n 的正...
LUCAS（数论定理）
2019-04-09
今日打卡 1、收获今天第一节课是初等数论。今天我们讲的是小费马定理和大费马定理。一开始我们对这些理定理，不是非常...
产品经理数学课（3）
关键词：剩余，同余定理，数论，hash 参考：杨迎球，中国剩余定理与同余式组，[D]安顺学院数学与计算机科学系，2...
2020-01-22（学习笔记附录）
数论概论同余式、幂与费马小定理费马小定理：p为质数，a除以p不为0，则a^(p-1) 除以p余1 欧拉公式：若...
自学Python:验证四方定理
四方定理是什么？ “四方定理”是数论中著名的一个定理，指所有自然数至多只要用四个数的平方和就可以表示。例如：99...
代数数论：孙子定理
学一点新东西中国剩余定理也就是同余方程组的可解性问题，这个问题是很有实践意义的。去超市买了一些鸡蛋，只记得不超...