ما هي حاسبة المعكوس الضربي النمطي؟
تجد هذه الحاسبة المعكوس الضربي النمطي لعدد صحيح a بالنسبة إلى المقياس m — أي العدد الصحيح الوحيد x في المجال \(0 \le x < m\) بحيث يتحقق \(a \cdot x \equiv 1 \pmod{m}\). وتعتمد على خوارزمية إقليدس الموسّعة التي تُرجِع كذلك القاسم المشترك الأكبر \(\gcd(a, m)\). هذه عملية من صميم نظرية الأعداد وتعمل بالطريقة نفسها في كل مكان؛ وتُستخدم على نطاق واسع في التشفير (توليد مفاتيح RSA) وفي دوال التجزئة (Hashing) وحلّ التطابقات الخطية.
طريقة الاستخدام
أدخِل العدد الصحيح a ومقياسًا موجبًا m (استخدم \(m \ge 2\) للحصول على معكوس وحيد ذي معنى). تقوم الأداة بإرجاع a إلى باقيه بالنسبة إلى m، ثم تُشغّل خوارزمية إقليدس الموسّعة، وتعرض المعكوس مع القاسم المشترك الأكبر \(\gcd(a, m)\). وإذا لم يكن a و m أوّليين فيما بينهما (أي \(\gcd \ne 1\)) فلا يوجد معكوس، وتُنبّهك الحاسبة إلى ذلك.
شرح الصيغة
يوجد المعكوس إذا وفقط إذا كان \(\gcd(a, m) = 1\). تجد خوارزمية إقليدس الموسّعة عددين صحيحين s و t بحيث \(a \cdot s + m \cdot t = \gcd(a, m)\). وعندما يكون القاسم المشترك الأكبر يساوي 1، يتحقق \(a \cdot s \equiv 1 \pmod{m}\)، ومن ثَمّ يكون المعكوس $$x = ((s \bmod m) + m) \bmod m$$ بعد تطبيعه إلى أصغر باقٍ غير سالب.
مثال محلول
لنأخذ \(a = 7\) و \(m = 4\): بما أن \(7 \equiv 3 \pmod{4}\)، فإننا نحلّ \(3x \equiv 1 \pmod{4}\). تُعطي خوارزمية إقليدس الموسّعة على (7, 4) قيمة \(\gcd = 1\) ومعامل بيزو \(s = -1\)، إذًا $$x = ((-1 \bmod 4) + 4) \bmod 4 = 3$$ والتحقق: \(7 \cdot 3 = 21 = 5 \cdot 4 + 1 \equiv 1 \pmod{4}\). الجواب هو 3.
الأسئلة الشائعة
متى لا يوجد معكوس؟ فقط عندما يكون \(\gcd(a, m) > 1\). على سبيل المثال \(a = 6\) و \(m = 9\) قيمتهما \(\gcd = 3\)، لذا لا يوجد معكوس.
هل يمكن أن يكون a سالبًا أو أكبر من m؟ نعم. نُرجِع a أولًا إلى باقيه بالنسبة إلى m؛ ولا تتغيّر النتيجة لأن \(a \equiv a' \pmod{m}\).
ماذا لو كان m = 1؟ كل عدد صحيح يطابق 0 بالنسبة إلى المقياس 1، لذا فإن المعكوس هو 0 بشكل بديهي.
