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

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

multiplicative Inverse mod n

تعريف 1 : يقال أن العدد b معكوس ضربي multiplicative inverse للعدد الصحيح a معيار n إذا كان ab \equiv 1\;(\bmod n).

ليس بالضرورة أن يكون لكل عدد a معكوس ضربي(سنبين الشرط الواجب توفره في الحقيقة أدناه), مثلا العدد 6 ليس له معكوس ضربي معيار 4. يكفي للتأكد من ذلك استعراض حواصل ضرب 6 في الأعداد 1,2,3 فقط

6 \cdot 1 \equiv 2\;(\bmod 4),\quad 6 \cdot 2 \equiv 0\;(\bmod 4)\quad 6 \cdot 3 \equiv 2\;(\bmod 4)

حقيقة 1: يوجد للعدد الصحيح a معكوس ضربي معيار n إذا وإذا فقط كان العددين a,n أوليان نسبيا.

الكفاية واضحة لأنه إذا كان العددين a,n أوليان نسبيا فحسب متطابقة بيزوه هناك صحيحين x,y بحيث ax+ny=1 وبالتالي x هو المعكوس الضربي للعدد a معيار k لأن

ax \equiv 1\;(\bmod n)

شرط الضرورة , افرض أن هناك صحيح b بحيث ab \equiv 1\;(\bmod n) وبالتالي فإن ab-1 يقبل القسمة على n. أي أن ab-1=kn حيث k عدد صحيح ومنه ab+kn=1 مما يعني أن العددين a,n أوليان نسبيا.

المعكوس الضربي ليس وحيدا, فمثلا كلا العددين 3,-2 هما معكوس ضربي للعدد 7 معيار 5. الملاحظ عليهما أنهما متطابقين معيار 5. هذه ليست صدفة فإذا كان a_1 ,a_2 نظيرا a معيار n فإن a_1 \equiv a_2 \;(\bmod n).

أيضا إذا كان a \equiv b\;(\bmod n) حيث b أحد الأعداد 1,2,...,n-1 فإن للعدد a معكوس ضربي معيار n إذا وإذا فقط كان للعدد b معكوس ضربي معيار n. بمعنى آخر للعدد a معكوس إذا كان مطابق لأحد الأعداد الصحيحة الموجبة الأصغر من n والأولية نسبيا مع n.

طريقة إيجاد المعكوس الضربي

إحدى الطرق الحسابية في إيجاد المعكوس الضربي للعدد a معيارn تعتمد على خوارزمية اقليدس أو على الخوارزمية الاقليدية الموسعة من خلالهما نستطيع التحقق أولا من أن العددين أوليان نسبيا وهذه الخوارزميات سبق مناقشتها. ثم نوجد x,y الخاصة بمتطابقة بيزوه لنحصل على تركيب على الشكل

ax+ny=1

وعندها يكون x هو المعكوس المطلوب لأن ax \equiv 1\;(\bmod n).