العدد 65 مركب، لأن 65 = 5 × 13. مع ذلك، باقي 8^64 عند القسمة عليه هو 1، وهي النتيجة التي قد تغريك بإعلان الأولية. سنحسبها دون كتابة القوة الهائلة، ثم نبدل الأساس إلى 2 ونحصل على باقي 16؛ العدد المختبر نفسه لم يتغير.
الخلاصة السريعة
نجاح 65 مع الأساس 8 لا يثبت أوليته؛ تحليله 5 × 13 يرفض ذلك مباشرة. أما الأساس 2 فيكشف تركيبه لأن باقي 2^64 على 65 هو 16، لا 1.
- إذا كان p أوليًا و a عددًا طبيعيًا لا يقبل القسمة على p، فلدينا a^(p−1) ≡ 1 (mod p). شرط الأساس جزء من مبرهنة فيرما الصغرى. [1]
- العدد 65 والأساس 8 أوليان نسبيًا، لكن 65 مركب. لدينا 8² = 64 وباقيه −1 بترديد 65؛ ثم 8^4 باقيه 1، فيكون 8^64 باقيه 1 أيضًا.
- مع الأساس 2، بواقي القوى ذات الأسس 1 و 2 و 4 و 8 و 16 و 32 و 64 هي 2، 4، 16، 61، 16، 61، 16 على 65. الباقي الأخير يختلف عن 1، فيرفض الأولية.
- في هذا الاختبار، للعدد n > 1 والأساس a بين 2 و n−1 مع قاسم مشترك أكبر 1، اختلاف باقي a^(n−1) عن 1 يثبت التركيب. مساواته 1 وحدها لا تثبت الأولية. [1]
- للعدد الأولي 13 والأساس 8، باقي 8^12 هو 1. لكن مع الأساس 13 يكون باقي 13^12 هو 0؛ لا نطبق صيغة الباقي 1 عندما يقسم العدد الأولي الأساس.
- للأولي p والأساس الطبيعي a، الصيغة a^p ≡ a (mod p) تشمل الأساس القابل للقسمة على p. [1] في 13^13 وباقي 13، النتيجتان 0؛ الأس هنا 13 وليس 12.
نثبت التركيب أولًا ثم نحسب نجاح الأساس ثمانية
نختار 65 = 5 × 13. العاملان أكبر من 1 وأصغر من 65، فيكفي وجودهما لإثبات أن العدد مركب. ليس مطلوبًا أن نعتمد على اختبار القوة كي نعرف ذلك. ثم نبحث عن نتيجة الاختبار نفسه لتفسير حدود ما يخبرنا به.
الأساس 8 والعدد 65 لا يشتركان في قاسم أكبر من 1: 65 = 8 × 8 + 1. هذا يحقق شرط الأولية النسبية، لكنه لا يجعل 65 أوليًا؛ الشرط يخص العلاقة بين عددين، والأولية تخص قواسم عدد واحد.
الأس المطلوب 64 لأنه أقل من 65 بواحد. لدينا 8² = 64، وباقي 64 على 65 هو 64، الذي يطابق −1. عند التربيع يصبح باقي 8^4 هو 1 لأن (−1)² = 1. ولأن 64 = 4 × 16، فإن 8^64 = (8^4)^16، وباقيه 1.
لم نساوِ8^64 بالعدد 1 كقيمة عادية؛ نتحدث عن باقي قسمة القوة على 65. وجود العاملين 5 و 13 باقٍ كما هو. إذن المثال يجمع تركيبًا مؤكدًا ونجاحًا حسابيًا مع أساس محدد، دون تناقض.
الشرط اللازم واتجاه الاستنتاج
الأولية تضمن نتيجة القوة بشرط الأساس المذكور في الملخص. [1]
إذا كان n > 1 و 2 ≤ a ≤ n−1 و gcd(a,n)=1، فباقي a^(n−1) المخالف للواحد يثبت التركيب؛ الباقي 1 لا يثبت الأولية. [1] الرمز gcd يعني القاسم المشترك الأكبر.
في مثالنا، نجاح الأساس 8 يعني أن 65 لم يُرفض بهذا الحساب؛ لا يعني أنه صار أوليًا أو أن تحليله خطأ. احتفظ في جوابك بالأساس والأس والقاسم والباقي، لأن كلمة «نجح» وحدها لا تصف ما اختبرته.
لا يحول تكرار النجاح في أمثلة صغيرة هذه العبارة إلى شرط كافٍ عام. مثال 65 واحد يكفي لنقض الاستنتاج «باقي 1 يعني أولي». ولا نستخرج منه احتمال خطأ أو تقييمًا لأداء برنامج، لأننا لم نحدد طريقة اختيار الأساس أو نموذجًا احتماليًا.
تبديل الأساس إلى اثنين يكشف العدد نفسه
نحسب القوى بالتربيع المتكرر: بدءًا من 2، يصبح باقي 2² هو 4، وباقي 2^4 هو 16. ثم 16² = 256 = 65 × 3 + 61، فيكون باقي 2^8 هو 61. وبعدها 61² = 3721 = 65 × 57 + 16، فيرجع الباقي إلى 16.
يتكرر الانتقال بين 16 و 61 عند مضاعفة الأس: للأس 16 باقي 16، وللأس 32 باقي 61، وللأس 64 باقي 16. ليس المقصود زيادة الأس بواحد؛ تربيع القوة يضاعف الأس. الجدول يضع الأساس 8 إلى جانب 2، مع قاسم ثابت 65.
العدد 2 أولي نسبيًا مع 65 لأن 65 فردي. لذلك الباقي 16 يرفض شرط الأولية في الاختبار. الرقم 16 في هذا السطر هو الباقي، بينما 64 هو الأس؛ لا نستبدل أحدهما بالآخر أو نقارن الباقي بالعدد 64.
الصورة الرئيسية تعرض الصفين نفسيهما، وتبرز البطاقة الأخيرة لكل منهما. اقرأ الأسس من اليسار إلى اليمين؛ النتيجة النهائية مع 8 هي 1 ومع 2 هي 16. كلا الصفين يخص العدد 65، ولا يمثلان عددين مختلفين.
| الأس | الباقي للأساس 8 | الباقي للأساس 2 |
|---|---|---|
| 1 | 8 | 2 |
| 2 | 64 | 4 |
| 4 | 1 | 16 |
| 8 | 1 | 61 |
| 16 | 1 | 16 |
| 32 | 1 | 61 |
| 64 | 1 | 16 |
الأولي ثلاثة عشر لا يجعل كل أساس صالحًا للصيغة نفسها
العدد 13 أولي؛ لو كان مركبًا لكان له عامل غير تافه لا يزيد على جذره. وبما أن 3² أصغر من 13 و 4² أكبر منه، نختبر 2 و 3؛ الباقيان 1 و 1، فلا يوجد قاسم منهما. أما 8 فلا يقبل القسمة على 13.
في هذا المثال، 8² = 64 = 13 × 4 + 12، فالباقي 12 يطابق −1. وباقي 8^4 هو 1، ومن 12 = 4 × 3 نحصل على باقي 8^12 مساويًا 1. هذا مثال مؤهل للصيغة ذات الأس السابق للعدد الأولي.
إذا بدلنا الأساس إلى 13، فكل قوة موجبة له تقبل القسمة على 13، وباقي 13^12 هو 0. لا يكذب ذلك المبرهنة؛ شرط عدم قسمة الأساس لم يتحقق. الصورة الداخلية تبقي العدد 13 ثابتًا وتظهر سبب اختلاف الباقيين.
أما الصيغة a^p ≡ a (mod p) فتشمل الأساس الطبيعي القابل للقسمة على p أيضًا. [1] في اختيار a=13 و p=13، باقي 13^13 هو 0، وباقي 13 هو 0؛ تتفق الصيغة العامة بينما صيغة الباقي 1 غير مؤهلة.
سجل ما اختبرته قبل الحكم
المجال هنا أعداد صحيحة n > 1. في المثال المركب استخدمنا أساسين صالحين بين 2 و 64، كل منهما أولي نسبيًا مع 65. وفي مثال 13 تعمدنا عرض أساس يساوي القاسم لنشرح سبب خروجه من شرط الصيغة الأولى. للعدد 2 لا يوجد أساس بين 2 و n−1؛ نطاق اختيار الأساس هذا لا يتيح إجراء التجربة عليه، ولا ينفي أوليته.
إذا وجد قاسم مشترك أكبر من 1 بين أساس a أصغر من n وبين n، فهو عامل غير تافه ويكشف التركيب مباشرة. لكن مجرد عدم تحقيق صيغة الباقي 1 مع أساس يساوي n لا يكفي لهذا الاستدلال: مثال 13 نفسه أولي، والقاسم المشترك مع أساس 13 هو 13.
أخذ الباقي بعد كل تربيع يحافظ على النتيجة: إذا كتبنا العدد 65q+r، فإن مربعه يتكون من حد يقبل القسمة على 65 وحد باقٍr². لذلك يمكن تربيع الباقي بدل القوة الكاملة. في مقالنا انتهى التربيع عند الأس 64 تحديدًا، دون إدخال تقريب أو كسور.
اكتب العدد المختبر، ثم الأساس، ثم الأس السابق للعدد، ثم الباقي. مع 65 والأساس 8 تحصل على 1، لكن التحليل 5 × 13 يبقى دليلًا على التركيب. ومع 65 والأساس 2 تحصل على 16 فتجد شاهدًا على فشل شرط الأولية. النجاح والفشل لا يعطيان الاستنتاج نفسه.
اقرأ أيضًا: تحليل العدد إلى عوامله الأولية
المراجع
أُعدّ هذا المقال بمساعدة الذكاء الاصطناعي، وخضع لمراجعة ذاتية بالأداة نفسها. لا يُنسب إلى مراجع بشري أو خبير مستقل. منهجية المحتوى.