#12 Многочлены, последовательности и теория чисел

Для \(k\ge1\) имеем \(a^k-b^k=(a-b)(a^{k-1}+a^{k-2}b+\cdots+b^{k-1})\). Константа даёт нулевую разность. Сумма таких выражений с целыми коэффициентами тоже делится на \(a-b\). Значит, утверждение верно для любого \(f\in\mathbb Z[x]\).

Первое утверждение следует из формулы разности степеней. Для второго заметим: \(a^{2n+1}+b^{2n+1}=a^{2n+1}-(-b)^{2n+1}\), а это делится на \(a-(-b)=a+b\).

Так как \(n+m\equiv n\pmod m\), для каждого одночлена \((n+m)^k\equiv n^k\pmod m\). Значит, \(f(n+m)\equiv f(n)\pmod m\). Поэтому остатки повторяются с периодом \(m\) (возможно, не минимальным).

Решаем \(n^2+n+1\equiv0\pmod7\). Проверка остатков даёт: при \(n\equiv2\), \(4+2+1=7\), а при \(n\equiv4\), \(16+4+1=21\). Другие остатки не подходят. Ответ: \(n\equiv2\) или \(4\pmod7\).

Вычислим: \(u_{n+1}=3(n+1)^2+2(n+1)+1=3n^2+8n+6\), \(u_{n-1}=3(n-1)^2+2(n-1)+1=3n^2-4n+2\). Тогда \(u_{n+1}-2u_n+u_{n-1}=6\). Это равно \(2\) умножить на старший коэффициент \(3\).

Из \(n-0\mid f(n)-f(0)\) получаем \(f(n)\equiv f(0)\pmod n\). Если \(n\mid f(n)\) для всех \(n\), то \(n\mid f(0)\) для всех \(n\), откуда \(f(0)=0\). Обратно, если \(f(0)=0\), то \(f(n)-f(0)\) делится на \(n\), значит \(n\mid f(n)\).

Так как \(f(0)=0\), многочлен \(x\) делит \(f(x)\) в \(\mathbb Z[x]\). Так как \(f(1)=0\), многочлен \(x-1\) тоже делит \(f(x)\). Они взаимно просты, значит \(x(x-1)\mid f(x)\) в \(\mathbb Z[x]\). Поэтому \(f(n)=n(n-1)g(n)\) при некотором \(g\in\mathbb Z[x]\), и делимость доказана.

Числа \(n\) и \(n-1\) имеют разную чётность, поэтому их произведение делится на \(2\). Следовательно, \(P(n)\in\mathbb Z\). Однако коэффициент при \(x^2\) равен \(\frac12\), не целый. Значит, \(P\) не является многочленом с целыми коэффициентами.

Пусть \(n\equiv r\pmod m\), \(0\le r

Пары \((F_n,F_{n+1})\) по модулю \(m\) имеют не более \(m^2\) значений, поэтому какая-то пара повторится. Переход \((x,y)\mapsto(y,x+y)\) обратим по модулю \(m\): из \((y,z)\) восстанавливаем \((z-y,y)\). Значит, если пара повторилась, то период продолжается назад до начальной пары \((0,1)\). Следовательно, последовательность периодична с самого начала.

Используем тождество \(F_{r+d}=F_{d-1}F_r+F_dF_{r+1}\). Если \(F_d\mid F_r\), то обе части правой суммы делятся на \(F_d\). Поэтому \(F_d\mid F_{r+d}\). Начиная с \(r=d\), по индукции получаем \(F_d\mid F_{2d},F_{3d},\ldots\). Если \(n=td\), то \(F_d\mid F_n\).

По модулю \(m\) существует только \(m^2\) возможных пар \((u_n,u_{n+1})\). Поэтому среди первых \(m^2+1\) пар две совпадут. Начиная с первого повторения, дальнейшие значения полностью определяются той же рекуррентной формулой, значит последовательность остатков будет повторяться. Это даёт периодичность с некоторого места.

Пусть \(p=f(a)\) — простое положительное число. Для любого целого \(t\) имеем \(a+pt\equiv a\pmod p\), значит \(f(a+pt)\equiv f(a)\equiv0\pmod p\). Так как \(f\) непостоянен, значения \(|f(a+pt)|\) неограниченно растут при больших \(t\). Для достаточно большого \(t\) получим положительное значение, большее \(p\), но делящееся на \(p\). Оно составно. Противоречие.

Докажем индукцией по \(k\). Для \(k=1\) формула известна. По биному Ньютона

\[(t+1)^{k+1}-t^{k+1}=(k+1)t^k+\sum_{j=0}^{k-1}\binom{k+1}{j}t^j.\]

Суммируем по \(t=1,\ldots,n\). Левая часть телескопируется в \((n+1)^{k+1}-1\). Суммы меньших степеней по предположению индукции уже являются многочленами. Поэтому \((k+1)S_k(n)\), а значит и \(S_k(n)\), является многочленом. Старший член получается из \((n+1)^{k+1}/(k+1)\), степень равна \(k+1\).

По модулю \(19\) имеем \(2^4=16\equiv-3\). Поэтому достаточно добиться \(2^n\equiv4\pmod{18}\), так как порядок \(2\) по модулю \(19\) делит \(18\). Остатки \(2^n\pmod{18}\) периодичны, и \(2^n\equiv4\pmod{18}\) при \(n\equiv2\pmod6\). Значит, для всех \(n\equiv2\pmod6\) число \(2^{2^n}+3\) делится на \(19\). При \(n>2\) оно больше \(19\), следовательно, составно. Таких \(n\) бесконечно много.

Возьмём \(m=1\) и \(p(x)=x^k+N-1\). Тогда \(p\in\mathbb Z[x]\), степень равна \(k\), а \(p(1)=1+N-1=N\). Построение завершено.

Если \(n^2\mid f(n)\), то тем более \(n\mid f(n)\), значит по задаче о \(n\mid f(n)\) имеем \(f(0)=0\), то есть \(f(x)=x h(x)\), где \(h\in\mathbb Z[x]\). Теперь \(n^2\mid f(n)=n h(n)\) даёт \(n\mid h(n)\) для всех \(n\). Снова применяем критерий и получаем \(h(0)=0\), то есть \(h(x)=xg(x)\). Следовательно, \(f(x)=x^2g(x)\). Обратное очевидно: \(f(n)=n^2g(n)\).

Оператор \(\Delta P(x)=P(x+1)-P(x)\) переводит целочисленные значения в целочисленные значения. Поэтому \(\Delta^dP(0)\) — целое число. Если старший коэффициент \(P\) равен \(c\), то при каждом применении \(\Delta\) степень уменьшается на \(1\), а старший коэффициент умножается на текущую степень. После \(d\) применений получаем постоянный многочлен со значением \(d!c\). Значит, \(d!c=\Delta^dP(0)\in\mathbb Z\).

Пусть \(m>n\). Из тождества \(F_m=F_{m-n}F_{n+1}+F_{m-n-1}F_n\) следует \(F_m\equiv F_{m-n}F_{n+1}\pmod{F_n}\). Известно, что \(\gcd(F_{n+1},F_n)=1\), поэтому \(\gcd(F_m,F_n)=\gcd(F_{m-n},F_n)\). Это ровно шаг алгоритма Евклида для индексов.

Повторяя шаг, получаем \(\gcd(F_m,F_n)=\gcd(F_g,F_0)\), где \(g=\gcd(m,n)\). Так как \(F_0=0\), это равно \(F_g\).

По модулю \(m\) последовательность пар \((F_n,F_{n+1})\) чисто периодична и начинается с \((0,1)\). Значит, существует период \(T>0\), для которого \((F_T,F_{T+1})\equiv(0,1)\pmod m\). В частности, \(F_T\equiv0\pmod m\).

Так как та же пара повторяется через каждый период, \((F_{qT},F_{qT+1})\equiv(0,1)\pmod m\) для всех \(q\ge1\). Поэтому \(m\mid F_{qT}\) для бесконечно многих \(qT\).