إذا كان $n$ عدد صحيح موجب و $a$ و $b$ عددين صحيحين قابلين للاستبدال (invertible) بالنسبة للقسمة على $n$ بحيث ينطبق $a \equiv b^{-1} \pmod{n}$، فما هو الباقي عندما يتم قسم العدد $ab$ على $n$؟
الحل:
نعلم أنه إذا كان $a$ قابلاً للاستبدال (invertible) بالنسبة للقسمة على $n$، فإنه يوجد عدد صحيح $a^{-1}$ بحيث ينطبق $a \cdot a^{-1} \equiv 1 \pmod{n}$. وبالمثل، إذا كان $b$ قابلاً للاستبدال (invertible) بالنسبة للقسمة على $n$، فإنه يوجد عدد صحيح $b^{-1}$ بحيث ينطبق $b \cdot b^{-1} \equiv 1 \pmod{n}$.
وبما أنه معطى أن $a \equiv b^{-1} \pmod{n}$، فإننا نستنتج أيضًا أن $ab \equiv 1 \pmod{n}$، لأنه يتم ضرب $a$ في $b^{-1}$ والناتج يكون $1$ بالنسبة للقسمة على $n$.
وبالتالي، الباقي عند قسم العدد $ab$ على $n$ هو $1$.
باختصار، الباقي عند قسم العدد $ab$ على $n$ هو $1$.
المزيد من المعلومات
لحل المسألة، سنستخدم عدة مفاهيم من نظرية الأعداد وحساب المودولو. دعنا نقوم بتوضيح الخطوات بالتفصيل وذكر القوانين المستخدمة:
-
تعريف القابلية للاستبدال (Invertibility): عدد صحيح $a$ يُعتبر قابلًا للاستبدال بالنسبة للقسمة على $n$ إذا كان لدينا عدد آخر $a^{-1}$ بحيث يتحقق الشرط التالي: $a \cdot a^{-1} \equiv 1 \pmod{n}$.
-
مساواة الاستبدال (Inversion Congruence): إذا كان $a \equiv b^{-1} \pmod{n}$، فهذا يعني أن $a$ يمكن استبداله بعكس $b$ بالنسبة للقسمة على $n$.
-
ضرب الاستبدالات (Multiplying Inverses): إذا كانت $a$ و $b$ قابلتين للاستبدال بالنسبة للقسمة على $n$، فإنه عند ضربهما معًا، يُنتج الناتج بالقسمة على $n$.
الآن، لنقم بحل المسألة:
معطيات المسألة:
- $a \equiv b^{-1} \pmod{n}$.
- $a$ و $b$ قابلتان للاستبدال بالنسبة للقسمة على $n$.
نريد أن نجد الباقي عند قسم $ab$ على $n$.
نظرًا لأن $a \equiv b^{-1} \pmod{n}$، فإنه يوجد $a^{-1}$ و $b$ بحيث:
- $a \cdot a^{-1} \equiv 1 \pmod{n}$.
- $b \cdot b^{-1} \equiv 1 \pmod{n}$.
نقوم بضرب المعادلتين معًا:
ونحصل على:
وهذا يعني أن الباقي عند قسم $ab$ على $n$ هو $1$.
باختصار، نستخدم قوانين الاستبدال والمساواة وضرب الاستبدالات لوصول إلى النتيجة النهائية التي تقول إن الباقي عند قسم $ab$ على $n$ هو $1$.