Теория на числата - делимост и прости числа - трудни задачи с решения

Решение:
Нека [tex]d[/tex] е най-големият общ делител на двете числа. Тогава [tex]d[/tex] дели всяка тяхна линейна комбинация с цели коефициенти, в частност
[tex]\left(2^{2004}-1\right)-4\left(2^{2002}-1\right)=2^{2004}-1-2^{2004}+4=3[/tex]
Следователно [tex]d=1[/tex] или [tex]d=3[/tex]. От друга страна, [tex]4\equiv 1\pmod 3[/tex], затова и двете числа се делят на [tex]3[/tex]:
[tex]2^{2002}-1=4^{1001}-1\equiv 1-1=0\pmod 3,\qquad 2^{2004}-1=4^{1002}-1\equiv 1-1=0\pmod 3[/tex]
Значи [tex]d=3[/tex]. (Това съответства на общото правило [tex]\text{НОД}\left(2^m-1; 2^n-1\right)=2^{\text{НОД}(m; n)}-1[/tex]: тук [tex]\text{НОД}(2002; 2004)=2[/tex] и [tex]2^2-1=3[/tex].)

Решение:
Последните две цифри на едно число се определят от остатъка му при деление на [tex]100[/tex], а последните две цифри на произведение зависят само от последните две цифри на множителите. Затова
[tex]666^{666}\equiv 66^{666}\pmod{100}[/tex]
Пресмятаме степени на [tex]66[/tex] по модул [tex]100[/tex]:
[tex]66^2=4356\equiv 56,\quad 66^4\equiv 56^2=3136\equiv 36,\quad 66^5\equiv 36\cdot 66=2376\equiv 76\pmod{100}[/tex]
Тъй като [tex]76^2=5776\equiv 76\pmod{100}[/tex], всяка степен [tex]76^k[/tex] с [tex]k\ge 1[/tex] завършва на [tex]76[/tex]. Понеже [tex]666=5\cdot 133+1[/tex], получаваме
[tex]66^{666}=\left(66^5\right)^{133}\cdot 66\equiv 76\cdot 66=5016\equiv 16\pmod{100}[/tex]
Следователно числото [tex]666^{666}[/tex] завършва на [tex]16[/tex].

Решение:
Ако [tex]N=q_1^{a_1}q_2^{a_2}\ldots q_k^{a_k}[/tex] е разлагането на [tex]N[/tex] на прости множители, то броят на делителите на [tex]N[/tex] е [tex](a_1+1)(a_2+1)\ldots(a_k+1)[/tex].
При [tex]p=2[/tex]: [tex]p^2+11=15=3\cdot 5[/tex] има [tex]4[/tex] делителя, така че [tex]p=2[/tex] не е решение. При [tex]p=3[/tex]: [tex]p^2+11=20=2^2\cdot 5[/tex] има [tex](2+1)(1+1)=6[/tex] делителя, така че [tex]p=3[/tex] е решение.
Нека сега [tex]p\ge 5[/tex]. Тогава [tex]p[/tex] е нечетно, затова [tex]p^2\equiv 1\pmod 4[/tex] и [tex]4\mid p^2+11[/tex]; освен това [tex]3\nmid p[/tex], затова [tex]p^2\equiv 1\pmod 3[/tex] и [tex]3\mid p^2+11[/tex]. Следователно
[tex]p^2+11=2^a\cdot 3^b\cdot m,\qquad a\ge 2,\ b\ge 1[/tex]
където [tex]m[/tex] не се дели нито на [tex]2[/tex], нито на [tex]3[/tex]. Ако [tex]d(m)[/tex] е броят на делителите на [tex]m[/tex], то броят на делителите на [tex]p^2+11[/tex] е
[tex](a+1)(b+1)\cdot d(m)\ge 3\cdot 2\cdot 1=6[/tex]
Равенство се достига само при [tex]a=2[/tex], [tex]b=1[/tex], [tex]m=1[/tex], т.е. [tex]p^2+11=12[/tex], което е невъзможно, защото [tex]p^2+11\ge 36[/tex]. Значи при [tex]p\ge 5[/tex] числото [tex]p^2+11[/tex] има повече от [tex]6[/tex] делителя. Единственото такова просто число е [tex]p=3[/tex].

Решение:
Нека [tex]N=2^3\cdot 3^4\cdot 5^6[/tex]. И [tex]x[/tex], и [tex]y[/tex] делят най-малкото си общо кратно [tex]N[/tex], затова
[tex]x=2^{a_1}3^{b_1}5^{c_1},\qquad y=2^{a_2}3^{b_2}5^{c_2}[/tex]
с цели неотрицателни степенни показатели. Най-малкото общо кратно взима по-големия показател на всяко просто число, затова [tex]\text{НОК}(x; y)=N[/tex] точно когато
[tex]\max(a_1; a_2)=3,\qquad \max(b_1; b_2)=4,\qquad \max(c_1; c_2)=6[/tex]
като трите условия са независими. За простото число [tex]2[/tex]: двойките [tex](a_1; a_2)[/tex] с [tex]0\le a_1, a_2\le 3[/tex] са [tex]4^2=16[/tex], като в [tex]3^2=9[/tex] от тях и двата показателя са най-много [tex]2[/tex]; следователно в [tex]16-9=7[/tex] двойки максимумът е точно [tex]3[/tex]. По същия начин простото число [tex]3[/tex] дава [tex]5^2-4^2=9[/tex] двойки, а простото число [tex]5[/tex] дава [tex]7^2-6^2=13[/tex] двойки.
По правилото за умножение броят на наредените двойки е
[tex]7\cdot 9\cdot 13=819[/tex]

Решение:
Тъй като [tex]323=17\cdot 19[/tex], където [tex]17[/tex] и [tex]19[/tex] са различни прости числа, достатъчно е да докажем, че [tex]a_n[/tex] се дели на [tex]17[/tex] и на [tex]19[/tex]. Ще използваме два факта. Първо, [tex]x-y[/tex] дели [tex]x^k-y^k[/tex] за всяко естествено [tex]k[/tex], защото
[tex]x^k-y^k=(x-y)\left(x^{k-1}+x^{k-2}y+\ldots+y^{k-1}\right)[/tex]
Второ, [tex]x^{2n}-y^{2n}=\left(x^2\right)^n-\left(y^2\right)^n[/tex] се дели на [tex]x^2-y^2=(x-y)(x+y)[/tex], а значи и на [tex]x+y[/tex].
Делимост на [tex]17[/tex]: записваме
[tex]a_n=\left(20^{2n}-3^{2n}\right)+\left(16^{2n}-1^{2n}\right)[/tex]
Първата скоба се дели на [tex]20-3=17[/tex] (по първия факт), а втората — на [tex]16+1=17[/tex] (по втория факт).
Делимост на [tex]19[/tex]: записваме
[tex]a_n=\left(20^{2n}-1^{2n}\right)+\left(16^{2n}-3^{2n}\right)[/tex]
Първата скоба се дели на [tex]20-1=19[/tex] (по първия факт), а втората — на [tex]16+3=19[/tex] (по втория факт).
Тъй като [tex]17[/tex] и [tex]19[/tex] са взаимно прости, [tex]a_n[/tex] се дели на [tex]17\cdot 19=323[/tex].

Решение:
Да допуснем, че [tex]121\mid n^2+3n+5[/tex] за някое естествено [tex]n[/tex]. Тогава [tex]121[/tex] дели и
[tex]4\left(n^2+3n+5\right)=4n^2+12n+20=(2n+3)^2+11[/tex]
В частност [tex]11\mid (2n+3)^2+11[/tex], откъдето [tex]11\mid (2n+3)^2[/tex]. Тъй като [tex]11[/tex] е просто число, [tex]11\mid 2n+3[/tex] и следователно [tex]121\mid (2n+3)^2[/tex].
Сега от [tex]121\mid (2n+3)^2+11[/tex] и [tex]121\mid (2n+3)^2[/tex] следва [tex]121\mid 11[/tex], което не е вярно. Полученото противоречие показва, че [tex]n^2+3n+5[/tex] никога не се дели на [tex]121[/tex].
(Числото може да се дели на [tex]11[/tex]: например при [tex]n=4[/tex] то е равно на [tex]33[/tex]. Затова в разсъждението наистина е нужен квадратът [tex]121=11^2[/tex].)

Решение:
Нека [tex]A=20x+17y[/tex], [tex]B=17x+20y[/tex] и [tex]d[/tex] е най-големият им общ делител. Тогава [tex]d[/tex] дели
[tex]20A-17B=(400-289)x=111x,\qquad 20B-17A=(400-289)y=111y[/tex]
Следователно [tex]d[/tex] дели [tex]\text{НОД}(111x; 111y)=111\cdot \text{НОД}(x; y)=111[/tex], т.е. [tex]d\le 111[/tex].
Стойността [tex]111=3\cdot 37[/tex] се достига. Например за взаимно простите числа [tex]x=1[/tex], [tex]y=38[/tex] (избрани така, че [tex]x\equiv y\pmod{37}[/tex] и [tex]3\mid x+y[/tex]) получаваме
[tex]A=20+646=666=6\cdot 111,\qquad B=17+760=777=7\cdot 111[/tex]
и тъй като [tex]6[/tex] и [tex]7[/tex] са взаимно прости, най-големият общ делител на [tex]A[/tex] и [tex]B[/tex] е [tex]111[/tex]. Най-голямата възможна стойност е [tex]111[/tex].

Решение:
Ако [tex]n=p_1^{a_1}p_2^{a_2}\ldots p_k^{a_k}[/tex] е разлагането на [tex]n[/tex] на прости множители, то броят на делителите му е [tex](a_1+1)(a_2+1)\ldots(a_k+1)[/tex]. Тъй като [tex]9[/tex] се представя като произведение на множители, по-големи от [tex]1[/tex], само като [tex]9[/tex] или [tex]3\cdot 3[/tex], числото [tex]n[/tex] има точно [tex]9[/tex] делителя тогава и само тогава, когато [tex]n=p^8[/tex] или [tex]n=p^2q^2[/tex], където [tex]p[/tex] и [tex]q[/tex] са различни прости числа.
Случай [tex]n=p^8[/tex]: [tex]2^8=256\lt 5000[/tex], [tex]3^8=6561[/tex] е в интервала, а [tex]5^8=390625\gt 8000[/tex], така че този случай дава [tex]1[/tex] число.
Случай [tex]n=(pq)^2[/tex]: тъй като [tex]70^2=4900\lt 5000\le 71^2=5041[/tex] и [tex]89^2=7921\le 8000\lt 90^2=8100[/tex], трябва
[tex]71\le pq\le 89[/tex]
В този интервал произведенията на две различни прости числа са
[tex]74=2\cdot 37,\quad 77=7\cdot 11,\quad 82=2\cdot 41,\quad 85=5\cdot 17,\quad 86=2\cdot 43,\quad 87=3\cdot 29[/tex]
Останалите числа са прости ([tex]71; 73; 79; 83; 89[/tex]) или се делят на квадрат на просто число, или имат три прости множителя ([tex]72; 75; 76; 78; 80; 81; 84; 88[/tex]). Значи този случай дава [tex]6[/tex] числа:
[tex]74^2=5476; \ 77^2=5929; \ 82^2=6724; \ 85^2=7225; \ 86^2=7396; \ 87^2=7569[/tex]
Общо има [tex]1+6=7[/tex] такива числа.

Решение:
Означаваме числото с [tex]f(n)[/tex] и го разлагаме на множители:
[tex]f(n)=n\left(9n^4-5n^2-4\right)=n\left(n^2-1\right)\left(9n^2+4\right)=(n-1)n(n+1)\left(9n^2+4\right)[/tex]
Нека [tex]D[/tex] е търсеният най-голям общ делител. Тогава [tex]D[/tex] дели числата
[tex]f(2)=1\cdot 2\cdot 3\cdot 40=240=2^4\cdot 3\cdot 5,\qquad f(3)=2\cdot 3\cdot 4\cdot 85=2040=2^3\cdot 3\cdot 5\cdot 17[/tex]
и следователно [tex]D[/tex] дели техния най-голям общ делител [tex]2^3\cdot 3\cdot 5=120[/tex]. Ще покажем, че [tex]120=3\cdot 8\cdot 5[/tex] дели [tex]f(n)[/tex] за всяко [tex]n[/tex].
Делимост на [tex]3[/tex]: едно от трите последователни числа [tex]n-1[/tex], [tex]n[/tex], [tex]n+1[/tex] се дели на [tex]3[/tex].
Делимост на [tex]8[/tex]: ако [tex]n[/tex] е нечетно, то [tex]n-1[/tex] и [tex]n+1[/tex] са последователни четни числа и едното от тях се дели на [tex]4[/tex], така че [tex]8\mid (n-1)(n+1)[/tex]. Ако [tex]n=2k[/tex] е четно, то [tex]9n^2+4=4\left(9k^2+1\right)[/tex] се дели на [tex]4[/tex], а [tex]n[/tex] се дели на [tex]2[/tex], така че [tex]8\mid n\left(9n^2+4\right)[/tex].
Делимост на [tex]5[/tex]: ако [tex]n[/tex] дава остатък [tex]0[/tex], [tex]1[/tex] или [tex]4[/tex] при деление на [tex]5[/tex], то едно от числата [tex]n[/tex], [tex]n-1[/tex], [tex]n+1[/tex] се дели на [tex]5[/tex]. Ако остатъкът е [tex]2[/tex] или [tex]3[/tex], то [tex]n^2\equiv 4\pmod{5}[/tex] и
[tex]9n^2+4\equiv 9\cdot 4+4=40\equiv 0\pmod{5}[/tex]
Тъй като [tex]3[/tex], [tex]8[/tex] и [tex]5[/tex] са взаимно прости по двойки, [tex]120\mid f(n)[/tex] за всяко естествено [tex]n[/tex]. Следователно [tex]D=120[/tex].

Решение:
Разлагаме [tex]P[/tex] с формулата за разлика на квадрати:
[tex]P=a\left[\left(a\left(a^2-7\right)\right)^2-6^2\right]=a\left(a^3-7a-6\right)\left(a^3-7a+6\right)[/tex]
Полиномът [tex]a^3-7a-6[/tex] има корен [tex]a=-1[/tex], а [tex]a^3-7a+6[/tex] има корен [tex]a=1[/tex]; след деление на съответните линейни множители получаваме
[tex]a^3-7a-6=(a+1)(a+2)(a-3),\qquad a^3-7a+6=(a-1)(a-2)(a+3)[/tex]
Следователно [tex]P[/tex] е произведение на седем последователни цели числа:
[tex]P=(a-3)(a-2)(a-1)\,a\,(a+1)(a+2)(a+3)[/tex]
Имаме [tex]5040=2^4\cdot 3^2\cdot 5\cdot 7[/tex]. Сред всеки седем последователни цели числа има кратно на [tex]7[/tex] и кратно на [tex]5[/tex]; има поне две кратни на [tex]3[/tex], така че произведението се дели на [tex]3^2[/tex]; има поне три последователни четни числа, а от всеки две последователни четни числа едното се дели на [tex]4[/tex], така че тези три числа дават множител поне [tex]2\cdot 2\cdot 4=2^4[/tex].
Тъй като [tex]16[/tex], [tex]9[/tex], [tex]5[/tex] и [tex]7[/tex] са взаимно прости по двойки и всяко от тях дели [tex]P[/tex], произведението им дели [tex]P[/tex]:
[tex]16\cdot 9\cdot 5\cdot 7=5040\mid P[/tex]

Решение:
Нека [tex]x=5^{\frac{p-1}{2}}[/tex]; то е цяло число, защото [tex]p[/tex] е нечетно.
Случай [tex]p=5[/tex]: [tex]x+10=5^2+10=35[/tex] се дели на [tex]5[/tex], така че [tex]p=5[/tex] е решение.
Случай [tex]p\ne 5[/tex]: според малката теорема на Ферма [tex]p[/tex] дели
[tex]5^{p-1}-1=x^2-1=(x-1)(x+1)[/tex]
и тъй като [tex]p[/tex] е просто, [tex]p\mid x-1[/tex] или [tex]p\mid x+1[/tex].
Ако [tex]p\mid x-1[/tex], то [tex]p\mid (x+10)-(x-1)=11[/tex], т.е. [tex]p=11[/tex]. Ако [tex]p\mid x+1[/tex], то [tex]p\mid (x+10)-(x+1)=9[/tex], т.е. [tex]p=3[/tex].
Проверка: при [tex]p=3[/tex] получаваме [tex]5+10=15[/tex], което се дели на [tex]3[/tex]; при [tex]p=11[/tex] получаваме [tex]5^5+10=3135=11\cdot 285[/tex].
Следователно [tex]p\in\{3; \,5; \,11\}[/tex]. Случаят [tex]p=5[/tex] лесно се пропуска, защото за него теоремата на Ферма не е приложима.

Решение:
Условието означава, че [tex]x^2[/tex] и [tex]x[/tex] имат еднакви последни три цифри, т.е.
[tex]x^2\equiv x\pmod{1000}\iff 1000\mid x(x-1),\qquad 100\le x\le 999[/tex]
Тъй като [tex]1000=8\cdot 125[/tex], а последователните числа [tex]x-1[/tex] и [tex]x[/tex] са взаимно прости, множителят [tex]8=2^3[/tex] дели изцяло едното от тях, както и [tex]125=5^3[/tex]. Ако двата делят едно и също число, то [tex]1000\mid x[/tex] или [tex]1000\mid x-1[/tex], което е невъзможно за трицифрено [tex]x[/tex]. Остават два случая.
Случай [tex]1[/tex]: [tex]125\mid x[/tex] и [tex]8\mid x-1[/tex]. Трицифрените кратни на [tex]125[/tex] са [tex]125; 250; 375; 500; 625; 750; 875[/tex], а остатъците им при деление на [tex]8[/tex] са [tex]5; 2; 7; 4; 1; 6; 3[/tex]. Само [tex]x=625[/tex] дава остатък [tex]1[/tex].
Случай [tex]2[/tex]: [tex]8\mid x[/tex] и [tex]125\mid x-1[/tex]. Тогава [tex]x\in\{126; 251; 376; 501; 626; 751; 876\}[/tex]. Нечетните числа не се делят на [tex]8[/tex], а измежду [tex]126; 376; 626; 876[/tex] само [tex]376=8\cdot 47[/tex] се дели на [tex]8[/tex].
Проверка:
[tex]625^2=390625,\qquad 376^2=141376[/tex]
Търсените числа са [tex]376[/tex] и [tex]625[/tex].

Решение:
Всяко от простите числа [tex]17[/tex], [tex]19[/tex], [tex]23[/tex] дели точно едно от числата [tex]1; 2; \ldots; 26[/tex], защото [tex]2\cdot 17=34\gt 26[/tex]. Ако например [tex]17[/tex] не е задраскано, произведението на неговата група се дели на [tex]17[/tex], а произведението на другата група не се дели, така че произведенията не са равни. Следователно [tex]17[/tex], [tex]19[/tex] и [tex]23[/tex] трябва да бъдат задраскани.
Ако останалите числа са разделени на две групи с равни произведения [tex]Q[/tex], то произведението на всички останали числа е [tex]Q^2[/tex], т.е. точен квадрат. Степенният показател на [tex]2[/tex] в [tex]26![/tex] е
[tex]\left\lfloor\frac{26}{2}\right\rfloor+\left\lfloor\frac{26}{4}\right\rfloor+\left\lfloor\frac{26}{8}\right\rfloor+\left\lfloor\frac{26}{16}\right\rfloor=13+6+3+1=23[/tex]
Задраскването на нечетните числа [tex]17[/tex], [tex]19[/tex], [tex]23[/tex] не го променя, така че произведението на останалите [tex]23[/tex] числа съдържа [tex]2[/tex] на нечетна степен и не е точен квадрат. Значи трябва да се задраска още поне едно число, т.е. общо поне [tex]4[/tex] числа.
Четири числа са достатъчни: задраскваме [tex]14[/tex], [tex]17[/tex], [tex]19[/tex], [tex]23[/tex]. Останалите числа могат да се разделят на групите [tex]\{1; 2; 3; 4; 5; 6; 7; 8; 9; 11; 24; 25; 26\}[/tex] и [tex]\{10; 12; 13; 15; 16; 18; 20; 21; 22\}[/tex], като произведението на всяка група е
[tex]2^{11}\cdot 3^5\cdot 5^3\cdot 7\cdot 11\cdot 13[/tex]
Следователно най-малкият брой е [tex]4[/tex].

Решение:
Нека числата в избрания ред са [tex]a_1, a_2, \ldots, a_{11}[/tex]. Всяко от тях е четирицифрено, така че полученото число е
[tex]N=a_1\cdot 10^{40}+a_2\cdot 10^{36}+\ldots+a_{10}\cdot 10^{4}+a_{11}[/tex]
Тъй като [tex]10^4-1=9999=11\cdot 909[/tex] и [tex]10^{4j}-1=\left(10^4\right)^j-1[/tex] се дели на [tex]10^4-1[/tex], всяко число [tex]10^{4j}-1[/tex] се дели на [tex]11[/tex]. Следователно разликата
[tex]N-\left(a_1+a_2+\ldots+a_{11}\right)=a_1\left(10^{40}-1\right)+a_2\left(10^{36}-1\right)+\ldots+a_{10}\left(10^{4}-1\right)[/tex]
се дели на [tex]11[/tex]. Сумата [tex]a_1+a_2+\ldots+a_{11}[/tex] не зависи от реда; тя е сбор на единадесет последователни числа със среден член [tex]2014[/tex]:
[tex]2009+2010+\ldots+2019=11\cdot 2014[/tex]
Следователно [tex]11\mid N[/tex] при всеки ред на числата. Тъй като [tex]N\gt 11[/tex], числото [tex]N[/tex] има делител, различен от [tex]1[/tex] и от [tex]N[/tex], така че не е просто.

Решение:
Ако един затвор има [tex]n[/tex] етажа, в него има [tex]n\cdot n\cdot n=n^3[/tex] затворници и за всеки от тях се отпускат [tex]n[/tex] евро, така че този затвор струва [tex]n^3\cdot n=n^4[/tex] евро. Следователно общият разход е
[tex]S=n_1^4+n_2^4+\ldots+n_{14}^4[/tex]
където [tex]n_1, n_2, \ldots, n_{14}[/tex] са естествени числа. Разглеждаме остатъците при деление на [tex]16[/tex]. Ако [tex]n=2k[/tex] е четно, то [tex]n^4=16k^4\equiv 0\pmod{16}[/tex]. Ако [tex]n=2k+1[/tex] е нечетно, то [tex]n^2=4k(k+1)+1=8t+1[/tex] за някое цяло [tex]t[/tex], защото [tex]k(k+1)[/tex] е четно, и
[tex]n^4=(8t+1)^2=64t^2+16t+1\equiv 1\pmod{16}[/tex]
Следователно [tex]S\equiv r\pmod{16}[/tex], където [tex]r[/tex] е броят на затворите с нечетен брой етажи и [tex]0\le r\le 14[/tex]. Значи остатъкът на [tex]S[/tex] при деление на [tex]16[/tex] е някое от числата [tex]0; 1; \ldots; 14[/tex]. От друга страна,
[tex]1\,599\,999=16\cdot 100\,000-1=16\cdot 99\,999+15[/tex]
дава остатък [tex]15[/tex] при деление на [tex]16[/tex]. Следователно общият разход не може да бъде [tex]1\,599\,999[/tex] евро и чиновникът е сгрешил.