अभाज्य संख्या কী?

उदाहरण 6.24 (फर्मा का विलोम विफल है: $341$)

फर्मा की लघु प्रमेय एक सस्ता भाज्यता परीक्षण देती है: यदि $n$ से सहअभाज्य किसी $a$ के लिए $a^{n-1} \not\equiv 1 \pmod n$, तो $n$ अभाज्य नहीं है। क्या यह परीक्षण अभाज्यता प्रमाणित भी कर सकता है? नहीं: $n = 341 = 11 \times 31$, जो भाज्य है, और $a = 2$ लीजिए। चूँकि $2^{10} = 1024 = 3 \times 341 + 1$,

भाज्य $341$ आधार $2$ के लिए फर्मा-परीक्षण पास कर जाता है (वह लघुतम ऐसा छद्म-अभाज्य है)। आधार $3$ उसका मुखौटा उतार देता है ($3^{340} \not\equiv 1$), और इसीलिए व्यावहारिक अभाज्यता-परीक्षण अनेक आधारों पर परीक्षण चलाते हैं, कुछ परिष्करणों के साथ — इसी विचार के औद्योगिक रूप ही टिप्पणी 6.27 के बड़े अभाज्यों को प्रमाणित करते हैं। उपदेश: निहितार्थ और उसका विलोम अलग-अलग जीवन जीते हैं (टिप्पणी 1.10), प्रमेयों के लिए भी।