dm3 (Лекция), страница 8

Ðåáðà 12, 14, 23, 24, 35, 36, 45, 56.2. Ðåáðà 12, 14, 16, 23, 25, 26, 36, 45.3. Ðåáðà 12, 14, 24, 25, 35, 36, 45, 56.4. Ðåáðà 12, 14, 23, 24, 25, 35, 36, 45.5. Ðåáðà 12, 14, 15, 23, 26, 35, 45, 56.6. Ðåáðà 12, 14, 23, 24, 25, 35, 36, 56.7. Ðåáðà 12, 14, 23, 24, 26, 36, 45, 56.8. Ðåáðà 12, 14, 15, 25, 34, 36, 45, 56.9. Ðåáðà 12, 13, 14, 24, 25, 26, 36, 45.10. Ðåáðà 12, 13, 14, 23, 24, 36, 45, 56.11. Ðåáðà 12, 14, 16, 23, 25, 35, 45, 46.12. Ðåáðà 12, 13, 14, 23, 25, 45, 46, 56.13.

Ðåáðà 12, 14, 25, 26, 35, 36, 45, 56.14. Ðåáðà 12, 14, 15, 23, 26, 35, 36, 45.15. Ðåáðà 12, 14, 23, 24, 25, 26, 35, 45.16. Ðåáðà 12, 13, 15, 16, 23, 34, 36, 56.17. Ðåáðà 12, 14, 23, 24, 34, 35, 36, 56.18. Ðåáðà 13, 14, 15, 23, 25, 36, 46, 56.19. Ðåáðà 12, 14, 15, 23, 25, 26, 35, 45.418Àëãåáðà âû÷åòîâ ïî ìîäóëþmÏóñòü m íàòóðàëüíîå ÷èñëî, m ≥ 2.

Íà ìíîæåñòâå Z öåëûõ ÷èñåë îïðåäåëèìäâóõìåñòíûå îïåðàöèè +, −, · (mod m)m êàê ôóíêöèè Z → {0, 1, . . . , m − 1}.Ðåçóëüòàòîì îïåðàöèè x + y, x − y, x · y (mod m) ÿâëÿåòñÿ îñòàòîê îò äåëåíèÿ îáû÷íîé ñóììû (ñîîòâåòñòâåííî ðàçíîñòè, ïðîèçâåäåíèÿ) öåëûõ ÷èñåë x, yíà m. Íàïðèìåð, 6 + 11 = 2 (mod 5), 9 − 20 = 1 (mod 6), 3 · 12 = 4 (mod 8),23 = 2·2·2 = 1 (mod 7). ×èñëà 0, 1, . .

. , m−1 íàçûâàþòñÿm. Ìíîæåñòâî {0, 1, . . . , m − 1} ñ îïåðàöèÿìè+, · (mod m) íàçûâàåòñÿm è îáîçíà÷àåòñÿ êàêZm :ñëîæåíèÿ, âû÷èòàíèÿ è óìíîæåíèÿïî ìîäóëþöàòåëüíûìè âû÷åòàìè ïî ìîäóëþàëãåáðîé âû÷åòîâ ïî ìîäóëþíàèìåíüøèìè íåîòðè-Zm = ({0, 1, . . . , m − 1}; +, · (mod m)).Îïåðàöèè +, · (mod m) äîñòàòî÷íî çàäàòü òîëüêî íà ìíîæåñòâå {0, 1, . . . ,m − 1}. Ýòî ìîæíî ñäåëàòü, óêàçûâàÿ ðåçóëüòàòû îïåðàöèé â äâóõ òàáëèöàõ ðàçìåðà m × m, íàïðèìåð,x 0 1+(÷àñòî x + y(mod 2)y01x 0 1·0 11 0(mod 2)y01(mod 2) çàïèñûâþò êàê x ⊕ y ),x 0 1 2x 0 1 2+y(mod 3) 0120 1 21 2 02 0 1·y(mod 3) 012x 0 1 2 3+0 00 1y0(mod 4)1230123123023010 0 00 1 20 2 1x 0 1 2 33012·y0(mod 4)1230000012302020321 àëãåáðå âàæíåéøåé çàäà÷àåé ÿâëÿåòñÿ ðåøåíèå óðàâíåíèé.

Ðàññìîòðèì ïðîñòåéøåå óðàâíåíèåax = b(mod m)42(1)â àëãåáðå âû÷åòîâ.Òåîðåìà 1 (î ðåøåíèè óðàâíåíèÿ ïåðâîé ñòåïåíè â àëãåáðå âû÷å-Ïóñòü d =ÍÎÄ(a, m) (íàèáîëüøèé îáùèé äåëèòåëü), òîãäà ñïðàâåäëèâîñëåäóþùåå.1. Åñëè ÷èñëî b íå äåëèòñÿ íà d, òî óðàâíåíèå (1) íå èìååò ðåøåíèÿ.2. Eñëè b êðàòíî d, òî óðàâíåíèå (1) èìååò â ìíîæåñòâå {0, 1, . . . , m − 1}ðîâíî d ðàçëè÷íûõ ðåøåíèé. Åñëè x0 ðåøåíèå, òî îñòàëüíûå d − 1 ðåøåíèéåñòüòîâ).xk = x0 + k(m/d)(mod m),Ïðèìåð 1.Óðàâíåíèå 12x = 45ÍÎÄ(12, 32) = 4, à 45 íå÷åòíî.Ïðèìåð 2. Ðàññìîòðèì óðàâíåíèå20x = 44k = 1, . .

. , d − 1.(mod 32)íå èìååò ðåøåíèé, òàê êàê(mod 108).(2)Èìååì ÍÎÄ(20, 108) = 4, 44 êðàòíî 4. Pàçäåëèì îáå ÷àñòè óðàâíåíèÿ (2) è ìîäóëüíà 4, ïîëó÷èì áîëåå ïðîñòîå óðàâíåíèå5x = 11(mod 27).(3)Äëÿ íåãî ÍÎÄ(5, 27) = 1, ïîýòîìó óðàâíåíèå (3) èìååò ðîâíî îäíî ðåøåíèåx0 ∈ {0, 1, . . . , 26}. Íåòðóäíî ïðîâåðèòü, ÷òî x0 = 13. (Ê ñîæàëåíèþ, íàéòè ðåøåíèå ìîæíî òîëüêî ïåðåáîðîì ðàçëè÷íûõ ýëåìåíòîâ êîíå÷íîãî ìíîæåñòâà âû÷åòîâ,õîòÿ âî ìíîãèõ ñëó÷àÿõ ïåðåáîð íå ïîëíûé.) Òîãäà îñòàëüíûå ðåøåíèÿ óðàâíåíèÿ(2) â ìíîæåñòâå {0, 1, . . .

, 107} åñòüx1 = 13 + 27 = 40, x2 = 13 + 2 · 27 = 67, x3 = 12 + 3 · 27 = 94.Îòâåò:x = 13, 40, 67, 94.Ïîÿñíèì, êàê ìîæíî ñîêðàòèòü ïåðåáîð ïðè ðåøåíèè óðàâíåíèÿ (3). ×èñëà 11 è11 + 27n, n ∈ Z, èìåþò îäèíàêîâûé îñòàòîê îò äåëåíèÿ íà 27, ïîýòîìó äîñòàòî÷íîíàéòè òàêîå íàèìåíüøåå íàòóðàëüíîå n, ÷òîáû ÷èñëî 11 + 27n äåëèëîñü íà 5.Äëÿ n = 1 ÷èñëî 11 + 27 = 38 íå äåëèòñÿ íà 5, äëÿ n = 2 ïîëó÷àåì ÷èñëî11 + 27 · 2 = 65, êðàòíîå 5. Òàêèì îáðàçîì, óðàâíåíèå (3) ðàâíîñèëüíî óðàâíåíèþ5x = 65 (mod 27), îòêóäà x = x0 = 65/5 = 13.Ê óðàâíåíèþ (1) ñâîäÿòñÿ è áîëåå ñëîæíûå âèäû óðàâíåíèé â àëãåáðå âû÷åòîâ.Ðàññìîòðèì ñèñòåìóðèöåé.ëèíåéíûõ óðàâíåíèé43ïî ìîäóëþ m ñ êâàäðàòíîé ìàò-Tåîðåìà 2.Åñëè êâàäðàòíàÿ ñèñòåìà ëèíåéíûõ óðàâíåíèé a11 x1 + · · · +a1n xn = b1(mod m)an1 x1 + · · · +ann xn = bn(mod m)....èìååò îïðåäåëèòåëü ∆ òàêîé, ÷òî ÍÎÄ(∆, m) = 1, òî ýòà ñèñòåìà óðàâíåíèéèìååò ðîâíî îäíî ðåøåíèå (x1, .

. . , xn) â ìíîæåñòâå {0, 1, . . . , m − 1}n.Ïðèìåð 3.Ðåøèì ñèñòåìó ïîðÿäêà 23x − 2y = 1 (mod m)4x + 7y = 2 (mod m)äëÿ ìîäóëåé m = 4, 9, 10, 16, 20, 30, 50, 100. Îïðåäåëèòåëü ñèñòåìû 3 · 7 + 2 · 4 = 29ÿâëÿåòñÿ ïðîñòûì ÷èñëîì, óñëîâèå òåîðåìû 2 âûïîëíÿåòñÿ, ñèñòåìà èìååò åäèíñòâåííîå ðåøåíèå äëÿ êàæäîãî ìîäóëÿ. Íàéäåì åãî. Âû÷èòàÿ èç âòîðîãî óðàâíåíèÿ ïåðâîå, ïîëó÷àåìx + 9y = 1(mod m).(4)Óìíîæèì óðàâíåíèå (4) íà 3 è âû÷òåì èç ðåçóëüòàòà ïåðâîå óðàâíåíèå èñõîäíîéñèñòåìû, ïîëó÷èì29y = 2,x = 1 − 9y(mod m).Ýòè ôîðìóëû îäíîçíà÷íî îïðåäåëÿþò ðåøåíèå.

Çàïèøåì ðåøåíèÿ (ïàðû (x, y))äëÿ êàæäîãî èç ðàññìàòðèâàåìûõ ìîäóëåé â òàáëèöó:m 4 9 10 16 20 30 50 100x 3 1 9 7 19 19 9 59y 2 1 8 10 18 28 38 38Êâàäðàòíîå óðàâíåíèåax2 + bx + c = 0(mod m)ìîæíî ðåøèòü íåñêîëüêèìè ñïîñîáàìè. Îäèí èç íèõ ðàçëîæåíèå íà ìíîæèòåëèax2 + bx + c = a(x − x1 )(x − x2 )(mod m).Äðóãîé ñïîñîá ñîñòîèò â ïðèìåíåíèè òåîðåìû Âèåòà7 è ôîðìóë äëÿ êîðíåéx1 + x2 = a−1 b,x1 x2 = a−1 c(mod m).Òðåòèé ñïîñîá ñîñòîèò â ïðèìåíåíèè îáùåé ôîðìóëû äëÿ êîðíåé êâàäðàòíîãîóðàâíåíèÿ â àðèôìåòèêå ïî ìîäóëþ m:px = (2a) (−b ± b2 − 4ac )−17 Ôðàíñóà(mod m).Âèåò (15401603) ôðàíöóçñêèé ìàòåìàòèê, "îòåö àëãåáðû"44Ïðèìåíÿòü åå ìîæíî òîëüêî ïðè íå÷åòíîì ìîäóëå m.  ýòîì ñëó÷àå ôîðìóëóìîæíî óïðîñòèòü:x = a−1 (−2−1 b ±p(2−1 b)2 − ac )(mod m).(5)Ïðèìåð 4.Ðåøèì óðàâíåíèå x2 + x + 2 = 0 (mod 11).

Åãî ìîæíî çàïèñàòüâ âèäå x2 − 10x + 24 = 0 (mod 11) è ðàçëîæèòüx2 + x + 2 = x2 − 10x + 24 = (x − 4)(x − 6)(mod 11),îòêóäàx1 = 4,x2 = 6.(6)Ëåãêî ïðîâåðèòü âûïîëíèìîñòü ôîðìóë Âèåòà: 4+6 = −1,Åñëè æå ïðèìåíèòü òðåòèé ñïîñîá è ôîðìóëó (5), òîx = −2−1 ±4×6 = 2(mod 11).pp√(2−1 )2 − 2 = −6 ± 62 − 2 = 5 ± 1(mod 11).√Èìååòñÿäâàçíà÷åíèÿêâàäðàòíîãîêîðíÿèç1ïîìîäóëþ11:1 = 1 (mod 11)√1 = −1 = 10 (mod 11), ïîýòîìó ïîëó÷àåì òå æå ðåøåíèÿ (6).è9Óðàâíåíèÿ â öåëûõ ÷èñëàõ äèñêðåòíîé ìàòåìàòèêå ïðèìåíÿþòñÿ òîëüêî öåëûå ÷èñëà, à ðàçðåøèìîñòü óðàâíåíèé â öåëûõ ÷èñëàõ îïðåäåëÿåòñÿ ñâîéñòâàìè äåëèìîñòè.

Íàïðèìåð, î÷åíü ïðîñòîå óðàâíåíèå 2x = 1 íå èìååò öåëî÷èñëåííûõ ðåøåíèé.  àëãåáðå âû÷åòîâ ðàññìàòðèâàþòñÿ îñòàòêè îò äåëåíèÿ öåëûõ ÷èñåë íà ìîäóëü, ïîýòîìó âû÷åòû ïðèìåíÿþòñÿ ïðè àíàëèçå è ðåøåíèè öåëî÷èñëåííûõ óðàâíåíèé. Ðàññìîòðèì îäíî èçòàêèõ óðàâíåíèé ëèíåéíîå óðàâíåíèå îòíîñèòåëüíî n íåèçâåñòíûõa1 x1 + · · · + an xn = c.Çäåñü êîýôôèöèåíòû a1 , . . .

, an , c è íåèçâåñòíûå x1 , . . . , xn öåëûå ÷èñëà. Íåîáõîäèìûì óñëîâèåì ðàçðåøèìîñòè òàêîãî óðàâíåíèÿ ÿâëÿåòñÿ äåëèìîñòü êîýôôèöèåíòà c íà ÍÎÄ(a1 , . . . , an ). Èíòåðåñíî, ÷òî ýòî æå óñëîâèå ÿâëÿåòñÿ è äîñòàòî÷íûì äëÿ ðàçðåøèìîñòè óðàâíåíèÿ. Åñëè n = 1, òî ðåøåíèå, êîãäà îíî ñóùåñòâóåò,åäèíñòâåííî: x1 = c/a1 . Ïðè n ≥ 2 óðàâíåíèå â ñëó÷àå ðàçðåøèìîñòè èìååò áåñêîíå÷íîå ìíîæåñòâî ðåøåíèé.Ðàññìîòðèì óðàâíåíèå ñ äâóìÿ íåèçâåñòíûìè. Äëÿ óïðîùåíèÿ îáîçíà÷åíèéçàïèøåì åãî â âèäåax + by = c,a > 0,45b 6= 0.(1)Ïóñòü d =ÍÎÄ(a, |b|). Tîãäà:åñëè c íå êðàòíî d, òî óðàâíåíèå (1) íåðàçðåøèìî,åñëè c êðàòíî d, òî óðàâíåíèå (1) èìååò áåñêîíå÷íîå ìíîæåñòâî ðåøåíèé, çàâèñÿùèõ îò öåëî÷èñëåííîãî ïàðàìåòðà k:Òåîðåìà.x = x0 + bk,ãäåx0ax0 = c ëþáîå öåëîå ïðè b = ±1.y=c − ax0− ak,bk ∈ Z,(2)ïðè |b| > 1,(mod |b|)Ïðèìåð.Ðàññìîòðèì óðàâíåíèå 3x − 7y = −24.

Èìååì a = 3, b = −7,d =ÍÎÄ(3, 7) = 1, óðàâíåíèå ðàçðåøèìî. Èç óðàâíåíèÿ â àëãåáðå âû÷åòîâ3x0 = −24 (mod 7) íàõîäèì x0 = 6. Òîãäà, ñîãëàñíî (2),x = 6 − 7k,y=−24 − 3 · 6− 3k = 6 − 3k,−7k ∈ Z.Ïîëåçíî áûâàåò ñäåëàòü ïðîâåðêó. Ïîäñòàâëÿÿ ïîëó÷åííûå âûðàæåíèÿ x = x(k),y = y(k) â ëåâóþ ÷àñòü èñõîäíîãî óðàâíåíèÿ, âèäèì, ÷òî ñëàãàåìûå, ñîäåðæàùèåk , óíè÷òîæàþòñÿ è ïîëó÷àåòñÿ ÷èñëî −24.Ôîðìóëû (2) îïðåäåëÿþò. Èç íåãî çàìåíîé ïåðåìåííîé k íàêîíêðåòíûå öåëûå ÷èñëà ïîëó÷àåòñÿ áåñêîíåñêîå ìíîæåñòâî.Âðàññìîòðåííîì ïðèìåðå ïðè k = 0 ïîëó÷àåì ÷àñòíîå ðåøåíèå (x, y) = (6, 6), ïðèk = 1 ÷àñòíîå ðåøåíèå (x, y) = (−1, 3) è òàê äàëåå.îáùåå ðåøåíèå÷àñòíûõ ðåøåíèéÇàäà÷à (ïîñëåäíÿÿ) äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ.Ðåøèòå ñëåäóþùåå óðàâíåíèå â öåëûõ ÷èñëàõ.1.2.3.4.5.6.7.8.9.10.2x − 11y = 5.4x + 7y = −20.9x − 5y = 10.15x − 4y = −2.12x + 5y = 6.3x + 16y = 5.14x − 9y = −3.5x + 16y = 8.7x + 11y = 9.11x − 3y = −20.11.1213.14.15.16.17.18.19.20.7x + 12y = −6.8x − 17y = 4.16x − 7y = −5.12x + 5y = 10.9x − 7y = −30.11x + 8y = 6.5x − 14y = 3.4x + 17y = −6.9x − 11y = 8.9x + 13y = −7.Ðåøåíèÿ âñåõ çàäà÷ ïðèñûëàéòå ïî àäðåñó MeshchaninovDG@mpei.ru4610×èñëà Ñòèðëèíãà 2-ãî ðîäà è ÷èñëà ÁåëëàÊîëè÷åñòâî ðàçáèåíèé n-ìíîæåñòâà íà k íåïóñòûõ ïîäìíîæåñòâ îáîçíà÷àåòñÿ êàêSn,k .

Çíà÷åíèÿ Sn,k , n, k ≥ 0, íàçûâàþòñÿ.Íàïðèìåð, S3,2 = 3, òàê êàê èìååòñÿ ðîâíî 3 ðàçáèåíèÿ ìíîæåñòâà {1, 2, 3} íà2 ïîäìíîæåñòâà, îäíî èç êîòîðûõ ñîäåðæèò ðîâíî îäèí ýëåìåíò, à âòîðîå äâà:1|23, 2|13, 3|12.Óêàæåì ïðîñòåéøèå ñâîéñòâà ýòèõ ÷èñåë.n≥1Sn,1 = Sn,n = 1, Sn,0 = 0.Äëÿ ÷èñëà S0,0 , íå èìåþùåãî ñîäåðæàòåëüíîãî ñìûñëà, ïðèìåì ôîðìàëüíîåñîãëàøåíèå S0,0 = 1.Òåîðåìà 1.Sn,k:÷èñëàìè Ñòèðëèíãà 2-ãî ðîäàÅñëè, òîÄëÿ ÷èñåëñïðàâåäëèâà ñëåäóþùàÿ ðåêóððåíòíàÿ ôîðìóëàSn,k = Sn−1,k−1 + kSn−1,k .Äîêàçàòåëüñòâî. Ðàññìîòðèì óíèâåðñàëüíîå ìíîæåñòâî U= {e1 , .

. . , en−1 , en }.Âñå åãî ðàçáèåíèÿ íà k íåïóñòûõ ïîäìíîæåñòâ ðàçäåëèì íà äâå ãðóïïû:ñîäåðæàùèå îäíîýëåìåíòíîå ïîäìíîæåñòâî {en }, êîëè÷åñòâî òàêèõ ðàçáèåíèéðàâíî ÷èñëó Sn−1,k−1 ðàçáèåíèé (n − 1) ïîäìíîæåñòâà {e1 , . . . , en−1 } íà k − 1 íåïóñòûõ ïîäìíîæåñòâ;íå ñîäåðæàùèå ïîäìíîæåñòâà {en }, ïðè ýòîì ýëåìåíò en ìîæåò îêàçàòüñÿ âëþáîì èç k íåïóñòûõ ïîäìíîæåñòâ (n − 1)-ìíîæåñòâà {e1 , .