أنظمة التطابقات الخطية في متغير واحد

 

Linear Congruence Systems in One Variable

 

يقال أن العدد x حل للنظام

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


 

المكون من تطابقات خطية بمتغير واحد إذا كان x حل لكل معادلة a_i x \equiv b_i (\bmod n_i ) من النظام.

 

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

 

حقيقة 1: العدد x حل للنظام

 

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

 

إذا وإذا فقط كان x حل للنظام

\begin{array}{l}x \equiv c_1 (\bmod n_1 /d_1 ) \\x \equiv c_2 (\bmod n_2 /d_2 ) \\\vdots \\x \equiv c_m (\bmod n_m /d_m ) \\\end{array}

 

حيث c_i حل للتطابق a_i x \equiv b_i (\bmod n_i ) و d_i = (a_i ,n_i ).

 

البرهان: ليكن x حل للنظام, إذا x حل لأي معادلة x \equiv b_i (\bmod n_i ) من النظام. إذا

 

x = c_i + \frac{{n_i k}}{{d_i }},\quad k \in \{ 0,1,2, \ldots ,d_i - 1\}

 

 

الحل x يمكن كتابته بصورته العامة المعبرة عن الفصل [x] بالشكل

 

x = c_i + \frac{{n_i k}}{{d_i }} + ns

 

 

حيث s عدد صحيح. خذ الآن n/d عامل مشترك , إذا

 

x = c_i + \frac{{n_i }}{{d_i }}(sd_i + k)

 

إذا

x \equiv c_i \;(\bmod n_i /d_i )

 

وحيث المعادلة كانت اختيارية فإن x حل للنظام الثاني.

 

عكسيا, إذا كان x حل للنظام الثاني فإن x حل لأي معادلة x \equiv c_i \;(\bmod \frac{{n_i }}{{d_i }}) منه. إذا

 

x = c_i + \frac{{n_i }}{{d_i }}m

 

حيث m عدد صحيح. باستخدام خوارزمية القسمة وبقسمة m على d يوجد صحيح s وباقي k بحيث

 

m = sd_i + k

إذا

x = c_i + \frac{{n_i }}{{d_i }}(sd_i + k) = c_i + \frac{{n_i k}}{{d_i }} + n_i s

 

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

 

مثال 1: حل النظام

2x=4 (mod 10)

9x=12 (mod 33)

 

بالتجريب نجد أن c_1 = 2,\;c_2 = 5 حلين للمعادلة الأولى والثانية على الترتيب. إذا وفق الحقيقة السابقة الحل x إن وجد هو حل للنظام التالي

 

x=2 (mod 5)

x=5 (mod 11)

 

لنبحث عن حل لهذا النظام الجديد. من المعادلة الأولى في هذا النظام لدينا

 

x=2+5r

 

حيث r عدد صحيح. بالتعويض في المعادلة الثانية نجد 2 + 5r \equiv 5(\bmod 11) ومنها

 

5r=3 (mod 11)

 

وبالتالي r=5+11s يمثل حل لهذا التطابق. بالتعويض في x عن r نجد أن

 

x=2+5(5+11s)= 27+55s

 

إذا

x=27 (mod 55)

 

وهو حل النظام الثاني وبالتالي حل للنظام الأول.

 

الحل الذي توصلنا له للنظام الثاني نستطيع الحصول عليه مباشرة باستخدام نظرية الباقي الصينية , انظر

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