Үлдэгдлийн тухай Хятадын теорем
Wikipedia-с
Үлдэгдлийн тухай Хятадын теорем (Chinese remainder theorem) нь "Сун Цзы Тооцооллын зарчим (孫子算経, Sun-tzi Suan-king) хэмээх эртний сударт анхлан бичигдсэн бүхэл тооны үлдэгдэлтэй холбоотой теорем юм. Уг теоремыг анхлан баталсан нээсэн хүн болон цаг хугацааны талаар тодорхой зүйл байдаггүй ч дээрх номонд анх бичигдсэн тул Сун Цзыгийн теорем гэх нь ч бий. Америкийн математикч Л.Е.Диксон тооны онолын түүхийн талаарх бүтээлдээ Үлдэгдлийн тухай Хятадын теорем хэмээсэн нь өдгөө албан ёсны нэршил нь болжээ.
3-аас 5-р зууны үед бүтээгдсэн Хятадын тооллын ухааны бүтээл "Sun-tzi Suan-king"-д "3-т хуваахад 2 үлддэг, 5-д хуваахад 3 үлддэг, 7-д хуваахад 2 үлддэг тоо олдох уу?" гэсэн бодлогыг бодолттой нь хамт бичиж үлдээсэн байдаг. Үлдэгдлийн тухай Хятадын теорем нь энэхүү бодлогыг ерөнхий тохиолдолд шийдсэн теорем юм.
Contents |
[Өөрчлөх] Теорем
Үлдэгдлийн тухай Хятадын теоремын өргөн тархсан тодорхойлолтыг доор бичвэл:
- Өгөгдсөн хоёр бүхэл тоо m, n нь харилцан анхны байвал дурын бүхэл a, b тоонуудын хувьд
- чанаруудыг хангах x гэсэн бүхэл тоо mn-ийн хувьд модулиар нэг утгатай оршин байна.
Үүнийг дараах байдлаар өргөтгөж болно.
- Өгөгдсөн k ширхэг бүхэл тоо m1, m2, ...,mk нь аль ч хоёр нь харилцан анхны бол дурын бүхэл тоо a1, a2, ..., ak-уудын хувьд
- нөхцлийг хангах x нь m1m2…mk-ийн хувьд модулиар нэг утгатай оршин байна.
"Sun-tzi Suan-king"-д бичигдсэн бодлогыг теоремын дээрх хэлээр хөрвүүлж бичвэл,
нөхцлүүдийг хангах x гэсэн тоо оршин байхыг илтгэж байгаа болно. Түүгээр ч үл барам x нь 3 × 5 × 7 = 105-ийн хувьд модулиар нэг утгатай. Өөрөөр хэлбэл, дээрх нөхцлийг хангах бас нэг y гэсэн тоо олддог бол заавал
байх ёстой.
[Өөрчлөх] Шийдийг олох арга
Аливаа теоремоор шийд оршин байх гэдэг нь уг шийдийг бодож гаргахаас тусдаа асуудал юм. Гэвч Үлдэгдлийн тухай Хятадын теоремын хувьд шийдийг нь харьцангуй амархан тооцоолох боломжтой. Үүнийг бодох хэд хэдэн арга байдаг.
[Өөрчлөх] Алгоритмын арга
"3,5,7"-гийн жишээг авч үзье. Евклидийн алгоритмаар
- 2 × 3 + (-1) × 5 = 1,
- (-2) × 3 + 1 × 7 = 1,
- 3 × 5 + (-2) × 7 = 1
болно. Үүнийг ашиглавал
- -35 = ((-1) × 5)×(1 × 7) ≡ 1 (mod 3), ≡ 0 (mod 5), ≡ 0 (mod 7),
- -84 = (2 × 3)×((-2) × 7) ≡ 0 (mod 3), ≡ 1 (mod 5), ≡ 0 (mod 7),
- -90 = ((-2) × 3)×(3 × 5) ≡ 0 (mod 3), ≡ 0 (mod 5), ≡ 1 (mod 7)
болох нь харагдах учраас
- 2 × (-35) + 3 × (-84) + 2 × (-90) = -502
гэдэг нь манай бодлогын нэгэн хариу болно. Мөн -502 + 3 × 5 × 7 × k (k ∈ Z) ч бас бодлогын хариу болох нь илэрхий. Нөгөө талаар теорем ёсоор бодлогын хариу маань 3 × 5 × 7 = 105 -ийн хувьд модулиар нэг утгатай тул бүх хариу нь -502 + 105k (k ∈ Z) хэлбэртэй байх ёстой. Өөрөөр хэлбэл дээрх шийд нь манай бодлогын ерөнхий шийд болно.
[Өөрчлөх] Теоремын өргөтгөл
Үлдэгдлийн тухай Хятадын теорем нь бүхэл тоо болон үлдэгдэлтэй холбоотой теорем хэдий ч үүнийг нэгжтэй цагираг болон түүний идеалийн хувьд болгон өргөтгөх боломжтой.
Template:Sci-stub
Categories: Тооны онол | Теорем