Решить в натуральных числах x! = y! z^2

[Woland]

ИСПРАВИЛ:

Руст писал(а):

Вначале надо доказать, что при k>1,y>k в разложении хотя бы одного числа входит простой множитель больше k.

Допустим это не так, тогда найдутся по крайней мере два числа
$M_1 , M_2 $ которые кратны m, где m -по условию максимальное
простое число <=k. т.е $ m=max|p_i| $, где $p_i $ -простые
и $ p_i<=k$ , тогда разность между двумя числами $D=M_1 - M_2 $ кратна m. Но поскольку числа $M_1 , M_2 $
не равны между собой и $M_1$ не делится не на одно из 2,3,..,m-1 то
оно должно делится на некоторое ПРОСТОЕ число большее k либо представлятся
ввиде $M_1=m^l$.

[Руст]

Woland писал(а):

Руст писал(а):

А вы не учли, что последнее число делится на простое число m гораздо меньше, чем k. Вот в приведённом примере k=89 а m=43.

Уважаемый Руст, доказательство взаимопростоты с числом p у меня получается из того, что я доказываю ,что существует число не
делящееся одновременно на 2,3,..,m-1. При этом совершенно не
важно на, что делятся выкинутые на том или ином этапе числа,
раз это число не делится не на одно из 2,3,..,m-1. Правда здесь
есть тонкий момент, связанный стем,что возможно на одном из
этапов, мы выкинули cамо число делящееся m.
Гипотеза: этого быть не может.

Как я и говорил контрпример достаточно большой. Минимальный из них такой:
у=14 478 292 443 583, k=89. Убедитесь, что вычеркивая по вашей методике числа из ряда y+1,y+2,y+3,...,y+89 вы последним вычеркните число делящееся на 43 - y+36. А в первом шаге вы вычеркните другое число делящееся на 43 - y+79.

[Руст]

Woland писал(а):

ИСПРАВИЛ:

Руст писал(а):

Вначале надо доказать, что при k>1,y>k в разложении хотя бы одного числа входит простой множитель больше k.

Допустим это не так, тогда найдутся по крайней мере два числа
$M_1 , M_2 $ которые кратны m, где m -по условию максимальное
простое число <=k. т.е $ m=max|p_i| $, где $p_i $ -простые
и $ p_i<=k$ , тогда разность между двумя числами $D=M_1 - M_2 $ кратна m. Но поскольку числа $M_1 , M_2 $
не равны между собой и $M_1$ не делится не на одно из 2,3,..,m-1 то
оно должно делится на некоторое ПРОСТОЕ число большее k либо представлятся
ввиде $M_1=m^l$.

Почему это число не делится ни на одно из других простых чисел. Как видно в приведённом примере это не так.

[Woland]

Руст писал(а):

Woland писал(а):

ИСПРАВИЛ:

Руст писал(а):

Вначале надо доказать, что при k>1,y>k в разложении хотя бы одного числа входит простой множитель больше k.

Допустим это не так, тогда найдутся по крайней мере два числа
$M_1 , M_2 $ которые кратны m, где m -по условию максимальное
простое число <=k. т.е $ m=max|p_i| $, где $p_i $ -простые
и $ p_i<=k$ , тогда разность между двумя числами $D=M_1 - M_2 $ кратна m. Но поскольку числа $M_1 , M_2 $
не равны между собой и $M_1$ не делится не на одно из 2,3,..,m-1 то
оно должно делится на некоторое ПРОСТОЕ число большее k либо представлятся
ввиде $M_1=m^l$.

Почему это число не делится ни на одно из других простых чисел. Как видно в приведённом примере это не так.

Вы согласны ,что оно не может делится на 2 и на 3 хотябы?

[Руст]

Если речь идёт о числе, которое делится на максимальное простое число не превышающее k, то оно может делится на любые другие простые числа меньше k. Найдите из указанного промежутка, число делящееся на 89. А если речь идёт о последнем числе в вашем построении, то здесь мне пришлось найти минимальный контрпример, когда другое число, делящееся на 43 из этого интервала чётно.

[juna]

А тут дискуссия...

Руст писал(а):

Я неправильно высказался и исправил. А это утверждение (которое вы доказываете) вообще не верно. Пусть числа $p_1,p_2,...,p_s, P=p_1*...*p_{s-2}$ простые не превосходящие к. Тогда выбем число а: $aP=-1(mod \ p_{s-1}),aP=1(mod \ p_s),(0<a<p_{s-1}p_s)$
Тогда взяв $y=aP-b, b=p_{s-1}$ получаем, что каждое число (y+1),(y+2),...(y+2b-1) делится на простое число меньшее к. Так как 2b-1>=k при k>4 то это доказывает, что это утверждение неверно.

Но мне доказательство Руста непонятно. Ясно, что контрпример нужно искать в больших промежутках, где все числа составные. Пусть по китайской теореме мы подбираем такие $a$, что $aP=-1(mod \ p_{s-1}),aP=1(mod \ p_s),(0<a<p_{s-1}p_s)$, почему из этого должно следовать, что в произведении $(ap_1p_2..p_{s-2}-p_{s-1}+1)(ap_1p_2..p_{s-2}-p_{s-1}+2)$ $(ap_1p_2..p_{s-2}-p_{s-1}+3)...(ap_1p_2..p_{s-2}-p_{s-1}+2p_{s-1}-1)$ нет числа взаимно простого со всеми остальными. И что такое $k$ в Ваших обозначениях?
Другие рассуждения пока не смотрел, контрпример 14 478 292 443 583, k=89 проверять желание как-то не возниканет.

[Woland]

Руст писал(а):

Woland писал(а):

Руст писал(а):

А вы не учли, что последнее число делится на простое число m гораздо меньше, чем k. Вот в приведённом примере k=89 а m=43.

Уважаемый Руст, доказательство взаимопростоты с числом p у меня получается из того, что я доказываю ,что существует число не
делящееся одновременно на 2,3,..,m-1. При этом совершенно не
важно на, что делятся выкинутые на том или ином этапе числа,
раз это число не делится не на одно из 2,3,..,m-1. Правда здесь
есть тонкий момент, связанный стем,что возможно на одном из
этапов, мы выкинули cамо число делящееся m.
Гипотеза: этого быть не может.

Как я и говорил контрпример достаточно большой. Минимальный из них такой:
у=14 478 292 443 583, k=89. Убедитесь, что вычеркивая по вашей методике числа из ряда y+1,y+2,y+3,...,y+89 вы последним вычеркните число делящееся на 43 - y+36. А в первом шаге вы вычеркните другое число делящееся на 43 - y+79.

Я проверил Ваш пример и действительно:
14 478 292 443 583+36=14478292443619
14 478 292 443 583+79=14478292443662
И НОД(14478292443619,14478292443662)=43 , и число
14478292443619=43*336704475433 ,причём число 336704475433 является простым.
и значит число 14478292443619 не могло быть выкинуто не на каком предыдущем шаге,
но то, что это последний шаг проверить достаточно трудно. (скажите Вы точно уверены
в том, что это число выкинется на последнем шаге, ведь весьма вероятно ,что в конце может остатся сразу несколько чисел, но не одно не имеет общих множителей простыми
меньшими k ). Кроме того я установил что в указанном Вами промежутке простых нет.
Значит гипотеза не верна.
Но не всё так плохо. По крайней мере для k<=6 это верно.

[maxal]

См. http://dxdy.ru/viewtopic.php?p=27408#27408

[Woland]

Maxal может Вы подскажете, как можно доказать,что среди k подряд идущих чисел,
найдется хотябы одно, которое делится на простое, большее k?

[Woland]

maxal писал(а):

Это неверное утверждение. Минимальным контр-примером является отрезок [2184,2200], состоящий из 17 целых чисел. Более того, доказано, что для каждого существуют последовательных целых чисел, среди которых нет ни одного взаимно-простого со всеми остальными.

А доказанно ли, что среди l чисел найдётся по крайней мере одно число имеющее с
о всеми остальными лишь один общий множитель?

[maxal]

Woland писал(а):

Maxal может Вы подскажете, как можно доказать,что среди k подряд идущих чисел,
найдется хотябы одно, которое делится на простое, большее k?

$1,2,3,\dots,k$ является контрпримером.

[Руст]

Я говорил, что при у>k=x-y в последовательности (y+1),(y+2),...,(y+k) существует число имеющее простой делитель больше к (можно даже несколько улучшить оценку больше m, который растёт примерно как k*lnk). Доказывается это простой оценкой:

$$ord_p(\frac{(y+1)(y+2)...(y+k)}{k!})\le max_{i|i\le k}(ord_p(y+i)).$$

[Руст]

Приведу вначале решение промежуточной задачи, число (y+1)(y+2)...(y+k) имеет простой делитель больше k при y>=k.
Допустим, что все простые делители не превосходят k. Тогда из приведённого неравенства получим, что
$f(y)=\frac{(y+1)(y+2)...(y+k-\pi(k))}{k!}$
не превосходит 1. Т.е. если f(y)>1, то существует простой делитель у указанного произведения больше чем k. Ясно, что f(y) многочлен от y монотонно растущий при положительных значениях y. Поэтому, если покажем, что f(k+l)>1, то при y>=k+l у указанного произведения имеется простой делитель больше k. При небольших k это неравенство не выполняется при l=0. Поэтому, пришлось гонять на компьютере до k=600. Максимальное значение при котором требуется сдвиг, для выполнения этого неравенства это k=199 l=1, максимальное значение требуемого сдвига при k=113 l=14. Так как максимальное расстояние между простыми когда они не превосходят 200 равно 14 то при 600>k>13 или выполняется неравенство или в произведении имеется простое значение, в любом случае это утверждение верно. При k<=13 максимальный сдвиг 9 и легко перебрать, что оно верно при k<=13. Для случая k>=600 (условно большие значения) для доказательства f(y=k)>1 применим аналитические методы. Вначале выясним, при каких с выполняется((2-с)k)!>(k!)^2 (эквивалентно f(k)>1 при с=pi(k)/k).
Используя формулу Стирлинга получаем:

$$(2-c)k[ln(2-c)+lnk-1]-2k(lnk-1)>2ln(\frac{k!e^k}{k^k})-ln(\frac{((2-c)k)!e^{(2-c)k}}{((2-c)k )^{(2-c)k)}})$$

Здесь правая часть O(ln k) а левая O(k). Поэтому исследуем вначале левую часть. Она убывает при 0<c<1. Так как при k>=600 pi(k)ln(k)/k<1.2 если при подставке c=1.2/ln k неравенство выполняется, то это доказывает утверждение.
При этом левая часть равна:
$k[2ln(2-\frac{1.2}{ln k})-1.2]+k\frac{1.2}{ln k}[1-ln(2-\frac{1.2}{ln k})]$
а правая часть не превосходит $(1+\frac{1}{12k})ln(2\pi k)-0.5ln(2\pi 5k/3)$
Легко проверяется, что приk>=600 уже первая член левой части положителен, второй член превосходит правую часть. Это доказывает наше утверждение при любом k.
Следствием этого утверждения является то, что при $y\le k^2+k$ наше уравнение не имет решений кроме указанных выше (тривиальных). Действительно, если y<=k(k+1), то у произведения имеется простой делитель p>=k+1. Так как p^2>x=y+k<=k^2+2k, то он входит в произведение только в один член и в первой степени.

[Руст]

По просьбе форумчан приведу краткое изложение решения.
Пусть $P=\{p_1,p_2,...,p_l\}$ множество всех простых меньших чем к. Общим делителем двух сомножителей могут быть только произведения этих чисел, меньшие чем k. Если уравнение имеет нетривиальное решение, то каждое число y+i представляется в виде произведения в первой степени некоторых из этих простых чисел и квадрата некоторого числа. Соответственно числу y+i сопоставляется некоторое подмножество S(i) множества P, а именно, состоящие из всех простых делящих y+i, степень которых нечётен. Тогда

$$y+i=a_i^2M(i), \ M(i)=\prod_{p\in S(i)} p.$$

Если для двух чисел числа M(i) и M(j) совпадают, то получаем два квадрата $|a_i^2-a_j^2|<\frac{k}{M(i)}, a_^2,a_j^2>y$, а это невозможно при доказанной ранее неравенству $y>k^2+k.$
При этом для решения каждое простое число должно входить в чётное количество подмножеств S(i).
В качестве иллюстрации k=2 два последовательных квадрата натуральных чисел (это невозможно). k=3 дает или два квадрата с расстоянием 2 или два квадрата с расстоянием 1.
k=5 имеется два простых, меньших 5 - 2 и 3. Имеется всего 4 подмножества у P, стало быть у двоих множители M(i) совпадают.
Однако, не всегда найдутся совпадающие множители. Например k=4 возможно M(1)=6,M(2)=1,M(3)=2,M(4)=3.
Введём следующую операцию умножения на множителях M(i) или сложения на S(i): По определению $M(i)*M(j)=\frac{M(i)M(j)}{gcd(M(i),M(j))^2}, S(i)+S(j)=S(i)US(j)-2S(i)*S(j)$ (сложение по модулю 2)
Тогда, всегда найдутся или две совпадающие M(i) или четыре множителя удовлетворяющие условию $M(i)*M(j)=M(s)*M(t)$, т.е произведения двух множителей после сокращения на квадрат общих множителей совпадает с соответствующей операцией для другой пары. С учётом y>k^2 это становится невозможным.
Есть и другие доказательства. Например, предположим вначале k=2m чётным и запишем уравнение в виде

$$P(t^2)=\prod_{i=1}^m (t^2-(2i-1)^2)=(2^mz)^2,t=2y+k+1>(k+1)(2k+1).$$

Выделяя отсюда полный квадрат $P(t^2)=Q(t)^2+R(t),deg R(t)\le 2[\frac{m-1}{2}].$
При этом

$$Q(t)=[t^m\prod_{i=1}^m(1-\frac{(2i-2)^2}{2t^2}-\frac{(2i-1)^4}{8t^4}-... ) ]$$

Здесь из разложения по t берутся только входящие в неотрицательной степени.
И при таком решении условие t>(k+1)(2k+1) приводит к противоречию с малой разницей двух квадратов чисел.

[maxal]

Руст писал(а):

число (y+1)(y+2)...(y+k) имеет простой делитель больше k при y>=k.

Это теорема Сильвестра-Шура, впоследствии упрощенная Эрдёшем, который доказал ее в форме:
если $n\geq 2k$, то ${n\choose k}$ имеет простой делитель $p>k$.

Фолкнер доказал более сильный результат (MR0190073 Faulkner, M. On a theorem of Sylvester and Schur. J. London Math. Soc. 41 1966 107--110):
Пусть $p_k$ - наименьшее простое большее $2k$. Тогда если $n\geq p_k$, ${n \choose k}$ имеет простой делитель $p\geq p_k$, за исключением случаев ${9 \choose 2}$ и ${10 \choose 3}$.

Затем Хэнсон доказал (MR0340162 Hanson, D. On a theorem of Sylvester and Schur. Canad. Math. Bull. 16 (1973), 195--199):
Произведение $k$ последовательных чисел $n(n+1)\cdots(n+k-1)$ больших $k$ содержит простой делитель больший $3k/2$, за исключением случаев $3\cdot 4$, $8\cdot 9$ и $6\cdot 7\cdot 8\cdot 9\cdot 10$.