Katta sonlarni ko’paytuvchilarga ajratish algoritmlari. Reja

5.2.6-Misol. x ning har qanday butun qiymatida x⁷ ≡x (mod 42) taqqoslamani to’g’riligini ko’rsating.
Yechilishi. Ferma teoremasiga ko’ra, x⁷ ≡x (mod 7). Endi x⁷ ≡x (mod 2 va 3) ekanligini isbot qilamiz, buning uchun 2 va 3 modullar bo’yicha chegirmalarning to’la sistemasini, y’ani 0, 1, 2 sonlarni sinash yetarli.
5.2.7-Misol. Butun sonning 100-darajasini 125 ga bo’lganda hosil bo’ladigan qoldiqni toping.
Yechilishi. Agar (a, 5) = 1 bo’lsa, u holda Eyler teoremasiga ko’ra:
a ^{φ (125)} = a¹⁰⁰≡1 (mod 125).
Agarda (a, 5) = 5 bo’lsa, u holda a¹⁰⁰ ≡0 (mod 125).
Demak, agar (a, 5) = 1 bo’lsa, u holda izlanayotgan qoldiq 1 ga teng. Agarda (a, 5) = 5 bo’lsa, u holda a¹²⁵ soni 125 ga bo’linadi.
5.3.Katta sonlarni berilgan songa bo’lgandagi qoldiqni hisoblash. Masala quyidagicha qo’yilgan. a^b son berilgan. Bu yerda a va b lar katta sonlar. a^b ni berilgan m songa bo’lganda qoldiqni hisoblang, yani quyidagi taqqoslamani yeching:
x ≡ a^b (mod m) (4.3)
Bu yerda 2 holat bo’ladi. 1-holatda a, m sonlar o’zaro tub, yani (a, m) = 1. 3-mavzuda keltirilgan taqqoslamalar xossasi va Eyler teoremasiga ko’ra
x ≡ , (4.4)
bu yerda a ≡ a₁ (mod m) , b ≡ b₁ (mod φ(m)).
5.3.1-Misol(1-holat (a, m)=1 uchun). 383¹⁷⁵ ni 45 ga bo’lgandagi qoldiqni toping.
Yechilishi. Demak, (4.3) formulaga ko’ra, a=383, b=175, m=45. Quyidagi taqqoslamani yechish kerak:
x ≡ 383¹⁷⁵ (mod 45).
Bu yerda, (a, m) = (383,45) =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) ni topishda Eyler funksiyasini quyidagi xossasidan foydalanamiz:
ifodadan φ(m) = kelib chiqadi. Shuning uchun m=45 ni tub ko’paytuvchilarga ajratib olamiz:
45= 3²∙5 bo’lgani uchun, p₁=3, s₁=2, p₂=5, s₂=1.
Bulardan,
φ(45) =
demak, 175 ≡ b₁ (mod 24),
175 = 24∙7+7 bo’lgani uchun b₁=7
a ≡ a₁ (mod m) taqqoslamada a va m larni qiymatini qo’yamiz: 383 ≡ a₁ (mod 45)
383=45∙8+23 bo’lgani uchun a₁=23.
a₁=23, b₁=7 va m=45 bo’lgani uchun (4.4) quyidagi ko’rinishda bo’ladi:
x ≡ , x ≡ 23⁷ (mod 45) = (23²)³∙23(mod 45) = (529)³∙23(mod 45) ≡ (34)³∙23(mod 45) = (34)²∙(34∙23)(mod 45)=1156∙782(mod 45) ≡31∙17(mod 45) = 527(mod 45) ≡ 32 (mod 45)
529= 11∙45+34 1156 = 25∙45+31 782 = 17∙45+17 527 = 13∙45+32
Shunday qilib, 383¹⁷⁵ ≡32 (mod 45). Izlanayotgan qoldiq 32 dan iborat.
2-holatda a, m sonlar o’zaro tub emas, yani (a, m) = d >1. Bu holatda d|x, yani d son x ga qoldiqsiz bo’linadi. Shuning uchun quyidagi belgilash kiritamiz: , , . Bu yerdan a= a₁d, m= m₁d, x= x₁d va ularni (4.3) ga qo’yamiz
x₁d ≡
Har ikki tomonni d ga qisqartirib yuborsak,
x₁ ≡ .