برهان لا نهائية الأعداد الأولية: لماذا قد يكون حاصل الضرب زائد1 مركبًا؟

برهان بقائمة منتهية

الأولي عدد صحيح أكبر من1 لا قواسم موجبة له غير1 ونفسه. أما المركب، فهو عدد صحيح أكبر من1 يقبل قاسمًا موجبًا آخر. [3]

نضرب عناصر قائمة أوليات منتهية غير فارغة فنحصل على P، ثم نضع N=P+1؛ الباقي1 مع كل عنصر. [1]

إذا كان N أوليًا فهو جديد. وإلا فله عامل أولي q؛ دخوله القائمة يجعله يقسم N−P=1، وهو مستحيل لأن q>1. [1][2]

لا تكتمل أي قائمة منتهية، ولا يلزم أن يكون N أوليًا. [1]

نتيجتان:31 و30031

نبدأ بالقائمة2،3،5. حاصل الضرب30، فيكون N=31. لا يقبل31 القسمة على2 أو3 أو5؛ وسنوضح حد الفحص في القسم التالي. هنا حصلنا على أولي خارج القائمة.

لكن31 ليس الأولي التالي بعد5. العدد7 أصغر منه وأكبر من5، ولا يقبل القسمة على2؛ لذلك هو أولي. بناء عدد جديد لا يعني إنتاج العدد التالي مباشرة.

نوسع القائمة إلى2،3،5،7،11،13. نحسب2×3×5×7×11×13=30030، ثم نضيف1 فنحصل على30031.

هذا الناتج مركب:59×509=59×(500+9)=29500+531=30031. كلا العاملين خارج القائمة الأصلية. لا يصح أن نعلن أولية30031 لمجرد أن القسمة على العناصر الستة تركت الباقي1.

نتحقق من البواقي دون تقريب:30031=2×15015+1=3×10010+1=5×6006+1=7×4290+1=11×2730+1=13×2310+1. هذه المساويات ترفض القواسم الستة، ولا ترفض جميع القواسم الممكنة.

فحص59 و509

لفهم حد الفحص، افترض أن n=ab مركب، حيث1<a≤b. عندئذ a²≤ab=n، فيكون a≤√n. ولأن a>1، فله عامل أولي لا يزيد علىa، وهو يقسم n أيضًا. وجود العامل الأولي تدعمه النتيجة VII.31. [2]

للعدد59، نجد7²=49<59<64=8². الأعداد الأولية التي لا تتجاوز جذره هي2،3،5،7. البواقي بالترتيب1،2،4،3؛ فلا يقسمه أي منها، ويكون59 أوليًا.

للعدد509، نجد22²=484<509<529=23². نختبر2،3،5،7،11،13،17،19. البواقي بالترتيب1،2،4،5،3،2،16،15؛ كلها غير صفرية، فيكون509 أوليًا.

يمكن التأكد من اكتمال قائمة الفحص حتى22: الأولية هي2،3،5،7،11،13،17،19. الأعداد الأخرى من2 إلى22 مركبة بعامل2 أو3 أو5 أو7. لا نختبر1، فهو يقسم كل عدد ولا يميز الأولية.

وللعدد31، نجد5²<31<6². قائمة الفحص2،3،5 كاملة تحت الجذر، وبواقيها1،1،1. لذلك كان إعلان أوليته في المثال الصغير صحيحًا، بخلاف الاكتفاء بالأعداد الستة لفحص30031.

أولي أصغر خارج القائمة

قد تكون القائمة مجرد مجموعة مختارة، لا جميع الأوليات حتى حد معين. نأخذ5 و11 وحدهما: P=55 وN=56=8×7=2³×7. العامل الأولي2 ليس في القائمة، لكنه أصغر من5 و11.

قسمة56 على5 تترك1، وعلى11 تترك1. فوجود عامل صغير غائب لا يناقض خطوة الباقي. لو كانت القائمة تحتوي جميع الأوليات حتى13 كما في المثال السابق، فإن أي أولي خارجها يتجاوز13؛ هذا استنتاج من اكتمال تلك القائمة حتى13، لا من كون N كبيرًا.

فرّق بين ثلاث مسائل: إثبات وجود أولي خارج قائمة، وفحص أولية عدد معين، وإيجاد الأولي التالي بعد عدد معين. تحقق الأولى لا ينجز الأخريين. المثال31 يرفض وعد «التالي»، والمثال30031 يرفض وعد «أولي دائمًا».

الأعداد هنا صحيحة موجبة، والعمليات دقيقة؛ لا نتعامل مع بواقي عشرية أو قياسات تقريبية. إن كتبت قائمة أوليات، راجع أولية عناصرها؛ ثم سجّل حاصل الضرب والزيادة والتحليل الذي وجدته، بدل تحويل رسم كبير إلى دليل على أولية الناتج.