2 Лаборатория иши Шахсий компьютерларда маълумотларнинг таърифланиши, кодлаш

Энг катта умумий бўлувчи ва энг кичик умумий каррали
а ва b нинг энг катта умумий бўлувчиси(ЭУБ(НОД))ни топишни биз ҳаммамиз мактабда ўрганганмиз. Яъни бу, а ва b қолдиқсиз бўлинадиган энг катта бутун сон d. Ҳеч қандай қийинчиликсиз ҳар бир ўқувчи айтиши мумкин ЭУБ(12,18)=6 га. Агар бу икки сондан бири 0 га тенг бўлсачи? Агар

а ва b манфий бўлсачи? Бу ҳақда мактаб дарсларида хар биримиз ўйлаб кўрганмиз.Бу саволларга жавоб бериши учун умумий бўлувчини нима эканлигини аниқлаштириб оламиз.

1-аниқлаштириш. а ва b қолдиқсиз бўлинадиган 0га тенг бўлмаган энг катта бутун сон d. Бу қуйидагича бўлади: d= ЭУБ (a,b). Агар иккита сон ҳам нолга тенг бўлса ЭУБ(0,0)=0. Булардан келиб чикиб қуйидаги тенгликка эга бўламиз:

ЭУБ(a,b)= ЭУБ(b,a),

ЭУБ(a,b)= ЭУБ(-a,b)

ЭУБ(a,0)=|a|

Айтиш мумкин нима учун ЭУБ (-12,18) тенг 6га, нега -6га эмас? -12 ва 18 , 6га ва -6га бўлинади. Буни жавоби осон: ЭУБ – бу энг катта умумий бўлувчи, 6 сони эса -6 дан катта .

Энг катта умумий бўлувчи ва энг кичик каррали бир-бири билан чамбарчас боғлиқдир.

2-аниқлаштириш. а ва b сонларининг Энг кичик умумий каррали(ЭУК(НОК))си а ва b сонларининг энг кичик умумий бўлинувчисидир.

Арифметиканинг асосий теоремаси шуни кўрсатадики, ҳар қандай натурал сон n ни оддий сонлар кўпайтмаси сифатида тасвирлаш мумкин:

Натурал сонларнинг бундай кенгайтмаси каноник дейилади.Бундан қуйидаги келиб чиқади, агар

бўлса, қуйидагича бўлади


Мисол 1. a = 24 ва b = 18 сонларини кўриб чиқамиз.Уларни оддий кўпайтма шаклида ёзиб оламиз 24 = 2³·3, 18 = 2·3². Шунингдек

НОД(24, 18) = 2^min(3,1) · 3^min(1,2) = 2¹ · 3¹ = 6,

   НОК(24, 18) = 2^max(3,1) · 3^max(1,2) = 2³ · 3² = 8 · 9 = 72

Худди шундай сонларни каноник усулда ёзилишини биз мактабда ЭУБ ва ЭУК ни топиш учун ўрганганмиз.Бироқ, бу усул алгоритмни ҳисоблашни реализациясида у даражада эффектли эмас.

Кейинги яққол фактни кўриб чиқамиз. Агар ЭУБ(a, b) = d, унда a ва b , d.га бўлинади. a – b фарқи ҳам d га бўлинади. ЭУБ ни ҳисоблашни рекуррентлиги