!
b = r1m2+r2
6
0 < r < r
r1 = r2mz+r3
(
0 < r < r2
r2 = r3m4 +r4
0 < r < r3
ri-2 = r;-m; +r;
• 0 < r < F¡-1
ri-1 = rm+1
+0
فإن
(r = g.c.d(a,b . كما أنه يمكن استخدام نفس المعادلات ابتداءً من الأخيرة
إلى الأولى لإيجاد m,nez بحيث أن r = am + bn
البرهان :
i+1
بما أن
i-1
•
" .
;ri-m; r 2 \
•
... إذن عدد البواقي لا يمكن أن يزيد عن (1 - m) وعليه يوجد EN بحيث أن 0 = Tint . ولكي نثبت أن ,r = g.c.d(a . لاحظ أن rmat = 1- يعني أن ١٣١ ٢ . لكن + + rim = " ، إذن " . وحيث أن 1 + T3 = Tigmi . إذن 3\" وعليه يمكن الاستمرار بنفس 71 1 r-zm 13 الأسلوب لنثبت أن \ و \ . إذن " قاسم مشترك للعددين a,b . وإذا كان نجد أن cri . ومن b = rim tr نجد أن c وهكذا يمكن استخدام جميع المعادلات الواحدة بعد الأخرى ونصل إلى أن \ . إذن (r = g.cda,b . ولإيجاد m,nez بحيث أن r = am + bn استخدم المعادلات الواردة في المبرهنة من الأسفل إلى الأعلى تجد أن
• c\a
I CEZ*
المعادلة
c\b فمن المعادلة
a = bm1 +r1
r; = r;_2 − r¡_,m; = r; ~2 − (r;-3 — r;-2m1_1)m;
-2
= ... = am + bn
= −r;_3m; + r;_2 (1 + m¡_¿m; ) =
i-2
1-1
مثال ١-٣-٤:
(أ) أوجد القاسم المشترك الأعظم للعددين 252 ، 90 ثم أوجد nez, بحيث أن
d = 252m+90n
·
لإيجاد d لاحظ أن 72 (90) 252 ، 18+ (72).1 = 90 ، (18)4 = 72
18 = d . ولإيجاد nez, بحيث أن 90 + d = 252m
•
إذن
لاحظ أن 4 - 90 = 72 . إذن (3) + (1-)252 = d → d - 90 + (90)2 = 252
إذن 1- = m ،
·
n = 3
(ب) أوجد القاسم المشترك الأعظم للعددين 2746 ، 335 ثم عبر عنه بالشكل
2746m+335n
•
لإيجاد القاسم المشترك الأعظم لاحظ أن
. 5=5×1 ، 66 = 13(5) +1
-:
• 335=5(66)+52746=8(335) +66
١٤
الكتاب — ص ١٤