Миникурс по теории чисел

ÌÈÍÈÊÓÐÑ ÏÎ ÒÅÎÐÈÈ ×ÈÑÅË À. Ñêîïåíêîâ Ïåðâûå ÷åòûðå ïóíêòà ïðèâîäÿòñÿ äëÿ ïîëíîòû, ÷òîáû ìèíèêóðñ ìîæíî áûëî èçó÷àòü 'ñ íóëÿ' (èç íèõ íà çàíÿòèÿõ Øêîë èñïîëüçîâàëèñü òîëüêî íàèáîëåå ñëîæíûå çàäà÷è).  ïóíêòå 'Ìàëàÿ òåîðåìà Ôåðìà' èñïîëüçîâíû çàäà÷è îò Ä. À. Ïåðìÿêîâà, à â ïóíêòå 'Ïåðâîîáðàçíûå êîðíè'  îò À. ß. Áåëîâà. Ïóíêò 'Êâàäðàòè÷íûå âû÷åòû' ñîñòàâëåí ïî êíèãå È. Ì. Âèíîãðàäîâ, Îñíîâû òåîðèè ÷èñåë. Ïðè ýòîì ÿ ñòàðàëñÿ ïîêàçàòü, êàê áûë ïðèäóìàí êâàäðàòè÷íûé çàêîí âçàèìíîñòè (äðóãîé ñïîñîá ïðèäóìàòü åãî ñîîáùèë ìíå À. ß. Áåëîâ). Ïóíêò 'ïðîâåðêà ïðîñòîòû ÷èñåë Ìåðñåííà' íàïèñàí Ñ. Â. Êîíÿãèíûì. Åñëè óñëîâèå çàäà÷è ÿâëÿåòñÿ óòâåðæäåíèåì, òî â çàäà÷å òðåáóåòñÿ ýòî óòâåðæäåíèå äîêàçàòü. Ëàòèíñêèìè áóêâàìè îáîçíà÷àþòñÿ öåëûå ÷èñëà.

Äåëèìîñòü è äåëåíèå ñ îñòàòêîì. ×èñëî a äåëèòñÿ íà íåíóëåâîå ÷èñëî b, åñëè ñóùåñòâóåò òàêîå k , ÷òî a = kb. Îáîçíà÷åíèå: b|a.  ýòîì ñëó÷àå b íàçûâàåòñÿ äåëèòåëåì ÷èñëà a. 1. Êàêèå èç ñëåäóþùèõ óòâåðæäåíèé âåðíû äëÿ ëþáûõ n, a, b? (a) 2|(n2 − n). (b) 4|(n4 − n). (c) Åñëè c|a è c|b, òî c|(a + b). (d) Åñëè b|a, òî bc|ac äëÿ ëþáîãî c. (e) Åñëè bc|ac äëÿ íåêîòîðîãî c, òî b|a. 2. (a) Ñôîpìóëèðóéòå è äîêàæèòå ïpèçíàêè äåëèìîñòè íà 2,4,5,10,3,9,11. (b) Äåëèòñÿ ëè ÷èñëî 11 . . . 1 èç 1993 åäèíèö íà 111111? (ñ) ×èñëî 1 . . . 1 (2001 åäèíèö) äåëèòñÿ íà 37. 3. (a) Åñëè k íå êðàòíî íè 2, íè 3, íè 5, òî k 4 − 1 êðàòíî 240. (b) Åñëè a + b + c äåëèòñÿ íà 30, òî è a5 + b5 + c5 äåëèòñÿ íà 30. 4. Ïóñòü a äåëèòñÿ íà 2 è íå äåëèòñÿ íà 4. Äîêàæèòå, ÷òî ÷èñëî ÷åòíûõ äåëèòåëåé a ðàâíî ÷èñëó íå÷åòíûõ äåëèòåëåé a. 5. (à) Äëÿ ëþáûõ a è b ñóùåñòâóåò òàêîå n, ÷òî nb ≤ a < (n + 1)b. (b) Òåîðåìà î äåëåíèè ñ îñòàòêîì. Äëÿ ëþáûõ ÷èñåë a è b (b 6= 0) ñóùåñòâóþò è åäèíñòâåííû òàêèå ÷èñëà q è r, ÷òî a = bq + r è 0 ≤ r < |b|. Ýòè ÷èñëà íàçûâàþòñÿ ÷àñòíûì è îñòàòêîì îò äåëåíèÿ a íà b. 6. (a) Íàéäèòå ÷àñòíûå è îñòàòêè îò äåëåíèÿ 1996 íà −17, −17 íà 4 è n2 + n + 1 íà n + 1 (äëÿ êàæäîãî öåëîãî n). (b) Íàéäèòå âñå âîçìîæíûå ÷àñòíûå (îñòàòêè) îò äåëåíèÿ ÷èñëà 57. 1997 (ñ) Íàéäèòå ïîñëåäíþþ öèôðó ÷èñëà 19971997 .

Òåñò. I. Ñêîëüêî äåëèòåëåé ó ÷èñëà 4? a) 1; b) 2; c) 3; d) 4; e) 5; f) 6; g) 7. II. Êàêèå èç ñëåäóþùèõ óòâåðæäåíèé âåðíû äëÿ ëþáûõ ÷èñåë a, b, c, n? a) 6|n3 − n; b) 3 - n2 + 1; c) åñëè b|a, òî |b| ≤ |a|; d) åñëè a|b è b|a, òî |a| = |b|; e) åñëè c|ab, òî c|a èëè c|b.

III. Îñòàòîê îò äåëåíèÿ −24 íà −10 ðàâåí: a) 4;

b) -4;

c) 6;

d) -6.

Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 1abcde, 2a. 1. Îòâåòû: (a,c,d,e) äà, (b) íåò. (a) Èìååì n2 − n = n(n − 1). ×¼òíûå ÷èñëà èäóò ÷åðåç îäèí. Ïîýòîìó îäíî èç ÷èñåë n èëè n − 1 ÷¼òíîå. Çíà÷èò èõ ïðîèçâåäåíèå n2 − n ÷¼òíîå. (b) 4 - (24 − 2) = 14. (c) Åñëè a = kc è b = mc, òî a + b = (k + m)c. (d) Åñëè a = kb, òî ac = k(bc). (e) Åñëè ac = kbc, òî c(a − kb) = 0. Òàê êàê bc 6= 0, òî c 6= 0. Çíà÷èò a = kb.

ÍÎÄ è ÍÎÊ Íàèáîëüøåå ÷èñëî, äåëÿùåå è a, è b, íàçûâàåòñÿ íàèáîëüøèì îáùèì äåëèòåëåì (a, b) ÷èñåë a è b (ïðåäïîëàãàåòñÿ, ÷òî ÷èñëà a è b íå ðàâíû íóëþ îäíîâðåìåííî). ×èñëà a è b íàçûâàþòñÿ âçàèìíî ïðîñòûìè, åñëè (a, b) = 1. 1. Íàéäèòå âñå âîçìîæíûå çíà÷åíèÿ (à) (n, 12); (b) (n, n + 1); (c) (n, n + 6); (d) (2n + 3, 7n + 6); (e) (n2 , n + 1). 2. (a) Äëÿ ëþáûõ äâóõ ÷èñåë a è b íàèáîëüøèé îáùèé äåëèòåëü (a, b) ñóùåñòâóåò è åäèíñòâåíåí. (b) (a, b) = b òîãäà è òîëüêî òîãäà, êîãäà a äåëèòñÿ íà b. (c) (a, b) äåëèòñÿ íà ëþáîé îáùèé äåëèòåëü a è b. (d) (ca, cb) = c(a, b) ïðè c > 0. a b (e) (a,b) è (a,b) âçàèìíî ïðîñòû.

3. Áèíàðíûé àëãîðèòì. (à) Èñïîëüçóÿ ðàâåíñòâà (2m, 2n) = 2(m, n),

(2m + 1, 2n) = (2m + 1, n) è (2m + 1, 2n + 1) = (2m + 1, m − n),

ïîñòðîéòå àëãîðèòì íàõîæäåíèÿ ÍÎÄ. k l (b) Íàéäèòå (22 + 1, 22 + 1). a3 + 2a 4. (a) Äëÿ ëþáîãî a äðîáü 4 íåñîêðàòèìà. a + 4a2 + 1 a (b) Åñëè äðîáü b íåñîêðàòèìà, òî è äðîáü a+b íåñîêðàòèìà. ab Íàìåíüøåå ïîëîæèòåëüíîå ÷èñëî, äåëÿùååñÿ íà a è íà b, íàçûâàåòñÿ íàèìåíüøèì îáùèì êðàòíûì [a, b] ÷èñåë a è b (ïðåäïîëàãàåòñÿ, ÷òî ÷èñëà a è b íå ðàâíû 0). 5. Íàéäèòå (a) [192, 270]. (b) [a2 − ab + b2 , ab]. 6. (à) Äëÿ ëþáûõ äâóõ ÷èñåë a è b [a, b] ñóùåñòâóåò è åäèíñòâåííî. (b) [a, b] = a òîãäà è òîëüêî òîãäà, êîãäà a äåëèòñÿ íà b. (c) Ëþáîå îáùåå êðàòíîå a è b äåëèòñÿ íà [a, b]. (d) [ca, cb] = c[a, b] ïðè c > 0. (e) [a,b] è [a,b] âçàèìíî ïðîñòû. a b

Òåñò. I. (−24; −10) = a) 4; b) -4; c) 2; d) -2. II. [15; −10] = a) 30; b) -30; c) 5; d) -5.

III. Êàêèå èç ñëåäóþùèõ óòâåðæäåíèé âåðíû äëÿ ëþáûõ ÷èñåë a, b? a) äðîáü b) äðîáü c) äðîáü

a b a b a b

íåñîêðàòèìà òîãäà è òîëüêî òîãäà, êîãäà (a, b) = 1; íåñîêðàòèìà òîãäà è òîëüêî òîãäà, êîãäà äðîáü a−b íåñîêðàòèìà; ab a−b íåñîêðàòèìà òîãäà è òîëüêî òîãäà, êîãäà äðîáü a+b íåñîêðàòèìà.

Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 1abcde, 2abcde.

ïðîñòûå ÷èñëà ×èñëî p > 1 íàçûâàåòñÿ ïðîñòûì, åñëè îíî íå èìååò ïîëîæèòåëüíûõ äåëèòåëåé, êðîìå p è 1. 1. (a) Íàéäèòå âñå p, òàêèå ÷òî p, p + 2, p + 4 ïðîñòûå. (b) Åñëè 111...11 (n åäèíèö) ïðîñòîå, òî n ïðîñòîå. Îáðàòíîå íåâåðíî. (c)* Äëÿ ëþáîãî n ñóùåñòâóåò m, òàêîå ÷òî âñå ÷èñëà m + 1, . . . , m + n ñîñòàâíûå. √ 2. (à) Åñëè a > 1 íå äåëèòñÿ íè íà îäíî ïðîñòîå p, òàêîå ÷òî p ≤ a, òî a ïðîñòîå. (b) Ðåøåòî Ýðàòîñôåíà. Ïóñòü p1 , . . . , pk  âñå ïðîñòûå ÷èñëà îò 1 äî n. Äëÿ êàæäîãî i = 1, . . . , k âû÷åðêíåì âñå ÷èñëà, äåëÿùèåñÿ íà pi è áîëüøèå pi . Òîãäà âñå íåâû÷åpêíóòûå ÷èñëà, ìåíüøèå n2 ,  ïpîñòûå. (c) Âûïèøèòå âñå ïðîñòûå ÷èñëà îò 1 äî 200. 3. (a) Ïðîñòûõ ÷èñåë áåñêîíå÷íî ìíîãî. (b)* Ïðîñòûõ ÷èñåë âèäà 4k + 3 áåñêîíå÷íî ìíîãî. Òåîðåìà Äèðèõëå. Åñëè a, b > 0 íå èìåþò îáùèõ äåëèòåëåé, îòëè÷íûõ îò ±1, òî ïðîñòûõ ÷èñåë âèäà ak + b áåñêîíå÷íî ìíîãî. (Äëÿ äîêàçàòåëüñòâà ýòîé òåîðåìû íóæíà òåîðèÿ, íå èçëàãàåìàÿ çäåñü.) 4. Îáîçíà÷èì n-îå â ïîðÿäêå âîçðàñòàíèÿ ïðîñòîå ÷èñëî ÷åðåç pn . (a) pn+1 ≤ p1 · . . . · pn + 1. (b) pn+1 ≤ p1 · . . . · pn − 1 ïðè n ≥ 2. (c) Ìåæäó p1 + . . . + pn è p1 + . . . + pn+1 âñåãäà åñòü òî÷íûé êâàäðàò. n 5. (a) Ïóñòü p ïðîñòîå è n < p < 2n. Òîãäà C2n äåëèòñÿ íà p. pn+1 (b) 2 > p1 · . . . · pn . 6. (a) Âåðíî ëè, ÷òî äëÿ ëþáîãî n ÷èñëî n2 + n + 41 ïðîñòîå? (b) Äëÿ ëþáîãî ìíîãî÷ëåíà f ñóùåñòâóåò òàêîå n, ÷òî f (n) ñîñòàâíîå.

Òåñò. I. Âåðíî ëè, ÷òî äëÿ ëþáîãî íàòóðàëüíîãî n ÷èñëî n2 + n + 41 ïðîñòîå? a) âåðíî; b) íå âåðíî. II. Êàêèõ ÷èñåë áîëüøå ñðåäè ÷èñåë 1, 2, 3, . . . , 100? a) ïðîñòûõ; b) íåïðîñòûõ; c) ïðîñòûõ è íåïðîñòûõ ÷èñåë ïîðîâíó. III. Êàêèå èç ñëåäóþùèõ óòâåðæäåíèé âåðíû äëÿ ëþáîãî ÷èñëà n? a) pn ≥ 2n − 5; b) pn ≤ 2n + 5; n c) pn ≤ 22 . Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 1ab.

Êàíîíè÷åñêîå ðàçëîæåíèå

1. (à) Ëþáîå íàòóðàëüíîå n ðàñêëàäûâàåòñÿ â ïðîèçâåäåíèå ïðîñòûõ ÷èñåë.

(b) Êàíîíè÷åñêîå ðàçëîæåíèå. Äëÿ ëþáîãî íàòóðàëüíîãî n íàéäóòñÿ òàêèå ðàçëè÷íûå ïðîñòûå p1 , . . . , pm è íàòóðàëüíûå a1 , . . . , am , ÷òî n = pa11 · . . . · pamm . (c)* Îñíîâíàÿ òåîðåìà àðèôìåòèêè. Ðàçëîæåíèå íàòóðàëüíîãî ÷èñëà â ïðîèçâåäåíèå ïðîñòûõ åäèíñòâåííî ñ òî÷íîñòüþ äî ïîðÿäêà ñîìíîæèòåëåé. Óêàçàíèå. Ìîæíî èñïîëüçîâàòü ëåììû èç 'ëèíåéíûõ äèîôàíòîâûõ óðàâíåíèé'. 2. Ïóñòü n = pa11 · . . . · pann  êàíîíè÷åñêîå ðàçëîæåíèå. Íàéäèòå (a) êîëè÷åñòâî α(n) íàòóðàëüíûõ äåëèòåëåé ÷èñëà n; (b) P ñóììó s(n) íàòóðàëüíûõ äåëèòåëåé ÷èñëà n; (c) α(d), ãäå ñóììà âåäåòñÿ ïî âñåì íàòóðàëüíûì äåëèòåëÿì ÷èñëà n. d/n

Ðåøàéòå çàäà÷ó ñíà÷àëà äëÿ ïðîñòîãî n, ïîòîì äëÿ n = pα , ïîòîì äëÿ n = p1 p2 è çàòåì äëÿ îáùåãî ñëó÷àÿ. 3. Íàéäèòå êàíîíè÷åñêîå ðàçëîæåíèå ÷èñåë 11 (à) 1995; (b) 17!; (c) C22 . n 4. (a) n! íå äåëèòñÿ íà 2 íè ïðè êàêîì n ≥ 1. (b) Ïîêàçàòåëü, ñ êîòîðûì ïðîñòîå p âõîäèò â êàíîíè÷åñêîå ðàçëîæåíèå ÷èñëà n!, ðàâåí ∞ P [ pni ].

i=1

(c) Íàéòè ÷èñëî íóëåé â êîíöå ÷èñëà 1979!. 5. (a) Èçâåñòíî, ÷òî (a, b) = 15, [a, b] = 840. Íàéäèòå a è b. (b) (a, b) · [a, b] = ab. (c) Âûðàçèòå [a, b, c] ÷åðåç a, b, c è ÍÎÄ'û ïîäñèñòåì ýòèõ ÷èñåë. (d) Âûðàçèòå (a, b, c) ÷åðåç a, b, c, [a, b], [b, c], [c, a], [a, b, c]. (e)* Äëÿ n ÷èñåë ñóùåñòâóþò ôîðìóëû, àíàëîãè÷íûå ôîðìóëàì ïðåäûäóùèõ ïóíêòîâ. Óêàçàíèå. Èñïîëüçóÿ ôîðìóëó âêëþ÷åíèé-èñêëþ÷åíèé è êàíîíè÷åñêîå ðàçëîæåíèå. 6. Íàòóðàëüíîå ÷èñëî íàçûâàåòñÿ ñîâåðøåííûì, åñëè îíî ðàâíî ñóììå âñåõ ñâîèõ íàòóðàëüíûõ äåëèòåëåé, ìåíüøèõ åãî. ×èñëî n ÷åòíîå ñîâåðøåííîå òîãäà è òîëüêî òîãäà, êîãäà n = 2p−1 (2p − 1), ãäå p è 2p − 1 ïðîñòûå. 7. (à) Åñëè (a, b) = 1 è ab = m2 , òî ñóùåñòâóþò òàêèå ÷èñëà k è l, ÷òî a = k 2 , b = l2 . (b) Íàéäèòå íåêîòîðûå òàêèå ÷èñëà n > m > 100, ÷òî 1 + 2 + . . . + n = m2 . (c) Íàéäèòå âñå òàêèå ÷èñëà m > n > 1, ÷òî 12 + 22 + . . . + n2 = m2 . (d) Åñëè n > 2, ab = cn è (a, b) = 1, òî a = xn è b = y n äëÿ íåêîòîðûõ x è y . (e) m(m + 1) íå ÿâëÿþòñÿ ñòåïåíüþ ïðîñòîãî ÷èñëà íè ïðè êàêîì öåëîì m > 1. 8. (a) Åñëè ab, òî ñóùåñòâóþò òàêèå ÷èñëà k , l, m, n, ÷òî a = kl, b = mn, c = km, d = ln. (b) Íàéäèòå âñå òàêèå ÷èñëà a, b, c, d, k, m, ÷òî ab, a + d = 2k , b + c = 2m . 9. Íàéäèòå íàèìåíüøåå òàêîå n, ÷òî èç ëþáûõ n ÷èñåë, íå ïðåâîñõîäÿùèõ 200, ìîæíî âûáðàòü äâà, îäíî èç êîòîðûõ äåëèòñÿ íà äðóãîå.

Òåñò. I. Íàéäèòå êàíîíè÷åñêîå ðàçëîæåíèå ÷èñëà 400: a) 4 · 102 ; b) 24 · 52 ; c) (2 · 2 · 5)2 . II. Íàçîâåì ïîëîæèòåëüíîå ÷åòíîå ÷èñëî ÷åòíîïðîñòûì, åñëè åãî íåëüçÿ ïðåäñòàâèòü â âèäå ïðîèçâåäåíèÿ äâóõ ìåíüøèõ ÷åòíûõ ÷èñåë. Êàêèå èç ñëåäóþùèõ óòâåðæäåíèé âåðíû? a) ëþáîå ïîëîæèòåëüíîå ÷åòíîå ÷èñëî ðàñêëàäûâàåòñÿ â ïðîèçâåäåíèå ÷åòíîïðîñòûõ ÷èñåë; b) ðàçëîæåíèå ïîëîæèòåëüíîãî ÷åòíîãî ÷èñëà â ïðîèçâåäåíèå ÷åòíîïðîñòûõ ÷èñåë åäèíñòâåííî ñ òî÷íîñòüþ äî ïîðÿäêà ñîìíîæèòåëåé. III. Óêàæèòå, êàêèå èç ñëåäóþùèõ ÷èñåë  ñîâåðøåííûå: a) 1; b) 6; c) 15; d) 28.

Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 1abc, 3abc. Îòâåò ê 5c. [a, b, c] =

a · b · c · (a, b, c) . (a, b) · (b, c) · (c, a)

ëèíåéíûå äèîôàíòîâû óðàâíåíèÿ

1. (a) Êóçíå÷èê ïåðåäâèãàåòñÿ âäîëü ïðÿìîé ïðûæêàìè ïî 6 ñì è 10 ñì (â îáå ñòîðîíû). Â

êàêèå òî÷êè îí ñìîæåò ïîïàñòü? (b) Íà îñòðîâå Óòîïèÿ â êàæäîé íåäåëå 7 äíåé, à â êàæäîì ìåñÿöå 31 äåíü. Òîìàñ Ìîð ïðîæèë òàì 365 äíåé. Äîêàçàòü, ÷òî ñðåäè íèõ áûë ïîíåäåëüíèê 13 ÷èñëà. (c) Ïàøà ïðèáàâèë ê äíþ ñâîåãî ðîæäåíèÿ, óìíîæåííîìó íà 12, ìåñÿö ñâîåãî ðîæäåíèÿ, óìíîæåííûé íà 31. Ïîëó÷èëîñü 473. Êîãäà ó Ïàøè äåíü ðîæäåíèÿ (íàéäèòå âñå âîçìîæíûå ðåøåíèÿ)? (d) Ðåøèòå óðàâíåíèå â öåëûõ ÷èñëàõ: nx + (2n − 1)y = 3 (n  ïàðàìåòð). 2. (a) Ëþáóþ ñóììó, áîëüøóþ 23 ïèàñòðîâ, ìîæíî ðàçìåíÿòü ìîíåòàìè ïî 5 è 7 ïèàñòðîâ. (b)* Íàéäèòå íàèìåíüøåå m, òàêîå ÷òî ëþáóþ ñóììó, áîëüøóþ m, ìîæíî ðàçìåíÿòü ìîíåòàìè ïî 12, 21 è 28 ïèàñòðîâ. 3. (a) Äëÿ ëþáîãî n ÷èñëî n5 − n äåëèòñÿ íà 30. (b) Åñëè ÷èñëî a äåëèòñÿ íà 2, íà 3 è íà 5, òî a äåëèòñÿ íà 30 (äîêàæèòå ïî îïðåäåëåíèþ äåëèìîñòè, íå èñïîëüçóÿ îñíîâíîé òåîðåìû àðèôìåòèêè, èáî îáû÷íî ïðè äîêàçàòåëüñòâå îñíîâíîé òåîðåìû àðèôìåòèêè èñïîëüçóåòñÿ ðåçóëüòàò, áëèçêèé ê òîìó, êîòîðûé íóæíî äîêàçàòü). 4. (a) Äëÿ ëþáîãî íåîòðèöàòåëüíîãî n ÷èñëî 202n + 162n − 32n − 1 äåëèòñÿ íà 323. (b) Åñëè ÷èñëî a äåëèòñÿ íà 17 è íà 19, òî a äåëèòñÿ íà 323 (ñì. çàìå÷àíèå ê 3b). 5. (a) Óðàâíåíèå 19x + 17y = 1 èìååò ðåøåíèå (çäåñü è äàëåå  â öåëûõ ÷èñëàõ). (b) Äëÿ ëþáûõ ÷èñåë a, b è c óðàâíåíèå ax + by = c èìååò ðåøåíèå òîãäà è òîëüêî òîãäà, êîãäà c äåëèòñÿ íà (a, b). (c) Ïóñòü ïàðà x0 , y0  ðåøåíèå óðàâíåíèÿ ax + by = c. Òîãäà ìíîæåñòâî ðåøåíèé ýòîãî b a óðàâíåíèÿ åñòü {x = x0 + t, y = y0 − t) | t ∈ Z}. (a, b) (a, b) 6. (a) Ëåììà î ïðåäñòàâëåíèè ÍÎÄ. Äëÿ ëþáûõ ÷èñåë a è b ñóùåñòâóþò òàêèå ÷èñëà x è y , ÷òî ax + by = (a, b). (b) åñëè (c, b) = 1 è b|ac, òî b|a; (c) åñëè p ïðîñòîå è p|ab, òî p|a èëè p|b; (d) åñëè (b, c) = 1, b|a è c|a, òî bc|a. 7. Àëãîðèòìîì Åâêëèäà íàçûâàåòñÿ ïðîöåññ ïîñòðîåíèÿ èç äàííîé ïàðû a0 , b0 ïîñëåäîâàòåëüíîñòè ïàð ak , bk ïî ñëåäóþùåìó ïðàâèëó: ak+1 = bk è bk+1 ðàâíî îñòàòêó îò äåëåíèÿ ak íà bk , åñëè bk 6= 0; åñëè bk = 0, òî ñëåäóþùèå ïàðû íå ñòðîÿò, à ãîâîðÿò, ÷òî àëãîðèòì çàâåðøèë ðàáîòó çà k øàãîâ. (a) (a, b) = (a − b, b). (b) (a, b) = (b, r), ãäå r - îñòàòîê îò äåëåíèÿ a íà b. (c) Äîêàæèòå, ÷òî äëÿ ëþáûõ ÷èñåë a è b 6= 0 ñóùåñòâóåò n òàêîå, ÷òî àëãîðèòì Åâêëèäà çàâåðøàåò ðàáîòó çà n øàãîâ (ò. å. bn = 0). Äëÿ ýòîãî n âûïîëíåíî an = (a, b). (d) Óêàæèòå ñïîñîá íàõîæäåíèÿ õîòÿ áû îäíîãî ðåøåíèÿ x0 , y0 óðàâíåíèÿ ax+by = c (ëþáîé: ìåòîä Ýéëåðà, ïî àëãîðèòìó Åâêëèäà èëè ÷åðåç ðàçëîæåíèå â öåïíóþ äðîáü). (e)* Ñîñòàâüòå áëîê-ñõåìó àëãîðèòìà ðåøåíèÿ óðàâíåíèÿ ax + by = c. 8. (a) Íàéäèòå (291 − 1, 263 − 1). (b) Íàéäèòå (232 + 1, 216 + 1).

(c) Äëÿ êàêèõ ÷èñåë a, b, n ÷èñëî na + 1 äåëèòñÿ íà nb − 1? 9. Èç óãëà áèëüÿðäíîãî ïîëÿ ïîä óãëîì 45◦ âûïóñêàþò øàðèê. Ñîáüåò ëè îí êåãëþ, ñòîÿùóþ â (2; 1), åñëè ðàçìåðû äîñêè (à) 12 × 18; (b) 17 × 18? 10. Îïðåäåëåíèå ñðàâíèìîñòè íàïîìíåíî â íà÷àëå ñëåäóþùåãî ïóíêòà. (a) Ðåøèòå ñèñòåìû ñðàâíåíèé  ½ ½  x ≡ 7 (8) x ≡ −1 (7) x ≡ 6 (12) x ≡ 18 (25) x ≡ 15 (5) x ≡ 8 (20)  6x ≡ 2 (7) (b) Êèòàéñêàÿ òåîðåìà îá îñòàòêàõ. Åñëè ÷èñëà m1 , . . . , ms ïîïàðíî âçàèìíî ïðîñòû, òî äëÿ ëþáûõ a1 , . . . , as ñóùåñòâóåò òàêîå x, ÷òî x ≡ ai (mi ) äëÿ ëþáîãî i = 1, . . . , s. (c) Ïðèäóìàéòå àëãîðèòì íàõîæäåíèÿ òàêîãî x. (d) Íàéäóòñÿ 1000 èäóùèõ ïîäðÿä ÷èñåë, íè îäíî èç êîòîðûõ íå ÿâëÿåòñÿ ñòåïåíüþ ïðîñòîãî. 11. ËÈÍÅÉÍÛÅ ÄÈÎÔÀÍÒÎÂÛ ÓÐÀÂÍÅÍÈß ñ íåñêîëüêèìè ïåðåìåííûìè. (a) Íà êàêèå êëåòêè ìîæåò ïîïàñòü øàõìàòíàÿ ôèãóðà òÿíèòîëêàé, êîòîðàÿ ìîæåò ñîâåðøàòü ñëåäóþùèå ïåðåäâèæåíèÿ ïî áåñêîíå÷íîé êëåò÷àòîé äîñêå: íà 2 êëåòêè ââåðõ è íà 5 âïðàâî; íà 2 êëåòêè âíèç è íà 5 âëåâî; íà 3 êëåòêè ââåðõ è íà 8 âïðàâî; íà 3 êëåòêè âíèç è íà 8 âëåâî? (b) Êàê èçìåíèòñÿ îòâåò äëÿ êîíå÷íîé äîñêè n × n êëåòîê? (c)* Ïðèäóìàéòå àëãîðèòì ðåøåíèÿ â öåëûõ ÷èñëàõ óðàâíåíèÿ a1 x1 + . . . + an xn = c.

Òåñò.

I?. II. Êóçíå÷èê ïåðåäâèãàåòñÿ âäîëü ïðÿìîé ïðûæêàìè ïî 6 ñì è 10 ñì (â îáå ñòîðîíû). Ñìîæåò

ëè îí ïîïàñòü â òî÷êó, íàõîäÿùóþñÿ îò íà÷àëüíîé íà ðàññòîÿíèè a) 3.5 ñì; b) 7 ñì; c) 14 ñì? III. Ñêîëüêî ðåøåíèé â öåëûõ ÷èñëàõ èìååò óðàâíåíèå ax+by = (a, b) äëÿ äàííûõ íåíóëåâûõ a è b? a) íè îäíîãî; b) åäèíñòâåííîå; c) áåñêîíå÷íî ìíîãî; d) çàâèñèò îò êîíêðåòíûõ ÷èñåë a è b. Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 1b, 2a, 3ab, 4ab, 5a. Óêàçàíèå ê 3b. 3a − 2a = a, ïîýòîìó a äåëèòñÿ íà 6. 6a − 5a = a, ïîýòîìó a äåëèòñÿ íà 30. Óêàçàíèå ê 4b. 19a − 17a = 2a, ïîýòîìó 2a äåëèòñÿ íà 323. 17a − 8 · 2a = a, ïîýòîìó a äåëèòñÿ íà 323. Óêàçàíèå ê 5b. Ìîæíî ñ÷èòàòü, ÷òî a > b > 0 è òîãäà äîêàçûâàòü èíäóêöèåé ïî a + b. Óêàçàíèå ê 8a. Äîêàæèòå, ÷òî (na − 1, nb − 1) = n(a,b) − 1.

Öåëûå òî÷êè ïîä ïðÿìîé Ýòè çàäà÷è ïîäâîäÿò øêîëüíèêà ê àëãîðèòìó âû÷èñëåíèÿ ñóììû fα (n) =

n P

[αk], ò.å. êî-

k=1

ëè÷åñòâà öåëûõ òî÷åê 'ïîä ïðÿìîé y = αx'. ×åðåç [x] è {x} îáîçíà÷àþòñÿ öåëàÿ è äðîáíàÿ ÷àñòè ÷èñëà x, ñîîòâåòñòâåííî. Ëàòèíñêèå áóêâû îáîçíà÷àþò öåëûå ÷èñëà. Àëãîðèòì ñòðîèòñÿ â çàäà÷àõ 2abc, çàäà÷à 1 ïîëåçíà 'äëÿ ðàçîãðåâà'.

1. Íàéäèòå fα (n) äëÿ

(a) öåëîãî α; (b) öåëîãî 2α; (c) öåëîãî 3α; (d) α = a/n äëÿ äàííûõ öåëûõ a è n; (e) Íàéäèòå lim fαn(n) 2 . n→∞

2. (a) fα (n) = f{α} (n) + 12 [α]n(n + 1).

(b) fα (n) + f1/α ([nα]) − [n/q] = n[nα], ãäå q  çíàìåíàòåëü íåñîêðàòèìîé äðîáè, ïðåäñòàâëÿþùåé ÷èñëî α, åñëè α ðàöèîíàëüíî, è q = ∞ (ò.å. [n/q] = 0), åñëè α èððàöèîíàëüíî. (c) Íàéäèòå àëãîðèòì âû÷èñëåíèÿ ñóììû fα (n). n P {αk}. (d) Íàéäèòå àëãîðèòì âû÷èñëåíèÿ ñóììû k=1

Òåñò. I. Íàéäèòå [−2.5]. a) -1; b) -2; c) -3. II. Íàéäèòå f√2 (4). a) 10; b) 12; b) 14. III. Ñóùåñòâóþò ëè òàêèå α è β , ÷òîáû ïðè ëþáîì n âûïîëíÿëîñü ðàâåíñòâî fα (n) = fβ (n)? a) ñóùåñòâóþò; b) íå ñóùåñòâóþò. Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 1ab. Óêàçàíèå ê 2b. 1 ≤ x ≤ n, 1 ≤ y ≤ [nα]. Óêàçàíèå ê 2c.

Ïîñ÷èòàéòå

êîëè÷åñòâî

öåëûõ

òî÷åê

â

ïðÿìîóãîëüíèêå

n 2n 2n ] + [ ] − f3/2 ([ ]); 3 3 3 2n 1 2n 2n 2n f3/2 ([ ]) [ ]([ ] + 1) + f1/2 ([ ]); 3 2 3 3 3 2n 2n n n n f1/2 ([ ]) = [ ][ ] + [ ] − f2 ([ ]), 3 3 3 3 3 f2/3 (n) = n[

ïîñêîëüêó [[x]/n] = [x/n] äëÿ öåëîãî n > 0 è, çíà÷èò, [

[ 2n ] 3 2 ]

= [ n3 ];

n n n f2 ([ ]) = [ ]([ ] + 1). 3 3 3

Çàìå÷àíèÿ. ×àñòíûé ñëó÷àé ðàâåíñòâà 2b (íà êîòîðîì îñíîâàí ïðåäëàãàåìûé àëãîðèòì) äëÿ ïîëîæèòåëüíûõ íå÷åòíûõ âçàèìíî ïðîñòûõ ÷èñåë p < q , α = p/q è n = (q − 1)/2 (òîãäà [nα] = (p − 1)/2) ïîÿâëÿåòñÿ ïðè äîêàçàòåëüñòâå êâàäðàòè÷íîãî çàêîíà âçàèìíîñòè [È. Ì. Âèíîãðàäîâ, Îñíîâû òåîðèè ÷èñåë, âîïðîñ 1á ê ãëàâå II è V.2.l]; äîêàçàòåëüñòâî îáùåãî ñëó÷àÿ àíàëîãè÷íî. Ñóììà èç 2d âû÷èñëåíà (áîëåå ãðîìîçäêèì ñïîñîáîì, ÷åì ïðåäëîæåííûé çäåñü) â [Â. Í. Äîáðîâîëüñêàÿ, Íåïîëíûå ñóììû äðîáíûõ äîëåé, ×åáûøåâñêèé ñáîðíèê, 5:2(10), 2004, 4248].

Ìàëàÿ òåîðåìà Ôåðìà. Ïóñòü m íàòóðàëüíîå ÷èñëî. ×èñëà a è b íàçûâàþòñÿ ñðàâíèìûìè ïî ìîäóëþ m 6= 0, åñëè a − b äåëèòñÿ íà m (èëè a è b èìåþò îäèíàêîâûå îñòàòêè îò äåëåíèÿ íà m). Îáîçíà÷åíèå: a ≡ b mod m èëè a ≡ b (m). Ñðàâíèìîñòü a ≡ b mod m ðàâíîñèëüíî òîìó, ÷òî a è b èìåþò îäèíàêîâûé îñòàòîê ïðè äåëåíèè íà m.

Ñâîéñòâà: ïî÷ëåííîå ñëîæåíèå, âû÷èòàíèå, óìíîæåíèå, âîçâåäåíèå â ñòåïåíü, äåëåíèå íà ÷èñëî, âçàèìíî ïðîñòîå ñ ìîäóëåì, ýêâèâàëåíòíîñòü, òðàíçèòèâíîñòü (öåïî÷êè ñðàâíåíèé). Ïðèìåð:

316 = (32 )8 = 98 = (92 )4 = 814 ≡ 124 = (122 )2 = 42 ≡ 62 6 ≡ 13 mod 23. Íàïðèìåð, óìíîæåíèå íà 13 ïî ìîäóëþ 17 óñòðîåíî òàê: 1 → 13 → 16 → 4 → 1 2 → 9 → 15 → 8 → 2 3 → 5 → 14 → 12 → 3 6 → 10 → 11 → 7 → 6 0 → 0. 1. Ïîñëåäîâàòåëüíîñòü îñòàòêîâ îò äåëåíèÿ an (n = 0, 1, . . .) íà b 6= 0 ïåðèîäè÷íà, íà÷èíàÿ ñ íåêîòîðîãî ìåñòà. 2. (a) Îáîçíà÷èì Z97 = {0, 1, . . . , 97}. Ðàññìîòðèì îòîáðàæåíèå f : Z97 → Z97 , çàäàííîå òàê: f (a) ðàâíî îñòàòêó îò äåëåíèÿ ÷èñëà 14a íà 97. Òîãäà f  âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå. Óêàçàíèå. Äîñòàòî÷íî äîêàçàòü, ÷òî f ñþðúåêòèâíî. 14 · 7 ≡ 1 mod 97. Çàìå÷àíèå. Èíîãäà êàê ðàç äîêàçûâàþò, ÷òî f èíúåêòèâíî, íî íåîáõîäèìàÿ äëÿ ýòîãî îñíîâíàÿ ëåììà àðèôìåòèêè îáû÷íî äîêàçûâàåòñÿ ÷åðåç ðàçðåøèìîñòü óðàâíåíèÿ 97x + 14y = 1, èç êîòîðîé ñðàçó âûòåêàåò ñþðúåêòèâíîñòü îòîáðàæåíèÿ f . (b) (14 · 1) · (14 · 2) · . . . · (14 · 96) ≡ 96! mod 97. (c) 1416 ≡ 1 mod 97. (d) Ìàëàÿ òåîðåìà Ôåðìà. Åñëè p ïðîñòîå, òî np − n äåëèòñÿ íà p äëÿ ëþáîãî öåëîãî n. (e) Ìàëàÿ òåîðåìà Ôåðìà (alio modo). Åñëè p ïðîñòîå è n íå äåëèòñÿ íà p, òî np−1 ≡ 1 mod p. (f) Äîêàæèòå, ÷òî äëÿ ïðîñòîãî p ÷èñëî Cpk äåëèòñÿ íà p äëÿ k = 1, 2, . . . , p − 1, è ïîëó÷èòå èç ýòîãî èíîå äîêàçàòåëüñòâî ìàëîé òåîðåìû Ôåðìà. 3. Íàéäèòå îñòàòîê îò äåëåíèÿ (a) 2100 íà 101. (b) 3102 íà 101. (c) 8900 íà 29. (d) 32000 íà 43. (e) 760 íà 143. (f) 260 + 650 íà 143. Ïðèäóìàéòå òàêîé ñïîñîá, ïðè êîòîðîì íåîáõîäèìûå âû÷èñëåíèÿ ìîæíî ïðîâåñòè óñòíî! 4. (a) Åñëè p ïðîñòîå è p > 2, òî 7p − 5p − 2 äåëèòñÿ íà 6p. (b) ×èñëî 11 . . . 1} äåëèòñÿ íà 2003. | {z 2002

(c) Åñëè p è q ðàçëè÷íûå ïðîñòûå ÷èñëà, òî pq + q p ≡ p + q mod pq . (d) ×èñëî 30239 + 23930 ñîñòàâíîå. Äàëåå áóêâàìè p, q, p1 , . . . , pk îáîçíà÷àþòñÿ ðàçëè÷íûå ïðîñòûå ÷èñëà. 5. (a) p − 1 äåëèòñÿ íà íàèìåíüøåå k > 0, äëÿ êîòîðîãî ak ≡ 1 mod p. (b) Äëèíà ïåðèîäà äåñÿòè÷íîé äðîáè 1/p äåëèò p − 1. (c) Åñëè p > 2 è 2p − 1 äåëèòñÿ íà d, òî d − 1 äåëèòñÿ íà 2p. Èíûìè ñëîâàìè, ëþáîé ïðîñòîé äåëèòåëü ÷èñëà 2p − 1 èìååò âèä 2kp + 1. 5 (d)* Èñïîëüçóÿ ðàâåíñòâî 641 = 54 + 24 = 1 + 5 · 27 , äîêàæèòå, ÷òî ÷èñëî 22 + 1 ñîñòàâíîå. (e)* Âåðíî ëè ÷òî åñëè np − n äåëèòñÿ íà p äëÿ ëþáîãî öåëîãî n, òî p ïðîñòîå? (Ò.å. âåðíà ëè òåîðåìà, îáðàòíàÿ ê ìàëîé òåîðåìå Ôåðìà â íåêîòîðîé ôîðìóëèðîâêå ïîñëåäíåé?) 6. (a) Åñëè p 6= q è n íå äåëèòñÿ íè íà p, íè íà q , òî n(p−1)(q−1) − 1 äåëèòñÿ íà pq . α (b) Åñëè n íå äåëèòñÿ íà p, òî np (p−1) − 1 äåëèòñÿ íà pα+1 . (c) Òåîðåìà Ýéëåðà. Åñëè n âçàèìíî ïðîñòî ñ m = pα1 1 · . . . · pαk k è ϕ(m) = (p1 − 1)p1α1 −1 · . . . · (pk − 1)pαk k −1 , òî nϕ(m) − 1 äåëèòñÿ íà m. (d) ϕ(m) ðàâíî êîëè÷åñòâó ÷èñåë îò 1 äî m, âçàèìíî ïðîñòûõ ñ m. (å) Èçâåñòíî, ÷òî n  íå÷åòíîå ÷èñëî îò 3 äî 47, íå äåëÿùååñÿ íà 5. Êàê áûñòðî âû÷èñëÿòü íåèçâåñòíîå n ïî èçâåñòíîìó n7 mod50? (Ýòà çàäà÷à ïîêàçûâàåò, ïî÷åìó äëÿ øèôðîâàíèÿ òàê âàæíî çíàòü ðàçëîæåíèå ÷èñëà íà ïðîñòûå ìíîæèòåëè.)

Òåñò. I. Íàéäèòå îñòàòîê îò äåëåíèÿ 229 íà 29. a) 1; b) 2; c) 3; d) 4. II. Íàéäèòå îñòàòîê îò äåëåíèÿ 230 íà 30. a) 1; b) 2; c) 3; d) 4. III. Êàêèå èç ñëåäóþùèõ óòâåðæäåíèé âåðíû äëÿ ëþáûõ a, b, m? a) a ≡ a (m); b) a ≡ b (m) ⇐⇒ b ≡ a (m); c) åñëè a ≡ b (m) è b ≡ c (m), òî a ≡ c (m); d) åñëè a ≡ b (m) è c ≡ d (m), òî a + c ≡ b + d (m); e) åñëè a ≡ b (m) è c ≡ d (m), òî ac ≡ bd (m); f) åñëè a ≡ b (m), òî äëÿ ëþáîãî c 6= 0 ac ≡ bc (mc); g) a ≡ −a (m); h) ëþáîå ÷èñëî ñðàâíèìî ñ ñóììîé ñâîèõ öèôð ïî ìîäóëþ 9 è ïî ìîäóëþ 3; Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 2abc. 2. (a) 14 · 7k ≡ k mod 97. (b) (14 · 1) · (14 · 2) · . . . · (14 · 96) ≡ f (1) · f (2) · . . . · f (96) = 96! mod 97. (c) Ñîêðàòèòå ðàâåíñòâî èç (b) íà 96!. Îòâåòû ê 3. (a) 1. (b) 9. (c) 7. (d) 15. (e) 1. (f) 24.

Êâàäðàòè÷íûå âû÷åòû. Öåëü ýòîãî öèêëà çàäà÷  ìîòèâèðîâàòü ïðîáëåìó ðàçðåøèìîñòè ñðàâíåíèÿ x2 ≡ a (p) è íàìåòèòü åå ðåøåíèå äëÿ ïðîñòîãî p. 1. (a) Âûÿñíèòå, êàêèå îñòàòêè ìîãóò äàâàòü êâàäðàòû (öåëûõ) ÷èñåë ïðè äåëåíèè íà 3,4,5,6,7,8,9,10. (b) Åñëè a2 + b2 äåëèòñÿ íà 3 (íà 7), òî a è b äåëÿòñÿ íà 3 (íà 7). (c) ×èñëî âèäà 4k + 3 íå ïðåäñòàâèìî â âèäå ñóììû äâóõ êâàäðàòîâ. (d) ×èñëî, èìåþùåå ïðîñòîé äåëèòåëü âèäà 4k +3 â íå÷åòíîé ñòåïåíè, íå ïðåäñòàâèìî â âèäå ñóììû äâóõ êâàäðàòîâ. (e)** Îñòàëüíûå öåëûå ÷èñëà ïðåäñòàâèìû â âèäå ñóììû äâóõ êâàäðàòîâ. (f) Ñóùåñòâóþò ñêîëü óãîäíî áîëüøèå òðîéêè ïîñëåäîâàòåëüíûõ ÷èñåë, íè îäíî èç êîòîðûõ íå ÿâëÿåòñÿ òî÷íûì êâàäðàòîì. (g) Ñóùåñòâóåò áåñêîíå÷íî ìíîãî ÷èñåë, íå ïðåäñòàâèìûõ â âèäå ñóììû òðåõ êâàäðàòîâ. ×åðåç p îáîçíà÷àåòñÿ íå÷åòíîå ïðîñòîå ÷èñëî. Ëàòèíñêèå áóêâû îáîçíà÷àþò öåëûå ÷èñëà èëè âû÷åòû ïî ìîäóëþ p (÷òî èìåííî  âèäíî èç êîíòåêñòà). 2. Ðåøèòå óðàâíåíèÿ â öåëûõ ÷èñëàõ. (a)  íå÷åòíûõ ÷èñëàõ: x21 + x22 + x23 + x24 + x25 = y 2 . (b) x2 + y 2 = 3z 2 . (c) 2x + 1 = 3y 2 . (d) x2 = 2003y − 1. (e) x2 + 1 = py , ãäå p ≡ 3 mod 4. Óêàçàíèå ê (d), (e): èñïîëüçóéòå ìàëóþ òåîðåìó Ôåðìà. 3. Ñâåäèòå óðàâíåíèå py = at2 + bt + c ê ñðàâíåíèþ x2 ≡ a (p). Îñòàòîê a 6= 0 íàçûâàåòñÿ êâàäðàòè÷íûì âû÷åòîì (êâàäðàòè÷íûì íåâû÷åòîì) ïî ìîäóëþ p, åñëè ñðàâíåíèå x2 ≡ a(p) ðàçðåøèìî (íåðàçðåøèìî). Ñëîâà 'ïî ìîäóëþ p' äàëåå îïóñêàþòñÿ. 4. (a) Äëÿ íåêîòîðûõ a è p îáà ÷èñëà a è −a ÿâëÿþòñÿ êâàäðàòè÷íûìè âû÷åòàìè.

(b) Ñðàâíåíèå x2 ≡ a2 (p) èìååò ðîâíî äâà ðåøåíèÿ äëÿ a, íå äåëÿùåãîñÿ íà p. (c) ×èñëî êâàäðàòè÷íûõ âû÷åòîâ ðàâíî ÷èñëó êâàäðàòè÷íûõ íåâû÷åòîâ è ðàâíî p−1 . 2 5. (a) Äëÿ ëþáîãî a 6= 0 ñóùåñòâóåò è åäèíñòâåííî b, òàêîå ÷òî ab ≡ 1(p). Îáîçíà÷åíèå: b = a−1 . (b) Ðåøèòå ñðàâíåíèå x ≡ x−1 (p). (c) Òåîðåìà Âèëüñîíà. (p − 1)! + 1 äåëèòñÿ íà p. 6. (a) Åñëè a 6= 0 êâàäðàòè÷íûé âû÷åò, òî a−1 òîæå êâàäðàòè÷íûé âû÷åò. (b) ×èñëî êâàäðàòè÷íûõ âû÷åòîâ ÷åòíî òîãäà è òîëüêî òîãäà, êîãäà −1 ÿâëÿåòñÿ êâàäðàòè÷íûì âû÷åòîì. (c) Óðàâíåíèå x2 + 1 = py ðàçðåøèìî â öåëûõ ÷èñëàõ ïðè p ≡ 1(4). (è íåðàçðåøèìî ïðè p ≡ 3(4)). 7. (a) Ïðîèçâåäåíèå äâóõ êâàäðàòè÷íûõ âû÷åòîâ ÿâëÿåòñÿ êâàäðàòè÷íûì âû÷åòîì. (b) Ïðîèçâåäåíèå êâàäðàòè÷íîãî âû÷åòà è êâàäðàòè÷íîãî íåâû÷åòà ÿâëÿåòñÿ êâàäðàòè÷íûì íåâû÷åòîì. (c) Ïðîèçâåäåíèå äâóõ êâàäðàòè÷íûõ íåâû÷åòîâ ÿâëÿåòñÿ êâàäðàòè÷íûì âû÷åòîì. 8. Åñëè ÷èñëî p = 8k + 5 ïðîñòîå, òî (a) 24k+2 ≡ −1 (p). (b) óðàâíåíèå x2 − 2 = py íåðàçðåøèìî â öåëûõ ÷èñëàõ. 9. Åñëè ÷èñëî p = 8k + 1 ïðîñòîå, òî (a) 24k ≡ 1 (p). (b) óðàâíåíèå x2 − 2 = py ðàçðåøèìî â öåëûõ ÷èñëàõ. Óêàçàíèå: Ìíîãî÷ëåí ñòåïåíè n íàä Zp èìååò íå áîëåå n êîðíåé. 10. (a) Åñëè ÷èñëî p = 8k ± 1 ïðîñòîå, òî 2(p−1)/2 ≡ 1 mod p. (b) Åñëè ÷èñëî p = 8k ± 3 ïðîñòîå, òî 2(p−1)/2 ≡ −1 mod p. (c) Äëÿ êàêèõ ïðîñòûõ p ðàçðåøèìî â öåëûõ ÷èñëàõ óðàâíåíèå x2 − 2 = py ? 11. (à) Åñëè ÷èñëî p = 12k ± 1 ïðîñòîå, òî 3(p−1)/2 ≡ 1 mod p. (b) Åñëè ÷èñëî p = 12k ± 5 ïðîñòîå, òî 3(p−1)/2 ≡ −1 mod p. (c) Äëÿ êàêèõ ïðîñòûõ p ðàçðåøèìî â öåëûõ ÷èñëàõ óðàâíåíèå x2 − 3 = py ? 12. Îáîçíà÷èì ½ a +1, a êâàäðàòè÷íûé âû÷åò ïî ìîäóëþ p ( ) := −1, a êâàäðàòè÷íûé íåâû÷åò ïî ìîäóëþ p p

2 2 Íàïðèìåð, ( ) = (−1)(p −1)/8 ïî çàäà÷å 10. p p−1 a (a) Êðèòåðèé Ýéëåðà. a 2 ≡ ( ) mod p. p (p−1)/2 P

a (b) ( ) = (−1) p

x=1

[ 2ax ] p

.

(p−1)/2 P

[ ax ] a p (c) ( ) = (−1) x=1 . p p−1 q−1 p q (d)* Êâàäðàòè÷íûé çàêîí âçàèìíîñòè Ãàóññà. ( ) = (−1) 2 · 2 ( ) äëÿ ïðîñòûõ íå÷åòíûõ p q ÷èñåë p è q . a (e) Êàê áûñòðî âû÷èñëÿòü ( )? p

Òåñò. I. Ìîæåò ëè −1 áûòü êâàäðàòè÷íûì âû÷åòîì ïî êàêîìó-íèáóäü ïðîñòîìó ìîäóëþ p?

a) ìîæåò; b) íå ìîæåò. II. Êàêèå èç ñëåäóþùèõ ñðàâíåíèé ðàçðåøèìû: a) x2 ≡ 10 (11); b) x2 ≡ 2 (41); c) x2 ≡ 6 (17). III. Êàêèå èç ñëåäóþùèõ óòâåðæäåíèé âåðíû äëÿ ëþáûõ öåëûõ a è m, òàêèõ ÷òî 0 < a < m? a) ñðàâíåíèå x2 ≡ a (m) èìååò íå áîëåå 2 ðåøåíèé; b) ñðàâíåíèå ax ≡ 1 (m) èìååò íå áîëåå 1 ðåøåíèÿ; c) ñðàâíåíèå ax ≡ 1 (m) èìååò íå ìåíåå 1 ðåøåíèÿ. Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 8a. Óêàçàíèå ê çàäà÷å 8a. Îñòàòêè îò äåëåíèÿ íà p ÷èñåë 2 · 1, 2 · 2, . . . , 2 · (4k + 2) ñîâïàäàþò ñ îñòàòêàìè îò äåëåíèÿ íà p ÷èñåë a1 , a2 , . . . , a2k+1 , −a2k+2 , −a2k+3 . . . , −a4k+2 , ãäå {a1 , a2 , . . . , a2k+1 , a2k+2 , a2k+3 . . . , a4k+2 }{1, 2, . . . , 4k + 2}. Ïîýòîìó 24k · (4k)! ≡ −(4k)! (p).

Çàäà÷è 9a, 10ab, 11ab è 12b ðåøàþòñÿ àíàëîãè÷íî çàäà÷å 8a. √ p p p Óêàçàíèå ê çàäà÷àì 8a, 9a, √ 10ab (Ñ. Â. Êîíÿãèí). Ïóñòü z = (1+i) 2/2. Òîãäà (z +1/z) −(z +1/z ) ïðåäñòàâèìî â âèäå p(A + B 2), ãäå A, B  öåëûå ÷èñëà. √ Óêàçàíèå ê çàäà÷àì 11ab√(Ñ. Â. Êîíÿãèí). Ïóñòü z = (1 + i 3)/2. Òîãäà (z + 1/z)p − (z p + 1/z p ) ïðåäñòàâèìî â âèäå p(A + B 3), ãäå A, B  öåëûå ÷èñëà. a+p

2 a 2a Óêàçàíèå ê 12c. ( )( )( ) = ( 2 ). p p p p

Ïðîâåðêà ïðîñòîòû ÷èñåë Ìåðñåííà. Ñ. Â. Êîíÿãèí. Çäåñü íåîáõîäèìî îïðåäåëåíèå è ïðîñòåéøèå ñâîéñòâà ñðàâíåíèé ïî ìîäóëþ, íàïîìíåííûå â íà÷àëå ïóíêòà 'Ìàëàÿ òåîðåìà Ôåðìà'. Ðåøèòå çàäà÷è 2e è 6a îòòóäà, à òàêæå 11a èç ïóíêòà 'ïåðâîîáðàçíûå êîðíè' (íèæå). 1. Ìàëàÿ òåîðåìà Ôåðìà íå ÿâëÿåòñÿ äîñòàòî÷íûì óñëîâèåì ïðîñòîòû. (a) Äîêàæèòå, ÷òî åñëè ÷èñëî p ≥ 5 ïðîñòîå, òî ÷èñëî n = (22p − 1)/3 ñîñòàâíîå, íî 2n−1 ≡ 1 mod n. (b) Íàéäèòå òàêîå ñîñòàâíîå n, ÷òî ïðè (a, n) = 1 âûïîëíåíî an−1 ≡ 1 mod n. 2. Äîêàæèòå, ÷òî (a) Åñëè n > 2  ïðîñòîå ÷èñëî è a íå äåëèòñÿ íà n, òî a(n−1)/2 ≡ ±1 mod n. (b) Åñëè n = 2s k + 1 è a(n−1)/2 ≡ −1 mod n äëÿ íåêîòîðîãî a, òî ëþáîé ïðîñòîé äåëèòåëü p ÷èñëà n óäîâëåòâîðÿåò ñðàâíåíèþ p ≡ 1 mod 2s . (c) Åñëè n = 2s k + 1, k ≤ 2s è a(n−1)/2 ≡ −1 mod n äëÿ íåêîòîðîãî a, òî n ïðîñòîå. Ìû ïîëó÷èëè äîñòàòî÷íîå óñëîâèå ïðîñòîòû ÷èñåë ñïåöèàëüíîãî âèäà. Îòìåòèì, ÷òî åñëè ÷èñëî n = 2s k + 1 äåéñòâèòåëüíî ÿâëÿåòñÿ ïðîñòûì, òî, êàê ïðàâèëî, íàéòè ÷èñëî a, óäîâëåòâîðÿþùåå ñðàâíåíèþ a(n−1)/2 ≡ −1 mod n, ìîæíî íåáîëüøèì ïåðåáîðîì. Öåëü îñòàâøèõñÿ çàäà÷  äîêàçàòåëüñòâî ñëåäóþùåãî êðèòåðèÿ ïðîñòîòû ÷èñåë 2m − 1.  äàëüíåéøåì ñ÷èòàåì, ÷òî m ≥ 3. Êðèòåðèé Ëþêà. ×èñëî n = 2m − 1 ïðîñòîå òîãäà è òîëüêî òîãäà, êîãäà m ïðîñòîå è Mm−1 2 äåëèòñÿ íà n. Çäåñü ïîñëåäîâàòåëüíîñòü Ëþêà çàäàíà ôîðìóëàìè M1 = 4 è Mk = Mk−1 − 2. m 3. Äîêàæèòå, ÷òî åñëè ÷èñëî 2 − 1 ïðîñòîå, òî ÷èñëî m ïðîñòîå.

4. Äàëåå p ≥ 5  ïðîñòîå ÷èñëî. Îáîçíà÷èì x± k = (2 +

√

3)k ± (2 −

√

√ − − X + = {k : x+ k ≡ 0 mod p} è X = {k : xk / 3 ≡ 0 mod p}.

3)k ,

(Ðåøèòå çàäà÷è 10 è 11 èç ïóíêòà 'êâàäðàòè÷íûå âû÷åòû' ïðè ïîìîùè óêàçàíèé îò Ñ. Â. Êîíÿãèíà.) Äîêàæèòå, ÷òî √ − (a) äëÿ ëþáîãî öåëîãî k ÷èñëà x+ k è xk / 3 öåëûå. (b) åñëè z1 , z2 ∈ X + , òî z1 + z2 ∈ X − . (c) åñëè z1 , z2 ∈ X − , òî z1 + z2 ∈ X − . (d) åñëè z1 ∈ X + è z2 ∈ X − , òî z1 + z2 ∈ X + . (e) p + 1 ∈ X − èëè p − 1 ∈ X − . (f) åñëè X + 6= ∅ è z  ìèíèìàëüíûé ïîëîæèòåëüíûé ýëåìåíò ìíîæåñòâà X + , òî X + = {(2k + 1)z}, ãäå k ïðîáåãàåò ìíîæåñòâî öåëûõ ÷èñåë, è z < p. (g) Åñëè m ïðîñòîå, òî Mk = x+ . 2k−1 5. Ïóñòü m  ïðîñòîå ÷èñëî è n = 2m − 1. Äîêàæèòå, ÷òî (a) Åñëè n ïðîñòîå, òî Mm−1 ≡ 0 mod n. (b) Åñëè Mm−1 ≡ 0 mod n, òî n ïðîñòîå.

Òåñò. I. Êàêèå èç óêàçàííûõ ÷èñåë ìîãóò áûòü ïðîñòûìè ïðè íåêîòîðîì n > 2? n a) 2n + 1; b) 2n − √ 1; c) 3 · 2n √ + 1; d) 23n + 1; e) 23n − 1; f) 22 + 1. II. Âû÷èñëèòå (2 + 3)4 + (2 − 3)4 . √ a) 97 + 56 3; b) 126; c) 194. n III. Èçâåñòíî, ÷òî ÷èñëî 5 · 2n+1 + 1 äåëèò 25·2 + 1. ×òî ìîæíî ñêàçàòü î ÷èñëå 5 · 2n+1 + 1? a) îíî ïðîñòîå; b) îíî ñîñòàâíîå; c) îíî ìîæåò áûòü è ïðîñòûì, è ñîñòàâíûì, â çàâèñèìîñòè îò ÷èñëà n. Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 1a, 2abc.

2p + 1 ñîñòàâíîå. 3 2p 2 p−1 2 2p Äàëåå, 2 = 2 ·(2 ) ≡ 4 mod p. Çíà÷èò, 2 −4 äåëèòñÿ íà 2p. Òàê êàê p > 3, òî n−1 = (22p −4)/3 òàêæå äåëèòñÿ íà 2p. Ñëåäîâàòåëüíî,

1. (a) Äåéñòâèòåëüíî, 2p = 2 · (22 )

p−1 2

≡ 2 mod 3. Ïîýòîìó n = (2p − 1)

2n−1 = (22p )

n−1 2p

≡ 1 mod (22p − 1).

Èòàê, 2n−1 − 1 äåëèòñÿ íà 22p − 1 = 3n. Óêàçàíèå ê çàäà÷å 2b. Ìîæíî èñêàòü â âèäå n = pqr, ãäå p, q, r  ðàçëè÷íûå ïðîñòûå ÷èñëà. √ √ √ Óêàçàíèå ê çàäà÷å 5a. 2 + 3 = ((1 + 3)/ 2)2 .

Ïåðâîîáðàçíûå êîðíè.

1. (a) Åñëè (a, 35) = 1, òî a ≡ 1 (35). 12

ϕ(m)

(b) Åñëè m äåëèòñÿ íà äâà ðàçëè÷íûõ ïðîñòûõ íå÷åòíûõ ÷èñëà è (a, m) = 1, òî a 2 ≡ 1 (m). Ïóñòü (g, m) = 1. Âû÷åò g íàçûâàåòñÿ ïåðâîîáðàçíûì êîðíåì ïî ìîäóëþ m, åñëè îñòàòêè îò äåëåíèÿ íà m ÷èñåë g 1 , g 2 , . . . , g ϕ(m) ≡ 1 ðàçëè÷íû. 2. (a) Åñëè m äåëèòñÿ íà äâà ðàçëè÷íûõ ïðîñòûõ íå÷åòíûõ ÷èñëà, òî íå ñóùåñòâóåò ïåðâîîáðàçíîãî êîðíÿ ïî ìîäóëþ m. (b) Ïóñòü x ≡ 3 mod 4. Ìîæåò ëè x2 ≡ 1 mod 2100 ? (c)* Ïðè n > 2 íå ñóùåñòâóåò ïåðâîîáðàçíîãî êîðíÿ ïî ìîäóëþ 2n .

3. (a) ×èñëî 2 ÿâëÿåòñÿ ïåðâîîáðàçíûì êîðíåì ïî ìîäóëþ 3n . Óêàçàíèå: 22 = 1 + 3.

(b) ×èñëî 2 ÿâëÿåòñÿ ïåðâîîáðàçíûì êîðíåì ïî ìîäóëþ 5n . Óêàçàíèå: 24 = 1 + 5 · 3. (c) Íàéäèòå ïåðâîîáðàçíûé êîðåíü ïî ìîäóëþ 7n . 4. Ïðè êàêèõ n (a) 2n − 1 äåëèòñÿ íà 3100 ? (b) 2n + 1 äåëèòñÿ íà 3100 ? (c) 5n − 1 äåëèòñÿ íà 2100 ? (d) 3n + 1 äåëèòñÿ íà 2100 ? 5. Íàéòè äëèíó ïåðèîäà äðîáè (à) 1/3100 ; (b) 1/7100 . 6. (a) Ïðè öèêëè÷åñêîé ïåðåñòàíîâêå öèôð â ïåðèîäå äðîáè 1/7 = 0, (142857) ïîëó÷ÿòñÿ äðîáè âèäà 1/7, 2/7, 3/7, 4/7, 5/7, 6/7. Äîêàæèòå àíàëîãè÷íûé ôàêò äëÿ äðîáè 1/p, åñëè â íåé äëèíà ïåðèîäà ðàâíà p − 1. (b) Íàéäèòå ìíîæåñòâî îñòàòêîâ îò äåëåíèÿ ÷èñåë âèäà 10k íà 3100 . (c) Äîêàæèòå, ÷òî â ðàçëîæåíèè äðîáè 1/3100 âñòðå÷àåòñÿ ëþáàÿ êîìáèíàöèÿ èç 20 èäóùèõ ïîäðÿä öèôð. 7.* Íàéäèòå òàêèå n, ÷òîáû ñðåäè ïîñëåäíèõ 1000 öèôð ÷èñëà 2n íàøëîñü 100 ïîäðÿä èäóùèõ (à) íóëåé; (b) äåâÿòîê. 8.* Àíàëîãè÷íî çàäà÷å 7 âîïðîñ ïðî 5n . Òåîðåìà î ïåðâîîáðàçíîì êîðíå. Äëÿ ëþáîãî ïðîñòîãî p ñóùåñòâóåò ÷èñëî g , äëÿ êîòîðîãî îñòàòêè îò äåëåíèÿ íà p ÷èñåë g 1 , g 2 , g 3 , . . . , g p−1 = 1 ðàçëè÷íû. 9. Ëåììû ê òåîðåìå î ïåðâîîáðàçíîì êîðíå. Ïóñòü p ïðîñòîå è a íå äåëèòñÿ íà p. (a) p − 1 äåëèòñÿ íà íàèìåíüøåå k > 0, äëÿ êîòîðîãî ak ≡ 1 (p). Óêàçàíèå: èñïîëüçóéòå ìàëóþ òåîðåìó Ôåðìà. (b) Äëÿ ëþáûõ öåëûõ n è a ñðàâíåíèå xn ≡ a (p) èìååò íå áîëåå n ðåøåíèé. (c) Åñëè p − 1 äåëèòñÿ íà d, òî ñðàâíåíèå xd ≡ 1 (p) èìååò ðîâíî d ðåøåíèé. 10. Äîêàæèòå òåîðåìó î ïåðâîîáðàçíîì êîðíå äëÿ (a) p = 2l + 1; (b) p = 2k · 3l + 1; (c) p = 2k · 3l · 5m + 1; (d) îáùåãî ñëó÷àÿ. 11. Ïóñòü p ïðîñòîå è a íå äåëèòñÿ íà p. Ïîëîæèì orda = ordp a := min{k ≥ 1 | ak ≡ 1 (p)}. ×èñëî ordp a íàçûâàåòñÿ ïîðÿäêîì (èëè èíäåêñîì) ýëåìåíòà a ïî ìîäóëþ p. (a) Åñëè am ≡ an (p), òî m − n äåëèòñÿ íà orda. (b) aordxa = ordx. (c) Åñëè ordx è ordy âçàèìíî ïðîñòû, òî ord(xy) = ordxordy . 12. Åñëè g ïåðâîîáðàçíûé êîðåíü ïî ìîäóëþ ïðîñòîãî p > 2, òî (a) ñóùåñòâóþò òàêèå t è u, ÷òî (g + pt)p−1 = 1 + pu è u íå äåëèòñÿ íà p. (b) Äëÿ ëþáîãî öåëîãî ïîëîæèòåëüíîãî n ñóùåñòâóåò ïåðâîîáðàçíûé êîðåíü ïî ìîäóëþ pn . (c) Òî æå ïî ìîäóëþ 2pn . 13. Òåîðåìà. Ïåðâîîáðàçíûå êîðíè ñóùåñòâóþò òîëüêî ïî ìîäóëÿì 2, 4, pn , 2pn . 14. Ëåììà Ãåíçåëÿ. Ïóñòü p  ïðîñòîå ÷èñëî, x ≡ 1 mod pn , x 6≡ 1 mod pn+1 , p > 2 èëè n > 1. Äîêàæèòå, ÷òî: (a) Åñëè (a, p) = 1, òî xa ≡ 1 mod pn , íî xa 6≡ 1 mod pn+1 . (b) xp ≡ 1 mod pn+1 , è åñëè n > 1 ëèáî p > 2, òî xp 6≡ 1 mod pn+2 . (ñ) Åñëè a = pk q è q âçàèìíî ïðîñòî ñ p, òî xa ≡ 1 mod pn+k è xa 6≡ 1 mod pn+k+1 . 15. Åñëè x  ïåðâîîáðàçíûé êîðåíü ïî ìîäóëþ p3 , ãäå p  íå÷¼òíîå ïðîñòîå, òî x  ïåðâîîáðàçíûé êîðåíü ïî ìîäóëþ pn . n 16. d|(22 + 1) ⇒ 2n+1 |(d − 1).

Òåñò. I. Íàéäèòå ïåðâîîáðàçíûé êîðåíü ïî ìîäóëþ 7.

a) 1; b) 2; c) 3. II. Äëÿ ëþáîãî ëè ÷èñëà m ñóùåñòâóåò ïåðâîîáðàçíûé êîðåíü ïî ìîäóëþ m? a) äëÿ ëþáîãî; b) íå äëÿ ëþáîãî. III. Ïóñòü P (x)  ìíîãî÷ëåí ñ öåëûìè êîýôôèöèåíòàìè. Íàçîâåì åãî êîðíåì ïî ìîäóëþ p ëþáîé çëåìåíò a ìíîæåñòâà {0, 1, 2, . . . , p − 1}, äëÿ êîòîðîãî p|P (a). Êàêèå èç ñëåäóþùèõ óòâåðæäåíèé âåðíû äëÿ ëþáîãî ïðîñòîãî p è ëþáîãî öåëîãî n > 0? a) ìíîãî÷ëåí xp−1 − 1 èìååò ðîâíî p − 1 êîðåíü ïî ìîäóëþ p; b) ìíîãî÷ëåí xn − 1 èìååò ðîâíî n êîðíåé ïî ìîäóëþ p; c) ìíîãî÷ëåí ñòåïåíè n èìååò íå áîëåå n êîðíåé ïî ìîäóëþ p. Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 9bc, 15, 16. Óêàçàíèå ê çàäà÷å 9b. Äîêàæåì áîëåå îáùåå óòâåðæäåíèå: ìíîãî÷ëåí ñòåïåíè n íàä Zp íå ìîæåò èìåòü áîëåå n êîðíåé â Zp . Çäåñü ìíîãî÷ëåíîì íàçûâàåòñÿ íàáîð åãî êîýôôèöèåíòîâ ïî ìîäóëþ p, à íå ôóíêöèÿ. Ïóñòü ìíîãî÷ëåí P (x) ñòåïåíè n èìååò â Zp ðàçëè÷íûå êîðíè x1 , . . . , xn , xn+1 . Ïðåäñòàâüòå åãî â âèäå P (x) = bn (x − x1 ) . . . (x − xn ) + bn−1 (x − x1 ) . . . (x − xn−1 ) + . . . + b1 (x − x1 ) + b0 ('èíòåðïîëÿöèÿ Íüþòîíà'). Ïîñëåäîâàòåëüíî ïîäñòàâëÿÿ â ñðàâíåíèå P (x) ≡ 0 (p) âû÷åòû x1 , . . . , xn , xn+1 , ïîëó÷èì b0 ≡ b1 ≡ . . . ≡ bn−1 ≡ bn ≡ 0 (p). Òî æå ñàìîå ðåøåíèå ìîæíî çàïèñàòü è òàê. Ïóñòü P  ìíîãî÷ëåí. Òîãäà ìíîãî÷ëåí P − P (a) äåëèòñÿ íà x − a, ò.å. P − P (a) = (x − a)Q äëÿ íåêîòîðîãî ìíîãî÷ëåíà Q ñ deg Q < deg P . Ïîýòîìó åñëè P (a) = 0, òî P = (x − a)Q äëÿ íåêîòîðîãî ìíîãî÷ëåíà Q ñòåïåíè ìåíüøå deg P . Òåïåðü òðåáóåìîå â çàäà÷å óòâåðæäåíèå äîêàçûâàåòñÿ èíäóêöèåé ïî ñòåïåíè ìíîãî÷ëåíà P . Óêàçàíèå ê çàäà÷å 9c. Çàìåòüòå, ÷òî ìíîãî÷ëåí xp−1 − 1 íàä Zp èìååò ðîâíî p − 1 êîðåíü è äåëèòñÿ íà xd − 1. Äîêàæèòå, ÷òî åñëè ìíîãî÷ëåí ñòåïåíè a èìååò ðîâíî a êîðíåé è äåëèòñÿ íà ìíîãî÷ëåí ñòåïåíè b, òî ýòîò ìíîãî÷ëåí ñòåïåíè b èìååò ðîâíî b êîðíåé. Äðóãîå ðåøåíèå ìîæíî ïîëó÷èòü, çàìåòèâ, ÷òî åñëè p = kd, òî äëÿ ëþáîãî a ñðàâíåíèå y k ≡ a (p) èìååò íå áîëåå k ðåøåíèé. Óêàçàíèå ê çàäà÷å 10. Ïóíêò (a) âûòåêàåò èç òîãî, ÷òî åñëè ïåðâîîáðàçíîãî êîðíÿ íåò, òî ñðàâíåíèå m−1 x2 ≡ 1 (p) èìååò p − 1 = 2m > 2m−1 ðåøåíèé. Îñòàëüíûå ïóíêòû àíàëîãè÷íû.

ÐÀÇÍÛÅ ÇÀÄÀ×È ÏÎ ÝËÅÌÅÍÒÀÐÍÎÉ ÒÅÎÐÈÈ ×ÈÑÅË Çàäà÷è äëÿ 89 êëàññà. Å. Ïîíîìàðåâà èëè Ä. Ïåðìÿêîâ?. 1. p è q  ðàçëè÷íûå ïðîñòûå ÷èñëà. Ñêîëüêî äåëèòåëåé ó ÷èñëà pn · q m ? 2. Íàéäèòå îñòàòîê îò äåëåíèÿ 6100 íà 7. 3. Äîêàæèòå, ÷òî ÷èñëî 22225555 + 55552222 äåëèòñÿ íà 7. 4. (a) Äîêàæèòå, ÷òî 1n + 2n + . . . + (n − 1)n äåëèòñÿ íà n ïðè íå÷åòíîì n. (b) Íàéòè âñå íàòóðàëüíûå n > 1, òàêèå ÷òî 1n + 2n + . . . + (n − 1)n äåëèòñÿ íà n. 5. Íàçîâåì íàòóðàëüíîå ÷èñëî n óäîáíûì, åñëè n2 + 1 äåëèòñÿ íà 1000001. Äîêàæèòå, ÷òî ñðåäè ÷èñåë 1, 2, . . ., 1000000 ÷åòíîå ÷èñëî óäîáíûõ. 6. Äîêàæèòå, ÷òî 11n+2 + 122n+1 äåëèòñÿ íà 133 ïðè ëþáîì íàòóðàëüíîì n. 7. Íàéäèòå îñòàòîê îò äåëåíèÿ íà 7 ÷èñëà 1010 + 10100 + 101000 + . . . + 1010000000000 . 8. 56a = 65b. Äîêàæèòå, ÷òî a + b  ñîñòàâíîå ÷èñëî. 9. Äîêàæèòå, ÷òî ÷èñëî ÿâëÿåòñÿ òî÷íûì êâàäðàòîì, òîãäà è òîëüêî òîãäà, êîãäà ó íåãî íå÷åòíîå ÷èñëî íàòóðàëüíûõ äåëèòåëåé. 10. (a) Ïóñòü p > 5  ïðîñòîå ÷èñëî. Äîêàçàòü, ÷òî ñóùåñòâóåò ÷èñëî âèäà 111 . . . 111, êîòîðîå äåëèòñÿ íà p.

(b) Ïóñòü n  íàòóðàëüíîå ÷èñëî, âçàèìíî ïðîñòîå ñ 10. Äîêàçàòü, ÷òî ñóùåñòâóåò ÷èñëî âèäà 111 . . . 111, êîòîðîå äåëèòñÿ íà n. 11.* Ïóñòü n  íàòóðàëüíîå ÷èñëî, òàêîå, ÷òî n + 1 äåëèòñÿ íà 24. Äîêàæèòå, ÷òî ñóììà âñåõ íàòóðàëüíûõ äåëèòåëåé n äåëèòñÿ íà 24. 12.* Äîêàæèòå, ÷òî íè îäíî èç ÷èñåë âèäà 103n+1 íåëüçÿ ïðåäñòàâèòü â âèäå ñóììû äâóõ êóáîâ íàòóðàëüíûõ ÷èñåë. 13.* (a) Ðåøèòå óðàâíåíèå x2 + y 2 = z 2 â öåëûõ ÷èñëàõ. Óêàçàíèå. Äîñòàòî÷íî ðåøèòü äëÿ âçàèìíî ïðîñòûõ x è z . Òîãäà y 2 = (z − x)(z + x), ãäå (z − x, z + x) ∈ {1, 2}. (b) Äîêàæèòå, ÷òî ñóùåñòâóåò íå ìåíåå 100 çíà÷åíèé α ∈ (0, π2 ), òàêèõ ÷òî è sin α, è cos α ðàöèîíàëüíû. n P 1 14. Äëÿ ëþáîãî öåëîãî n ÷èñëî íå öåëîå. k k=1

Çàäà÷è äëÿ 1011 êëàññà. Áåëîâ À., Øíóðíèêîâ È. è Çàñîðèí À. 1. Íàéòè âñå öåëûå ÷èñëà n, äëÿ êîòîðûõ (a) n2 + 1 äåëèòñÿ íà n + 1. (b) n − 3|n3 − 3. 2. (à) Äîêàæèòå, ÷òî åñëè 7|a2 + b2 , ãäå a è b öåëûå ÷èñëà, òî 7|a è 7|b. (b)* Ïóñòü p = 4k + 3  ïðîñòîå ÷èñëî, äåëÿùåå a2 + b2 . Äîêàæèòå, ÷òî p|a è p|b. 3. Äîêàçàòü, ÷òî ñóùåñòâóåò áåñêîíå÷íî ìíîãî íàòóðàëüíûõ n, äëÿ êîòîðûõ ÷èñëî 4n2 + 1 äåëèòñÿ îäíîâðåìåííî íà è 13 è íà 5. 4. Äîêàçàòü, ÷òî äëÿ âñåõ íàòóðàëüíûõ n èìååì (a) 169|33n+3 − 26n − 27. 6n+2 (b) 19|22 + 3. n Fn (ñ) Fn |2 − 2, ãäå Fn = 22 + 1. (d) 3 · (15 + 25 + 35 + . . . + n5 ) äåëèòñÿ íà 13 + 23 + 33 + . . . + n3 . (e) n2 |(n + 1)n − 1. n (f) (2n − 1)2 |2(2 −1)n − 1. 5. Äîêàçàòü, ÷òî (a) 13|270 + 370 . (b) 11 · 31 · 61|2015 − 1. 6. (a) Äîêàçàòü, ÷òî ñóùåñòâóåò áåñêîíå÷íîå ÷èñëî íàòóðàëüíûõ ÷èñåë n òàêèõ, ÷òî n|2n + 1. (b) Íàéòè âñå òàêèå ïðîñòûå ÷èñëà n. n 7. Äîêàçàòü, ÷òî åñëè k íå÷åòíîå, à n íàòóðàëüíîå, òî 2n+2 |k 2 − 1. µ m ¶ a −1 8. Äîêàçàòü, ÷òî äëÿ íàòóðàëüíûõ m è a > 1 èìååì: , a − 1 = (a − 1, m). a−1 9. Èññëåäîâàòü, äëÿ êàêèõ íàòóðàëüíûõ n êîòîðîå èç ÷èñåë an = 22n+1 − 2n+1 + 1 è bn = 2n+1 2 + 2n+1 + 1 äåëèòñÿ è êîòîðîå íå äåëèòñÿ íà 5. 10. (a) Äîêàçàòü, ÷òî äëÿ êàæäîãî íàòóðàëüíîãî ÷èñëà n ñóùåñòâóåò òàêîå íàòóðàëüíîå x xx ÷èñëî x, ÷òî êàæäûé èç ÷ëåíîâ áåñêîíå÷íîé ïîñëåäîâàòåëüíîñòè x + 1, xx + 1, xx + 1, xx + 1, . . . äåëèòñÿ íà n. (b) Äîêàçàòü, ÷òî ñóùåñòâóåò áåñêîíå÷íî ìíîãî íå÷åòíûõ ÷èñåë n, äëÿ êîòîðûõ íè ïðè êàêîì xx x ÷åòíîì x íè îäíî èç ÷èñåë áåñêîíå÷íîé ïîñëåäîâàòåëüíîñòè xx +1, xx +1, xx +1, . . . íå äåëèòñÿ íà n. 11. (a) ×èñëî x îêàí÷èâàåòñÿ íà 2. Ïîñëå òîãî, êàê åãî ïîñëåäíþþ öèôðó ïåðåñòàâèëè â íà÷àëî, îíî óäâîèëîñü. Íàéòè âñå òàêèå x. (b) Ïîñëåäíþþ öèôðó ÷èñëà x ïåðåñòàâèëè â íà÷àëî. Îíî óäâîèëîñü. Äîêàçàòü, ÷òî x åñòü 2 . öèêëè÷åñêèé ñäâèã ïåðèîäà äðîáè 19

12. Äàíû ÷èñëà R è m. Ïîñëåäîâàòåëüíîñòü çàäàíà ðåêóððåíòíî: a0 çàäàíî, an+1 = man . Äîêàçàòü, ÷òî îñòàòêè an îò äåëåíèÿ íà R ñòàáèëèçèðóþòñÿ. 13. Äîêàçàòü, ÷òî åñëè 1 + 12 + . . . + p1 = m , òî n 4 (a) p|m; (b) p |(np − m). 14*. Íàòóðàëüíûé ðÿä ðàçáèò íà íåñêîëüêî àðèôìåòè÷åñêèõ ïðîãðåññèé. Äîêàçàòü, ÷òî ó äâóõ èç íèõ ðàçíîñòü ñîâïàäàåò. ∞ P 1 15*. Ïîëîæèì a1 = 1, an+1 = 9an . Äîêàçàòü, ÷òî â äåñÿòè÷íîì ðàçëîæåíèè ÷èñëà an n=1

âñòðå÷àåòñÿ ëþáàÿ êîìáèíàöèÿ öèôð. Ñì. À. Åðîøèí, Ìàòåìàòè÷åñêîå Ïðîñâåùåíèå, 8. 16. Ïðè êàêîì íàèìåíüøåì n èç ëþáûõ n ÷èñåë ìîæíî âûáðàòü k(k > 0), ïîïàðíî ñðàâíèìûõ ïî ìîäóëþ m(m > 0)? Ñì. òàêæå çàäà÷è 4b è 1014 äëÿ 8-9 êëàññà.

Òåñò. I. Íàéäèòå îñòàòîê îò äåëåíèÿ íà 7 ÷èñëà

1010 + 10100 + 101000 + . . . + 1010000000000 . a) 0; b) 1; c) 2; d) 3; e) 4; f) 5; g) 6. II. Âûáåðèòå âñå çíà÷åíèÿ n èç ïðèâåäåííûõ íèæå, ïðè êîòîðûõ 1n + 2n + . . . + (n − 1)n äåëèòñÿ íà n. a) 7; b) 8; c) 10. III. Ñóùåñòâóåò ëè ïðîñòîå ÷èñëî âèäà 111 . . . 111, ãäå êîëè÷åñòâî åäèíèö ðàâíî 3n? a) ñóùåñòâóåò; b) íå ñóùåñòâóåò. Ðåøåíèÿ è óêàçàíèÿ. Äî ïîëó÷åíèÿ çà÷åòà øêîëüíèêàì äîñòóïíû ðåøåíèÿ çàäà÷ 1a. 1. (a) Îòâåò: {−3; −2; 0; 1} Ïóñòü n + 1|n2 + 1. Òîãäà n + 1|n2 + 1 − (n + 1)(n − 1) = 2. Çíà÷èò, n + 1 = ±2 èëè n + 1 = ±1. Òîãäà íàõîäèì n = −3, −2, 0 èëè 1. Ïðîâåðêîé óáåæäàåìñÿ, ÷òî âñå òàêèå çíà÷åíèÿ n ïîäõîäÿò.

Ïðàâèëüíûå îòâåòû íà òåñòîâûå âîïðîñû. Äåëèìîñòü è äåëåíèå ñ îñòàòêîì: If, IIabd, IIIc. ÍÎÄ è ÍÎÊ: Ic, IIa, IIIab. ÏÐÎÑÒÛÅ ×ÈÑËÀ: Ib, IIb, IIIac. Êàíîíè÷åñêîå ðàçëîæåíèå: Ib, IIa, IIIbd. ËÈÍÅÉÍÛÅ ÄÈÎÔÀÍÒÎÂÛ ÓÐÀÂÍÅÍÈß: Ia, IIc, IIIc. Öåëûå òî÷êè ïîä ïðÿìîé: Ic, IIb, IIIb. Ìàëàÿ òåîðåìà Ôåðìà: Ib, IId, IIIabcdefh. Êâàäðàòè÷íûå âû÷åòû: Ia, IIb, IIIb. Ïðîâåðêà ïðîñòîòû ÷èñåë Ìåðñåííà: Iabcf, IIc, IIIa. Ïåðâîîáðàçíûå êîðíè: Ic, IIb, IIIac. Ðàçíûå çàäà÷è ïî ýëåìåíòàðíîé òåîðèè ÷èñåë If, IIa, IIIb.