Mavzu: Yevklid algoritmi

Yaroqlilik isboti [ tahrirlash ]

Evklid algoritmining haqiqiyligini ikki bosqichli argument bilan isbotlash mumkin. Birinchi bosqichda yakuniy nolga teng bo'lmagan qoldiq r _N -1 a va b ni bo'lish uchun ko'rsatilgan . U umumiy bo'luvchi bo'lgani uchun u eng katta umumiy bo'luvchi g dan kichik yoki unga teng bo'lishi kerak . Ikkinchi bosqichda a va b ning har qanday umumiy bo'luvchisi , shu jumladan g , r _{N -1 ga} bo'linishi kerakligi ko'rsatilgan ; shuning uchun g r _N -1 dan kichik yoki teng bo'lishi kerak . Bu ikki qarama-qarshi tengsizlik r _{N ni bildiradi−1} = g .
r _N −1 a va b ni ham (birinchi qadam) bo‘lishini ko‘rsatish uchun r _N −1 o‘zidan oldingi r _{N −2 ni ajratadi.}
r _N -2 = q _N r _N -1
chunki oxirgi qoldiq r _N nolga teng. r _N -1 o'zidan keyingi oldingi r _{N -3 ni ham ajratadi}
r _N -3 = q _N -1 r _N -2 + r _N -1
chunki u har ikkala shartni tenglamaning o'ng tomoniga ajratadi. Xuddi shu argumentni takrorlash, r _N -1 oldingi barcha qoldiqlarni, shu jumladan a va b ni ajratadi . Oldingi qoldiqlarning hech biri r _N -2 , r _{N -3 va boshqalar} a va b ni ajratmaydi , chunki ular qoldiq qoldiradi. r _N -1 a va b ning umumiy bo'luvchisi bo'lgani uchun r _N -1 ≤ g .
Ikkinchi bosqichda a va b ni ham bo‘luvchi har qanday natural c soni (boshqacha aytganda, a va b ning har qanday umumiy bo‘luvchisi) r _k qoldiqlarini ajratadi . Ta'rifga ko'ra, a va b c ning ko'paytmalari sifatida yozilishi mumkin : a = mc va b = nc , bu erda m va n natural sonlardir. Shuning uchun, c boshlang'ich qoldiqni r ₀ ga bo'ladi , chunki r ₀ = a - q ₀ b = mc - q ₀ nc = ( m - q ₀ n ) c . O'xshash argument c ning keyingi qoldiqlarni ham bo'lishini ko'rsatadi r ₁ , r ₂ , va hokazo. Shuning uchun eng katta umumiy bo'luvchi g r _N -1 ni bo'lishi kerak , bu g ≤ r _N -1 ni nazarda tutadi . Argumentning birinchi qismi teskarisini ko'rsatganligi sababli ( r _N -1 ≤ g), bundan g = r _N -1 kelib chiqadi . Shunday qilib, g barcha keyingi juftlarning eng katta umumiy boʻluvchisidir:
g = gcd( a , b ) = gcd( b , r ₀ ) = gcd( r ₀ , r ₁ ) = … = gcd( r _N -2 , r _N -1 ) = r _N -1 .
Misol:
Misol uchun, Evklid algoritmidan a = 1071 va b = 462 ning eng katta umumiy boʻluvchisini topish uchun foydalanish mumkin. Boshlash uchun, 462 ning karralari 1071 dan qoldiq 462 dan kichik boʻlguncha ayiriladi. Bunday ikkita koʻpaytmani ayirish mumkin ( q) . ₀ = 2), 147 qoldig'ini qoldirib:
1071 = 2 × 462 + 147.
Keyin 147 ning karralari 462 dan qoldiq 147 dan kichik bo'lgunga qadar ayiriladi. Uch karrali ayirish mumkin ( q ₁ = 3), qoldiq 21:
462 = 3 × 147 + 21.
Keyin 147 dan 21 ning koʻpaytmalari qoldiq 21 dan kichik boʻlguncha ayiriladi. Etti karrali ayirish mumkin ( q ₂ = 7 ), qoldiq qolmaydi:
147 = 7 × 21 + 0.
Oxirgi qoldiq nolga teng bo'lganligi sababli, algoritm 1071 va 462 ning eng katta umumiy bo'luvchisi sifatida 21 bilan tugaydi. Bu yuqoridagi tub faktorizatsiya orqali topilgan gcd (1071, 462) bilan mos keladi . Jadval shaklida bosqichlar



Evklid algoritmini eng katta umumiy bo'luvchi uchun yuqorida berilgan plitka o'xshashligi nuqtai nazaridan tasavvur qilish mumkin. ^[17] Faraz qilaylik, biz a × b toʻrtburchakni toʻgʻridan-toʻgʻri toʻrtburchaklar bilan qoplashni xohlaymiz , bunda a ikki raqamdan kattasi. Biz birinchi navbatda b × b kvadrat plitalari yordamida to'rtburchakni plitka qo'yishga harakat qilamiz ; ammo, bu r ₀ × b qoldiq to'rtburchakni oxirigacha qoldiradi, bu erda r ₀ < b . Keyin qoldiq to'rtburchakni r ₀ × r ₀ kvadrat plitalar bilan qoplashga harakat qilamiz . Bu ikkinchi qoldiq to'rtburchakni qoldiradir ₁ × r ₀ , biz r ₁ × r ₁ kvadrat plitalari yordamida plitka qo'yishga harakat qilamiz va hokazo. Ketma-ketlik qoldiq to'rtburchaklar bo'lmaganda, ya'ni kvadrat plitalar oldingi qoldiq to'rtburchakni to'liq qoplaganida tugaydi. Eng kichik kvadrat kafelning yon tomonlarining uzunligi asl to'rtburchakning o'lchamlarining GCD dir. Misol uchun, qo'shni rasmdagi eng kichik kvadrat kafel 21 × 21 (qizil rangda ko'rsatilgan) va 21 - 1071 va 462 GCD, asl to'rtburchakning o'lchamlari (yashil rangda ko'rsatilgan).