Katta sonlarni ko’paytuvchilarga ajratish algoritmlari. Reja

5.3.1-Misol(1-holat (a, m) = d uchun.) 126¹⁰²⁰ ni 138 ga bo’lgandagi qoldiqni toping.
Yechilishi. Demak, (4.3)formulaga ko’ra, a=126, b=1020, m=138. Quyidagi taqqoslamani yechish kerak:
x ≡ 126¹⁰²⁰ (mod 138) (4.5)
1) (a, m) = (126,138) ≠1. Shuning uchun 126 va 138 larni tub ko’paytuvchilarga ajratamiz.
126=2∙3²∙7, 138 = 2∙3∙23 ligidan (126,138) = 6. Demak, d = 6.
a= a₁d →126 = a₁∙6 → a₁=21. Demak, 126 =21∙6.
m= m₁d →138 = m₁∙6 → m₁=23. Demak, 138 =23∙6.
x= x₁d → x = x₁∙6
Endi 126,138 va x larni yangi ko’rinishini (4.5) ga qo’yamiz.
x₁∙6 ≡ 126∙126^1020-1 (mod 23∙6)
x₁∙6 ≡ 21∙6∙126¹⁰¹⁹ (mod 23∙6) | 6 ga qisqartiramiz.
x₁ ≡ 21∙126¹⁰¹⁹ (mod 23)
Demak, a=126, b=1019, m=23. (a, m) = (126, 23) =1 bo’lgani uchun (4.4) formulaga ko’ra a ≡ a₁ (mod m) va b ≡ b₁ (mod φ(m)) dan a₁, b₁ va φ(m) larni qiymatini topamiz.
m=23 tub son bo’lgani uchun φ(23) = 22.
126 ≡ a₁ (mod 23) 126 = 23∙5+11 bo’lgani uchun a₁=11.
1019≡ b₁ (mod 22) 1019 = 22∙46+7 bo’lgani uchun b₁=7.
Endi (4.4) formulaga ko’ra x₁ ≡ =21∙11⁷ (mod 23)=21∙11∙(11³)²(mod 23)= =231∙(1331)²(mod 23) ≡1∙(20)²(mod 23) = 400(mod 23) ≡ 9(mod 23)
231=23∙10+1, 1331=23∙57+20, 400=23∙17+9.
Boshda belgilashimizga ko’ra, x= x₁∙6≡ 9∙6 (mod 23)=54(mod 23).
Demak, 126¹⁰²⁰ ni 138 ga bo’lganda qoldiq 54 ga teng ekan.


Uyga vazifa
5.1-Misol. Bo’linishning qoldiqlarini toping:
a) 109³⁴⁵ ni 14 ga;
b) 439²⁹¹ ni 60 ga;
c) 293²⁷⁵ ni 48 ga.
5.2-misol. 243⁴⁰² sonining oxirgi uchta raqamini toping.