费马小定理

如果 是一个 素数 并且 是一个 自然数，则

(1)

此外，如果 ( 不整除 )，则存在一些最小的指数 使得

(2)

并且 整除 。 因此，

(3)

该定理有时也简称为“费马定理”（Hardy 和 Wright 1979，第 63 页）。

这是 中国猜想 的推广和 欧拉定理 的特例。 它有时被称为费马素性检验，是素性的 必要 但非 充分 条件。 虽然费马可能已经证明了它（但未公开），但第一个证明是由欧拉在 1749 年发表的。 目前尚不清楚“费马小定理”这个术语何时首次被用于描述该定理，但 Hensel (1913) 在一本德语教科书中使用了它，并且出现在 Mac Lane (1940) 和 Kaplansky (1945) 的著作中。

该定理很容易通过对 进行数学 归纳 证明。 假设 （即， 整除 ）。 然后检查

(4)

根据 二项式定理，

(5)

改写为，

(6)

但是 整除右边，所以它也整除左边。 结合归纳假设，得到 整除总和

(7)

如假设，因此该假设对于任何 都成立。 该定理有时被称为费马简单定理。威尔逊定理 是费马小定理的 推论。

费马小定理表明，如果 是 素数，则不存在一个基数 ，其中 使得 对模 具有非零余数。 如果存在这样的基数 ，则可以保证 是合数。 然而，费马小定理中非零余数的缺乏并不能保证 是 素数。 明确地证明合数，同时通过一些 素数 的性质使得费马小定理成为一个 合数性检验，有时称为 费马合数性检验。 对于某些非平凡基数满足费马小定理并且未知为合数的数称为 可能素数。

合数 被称为 费马伪素数（或有时简称为“伪素数”），对于某些 s 具有零余数，因此未被识别为合数。 更糟糕的是，存在被称为 卡迈克尔数 的数字（其中最小的是 561），对于任何选择与 互质 的基数 都给出零余数。 然而，费马小定理的逆定理 提供了一个证明数字素性的标准。 下表列出了前 100 个基数 的最小 伪素数 （OEIS A007535；Beiler 1966，第 42 页，勘误已更正）。

2	341	22	69	42	205	62	63	82	91
3	91	23	33	43	77	63	341	83	105
4	15	24	25	44	45	64	65	84	85
5	124	25	28	45	76	65	112	85	129
6	35	26	27	46	133	66	91	86	87
7	25	27	65	47	65	67	85	87	91
8	9	28	45	48	49	68	69	88	91
9	28	29	35	49	66	69	85	89	99
10	33	30	49	50	51	70	169	90	91
11	15	31	49	51	65	71	105	91	115
12	65	32	33	52	85	72	85	92	93
13	21	33	85	53	65	73	111	93	301
14	15	34	35	54	55	74	75	94	95
15	341	35	51	55	63	75	91	95	141
16	51	36	91	56	57	76	77	96	133
17	45	37	45	57	65	77	247	97	105
18	25	38	39	58	133	78	341	98	99
19	45	39	95	59	87	79	91	99	145
20	21	40	91	60	341	80	81	100	153
21	55	41	105	61	91	81	85