اختبار فيرما لأولية عدد ما
تعريفًا بالموضوع، اختبار فيرما لأولية عدد ما هو اختبار احتمالي لتحديد إذا كان عدد طبيعي ما عددا أوليا محتملا. ونتناول فيما يلي مزيدًا من التفاصيل.
فكرة
في هذا الإطار، يَكمُن الجزء الاحتمالي في اختبار فيرما بأنّ هنالك أعداد تُحقّق المعادلة أعلاه ولكنّها ليست أوّلية. أي، لنفترض أن لدينا عدد p ليس أوّلي، من الممكن أن نختار عدد a بشكل عشوائي، والذي يُحقق المعادلة (أنظر: أعداد فيرما شبه الأولية). بالتالي، إذا اخترنا عدداً عشوائياً وتبيّن أن هذا العدد يُحقق المعادلة، لا نستطيع التحديد بشكل قطعيّ ما إذا كان العدد أوّليا. في هذه الحالة بإمكاننا اختيار عدد عشوائي آخر وفحص ما إذا كان هو كذلك يُحقق المعادلة. في حال تبيّن أن جميع الأعداد حقّقت المعادلة، فالاختبار يُجيب بأن العدد هو أوّلي مُحتمل.
وعلى صعيد آخر، عليه، لفحص ما إذا كان عدداً ما أوّلياً، فباستطاعنا اختيار عدد عشوائي a لا يقسم على p، وفحص ما إذا كان يُحقق المعادلة أعلاه أم لا. إذا تبيّن أنّ العدد a لا يُحقق المعادلة، فبالضرورة p ليس أوّلي.
في هذا الإطار، بحسب مبرهنة فيرما الصغرى، والتي بحسبها فإن لكل عدد أوّلي p، وعدد a بحيث أن p لا يـُقـسِّم a يتحققّ:
مثال
وفي هذا الصدد، لذلك فإن العدد الذي اخترناه يُحقق المعادلة. الآن هنالك احتمالين، إمّا أن يكون 221 عدداً أوّليّا حقاً، أو عدد «فيرما كاذب». لذلك نقوم باختيار عدد آخر، مثلاً a = 24.
وفي السياق ذاته، لذلك فإن 221 ليس عدد أوّلي والعدد 38 هو في الحقيقة عدد «فيرما كاذب»، علاوة على ذلك، فإن العدد 24 شاهد على كوَن العدد 221 عدد غير أوّلي.
وعلى صعيد آخر، لنفتَرض أنّ لدينا عدد n = 221 ونودّ التحقق ما إذا كان أوّليا. اختر بشكل عشوائي عدد ، مثلاً a = 38. الآن نفحص ما إذا كان العدد الذي اخترناه يُحقق المعادلة في الأعلى.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟