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

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

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