Наибольший общий делитель бинома

[venco]

venco в сообщении #245920 писал(а):

ananova в сообщении #245897 писал(а):

Хочу найти все делители числа

$$ (x+y)^p - x^p - y^p $$

Есть делители: $p, x, y, (x+y)$.
Если $p>3$, то есть ещё делитель $x^2+xy+y^2$.

Похоже, если $p \equiv 1 \pmod 6$, то делитель $x^2+xy+y^2$ в квадрате.

[Nilenbert]

venco в сообщении #245936 писал(а):

Похоже, если $p \equiv 1 \pmod 6$, то делитель $x^2+xy+y^2$ в квадрате.

Да, именно так. Это как раз написано в книге Рибенбойм П. Последняя теорема Ферма для любителей. –М : Мир, 2003, параграф VII.2.

[ananova]

Благодарю, maxal! Очень выручили. Прямо "веер" без какой-либо видимой закономерности.

-- Ср сен 23, 2009 20:33:26 --

Кстати, в списке вариантов делителей нет простого числа $p$. По условию $p <x <y$

[maxal]

ananova в сообщении #245952 писал(а):

Кстати, в списке вариантов делителей нет простого числа $p$.

В приведенных мной разложениях $p$ считается фиксированным простым числом, а делители перечисляются как многочлены от $x$ и $y$.

[ananova]

Количество делителей не так много, как казалось. Даже без интуиции видно, что их количество меньше чем p. А более точная оценка, пожалуй даст значительно меньшие числа. А есть оператор обратный факториалу? А то бы точней можно было бы расчитать границу по количеству уникальных простых делителей.

[ananova]

Решил на каникулах вернуться к старой темке и задать уточнящий вопрос:

ananova в сообщении #245897 писал(а):

Хочу найти все делители числа

$$ (x+y)^p - x^p - y^p $$

Если $p$ - простое , то p является делителем бинома без двух крайних членов. Может ли число $p^2$ или того более $p^k$ быть делителем, при НОД $(x, y, p)$=1? Чисто интуитивно, вроде как не может, но интуиция может подводить.

[maxal]

ananova
еще как может:
$x=y=1$, $p=1093$ например.

-- Wed Dec 30, 2009 16:49:47 --

И кстати, если нечетное $p$ делит $x+y$, $p^2$ делит $(x+y)^p - x^p - y^p$.

Но даже если потребовать попарной взаимной простоты всех $x$, $y$, $x+y$, $p$, то все равно решения существуют. Вот, например, тройки [p,x,y], которые дают делимость на $p^5$:

[7, 3, 5]
[13, 7, 8]
[19, 5, 16]
[31, 11, 24]
[37, 7, 33]
[43, 13, 35]
[61, 9, 56]
[67, 32, 45]
[73, 17, 63]
[79, 40, 51]
[97, 55, 57]

[ananova]

Очень признателен, maxal!
Не в службу, а в дружбу, - как говорится - запустите, пожалуйста, программку на генерацию подобных троек:
исключите все случаи, когда p≥x/2, при этом оставьте условие $x<y$. Есть уверенность, что ни одной тройки не получится.

[maxal]

ananova
То есть вам нужны тройки, удовлетворяющие $2p<x<y$ ?
А делимость на какую степень $p$ ? Если $p^2$, то вот например: $(p,x,y)=(7, 15, 16).$

-- Thu Dec 31, 2009 09:22:50 --

Меня заинтересовал следующий "феномен":
Существует очень много попарно взаимно-простых троек $x<y<p$, где $p$ - простое, удовлетворяющих делимости $p^5\mid ((x+y)^p - x^p - y^p)$ (в частности, даже при $p$ не делящем $x+y$), но вот ни одной тройки с делимостью на $p^6$ пока что найти не удалось.
Есть ли этому простое объяснение?

[ananova]

Да, все правильно! Благодарю. Теперь есть над чем подумать!

[age]

maxal в сообщении #276738 писал(а):

Меня заинтересовал следующий "феномен":
Существует очень много попарно взаимно-простых троек $x<y<p$, где $p$ - простое, удовлетворяющих делимости $p^5\mid ((x+y)^p - x^p - y^p)$ (в частности, даже при $p$ не делящем $x+y$), но вот ни одной тройки с делимостью на $p^6$ пока что найти не удалось.
Есть ли этому простое объяснение?

Ну поскольку для ряда $p=6k+1$ (кажется) число $(x+y)^p-x^p-y^p$ делится на $(x^2+xy+y^2)^2$, то если $x^2+xy+y^2\div p^2$, то $(x^2+xy+y^2)^2\div p^4$. Плюс, если $p$ - простое, то $(x+y)^p-x^p-y^p\div p$. Итого $p^5$. Остальные множители $(x+y)^p-x^p-y^p$ на $p$ не делятся, что, в принципе, очевидно, т.к. все множители - взаимно простые числа. Поэтому, для того, чтобы была делимость на $p^6$ необходимо либо чтобы $x^2+xy+y^2\div p^3$, либо чтобы "большой множитель" делился на $p^5$ (если $x<y<p$).
Возможно, можно рассмотреть оба случая и доказать:
1. $x^2+xy+y^2\div p^3$ - невозможно, при $x<y<p$.
2. "большой множитель" не делится на $p$, при $p>7$, $x<y<p$. (а может и вообще никогда)

Да, если $x>p$, то $(18+1)^7-18^7-1^7\div 7^7$.

[age]

Совсем что-то не соображал, что писал! Случай 1
$x^2+xy+y^2\div p^3$ - невозможно, при $x<y<p$ - тривиален, т.к. $x^2+xy+y^2<3y^2$. Поэтому, если $p>y$, то $p^3>3y^2>x^2+xy+y^2$.

Остается доказать, что
2. "большой множитель" не делится на $p$, при $p>7$, $x<y<p$.
В частности, при $p=11$ "больший множитель" равен $B=x^6+3x^5y+7x^4y^2+9x^3y^3+7x^2y^4+3xy^5+y^6$ и может быть приведен к виду:

$B=\left[(a^2-b)^3+a^2b^2\right]\div11$ для некоторых $a,b$.

Эту задачу, думаю, можно решить.

[ananova]

age в сообщении #276781 писал(а):

Да, если $x>p$, то $(18+1)^7-18^7-1^7\div 7^7$.

Любопытное наблюдение. Т.е. возможно:

$x>p$, то $(x+1)^p-x^p-1^p\div p^p$

А вот такое возможно?:
$x>p$, то $(x+p)^p-x^p-p^p\div p^p$

[age]

age в сообщении #276831 писал(а):

$B=\left[(a^2-b)^3+a^2b^2\right]\div11$ для некоторых $a,b$.

Эту задачу, думаю, можно решить.

На самом деле $B$ эквивалентно не уравнению, а системе:
$\begin{cases} B=\left[(a^2-b)^3+a^2b^2\right]\div11\\ a^2-4b=u^2 \end{cases}$
В пределах $a,b<3500$ эта система решений не имеет.

[maxal]

age в сообщении #276831 писал(а):

частности, при $p=11$ "больший множитель" равен $B=x^6+3x^5y+7x^4y^2+9x^3y^3+7x^2y^4+3xy^5+y^6$ и может быть приведен к виду:

$B=\left[(a^2-b)^3+a^2b^2\right]\div11$ для некоторых $a,b$.

Чтобы удостоверится в неделимости $B$ на 11 ни при каких целых $x,y$ не нужно делать никаких преобразований - достаточно перебрать все возможные значения $x,y$ от 0 до 10.