Одно сравнение

[Руст]

Пусть $p>3$ простое число и $p|n^2+n+1$ для некоторого целого $n$.
Докажите, что

$$(n+1)^p=n^p+1\mod p^3.$$

[nnosipov]

Это задача М2173 из "Задачника Кванта". Решение получается из следующих наблюдений. Во-первых, $p$ имеет вид $6k+1$. Во-вторых, при таких $p$ многочлен

$$ f(x):=(x+1)^p-x^p-1 $$

делится на $(x^2+x+1)^2$. В-третьих, все коэффициенты многочлена $f(x)$ кратны $p$.

[Руст]

Я забыл замечательное свойство, что $px(x+1)(x^2+x+1)^a|f(x)$ при $p>3$, где $a=1$ при $p=-1\mod 3$ и $a=2$ при $p=1\mod 3$, т.е. $a=3 -(p\%3)$.
Соответственно решил задачу существенно проще, без использования этого свойства.
В частности, моим методом удается показать, что при $1<n<p$ и $p|n^2+n+1$ никогда $p^4\not |(n+1)^p-n^p-1$.
Для делимости на $p^4$ необходимо (и достаточно) в этом случае $p^2|n^2+n+1$.

[nnosipov]

Это также просто. Достаточно поделить с остатком многочлен

$$ g(x)=\frac{f(x)}{p(x^2+x+1)^2}=\frac{(x+1)^p-x^p-1}{p(x^2+x+1)^2} $$

на $x^2+x+1$. При $p=6k+1$ остаток будет равен $-k$.

[Руст]

nnosipov в сообщении #685472 писал(а):

Это также просто. Достаточно поделить с остатком многочлен

$$ g(x)=\frac{f(x)}{p(x^2+x+1)^2}=\frac{(x+1)^p-x^p-1}{p(x^2+x+1)^2} $$

на $x^2+x+1$. При $p=6k+1$ остаток будет равен $-k$.

Не понял, как вы лихо поделили. Вообще то соотношение $f_p(x)=\frac{(x+1)^p-x^p-1}{px(x+1)(x^2+x+1)^a}, f_p(x)\in Z[x]$ открыл Коши в 1841 году.
Тут то понятно делимость. А дальше как делить?

[nnosipov]

Руст в сообщении #685529 писал(а):

Вообще то соотношение $f_p(x)=\frac{(x+1)^p-x^p-1}{px(x+1)(x^2+x+1)^a}, f_p(x)\in Z[x]$ открыл Коши в 1841 году.

Интересно, не знал об этом. Запишем $f_p(x)=(x^2+x+1)q(x)+ax+b$, после чего достаточно будет вычислить $f_p(\zeta)$, где $\zeta$ --- комплексный кубический корень из единицы. Получите $f_p(\zeta)=k$ при $p=6k+1$, т.е. будет $a=0$, $b=k$. Для вычисления $f_p(\zeta)$ можно воспользоваться Лопиталем.

[Руст]

nnosipov в сообщении #685552 писал(а):

Руст в сообщении #685529 писал(а):

Вообще то соотношение $f_p(x)=\frac{(x+1)^p-x^p-1}{px(x+1)(x^2+x+1)^a}, f_p(x)\in Z[x]$ открыл Коши в 1841 году.

Интересно, не знал об этом.

Я освежил память из книги Рибенбойма "Прследняя теорема Ферма". Этим люди занимались в связи с теоремой Ферма, хотя и само по себе тут есть довольно любопытные вещи.
В частности, можно ввести переменную $y=x^2+x+1$ и разложить $f_p(x)=\prod_(y-\alpha_i)$. Причем корни $\alpha_i$ объединяются в тройки $\alpha_{3k}+\alpha_{3k-1}+\alpha_{3k-2}=0$. Если один из корней принадлежит $Z_p$, то остальный тоже. Если доказать, что нет корней из $Z_p$, то отсюда можно получить первый случай теоремы Ферма, возможно и второй.

[nnosipov]

Руст в сообщении #685590 писал(а):

Этим люди занимались в связи с теоремой Ферма,

А, вот в чём дело. Надо заглянуть в Рибенбойма, спасибо за информацию.

[Руст]

Если Обозначить через $f_p(x)=\frac{(x+1)^p-x^p-1}{x(x+1)(x^+x+1)^a}=z^{3k-3}g_p(u), u=\frac{(z-1)^2}{z^3}, z=x^2+x+1$, то он удовлетворяет следующему рекурентному соотношению:

$$g_p(u)=(2+3u)g_{p-6}(u)-(3u^2-6u+1)g_{p-12}(u)+u^3g_{p-18}u,$$

$p-$ произвольные нечетные числа.
Начальные условия:
$g_3(u)=3,(a=0), g_5(u)=5, g_7(u)=7$
$g_9(u)=9+3u,g_{11}(u)=11(1+u), g_{13}(u)=13(1+2u)$,
$g_{15}(u)=15+50u+3u^2, g_{17}(u)=17(1+5u+u^2), g_{19}(u)=19(1+7u+3u^2),$
Отсюда даже не видно, почему для простых $p$ многочлен $g_p(u)$ степени $[\frac{p-3}{6}]$ делится на $p$. Тем не менее это так.
$g_{23}(u)=23(1+12u+14u^2+u^3),...$, когда $p=q^l$- степень простого больше 3, то все коэффициенты делятся на простое $q$, но некоторые не делятся на $p$.
Например $g_{25}(u)=25+375u+630u^2+100u^3$.

[Руст]

Ночью не смог звснуть, пока не нашел точную формулу для многочлена Коши для нечетных $n$:

$$f_n(x)=\frac{\(x+1)^n-x^n-1}{nx(x+1)}=(x^2+x+1)^kg_n(u).$$

Здесь $k=\frac{n-3}{2}, u=\frac{x^2(x+1)^2}{(x^2+x+1)^3}$ и

$$g_n(u)=\frac{1}{n}\sum_{i=0}^{[(n-3)/6]}(2C_{k-i}^{2i+1}+3C_{k-i}^{2i})u^i=\sum_{i=0}^{[(n-3)/6]}\frac{C_{k-i}^{2i}u^i}{2i+1}.$$

Из двух представлений видно, что при простом $n$ многочлен с целыми коэффициентами, при не простом для некоторых членов могут стоять делители числа $n$ в знаменателе.

Используя это можно доказать первый случай теоремы Ферма. Возможно как нибудь запишу на соответствующей теме.

[nnosipov]

Интересное тождество для $f_n(u)$. Попробуем понять, почему оно верно.

[Руст]

Попробуйте доказать. Задача не простая, но и не требует ничего из высшей математики.