فروبينيوس شبه الأولي

في نظرية الأعداد ، يُعرف العدد شبه الأولي لفروبينيوس بأنه عدد شبه أولي ، وقد استُلهم تعريفه من اختبار فروبينيوس التربيعي الذي وصفه جون غرانثام في ورقة بحثية أولية نُشرت عام 2000. ^{[ 1 ] [ 2 ]} يمكن تعريف الأعداد شبه الأولية لفروبينيوس بالنسبة لكثيرات الحدود من الدرجة الثانية على الأقل، ولكنها دُرست على نطاق واسع في حالة كثيرات الحدود التربيعية . ^{[ 3 ] [ 4 ]}

تعريف الأعداد الأولية الزائفة لفروبينيوس بالنسبة لكثير الحدود التربيعي الأحادي${\displaystyle x^{2}-Px+Q}$، حيث يكون التمييز${\displaystyle D=P^{2}-4Q}$ليس مربعًا، ويمكن التعبير عنه بدلالة متواليات لوكاس${\displaystyle U_{n}(P,Q)}$و${\displaystyle V_{n}(P,Q)}$على النحو التالي.

العدد المركب n هو عدد فروبينيوس${\displaystyle (P,Q)}$عدد أولي زائف إذا وفقط إذا

${\displaystyle (1)\qquad \gcd(n,2QD)=1,}$

${\displaystyle (2)\qquad U_{n-\delta }(P,Q)\equiv 0{\pmod {n}},}$و

${\displaystyle (3)\qquad V_{n-\delta }(P,Q)\equiv 2Q^{(1-\delta )/2}{\pmod {n}},}$

أين${\displaystyle \delta =\left({\tfrac {D}{n}}\right)}$هو رمز جاكوبي .

عند تحقق الشرط (2)، يصبح الشرط (3) مكافئًا لـ

${\displaystyle (3')\qquad V_{n}(P,Q)\equiv P{\pmod {n}}.}$

لذلك، فإن فروبينيوس${\displaystyle (P,Q)}$يمكن تعريف العدد الأولي الزائف n بشكل مكافئ من خلال الشروط (1-3)، أو من خلال الشروط (1-2) و (3′).

بما أن الشرطين (2) و(3) يتحققان لجميع الأعداد الأولية التي تحقق الشرط البسيط (1)، فيمكن استخدامهما كاختبار احتمالي لأولية العدد . (إذا لم يتحقق الشرط (1)، فإما أن يكون القاسم المشترك الأكبر أقل من n ، وفي هذه الحالة يكون عاملاً غير تافه ويكون n عددًا مركبًا، أو أن القاسم المشترك الأكبر يساوي n ، وفي هذه الحالة ينبغي تجربة قيم مختلفة للمعاملين P و Q بحيث لا تكون من مضاعفات n ).

كل فروبينيوس${\displaystyle (P,Q)}$العدد الأولي الزائف هو أيضًا

• عدد لوكاس شبه أولي ذو معلمات${\displaystyle (P,Q)}$، لأنها محددة بالشروط (1) و(2)؛ ^{[ 2 ] [ 3 ] [ 5 ]}
• عدد أولي زائف من نوع ديكسون ذو معلمات${\displaystyle (P,Q)}$، حيث يتم تعريفها بالشروط (1) و (3)؛ ^{[ 5 ]}
• قاعدة فيرما شبه الأولية${\displaystyle |Q|}$متى${\displaystyle |Q|>1}$.

إن عكس أي من هذه العبارات غير صحيح، مما يجعل فروبينيوس${\displaystyle (P,Q)}$الأعداد الأولية الزائفة هي مجموعة جزئية فعلية من كل من مجموعتي الأعداد الأولية الزائفة لوكاس والأعداد الأولية الزائفة ديكسون ذات المعاملات.${\displaystyle (P,Q)}$، وأعداد فيرما الأولية الزائفة للأساس${\displaystyle |Q|}$متى${\displaystyle |Q|>1}$علاوة على ذلك، يترتب على ذلك أنه بالنسبة لنفس المعايير${\displaystyle (P,Q)}$يكون العدد المركب عددًا أوليًا زائفًا من نوع فروبينيوس إذا وفقط إذا كان عددًا أوليًا زائفًا من نوع لوكاس وديكسون. بعبارة أخرى، لكل زوج ثابت من المعاملات${\displaystyle (P,Q)}$، مجموعة الأعداد الأولية الزائفة لفروبينيوس تساوي تقاطع مجموعتي الأعداد الأولية الزائفة للوكاس وديكسون.

بينما كل فروبينيوس${\displaystyle (P,Q)}$العدد شبه الأولي هو عدد شبه أولي لوكاس، ولكنه ليس بالضرورة عددًا شبه أولي لوكاس قويًا . على سبيل المثال، 6721 هو أول عدد شبه أولي فروبينيوس لـ${\displaystyle (P,Q)=(1,-1)}$، وهو ليس عددًا أوليًا زائفًا قويًا من نوع لوكاس.

كل عدد شبه أولي من نوع فروبينيوس إلى${\displaystyle x^{3}-x-1}$وهو أيضًا عدد أولي زائف مقيد من نوع بيرين . تنطبق عبارات مماثلة على كثيرات الحدود التكعيبية الأخرى من الشكل${\displaystyle x^{3}-rx^{2}+sx-1}$[ ^{2 ]​}

أعداد فروبينيوس الأولية الزائفة بالنسبة لكثير حدود فيبوناتشي${\displaystyle x^{2}-x-1}$يتم تحديدها بدلالة أرقام فيبوناتشي${\displaystyle F_{n}=U_{n}(1,-1)}$وأرقام لوكاس${\displaystyle L_{n}=V_{n}(1,-1)}$تشكل هذه الأعداد الأولية الزائفة لفروبينيوس المتتالية التالية:

4181، 5777، 6721، 10877، 13201، 15251، 34561، 51841، 64079، 64681، 67861، 68251، 75077، 90061، 96049، 97921، 100127، 113573، 118441، 146611، 161027، 162133، 163081، 186961، 197209، 219781، 231703، 252601، 254321، 257761، 268801، 272611، 283361، 302101، 303101، 330929، 399001، 430127، 433621، 438751، 489601، ... (التسلسل A212424 في OEIS ) .

بينما يُعدّ العدد 323 أول عدد أولي زائف من نوع لوكاس بالنسبة لكثير الحدود فيبوناتشي${\displaystyle x^{2}-x-1}$أول عدد أولي زائف لفروبينيوس بالنسبة لنفس متعددة الحدود هو 4181 (ذكره غرانثام على أنه 5777 ^{[ 2 ]،} لكن العديد من المؤلفين أشاروا إلى أن هذا غير صحيح، وأنه بدلاً من ذلك أول عدد أولي زائف له${\displaystyle \left({\tfrac {5}{n}}\right)=-1}$بالنسبة لهذه متعددة الحدود ^{[ 3 ]} ).

حالة أخرى، أعداد فروبينيوس الأولية الزائفة بالنسبة لكثير الحدود التربيعي${\displaystyle x^{2}-3x-1}$يمكن تحديد ذلك باستخدام لوكاس${\displaystyle (3,-1)}$التسلسل و هي:

119، 649، 1189، 4187، 12871، 14041، 16109، 23479، 24769، 28421، 31631، 34997، 38503، 41441، 48577، 50545، 56279، 58081، 59081، 61447، 75077، 91187، 95761، 96139، 116821، 127937، 146329، 148943، 150281، 157693، 170039، 180517، 188501، 207761، 208349، 244649، 281017، 311579، 316409، 349441، 350173، 363091، 371399، 397927، 423721، 440833، 459191، 473801، 479119، 493697، ... (التسلسل A327655 في OEIS )

في هذه الحالة، يكون العدد الأولي الزائف الأول لفروبينيوس بالنسبة لكثير الحدود التربيعي${\displaystyle x^{2}-3x-1}$وهو 119، وهو أيضًا أول عدد أولي زائف من نوع لوكاس بالنسبة لنفس متعددة الحدود. بالإضافة إلى ذلك،${\displaystyle \left({\tfrac {13}{119}}\right)=-1}$.

متعددة الحدود من الدرجة الثانية${\displaystyle x^{2}-3x-5}$، أي${\displaystyle (P,Q)=(3,-5)}$تحتوي هذه الدالة على أعداد أولية زائفة أقل مقارنةً بالعديد من الدوال التربيعية البسيطة الأخرى. باستخدام نفس العملية المذكورة أعلاه، نحصل على المتتالية التالية:

13333، 44801، 486157، 1615681، 3125281، 4219129، 9006401، 12589081، 13404751، 15576571، 16719781، ….

لاحظ أن هناك 3 أعداد أولية زائفة فقط أقل من 500000، بينما هناك العديد من الأعداد الأولية الزائفة من نوع فروبينيوس (1، -1) و (3، -1) أقل من 500000.

كل عنصر في هذه المتتالية هو عدد أولي زائف من نوع فيرما للأساس 5، وكذلك عدد أولي زائف من نوع لوكاس (3، -5)، لكن العكس غير صحيح: فالعدد 642001 هو عدد أولي زائف من نوع psp-5 وعدد أولي زائف من نوع لوكاس (3، -5)، ولكنه ليس عدداً أولياً زائفاً من نوع فروبينيوس (3، -5). (لاحظ أن العدد الأولي الزائف من نوع لوكاس للزوج ( P ، Q ) ليس بالضرورة أن يكون عدداً أولياً زائفاً من نوع فيرما للأساس | Q |، على سبيل المثال، العدد 14209 هو عدد أولي زائف من نوع لوكاس (1، -3)، ولكنه ليس عدداً أولياً زائفاً من نوع فيرما للأساس 3).

كما تم تعريف الأعداد الأولية الزائفة القوية لفروبينيوس. ^{[ 2 ]} يمكن الاطلاع على تفاصيل تطبيقها على كثيرات الحدود التربيعية في كتاب كراندال وبوميرانس. ^{[ 3 ]}

من خلال فرض القيود التي${\displaystyle \delta =-1}$و${\displaystyle Q\neq \pm 1}$يوضح مؤلفو ^{[ 6 ]} كيفية الاختيار${\displaystyle P}$و${\displaystyle Q}$بحيث لا يوجد سوى خمسة أعداد فردية مركبة أقل من${\displaystyle 10^{15}}$والتي ينطبق عليها الشرط (3)، أي التي${\displaystyle V_{n+1}\equiv 2Q{\pmod {n}}}$.

يمكن استخدام الشروط التي تحدد العدد شبه الأولي لفروبينيوس لاختبار احتمالية أولية عدد معين n . غالبًا لا تعتمد هذه الاختبارات على معايير ثابتة.${\displaystyle (P,Q)}$بل يتم اختيارها بطريقة معينة بناءً على العدد المدخل n لتقليل نسبة النتائج الإيجابية الخاطئة ، أي الأعداد المركبة التي تجتاز الاختبار. تُسمى هذه الأعداد المركبة أحيانًا بالأعداد الأولية الزائفة لفروبينيوس، على الرغم من أنها قد تتوافق مع معايير مختلفة.

باستخدام أفكار اختيار المعاملات التي طُرحت لأول مرة في دراسة بايلي وواغستاف (1980) ^{[ 7 ]} كجزء من اختبار بايلي-PSW للأولوية ، والتي استخدمها غرانثام في اختبار فروبينيوس التربيعي الخاص به ^{[ 8 ]} ، يُمكن إنشاء اختبارات تربيعية أفضل. على وجه الخصوص، تبيّن أن اختيار المعاملات من البواقي غير التربيعية modulo n (استنادًا إلى رمز جاكوبي ) يُنتج اختبارات أقوى بكثير، وهو أحد أسباب نجاح اختبار بايلي-PSW للأولوية . على سبيل المثال، بالنسبة للمعاملات ( P , 2)، حيث P هو أول عدد صحيح فردي يحقق الشرط التالي:${\displaystyle \left({\tfrac {D}{n}}\right)=-1}$، لا توجد أعداد أولية زائفة أقل من 2 ⁶⁴ .

يقترح خاشين اختبارًا آخر. ^{[ 9 ]} بالنسبة لعدد غير مربع معطى n ، يحسب أولًا المعامل c باعتباره أصغر عدد أولي فردي له رمز جاكوبي${\displaystyle \left({\tfrac {c}{n}}\right)=-1}$ثم يتحقق من التطابق:

${\displaystyle (1+{\sqrt {c}})^{n}\equiv (1-{\sqrt {c}}){\pmod {n}}}$.

بينما تجتاز جميع الأعداد الأولية n هذا الاختبار، فإن العدد المركب n يجتازه إذا وفقط إذا كان n عددًا أوليًا زائفًا من نوع فروبينيوس لـ${\displaystyle (P,Q)=(2,1-c)}$على غرار المثال السابق، يشير خاشين إلى أنه لم يتم العثور على أي عدد أولي زائف لاختباره. ويُبين كذلك أن أي عدد أولي زائف موجود تحت 2^ ⁶⁰ يجب أن يكون له عامل أقل من 19 أو أن يكون c أكبر من 128.

• عدد أولي زائف
• لوكاس شبه أولي
• فرديناند جورج فروبينيوس
• اختبار فروبينيوس التربيعي

• وايسستين، إريك دبليو. “فروبينيوس بسيودوبريم” . عالم الرياضيات .
• وايسستين ، إريك دبليو. “Strong Frobenius Pseudoprime” . عالم الرياضيات .
• جاكوبسن، دانا إحصائيات الأعداد الأولية الزائفة، الجداول، والبيانات (بيانات لأعداد فروبينيوس الأولية الزائفة (1،-1) و(3،-5))