Sonlar nazariyasi

 
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
1
 d, b = b
1
 d, m = m
1
 d
bo’lsa, u holda
a
1
 
≡
 b
1
 (mod m
1
)
bo’ladi. 
3.
Agar 
a 
≡
 b (mod m
1
)
, 
a 
≡
 b (mod m
2
), ..., a ( b (mod m
k
) 
bo’lsa, u holda
a 
≡
 b (mod M) 
bo’ladi, bu yerda 
M = [m
1
, m
2
,..., 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 4
k + 
1 dan iborat; 
h) 
N
sonining ko’rinishi 10
k + 
3 dan iborat; i)
N
sonining ko’rinishi 8
k – 
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
5n
– 1 ning 31 ga bo’linishini isbotlang 
(n 
∈
 
N
)
. 
Yechilishi
. 
 
2
5
– 1 = 31 bo’lganligi uchun 2
5
≡
1
 (mod 
31
)
. Bu taqqoslamaning 
ikkala tomonini (6-xossaga asosan)
n 
darajaga ko’tarib, 2
5n
≡
1
(mod 
31
) 
ni hosil 
qilamiz, bu esa 31 

(2
5n
– 1) ni anglatadi. 
■
4-Misol
. 2
100
sonining oxirgi ikkita raqamini toping. 

---

33 
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
100
≡
x
(
mod
100). 
Ikkining kichik darajalaridan boshlab, 100 ga bo’lganda hosil bo’ladigan 
qoldiqlarni ketma-ket ajratamiz: 
2
100
= (2
10
)
10
= (1024)
10
; (1024)
10
≡
(24)
10
(
mod
100). 
(24)
10
= (576)
5
≡
76 
5 
≡
(76)
4
⋅
76 = (5776)
2
⋅
76 
≡
(76)
2
⋅
76 = 5776
⋅
76
≡
76
2
≡
5776 
≡
76 
(
mod
100). 
Shunday qilib, 2
100
sonining oxirgi ikki raqamir 7 va 6 dan iborat. 
■
5-Misol
.

Agar p – tub son bo’lsa, u holda

k
p
C
1
−
≡
(-1)
k 
(mod p) 
taqqoslamani 
isbotlang. 
Yechilishi
. Ma’lumki, ixtiyoriy 
p
va 
k 
sonlar uchun 
k
p
k
p
k
p
C
C
C
=
+
−
−
−
1
1
1
formula 
o’rinli, 
k
p
C
- 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, 
k
p
C
 
≡
 
0
 (mod p)
. U holda 
k
p
C
1
−
 
≡
 
(-1)
 
1
1
−
−
k
p
C
(mod p)
. 
Bu rekurrent munosabatni ketma-ket qo’llab, yuqori ko’rsatkichni 1 gacha 
kamaytiramiz: 
( )
( )
( )
( ) (
) ( ) (
)
p
mo
p
k
k
k
p
k
p
k
p
k
p
C
C
C
C
d
1
1
1
1
1
1
1
3
1
3
2
1
2
1
1
1
−
≡
−
−
≡
≡
−
≡
−
≡
−
≡
−
−
−
−
−
−
−
−
...
. 
■
6-Misol
. Agar 
a
va 
b
– ixtiyoriy butun sonlar, 
p
– tub son bo’lsa, quyidagi 
taqqoslamani isbotlang 
(a + b)
p 
≡
 a
p
 + b
p
 (mod p)
. 
Yechilishi
. Binomni yoyish formulasidan: 
p
p
p
p
p
p
p
p
p
p
b
ab
b
a
b
a
 
a
 b)
(a 
C
C
C
+
+
+
+
+
=
+
−
−
−
−
1
1
2
2
2
1
1
...
. 
O’ng tomonda ikkinchi qo’shiluvchidan boshlab, p
-1
–nchi qo’shiluvchigacha barcha 
qo’shiluvchilar 
p 
ga bo’linadi, chunki 
C
k
p
= 
k
k
p
p
p
⋅
⋅
⋅
−
−
−
...
2
1
)
1
(
)...(
1
(
, bu yerda
k < p
. 
Demak, 
(
)
p
d
mo
C
i
p
0
≡
,
i
= 1, 2, ..., (
p
-1). 
Bu yerdan 
(a + b)
p 
≡
 a
p
 + b
p
 (mod p) 
kelib chiqadi. 
■
MAShQLAR 
1.
Qanday modul bo’yicha barcha butun sonlar o’zaro taqqoslanadi? 
2.
Quyidagi taqqoslamalardan qaysilari to’g’ri: 
a) 1 
≡
-5 (
mod
6); b) 546 
≡
0 (
mod
13); c) 1956 
≡
5 (
mod
12); 
d) 2
3
≡
1 (
mod
4); e) 3
m
≡
-1 (
mod m
)? 
3*.
Berilgan modul bo’yicha har qanday butun son o’zining qoldig’i bilan 
taqqoslanishini isbot qiling. 

---

34 
n 
4n+1 
4n+1 
4.
Quyidagi taqqoslamalarni qanoatlantiradigan 
x
ning barcha qiymatlarini 
toping: 
a) 
x
≡
0 (
mod
3); b) 
x
≡
1 (
mod
2). 
5.
Quyidagi taqqoslamalarni qanoatlantiradigan 
m
ning barcha qiymatlarini 
toping: 3
r
+ 1 
≡
r
+ 1 (
mod m
). 
6.
Agar 
x
= 13 soni 
x
≡
5 (
mod m
) taqqoslamani qanoatlantirsa, modulning 
mumkin bo’lgan qiymatlarini toping.
7*.
Agar 
n
– toq son bo’lsa, u holda 
n
2 
- 1
≡
0 (
mod
8) taqqoslama o’rinli 
ekanligini ko’rsating. 
8*.
Agar 100
a
+ 10
b
+ 
c
≡
0 (
mod
21) bo’lsa, u holda 
a
– 2
b
+ 4
c
≡
0 (
mod
21) taqqoslamaning o’rinli ekanligini ko’rsating. 
9.
Agar 3
n
≡
-1 (
mod
10) bo’lsa, u holda 3
n+4
≡
-1 (
mod
10) (
n
∈
N
) 
taqqoslamaning o’rinli ekanligini ko’rsating,. 
10*.
2
11
•
31
≡
2 (
mod
11
⋅
31) taqqoslamaning to’g’riligini ko’rsating. 
11*.
Agar 
x
= 3
n
+ 1, 
n
= 0, 1, 2,.... bo’lsa, u holda 1 + 3
x
+ 9
x
ning 13 ga 
bo’linishini ko’rsating.
12.
N
= 11
⋅
18
⋅
2322
⋅
13
⋅
19 soni 7 modul bo’yicha absolyut qiymati bo’yicha 
eng kichik qanday son bilan taqqoslanadi? 
13.
3
14
≡
-1 (
mod
29) ni tekshiring. 
14.
1532
5 
– 1 ni 9 ga bo’lganda hosil bo’ladigan qoldiqni toping. 
15*.
Agar 
a
≡
b
(
mod p
n
) bo’lsa, u holda
a
p
 
≡
 b
p
 (mod p
n+1
) 
ni isbotlang. 
16
Agar 
ax 
≡
 bx (mod m) 
bo’lsa, u holda 
(
)






≡
m
,
x,
m
mo
b
a
d
ni isbotlang. 
17*.
Agar
a
4
a
3
a
2
a
1
a
0
 
≡
0 (
mod
33) bo’lsa, u holda 
a
4
 + a
3
a
2 
+ a
1
a
0
≡
0 (
mod
33) ni isbotlang. a
i+1 
= 0 da
a
i+1
a
i
 = a
i 
deb oling. 
18*.
Berilgan sonning oxirgi ikkita raqamini toping: a) 9
9
; b) 7
9
. 
19*.
r
r+
2 
+ (
r
+2)
r
≡
0 (
mod
2
r
+2) taqqoslamani isbot qiling, bu yerda 
r
> 2. 
20*.
Quyidagi sonlarni 
,...,
2
3
,
2
1
−
−
−
−
p
p
- 1, 0, 1,..., 
2
1
,
2
3
−
−
p
p
r > 2 modul bo’yicha o’zaro taqqoslanmasligini ko’rsating.