Шугаман congruence тэгшитгэл¶

Энэ тэгшитгэл дараах хэлбэртэй:

$$a \cdot x \equiv b \pmod n,$$

энд $a$, $b$ ба $n$ нь өгөгдсөн бүхэл тоо, $x$ нь үл мэдэгдэх бүхэл тоо юм.

$[0, n-1]$ интервалаас $x$ утгыг олох шаардлагатай (тооны шулуун дээр бие биенээсээ $n \cdot k$-гаар ялгаатай төгсгөлгүй олон шийд байж болох нь тодорхой, энд $k$ нь дурын бүхэл тоо). Хэрэв шийд цор ганц биш бол бид бүх шийдийг хэрхэн олохыг авч үзнэ.

Урвуу элемент олох замаар бодох¶

Эхлээд $a$ ба $n$ харилцан анхны ($\gcd(a, n) = 1$) байх энгийн тохиолдлыг авч үзье. Тэгвэл $a$-гийн урвуу-г олж, тэгшитгэлийн хоёр талыг урвуугаар үржүүлснээр бид цор ганц шийд авч болно.

$$x \equiv b \cdot a ^ {- 1} \pmod n$$

Одоо $a$ ба $n$ харилцан анхны биш ($\gcd(a, n) \ne 1$) тохиолдлыг авч үзье. Тэгвэл шийд үргэлж оршихгүй (жишээ нь $2 \cdot x \equiv 1 \pmod 4$ шийдгүй).

$g = \gcd(a, n)$ гэе, өөрөөр хэлбэл $a$ ба $n$-ийн хамгийн их ерөнхий хуваагч (энэ тохиолдолд нэгээс их).

Тэгвэл хэрэв $b$ нь $g$-д хуваагдахгүй бол шийд байхгүй. Үнэндээ дурын $x$-ийн хувьд тэгшитгэлийн зүүн тал $a \cdot x \pmod n$ нь үргэлж $g$-д хуваагддаг бол баруун тал нь түүнд хуваагддаггүй тул шийд байхгүй гэж гарна.

Хэрэв $g$ нь $b$-г хуваадаг бол тэгшитгэлийн хоёр талыг $g$-д хуваах замаар ($a$, $b$ ба $n$-г $g$-д хуваах) бид шинэ тэгшитгэл авна:

$$a^\prime \cdot x \equiv b^\prime \pmod{n^\prime}$$

энд $a^\prime$ ба $n^\prime$ аль хэдийн харилцан анхны бөгөөд бид ийм тэгшитгэлийг хэрхэн бодохыг аль хэдийн сурсан. Бид $x$-ийн шийд болгон $x^\prime$-г авна.

Энэ $x^\prime$ нь мөн анхны тэгшитгэлийн шийд болох нь тодорхой. Гэвч энэ нь цорын ганц шийд байхгүй. Анхны тэгшитгэл яг $g$ шийдтэй болохыг харуулж болох бөгөөд тэдгээр нь дараах хэлбэртэй байна:

$$x_i \equiv (x^\prime + i\cdot n^\prime) \pmod n \quad \text{энд } i = 0 \ldots g-1$$

Дүгнэвэл шугаман congruence тэгшитгэлийн шийдийн тоо нь $g = \gcd(a, n)$ эсвэл тэгтэй тэнцүү байна гэж хэлж болно.

Өргөтгөсөн Евклидийн алгоритмаар бодох¶

Бид шугаман congruence-г дараах Диофантын тэгшитгэл болгон дахин бичиж болно:

$$a \cdot x + n \cdot k = b,$$

энд $x$ ба $k$ нь үл мэдэгдэх бүхэл тоо.

Энэ тэгшитгэлийг бодох аргыг Шугаман Диофантын тэгшитгэл өгүүлэлд тайлбарласан бөгөөд энэ нь Өргөтгөсөн Евклидийн алгоритм-ыг хэрэглэхээс бүрдэнэ.

Мөн тэнд олдсон нэг шийдээс энэ тэгшитгэлийн бүх шийдийг олох аргыг тайлбарласан бөгөөд сайтар авч үзвэл энэ арга нь өмнөх хэсэгт тайлбарласан аргатай яг эквивалент юм.