Urganch davlat universiteti axborot texnologiyalari kafedrasi

4.3. Bo‘lishdan qoldiqlar. 

Ko‘plab  masalalarga  summalarni  bo‘lishdagi  qoldiqlarni,  farqi  ratsiyo‘nal  yechim  davomida 

o‘zgarmaydigan  berilgan  natural  p  songa  qandaydir  sonlarni  ko‘paytirishlarning  qoldiqlarni 

hisoblashga to‘g‘ri keladi. Odatda buning uchun avvalo summani izlash va shu kabilar, keyin esa 

qoldiqni hisoblash shart emas- quyidagi argumentlarni ishlatish mumkin:  

(a+b) mod p = ((a mod p)+(b mod p))mod p, 

(a+b) mod p = ((a mod p)+(b mod p))mod p,  a>b,  

 

(4.6) 

(a+b) mod p = ((a mod p)+(b mod p))mod p, 

Masalan, (a+b) mod p ni hisoblash uchun a va b sonlarni bilish shart emas – faqat a mod p va b 

mod p ni bilish yetarli. Bu ayniyatni isbotlaymiz (boshqa operatsiyalarning isbotlari anologikdir): 

(a+b) mod p = ((a div p)*p+a mod p+(b div p)*p+b mod p) mod p = ((a modp)+(b mod p)) mod 

p. 

Ayirishlar uchun formula boshqalaridan shu bilan farq qiladiki, ko‘plab kompilyatorlarda manfiy 

sonini natural songa bo‘linuvchidagi qoldiq manfiy bo‘ladi: masalan (-13 mod 10) 7 emas, balki 

3 bo‘ladi. 

Bo‘lishlar  uchun  analogik  f  formulalar  yo‘q  va  bo‘lishi  mumkin  emas,  chunki  avval  x  sonini 

olish kerak, keyin esa bo‘lish noto‘g‘ri songa. Masalan,  

(16 mod 2) mod 100=10 100=8 30=((16 mod 100) div 2) mod 10.