Gli antichi cinesi erano convinti che un intero n sia primo se e solo se

Ci si rese conto solo nel '700 che questo non è vero. Il più piccolo controesempio è  341 = 11^.31 . Per trovare un altro controesempio bisogna arrivare a  561 = 3^.11^.17 .
I numeri che superano il test "cinese" ma non sono primi si chiamano pseudoprimi; ce ne sono infiniti.
La condizione è però necessaria perchè n sia primo. Un famoso risultato di teoria dei numeri, scoperto da Fermat intorno al 1640, dice infatti:

Ci si può chiedere se la tesi del teorema di Fermat caratterizzi i primi, cioè se tutti i numeri q tali che  sia divisibile per q per ogni intero a siano primi. Purtroppo questo è falso; un controesempio è 561.