حساب التطابق

قواعد الحساب التالية مهمة في عمليات حساب التطابق:

• نظرية 1

إذا كان لدينا أن:

$$a \equiv a\,' \pmod{n}$$

و

$$\, b \equiv b\,' \pmod{n}$$

فستنطبق لدينا قواعد الحساب التالية

القاعدة 1: $$a + b \equiv a\,' + b\,' \pmod{n}$$

القاعدة 2: $$a \cdot b \equiv a\,' \cdot b\,' \pmod{n}$$

القاعدة 3: $$a^m \equiv (a\,')^m \pmod{n}$$

لجميع الأعداد الصحيحة الموجبة $m$

أي أن هذه النظرية تنص على أنه يمكن استبدال الأعداد المتطابقة مع بعضها البعض. دعونا نرى كيف يمكن ذلك في بعض الأمثلة.

فيما يلي سنقوم بإثبات صحة القاعدة الأولى ونأخذ أمثلة على القواعد الثلاثة ونترك عملية اثبات القاعدتين 2 و3 كتمارين.

قاعدة الحساب 1 – إثبات الإضافة

تنص القاعدة 1 على أن:
$$\mathbf{a + b \equiv a\,' + b\,' \pmod{n}}$$

بما أن

$$a \equiv a\,' \pmod{n}$$

و

$$b \equiv b\,' \pmod{n},$$

فهذا يعني أن لدينا عددين صحيحين \(\,k_1 \,و \,k_2\), حيث أن

$$\begin{cases}a - a\,' = \,k_1 \cdot n \hspace{2.5cm} (1) \\ b - b\,' = \,k_2 \cdot n \hspace{2.5cm} (2)\end{cases}$$

$\Leftarrow$ يجب أن لا ننسى أن الفرق بين أي عددين متطابقين (بقياس عدد صحيح $n$) عبارة عن عدد صحيح من مضاعفات الــ $n$.

بجمع المعادلتين $\left(1\right) + \left(2\right)$ سنحصل على

$$(a + b) - (a\,' + b\,') = (k_1 + k_2)\cdot n$$

ليكن \(k = k_1 + k_2\), لنحص على

$$(a + b) - (a\,' + b\,') = k\cdot n$$

حيث \(k\) عدد صحيح لأن \(k_1\) و \(k_2\) أعداد صحيحة, وهذا ما يدل على أن

$$\mathbf{a + b \equiv a\,' + b\,' \pmod{n}}$$

---

مثال: الباقي عند قسمة $141 + 31$ علــى $7$.

نعلم أن باقي قسمة كل من $141$ و $31$ بصورة منفصلة هو

$$\frac{141}{7}=20 \text{ rest } 1 $$

و

$$\frac{31}{7}=4 \text{ rest } 3. $$

نلاحظ أن $141$ تتطابق مع باقيها وهو الــ $1$ بقياس $7$, حيث أن $141$ و $1$ لهما الباقي $1$ عند القسمة علــى $7$. نفس الشئ ينطبق علــى الــ $31$, أي أن $31$ تتطابق مع باقيها وهو $3$ بقياس $7$. بإستخدام القاعدة الأولى يمكننا استبدال الــ $141$ بالــ $1$ و$31$ بالــ $3$. لنحصل على

$$141 + 31 \equiv 1 + 3 \pmod{7}.$$

نلاحظ أن حساب باقي قسمة الطرف الأيمن أسهل بكثير من قسمة الطرف الأيسر وذلك لأن $(1 + 3 = 4 )$ وعند قسمة العدد $4$ علــى $7$ فمن الواضح أن الباقي سيكون $4$, ولكن وفقًا لتعريف الأعداد المتطابقة فهذا يعني أن $\left(141 + 31\right)$ سيكون لها نفس الباقي عند القسمة علــى $7$ أي سيكون الباقي $4$.
هذه هي الطريقة الأكثر شيوعًا لاستخدام هذه القواعد الحسابية، أي باستبدال جميع الأعداد ببواقيها عند القسمة على $n$. ومع ذلك فمن المهم جداً ملاحظة أن القاعدة 1 لا تنص على أن (باقي "المجموع" يساوي "مجموع البواقي"). فهذا ليس بصحيح تماما..
لنفترض على سبيل المثال أننا نريد حساب باقي المجموع $17 + 28$ عند القسمة علـى $6$. سيكون المجموع $45$, والذي له الباقي $3$ عند القسمة علـى $6$ وذلك لأن \((45 = 7 \cdot 6+3)\). ولكن عند قسمة كل من $17$ و $28$ علـى العدد $6$ بصورة منفصلة ستكون البواقي هي $5$ و $4$ على التوالي. وبالتالي فان مجموع البواقي سيكون $$5 + 4 = 9,$$

وهو ما لا يساوي $3$ وهو باقي المجموع. في حين أن باقي حاصل قسمة الــ $9$ علـى الــ $6$ يساوي الــ $3$، تماماً كباقي المجموع. ولذلك فان النص الصحيح للقاعدة هو أن (باقي "المجموع" يساوي باقي "مجموع البواقي").

---

القاعدة 2 - الضرب​​

تنص القاعدة 2 على أن:

$$\mathbf{a \cdot b \equiv a\,' \cdot b\,' \pmod{n}}$$

مثال:

لنأخذ مثال على القاعدة 2. لنحسب الباقي في حالة قسمة $(17·21)$ علـى $5$. فإذا قسمنا العاملين بصورة منفصلة سيكون لدينا

$$\frac{17}{5} = 3 \text{ rest } 2 $$

و

$$\frac{21}{5} = 4 \text{ rest } 1 $$

بما أن أي عدد يتطابق مع باقيه فيمكننا استبدال $17$ و $21$ بالـ $2$ والـ $1$ على التوالي, لنحصل على ما يلي

$$17\cdot 21\equiv 2\cdot 1=2 \pmod{5}.$$

إشارة التساوي الأخير هي مساواة عادية ولا يوجد حساب تطابق في هذه الخطوة وانما هي عبارة عن ناتج حاصل ضرب الـ $2$ فــي الـ $1$. نلاحظ أن نتيجة هذه الحسابات تعني أن الأعداد $(17·21)$ و $2$ لها نفس الباقي عند القسمة علـى $5$. بما أن العدد $2$ أقل من $5$ فسيكون الباقي عند القسمة علـى $5$ هو الـ $2$ نفسها. ولذلك فإن العدد $(17·21)$ له الباقي $2$ عند القسمة علـى $5$.

هنا أيضا علينا ملاحظ أن القاعدة 2 لا تنص على أن(”باقي حاصل الضرب" يساوي "حاصل ضرب البواقي”). لنفترض على سبيل المثال أننا نريد حساب باقي حاصل الضرب $(15·10)$ عند القسمة علـى $4$. الباقي هو $2$ لأن

$$15 \cdot 10 = 150 = 148 + 2 = 37 \cdot 4 + 2.$$

ولكن بصورة منفصلة باقي قسمة $15$ علـى $4$ هو $3$ وباقي قسمة $10$ علـى $4$ هو $2$. بالتالي فان حاصل ضرب البواقي هو

$$3 \cdot 2 = 6,$$

وهو ما لا يساو الباقي $2$. ففي هذه الحالة فان القاعدة الصحيحة تنص على أن (باقي "ناتج الضرب" يساوي باقي "ناتج ضرب البواقي”), كما نلاحظ أن باقي قسمة $6$ علـى $4$ هو $2$.

---

​القاعدة 3 - القوى

تنص القاعدة 3 على أن:

$$\mathbf{a^m \equiv (a\,')^m \pmod{n}}$$

مثال:

دعونا نأخذ مثال على القاعدة 3. لنقوم بحساب الباقي عند قسمة العدد \(2^{10}\) علـى $3$. سنستخدم أولاً قواعد الأُسس والقوى لإعادة كتابة هذا العدد:

$$2^{10} = 2^{2 \cdot 5} = (2^2)^5 = 4^5.$$

الآن أصبح العدد في قاعدة الأُس هو $4$ بدلاً من $2$ و وفقاً للقاعدة 3 يمكننا استبداله بعدد مطابق بالقياس $3$, وليكن في هذه الحالة هو باقي قسمة العدد $4$ علـى $3$ وهو $1$. بالتالي سنحصل على

$${4}^{5} \equiv {1}^{5}\, \pmod{3}.$$

وهذا يعني أن

$$2^{10} = 4^5 \equiv 1^5 = 1\, \pmod{3},$$

حيث واحد مرفوع للقوة خمسة يساوي الواحد الصحيح نفسه مساواة عادية ولم يتم استخدام حساب التطابق. وهذا يعني أن العدد \(2^{10}\) والعدد $1$ لهما نفس الباقي عند القسمة على $3$. وبما أن باقي قسمة الـ $1$ علـى $3$ وهو $1$ نفسه(لأن الـ $1$ أقل من الـ $3$) فهذا يعني أن باقي العدد \(2^{10}\) هو $1$ عند القسمة على $3$.

حتى في هذه الحالة فهذا لا يعني أن القاعدة 3 تنص على أن (باقي "العدد المرفوع للقوة" يساوي "قوة الباقي”). فإذا أردنا على سبيل المثال الباقي عند قسمة العدد \(7^2\) علـى $4$. فإن الباقي هو $1$ وذلك لأن

$$7^2 = 49 = 48+1=12 \cdot 4 + 1.$$

لكن الباقي عند قسمة الأساس $7$ علـى $4$ هو $3$ وقوة هذا الباقي هي

$$3^2 = 9,$$

تطبيقات قواعد حساب التطابق

لقد مررنا الآن على قواعد حساب التطابق المختلفة, لنرى كيف يمكننا استخدام حساب التطابق لحل بعض المسائل المختلفة..

---

إذا كان اليوم هو يوم الخميس، أي يوم من أيام الأسبوع بعد مليون يوم؟

كما هو معروف فإن أسماء أيام الأسبوع تتكرر كل سبعة أيام. إذا كان اليوم هو يوم الخميس على سبيل المثال فسيكون يوم الخميس مرة أخرى بعد سبعة أيام أو أربعة عشر يوماً وهكذا، أي من مضاعفات السبعة وهي عدد أيام الأسبوع.

هذا ما يمكننا استخدامه لحل هذه المسألة. إذا كان عدد الأيام التي مرت من اليوم يقبل القسمة على $7$ (أي أن الباقي صفراً عند القسمة على $7$), فهذا يعني أن اليوم الذي نبحث عنه هو نفس اليوم من أيام الأسبوع (أي يوم الخميس في هذه الحالة). أما إذا كان الباقي عند القسمة علـى $7$ هو $1$ فهذا يعني أن اليوم المقابل من الأسبوع هو يوم الجمعة، أو كان الباقي $2$ عند القسمة علـى $7$ فسيكون اليوم هو السبت وهكذا إلخ...

لذلك سنبحث عن الباقي عند قسمة العدد مليون علـى الـ $7$. العدد مليون يمكننا كتابته في صيغة القوى \(10^6\). ويمكننا استخدام القاعدة $3$ ونستبدل $10$ بالباقي $3$ عند القسمة علـى $7$ ومن ثم نعيد كتابة هذه القوة باستخدام قوانين الأُسس والقوى:

$${10}^{6} \equiv {3}^{6} = {3}^{2 \cdot 3} = (3^2)^3 = 9^3 \, \pmod{7}.$$

يمكننا الآن استخدام القاعدة $3$ مرة أخرى واستبدال الأساس $9$ بالباقي $2$ (عند القسمة علـى $7$) لنحصل علـى

$${9}^{3} \equiv {2}^{3}\, \pmod{7}.$$

نلاحظ أن القوة الأخيرة أصبحت بسيطة ويمكن حسابها بسهولة

$$2^3 = 8.$$

الآن لقد توصلنا الى أن العدد \(10^6\) والـ $8$ لهما نفس الباقي عند القسمة علـى $7$. والباقي عند قسمة الـ $8$ علـى $7$ هو $1$, فهذا يعني أنّ الباقي في حالة قسمة المليون علـى $7$ يساوي $1$. لذلك إذا كان اليوم هو يوم خميس فان اليوم بعد مليون يوم سيكون يوم جمعة.

---

ما هو آخر رقم في العدد (72⁴ + 13⁶)؟

الرقم الأخير في أي عدد صحيح هو رقم الآحاد والذي يأخذ واحد من $10$ قيّم مختلفة ($0$ الى $9$). لكي نتعرف على الرقم الأخير للعدد $({72}^4 + {13}^6)$ هو نفس عملية حساب الباقي عند القسمة علـى $10$. سنستخدم القاعدتين $1$ و $3$ حيث يمكننا استبدال كل أساس بباقيه عند القسمة علـى $10$. لنحصل علـى

$$ {72}^{4} + {13}^{6} \equiv {2}^{4} + {3}^{6}\, \pmod{10}.$$

الآن سنستخدم قواعد الأسس والقوى لإعادة كتابة هذه الحدود لنحصل على

$$2^4 + 3^6 = 2^{2 \cdot 2} + 3^{3 \cdot 2} =(2^2)^2 +(3^3)^2 = 4^2 + 27^2 = 16 + 27^2$$

هنا يمكننا استخدام القاعدتين الأولى والثالثة مرة أُخرى لنحصل على

$$16 + 27^2 \equiv 6 +7^2 = 6 + 49 \equiv 6+9 = 15 \pmod{10}.$$

ملاحظة! انتبه لاستخدام علامتي التطابق والتساوي العادية.

الآن توصلنا الى أن العددين $({72}^4 + {13}^6)$ و$15$ لهما نفس الباقي عند القسمة علـى $10$. بما أن الباقي عند قسمة $15$ علـى $10$ هو $5$ فهذا يعني أن الباقي عند قسمة $({72}^4 + {13}^6)$ علـى $10$ هو أيضا $5$، أي أن الرقم الأخير في العدد $({72}^4 + {13}^6)$​ هو $5$.

---

باقي الأعداد الكبيرة

الأعداد الكبيرة مفيدة جداً في العديد من التطبيقات التقنية للحساب القياسي أو المعياري كتقنية التشفير على سبيل المثال. دعونا نأخذ مثال .

ماهو باقي العدد \( 5^{41615103} \) عند القسمة علـى $6$؟

نعلم أن الباقي الممكن هو أحد الأرقام $4 ,3 ,2 ,1 ,0$ أو $5$, لكن السؤال هو كيف يمكننا تحديد ذلك؟

لنتخيل أن لدينا سلسله من الأعداد تبدأ من العدد $1$ وتنتهي بالعدد $41615103$ كما يلي:

$$1, \, 2, \, 3, \,\text{...}, \, 41615103 $$

أي أن العدد التالي يزيد عن سابقه بواحد صحيح فقط, ونريدإيجاد نمط لبواقي قسمة العدد "$5$ مرفوعة لأعداد هذه السلسله" علـى العدد $6$. إبتداءً من $5^3, 5^2, 5^1$ وهكذا...

باقي قسمة العدد $5^1$ علـى العدد $6$ هو $5$ وهذا ما يمكننا كتابته كما يلي

$$5^1 \equiv 5 \pmod{6}$$

وباقي قسمة العدد $5^2$ علـى العدد $6$ هو $1$ وهذا ما يمكننا كتابته كما يلي

$$5^2 \equiv 1 \pmod{6}$$

ووفقًا للقاعدة $2$ ، يمكننا دمج هاتين المعادلتين بضرب الطرف الأيسر فـي الأيسر والأيمن فـي الأيمن للحصول على علاقة تطابق جديدة.

$$5^1 \cdot 5^2 \equiv 5 \cdot 1 \pmod{6}$$

وهذا ما يعطينا

$$5^3 \equiv 5 \pmod{6}$$

بنفس الطريقة يمكننا الحصول على \((5^4 \equiv 5 \pmod{6})\) والخ...

\begin{align*}
5^1 \equiv 5 \pmod{6}, \\
5^2 \equiv 1 \pmod{6}, \\
5^3 \equiv 5 \pmod{6}, \\
5^4 \equiv 1 \pmod{6}, \\
5^5 \equiv 5 \pmod{6},\\
\hspace{-5.6cm} ...
\end{align*}

لقد توصلنا الآن الى أن الباقي عند قسمة العدد \(5^n\) علـى $6$ هو $5$ للأعداد الصحيحة الفردية, \((n = 1, 3, 5, ...)\) و $1$ للأعداد الصحيحة الزوجية, \((n = 0, 2, 4, ...)\).

ومن الواضح أن العدد $41615103$ هو عدد صحيح فردي, ما يعني أن الباقي عند قسمة العدد \( 5^{41615103} \) علـى $6$ هو $5$.

---

فيديو الدرس بالسويدية