أنظمة الرواسب (البواقي) صورة محترف أح

أنظمة الرواسب (البواقي)

Residue Systems

هذا المفهوم يعتبر أحد أهم مفاهيم التطابقات خصوصا وساهم في تقديم تصور أعمق للتطابقات, الفكرة تبدأ ملاحظة أنه عندما نختار عدد طبيعي n فإننا نعلم أن بواقي القسمة على هذا العدد هي

0,1,2,..., n-1

هذه البواقي محدودة العدد جزأت مجموعة الأعداد الصحيحة إلى فصول تكافؤ

[0], [1], [2],...,[n-1]

باستخدام العلاقة

a \sim b \Leftrightarrow a \equiv b\;(\bmod n)

وكما يعلم من له معرفة بعلاقات التكافؤ وفصولها أن العمليات على الفصول تكون مستقلة عن ممثل الفصل, نحن هنا نهتم بهذا السؤال من جانب نظرية العدد فنقول أن اختيار أي ممثل لفصل التكافؤ هو ممثل عن الباقي الذي يظهر عن قسمة كل عناصر الفصل على العدد n. بمعنى آخر لو قمنا باختيار n عنصرا بطريقة عشوائية من جميع فصول التكافؤ ولتكن \{ a_0 ,a_1 , \ldots ,a_{n - 1} \} ثم سجلنا بواقي قسمة هذه الأعداد على n فسنجد أن البواقي جميعها ستظهر

0,1,2,..., n-1

ولذلك عناصر مثل هذه المجموعة \{ a_0 ,a_1 , \ldots ,a_{n - 1} \} تسمى نظام بواقي تام أو نظام رواسب تام. الآن نقدم التعريف الرياضي لمفهوم أنظمة الرواسب.

تعريف 1: نقول أن الأعداد r_1 ,r_2 , \ldots ,r_n تمثل نظام بواقي (رواسب) تام complete residue system معيار n إذا كان كل عدد صحيح يطابق واحد فقط من هذه الأعداد معيار n.

لذلك يكفي لاختبار ما إذا كان n من الأعداد الصحيحة تمثل نظام بواقي تام معيار n أن نثبت أن كل عدد منها يطابق عدد واحد فقط من الأعداد 0,1,2,...,n-1. هذه الأعداد الأخيرة هي نظام رواسب تام بحد ذاتها.

هناك طريقة أخرى لاختبار ما إذا كان عدد n من الأعداد r_1 ,r_2 , \ldots ,r_n يمثل نظام بواقي تام معيار n أم لا, نحددها الآن.

حقيقة 1: الأعداد r_1 ,r_2 , \ldots ,r_n تمثل نظام بواقي تام معيار n إذا وفقط إذا كان r_i \not \equiv r_j لكل i \ne j.

في إثبات هذه الحقيقة نسير على النحو التالي:

افرض أن r_1 ,r_2 , \ldots ,r_n تمثل نظام بواقي تام معيار n إذا r_i \not \equiv r_j لكل i \ne j لأن عكس ذلك سيجعل r_i مثلا يطابق عنصرين من نظام البواقي وهذا مستحيل. عكسيا افرض أن r_i \not \equiv r_j لكل i \ne j إذا كل الأعداد

r_1 ,r_2 , \ldots ,r_n

لها بواقي مختلفة عند قسمتها على العدد n. وحيث أن عددها n فإن كل عدد صحيح يطابق واحد فقط من هذه الأعداد معيار n وبالتالي r_1 ,r_2 , \ldots ,r_n نظام بواقي تام معيار n.

نختم بهذه النظرية المفيدة في أنظمة الرواسب التامة.

نظرية 1: إذا كان r_1 ,r_2 , \ldots ,r_n نظام بواقي تام معيار n وكان a عدد صحيح بحيث (n,a) = 1 فإن

ar_1 + b,\;ar_2 + b,\; \ldots \,,\;ar_n + b

نظام بواقي تام معيار n وذلك لأي عدد صحيح b. وكحالة خاصة فإن كل عدد n من الأعداد الصحيحة المتتابعة تمثل نظام بواقي تام معيار n.

باستخدام الحقيقة السابقة يكفي إثبات عدم تطابق أي عنصرين من

ar_1 + b,\;ar_2 + b,\; \ldots \,,\;ar_n + b

معيار n. لذلك افرض جدلا أن ar_i + b \equiv ar_j + b إذا ar_i \equiv ar_j ومنه a(r_i - r_j ) \equiv 0 كل هذه التطابقات معيار n ولكن كتبت مختصرة . ولكن r_i - r_j \ne 0 وكذلك a أولي نسبيا مع n. إذا r_i \equiv r_j \;(\bmod n) وهذا يناقض الحقيقة أعلاه حيث العنصرين من نظام رواسب تام. إذا الفرض خاطيء ويثبت المطلوب.

الحالة الخاصة المشار إليها في النظرية نتتج من حقيقة أن 0,1,2,...,n-1 نظام بواقي تام وأن أي عدد n من الأعداد الصحيحة المتتابعة تنتج من إضافة عدد ثابت b لهذه الأعداد.