Jabarkan Jika bilangan bulat dari Teorema kecil Fermat

dan untuk bilangan prima  membagi

Teorema ini membentuk dasar untuk uji primalitas Lucas, sebuah uji primaliti.

Jika  dan  adalah bilangan coprime sehingga  habis dibagi , maka  tidak perlu bilangan prima. Jika tidak, maka  disebut (Fermat) pseudoprima ke basis .  Pseudoprime pertama ke basis 2 ditemukan pada tahun 1820 oleh Pierre Frédéric Sarrus: 341 = 11 × 31.

Bilangan  yang merupakan pseudoprime Fermat ke basis  untuk setiap bilangan  yang koprima dengan  disebut bilangan Carmichael (misalnya 561). Bergantian, bilangan  memenuhi persamaan

bisa berupa bilangan prima atau bilangan Carmichael.