Sonlar nazariyasi

21*.
2
3
≡
-1 (
mod
3
n+1
), 
n
∈
 
N 
taqqoslamani isbotlang. 
22*.
N
= 3
2
+ 2 va 
M
= 2
3
+ 3 (
n
∈
N
) ko’rinishdagi sonlarning murakkab 
sonlardan iboratligini isbot qiling. 
23*.
Agar
(
)
m
d
mo
b
a
bd
ас



≡
≡
taqqoslamalar berilgan va
(a, m)
= 1 bo’lsa, u holda birinchi taqqoslamani ikkinchi 
taqqoslamaga hadma-had bo’lish natijasida
c 
≡
d (mod m) 
ni hosil qilinishini 
ko’rsating. 

---

35 
24.
a
100 
≡
2 (
mod
73) va 
a
101 
≡
69 (
mod
73) ekanligi ma’lum. 
a
ni 73 ga 
bo’linganida hosil bo’ladigan qoldiqni toping. 
25*.
19
2
11
b
a
+
∈
Z
ifoda berilgan. 
19
5
18
b
a
+
∈
Z 
ni isbotlang. 
26.
2
x
+ 7
y
= 19
z
va 2
x
+ 5
y
= 19
z
tenglamalar natural sonlarda yechimga ega 
emasligini ko’rsating. 
27.
p
> 2 (
p
– tub son) bo’lganda 
1
2
k
+1
+ 2
2
k
+1
+ 3
2
k
+1
+...+ (
p
-1)
2
k
+1
≡
0 (
mod p
) 
taqqoslamani to’g’riligini ko’rsating. 
§ 2. Chegirmalar sinflari. Eyler va Ferma teoremalari 
 
m
natural songa bo’linganida 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
1
, 
x
2
,..., 
x
s
butun sonlar sistemasi 
s = m
va 
i 
≠
 j 
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
1
, 
x
2
,..., 
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

---

36 
qabul qiladigan qiymatlar ham chegirmalarning keltirilgan sistemasidan iborat 
bo’lishi zarur va yetarlidir. 
m
> 1 va 
(a, m)
= 1 bo’lganda quyidagi taqqoslama o’rinli: 
a
ϕ
(m) 
≡
1 
(mod m)
, 
bu yerda 
ϕ
(m)
–Eyler funksiyasi (
Eyler teoremasi
). 
p 
tub son va 
(a, p)
= 1 bo’lganda quyidagi taqqoslama o’rinli: 
a
p-1 
≡
 1 (mod p)
(
Ferma teoremasi
). 
a 
butun sonni o’zida saqlaydigan 
m
bo’yicha chegirmalar sinfini 
a mod m 
bilan 
belgilaymiz. Demak,
a mod m = a + m