......
..........
..........
2
2
1
1
(4)
48
So’ngra yuqoridagi usul qo’llaniladi.
Agar (1) sistemaning
a
i
x
≡
b
i
(mod m
i
) (i =
1
, n)
taqqoslamalari uchun
(a
i
, m
i
) =
d
i
va
d
i
|b
i
bo’lsa, u holda har bir
i
-nchi taqqoslamaning hadlarini va modulini
d
i
ga
qisqartirib, (1) sistemaga teng kuchli bo’lgan quyidagi sistema hosil qilinadi:
≡
≡
≡
n
n
n
n
n
n
d
m
d
mo
d
b
x
d
a
d
m
d
mo
d
b
x
d
a
d
m
d
mo
d
b
x
d
a
...
..........
..........
..........
2
2
2
2
2
2
1
1
1
1
1
1
. (5)
Bu sistemaning taqqoslamalirini
x
ga nisbatan yechib, (5) sistemaning yechimini
quyidagi sistemaning yechimiga keltirish mumkin:
≡
≡
≡
n
n
n
d
m
d
mo
x
d
m
d
mo
x
d
m
d
mo
x
α
α
α
.......
..........
..........
2
2
2
1
1
1
(6)
Agar (4) sistemada
m
1
, m
2
,..., m
n
modullar juft-jufti bilan o’zaro tub bo’lsa,
i
≠
j
da
(m
i
, m
j
)
= 1 bo’lsa, u holda uning yechimini quyidagi formula bilan ham topish
mumkin
n
n
n
y
m
M
y
m
M
y
m
M
x
α
α
α
+
+
+
=
...
2
2
2
1
1
1
0
, (7)
bu yerda
M = [m
1
, m
2
,..., m
n
]
va
y
1
, y
2
,..., y
n
lar
(
)
n
i
m
d
mo
y
m
M
i
i
i
,
,
1
1
=
=
taqqoslamalarning yechimlaridan iborat. Sistemaning yechimi
x
≡
x
0
(mod M)
taqqoslamadan iborat bo’ladi.
Agar
n
n
d
m
d
m
d
m
,...,
,
2
2
1
1
muodullar juft-jufti bilang o’zaro tub bo’lsa, Bu usul bilan (6)
sistemani ham yechish mumkin.
Misol 1.
Quyidagi taqqoslamalr sistemasini yeching:
(
)
(
)
(
)
≡
≡
≡
14
9
10
3
16
13
d
mo
x
d
mo
x
d
mo
x
Yechilishi.
Birinchi taqqoslamadan:
x
= 16
t
+ 13.
ni hosil qilamiz.
x
ning bu qiymatini ikkinchi taqqoslamag qo’yamiz:
49
16
t
+ 13
≡
3 (
mod
10), yoki 16
t
+ 10
≡
0 (
mod
10),
Bu yerdan 8
t
≡
0 (
mod
5), yoki 16
t
≡
0 (
mod
5) ni hosil qilamiz.
Demak,
t
= 5
t
1
.
t
= 5
t
1
ni
x
= 16
t
+ 13 ifodaga qo’yamiz:
x
= 16
⋅
5
t
1
+ 13 = 80
t
1
+ 13.
x
ning topilgan qiymatini uchinchi taqqoslamag qo’yamiz:
80
t
1
+ 13
≡
9 (
mod
14), yoki 80
t
1
≡
- 4 (
mod
14), bu yerdan
80
t
1
≡
10 (
mod
14), yoki 40
t
1
≡
5 (
mod
7), yoki
8
t
1
≡
1 (
mod
7), bu yerdan
t
1
≡
1 (
mod
7), ya’ni,
t
1
= 7
t
2
+ 1.
t
1
= 7
t
2
+ 1 ni
x
= 80
t
1
+ 13 ifodaga qo’yib,
x
= 80 (70
t
2
+ 1) + 13 = 560
t
2
+ 93
ni hosil qilamiz. Shunday qilib,
x
≡
93 (mod 560).
■
Tekshirish
: 93 – 13 ayirma 16 ga bo’linadi; 93 – 13 ayirma 10 ga bo’linadi; 93
– 9 ayirma 14 ga bo’linadi.
Eslatma.
16
t
≡
0 (
mod
10) taqqoslamani yechishda biz 8
t
≡
0 (
mod
5)
taqqoslamani hosil qildik, uning yechimi
t
≡
0 (
mod
5), yoki
t
= 5
t
1
berilgan
taqqoslamaning
x
= 80
t
1
+ 13 yechimiga olib keldi. Ammo 16
t
≡
0 (
mod
10)
taqqoslamaning ikkinchi
t
≡
5 (
mod
10), yoki
t
= 10
t
1
+ 5 yechimi ham mavjud
(chunki,
d
= (16, 10) = 2). Bu yechimni
x
= 16
t
+ 13 ifodaga qo’yib,
x
= 16(10
t
1
+ 5)
+13 = 160
t
1
+ 93 yechimni hosil qilamiz. Lekin 93
≡
13 (
mod
80) bo’lganligi uchun,
ya’ni 93 va 13 sonlari 80 modul bo’yicha bir sinfga tegishli bo’lganligi uchun
x
ning
bu qiymatiga mos bo’lgan yechim qaralmaydi.
Bu eslatmadan (1-misol) agar sistemaning biror taqqoslamasi yoki
t
1
ga nisbatan
biror taqqoslama
m
modul bo’yicha
d
ta yechimga ega bo’lsa, u holda sistemani
yechimini topish uchun
d
ta yechimga ega bo’lgan taqqoslama yechimini unga teng
kuchli bo’lgan
m/d
modul bo’yicha taqqoslama yechimi bilan almashtirish yetarlidir.
Misol 2. Taqqoslamalar sistemasini yeching:
(
)
(
)
(
)
≡
≡
≡
5
2
3
35
5
15
11
3
7
d
mo
x
d
mo
x
d
mo
x
Yechilishi
. Sistemaning har bir taqqoslamasini alohida yechib, bu sistemaga teng
kuchli bo’lgan quyidagit sistemani hosil qilamiz:
(
)
(
)
(
)
≡
≡
≡
5
4
7
5
11
2
d
mo
x
d
mo
x
d
mo
x
Bu sistemaning modullari juf-jufti bilan o’zaro tub sonlardan iborat bo’lganligi
uchun uning yechimini (7) formula bilan topish mumkin.
M
= [11, 7, 5] = 385,
77
55
35
3
2
1
=
=
=
m
M
m
M
m
M
,
,
.
sonlarni topib, quyidagi taqqoslamalarni tuzamiz:
35
u
1
≡
1 (
mod
11), 55
u
2
≡
1 (
mod
7), 77
u
3
≡
1 (
mod
5),
50
bu yerdan
u
1
= 6,
u
2
= - 1,
u
3
= 3 larni hosil qilamiz.
Endi (7) formuladan quyidagini hosil qilamiz:
x
0
= 35
⋅
6
⋅
2 + 55
⋅
(-1)
⋅
5 + 77
⋅
3
⋅
4 = 1069
≡
299 (
mod
385).
Shunday qilib,
x
≡
299 (
mod
385).
■
Misol 3. Taqqoslamalar sistemasini yeching:
(
)
(
)
(
)
≡
≡
≡
12
8
3
7
3
4
9
7
5
d
mo
x
d
mo
x
d
mo
x
Yechilishi
. Berilgan sistemaning uchinchi taqqoslamasida (3, 12) = 3, ammo 8
soni 3 ga bo’linmaydi, shuning uchun bu taqqoslama ham berilgan sistema ham
yechimga ega emas.
Misol 4. Taqqoslamalar sistemasini yeching:
(
)
(
)
(
)
−
≡
≡
≡
6
1
2
3
3
2
d
mo
x
d
mo
x
d
mo
x
Yechilishi
. Sistemaning dastlabki ikkita taqqoslamasi
x
≡
-1 (
mod
3) va
x
≡
-1
(
mod
2) taqqoslamalarga teng kuchli, shuning uchun ularni uchinchi taqqoslamaning
natijasi bo’lganligi uchun tashlab yuborilsa bo’ladi. Shunday qilib, sistema uchinchi
taqqoslamasining yechimi sistemaning ham yechimi bo’ladi, ya’ni.
x
≡
-1
≡
5 (
mod
6).
■
Misol 5. 2, 3, 4, 5, 6 va 7 sonlariga bo’linganida mos ravishda 1, 2, 3, 4, 5
va 0 qoldiq hosil bo’ladigan sonni toping.
Yechilishi
. Masala yuidagi taqqoslamalr sistemasiga keltiriladi:
(
)
(
)
(
)
(
)
(
)
(
)
≡
≡
≡
≡
≡
≡
7
0
6
5
5
4
4
3
3
2
2
1
d
m
о
x
d
m
о
x
d
m
о
x
d
m
о
x
d
mo
x
d
mo
x
x
≡
1 (
mod
2) yoki
x
≡
3 (
mod
2) taqqoslama
x
≡
3 (
mod
4) taqqoslamaning natijasi
sifatida tashlab yuborilishi mumkin. Xuddi shunday
x
≡
2 (
mod
3) taqqoslama ham
olinmaydi.
Shunday qilib, quyidagi sistemani hosil qilamiz:
(
)
(
)
(
)
(
)
≡
≡
≡
≡
7
0
6
5
5
4
4
3
d
m
о
x
d
m
о
x
d
m
о
x
d
m
о
x
Bu sistemani yechib,
x
≡
119 (
mod
420) ni hosil qilamaiz.
■
Misol 6.
Quyidagi taqqoslama yechimga ega bo’ladigan
a
ning qiymatlarini
toping:
51
(
)
(
)
(
)
≡
≡
≡
35
21
8
18
5
d
m
о
а
x
d
m
о
x
d
m
о
x
Yechilishi.
Birinchi taqqoslamadan
x
= 18
t
+ 5
ni hosil qilamiz.
x
ning bu qiymatini ikkinchi taqoslamaga qo’yib,
t
ning qiymatini
topamiz:
18
t
+ 5
≡
8 (
mod
21), yoki 18
t
≡
3 (
mod
21), yoki 6
t
≡
1 (
mod
7),
t
≡
6 (
mod
7).
t
≡
-1 (
mod
7) ni olish qulayroq, bu yerdan
t
= 7
t
1
– 1. Bu qiymatni
x
ning ifodasiga
qo’yib,
x
= 16 (7
t
1
– 1) = 5 = 126
t
1
– 13.
x
ning hosil qilingan qiymatini sistemaning uchinchi taqqoslamaga qo’yamiz:
126
t
1
– 13
≡
a
(
mod
35), t.ye. 21
t
1
≡
a
= 13 (
mod
35).
(21, 35) = 7 bo’lganligi uchun oxirgi taqqoslama yechimga ega bo’lishi uchun
a
+ 13
≡
0 (
mod
7) taqqoslama yechimga ega bo’lishi kerak, bu yerdan
a
≡
1 (
mod
7).
Shunday qilib, berilgan sistema
a
≡
1 (
mod
7) bo’lganda yechimga ega.
■
Misol 7.
Dostları ilə paylaş: |