Хятадын үлдэгдлийн теорем¶

Хятадын үлдэгдлийн теоремыг (энэ өгүүллийн үлдсэн хэсэгт CRT гэж нэрлэнэ) Хятадын математикч Сун Зи нээсэн.

Томьёолол¶

$m = m_1 \cdot m_2 \cdots m_k$ гэе, энд $m_i$ нь хос хосоороо харилцан анхны. $m_i$-ээс гадна бидэнд congruence-үүдийн систем өгөгдсөн

$$\left\{\begin{array}{rcl} a & \equiv & a_1 \pmod{m_1} \\ a & \equiv & a_2 \pmod{m_2} \\ & \vdots & \\ a & \equiv & a_k \pmod{m_k} \end{array}\right.$$

энд $a_i$ нь өгөгдсөн зарим тогтмолууд. CRT-ийн анхны хэлбэр нь өгөгдсөн congruence-үүдийн систем $m$ модулиар үргэлж яг ганц шийдтэй байна гэж хэлдэг.

Жишээ нь congruence-үүдийн систем

$$\left\{\begin{array}{rcl} a & \equiv & 2 \pmod{3} \\ a & \equiv & 3 \pmod{5} \\ a & \equiv & 2 \pmod{7} \end{array}\right.$$

нь $105$ модулиар $23$ шийдтэй, учир нь $23 \bmod{3} = 2$, $23 \bmod{5} = 3$, ба $23 \bmod{7} = 2$. Бид шийд бүрийг $k \in \mathbb{Z}$-ийн хувьд $23 + 105\cdot k$ гэж бичиж болно.

Дүгнэлт¶

CRT-ийн үр дагавар бол дараах тэгшитгэл

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

нь дараах тэгшитгэлийн системтэй эквивалент байх явдал юм

$$\left\{\begin{array}{rcl} x & \equiv & a_1 \pmod{m_1} \\ & \vdots & \\ x & \equiv & a_k \pmod{m_k} \end{array}\right.$$

(Дээрхтэй адил $m = m_1 m_2 \cdots m_k$ бөгөөд $m_i$ нь хос хосоороо харилцан анхны гэж үзнэ).

Хоёр модулийн шийд¶

Харилцан анхны $m_1, m_2$-ийн хувьд хоёр тэгшитгэлийн системийг авч үзье:

$$ \left\{\begin{align} a &\equiv a_1 \pmod{m_1} \\ a &\equiv a_2 \pmod{m_2} \\ \end{align}\right. $$

Бид $a \pmod{m_1 m_2}$-ийн шийдийг олохыг хүсэж байна. Өргөтгөсөн Евклидийн алгоритм-ыг ашиглан бид дараах нөхцөлийг хангах Безугийн коэффициент $n_1, n_2$-г олж болно

$$n_1 m_1 + n_2 m_2 = 1.$$

Үнэндээ $n_1$ ба $n_2$ нь зүгээр л $m_2$ ба $m_1$ модулиар авсан $m_1$ ба $m_2$-ийн модулийн урвуу юм. Бидэнд $n_1 m_1 \equiv 1 \pmod{m_2}$ тул $n_1 \equiv m_1^{-1} \pmod{m_2}$, эсрэгээрээ $n_2 \equiv m_2^{-1} \pmod{m_1}$ болно.

Эдгээр хоёр коэффициентээр бид шийдийг тодорхойлж болно:

$$a = a_1 n_2 m_2 + a_2 n_1 m_1 \bmod{m_1 m_2}$$

$a \bmod{m_1}$ ба $a \bmod{m_2}$-г тооцоолох замаар энэ нь үнэхээр шийд болохыг шалгахад амархан.

$$ \begin{array}{rcll} a & \equiv & a_1 n_2 m_2 + a_2 n_1 m_1 & \pmod{m_1}\\ & \equiv & a_1 (1 - n_1 m_1) + a_2 n_1 m_1 & \pmod{m_1}\\ & \equiv & a_1 - a_1 n_1 m_1 + a_2 n_1 m_1 & \pmod{m_1}\\ & \equiv & a_1 & \pmod{m_1} \end{array} $$

Хятадын үлдэгдлийн теорем нь мөн $m_1 m_2$ модулиар зөвхөн 1 шийд оршихыг баталгаажуулдгийг анхаараарай. Үүнийг батлахад бас амархан.

Танд $x$ ба $y$ гэсэн хоёр өөр шийд байна гэж үзье. $x \equiv a_i \pmod{m_i}$ ба $y \equiv a_i \pmod{m_i}$ тул $x − y \equiv 0 \pmod{m_i}$ гэж гарах ба улмаар $x − y \equiv 0 \pmod{m_1 m_2}$ буюу эквивалентаар $x \equiv y \pmod{m_1 m_2}$ болно. Тиймээс $x$ ба $y$ нь үнэндээ ижил шийд юм.

Ерөнхий тохиолдлын шийд¶

Индукцын шийд¶

$m_1 m_2$ нь $m_3$-тай харилцан анхны тул бид хоёр модулийн шийдийг дурын тооны модулийн хувьд индукцээр давтан хэрэглэж болно. Эхлээд эхний хоёр congruence ашиглан $b_2 := a \pmod{m_1 m_2}$-г тооцоолно, дараа нь $a \equiv b_2 \pmod{m_1 m_2}$ ба $a \equiv a_3 \pmod {m_3}$ congruence ашиглан $b_3 := a \pmod{m_1 m_2 m_3}$-г тооцоолж болно, гэх мэт.

Шууд байгуулалт¶

Лагранжийн интерполяцтай төстэй шууд байгуулалт хийх боломжтой.

$M_i := \prod_{i \neq j} m_j$ гэе, энэ нь $m_i$-ээс бусад бүх модулийн үржвэр, мөн $N_i$ нь модулийн урвуу $N_i := M_i^{-1} \bmod{m_i}$ байг. Тэгвэл congruence-үүдийн системийн шийд нь:

$$a \equiv \sum_{i=1}^k a_i M_i N_i \pmod{m_1 m_2 \cdots m_k}$$

Бүх $i$-гийн хувьд $a \bmod{m_i}$-г тооцоолох замаар энэ нь үнэхээр шийд болохыг шалгаж болно. $i \neq j$-ийн хувьд $M_j$ нь $m_i$-ийн үржвэр тул бидэнд

$$\begin{array}{rcll} a & \equiv & \sum_{j=1}^k a_j M_j N_j & \pmod{m_i} \\ & \equiv & a_i M_i N_i & \pmod{m_i} \\ & \equiv & a_i M_i M_i^{-1} & \pmod{m_i} \\ & \equiv & a_i & \pmod{m_i} \end{array}$$

Implementation¶

struct Congruence {
    long long a, m;
};

long long chinese_remainder_theorem(vector<Congruence> const& congruences) {
    long long M = 1;
    for (auto const& congruence : congruences) {
        M *= congruence.m;
    }

    long long solution = 0;
    for (auto const& congruence : congruences) {
        long long a_i = congruence.a;
        long long M_i = M / congruence.m;
        long long N_i = mod_inv(M_i, congruence.m);
        solution = (solution + a_i * M_i % M * N_i) % M;
    }
    return solution;
}

Харилцан анхны биш модулийн шийд¶

Дурдсанчлан дээрх алгоритм нь зөвхөн харилцан анхны модуль $m_1, m_2, \dots m_k$-ийн хувьд ажиллана.

Харилцан анхны биш тохиолдолд congruence-үүдийн систем нь $\text{lcm}(m_1, m_2, \dots, m_k)$ модулиар яг ганц шийдтэй байх, эсвэл огт шийдгүй байна.

Жишээ нь дараах системд эхний congruence нь шийд сондгой болохыг, хоёр дахь congruence нь шийд тэгш болохыг илэрхийлж байна. Тоо нэгэн зэрэг сондгой бас тэгш байх боломжгүй тул шийд байхгүй нь тодорхой.

$$\left\{\begin{align} a & \equiv 1 \pmod{4} \\ a & \equiv 2 \pmod{6} \end{align}\right.$$

Систем шийдтэй эсэхийг тодорхойлох нь нэлээд энгийн. Хэрэв шийдтэй бол бид анхны алгоритмыг ашиглан бага зэрэг өөрчилсөн congruence-үүдийн системийг бодож болно.

Ганц congruence $a \equiv a_i \pmod{m_i}$ нь $a \equiv a_i \pmod{p_j^{n_j}}$ congruence-үүдийн системтэй эквивалент бөгөөд энд $p_1^{n_1} p_2^{n_2}\cdots p_k^{n_k}$ нь $m_i$-ийн анхны үржигдэхүүнд задаргаа юм.

Энэ баримтыг ашиглан бид congruence-үүдийн системийг зөвхөн анхны тооны зэргийг модуль болгон агуулсан систем болгон өөрчилж болно. Жишээ нь дээрх congruence-үүдийн систем дараахтай эквивалент:

$$\left\{\begin{array}{ll} a \equiv 1 & \pmod{4} \\ a \equiv 2 \equiv 0 & \pmod{2} \\ a \equiv 2 & \pmod{3} \end{array}\right.$$

Анхнаасаа зарим модуль нийтлэг үржигдэхүүнтэй байсан тул бид ижил анхны тоонд суурилсан, гэхдээ өөр өөр анхны зэрэгтэй байж болох зарим congruence-ийн модулийг авна.

Ижил анхны тоонд суурилсан бүх congruence-ийн дотроос хамгийн өндөр анхны зэргийн модультай congruence нь хамгийн хүчтэй нь байхыг ажиглаж болно. Энэ нь өөр ямар нэг congruence-тэй зөрчилдөх эсвэл бусад бүх congruence-г аль хэдийн илэрхийлж байх болно.

Бидний тохиолдолд эхний congruence $a \equiv 1 \pmod{4}$ нь $a \equiv 1 \pmod{2}$-г илэрхийлэх бөгөөд улмаар хоёр дахь congruence $a \equiv 0 \pmod{2}$-той зөрчилдөнө. Тиймээс энэ congruence-үүдийн систем шийдгүй.

Хэрэв зөрчил байхгүй бол тэгшитгэлийн систем шийдтэй. Бид хамгийн өндөр анхны зэргийн модультайгаас бусад бүх congruence-г үл тоомсорлож болно. Эдгээр модуль одоо харилцан анхны болсон тул бид үүнийг дээрх хэсгүүдэд авч үзсэн алгоритмаар бодож болно.

Жишээ нь дараах систем $\text{lcm}(10, 12) = 60$ модулиар шийдтэй.

$$\left\{\begin{align} a & \equiv 3 \pmod{10} \\ a & \equiv 5 \pmod{12} \end{align}\right.$$

Congruence-үүдийн систем нь дараах congruence-үүдийн системтэй эквивалент:

$$\left\{\begin{align} a & \equiv 3 \equiv 1 \pmod{2} \\ a & \equiv 3 \equiv 3 \pmod{5} \\ a & \equiv 5 \equiv 1 \pmod{4} \\ a & \equiv 5 \equiv 2 \pmod{3} \end{align}\right.$$

Ижил анхны модультай цорын ганц congruence нь $a \equiv 1 \pmod{4}$ ба $a \equiv 1 \pmod{2}$ юм. Эхнийх нь хоёр дахийг аль хэдийн илэрхийлж байгаа тул бид хоёр дахийг үл тоомсорлож, оронд нь дараах харилцан анхны модультай системийг бодож болно:

$$\left\{\begin{align} a & \equiv 3 \equiv 3 \pmod{5} \\ a & \equiv 5 \equiv 1 \pmod{4} \\ a & \equiv 5 \equiv 2 \pmod{3} \end{align}\right.$$

Энэ нь $53 \pmod{60}$ шийдтэй бөгөөд үнэхээр $53 \bmod{10} = 3$ ба $53 \bmod{12} = 5$.

Гарнерийн алгоритм¶

CRT-ийн бас нэг үр дагавар бол бид том тоог бага бүхэл тооны массив ашиглан илэрхийлж болох явдал юм.

Маш том тоотой олон тооцоолол хийхийн оронд (1000 оронтой тоог хуваахыг бодоод үз, энэ нь өртөг өндөртэй байж болно) та хэдэн харилцан анхны модуль сонгож, том тоог congruence-үүдийн систем хэлбэрээр илэрхийлж, бүх үйлдлийг тэгшитгэлийн систем дээр хийж болно. $m_1 m_2 \cdots m_k$-ээс бага дурын тоо $a$-г $a_1, \ldots, a_k$ массив хэлбэрээр илэрхийлж болно, энд $a \equiv a_i \pmod{m_i}$.

Дээрх алгоритмыг ашиглан та хэрэгтэй үедээ том тоог дахин сэргээж болно.

Эсвэл та тоог холимог суурьт илэрхийллээр илэрхийлж болно:

$$a = x_1 + x_2 m_1 + x_3 m_1 m_2 + \ldots + x_k m_1 \cdots m_{k-1} \text{ энд }x_i \in [0, m_i)$$

Гарнерийн алгоритм гэсэн тусгай өгүүлэлд авч үзсэн Гарнерийн алгоритм нь $x_i$ коэффициентүүдийг тооцоолдог. Эдгээр коэффициентээр та бүтэн тоог сэргээж болно.