نظرية الباقي الصينية CRT

نظرية الباقي الصينية: CRT
Chinese Remainder Theorem-CRT
سميت بهذا الاسم لأن أول ظهور لها على ما يعرف كان في الكتاب الصيني الموغل في
القد م Sun Tzu Suan Ching ويسمى أيضا Sunzi Suanjing
الذي كتب من قبل الصيني Sun Zi في القرن الثالث الميلادي وهناك من يرى
أنه كتب بعد هذا التاريخ بسنين عديدة.

نظرية 1 (نظرية الباقي الصينية CRT):
إذا كانت الأعداد الصحيحة الموجبة أولية نسبيا مثنى مثنى فإن للنظام

حل وحيد معيار .
البرهان: نثبت أولا وحدانية الحل فيما لو وجد, ثم بعد ذلك نثبت وجود
حل بالشرط المذكور في النظرية. افرض أن x,y حلين للنظام. إذا

إذا لكل i=1,2,..,k فإن تقسم الفرق x-y . ولكن كل الأعداد
نسبية أوليا مثنى مثنى, بمعنى أي اثنين منهما لا يقسمهما سوى العدد واحد. إذا مضاعفهم المشترك الأصغر يقسم x-y وبالتالي
أي ان الحلين متطابقان معيار .
إثبات وجود الحل, وهذه طريقة بنائية في البرهان , تعطينا صيغة رياضية للحل
وليس إثبات وجود فقط. لأي حيث i=1,2,..,k عرف

أي أن هو حاصل الضرب مقسموما على . إذن
وذلك لكل i. وبالتالي لكل i يوجد عدد صحيح بحيث
أي أن هو المعكوس الضربي للعدد قياس وهذا موجود
ندعي أن العدد

يمثل حل للنظام. لإثبات هذا يكفي إثبات أنه حل لأي معادلة .
لنعوض بالعدد x في هذه المعادلة

العدد يقسم كل حدود الطرف الأيسر ما عدا الحد رقم i .
إذن لكل وعليه فإن

وهذا التطابق صحيح, فهو ليس سوى ناتج ضرب التطابقين
و .
إذن x حل للنظام وتثبت النظرية.
فيما يلي نعطي حقيقة تعتبر مكملة لنظرية الباقي الصينية وتتعلق بأنظمة
التطابقات الخطية التي لا شرط نظرية الباقي, ثم نورد مثال بعد ذلك نوضح كيف
تستخدم هذه الحقيقة إلى جانب CRT لحل نظام معطى.
حقيقة 1: التقارير التالية متكافئة
1) النظام
قابل للحل
2) المعادلة الديفونتية ms-nt = c-b قابلة للحل
3)
وبشكل عام إذا كان x,y عددين يمثلان حل لهذا للنظام فإن

أي أن الحل وحيد معيار المضاعف المشترك الأصغر .
البرهان: للنظام حل x إذا وإذا فقط وجد عددين صحيحين s,t بحيث
x=b+ms و x=c+nt
وهذا يؤدي إلى ms-nt = c-b
وحيث d يقسم الطرف الأيسر فإنه يقسم الطرف الأيمن وبالتالي
c-b = 0 (mod d) or c=b (mod d)
إذا ويجد عدد صحيح k بحيث: c-b=dk
ولكن من متطابقة بيزو يوجد z,w بحيث: d=zm+wnبالتعويض عن d في المساواة السابقة ينتج
c-b=( zm+wn)k= (zk)m+(wk)n
إذن : c- (wk)n = (zk)m+b
لاحظ الطرف الأيمن حل للمعادلة الأولى من النظام والطرف الأيسر حل للمعادلة الثانية منه, إذا العدد x حيث
x=c- (wk)n = (zk)m+b
حل للنظام وبهذا يثبت صحة تكافؤ 1) و 2) و 3).
لإثبات وحدانية الحل معيار المضاعف المشترك الأصغر افرض أن y حل آخر للنظام, إذا
x-y = 0 (mod m) , x-y = 0 (mod n)
وهذا يقتضي: x-y = 0 (mod lcm(m,n))
إذن
.مثال 1
لدى فتاة سلة من البيض تريد بيعها, عند سؤالها كم عدد البيض قالت لا أعرف
ولكن إذا أحصيته اثنتان يبقى واحدة وإذا أحصيته ثلاثا يبقى بيضتين وإذا عددته أربعا
يبقى ثلاث بيضات وإذا عددته خمسا يبقى أربع وإذا عددته ستا يبقى خمسا أما إذا
عددته سبعا فلا يبقى منه شيء.كم عدد البيض الذي في السلة؟.
ليكن x عدد البيض. إذا ما ذكرته الفتاة يمثل النظام التالي
x = 1 (mod 2)
x = 2 (mod 3)
x = 3 (mod 4)
x = 4 (mod 5)
x = 5 (mod 6)
x = 0 (mod 7)
نريد حل المسألة باستخدام CRT وذلك لما في هذه الطريقة من جزئيات مهمة نود
أن يتعرف القارئ عليها وسنعرض في نهاية الحل طريقة أخرى. لكي نطبق CRT
بحيث أن تكون أعداد المعيار أولية نسبيا مثنى مثنى, وهذا غير متحقق هنا, لذلك
نحاول حذف بعض من المعادلات أو دمج بعضها في معادلة واحدة.
واضح انه عندما تكون المعادلة الثالثة صحيحة تكون الأولى صحيحة لذلك يمكن حذف
الأولى أيضا إذا كانت المعادلة الخامسة صحيحة تكون الثانية صحيحة لذلك
يمكن حذف الثانية المعادلة الثالثة والسادسة يمكن دمجهما
في المعادلة وبالتالي ينخفض النظام إلى
x = 4 (mod 5)
x = 0 (mod 7)
x = 11 (mod 12)
أعداد المعايير أولية نسبيا مثنى مثنى. كذلك

لنعين المعكوس الضربي للعدد معيار 5 وذلك بحل المعادلة

جزء معامل إلى 80+4, العدد 80 يقبل القسمة على 5 وبالتالي تختصر المعادلة إلى
ومنه ينتج أن .
بطريقة مشابهة نجد أن .
إذا الحل هو
x=84(4)(4)+60(0)(2)+35(11)(11)
وهذا الحل هو معيار M=420 ولذلك ولاختصار الحسابات نعمد إلى الإستفادة من كون
84, 60, 35 قواسم للعدد M ونحاول أكمالها لتكون من مضاعفات M
حت يمكن حذفها من الحساب كما يلي
x=84(15+1)+0+35(120+1)
x=84(15)+84+35(120)+35
الحدين الأول والثالث مضاعفات للعدد M إذن
x=84+35=119
إذا 119 هو اقل عدد من البيض تملكه الفتاة.
طريقة أخرى
من طبيعة هذه المسألة أن الباقي أقل من المقسوم عليه بمقدار واحد فقط
وذلك في كل الأعداد من 2 إلى 6. إذا بإضافة 1 إلى عدد البيض x يصبح x+1
من مضاعفات كلا من 2,3,4,5,6, ويزيد عن مضاعفات العدد 7 بمقدار 1.
العدد 60 هو المضاعف المشترك الأصغر لأعداد 2,3,4,5,6, وكلما ما علينا الآن هو
مضاعفة هذا العدد حتى يعطي باقي قدره 1 عند قسمته على 7
من المحاولة الأولى يتحقق المطلوب حيث
120=2(60)=120=119+1=7(17)=1
إذا العدد المطلوب هو x=119 وهو عدد البيض المرتقب.
عكس CRT غير صحيح بشكل عام
مطلوب منك أن تحدد أي النظامين
x = 3 (mod 24)
x = 9 (mod 30)
و
x = 3 (mod 24)
x = 8 (mod 30)
قابل للحل وأيهما غير قابل للحل؟
مسائل

حل النظام التالي
3x = 5 (mod 23)
5x = 7 (mod 24)
7x = 3 (mod 25)

اوجد الحدودية f التي فيها
f(-1)=9, f(2)=-16, f(5)=15