ما معنى العدد الأولي؟

مثال 6.24 (عكس مبرهنة فيرما يخفق: العدد $341$)

تعطي مبرهنة فيرما الصغرى اختبارَ تركيبٍ رخيصًا: فإذا كان $a^{n-1} \not\equiv 1 \pmod n$ من أجل $a$ ما أوليّ مع $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)، حتى في المبرهنات.