Основы теории чисел

Ãëàâà 1. Îñíîâû òåîðèè ÷èñåë 1.1. Îñíîâíûå îïðåäåëåíèÿ def Ãîâîðÿò, ÷òî öåëîå ÷èñëî a äåëèòñÿ íà öåëîå ÷èñëî b, åñëè a = bq äëÿ íåêîòîðîãî öåëîãî ÷èñëà q .  ýòîì ñëó÷àå ãîâîðÿò òàêæå ¾a êðàòíî . b¿ (a .. b) è ¾b ÿâëÿåòñÿ äåëèòåëåì ÷èñëà a¿ (b|a). def Öåëîå ÷èñëî íàçûâàåòñÿ ïðîñòûì, åñëè îíî êðàòíî òîëüêî ñàìîìó ñåáå è 1. Ïðîñòîå ÷èñëî îáîçíà÷àåòñÿ p. Íå ïðîñòûå öåëûå ÷èñëà íàçûâàþòñÿ ñîñòàâíûìè. def Âñÿêîå ÷èñëî, ÿâëÿþùååñÿ îäíîâðåìåííî äåëèòåëåì äâóõ öåëûõ ÷èñåë m è n, íàçûâàåòñÿ èõ îáùèì äåëèòåëåì; ìàêñèìàëüíîå èç òàêèõ ÷èñåë íàçûâàåòñÿ íàèáîëüøèì îáùèì äåëèòåëåì (ÍÎÄ) è îáîçíà÷àåòñÿ ÍÎÄ(m, n) èëè ïðîñòî (m, n). def Äâà öåëûõ ÷èñëà m è n íàçûâàþòñÿ âçàèìíî-ïðîñòûìè, åñëè èõ ÍÎÄ ðàâåí 1, ò.å. ÍÎÄ(m, n)=1. 1.2. Àëãîðèòì Åâêëèäà Âíå çàâèñèìîñòè îò äåëèìîñòè öåëîãî ÷èñëà a íà öåëîå ÷èñëî b 6= 0, ÷èñëî a âñåãäà ìîæíî ðàçäåëèòü íà b ñ îñòàòêîì, òî åñòü ïðåäñòàâèòü â âèäå: a = bq +r, ãäå 0 6 r < |b|.  ýòîì ñëó÷àå ÷èñëî a íàçûâàþò äåëèìîå, b äåëèòåëü, q  ÷àñòíîå, r  îñòàòîê. Àëãîðèòì: Ïóñòü a è b  öåëûå ÷èñëà, íå ðàâíûå îäíîâðåìåííî íóëþ, è ïîñëåäîâàòåëüíîñòü ÷èñåë a > b > r1 > r2 > r3 > r4 > . . . > rn > rn+1 = 0 îïðåäåëåíà òàê, ÷òî êàæäîå rk  ýòî îñòàòîê îò äåëåíèÿ äâóõ ïðåäûäóùèõ 1 2 Ãëàâà 1. Îñíîâû òåîðèè ÷èñåë ÷èñåë, òî åñòü: a = bq0 + r1 , b = r1 q 1 + r2 , r1 = r2 q2 + r3 , ··· rk−2 = rk−1 qk−1 + rk , ··· rn−2 = rn−1 qn−1 + rn , rn−1 = rn qn . Òîãäà ÍÎÄ(a, b) = rn (ïîñëåäíåìó íåíóëåâîìó îñòàòêó). Ïðèìåð: Íàéòè: 1) ÍÎÄ(144, 233); 2) ÍÎÄ(1202, 4848); 3) ÍÎÄ(10223, 33341); 4) ÍÎÄ(1234567, 7654321). 1.3. Ôàêòîðèçàöèÿ ÷èñëà Îñíîâíàÿ òåîðåìà àðèôìåòèêè: Êàæäîå íàòóðàëüíîå ÷èñëî n > 1 ìîæíî ïðåäñòàâèòü â âèäå n = p1 ·. . .·pk , ãäå p1 , . . . , pk  ïðîñòûå ÷èñëà, ïðè÷¼ì òàêîå ïðåäñòàâëåíèå åäèíñòâåííî (åñëè íå ó÷èòûâàòü ïîðÿäîê ñëåäîâàíèÿ ìíîæèòåëåé). Ñëåäñòâèå: Êàæäîå íàòóðàëüíîå ÷èñëî n åäèíñòâåííûì îáðàçîì ïðåäñòàâèìî â âèäå n = pα1 1 · pα2 2 · . . . · pαk k , ãäå p1 < p2 < . . . < pk  ïðîñòûå ÷èñëà, è α1 , . . . , αk  íåêîòîðûå íàòóðàëüíûå ÷èñëà. Òàêîå ïðåäñòàâëåíèå ÷èñëà n íàçûâàåòñÿ åãî êàíîíè÷åñêèì ðàçëîæåíèåì íà ïðîñòûå ñîìíîæèòåëè èëè ôàêòîðèçàöèåé ÷èñëà n. Ïî êàíîíè÷åñêîìó ðàçëîæåíèþ ÷èñåë m è n íà ïðîñòûå ìíîæèòåëè ìîæíî ëåãêî âû÷èñëèòü èõ ÍÎÄ: n = pα1 1 · ... · pαk k , 1.4. 3 Ñðàâíèìîñòü ÷èñåë m = pβ1 1 · ... · pβkk , ãäå p1 , . . . , pk  ðàçëè÷íûå ïðîñòûå ÷èñëà, à α1 , . . . , αk è β1 , . . . , βk  íåîòðèöàòåëüíûå öåëûå ÷èñëà (îíè ìîãóò áûòü íóëÿìè, åñëè ñîîòâåòñòâóþùåå ïðîñòîå îòñóòñòâóåò â ðàçëîæåíèè). Òîãäà ÍÎÄ(n, m) è ÍÎÊ[n, m] âûðàæàþòñÿ ôîðìóëàìè: min(α1 ,β1 ) · ... · pk max(α1 ,β1 ) · ... · pk (n, m) = p1 [n, m] = p1 min(αk ,βk ) , max(αk ,βk ) . Åñëè ÷èñåë áîëåå äâóõ: a1 , a2 , . . . an , èõ ÍÎÄ íàõîäèòñÿ ïî ñëåäóþùåìó àëãîðèòìó: α2 = (a1 , a2 ) α3 = (α2 , a3 ) ......... αn = (αn−1 , an )  ýòî è åñòü èñêîìûé ÍÎÄ. Ïðèìåð: Íàéòè ÍÎÄ ÷èñåë 1) 60 è 48; 2) 23 35 57 79 11 è 29 37 55 73 13; 3) 25 33 55 76 132 17 è 34 53 77 19 232 . 1.4. Ñðàâíèìîñòü ÷èñåë def Åñëè äâà öåëûõ ÷èñëà a è b ïðè äåëåíèè íà m äàþò îäèíàêîâûå îñòàòêè, òî îíè íàçûâàþòñÿ ñðàâíèìûìè (èëè ðàâíîîñòàòî÷íûìè) ïî ìîäóëþ ÷èñëà m. Ñðàâíèìîñòü ÷èñåë a è b çàïèñûâàåòñÿ â âèäå ôîðìóëû (ñðàâíåíèÿ): a ≡ b (mod m). ×èñëî m íàçûâàåòñÿ ìîäóëåì ñðàâíåíèÿ. Îïðåäåëåíèå ñðàâíèìîñòè ÷èñåë a è b ïî ìîäóëþ m ðàâíîñèëüíî ëþáîìó èç ñëåäóþùèõ óòâåðæäåíèé: • ðàçíîñòü ÷èñåë a è b äåëèòñÿ íà m áåç îñòàòêà; • ÷èñëî a ìîæåò áûòü ïðåäñòàâëåíî â âèäå a = b + k · m, ãäå k  íåêîòîðîå öåëîå ÷èñëî. 4 Ãëàâà 1. Îñíîâû òåîðèè ÷èñåë Íàïðèìåð, ÷èñëà 32 è -10 ñðàâíèìû ïî ìîäóëþ 7, òàê êàê îáà ÷èñëà ïðè äåëåíèè íà 7 äàþò îñòàòîê 4: 32 = 7 · 4 + 4; −10 = 7 · (−2) + 4. Òàêæå ÷èñëà 32 è -10 ñðàâíèìû ïî ìîäóëþ 7, òàê êàê èõ ðàçíîñòü 32 − (−10) = 42 äåëèòñÿ íà 7 è ê òîìó æå èìååò ìåñòî ïðåäñòàâëåíèå 32 = 6 · 7 + (−10). 1.5. Ñâîéñòâà ñðàâíåíèÿ Îòíîøåíèå ñðàâíåíèÿ ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè è îáëàäàåò ìíîãèìè ñâîéñòâàìè îáû÷íûõ ðàâåíñòâ. Íàïðèìåð, èõ ìîæíî ñêëàäûâàòü è ïåðåìíîæàòü: åñëè a1 ≡ b1 (mod n); a2 ≡ b2 (mod n), òî a1 a2 ≡ b1 b2 (mod n); a1 + a2 ≡ b1 + b2 (mod n). Ñðàâíåíèÿ, îäíàêî, íåëüçÿ, âîîáùå ãîâîðÿ, äåëèòü äðóã íà äðóãà èëè íà äðóãèå ÷èñëà. Ïðèìåð: 14 ≡ 20 (mod 6), îäíàêî, ñîêðàòèâ íà 2, ìû ïîëó÷àåì îøèáî÷íîå ñðàâíåíèå: 7 ≡ 10 (mod 6). Ïðàâèëà ñîêðàùåíèÿ äëÿ ñðàâíåíèé ñëåäóþùèå. • Ìîæíî äåëèòü îáå ÷àñòè ñðàâíåíèÿ íà ÷èñëî, âçàèìíî ïðîñòîå ñ ìîäóëåì: åñëè ac ≡ bc (mod n) è ÍÎÄ(c, n) = 1, òî a ≡ b (mod n). • Ìîæíî îäíîâðåìåííî ðàçäåëèòü îáå ÷àñòè ñðàâíåíèÿ è ìîäóëü íà èõ îáùèé äåëèòåëü: åñëè ac ≡ bc (mod nc), òî a ≡ b (mod n). • Íåëüçÿ òàêæå âûïîëíÿòü îïåðàöèè ñî ñðàâíåíèÿìè, åñëè èõ ìîäóëè íå ñîâïàäàþò. Äðóãèå ñâîéñòâà: • Åñëè a ≡ b (mod m1 ) è a ≡ b (mod m2 ), òî a ≡ b (mod m), ãäå m = [m1, m2]. • Åñëè a ≡ b (mod m), òî a, b ñðàâíèìû ïî ëþáîìó ìîäóëþ  äåëèòåëþ m. 1.6. Êëàññû âû÷åòîâ def Ìíîæåñòâî âñåõ ÷èñåë, ñðàâíèìûõ ñ a ïî ìîäóëþ m íàçûâàåòñÿ êëàññîì âû÷åòîâ a ïî ìîäóëþ m, è îáû÷íî îáîçíà÷àåòñÿ [a]m èëè ām . Òàêèì îáðàçîì, ñðàâíåíèå a ≡ b (mod n) ðàâíîñèëüíî ðàâåíñòâó êëàññîâ âû÷åòîâ [a]m = [b]m . 1.7. Òàáëèöà ñëîæåíèÿ è óìíîæåíèÿ ïî ìîäóëþ M è 5 P Ïîñêîëüêó ñðàâíåíèå ïî ìîäóëþ m ÿâëÿåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè íà ìíîæåñòâå öåëûõ ÷èñåë Z, òî êëàññû âû÷åòîâ ïî ìîäóëþ m ïðåäñòàâëÿþò ñîáîé êëàññû ýêâèâàëåíòíîñòè; èõ êîëè÷åñòâî ðàâíî m. Ìíîæåñòâî âñåõ êëàññîâ âû÷åòîâ ïî ìîäóëþ m îáîçíà÷àåòñÿ Zm . Îïåðàöèè ñëîæåíèÿ è óìíîæåíèÿ íà Z èíäóöèðóþò ñîîòâåòñòâóþùèå îïåðàöèè íà ìíîæåñòâå Zm : [a]m + [b]m = [a + b]m ; [a]m · [b]m = [a · b]m . Îòíîñèòåëüíî ýòèõ îïåðàöèé ìíîæåñòâî Zm ÿâëÿåòñÿ êîíå÷íûì êîëüöîì, à åñëè m ïðîñòîå  êîíå÷íûì ïîëåì. 1.7. Òàáëèöà ñëîæåíèÿ è óìíîæåíèÿ ïî ìîäóëþ m è p Ñîñòàâèì òàáëèöó ñëîæåíèÿ è óìíîæåíèÿ ÷èñåë â Z6 : + 1 2 3 4 5 1 2 3 4 5 1 1 2 3 4 5 2 2 3 4 5 1 3 3 4 5 1 2 4 4 5 1 2 3 5 5 1 2 3 4 · 1 2 3 4 5 1 1 2 3 4 5 2 2 4 2 4 3 3 3 3 4 4 2 4 2 5 5 4 3 2 1 È òàáëèöó óìíîæåíèÿ ÷èñåë â Z7 : · 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 4 6 1 3 5 3 3 6 2 5 1 4 4 4 1 5 2 6 3 5 5 3 1 6 4 2 6 6 5 4 3 2 1 1.8. Îáðàòèìûå ýëåìåíòû ïî ìîäóëþ m def Îñòàòîê (âû÷åò) ïî ìîäóëþ m íàçûâàåòñÿ îáðàòèìûì, åñëè â ïðîèçâåäåíèè ñ êàêèì-òî äðóãèì îñòàòêîì îí äàåò 1. Äðóãèìè ñëîâàìè a îáðàòèì, åñëè óðàâíåíèå ax ≡ 1 (mod m) èìååò ðåøåíèå, ò.å. åñëè â ñòðîêå a òàáëèöû åñòü åäèíèöà. 6 Ãëàâà 1. Îñíîâû òåîðèè ÷èñåë Îáðàòèìûìè ïî ìîäóëþ m ÿâëÿþòñÿ òîëüêî òå îñòàòêè, êîòîðûå âçàìíî ïðîñòû ñ m. Ïî òàáëèöå óìíîæåíèÿ ìîæíî íàéòè âñå îáðàòèìûå ýëåìåíòû ïî ìîäóëþ. Íà îáðàòèìûå ýëåìåíòû ìîæíî ¾äåëèòü¿: åñëè a îáðàòèì, òî ñðàâíåíèå ax ≡ b (mod m) èìååò åäèíñòâåííîå ðåøåíèå ïðè ëþáîì b. Åñëè ýëåìåíò, êîòîðûé äàåò 1 â ïðîèçâåäåíèè ñ a îáîçíà÷èòü ÷åðåç a−1 . Òîãäà x ≡ a−1 b (mod m) áóäåò ðåøåíèåì ñðàâíåíèÿ, ò.ê. ax ≡ a(a−1 b) ≡ (aa−1 )b ≡ 1 · b ≡ b (mod m). 1) Ðåøèòü ñðàâíåíèÿ: à) 3x ≡ 1 (mod 7); á) 5x + 8 ≡ 4 (mod 7); â) 4x − 3 ≡ 2 (mod 6); ã) 7x − 3 ≡ 5 (mod 11); ä) 7x + 17 ≡ 13 (mod 19);   x + 2y = 1 2) Ðåøèòü ñèñòåìó óðàâíåíèé: y + 2z = 2   2x + z = 1 a) â Z3 ; b) â Z5 . 1.9. Êèòàéñêàÿ òåîðåìà îá îñòàòêàõ Êèòàéñêàÿ òåîðåìà îá îñòàòêàõ: Ïóñòü m1 , m2 , . . . , mn  ïî- ïàðíî âçàèìíî ïðîñòûå ÷èñëà, ò.å. ÍÎÄ(mi , mj ) = 1 äëÿ âñåõ 1 6 i 6= j 6 n. Òîãäà ñèñòåìà ñðàâíåíèé   x ≡ a1 (mod m1 ),   x ≡ a2 (mod m2 ), ..  .    x ≡ a (mod m ). n n èìååò ðåøåíèå, êîòîðîå åäèíñòâåííî ïî ìîäóëþ M = m1 · m2 · · · · · mn . M , 1 6 j 6 n, è zj  ðåøåíèå ñðàâíåíèÿ Äàëåå, åñëè Mj = mj Mj zj ≡ aj (mod mj ) äëÿ êàæäîãî j , òîãäà ðåøåíèå ñèñòåìû èìååò âèä x≡ n X j=1 Mj zj (mod M ). 1.9. 7 Êèòàéñêàÿ òåîðåìà îá îñòàòêàõ Äîêàçàòåëüñòâî. ëþáîì k, 1 6 k 6 n, Ïóñòü x îïðåäåëåíî ñîãëàñíî òåîðåìå. Òîãäà ïðè x≡ n X Mj zj (mod M ), Mj zj (mod mk ) = j=1 òàê ÷òî x≡ n X Mj zj (mod M ) ≡ j=1 n X j=1 = Mk zk (mod mk ) ≡ ak (mod mk ). ïîýòîìó x óäîâëåòâîðÿåò n ñðàâíåíèÿì: x ≡ ak (mod mk ) ïðè 1 6 k 6 n. Åñëè x0 òàêæå óäîâëåòâîðÿåò n ñðàâíåíèÿì, òîãäà x − x0 ≡ 0 (mod mk ) ïðè 1 6 k 6 n. Ïîñêîëüêó ÍÎÄ(mi , mj ) = 1 ïðè i 6= j , ïîëó÷àåì x ≡ x0 (mod M ). ò.å. ðåøåíèå x åäèíñòâåííî ïî ìîäóëþ M . Ïðèìåð: Íàéòè ðåøåíèå ñèñòåìû ñðàâíåíèé ( x ≡ 5 (mod 4) x ≡ 7 (mod 11) Ò.ê. ÍÎÄ(4, 11) = 1 ⇒ M = 44, M1 = 11, M2 = 4. Âñïîìîãàòåëüíàÿ ñèñòåìà ( ( ( 11z1 ≡ 5 (mod 4) 3z1 ≡ 5 (mod 4) (·3) z1 ≡ 3 (mod 4) ⇒ ⇒ 4z2 ≡ 7 (mod 11) 4z2 ≡ 7 (mod 11) (·3) z2 ≡ 10 (mod 11) Îòêóäà íàõîäèì ðåøåíèå ñèñòåìû x ≡ 11 · 3 + 4 · 10 Ïðèìåð: (mod 44) ⇒ x ≡ 73 (mod 44) ⇒ x ≡ 29 Íàéòè ðåøåíèå ñèñòåìû ñðàâíåíèé  x ≡ 4 (mod 5)    x ≡ 3 (mod 4)  x ≡ 2 (mod 7)    x ≡ 6 (mod 9) (mod 44). 8 Ãëàâà 1. Îñíîâû òåîðèè ÷èñåë Êèòàéñêàÿ òåîðåìà îá îñòàòêàõ äîïóñêàåò îáîáùåíèå íà ñëó÷àé íå âçàèìíî ïðîñòûõ ìîäóëåé m1 , m2 , . . . , mn . Òåîðåìà: Ñèñòåìà ñðàâíåíèé   x ≡ a1 (mod m1 ),   x ≡ a2 (mod m2 ), ..  .    x ≡ a (mod m ). n n èìååò ðåøåíèå òîãäà è òîëüêî òîãäà, êîãäà ai − aj êðàòíî ÍÎÄ(mi , mj ) äëÿ âñåõ 1 6 i < j 6 n. Åñëè ðåøåíèå ñóùåñòâóåò, òî îíî åäèíñòâåííî ïî ìîäóëþ ÍÎÊ[m1 · m2 · · · · · mn ]. Ïðèìåð: Íàéòè ðåøåíèå ñèñòåìû ñðàâíåíèé   x ≡ 1 (mod 3) x ≡ 3 (mod 4)   x ≡ 7 (mod 10) Ðåøåíèå ñðàâíåíèÿ x≡1 (mod 3) èìååò âèä 3t + 1. Ïîäñòàâëÿÿ ýòó âåëè÷èíó âî âòîðîå ñðàâíåíèå, ïîëó÷èì 3t + 1 ≡ 3 (mod 4). Ïîýòîìó 3t ≡ 2 (mod 4), îòêóäà t ≡ 2 (mod 4). Ïîýòîìó t = 4u + 2. Ïîäñòàâëÿÿ íàéäåííîå t â âûðàæåíèå äëÿ x, ïîëó÷èì ðåøåíèå ïåðâûõ äâóõ ñðàâíåíèé x = 3(4u + 2) + 1 ⇒ x = 12u + 7. Ïîäñòàâëÿåì íàéäåííîå ðåøåíèå â òðåòüå ñðàâíåíèå: 12u + 7 ≡ 7 (mod 10) ⇒ 2u ≡ 0 (mod 10) ⇒ u ≡ 0 (mod 5). Îòñþäà u = 5v äëÿ íåêîòîðîãî v , è ðåøåíèå ñèñòåìû x = 12(5v) + 7 = 60v + 7. 1.10. Ôóíêöèÿ Ýéëåðà def Êîëè÷åñòâî ïîëîæèòåëüíûõ öåëûõ ÷èñåë, ìåíüøèõ n è âçàèìíî ïðîñòûõ ñ n íàçûâàåòñÿ ôóíêöèåé Ýéëåðà è îáîçíà÷àåòñÿ ϕ(n). Ïðèìåð: ϕ(1) = 1; ϕ(5) = 4; ϕ(9) = 6; ϕ(2) = 1; ϕ(6) = 2; ϕ(10) = 4; ϕ(3) = 2; ϕ(7) = 6; ϕ(11) = 10; 1.11. 9 Óïðàæíåíèÿ ϕ(8) = 4; ϕ(12) = 4. Òåîðåìà (Ãàóññ): Åñëè n  ïîëîæèòåëüíîå öåëîå ÷èñëî, òî X ϕ(d) = n ϕ(4) = 2; d|n ãäå äåëèòåëè d ÿâëÿþòñÿ ïîëîæèòåëüíûìè äåëèòåëÿìè ÷èñëà n. Ïðèìåð: Ïóñòü n = 10. Òîãäà åãî äåëèòåëÿìè ÿâëÿþòñÿ ÷èñëà 1, 2, 5, 10. Ïî òåîðåìå ïîëó÷àåì: X ϕ(10) = ϕ(1) + ϕ(2) + ϕ(5) + ϕ(10) = 1 + 1 + 4 + 4 = 10. d|10 Òåîðåìà: Åñëè ÷èñëà n m  âçàèìíî ïðîñòûå, òî ϕ(nm) = ϕ(n)ϕ(m). Òåîðåìà: Åñëè p  ïðîñòîå ÷èñëî, òî ϕ(pk ) = pk − pk−1 . Ñëåäñòâèå: Öåëîå ïîëîæèòåëüíîå ÷èñëî p ÿâëÿåòñÿ ïðîñòûì òîãäà è òîëüêî òîãäà, êîãäà ϕ(pk ) = p − 1. Ñëåäñòâèå: ϕ(2k ) = 2k−1 . Òåîðåìà: Åñëè n  öåëîå ïîëîæèòåëüíîå ÷èñëî ñ ðàçëîæåíèåì íà ïðîñòûå ìíîæèòåëè âèäà n = pα1 1 · pα2 2 · . . . · pαk k , òî ϕ(n) = k Y pαi i −1 (pi i=1  k  Y
1 − 1) = n 1− . pi i=1 Òåîðåìà: Åñëè öåëîå ÷èñëî n áîëüøå 2, òî ϕ(n)  ÷åòíîå. Òåîðåìà (Óèëñîí): Öåëîå ïîëîæèòåëüíîå ÷èñëî p ÿâëÿåòñÿ ïðî- ñòûì òîãäà è òîëüêî òîãäà, êîãäà (p − 1)! ≡ −1 (mod p). 1.11. Óïðàæíåíèÿ 1) Äîêàæèòå, ÷òî åñëè ÷èñëî p  ïðîñòîå è p > 2, òî (p − 2)! ≡ 1 (mod p). 2) Äîêàæèòå, ÷òî 1 · 2 · 3 · · · · · 1007 ≡ 1 (mod 1009). 3) Ïîñòðîéòå òàáëèöó çíà÷åíèé ϕ(n) ïðè 1 > n > 50. 4) Âû÷èñëèòå çíà÷åíèå ϕ(2025). 1.12. Ñïèñîê ëèòåðàòóðû Àíäåðñîí