1.6 Eyler teoremasi
Agar n ≥ 0 musbat butun son va (a, n)=1 bo‘lsa, bu yerda a – butun, unda quyidagi formula orqali aniqlanadi:
aφ(n)=1 mod n.
Misol: 41126 =? mod 127.
EKUB(41,127) = 1, φ(127) = 126, shuning uchun 41126 = 1 mod 127.
4336 = ? mod 377.
EKUB(4, 377) = 1, 377 = 13∙29, 13 va 29 – tub sonlar, shuning uchun
φ(377) = φ(13) ∙ φ(29) = 12∙28 = 336, shuning uchun 4336 = 1 mod 377.
1.7 O‘zaro teskari sonlar
n soni uchun modul bo‘yicha r o‘zaro teskari deb shunday m soniga aytiladiki, u uchun quyidagi bajariladi:
(n∙m) mod r = 1,
yoki
n∙m = 1 mod r. (1)
Isbot: Eyler teoremasi bo‘yicha: nφ(r)=1 mod r yoki
1 = nφ(r) mod r. (2)
(1) va (2) qayta ko‘paytirib, n∙m = nφ(r) mod r ni olamiz, ikkita qismini n ga bo‘lib, m = nφ(r)-1 mod r ni olamiz.
Misol:
4 soni uchun 7 modul bo‘yicha o‘zaro teskarisini toping.
4∙m = 1 mod 7, m = 4φ(7)-1 mod 7= 45 mod 7 = 2.
Tekshirish: n∙m = 1 mod r.
4∙2 mod 7 = 8 mod 7=1.
1.8 Modulyar arifmetika tamoyillari
Modulyar arifmetika quyidagi tenglamaga asoslanadi:
(a*b) mod m = [(a mod m)*(b mod m)] mod m, (3)
bu erda * - quyidagi har qanday jarayon:
“+” (qo‘shish); “-” (ayirish); “x” (ko‘paytirish).
Ushbu tenglama modulyar arifmetikada (a*b) mod m hisoblash oddiy butun sonli arifmetikada m (mod m)da olingan natijaga keyinchalik bo‘lingandagi qoldiqni olish bilan (a*b) hisoblash ham o‘sha natijani beradi.
Misol: 7∙9 mod 5 =[(7 mod 5)∙(9 mod 5)] mod 5.
Modulyar arifmetikaning tamoyillari darajaga keltirilgan jarayonlarga qo’llanilgan, modomiki darajaga keltirish ko‘p marotaba ko‘paytirishga ekvivalent.
Misol: 35 mod 7 ifodani ko‘rib chiqamiz. 3 ni 5-darajaga keltirish va undan keyin 7 modul bo‘yicha natijani olish quyidagi tarzda amalga oshirilishi mumkin:
Modomiki 5 = 2 ∙ 2 + 1, unda 35=32∙2+1=(32)2∙31.
3 sonini kvadratga ko‘taramiz: 3∙3=9 ( 32 )
Natijani kvadratga ko‘taramiz: 9∙9=81 ( (32) 2 )
3 ga ko‘paytiramiz: 81∙3=243 ( (32) 2∙3 )
7 modul bo‘yicha olamiz: 243 mod 7=5
Dostları ilə paylaş: |
