2-ma’ruza Mavzu: Faktorlash muammosi va uni hisoblash; Qoldiq haqidagi Xitoy teoremasi; Sonni tub ko‘paytuvchilarga ajratish

4-kadam . 3-qadamning oxirgi natijasi r₀ = aye (mod n) biz qidirayotgan yechim deb elon qilinadi.
Misol-1. 43¹⁰³² (mod 41) – qoldiqni hisoblang.
Yechish: e=1032, bu sonni ikkilik sanoq sistemasiga o‘tkazamiz:
1032= 2¹⁰ +2³ = 10000001000₂
yani m=10 , (v₁₀ v₉ v₈ v₇ v₆ v₅ v₄ v₃ v₂ v₁v₀ ) ₂ = (10000001000)₂
Demak, algoritm qadamiga muvofiq:
R_m , m =10,9,…1,0
Qiymatlar quyidagi qoida bo‘yicha hisoblanadi:
R₁₀ = 43 (mod 41)=2,
R₉ = 2² *(mod 41)= 4,
R₈ = 4²(mod 41)=16,
R₇ =16²(mod 41)=10,
R₆ = 10² (mod 41)=18,
R₅ = 18² (mod 41)= 37,
R₄ =37²(mod 41)= 16,
R₃ =16² *43(mod 41)= 20
R₂=20² (mod 41)=31,
R₁= 31²(mod 41)=18,
R₀ = 18² (mod 41)=37.
javob
43¹⁰³² (mod 41) = 37.
Mashqlar
Effektiv algoritm yordamida quyidagilar hisoblansin.
№1 3²⁷⁵ (mod 100).
№2 6⁵⁰⁰⁰ ( mod 1000).
№3 11²⁴⁶⁸¹ ( mod 83).
Kvadratik taqqoslama
Tarif. Ushbu
ax² + b x + c 0 ( mod m), (1)
ko‘rinishdagi taqqoslama kvadratik taqqoslama deyiladi.
Bu yerda a soni m ga bo‘linmaydi.
Teorema. (1) ko‘rinishdagi kvadratik taqqoslamani har doim

x ² d ( mod m₁ ) (2)
ko‘rinishga keltirsh mumkin.
Haqiqatan , (1) ning ikkala qismini va va modulini 4*a ga ko‘paytirsak ( bunga haqqimiz bor, chunki taqqoslama xossasiga ko‘ra ):
4a² x² + 4 a b x + 4as 0 ( mod 4m*a)
yoki
(2ax +b) ² – b² + 4ac 0 ( mod 4m*a) ,
u = 2ax + b desak, oxirgi taqqoslama
u² b² – 4ac ( mod 4 m*a) (3)
ko‘rinishga keladi . Nixoyat b² – 4ac = d , 4*m*a = m₁ belgilash kiritib,
u² d ( mod m₁ ) (4)
taqqoslamani hosil qilamiz. (1) ning har bir yechimi (4) ni ham qanoatlantiradi. Lekin (4) har bir yechimi (1) ning ham yechimi bo‘lavermaydi. Shuning uchun (4) ning yechimlari orasidan (1) ning ham yechimi bo‘ladiganlarini ajrata olish kerak . Buning uchun esa
x = (u-b)/ 2a
nisbat butun son ekanligiga qarash kerak, yani nisbat butun son bo‘lsa , (4) qanoatlantiruvchi yechim (1) ning ham yechimi bo‘ladi. Odatda misollar yechishda (1) dan (4) ga o‘tishda, taqqoslamaning chap qismini biror ifodaning to‘la kvadrati shakliga keltirib olish lozim.