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

 

Chinese Remainder Theorem(CRT)

 

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

 

 

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

 

\begin{array}{l}x \equiv b_1 (\bmod n_1 ) \\x \equiv b_2 (\bmod n_2 ) \\\vdots \\x \equiv b_m (\bmod n_m )\end{array}

حل وحيد معيار n_1 n_2 \ldots n_k .

 

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

 

x \equiv y \equiv b_i (\bmod n_i ),\quad i = 1,2, \ldots ,k

 

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

 

x \equiv y(\bmod n_1 n_2 \ldots n_k )

 

أي ان الحلين متطابقان معيار n_1 n_2 \ldots n_k .

 

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

 

M_i = n_1 \ldots n_{i - 1} n_{i + 1} \ldots n_k

 

أي أن M_i هو حاصل الضرب مقسموما على n_i . إذا (M_i ,n_i ) = 1 وذلك لكل i. وبالتالي لكل i يوجد عدد صحيحx_i بحيث

 

M_i x_i \equiv 1\;(\bmod n_i )

 

 

أي أن x_i هو المعكوس الضربي للعدد M_i قياس n_i وهذا موجود , راجع موضوع المعكوس الضربي

 

http://www.mathramz.com/math/multiplicative_inverse_mod_n

 

ندعي أن العدد

x = M_1 x_1 b_1 + M_2 x_2 b_2 + \cdots + M_k x_k b_k

 

 

يمثل حل للنظام. لإثبات هذا يكفي إثبات أنه حل لأي معادلة x \equiv b_i (\bmod n_i ). لنعوض بالعدد x في هذه المعادلة

 

M_1 x_1 b_1 + M_2 x_2 b_2 + \cdots + M_k x_k b_k \equiv b_i (\bmod n_i )

 

 

العدد n_i يقسم كل حدود الطرف الأيسر ما عدا الحد رقم i . إذا M_j x_j b_j \equiv 0\;(\bmod n_j ) لكل j \ne i وعليه فإن

 

M_i x_i b_i \equiv b_i (\bmod n_i )

 

 

وهذا التطابق صحيح, فهو ليس سوى ناتج ضرب التطابقين M_i x_i \equiv 1\;(\bmod n_i ) , b_i \equiv b_i (\bmod n_i ). إذا x حل للنظام وتثبت النظرية.

 

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

 

حقيقة 1: التقارير التالية متكافئة

 

1) النظام
\begin{array}{l}x \equiv b(\bmod m) \\x \equiv c(\bmod n) \\\end{array} قابل للحل

 

2) المعادلة الديفونتية ms-nt = c-b قابلة للحل

 

3) b \equiv c(\bmod \;(m,n))

 

 

وبشكل عام إذا كان x,y عددين يمثلان حل لهذا للنظام فإن x \equiv y(\bmod lcm(m,n)) أي أن الحل وحيد معيار المضاعف المشترك الأصغر lcm(m,n).

 

البرهان: للنظام حل x إذا وإذا فقط وجد عددين صحيحين s,t بحيث

 

x=c+nt

x=b+ms

وهذا يؤدي إلى

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))

 

إذا x \equiv y(\bmod 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 \equiv 11(\bmod 12) وبالتالي ينخفض النظام إلى

 

x = 4 (mod 5)

x = 0 (mod 7)

x = 11 (mod 12)

 

أعداد المعايير n_1 = 5,n_2 = 7,n_3 = 12 أولية نسبيا مثنى مثنى. كذلك

 

M = 420,M_1 = 84,M_2 = 60,M_3 = 35

 

 

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

 

84x_1 = 1(\bmod 5)

 

جزء معامل x_1 إلى 80+4, العدد 80 يقبل القسمة على 5 وبالتالي تختصر المعادلة إلى

4x_1 = 1(\bmod 5) ومنه ينتج أن x_1 = 4.

 

بطريقة مشابهة نجد أن x_2 = 2,\;x_3 = 11. إذا الحل هو

 

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

 

مراجع

http://www.cut-the-knot.org/blue/chinese.shtml

http://www.math.okstate.edu/