费马测试被称为概率性素性测试，它判断的是“某个数是素数的概率大不大”。在讲解费马测试之前，我们先来学习基础知识——素数的性质。首先来看一看素数5 有什么样的性质。

对于比5 小的数，分别计算它们的5 次方，结果如上图所示。

接下来，再对结果分别进行mod 运算，求得它们除以5 后的余数，结果如上图所示。

观察原本的数和余数，发现两者一致。

由此，可以推导出关于素数5，以上公式成立。
【费马小定理】
实际上不只是5，对于任意素数p，上面的公式都是成立的。这就是“费马小定理”。根据是否满足费马小定理来判断一个数是否为素数的方法就是“费马测试”。

【样例】
那么，我们就用费马测试来判断一下 $113$ 是否为素数吧。
随机选择 $3$ 个比 $113$ 小的数作为 $n$，计算这些数的 $113$ 次方，再用 $113$ 去除得到的结果，求出余数。$3$ 个数最后得到的余数都和原本的数相同，因此可以判断 $113$ 是素数。

确认 $n$ 和余数一致的次数越多，需要判断的数确实为素数的可能性就越大。但是，如果每一个小于 $p$ 的数都要去计算，就会非常耗费时间。实际上，如果确认了几组 $n$ 和余数之后就能判断该数是素数的可能性非常高，那么大致就可以判定该数是素数了。