素数の判定

定义判断

$1000000007\not\equiv 0(mod$ $2)$
$1000000007\not\equiv 0(mod$ $3)$
$1000000007\not\equiv 0(mod$ $5)$
$1000000007\not\equiv 0(mod$ $7)$

$\vdots$

$1000000007\not\equiv 0(mod$ $31607)$

所以 $1000000007$ 是素数

费马小定理逆用

费马小定理: $a^p\equiv a(mod$ $p),p$ 是素数 $,a$ 是整数

$2^{1000000007}\equiv 2(mod$ $1000000007)$
$3^{1000000007}\equiv 3(mod$ $1000000007)$
$4^{1000000007}\equiv 4(mod$ $1000000007)$
$5^{1000000007}\equiv 5(mod$ $1000000007)$

$\vdots$
$1000000006^{1000000007}\equiv 1000000006(mod$ $1000000007)$

所以 $1000000007$ 是素数的概率非常大(上述式子是必要不充分条件)

威尔逊定理(我愿称之为最强)

威尔逊定理: 当且仅当 $p$ 为素数时 $(p-1)!\equiv -1(mod$ $p)$

当且仅当！充要条件！亦可赛艇！

$1000000006!\equiv -1(mod$ $1000000007)$

所以 $1000000007$ 是素数

素数の判定

原文：https://www.cnblogs.com/zhangshaojia/p/14729643.html