Модулийн тоог харьцуулах онол. Натурал тоогоор харьцуулах

Хэрэв хоёр бүхэл тоо бол a (\displaystyle a)Тэгээд b (\displaystyle b)хуваах үед m (\displaystyle m)ижил үлдэгдэл өгөх, тэдгээрийг нэрлэдэг харьцуулах боломжтой(эсвэл адил үлдэгдэл) модулийн дугаар m (\displaystyle m) . Загвар:/фрэйм ​​Тоонуудын харьцуулалт a (\displaystyle a)Тэгээд b (\displaystyle b)томъёогоор бичсэн ( харьцуулалт):

Тоо m (\displaystyle m)дуудсан модульхарьцуулалт.

Тодорхойлолт харьцуулах чадвартоо a (\displaystyle a)Тэгээд b (\displaystyle b)модуль m (\displaystyle m)дараах мэдэгдлүүдийн аль нэгтэй тэнцүү байна:

Баталгаа

Дээрх шинж чанаруудаас гадна харьцуулалт хийхэд дараах мэдэгдлүүд хүчинтэй байна.

Баталгаа

(\displaystyle a\equiv b(\pmod (m)).)

a − b = m t . (\displaystyle a-b=mt.)Учир нь m (\displaystyle m) d (\displaystyle d)

(\displaystyle a\equiv b(\pmod (m)).)

a − b = m t = c d t = q d , (q = c t) (\displaystyle a-b=mt=cdt=qd,(q=ct))

Баталгаа

(\displaystyle a\equiv b(\pmod (m)).)

a ≡ b (mod m i) , i = 1 , 2 , . ..

a − b (\displaystyle a-b)

Үр дагавар:

Тоонуудын дарааллаар модулийн хувьд харьцуулж болноТэгээд , анхны хүчин зүйл болгон каноник задрал нь хэлбэртэй байна m = ∏ i = 1 d p i α i , (\displaystyle m=\prod _(i=1)^(d)p_(i)^(\альфа _(i)),) m (\displaystyle m)шаардлагатай бөгөөд хангалттай a ≡ b (mod p i α i) , i = 1 , 2 , … , d (\displaystyle a\equiv b(\pmod (p_(i)^(\alpha _(i))))),\quad i= 1,2,\цэг,г)Тэгээд Харьцуулалт бүхий үйлдлүүдИжил модультай харьцуулах нь энгийн тэгш байдлын олон шинж чанартай байдаг. Жишээлбэл, тэдгээрийг нэмэх, хасах, үржүүлэх боломжтой: хэрэв тоонууд a 1 , a 2 , .Тэгээд b 1 ⋅ b 2 ⋅ .. m (\displaystyle m).

⋅ b n (\displaystyle b_(1)\cdot b_(2)\cdot ...\cdot b_(n)) a (\displaystyle a)Тэгээд b (\displaystyle b)Мөн модулийн хувьд харьцуулж болно m (\displaystyle m). Гэсэн хэдий ч, хэрэв модулиуд нь таарахгүй бол та эдгээр үйлдлийг харьцуулах замаар хийж чадахгүй. Харьцуулалтын хоёр хэсэгт ижил тоог нэмж оруулахаас гадна тэмдгийг өөрчилснөөр харьцуулалтын нэг хэсгээс нөгөөд шилжүүлэх боломжтой гэдгийг тусад нь тэмдэглэх нь зүйтэй. Хэрэв тоонуудТэгээд модулийн хувьд харьцуулж болно. m (\displaystyle m), дараа нь тэдний зэрэг a k (\displaystyle a^(k)) .

b k (\displaystyle b^(k)) a (\displaystyle a)Тэгээд b (\displaystyle b)ямар ч байгалийн дор m (\displaystyle m) k (\displaystyle k) Харьцуулалтын аль ч хэсэгт та модулийн бүхэл үржвэрийг нэмж болно, өөрөөр хэлбэл хэрэв тоонууд байвалхарьцуулж болохуйц модуль зарим тоо , дараа ньмодуль m (\displaystyle m) (a + t 1 (\displaystyle a+t_(1))Тэгээд -тай харьцуулах боломжтой b + t 2 (\displaystyle b+t_(2)) a (\displaystyle a)Тэгээд b (\displaystyle b) t 1 (\displaystyle t_(1)) m (\displaystyle m) t 2 (\displaystyle t_(2)) - дурын бүхэл тоонууд).Тэгээд харьцуулах боломжтой зарим бүхэл тоо, дараа нь тоонууд a q (\displaystyle aq) b q (\displaystyle bq) Тоонууд нь харьцуулж болохуйц модуль юм m q (\displaystyle mq)

,Хаана q (\displaystyle q)- бүхэлд нь. Гэсэн хэдий ч харьцуулалтыг ерөнхийд нь бие биенээсээ эсвэл өөр тоогоор хувааж болохгүй. Жишээ: 14 ≡ 20 (mod 6) (\displaystyle 14\equiv 20(\pmod (6)))

• Гэсэн хэдий ч 2-оор бууруулснаар бид алдаатай харьцуулалтыг олж авна:

GCD (\displaystyle a-b=mt.)(d , m) = 1 , (\displaystyle ((d,m)=1),) (\displaystyle a-b=mt.)Тэр .

• Хэрэв тоо

Дээрх жишээн дээрх шиг модультай харилцан адилгүй, дараа нь -аар багасгана энэ нь хориотой.Та харьцуулалтын хоёр тал болон модулийг нийтлэг хуваагчаар нэгэн зэрэг хувааж болно. Хэрэв .

a c ≡ b c (mod m c) (\displaystyle (ac)\equiv (bc)(\pmod (mc)))

, Тэр

a ≡ b (mod m) (\displaystyle a\equiv b(\pmod (m))) a (\displaystyle a)модуль m (\displaystyle m)Холбогдох тодорхойлолтууд Хасгалын ангиуд a (\displaystyle a)модуль m (\displaystyle m) Харьцуулж болох бүх тооны багц , дуудсанхасах анги , ба ихэвчлэн тэмдэглэгдсэн байдаг[ a ] ​​m (\displaystyle [a]_(m)) Хэрэвэсвэл a ¯ m (\displaystyle (\bar (a))_(m)) .

. Тэгэхээр харьцуулалт үлдэгдэл ангиудын тэгш эрхтэй тэнцүү байнамодуль m (\displaystyle m)[ a ] ​​m = [ b ] m (\displaystyle [a]_(m)=[b]_(m)) Ямар ч ангийн дугаарыг дууддагхасах m (\displaystyle m). Баттай байя Тоонууд нь харьцуулж болохуйц модуль юм r (\displaystyle r) q = m t + r (\displaystyle q=mt+r), Хаана t (\displaystyle t)-бүхэл. Үлдэгдэлтэй тэнцэх хасалт Ямар ч ангийн дугаарыг дууддагдуудсан хамгийн бага сөрөг бус хасалт, мөн хасалт ρ (\displaystyle \rho), хамгийн жижиг үнэмлэхүй үнэ цэнэХолбогдох тодорхойлолтууд туйлын хамгийн бага хасалт. At r< m 2 {\displaystyle r<{\frac {m}{2}}} бид үүнийг ойлгодог ρ = r (\displaystyle \rho =r), өөрөөр ρ = r − m (\displaystyle \rho =r-m). Хэрэв m (\displaystyle m)- тэр ч байтугай ба r = m 2 (\ displaystyle r = (\ frac (m) (2)))Та харьцуулалтын хоёр тал болон модулийг нийтлэг хуваагчаар нэгэн зэрэг хувааж болно. ρ = − m 2 (\displaystyle \rho =-(\frac (m)(2))) .

Модуль харьцуулах боломжтой учраас m (\displaystyle m)бүхэл тооны олонлог дээрх эквивалент хамаарал, дараа нь модулийн үлдэгдлийн ангиуд m (\displaystyle m)эквивалент ангиудыг төлөөлөх; тэдний тоо тэнцүү байна m (\displaystyle m).

Бүх үлдэгдэл ангийн модулийн багц m (\displaystyle m)эсвэл гэж тэмдэглэнэ Z / m Z (\displaystyle \mathbb (Z) /m\mathbb (Z) )хасах анги Z / (m) (\displaystyle \mathbb (Z) /(м)) .

Нэмэх, үржүүлэх үйлдлүүд Z (\displaystyle \mathbb (Z))багц дээр харгалзах үйлдлүүдийг өдөөх Z m (\displaystyle \mathbb (Z)_(m)):

Эдгээр үйл ажиллагааны талаар маш олон байдаг Z m (\displaystyle \mathbb (Z)_(m))нь хязгаарлагдмал цагираг бөгөөд анхны тоон хувьд m (\displaystyle m)- хязгаарлагдмал талбар.

Суутгалын систем

Үлдэгдэл систем нь хязгаараас хэтрэхгүйгээр хязгаарлагдмал тооны тоон дээр арифметик үйлдлүүдийг хийх боломжийг олгодог. Суутгалын бүрэн системмодуль m (\displaystyle m)- дурын багц m (\displaystyle m)хосоор харьцуулшгүй модуль m (\displaystyle m)бүхэл тоо. Ихэвчлэн модулийн суутгалын бүрэн систем хэлбэрээр m (\displaystyle m)хоёр багцын нэгийг авна:

• хамгийн бага сөрөг бус үлдэгдэл, өөрөөр хэлбэл тоонууд:

• эсвэл туйлын хамгийн бага суутгал, тооноос бүрдэнэ

Хосоор харьцуулшгүй модулийн хамгийн их багц m (\displaystyle m)тоонууд нь нийлдэг m (\displaystyle m)Холбогдох тодорхойлолтууд өгөгдсөн суутгалын системмодуль m (\displaystyle m). Модулийн үлдэгдэл багассан аливаа систем m (\displaystyle m)агуулсан φ (м) (\displaystyle \varphi (м))элементүүд, хаана φ (⋅) (\displaystyle \varphi (\cdot))- Эйлер функц.

Жишээлбэл, тооны хувьд m = 42 (\displaystyle m=42). Суутгалын бүрэн системтоогоор илэрхийлж болно: 0 , 1 , 2 , 3 , … , 21 , 22 , 23 , … , 39 , 40 , 41 (\displaystyle 0,1,2,3,\ldots ,21,22,23,\ldots ,39,40, 41), А өгсөн - 1 , 5 , 11 , 13 , 17 , 19 , 23 , 25 , 29 , 31 , 37 , 41 (\displaystyle 1,5,11,13,17,19,23,25,29,31,37,41).

Талбай дээрх олон гишүүнтийн цагираг дахь харьцуулалт

Харьцуулалтыг шийдвэрлэх

Нэгдүгээр зэргийн харьцуулалт

Тооны онол, криптограф болон шинжлэх ухааны бусад салбарт эхний түвшний харьцуулалтын шийдлийг олох асуудал ихэвчлэн гарч ирдэг.

(\ displaystyle ax \ equiv b (\ pmod (m)).) Ийм харьцуулалтыг шийдэх нь тооцоолохоос эхэлдэг . Харьцуулах товчлолын дүрэм дараах байдалтай байна. d = (\ Displaystyle d =)(a , m) (\displaystyle (a,m))

x ≡ c a 1 x ≡ c b 1 ≡ a 1 − 1 b 1 (mod m 1) . , өөрөөр хэлбэл ийм тоог олоорой(\ displaystyle x \ equiv ca_ (1) x \ equiv cb_ (1) \ equiv a_ (1) ^ (-1) b_ (1) (\ pmod (m_ (1))).) , өөрөөр хэлбэл ийм тоог олооройҮнэ цэнийн практик тооцоо

хэлбэрээр:

c ≡ a 1 − 1 ≡ a 1 φ (m 1) − 1 (mod m 1) (\displaystyle c\equiv a_(1)^(-1)\equiv a_(1)^(\varphi (m_(1) ))-1)(\pmod (m_(1))))Жишээ

Харьцуулбал 6 x ≡ 26 (mod 22) (\displaystyle 6x\equiv 26(\pmod (22)))бидэнд байгаа

, тиймээс модуль 22 харьцуулалт нь хоёр шийдэлтэй байна. 26-г 22-той харьцуулж болох 4-өөр сольж, дараа нь бүх гурван тоог 2-оор бууруулъя.

3 нь модуль 11-тэй нэгдмэл утгатай тул 11 модулийг урвуу болгож, олж болно

Харьцуулалтыг 4-ээр үржүүлснээр бид 11 модулийн шийдлийг олж авна.

Жишээ 2.Харьцуулалт өгсөн:

Модуль нь анхны тоо гэдгийг анхаарна уу. Эхний шийдэл бол Bezout хамаарлыг ашиглах явдал юм. Евклидийн алгоритм эсвэл Безутын харилцааны тухай өгүүлэлд өгөгдсөн программыг ашигласнаар бид тоонуудын хувьд энэ хамаарлыг олж харлаа.Тэгээд 100 (\displaystyle 100) 65537 (\displaystyle 65537)

17695 ⋅ 100 ≡ 1 (mod 65537) (\ displaystyle 17695 \ cdot 100 \ equiv 1 (\ pmod (65537)))

100 ⋅ 725495 ≡ 41 (mod 65537) (\displaystyle 100\cdot 725495\эквив 41(\pmod (65537))) Үүнээс үзэхэд анхны харьцуулалтын шийдэл байдаг. Үүнийг түүнтэй харьцуулах зүйлээр солих нь илүү тохиромжтой 4588 (\displaystyle 4588) (хуваалтын үлдэгдэл 725495 (\displaystyle 725495) 100 (\displaystyle 100)дээр ). Хариулт:

x ≡ 4588 (mod 65537) .

(\ displaystyle x \ equiv 4588 (\ pmod (65537)).) Хоёрдахь шийдлийн арга нь илүү энгийн бөгөөд хурдан бөгөөд Bezout хамаарлыг бүтээх шаардлагагүй боловч Евклидийн алгоритмтай адил юм.Алхам 1. Модулийг x-ийн коэффициентээр үлдэгдэлтэй хуваана: 65537 = 100 ⋅ 655 + 37 (\displaystyle 65537=100\cdot 655+37). Анхны харьцуулалтын хоёр талыг хуваалтаар үржүүлнэ 655 (\displaystyle 655)болон нэмэх 37 x (\displaystyle 37x); бид авах: 100 (\displaystyle 100) 65537 x ≡ 26855 + 37 x (mod 65537) (\displaystyle 65537x\equiv 26855+37x(\pmod (65537)))

, өөрөөр хэлбэл, тэгтэй харьцуулах боломжтой бөгөөд үүнээс: 37 x ≡ − 26855 (mod 65537) (\displaystyle 37x\equiv -26855(\pmod (65537)))Бид хүлээн авсан

x (\displaystyle x) коэффициент 100-ийн оронд 37. Дараагийн алхам бүрт бид нэгийг авах хүртэл ижил аргаар бууруулна.Алхам 2. Үүнтэй адилаар x-ийн шинэ коэффициентээр хуваана: 65537 = 37 ⋅ 1771 + 10 (\displaystyle 65537=37\cdot 1771+10). Анхны харьцуулалтын хоёр талыг хуваалтаар үржүүлнэ . Өмнөх алхамд олж авсан харьцуулалтын хоёр талыг хуваалтаар үржүүлье 1771 (\displaystyle 1771)

10 x (\displaystyle 10x) 1. ; Зүүн гар талыг дахин тэгээр сольж, бид олж авна. ТодорхойлолтТэгээд Хэрэв хоёр тоо нь 1 бол)хуваах үед аб хижил үлдэгдлийг өгнө r а.

, тэгвэл ийм тоонуудыг equiremainder эсвэл гэж нэрлэдэг 1. модулийн хувьд харьцуулж болно аМэдэгдэл ТодорхойлолтБолъё

зарим эерэг тоо. Дараа нь тоо бүр хүргэлж, үүнээс гадна, цорын ганц арга замаар хэлбэрээр төлөөлж болно аГэхдээ эдгээр тоонуудыг тохируулснаар авч болно тэнцүү 0, 1, 2,...,−1. Тиймээс

Энэ төлөөлөл өвөрмөц гэдгийг харуулъя. Ингэж бодъё ахоёр янзаар төлөөлж болно a=sp+rТэгээд a=s 1 а+х 1. Дараа нь

(2)

a − b = m t . х 1 нь 0,1, ..., тоонуудын аль нэгийг хүлээн авна. а−1, дараа нь үнэмлэхүй утга х 1 −хбага а. Гэхдээ (2) -аас үүнийг дагаж мөрддөг х 1 −холон а. Тиймээс х 1 =хТэгээд с 1 =с.

Тоо хдуудсан үлдэгдэл ангиудын тэгш эрхтэй тэнцүү байнатоо Тодорхойлолтмодуль а(өөрөөр хэлбэл тоо хтооны үлдэгдэл гэж нэрлэдэг Тодорхойлолт 725495 (\displaystyle 725495) а).

, тэгвэл ийм тоонуудыг equiremainder эсвэл гэж нэрлэдэг 2. Хэрэв хоёр тоо бол ТодорхойлолтТэгээд Хэрэв хоёр тоо нь 1 бол)Мөн модулийн хувьд харьцуулж болно аТа харьцуулалтын хоёр тал болон модулийг нийтлэг хуваагчаар нэгэн зэрэг хувааж болно. a−bхуваасан а.

Үнэхээр. Хэрэв хоёр тоо бол ТодорхойлолтТэгээд Хэрэв хоёр тоо нь 1 бол)Мөн модулийн хувьд харьцуулж болно а, дараа нь хуваах үед аижил үлдэгдэлтэй байна а. Дараа нь

хуваасан а, учир нь (3) тэгшитгэлийн баруун тал нь хуваагдана а.

, тэгвэл ийм тоонуудыг equiremainder эсвэл гэж нэрлэдэг 3. Хэрэв хоёр тооны зөрүү нь хуваагддаг бол а, дараа нь эдгээр тоонуудыг модулийн хувьд харьцуулж болно а.

Баталгаа. -ээр тэмдэглэе хТэгээд х 1 хуваагдлын үлдэгдэл ТодорхойлолтТэгээд Хэрэв хоёр тоо нь 1 бол) 725495 (\displaystyle 725495) а. Дараа нь

Жишээ 25≡39 (mod 7), −18≡14 (mod 4).

Эхний жишээнээс харахад 25-ыг 7-д хуваахад 39-тэй ижил үлдэгдэл гарна. Үнэхээр 25 = 3 7 + 4 (үлдэгдэл 4). 39=3·7+4 (үлдэгдэл 4). Хоёрдахь жишээг авч үзэхдээ үлдэгдэл нь модулиас бага сөрөг бус тоо байх ёстойг анхаарах хэрэгтэй (жишээ нь 4). Дараа нь бид бичиж болно: −18=−5·4+2 (үлдэгдэл 2), 14=3·4+2 (үлдэгдэл 2). Тиймээс −18-ыг 4-т хуваахад 2-ын үлдэгдэл, 14-ийг 4-т хуваахад 2-ын үлдэгдэл үлдэнэ.

Модулийн харьцуулалтын шинж чанарууд

Өмч 1. Хэнд ч зориулав ТодорхойлолтТэгээд аҮргэлж

үргэлж харьцуулалт байдаггүй

Хаана λ тоонуудын хамгийн том нийтлэг хуваагч юм мТэгээд а.

Баталгаа. Болъё λ тоонуудын хамгийн том нийтлэг хуваагч мТэгээд а. Дараа нь

a − b = m t . m(a−b)хуваасан к d (\displaystyle d)

Тиймээс

Тэгээд мнь тооны хуваагчдын нэг юм а d (\displaystyle d)

Хаана h=pqs.

Бид сөрөг модулиуд дээр суурилсан харьцуулалтыг зөвшөөрөх боломжтой гэдгийг анхаарна уу, i.e. харьцуулалт a≡bгорим( а) энэ тохиолдолд ялгаа гэсэн үг a−bхуваасан а. Харьцуулалтын бүх шинж чанарууд сөрөг модулиудын хувьд хүчинтэй хэвээр байна.

Үл мэдэгдэх нэг зүйлтэй харьцуулах xшиг харагдаж байна

Хаана. Хэрэв Тодорхойлолт n -д хуваагдахгүй м, үүнийг ингэж нэрлэдэг зэрэгхарьцуулалт.

Шийдвэрээрхарьцуулалт нь дурын бүхэл тоо юм x 0 , үүний төлөө

Хэрэв X 0 харьцуулалтыг хангасан бол 9 харьцуулалтын шинж чанарын дагуу харьцуулах боломжтой бүх бүхэл тоо x 0 модуль м. Тиймээс ижил үлдэгдэл ангиллын модульд хамаарах бүх харьцуулалтын шийдлүүд Т, бид үүнийг нэг шийдэл гэж үзэх болно. Тиймээс харьцуулалт нь түүнийг хангадаг үлдэгдлийн бүрэн системийн элементүүд байгаа тул олон шийдэлтэй байдаг.

Шийдлийн багц нь давхцаж байгаа харьцуулалтыг гэнэ тэнцүү.

2.2.1 Нэгдүгээр зэргийн харьцуулалт

Нэг үл мэдэгдэх зүйлтэй нэгдүгээр зэрэглэлийн харьцуулалт Xшиг харагдаж байна

(2.2)

Теорем 2.4. Харьцуулалт нь дор хаяж нэг шийдэлтэй байхын тулд тоо байх шаардлагатай бөгөөд хангалттай Хэрэв хоёр тоо нь 1 бол) GCD-д хуваагдсан( Тодорхойлолт, м).

Баталгаа.Эхлээд бид зайлшгүй шаардлагатайг нотолж байна. Болъё г = GCD( Тодорхойлолт, м) Тэгээд X 0 - харьцуулах шийдэл. Дараа нь , өөрөөр хэлбэл ялгаа Өө 0 − Хэрэв хоёр тоо нь 1 бол) хуваасан Т.Тэгэхээр ийм бүхэл тоо байна q, Юу Өө 0 − Хэрэв хоёр тоо нь 1 бол) = кв. Эндээс Хэрэв хоёр тоо нь 1 бол)= аа 0 − кв. Тэгээд тэрнээс хойш г, нийтлэг хуваагчийн хувьд тоог хуваадаг АТэгээд Т,дараа нь хасах болон хасах хоёр хуваагдана г, тиймээс Хэрэв хоёр тоо нь 1 бол) хуваасан г.

Одоо хангалттай гэдгийг баталъя. Болъё г- тоонуудын хамгийн том нийтлэг хуваагч АТэгээд Т,Тэгээд Хэрэв хоёр тоо нь 1 бол) хуваасан г. Дараа нь хуваагдах байдлын тодорхойлолтоор дараах бүхэл тоонууд байна Тодорхойлолт 1 , Хэрэв хоёр тоо нь 1 бол) 1 ,Т 1 , Юу .

Өргөтгөсөн Евклидийн алгоритмыг ашиглан бид 1 = gcd( тоонуудын шугаман дүрслэлийг олно. Тодорхойлолт 1 , м 1 ):

зарим хүмүүсийн хувьд x 0 , y 0 . Сүүлийн тэгшитгэлийн хоёр талыг үржүүлье Хэрэв хоёр тоо нь 1 бол) 1 г:

эсвэл ижил зүйл юу вэ,

,

Энэ нь харьцуулалтын шийдэл юм. □

Жишээ 2.10. Харьцуулалт 9 X gcd(9, 12) = 3 ба 6 нь 3-т хуваагддаг тул = 6 (mod 12) шийдэлтэй байна. □

Жишээ 2.11. Харьцуулалт 6x= 9 (mod 12) нь шийдэлгүй, учир нь gcd(6, 12) = 6, 9 нь 6-д хуваагддаггүй. □

Теорем 2.5. Харьцуулалт (2.2)-ыг шийдвэрлэх боломжтой ба г = GCD( Тодорхойлолт, м). Дараа нь харьцуулах шийдлүүдийн багц (2.2) бүрдэнэ г модулийн үлдэгдэл ангиуд Т,тухайлбал, хэрэв X 0 - шийдлүүдийн нэг бол бусад бүх шийдлүүд байна

Баталгаа.Болъё X 0 - харьцуулалтын шийдэл (2.2), өөрөөр хэлбэл Тэгээд , . Тиймээс ийм зүйл байдаг q, Юу Өө 0 − Хэрэв хоёр тоо нь 1 бол) = кв. Одоо оронд нь сүүлчийн тэгшитгэлд орлуулж байна X 0 хэлбэрийн дурын шийдэл, эндээс бид илэрхийллийг олж авдаг

, -д хуваагддаг м. □

Жишээ 2.12. Харьцуулалт 9 X=6 (mod 12) нь gcd(9, 12)=3 тул яг гурван шийдэлтэй. Эдгээр шийдлүүд: X 0 = 2, x 0 + 4 = 6, X 0 + 2∙4=10.□

Жишээ 2.13. Харьцуулалт 11 X=2 (mod 15) нь өвөрмөц шийдэлтэй X 0 = 7, учир нь GCD(11,15)=1.□

Бид нэгдүгээр зэрэглэлийн харьцуулалтыг хэрхэн шийдвэрлэхийг танд үзүүлэх болно. Ерөнхий байдлыг алдалгүйгээр бид GCD( Тодорхойлолт, t) = 1. Дараа нь (2.2) харьцуулах шийдлийг жишээлбэл, Евклидийн алгоритмыг ашиглан хайж болно. Үнэн хэрэгтээ, Евклидийн өргөтгөсөн алгоритмыг ашиглан бид 1-ийг тоонуудын шугаман хослол болгон төлөөлдөг. ТодорхойлолтТэгээд Т:

Энэ тэгш байдлын хоёр талыг үржүүлье Хэрэв хоёр тоо нь 1 бол), бид авах: Хэрэв хоёр тоо нь 1 бол) = abq + mrb, хаана abq - Хэрэв хоёр тоо нь 1 бол) = - mrb, тэр нь Тодорхойлолт ∙ (bq) = Хэрэв хоёр тоо нь 1 бол)(mod м) Мөн bq- харьцуулалтын шийдэл (2.2).

Өөр нэг шийдэл бол Эйлерийн теоремыг ашиглах явдал юм. GCD(a,) гэдэгт бид дахин итгэж байна. Т)= 1. Эйлерийн теоремыг хэрэглэнэ. . Харьцуулалтын хоёр талыг үржүүлнэ Хэрэв хоёр тоо нь 1 бол): . Сүүлийн илэрхийллийг дахин бичих , бид үүнийг харьцуулах шийдэл болохыг олж авна (2.2).

Одоо GCD ( Тодорхойлолт, м) = г>1. Дараа нь Тодорхойлолт = Тодорхойлолттг, м = мтг, хаана GCD( А 1 , м 1) = 1. Үүнээс гадна зайлшгүй шаардлагатай Хэрэв хоёр тоо нь 1 бол) = Хэрэв хоёр тоо нь 1 бол) 1 г, харьцуулалтыг шийдвэрлэх боломжтой байхын тулд. Хэрэв X 0 - харьцуулах шийдэл А 1 x = Хэрэв хоёр тоо нь 1 бол) 1 (mod м 1) бөгөөд GCD-ээс хойш цорын ганц нь ( А 1 , м 1) = 1, тэгвэл X 0 шийдэл, харьцуулалт байх болно А 1 xd = дб 1 (mod м 1), өөрөөр хэлбэл анхны харьцуулалт (2.2). Амрах г- 2.5 теоремоор 1 шийд олдсон.

Хоёр бүхэл тооны хувьд XТэгээд цагтХэрэв тэдгээрийн ялгаа нь тэнцүү бол харьцуулах харьцааг паритетаар оруулъя тэгш тоо. Өмнө нь оруулсан гурван тэнцлийн нөхцөл хангагдсан эсэхийг шалгахад хялбар байдаг. Ингэж оруулсан эквивалент харьцаа нь бүхэл тоон багцыг тэгш тооны дэд олонлог ба сондгой тооны дэд олонлог гэсэн хоёр салангид дэд олонлогт хуваадаг.

Энэ тохиолдлыг ерөнхийд нь авч үзвэл, зарим тогтмол натурал тооны үржвэрээр ялгаатай хоёр бүхэл тоо нь эквивалент гэж хэлэх болно. Энэ нь Гауссын танилцуулсан модулийг харьцуулах үзэл баримтлалын үндэс суурь юм.

Тоо А, харьцуулах боломжтой Хэрэв хоёр тоо нь 1 бол)модуль м, хэрэв тэдгээрийн ялгаа нь тогтмолд хуваагддаг бол натурал тоо м, тэр нь а - бхуваасан м. Үүнийг бэлгэдлийн хувьд дараах байдлаар бичнэ.

a ≡ b(mod m),

мөн ингэж уншина: Ахарьцуулж болохуйц модуль зарим тоо Хэрэв хоёр тоо нь 1 бол)модуль м.

Харьцуулалт ба тэгш байдлын гүн гүнзгий аналогийн ачаар ийм байдлаар нэвтрүүлсэн хамаарал нь тоонууд нь олон тоогоор ялгаатай байх тооцоог хялбаршуулдаг. м, үнэндээ ялгаагүй (харьцуулалт нь m-ийн зарим үржвэр хүртэлх тэгш байдал учраас).

Жишээлбэл, 7 ба 19-ийн тоог харьцуулах боломжтой модуль 4, гэхдээ харьцуулах боломжгүй модуль 5, учир нь 19-7=12 нь 4-т хуваагддаг ба 5-д хуваагддаггүй.

Мөн тоо гэж хэлж болно Xмодуль мбүхэл тоонд хуваахад үлдсэнтэй тэнцүү X 725495 (\displaystyle 725495) м, учир нь

x=km+r, r = 0, 1, 2, ... , m-1.

Өгөгдсөн модулийн дагуу тоонуудын харьцуулалт нь эквивалентын бүх шинж чанартай эсэхийг шалгахад хялбар байдаг. Тиймээс бүхэл тоонуудын багцыг модулийн хувьд харьцуулж болох тооны ангиудад хуваадаг м. Ийм ангиудын тоо тэнцүү байна м, мөн ижил ангиллын бүх тоонуудыг хуваах үед мижил үлдэгдлийг өгнө. Жишээлбэл, хэрэв м= 3, тэгвэл бид 3-ын үржвэр (3-т хуваахад 0-ийн үлдэгдэл өгдөг), 3-т хуваагдахад 1 үлдэгдэл үлдээдэг тоонуудын ангилал, гарах тоонуудын ангилал гэсэн гурван анги авна. 3-т хуваахад үлдэгдэл 2.

Харьцуулалтыг ашиглах жишээг сайн мэддэг хуваагдах шалгуураар өгсөн болно. Нийтлэг тооны дүрслэл nтоогоор аравтын системТооцоолол нь дараах хэлбэртэй байна.

n = c10 2 + b10 1 + a10 0,

Хаана а, б, в,- баруунаас зүүн тийш бичигдсэн тооны цифрүүд, тиймээс А- нэгжийн тоо, Хэрэв хоёр тоо нь 1 бол)- аравтын тоо гэх мэт. 10 мянгаас хойш ≡ Ямар ч k≥0-ийн хувьд 1(mod9) байвал бичигдсэн зүйлээс ингэж гарна

n ≡ c + b + a(mod9),

эндээс 9-д хуваагдах тестийн дараа: nЦифрүүдийн нийлбэр нь 9-д хуваагдах тохиолдолд л 9-д хуваагдана. Энэ үндэслэл нь 9-ийг 3-аар солиход мөн хамаарна.

Бид 11-д хуваагдах тестийг авдаг. Харьцуулалт:

10≡- 1 (mod11), 10 2 ≡ 1(mod11) 10 3 ≡- 1(mod11) гэх мэт. Тийм ч учраас n ≡ c - b + a - ….(mod11).

Тиймээс, n a - b + c -... цифрүүдийн ээлжлэн нийлбэр нь 11-д хуваагдах тохиолдолд л 11-д хуваагдана.

Жишээлбэл, 9581 тооны цифрүүдийн ээлжлэн нийлбэр нь 1 - 8 + 5 - 9 = -11, энэ нь 11-д хуваагддаг бөгөөд энэ нь 9581 тоо 11-д хуваагддаг гэсэн үг юм.

Хэрэв харьцуулалт байгаа бол: , тэгвэл тэдгээрийг тэгшитгэлтэй ижил аргаар гишүүнээр нь нэмж, хасаж, үржүүлж болно.

Харьцуулалтыг үргэлж бүхэл тоогоор үржүүлж болно:

хэрэв , тэгвэл

Гэсэн хэдий ч, харьцуулалтыг аль нэг хүчин зүйлээр багасгах нь үргэлж боломжгүй байдаг, гэхдээ 42 ба 12 тоонуудын хувьд нийтлэг хүчин зүйл 6-аар багасгах боломжгүй; ийм бууралт нь буруу үр дүнд хүргэдэг, учир нь .

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

Аливаа бүхэл тоог харьцуулах боломжтой гэдгийг дээр дурдсан мдараах тоонуудын аль нэгээр: 0, 1, 2,... , m-1.

Энэ цувралаас гадна ижил шинж чанартай бусад цуврал тоонууд байдаг; Тиймээс, жишээлбэл, ямар ч тоог mod 5-ыг дараах тоонуудын аль нэгтэй нь харьцуулж болно: 0, 1, 2, 3, 4, гэхдээ дараах тоонуудын аль нэгтэй харьцуулж болно: 0, -4, -3, -2, - 1, эсвэл 0, 1, -1, 2, -2. Ийм тоонуудын аль нэгийг модуль 5-ын үлдэгдлийн бүрэн систем гэж нэрлэдэг.

Тиймээс үлдэгдэл горимын бүрэн систем мямар ч цуврал мбие биетэйгээ харьцуулах боломжгүй хоёр тоо. Ихэвчлэн 0, 1, 2, ..., гэсэн тооноос бүрдэх бүрэн хасалтын системийг ашигладаг. м-1. Тоо хасаж байна nмодуль мнь хэлтсийн үлдсэн хэсэг юм n 725495 (\displaystyle 725495) м, энэ нь төлөөллийн дагуу n = км + r, 0<х<м- 1.