Полные квадраты

[lopkityu]

Найдите все такие пары натуральных чисел $ (n, k) $, что число $ (n+1)(n+2)...(n+k)-k $ является полным квадратом.

Задача взята из заключительного этапа казахстанской республиканской олимпиады для школьников. Решение есть, но оно, на мой взгляд, слишком объёмное и непростое как для девятиклассников, которым она предлагалась.

[Руст]

Для школьников такую задачу нельзя давать.
Надо заметить, что член $S(n)=(n+1)(n+2)...(n+k)$ делится на $k!$.
Если $k\ge 5$ и простое, то тот член, который делится на это простое, после деления должен дать остаток -1 по модулю $k=p$.
Кроме того $k=7\mod 8$ и $(\frac{-k}{q})=(\frac qk)=1 \forall q<k$. Последнее не выполняется, иначе получается, что все нечетные числа квадратичные вычеты по $k$.
Если $k$ не простое, то любой простой делитель входит в $S(n)$ в большей степени чем в $k$. Следовательно число $k$ квадрат. Нечетным квадратом не может быть, так как в этом случае обязан быть $7\mod 8$.
Если $k=2^{2l}$, то $l\ge 2$ и $S(n)/k$ делится как минимум на 128 (достаточно на 4), что после вычета не даст число вида $1\mod 8$, т.е. квадрат.
Уж тем более это верно в случае $k=2^{2l}m^2$.
Остаются случаи $k\le 4$.
$k=4$ $S(n)-4=(n^2+5n+5)^2-5>(n^2+5n+4)^2$.
$k=1$, то решением будет $n=m^2$
$k=2$ $n(n+3)=m^2\to n=1$ решение $(n,k)=(1,2)$.
Наиболее сложный случай $k=3$, дает эллиптическое уравнение $m^2=n^3+6n^2+11n+3$. Из теории эллиптических кривых можно показать отсутствие целых решений.

[lopkityu]

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

Если $k=2^{2l}$, то $l\ge 2$ и $S(n)/k$ делится как минимум на 128 (достаточно на 4), что после вычета не даст число вида $1\mod 8$, т.е. квадрат.

Что-то не могу вникнуть в смысл этой фразы. Мои рассуждения в случае составного $ k $ сводились к построению бесконечной последовательности $ \{ p_{m}: m\geq 1 \} $, где $ p_1=3 $, а $ \forall i\geq 1\ p_{i+1} $ - простой делитель числа $ \prod \limits_{j=1}^{i} p_{j}^2 -2 $, который имеет вид $ 4r+3 $, а дальше показывалось, что все члены последовательности разные и что $ k $ обязано делиться на каждое из этих чисел, откуда все и следует.

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

Наиболее сложный случай $k=3$, дает эллиптическое уравнение $m^2=n^3+6n^2+11n+3$. Из теории эллиптических кривых можно показать отсутствие целых решений.

Увы, я не знаком пока с этой теорией, поэтому пришлось здесь пользоваться старыми добрыми методами.
Имеем $ (n+1)(n+2)(n+3)-3=q^2 $, откуда $ n+2=\frac{q^2+3}{(n+2)^2-1} $, причем видим, что $ n+2 $ - четное. Так как $ q^2+3 \equiv 3 \mod \ 9 $, то $ (n+2)^2-1 $ может делиться только на 3, но не на 9. Тогда $ (n+2)^2-1 $ имеет простой делитель $ p>3 $ и $ 1=\left( \frac{-3}{p} \right)=\left( \frac{p}{3} \right) $, откуда $ p\equiv 1\mod \ 3 $. Если $ (n+2)^2-1 $ взаимно простое с 3, то $ (n+2)^2 \equiv 2\mod \ 3 $; если же нет, то $ (n+2)^2 \equiv 4\mod \ 9 $, из чего делаем вывод, что $ n+2 \equiv 2\mod \ 9 $ или $ n+2 \equiv 7\mod \ 9 $. Проверку проходит только второе решение. Тогда $ n+3 $ взаимно простое с 2 и 3, и аналогичными рассуждениями показываем, что $ n+3 \equiv 1\mod \ 3 $. Противоречие
А вообще интересно, могут ли быть здесь идеи, которые приводят к этим результатам проще и быстрее, на уровне школьных знаний.

[Руст]

lopkityu в сообщении #1005449 писал(а):

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

Если $k=2^{2l}$, то $l\ge 2$ и $S(n)/k$ делится как минимум на 128 (достаточно на 4), что после вычета не даст число вида $1\mod 8$, т.е. квадрат.

Что-то не могу вникнуть в смысл этой фразы.

Из $l\ge 2$ следует, что $k\ge 16$ и $\frac{S(n)}{k}$ делится на $2^{v_2(15!)}=2^{10}$.

[nnosipov]

lopkityu в сообщении #1005449 писал(а):

Увы, я не знаком пока с этой теорией, поэтому пришлось здесь пользоваться старыми добрыми методами.
Имеем $ (n+1)(n+2)(n+3)-3=q^2 $, откуда $ n+2=\frac{q^2+3}{(n+2)^2-1} $, причем видим, что $ n+2 $ - четное. Так как $ q^2+3 \equiv 3 \mod \ 9 $, то $ (n+2)^2-1 $ может делиться только на 3, но не на 9. Тогда $ (n+2)^2-1 $ имеет простой делитель $ p>3 $ и $ 1=\left( \frac{-3}{p} \right)=\left( \frac{p}{3} \right) $, откуда $ p\equiv 1\mod \ 3 $. Если $ (n+2)^2-1 $ взаимно простое с 3, то $ (n+2)^2 \equiv 2\mod \ 3 $; если же нет, то $ (n+2)^2 \equiv 4\mod \ 9 $, из чего делаем вывод, что $ n+2 \equiv 2\mod \ 9 $ или $ n+2 \equiv 7\mod \ 9 $. Проверку проходит только второе решение. Тогда $ n+3 $ взаимно простое с 2 и 3, и аналогичными рассуждениями показываем, что $ n+3 \equiv 1\mod \ 3 $. Противоречие
А вообще интересно, могут ли быть здесь идеи, которые приводят к этим результатам проще и быстрее, на уровне школьных знаний.

Вот этот кусок можно изложить попроще.

Одно из чисел $n+1$, $n+2$, $n+3$ имеет вид $3k-1$, а значит, имеет простой делитель $p$ такого же вида. Это $p$ не может быть нечётным, ибо все нечётные простые делители $m^2+3$ имеют вид $3k+1$. Осталось рассмотреть случай, когда одно из чисел $n+1$, $n+2$, $n+3$ есть степень двойки с нечётным показателем. Так как $m^2+3 \not\equiv 0 \pmod{8}$, то этот показатель должен быть равен единице. Но таких решений нет.

На мой взгляд, уровень теоретико-числовых задач на этой олимпиаде весьма высок. Статистика показывает, что школьники с такими задачами не справляются. Интересно было бы узнать, почему задачи такого уровня всё же предлагаются.

[lopkityu]

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

Вот этот кусок можно изложить попроще.

Одно из чисел $n+1$, $n+2$, $n+3$ имеет вид $3k-1$, а значит, имеет простой делитель $p$ такого же вида. Это $p$ не может быть нечётным, ибо все нечётные простые делители $m^2+3$ имеют вид $3k+1$. Осталось рассмотреть случай, когда одно из чисел $n+1$, $n+2$, $n+3$ есть степень двойки с нечётным показателем. Так как $m^2+3 \not\equiv 0 \pmod{8}$, то этот показатель должен быть равен единице. Но таких решений нет.

Хех, что-то я перемудрил с выкладками...

[TR63]

lopkityu в сообщении #1005449 писал(а):

$ n+2 $ - четное.

Почему только чётное?

-- 19.04.2015, 19:05 --

Вот, если оно нечётное, тогда всё просто.

[lopkityu]

TR63 в сообщении #1005607 писал(а):

Почему только чётное?

В противном случае $ (n+1)(n+2)(n+3)-3 \equiv5\mod 8 $ и квадрата не выйдет.

[scwec]

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

Интересно было бы узнать, почему задачи такого уровня всё же предлагаются.

Включил ведь Д.Э. Кнут ВТФ в упражнения во втором томе "Искусство программирования" 1980г,
а в издание 2000 года, когда проблема уже была решена, неразрешенную $x^n+y^n+z^n=w^n$ для $n>4$.
Имеет право.
Кстати, в разобранной здесь задаче случай $k=4$ относится к области эллиптических кривых,
так же как и $k=3$

[nnosipov]

lopkityu в сообщении #1005587 писал(а):

Хех, что-то я перемудрил с выкладками...

Я там тоже слегка ошибся (со степенями двойки погорячился), но это легко поправить.

scwec в сообщении #1005646 писал(а):

Кстати, в разобранной здесь задаче случай $k=4$ относится к области эллиптических кривых,

Относится, но ... Там ведь будет уравнение вида $n^4+\ldots=q^2$, которое легко решается "зажиманием" между двумя квадратами.

[scwec]

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

Там ведь будет уравнение вида $n^4+\ldots=q^2$, которое легко решается "зажиманием" между двумя квадратами

Конечно. Никаких возражений. Зажиманием так зажиманием.

[Shadow]

Для $k=4$ можно зажать, можно записать как $(n+1)(n+2)(n+3)(n+4)=q^2+2^2$ и включить теорему Ферма-Эйлера. Она работает и при $k=3$
$(n-1)n(n+1)=q^2+3\;\Rightarrow (n+2)(n^2-2n+3)=q^2+3^2$ и поскольку $4\mid n$ обратить внимание на второй сомножитель левой части, но г-н nnosipov
нашел более простое решение. Но из той же оперы - довольно нетривиалное для доказательства утверждение, непосильное для школьника.

Неговоря об общее решение Руст

[rightways]

Пусть $k>4$ , тогда $(n+1)...(n+k-4)=(k-4)m$ , пусть $(n+k-3)(n+k-2)(n+k-1)(n+k)=4s$, тогда
$a^2+4=(k-4)(4ms-1)$
-что невозможно.
Значит $k\le 4$ дальше уже легко...

-- 22.04.2015, 02:32 --

При $k=4$ точно такое же противоречие выходит. ?

[lopkityu]

rightways
Вот оно! Это именно то, что я искал

rightways в сообщении #1006595 писал(а):

При $k=4$ точно такое же противоречие выходит. ?

Здесь можно даже взять $ k>3 $ и аналогично прийти к тому, что $ a^2+3=(k-3)(3ms-1) $. $ s $ - четное, потому правая часть имеет простой делитель вида $ 6r-1 $, а $ (-3) $ не является по нему вычетом.
А вот еще понизить планку до $ k>2 $ что-то не получается. Было бы хорошо одним махом отсеять все нетривиальные случаи...

[Naf2000]

lopkityu в сообщении #1006622 писал(а):

rightways
Вот оно! Это именно то, что я искал

rightways в сообщении #1006595 писал(а):

При $k=4$ точно такое же противоречие выходит. ?

Здесь можно даже взять $ k>3 $ и аналогично прийти к тому, что $ a^2+3=(k-3)(3ms-1) $. $ s $ - четное, потому правая часть имеет простой делитель вида $ 6r-1 $, а $ (-3) $ не является по нему вычетом.
А вот еще понизить планку до $ k>2 $ что-то не получается. Было бы хорошо одним махом отсеять все нетривиальные случаи...

Я так понимаю тут используется квадратичный закон взаимности, а без него задачу можно решить?