نظرية بروث

في نظرية الأعداد ، تُعدّ نظرية بروث أساسًا لاختبار أولية أعداد بروث، المعروف باسم اختبار بروث . أعداد بروث، التي تُسمى أحيانًا أعداد بروث من النوع الأول ، هي الأعداد الصحيحة p التي تأخذ الشكل p = k²/ ( ²ⁿ + 1) حيث k عدد فردي ، و k < ²ⁿ . للاطلاع على أعداد بروث من النوع الثاني ، انظر موضوع أعداد ريزل . سُميت النظرية أيضًا نسبةً إلى عالم الرياضيات الفرنسي فرانسوا بروث ، الذي نشرها لأول مرة.

تنص النظرية ^{[ 1 ] [ 2 ]} على أنه لأي عدد بروث (من النوع الأول)، p ، فإن p يكون أوليًا إذا وُجد عدد صحيح a بحيث يعطي معيار أويلر -1، أي

${\displaystyle a^{\frac {p-1}{2}}\equiv -1{\pmod {p}}}$.

في هذه الحالة، يُطلق على p اسم عدد أولي بروثي .

يكفي إيجاد قيمة واحدة فقط لـ a لتأكيد أولية العدد بشكل قاطع، بشرط أن يكون p عددًا بروثيًا. والتحقق من أن p عدد بروثي أمرٌ بديهي.

هذا اختبار عملي، لأنه إذا كان p عددًا أوليًا، فإن أي قيمة مختارة لـ a لديها فرصة نجاح بنسبة 50% تقريبًا، وإذا لم يكن p عددًا أوليًا، فلن تنجح أي قيمة مختارة لـ a . علاوة على ذلك، بما أن الحساب يتم بتردد p ، فلا يجب النظر إلا في قيم a الأصغر من p .

من أمثلة هذه النظرية ما يلي:

• بالنسبة لـ p = 3 = 1(2 ¹ ) + 1، لدينا أن 2 ^(3−1)/2 + 1 = 3 يقبل القسمة على 3، لذا فإن 3 عدد أولي.
• بالنسبة لـ p = 5 = 1(2 ² ) + 1، لدينا أن 3 ^(5−1)/2 + 1 = 10 يقبل القسمة على 5، لذا فإن 5 عدد أولي.
• بالنسبة لـ p = 13 = 3(2 ² ) + 1، لدينا أن 5 ^(13−1)/2 + 1 = 15626 يقبل القسمة على 13، لذا فإن 13 عدد أولي.
• بالنسبة لـ p = 9، وهو ليس عددًا أوليًا، لا يوجد a بحيث يكون a ^(9−1)/2 + 1 قابلاً للقسمة على 9.

يمكن التحقق بشكل حتمي من أن p = 9 ليس عددًا أوليًا بالتأكد من عدم وجود قيمة لـ a (بمعدل 9). ويمكن القيام بذلك من خلال فحص كل قيمة لـ a من 2 إلى 8 بشكل منهجي (حيث أن a = 0 و a = 1 لن يكونا صحيحين أبدًا لأي قيمة لـ p ). ومع ذلك، يكفي فحص القيم من 2 إلى 5، أي نصف جميع القيم الممكنة الأقل من 9. إذا كان 9 عددًا أوليًا، فبحسب مبدأ التوزيع، ستؤكد إحدى هذه القيم على الأقل أولية العدد، إذ من المتوقع أن يؤكد نصفها ذلك.

بدلاً من ذلك، إذا استخدمنا الصيغة الحتمية التي يتم فيها حساب الباقي التربيعي مباشرة، فإن العمل يتطلب عددًا أقل من التكرارات لتأكيد كل من التركيبية والأولوية:

• بالنسبة لـ p = 97 = 3(2 ⁵ ) + 1، لدينا باقي تربيعي a = 5، و 5 ^(97−1)/2 + 1 = 3552713678800500929355621337890626 يقبل القسمة على 97، لذا فإن 97 عدد أولي.
• بالنسبة لـ p = 1537 = 3(2 ⁹ ) + 1، لدينا باقي تربيعي a = 5، و 5 ^(1537−1)/2 + 1 = 1052 (mod 1537) لا يقبل القسمة على 1537، لذا فإن 1537=29×53 ليس عددًا أوليًا.

في المثالين السابقين، حُسبت قيمة مناسبة لـ a مباشرةً باستخدام حساب الباقي التربيعي، بحيث تكون نتائج الاختبار قاطعة - أي باقي تربيعي صالح في كلتا حالتي العدد الأولي والمركب. لم يكن من الضروري البحث بشكل منهجي عن قيمة a للتحقق من حالة العدد الأولي، أو تكرار الاختبار عددًا كافيًا من المرات للحالة المركبة. إذا تعذر العثور على باقي تربيعي، أو إذا لم يكن موجودًا أصلًا، فيمكننا اعتبار ذلك تأكيدًا على كون العدد مركبًا.

يُقدّم معيار أويلر رؤى إضافية حول العدد p ، وهي ليست بالضرورة من مكونات نظرية بروث. هذه حقائق ثانوية تُعزى في الغالب إلى نظريات أخرى، ويتم تقييمها بسهولة عند تطبيق اختبار بروث. لا يشترط أن يكون العدد p عددًا من أعداد بروث حتى يكون المعيار مفيدًا. لنفترض أن لدينا عددًا صحيحًا p ، ولنختر قيمة عشوائية لـ a . احسب معيار أويلر:

${\displaystyle a^{\frac {p-1}{2}}\equiv b{\pmod {p}}.}$

توجد عموماً خمس نتائج متميزة. بعض هذه النتائج لا يعتمد على كون p عدداً من نوع بروث، وبالتالي فهي صالحة لأي شكل من أشكال الأعداد الأولية المرشحة.

أولية العدد p :

• b = −1، وفي هذه الحالة يتم استيفاء معيار بروث ويتم تأكيد أن p هو عدد أولي بروثي، وفقًا لنظرية بروث، إذا كان p بالفعل عددًا بروثيًا.

إذا لم يكن p عددًا من أعداد بروث، وكان b = −1، فإن هذا يُشير إلى أولية العدد، ولكنه ليس دليلًا قاطعًا عليها. راجع اختبار سولوفاي-ستراسن الاحتمالي لأولية العدد واختبار ميلر-رابين .

نتيجة غير حاسمة:

• b = 1، وفي هذه الحالة يكون الاختبار غير حاسم ويجب إعادة المحاولة بقيمة a جديدة .

هذا الشرط هو ما يتطلب التكرار ويجعل الاختبار احتماليًا، كما لو كان p عددًا أوليًا، فإن b = ±1 يحدث باحتمالية متساوية تقريبًا، على الرغم من أنه لا يزال من الممكن استيفاء شرط b = 1 مع p سواء كان عددًا مركبًا أو غير بروثي.

This is true unless a happens to also be a quadratic nonresidue of a Proth number p, in which case compositeness is indicated.

Compositeness of p, as per Euler's criterion and the Legendre symbol, which offer early exit conditions when b ≠ ±1. In each of these cases p is not prime and also need not be a Proth number:

• b² = 1, with nontrivial divisors of p being GCD(b ± 1, p).
• b² ≠ 1, where p is proven composite by Fermat's test, base a.
• b = 0, where p has a nontrivial divisor GCD(a, p).

A Proth Certificate is a primality certificate associated with Proth numbers and Proth's test, specifically. It is a document or digital proof of verification of any conditions proving primality (or compositeness). It typically contains the values k and n that comprises the Proth number, p, thus proving that it is a Proth number, as well as the a-value that proves primality. It may also prove compositeness, if appropriate. The certificate often shows the work of proof, including evidence that a is a quadratic nonresidue, etc., if necessary.

The first Proth primes are (sequence A080076 in the OEIS):

3, 5, 13, 17, 41, 97, 113, 193, 241, 257, 353, 449, 577, 641, 673, 769, 929, 1153 ....

The largest known Proth prime as of 2016 is 10223 × 2^31172165 + 1, and is 9,383,761 digits long.^[3] It was found by Peter Szabolcs in the PrimeGridvolunteer computing project, which announced it on 6 November 2016.^[4] It is the 11th-largest known prime number as of January 2024, it was the largest known non-Mersenne prime until being surpassed in 2023,^[5] and is the largest Colbert number. The second-largest known Proth prime is 202705 × 2^21320516 + 1, found by PrimeGrid.^[6]

يستخدم برهان هذه النظرية اختبار بوكلينغتون-ليمر للأعداد الأولية . ويُعدّ إثبات نظرية بروث باستخدام هذا الاختبار حالةً خاصةً بسيطةً نسبيًا. كما أنه يُشابه إلى حد كبير برهان اختبار بيبان . ويمكن الاطلاع على البرهان في الصفحة 52 من المرجع ^{[ 1 ] .}

عندما يكون k = n ، يأخذ عدد بروث الشكل p = n² / ⁽ⁿ + 1). إذا خففنا الشرط الذي يشترط أن يكون k (أو n ) فرديًا، تُعرف هذه الأعداد بأعداد كولين ، مع أعداد كولين الأولية المقابلة . على الرغم من أن اختبار بروث يعمل عندما يكون n فرديًا، فإن لأعداد كولين اختبارات أولية خاصة بها لأي قيمة لـ n .

علاوة على ذلك، يمكن تعميم اختبارات كولين الأولية على الأعداد من الشكل p = nc ⁿ + 1، للأساسات العشوائية c .

نشر فرانسوا بروث (1852-1879) النظرية في عام 1878. ^{[ 7 ] [ 8 ]}

• اختبار بيبين (الحالة الخاصة k  =  1، حيث يتم اختيار a  =  3)
• رقم سيربينسكي

• وايسشتاين، إريك دبليو. "نظرية بروث" . عالم الرياضيات .