費馬小定理

如果 是一個 素數 並且 是一個 自然數，則

(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