カーマイケル数
カーマイケル数 n は、その全ての素因子 p に対して p − 1 が n − 1 を割り切るという特徴を持つ。例えば2821を例に取ると、
2821 = 7 × 13 × 31
2821 − 1 = 2820 = (7 − 1) × 470 = (13 − 1) × 235 = (31 − 1) × 94
である。逆に、この性質を持ち、平方因子を持たない合成数はカーマイケル数である。カーマイケル数は、少なくとも3個以上の異なる素数の積である。
フェルマーテストでは確率的素数と誤判定されるカーマイケル数であるが、フェルマーテストの改善版であるミラー-ラビン素数判定法では、ひとつの底に対する誤判定の確率は 1/4 以下となる。