ما هي مبرهنة فيرما الصغرى؟
تُعدّ مبرهنة فيرما الصغرى حجر الأساس في نظرية الأعداد. تنصّ على أنه إذا كان p عددًا أوليًا وa عددًا صحيحًا لا يقبل القسمة على p (أي أن \(\gcd(a, p) = 1\))، فإنّ a مرفوعًا للأُسّ (p − 1) يُعطي باقيًا قدره 1 عند القسمة على p. وبالرموز: $$a^{\,p-1} \equiv 1 \pmod{p}$$ كما توجد صيغة أعمّ تصحّ لأي عدد صحيح a وهي: $$a^{\,p} \equiv a \pmod{p}$$
كيفية استخدام الحاسبة
أدخِل قيمة الأساس a وقيمة p. تتحقق الحاسبة ممّا إذا كان p عددًا أوليًا، ثم تحسب \(\gcd(a, p)\)، وتُقيّم كلًّا من \(a^{\,p-1} \bmod p\) و \(a^{\,p} \bmod p\) باستخدام الرفع الأُسّي النمطي السريع. فعندما يكون p أوليًا و \(\gcd(a, p) = 1\)، تكون النتيجة الأولى دائمًا 1 — وهو ما يؤكد صحة المبرهنة. أمّا إذا لم تتحقق هذه الشروط، فتُعرَض نتيجة \(a^{\,p-1}\) على شكل غير متاح (n/a)، لأنّ المبرهنة لا تضمن أن تكون القيمة 1.
شرح الصيغة الرياضية
يقوم الرفع الأُسّي النمطي بتربيع الأساس بشكل متكرر مع أخذ الباقي بالقسمة على p في كل خطوة، بحيث تبقى الأُسس الكبيرة قابلة للحساب بسهولة. وتُشكّل هذه المبرهنة الأساس لاختبارات الأولية (اختبار فيرما)، ولحسابات مفاتيح التشفير في خوارزمية RSA، ولإيجاد المعكوسات النمطية، إذ يُعطي \(a^{\,p-2} \bmod p\) معكوس a نسبةً إلى عدد أولي p.
مثال محلول
لِنفترض أن \(a = 2\) و \(p = 7\). وبما أنّ 7 عدد أولي و \(\gcd(2, 7) = 1\)، فإننا نتوقع أن يكون $$2^{6} \bmod 7 = 64 \bmod 7 = 1. \checkmark$$ أمّا الصيغة العامة فتُعطي $$2^{7} \bmod 7 = 128 \bmod 7 = 2,$$ وهو ما يساوي \(a \bmod 7 = 2\). ✔
الأسئلة الشائعة
ماذا لو لم يكن p عددًا أوليًا؟ قد لا تتحقق المبرهنة في هذه الحالة. تُنبّهك الحاسبة بأنّ p ليس أوليًا، وتكون عندئذٍ قيمة الصيغة العامة \(a^{\,p} \bmod p\) هي الوحيدة ذات المعنى، دون أن تساوي a بالضرورة.
ماذا لو كان a من مضاعفات p؟ عندئذٍ يكون \(\gcd(a, p) \neq 1\)، وبالتالي لن تساوي \(a^{\,p-1} \bmod p\) القيمة 1 (بل تكون 0). ومع ذلك تبقى الصيغة العامة \(a^{\,p} \equiv a\) صحيحة.
هل يمكنني استخدامها لإيجاد المعكوسات النمطية؟ نعم — فمن أجل عدد أولي p، يكون \(a^{\,p-2} \bmod p\) هو المعكوس الضربي لـ a نسبةً إلى p.
