حاسبة المعكوس الضربي للباقي

أدخل الحساب

العدد الصحيح a

القياس m

نتائج

المعكوس الضربي

٤

a^-1 mod m

gcd(a, m)	١
المعكوس موجود	نعم

ما هو المعكوس الضربي بالقياس m؟

المعكوس الضربي بالقياس لعدد صحيح a بالنسبة للقياس m هو عدد صحيح x يقع ضمن المجال من 1 إلى m−1 ويحقق العلاقة \((a \cdot x) \bmod m = 1\). بعبارة أخرى، عند ضرب a في x وقسمة الناتج على m يكون الباقي مساوياً تماماً للواحد. ويُعدّ هذا المفهوم المكافئ لعملية القسمة على a في حساب الباقي (الحساب القياسي)، وهو حجر أساس في نظرية الأعداد والتشفير (توليد مفاتيح خوارزمية RSA، ودوال التجزئة (Hashing)، ونظرية الباقي الصينية، و␣غيرها الكثير).

Modular arithmetic wraps the number line into a circle of m positions.

كيفية استخدام الحاسبة

أدخل العدد الصحيح a والقياس m (على أن يكون m مساوياً للعدد 2 أو أكبر). تقوم الحاسبة بتبسيط a بالقياس m، ثم تطبّق خوارزمية إقليدس الموسعة، وتُعيد المعكوس إن وُجد. أما القيم السالبة للعدد a فتُعالَج تلقائياً عبر إرجاعها إلى المجال من 0 إلى m−1.

شرح الصيغة الرياضية

يوجد المعكوس إذا وفقط إذا كان القاسم المشترك الأكبر \(\gcd(a, m) = 1\) — أي أنّ a وm لا يشتركان في أي عامل مشترك سوى الواحد (يكونان أوّليين فيما بينهما). تجد خوارزمية إقليدس الموسعة عددين صحيحين s وt يحققان \(a \cdot s + m \cdot t = \gcd(a, m)\). وعندما يكون القاسم المشترك الأكبر مساوياً للواحد، فإنّ المعامل s مبسطاً بالقياس m هو المعكوس المطلوب. أمّا إذا كان \(\gcd(a, m) \neq 1\)، فلا وجود لأي معكوس.

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}}, \quad x \text{ exists } \iff \gcd\!\left(\text{a},\, \text{m}\right) = 1$$

The extended Euclidean algorithm yields x satisfying a·x + m·y = 1.

مثال محلول

لنوجد معكوس العدد 3 بالقياس 11. نبحث عن قيمة x تحقق \((3 \cdot x) \bmod 11 = 1\). وبالتجربة نجد أنّ \(3 \cdot 4 = 12\)، و\(12 \bmod 11 = 1\). إذن المعكوس هو 4. وتعطي خوارزمية إقليدس الموسعة النتيجة ذاتها فوراً لأنّ \(\gcd(3, 11) = 1\).

Multiplying a by its inverse x lands exactly on 1 after wrapping mod m.

الأسئلة الشائعة

متى لا يوجد معكوس؟ عندما لا يكون a وm أوّليين فيما بينهما. فمثلاً، لا يملك العدد 4 معكوساً بالقياس 8 لأنّ \(\gcd(4, 8) = 4 \neq 1\).

هل يجب أن يكون القياس عدداً أوّلياً؟ لا. يصلح أي قياس ما دام a أوّلياً بالنسبة إليه. وإذا كان m عدداً أوّلياً، فإنّ كل عدد a غير صفري من 1 إلى m−1 يملك معكوساً.

لماذا تقع النتيجة دائماً بين 1 وm−1؟ لأنّنا نبسّط المعكوس بالقياس m للحصول على أصغر ممثل موجب قياسي (الصورة النموذجية).