|
TEOREMA. Agar (????, ????) = 1 bo`lsa, u holda (1) taqqoslama yagona yechimga ega bo`ladi.
ISBOTI
|
| bet | 3/4 | | Sana | 16.05.2024 | | Hajmi | 228,14 Kb. | | #237186 |
Bog'liq eyleer - копия dskret Muxlisa, Ko\'zgu compressed, AKADEMIK YOZUVVTEOREMA. Agar (𝑎, 𝑚) = 1 bo`lsa, u holda (1) taqqoslama yagona yechimga ega bo`ladi.
ISBOTI. m modul` bo`yicha chegirmalarning to`la sistemasi
bo`lsin, u holda
𝑥 1, 𝑥 2, … , 𝑥 𝑚
𝑎𝑥1, 𝑎𝑥2, … , 𝑎𝑥𝑚 (2)
ham chegirmalarning to`la sistemasi bo`lishi ma`lum. Agar (1) da 𝑥 o`rniga ketma ket (2) dagi chegirmalarni qo`yib ko`rsak, u holda bu taqqoslamaning chap qismi chegirmalarning to`la sistemasidagi barcha qiymatlardan o`tadi. Bu esa bitta va faqat bitta 𝑥 𝑖 son uchun 𝑎𝑥 𝑖 sonning b songa tegishli bo`lgan chegirma sinfiga tegishli bo`lishini bildiradi, bunda
𝑎𝑥 𝑖 ≡ 𝑏(𝑚𝑜𝑑𝑚)
bo`ladi. Demak, agar (𝑎, 𝑚 ) = 1 bo`lsa, (1) taqqoslama yagona bo`lgan
𝑥 = 𝑥 𝑖(𝑚𝑜𝑑𝑚) yoki 𝑥 = 𝑥 𝑖 + 𝑚𝑡, 𝑡 ∈ ℤ
yechimga ega bo`ladi.
TEOREMA. Agar (𝑎, 𝑚 ) = 𝑑 > 1 va 𝑏 son 𝑑 ga bo’linmasa, u holda
𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚) taqqoslama yechimga ega bo`lmaydi.
ISBOTI. Faraz qilaylik, 𝑎𝑥 ≡ 𝑏(𝑚𝑜𝑑𝑚) taqqoslama uchun 𝑚 modul` bo`yicha 𝑥 1 sinf yechim bo`lsin va 𝑥 1 ∈ ̅𝑥̅ 1̅ bo`lsin, u holda
𝑎𝑥1 ≡ 𝑏(𝑚𝑜𝑑𝑚) yoki 𝑎𝑥1 − 𝑏 = 𝑚𝑡, 𝑡 ∈ ℤ
bo`ladi. 𝑎 ⋮ 𝑑 ∧ 𝑚 ⋮ 𝑑 dan 𝑏 ⋮ 𝑑 kelib chiqadi. Bunday bo`lishi mumkin emas, shartga ko`ra 𝑏 son 𝑑 ga bo’linmaydi. Demak, teorema isbotlandi.
TEOREMA. Agar (𝑎, 𝑚) = 𝑑 > 1 va 𝑏 son 𝑑 ga bo’linsa, u holda 𝑎𝑥 ≡
𝑏(𝑚𝑜𝑑𝑚) taqqoslama 𝑑 ta turli yechimlarga ega bo`ladi. Bu yechim 𝑚
𝑑
modul`
bo`yicha bitta sinfni tashkil qiladi.
ISBOTI. Shartga ko`ra 𝑎, 𝑏 va 𝑚 sonlar 𝑑 ga bo`linadi. 𝑎 = 𝑎 1𝑑, 𝑏 =
𝑏 1𝑑 ∧ 𝑚 = 𝑚 1𝑑 (1) ni 𝑑 ga bo`lib, unga teng kuchli bo`lgan
𝑎𝑥 1 ≡ 𝑏 1(𝑚𝑜𝑑𝑚 1) (4)
taqqoslamaga ega bo`lamiz. Haqiqatan 𝑥 = 𝛼 son (4) ni qanoatlantirsa, u holda
𝑎𝛼 ≡ 𝑏(𝑚𝑜𝑑𝑚) taqqoslamaga ega bo`lamiz, uning ikkala qismini va modulni 𝑑
ga bo`lib, 𝑎 1𝛼 = 𝑏 1(𝑚𝑜𝑑𝑚 1) hosil bo`ladi. Demak, 𝛼 (4) ni qanoatlantiradi.
Aksincha, 𝑥 = 𝛽 butun son 𝑎 1𝛽 ≡ 𝑏 1(𝑚𝑜𝑑𝑚 1) taqqoslamani qanoatlantirsin. Bu taqqoslamaning ikkala qismini va modulni 𝑑 ga ko`paytirib,
𝑎𝛽 ≡ 𝑏(𝑚𝑜𝑑𝑚) taqqoslamani hosil qilamiz. Demak, 𝛽 (1) ni qanoatlantiradi.
Shunday qilib (1) va (4) teng kuchli ekan. (4) dagi (𝑎, 𝑚 1) = 1, shuning uchun bu taqqoslama
𝑥 = 𝑥 0(𝑚𝑜𝑑𝑚 ) ∨ 𝑥 = 𝑥 0 + 𝑚𝑡, (𝑡 ∈ 𝑡)
yagona echimga ega, bu erda 𝑥 0 𝑚 modul` bo`yicha manfiymas eng kichik chegirma bo`lsin yoki
… 𝑥 0 − 2𝑚 1, 𝑥 0 − 𝑚 1, 𝑥 0, 𝑥 0 + 𝑚, 𝑥 0 + 2𝑚 1, … , 𝑥 0 + (𝑑 − 1 )𝑚 1, 𝑥 0 +
𝑑 𝑚1 , 𝑥 0 + (𝑑 + 1 )𝑚 1, … (5)
dagi har bir chegirma (4) ni qanoatlantiradi va demak, (1) ni ham qanoatlantiradi.
𝑚1
= 𝑚
𝑑
modul` bo`yicha (5) dagi hamma sonlar bitta sinfga tegishli, lekin 𝑚 =
𝑚 1𝑑 modul` bo`yicha ular turli sinflarga tegishli bo`ladi, bu sinflarning chegirmalari esa
𝑥0, 𝑥0 + 𝑚1, 𝑥0 + 2𝑚1, … , 𝑥0 + (𝑑 − 2)𝑚1, 𝑥0 + (𝑑 − 1)𝑚1
Demak, (1) m modul` bo`yicha 𝑑 ta turli echimga ega bo`ladi:
𝑥 ≡ 𝑥0(𝑚𝑜𝑑𝑚), 𝑥 ≡ 𝑥0 + 𝑚1(𝑚𝑜𝑑𝑚)
𝑥 ≡ 𝑥0 + 2𝑚1(𝑚𝑜𝑑𝑚), … , 𝑥 ≡ 𝑥0 + (𝑑 − 1)𝑚1(𝑚𝑜𝑑𝑚)
bu erda 𝑥0 −(3) taqqoslamaning yechimi bo`lgan sinfning eng kichik manfiymas chegirmasi.
Misol. 3𝑥 ≡ 6(𝑚𝑜𝑑9)
(3,6) = 3 ∧ 6 ⋮ 3 =2 3 ta yechimga ega.
𝑥 = 2(𝑚𝑜𝑑3)
Demak, berilgan taqqoslamaning barcha yechimlari
𝑥 = 2(𝑚𝑜𝑑9), 𝑥 = 2 + 3(𝑚𝑜𝑑9) ≡ 5(𝑚𝑜𝑑9)
bo`ladi.
𝑥 ≡ 2 + 3 ∙ 2(𝑚𝑜𝑑𝑚) ≡ 8(𝑚𝑜𝑑9)
|
| |
