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

Чөлөөт нэвтэрхий толь — Википедиагаас
Харайх: Удирдах, Хайлт

Үлдэгдлийн тухай Хятадын теорем (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 ширхэг бүхэл тоо m1, m2, ...,mk нь аль ч хоёр нь харилцан анхны бол дурын бүхэл тоо a1, a2, ..., ak-уудын хувьд
\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 нь m1m2mk-ийн хувьд модулиар нэг утгатай оршин байна.

"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 (kZ) хэлбэртэй байх ёстой. Өөрөөр энэ шийд нь манай бодлогын ерөнхий шийд болно.

Теоремын өргөтгөл[засварлах]

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