Katta sonlarni ko’paytuvchilarga ajratish algoritmlari. Reja

5-mavzu. Katta sonlarni ko’paytuvchilarga ajratish algoritmlari.
Reja:
5.1. Taqqoslama tushunchasi va uning xossalari.
5.2. Chegirmalar sinfi.
5.3. Katta sonlarni berilgan songa bo’lgandagi qoldiqni hisoblash


5.1. Taqqoslama tushunchasi va uning xossalari. a va b butun sonlarni butun musbat m soniga bo’lganda bir xil qoldiq qoladigan, ya’ni
a = mq₁ + r va b = mq₂ + r,
bo’lsa, a va b sonlar teng qoldiqdli yoki m modul bo’yicha o’zaro taqqoslanadigan sonlar deyiladi va quyidagicha yoziladi:
a b (mod m)
“a son b bilan m modul bo’yicha taqqoslanadi” deb o’qiladi.
Agar a b (mod m) bo’lsa, u holda a – b ayirma m ga qoldiqsiz bo’linadi, va
aksincha, agar a va b sonlarning ayirmasi m ga bo’linsa, u holda a b (mod m) o’rinli
bo’ladi (taqqoslamaning ma’nosi haqidagi teorema).
Har qanday butun son m modul bo’yicha o’zining qoldig’i bilan taqqoslanadi,
ya’ni, agar a = mq + r bo’lsa, u holda a r (mod m) bo’ladi.
Xususiy holda, agar r = 0 bo’lsa, u holda a 0 (mod m) bo’ladi; bu taqqoslama
m | a ekanligini, ya’ni m soni a ning bo’luvchisi ekanligini bildiradi, aksincha ham
o’rinli, agar m a bo’lsa, u holda a 0 (mod m) deb yoziladi.
Taqqoslamalarning asosiy xossalari (tengliklarning xossalariga o’xshash)
1. Agar a c (mod m) va b c (mod m) bo’lsa, u holda a b (mod m) bo’ladi.
2. Agar a b (mod m) va c d (mod m) bo’lsa, u holda a c bd (mod m) bo’ladi.
3. Agar a + b c (mod m) bo’lsa, u holda a c - b (mod m) bo’ladi.
4. Agar a b (mod m) bo’lsa, u holda a mk b (mod m), yoki a b mk(mod m) bo’ladi.
5. Agar a b (mod m) va c d (mod m) bo’lsa, u holda ac bd (mod m)bo’ladi.
6. Agar a b (mod m) bo’lsa, u holda aⁿ bⁿ (mod m) (n∈N) bo’ladi.
7. Agar a b (mod m) bo’lsa, u holda ixtioriy k butun son uchun a^k b^k (mod m) bo’ladi.
8. Agar a^k b^k (mod m) va (k,m) = 1 bo’lsa, u holda a b (mod m) bo’ladi.
9. Agar f(x) = a₀ xⁿ + a₁ x^n-1 + ... + a_n (a_i ∈Z) va x x₁ (mod m) bo’lsa, u holda f(x) f(x₁) (mod m) bo’ladi.
Taqqoslamalarninng maxsus xossalari
1. Agar a ≡ b (mod m) bo’lsa, u holda k∈N uchun ak ≡ bk (mod mk) bo’ladi.
2. Agar a ≡ b (mod m) va a = a₁ d, b = b₁ d, m = m₁ d bo’lsa, u holda a₁ ≡ b₁ (mod m₁) bo’ladi.
3. Agar a ≡ b (mod m₁), a ≡ b (mod m₂), ..., a ( b (mod m_k) bo’lsa, u holda a ≡ b (mod M) bo’ladi, bu yerda M = [m₁, m₂,..., m_k].
4. Agar taqqoslama m modul bo’yicha o’rinli bo’lsa, u holda bu taqqoslama m ning ixtiyoriy bo’luvchisi bo’lgan d modul bo’yicha ham o’rinli bo’ladi.
5. Agar taqqoslamaning bir tomoni biror songa bo’linsa, u holda uning ikkinchi tomoni va moduli ham shu songa bo’linadi.
5.1.1.Eyler funksiyasi.
Teorema(Fermaning kichik teoremasi). Agar p tub, a butun son bo’lsa, u holda quyida munosabat o’rinli:

Ta’rif. Har bir m>1 natural son uchun m dan katta bo’lmagan va m bilan o’zaro tub bo’lgan natural sonlar soni Eyler funksiyasi ϕ(m) bilan aniqlanadi.

m	2	3	4	5	6	7	8	9	10	11	12	13	14	15
ϕ(m)	1	2	2	4	2	6	4	6	4	10	4	12

Teorema. Eyler funksiyasi uchun quyidagi amallar o’rinli:
1) ϕ(p)=p-1, agar p tub son bo’lsa;
2) ϕ(p^s)=p^s-1-1, agar p tub son bo’lsa;
3) agar (m,n)=1 bo’lsa, u holda ϕ(mn)= ϕ(m) ϕ(n);
4)Agar ifoda m sonini kanonik ko’rinishda bo’luvchilarga ajratilgan ko’paytmasi bo’lsa, u holda
Misol. ϕ(48) ni aniqlang.
m=48=2⁴∙3 bo’lgani uchun, ϕ(48)= 2^4-1∙(2-1)∙3^1-1∙(3-1)=16.
Teorema(Takomillashgan Eyler ). Agar m>1 natural, a butun son bo’lsa, u holda (m,a)=1 ekanligidan a^φ(m)1(mod m) munosabat o’rinli.
5.1.1-Misol. Quyidagi shartlarni taqqoslamalar yordamida yozing:
a) 219 va 128 sonlarni 7 ga bo’lganda bir xil qoldiq qoladi;
b) (-352) sonini 31 ga bo’linganida qoldiq 20 ga teng bo’ladi ;
c) 487 - 7 ayirma 12 ga bo’linadi; d) 20 – soni 389 ni 41 ga bo’lgandagi qoldiqdan iborat; e) N soni juft; f) N soni toq; g) N sonining ko’rinishi 4k + 1 dan iborat;
h) N sonining ko’rinishi 10k + 3 dan iborat; i) N sonining ko’rinishi 8k –3 dan iborat.
Yechilishi. Taqqoslamaning ma’nosi haqidagi teoremaga asosan:
a) 219 ≡128 (mod 7); b) –352 ≡20 (mod 31); c) 487 ≡7 (mod 12);
d) 389 ≡20 (mod 41); e) N ≡0 (mod 2); f) N ≡1 yoki -1 (mod 2);
g) N ≡1 (mod 4); h) N ≡3(mod 10); i) N ≡-3 (mod 8).
5.1.2-Misol. Quyidagi shartni qanoatlantiradigan m ning qiymatlarini toping:
20 ≡8 (mod m).
Yechilishi. m ning qiymatlari (taqqoslamaning ma’nosi haqidagi teoremaga asosan) 20 – 8 = 12 ning bo’luvchilaridan iborat, ya’ni: 1; 2; 3; 4; 6; 12.
5.1.3-Misol. 2⁵ⁿ – 1 ning 31 ga bo’linishini isbotlang (n ЄN).
Yechilishi. 2⁵ – 1 = 31 bo’lganligi uchun 2⁵ ≡1 (mod 31). Bu taqqoslamaning ikkala tomonini (6-xossaga asosan) n darajaga ko’tarib, 2⁵ⁿ ≡1 (mod 31) ni hosil qilamiz, bu esa 31 (2⁵ⁿ – 1) ni anglatadi.
5.1.4-Misol. 2¹⁰⁰ sonining oxirgi ikkita raqamini toping.
Yechilishi. Berilgan sonning oxirgi ikki raqami bu sonni 100 ga bo’lganda hosil bo’ladigan qoldiqdan iborat. Demak, quyidagi taqqoslamani qanoatlantiradigan x sonini topish talab qilinadi:
2¹⁰⁰ ≡x (mod 100).
Ikkining kichik darajalaridan boshlab, 100 ga bo’lganda hosil bo’ladigan qoldiqlarni ketma-ket ajratamiz:
2¹⁰⁰ = (2¹⁰)¹⁰ = (1024)¹⁰; (1024)¹⁰ ≡ (24)¹⁰ (mod 100).
(24)¹⁰ = (576)⁵ ≡76 ⁵ ≡(76)⁴⋅76 = (5776)²⋅76 ≡(76)²⋅76 = 5776⋅76 ≡76² ≡5776 ≡76
(mod 100).
Shunday qilib, 2¹⁰⁰ sonining oxirgi ikki raqami 7 va 6 dan iborat.
5.2. Chegirmalar sinfi. m natural songa bo’linganda bir xil r qoldiq qoladigan barcha butun sonlar to’plami m modul bo’yicha sonlar sinfini tashkil qiladi. Bu sinfning har bir soni umumiy holda mk+r, k∈Z ko’rinishda yoziladi. Barcha sinflar soni m ga teng.
Sinfning ixtiyoriy soni m modul bo’yicha chegirma deyiladi (shu sinfning boshqa sonlariga nisbatan).
Har bir sinfdan ixtiyoriy ravishda bittadan olingan sonlar to’plami berilgan m modul bo’yicha chegirmalarning to’la sinfi deyiladi.
Odatda chegirmalarning to’la sinfi sifatida berilgan m bo’yicha eng kichik manfiy bo’lmagan chegirmalar, ya’ni 0, 1, 2,..., m - 1 sistema olinadi.
Ba’zan berilgan m modul bo’yicha chegirmalardan absolyut qiymati bo’yicha eng kichik musbat bo’lmagan chegirmalarning to’la sistemasi ham qaraladi: -(m-1), -(m-2),..., -2, -1, 0. m modul bo’yicha absolyut qiymati jihatidan eng kichik chegirmalarning to’la sinfi ham ishlatiladi. Masalan, m = 7 bo’lganda bu sistema -3, - 2, -1, 0, 1, 2, 3 chegirmalardan iborat bo’ladi; m = 8 bo’lganda esa -3, -2, -1, 0, 1, 2, 3, 4 yoki –4, -3, -2, -1, 0, 1, 2, 3 chegirmalardan tashkil topadi.
Chegirmalarning to’la sistemasidan olingan va m modul bilan o’zaro tub bo’lgan chegirmalar m modul bo’yicha chegirmalarning keltirilgan sistemasi deyiladi. Kelitirilgan sistemada chegirmalar soni φ(m)- Eyler funksiyasining qiymatiga teng.
Chegirmalarning to’la sistemasidagi kabi keltirilgan sistemaning ham uch turi ishlatiladi: eng kichik musbat chegirmalarning keltirilgan sistemasi, absolyut qiymati bo’yicha eng kichik manfiy chegirmalarning keltirilgan sistemasi va absolyut qiymati bo’yicha eng kichik chegirmalarning keltirilgan sistemasi.
x₁, x₂,..., x_s butun sonlar sistemasi s =φ (m) va i ≠j,( x_i,m)=1 da x_i ≡x_j (mod m) bo’lganda va faqat shu holda m modul bo’yicha chegirmalarning to’la sistemasidan iborat bo’ladi.
(a, m) = 1 bo’lganda ax + b chiziqli formaning qiymatlari m modul bo’yicha chegirmalarning to’la sistemasidan iborat bo’lishi uchun x qabul qiladigan qiymatlar ham chegirmalarning to’la sistemasidan iborat bo’lishi zarur va yetarlidir.
x₁, x₂,..., x_s butun sonlar sistemasi s =φ (m) va i ≠j,( x_i,m)=1 da x_i ≡x_j (mod m) bo’lganda va faqat shu holda m modul bo’yicha chegirmalarning keltirilgan sistemasidan iborat bo’ladi.
(a, m) = 1 bo’lganda ax chiziqli formaning qiymatlari m modul bo’yicha chegirmalarning keltirilgan sistemasidan iborat bo’lishi uchun x qabul qiladigan qiymatlar ham chegirmalarning keltirilgan sistemasidan iborat bo’lishi zarur va yetarlidir.
m > 1 va (m, a) = 1 bo’lganda quyidagi taqqoslama o’rinli:
a ^{φ (m)} ≡1 (mod m),
bu yerda φ (m) –Eyler funksiyasi (Eyler te oremasi).
p tub son va (a, p) = 1 bo’lganda quyidagi taqqoslama o’rinli:
a^p-1 ≡1 (mod m), (Ferma teoremasi).
a butun sonni o’zida saqlaydigan m bo’yicha chegirmalar sinfini a mod m bilan belgilaymiz. Demak,
a mod m = a + mZ = {a + km k ∈Z}.
Z/mZ bilan m modul bo’yicha barcha chegirmalar sinflari to’plamini belgilaymiz:
Z/mZ = {0 mod m, 1 mod m,..., (m-1) mod m}.
Bu to’plamda qo’shish va ko’paytirish amallarini quyidagi tengliklar orqali kiritiladi:
a mod m + b mod m = (a + b) mod m,
(a mod m) ⋅(b mod m) = ab mod m.
(Z/mZ, +) – abel gruppasidan, hamda Z gruppaning mZ qism gruppa bo’yicha faktor gruppasidan iborat bo’lib, m modul bo’yicha chegirmalar sinfining additive gruppasi deyiladi.
(Z/mZ, +, ⋅) – birlik elementli kommutativ xalqadan iborat bo’lib, m modul bo’yicha chegirmalar sinfinig xalqasi deyiladi.
Agar (m, a) = 1 bo’lsa, m mod a sinf a modul bilan o’zaro tub bo’lgan chegirmalar sinfi deyiladi.
m modul bilan o’zaro tub bo’lgan chegirmalar sinflari to’plami ko’paytirishga nisbatan abel gruppasi tashkil etadi va u m modul bilan o’zaro tub bo’lgan chegirmalar sinflarining multiplikativ gruppasi deyiladi.
Agar ab ≡1 (mod m) bo’lsa, a chegirma b chegirmaga m modul bo’yicha
teskari deyiladi.
5.2.1-Misol. 10 modul bo’yicha chegirmalar to’la sistemasining uchta turini yozing.
Yechilishi. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – 10 modul bo’yicha eng kichik manfiy bo’lmagan chegirmalarning to’la sistemasi.
-9, -8, -7, -6, -5, -4, -3, -2, -1, 0 – 10 modul bo’yicha absolyut qiymati jihatidan eng kichik manfiy chegirmalarning to’la sistemasi.
-4, -3, -2, -1, 0, 1, 2, 3, 4, 5 yoki –5, -4, -3, -2, -1, 0, 1, 2, 3, 4 – 10 modul bo’yicha absolyut qiymati jihatidan eng kichik chegirmalarning to’la sistemasi.