如果p是素数，且a%p!=0, 那么
证明：
因为gcd(p,a)=1, 所以 lcm(p,a) = p*a
设 1<=ri < p, 那么ri * a mod p 的余数各不相同，且从1->p-1
根据模的性质，如果，
则
所以
因为
两边除去(p-1)!得
所以成立
根据这个，我们可以判断一个数不是素数。 如果不满足这个，那么就不是素数
但是不能用这个来判断一个数是不是素数，因为有不是素数的数满足这个等式。
欧拉公式， 如果gcd(a,m)==1, 则 
是欧拉函数，表示小于等于m且与m互质的数字
费马小定理是欧拉函数的特殊情况，因为如果m是素数，那么=m-1
我们想象 费马小定理是怎么证明的， 它用到了一个性质，如果
所以我们可以这样子，设
，bi代表第i个与m互素的数，
那么数列
与数列
相同，尽管他们的次序可能不同
证明：
因为
所以
，
所以数列同余于数列中的某个数
且数列的余数各不相同， 这个可参见费马小定理的证明。
所以证明得 数列与数列相同，尽管他们的次序可能不同
所以
