Теория чисел: делимость и простые числа - сложные задачи с решениями

Решение:
Пусть [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]8[/tex] делится только [tex]376=8\cdot 47[/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]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]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] евро, и чиновник ошибся.