Үлдэгдлийн тухай Хятадын теорем

Үлдэгдлийн тухай Хятадын теорем (Chinese remainder theorem) нь "Сун Цзы Тооцооллын зарчим (孫子算経, Sun-tzi Suan-king) хэмээх эртний сударт анхлан бичигдсэн бүхэл тооны үлдэгдэлтэй холбоотой теорем юм. Уг теоремыг анхлан баталсан нээсэн хүн болон цаг хугацааны талаар тодорхой зүйл байдаггүй ч дээрх номонд анх бичигдсэн тул Сун Цзыгийн теорем гэх нь ч бий. Америкийн математикч Л.Е.Диксон тооны онолын түүхийн талаарх бүтээлдээ Үлдэгдлийн тухай Хятадын теорем хэмээсэн нь өдгөө албан ёсны нэршил нь болжээ.

3-аас 5-р зууны үед бүтээгдсэн Хятадын тооллын ухааны бүтээл "Sun-tzi Suan-king"-д "3-т хуваахад 2 үлддэг, 5-д хуваахад 3 үлддэг, 7-д хуваахад 2 үлддэг тоо олдох уу?" гэсэн бодлогыг бодолттой нь хамт бичиж үлдээсэн байдаг. Үлдэгдлийн тухай Хятадын теорем нь энэхүү бодлогыг ерөнхий тохиолдолд шийдсэн теорем юм.

Теорем

Үлдэгдлийн тухай Хятадын теоремын өргөн тархсан тодорхойлолтыг доор бичвэл:

Өгөгдсөн хоёр бүхэл тоо m, n нь харилцан анхны байвал дурын бүхэл a, b тоонуудын хувьд

$x\equiv a{\pmod {m}},$

$x\equiv b{\pmod {n}}$

чанаруудыг хангах x гэсэн бүхэл тоо mn-ийн хувьд модулиар нэг утгатай оршин байна.

Үүнийг дараах байдлаар өргөтгөж болно.

Өгөгдсөн k ширхэг бүхэл тоо m₁, m₂, ...,m_k нь аль ч хоёр нь харилцан анхны бол дурын бүхэл тоо a₁, a₂, ..., a_k-уудын хувьд

${\begin{matrix}x&\equiv &a_{1}{\pmod {m_{1}}},\\x&\equiv &a_{2}{\pmod {m_{2}}},\\&\vdots &\\x&\equiv &a_{k}{\pmod {m_{k}}}\end{matrix}}$

нөхцлийг хангах x нь m₁m₂…m_k-ийн хувьд модулиар нэг утгатай оршин байна.

"Sun-tzi Suan-king"-д бичигдсэн бодлогыг теоремын дээрх хэлээр хөрвүүлж бичвэл,

$x\equiv 2{\pmod {3}},$

$x\equiv 3{\pmod {5}},$

$x\equiv 2{\pmod {7}}$

нөхцлүүдийг хангах x гэсэн тоо оршин байхыг илтгэж байгаа болно. Түүгээр ч үл барам x нь 3 × 5 × 7 = 105-ийн хувьд модулиар нэг утгатай. Өөрөөр хэлбэл, дээрх нөхцлийг хангах бас нэг y гэсэн тоо олддог бол заавал

$x\equiv y{\pmod {105}}$

байх ёстой.

Шийдийг олох арга

Аливаа теоремоор шийд оршин байх гэдэг нь уг шийдийг бодож гаргахаас тусдаа асуудал юм. Гэвч Үлдэгдлийн тухай Хятадын теоремын хувьд шийдийг нь харьцангуй амархан тооцоолох боломжтой. Үүнийг бодох хэд хэдэн арга байдаг.

Алгоритмын арга

Дараах жишээг авч үзье.

$x\equiv 2{\pmod {3}},$

$x\equiv 3{\pmod {5}},$

$x\equiv 2{\pmod {7}}$

Евклидийн алгоритмаар

12 × 3 + (-1) × 35 (=5 × 7) = 1,

(-2) × 5 + 1 × 21 (=3 × 7) = 1,

(-2) × 7 + 1 × 15 (=3 × 5) = 1

болно. Үүнийг ашиглавал

((-1) × 35)= -35 ≡ 1 (mod 3), ≡ 0 (mod 5), ≡ 0 (mod 7),

(1 × 21) = 21 ≡ 0 (mod 3), ≡ 1 (mod 5), ≡ 0 (mod 7),

(1 × 15) = 15 ≡ 0 (mod 3), ≡ 0 (mod 5), ≡ 1 (mod 7)

болох нь харагдах учраас

2 × (-35) + 3 × 21 + 2 × 15 = 23

гэдэг нь манай бодлогын нэгэн хариу болно. Теорем ёсоор бодлогын хариу маань 3 × 5 × 7 = 105 -ийн хувьд модулиар нэг утгатай тул бүх хариу нь 23 + 105k (k ∈ Z) хэлбэртэй байх ёстой. Өөрөөр энэ шийд нь манай бодлогын ерөнхий шийд болно.

Теоремын өргөтгөл

Үлдэгдлийн тухай Хятадын теорем нь бүхэл тоо болон үлдэгдэлтэй холбоотой теорем хэдий ч үүнийг нэгжтэй цагираг болон түүний идеалийн хувьд болгон өргөтгөх боломжтой.

Энэ математикийн тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.