Reja Taqqoslamalar va ularning xossalari

3-4-Mavzu Taqqoslamalar va ularning xossalari. Chegirmalar sinflari. Multiplikativ funksiyalar. Eyler va Ferma teoremalari. Birinchi darajali taqqoslamalar.
Reja

1. 
   Taqqoslamalar va ularning xossalari.
   
2. 
   Chegirmalar sinflari. Multiplikativ funksiyalar. Eyler va Ferma teoremalari.
   
3. 
   Taqqoslama tushunchasi va uning xossalari
   

a va b butun sonlarni butun musbat 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 ak  bk (mod m) bo’ladi,.
   
8. 
   Agar ak  bk (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.
   

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). ■
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. ■
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. ■
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 raqamir 7 va 6 dan iborat. ■
5-Misol. Agar p – tub son bo’lsa, u holda  (-1)^k (mod p) taqqoslamani isbotlang.
Yechilishi. Ma’lumki, ixtiyoriy p va k sonlar uchun formula o’rinli, - butun sondan iborat bo’lib, p ga bo’linadi, chunki k < p, p esa tub sondan iborat, shuning uchun u maxrajning birorta ham ko’paytuvchisi bilan qisqarib ketmaydi. Shunday qilib,  0 (mod p). U holda  (-1) (mod p).
Bu rekurrent munosabatni ketma-ket qo’llab, yuqori ko’rsatkichni 1 gacha kamaytiramiz:
. ■