شبكة الرياضيات رمز

 

CRT Examples and Methods

 

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

 

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

x= 2 (mod 3)

x= 9 (mod 5)

 

الحل: نوجد عدة أعداد تحقق النظام الأول وهي

2, 5, 8, 11, 14, 17, ...

 

ثم ابحث في هذه الأعداد أيهما حل للتطابق الثاني , ستجد أن العدد 14 يحقق هذا التطابق , إذا 14 حل للنظام وحيث الحل وحيد معيار 15 حسب نظرية الباقي الصينية CRT فإن الحل هو x حيث

 

x= 9 (mod 5)

 

 

مثال 2: اوجد أصغر عدد موجب يحقق التطابقات

 

x= 1 (mod 2)

x= 2 (mod 3)

x= 3 (mod 5)

الحل:

الطريقة الأولى: العددين 2,3 أوليان نسبيا إذا كل x تحقق المعادلتين لابد أن تكون على الصورة

 

x=5+6k

 

ابدأ في اختبار أعداد بدلا من k لتجد أن k=8 يجعل x محققة للمعادلة الثالثة , أذا الحل هو

 

x=5+48=53

 

وهذا الحل هو معيار 30 حسب نظرية الباقي الصينية, إذا أصغر عدد هو x=23.

 

الطريقة الثانية:

المعادلة الأولى تعني x=2a+1 . عوض عن x في المعادلة الثانية بهذه القيمة, إذا

 

2a+1=2 (mod 3)

وبالتالي

2a=1 (mod 3)

 

باختبار الأعداد a=0,1,2 نجد أن a=2 حلا ولذلك a يكتب على لصورة العامة a=2+3b , بالتعويض بهذه القيمة في x ينتج

 

x=2a+1=2(2+3b)+1=5+6b

 

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

5+6b=3 (mod 5)

أي

b=3 (mod 5)

إذا b=3 وبالتالي x=23.

 

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

x = 1 (mod 2)

x = 1 (mod 3)

x = 1 (mod 4)

x = 1 (mod 5)

x = 1 (mod 6)

x = 0 (mod 7)

 

المعادلات الخمس الأولى تكافئ المعادلة

x = 1 (mod 60)

 

حيث 60 هنا هي المضاعف المشترك الأصغر للأعداد 2,3,4,5,6.وهذه المعادلة ناتج تطبيق^[م] متعاقب للحقيقة 1 في موضوع نظرية الباقي الصينية. إذا

 

x=60k+1

عوض بهذه القيمة في المعادلة السادسة لينتج

 

60k+1= 0 (mod 7)

 

بسط هذه المعادلة باستبعاد مضاعف العدد 7 من 60 لتحصل على

 

4k = -1 (mod 7)

4k = 6 (mod 7)

 

إذا k=5 وبالتالي

x=60k+1=300+1=301

 

وهو الحل الوحيد معيار 240 حسب نظرية الباقي الصينية CRT.

 

مثال 4: (استخدام نظرية CRT في حل تطابق خطي واحد) حل التطابق الخطي

 

19x= 3 (mod 70)

هذه المعادلة تكافئ النظام

 

19x= 3 (mod 2)

19x= 3 (mod 5)

19x= 3 (mod 7)

 

تأكد من ذلك, أي x حل للنظام إذا وإذا فقط كان حل للمعادلة, لاحظ أن 2,5,7 أولية نسبيا فيما بينها حاصل ضربهم 70.

 

الأعداد 3, 2, 2 تمثل حلول لمعادلات النظام على الترتيب. إذا النظام يكافئ

 

 

x= 3 (mod 2)

x= 2 (mod 5)

x= 2 (mod 7)

 

طبق نظرية الباقي الصينية الآن على هذا النظام الأخير نجد أن

 

 

 

x=35(1)(3)+14(4)(2)+10(5)(2) (mod 70)

 

قم ببعض الحسابات لوضع كل حد كمضاعفات للعدد 70 من اجل الحصول على أبسط صورة للعدد x

 

x=(70+35)+(70+14(3)))+(70+10(3))=35+42+30 =37 (mod 70)

 

إذا حل المعادلة

(mod 70) 19x=3 هو (mod 70) x=37.

 

 

مثال 5: (استخدام خوارزمية إقليدس أو الخوارزمية الاقليدية الموسعة): حل النظام

 

x= 13 (mod 27)

x= 7 (mod 16)

مخطط الحل: بما أن 27,16 أوليان نسبيا فإن هناك عددين صحيحين s,t بحيث

 

27s+16t=1

استخدم خوارزمية إقليدس أو الخوارزمية الاقليدية الموسعة لإيجاد هذين العددين , ستجد أن

 

3(27)+(-5)(16)=1

 

هذه المساواة توصلنا لحل النظام بسرعة. لاحظ أن كلا من العددين 27,16 مضروب في معكوسه الضربي المتطلب في نظرية الباقي الصينية, إذا الحل x (وفق هذه النظرية) هو

 

x=3(27)(7)+(-5)(16)(13) (mod 432)

 

ثم قم ببعض الحسابات لوضع كل حد كمضاعفات للعدد 432 من اجل الحصول على أبسط صورة للعدد x, وبعد حذف هذه المضاعفات نجد

 

x=27(5)-16(11)=-41=391 (mod 432)

 

مراجع

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

مقدمة في نظرية الأعداد فوزي الذكير , معروف سمحان