بروث برايم

عدد بروث هو عدد طبيعي N على الصورة${\displaystyle N=k\times 2^{n}+1}$حيث k و n عددان صحيحان موجبان ، و k عدد فردي و${\displaystyle 2^{n}>k}$العدد الأولي لبروث هو عدد بروث أولي . سُميت هذه الأعداد نسبةً إلى عالم الرياضيات الفرنسي فرانسوا بروث . ^{[ 2 ]} الأعداد الأولية القليلة الأولى لبروث هي

3، 5، 13، 17، 41، 97، 113، 193، 241، 257، 353، 449، 577، 641، 673، 769، 929، 1153، 1217، 1409، 1601، 2113، 2689، 2753، 3137، 3329، 3457، 4481، 4993، 6529، 7297، 7681، 7937، 9473، 9601، 9857 ( OEIS : A080076  ).

لا يزال وجود عدد لا نهائي من أعداد بروث الأولية سؤالاً مفتوحاً. وقد أُثبت في عام 2022 أن مقلوب مجموع أعداد بروث الأولية يتقارب إلى عدد حقيقي قريب من 0.747392479، وهو أقل بكثير من قيمة 1.093322456 لمقلوب مجموع أعداد بروث. ^{[ 1 ]}

يمكن اختبار أولية أعداد بروث بسهولة أكبر من العديد من الأعداد الأخرى ذات الحجم المماثل.

يأخذ رقم بروث الشكل التالي:${\displaystyle N=k\times 2^{n}+1}$حيث k و n عددان صحيحان موجبان،${\displaystyle k}$غريب و${\displaystyle 2^{n}>k}$العدد الأولي لبروث هو عدد بروثي أولي. ^{[ 2 ] [ 3 ]} بدون الشرط التالي:${\displaystyle 2^{n}>k}$جميع الأعداد الصحيحة الفردية الأكبر من 1 ستكون أعداد بروث. ^{[ 4 ]}

يمكن اختبار أولية عدد بروث باستخدام نظرية بروث ، التي تنص على أن عدد بروث${\displaystyle p}$يكون العدد أوليًا إذا وفقط إذا وُجد عدد صحيح${\displaystyle a}$والتي

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$^{[ 3 ] [ 5 ]}

يمكن استخدام هذه النظرية كاختبار احتمالي لأولية الأعداد، من خلال التحقق من العديد من الخيارات العشوائية لـ${\displaystyle a}$سواء${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}.}$ إذا لم ينجح هذا لعدة مرات عشوائية${\displaystyle a}$إذاً، فمن المرجح جداً أن يكون العدد${\displaystyle p}$هو عدد مركب . هذا الاختبار هو خوارزمية لاس فيغاس : فهو لا يُرجع أبدًا نتيجة إيجابية خاطئة ولكنه قد يُرجع نتيجة سلبية خاطئة ؛ بمعنى آخر، فهو لا يُبلغ أبدًا عن عدد مركب على أنه " أولي على الأرجح " ولكنه قد يُبلغ عن عدد أولي على أنه "محتمل أن يكون مركبًا".

في عام 2008، ابتكر سزي خوارزمية حتمية تعمل في أكثر من${\displaystyle {\tilde {O}}((k\log k+\log N)(\log N)^{2})}$الزمن، حيث Õ هو رمز O الناعم . بالنسبة لعمليات البحث النموذجية عن أعداد بروث الأولية، عادةً${\displaystyle k}$إما أن تكون ثابتة (مثل البحث عن 321 عددًا أوليًا أو مشكلة سيربينسكي) أو من رتبة${\displaystyle O(\log N)}$(مثلاً، بحث كولين عن الأعداد الأولية ). في هذه الحالات، تعمل الخوارزمية في مدة زمنية لا تتجاوز${\displaystyle {\tilde {O}}((\log N)^{3})}$، أو${\displaystyle O((\log N)^{3+\epsilon })}$وقت للجميع${\displaystyle \epsilon >0}$يوجد أيضًا خوارزمية تعمل في${\displaystyle {\tilde {O}}((\log N)^{24/7})}$الوقت. ^{[ 2 ] [ 6 ]}

أعداد فيرما هي حالة خاصة من أعداد بروث، حيث k = 1. في مثل هذه الحالة، يثبت اختبار بيبين أنه يكفي التحقق من الأساس a = 3 فقط للتحقق بشكل حتمي من أولية عدد فيرما أو نفيها.

اعتبارًا من عام 2022أكبر عدد أولي معروف في بروث هو${\displaystyle 10223\times 2^{31172165}+1}$يبلغ طوله 9,383,761 رقمًا. ^{[ 7 ]} اكتشفه بيتر سزابولكس في مشروع الحوسبة التطوعية PrimeGrid الذي أعلن عنه في 6 نوفمبر 2016. ^{[ 8 ]} وهو أيضًا ثالث أكبر عدد أولي معروف غير عدد ميرسين . ^{[ 9 ]}

مشروع "سبعة عشر أو لا شيء" ، يبحث عن أعداد أولية من نوع بروث ذات قيمة معينة.${\displaystyle t}$لإثبات أن 78557 هو أصغر عدد سيربينسكي ( مسألة سيربينسكي )، تم العثور على 11 عددًا أوليًا كبيرًا من نوع بروث بحلول عام 2007. وقد أسفرت حلول مماثلة لمسألة سيربينسكي الأولية ومسألة سيربينسكي الموسعة عن العديد من الأعداد الأخرى.

بما أن قواسم أعداد فيرما${\displaystyle F_{n}=2^{2^{n}}+1}$دائماً ما تكون على شكل${\displaystyle k\times 2^{n+2}+1}$من المعتاد تحديد ما إذا كان عدد بروث الأولي الجديد يقسم عدد فيرما. ^{[ 10 ]}

اعتبارًا من يناير 2025، يُعدّ مشروع PrimeGrid المشروع الرائد في مجال الحوسبة للبحث عن الأعداد الأولية في بروث. وتشمل مشاريعه الرئيسية ما يلي:

• بحث عام عن الأعداد الأولية في بروث
• 321 البحث عن الأعداد الأولية (البحث عن الأعداد الأولية من الشكل${\displaystyle 3\times 2^{n}+1}$(وتسمى أيضًا أعداد ثابت الأولية من النوع الثاني )
• 27121 البحث عن الأعداد الأولية (البحث عن الأعداد الأولية من الشكل${\displaystyle 27\times 2^{n}+1}$و${\displaystyle 121\times 2^{n}+1}$)
• بحث كولين عن الأعداد الأولية (البحث عن أعداد أولية من الشكل${\displaystyle n\times 2^{n}+1}$)
• مسألة سيربينسكي (وتعميماتها الأولية والموسعة) – البحث عن أعداد أولية من الشكل${\displaystyle k\times 2^{n}+1}$حيث k موجود في هذه القائمة:

k ∈ {21181, 22699, 24737, 55459, 67607, 79309, 79817, 91549, 99739, 131179, 152267, 156511, 163187, 200749, 209611, 222113, 225931, 227723, 229673, 237019, 238411}

اعتبارًا من يونيو 2023، فإن أكبر الأعداد الأولية لبروث المكتشفة هي: ^{[ 11 ]}

العدد البروثي من النوع الثاني هو عدد طبيعي N على الصورة${\displaystyle N=k\times 2^{n}-1}$حيث k و n عددان صحيحان موجبان ، و k عدد فردي و${\displaystyle 2^{n}>k}$العدد الأولي من نوع بروث الثاني هو عدد بروث من النوع الثاني يكون أوليًا . الأعداد الأولية القليلة الأولى من نوع بروث الثاني هي:

3، 7، 11، 23، 31، 47، 79، 127، 191، 223، 239، 383، 479، 607، 863، 991، 1087، 1151، 1279، 1471، 1663، 2111، 2239، 2687، 2879، 3391، 3583، 3967، 5119، 5503، 6143، 6271، 6911، 7039، 8191، 8447، 8831، 9343 ( OEIS : A112715  ).

يمكن اختبار أولية أكبر الأعداد الأولية من النوع الثاني باستخدام اختبار لوكاس-ليمر-ريزل .

اعتبارًا من يناير 2025، يُعدّ مشروع PrimeGrid المشروع الرائد في مجال الحوسبة للبحث عن أعداد بروث الأولية من النوع الثاني. وتشمل مشاريعه الرئيسية ما يلي:

• بحث عام عن عدد أولي بروث من النوع الثاني
• 321 البحث عن الأعداد الأولية (البحث عن الأعداد الأولية من الشكل${\displaystyle 3\times 2^{n}-1}$(وتسمى أيضًا أعداد ثابت الأولية )
• 27121 البحث عن الأعداد الأولية (البحث عن الأعداد الأولية من الشكل${\displaystyle 27\times 2^{n}-1}$و${\displaystyle 121\times 2^{n}-1}$)
• بحث وودال عن الأعداد الأولية (البحث عن أعداد أولية من الشكل${\displaystyle n\times 2^{n}-1}$)
• مسألة ريزل (وتعميماتها الأولية والموسعة) – البحث عن أعداد أولية من الشكل${\displaystyle k\times 2^{n}-1}$حيث k موجود في هذه القائمة:

k ∈ {23669, 31859, 38473, 46663, 67117, 74699, 81041, 121889, 129007, 143047, 161669, 206231, 215443, 226153, 234343, 245561, 250027, 315929, 319511, 324011, 325123, 327671, 336839, 342847, 344759, 362609, 363343, 364903, 365159, 368411, 371893, 384539، 386801، 397027، 409753، 444637، 470173، 474491، 477583، 485557، 494743 }

استُخدمت الأعداد الأولية الصغيرة من نوع بروث (أقل من ^{10²⁰ ) في بناء سلالم الأعداد الأولية، وهي متواليات من الأعداد الأولية بحيث يكون كل حد منها "قريبًا" (في حدود 10¹¹} تقريبًا ) من الحد السابق. وقد استُخدمت هذه السلالم للتحقق تجريبيًا من صحة التخمينات المتعلقة بالأعداد الأولية . على سبيل المثال، تم التحقق من صحة تخمين غولدباخ الضعيف في عام 2008 حتى 8.875 × 10³⁰ ^{باستخدام} سلالم الأعداد الأولية المُنشأة من أعداد بروث الأولية. ^{[ 18 ]} (وقد أثبت هارالد هيلفغوت هذا التخمين لاحقًا . ^{[ 19 ] [ 20 ]} )

كذلك، يمكن للأعداد الأولية لبروث أن تُحسّن اختزال دين بوير بين مسألة ديفي-هيلمان ومسألة اللوغاريتم المنفصل . وقد استُخدم العدد الأولي 55 × ²²⁸⁶  + 1 في هذا السياق. ^{[ 21 ]} 

نظرًا لأن الأعداد الأولية في بروث لها تمثيلات ثنائية بسيطة ، فقد تم استخدامها أيضًا في الاختزال المعياري السريع دون الحاجة إلى الحساب المسبق، على سبيل المثال من قبل مايكروسوفت . ^{[ 22 ]}