2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Полные квадраты
Сообщение18.04.2015, 19:54 


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

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

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение18.04.2015, 22:30 
Заслуженный участник


09/02/06
4382
Москва
Для школьников такую задачу нельзя давать.
Надо заметить, что член $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$. Из теории эллиптических кривых можно показать отсутствие целых решений.

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 00:33 


18/04/15
38
Руст в сообщении #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 $. Противоречие :D
А вообще интересно, могут ли быть здесь идеи, которые приводят к этим результатам проще и быстрее, на уровне школьных знаний.

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 10:08 
Заслуженный участник


09/02/06
4382
Москва
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}$.

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 10:24 
Заслуженный участник


20/12/10
8858
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 $. Противоречие :D
А вообще интересно, могут ли быть здесь идеи, которые приводят к этим результатам проще и быстрее, на уровне школьных знаний.
Вот этот кусок можно изложить попроще.

Одно из чисел $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}$, то этот показатель должен быть равен единице. Но таких решений нет.

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

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 16:31 


18/04/15
38
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}$, то этот показатель должен быть равен единице. Но таких решений нет.

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

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 17:54 


03/03/12
1380
lopkityu в сообщении #1005449 писал(а):
$ n+2 $ - четное.

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

-- 19.04.2015, 19:05 --

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

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 18:07 


18/04/15
38
TR63 в сообщении #1005607 писал(а):
Почему только чётное?

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

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 19:30 
Заслуженный участник


17/09/10
2132
nnosipov в сообщении #1005520 писал(а):
Интересно было бы узнать, почему задачи такого уровня всё же предлагаются.

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

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 19:40 
Заслуженный участник


20/12/10
8858
lopkityu в сообщении #1005587 писал(а):
Хех, что-то я перемудрил с выкладками...
Я там тоже слегка ошибся (со степенями двойки погорячился), но это легко поправить.
scwec в сообщении #1005646 писал(а):
Кстати, в разобранной здесь задаче случай $k=4$ относится к области эллиптических кривых,
Относится, но ... Там ведь будет уравнение вида $n^4+\ldots=q^2$, которое легко решается "зажиманием" между двумя квадратами.

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 19:49 
Заслуженный участник


17/09/10
2132
nnosipov в сообщении #1005653 писал(а):
Там ведь будет уравнение вида $n^4+\ldots=q^2$, которое легко решается "зажиманием" между двумя квадратами

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

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение19.04.2015, 21:03 


26/08/11
2057
Для $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
нашел более простое решение. Но из той же оперы - довольно нетривиалное для доказательства утверждение, непосильное для школьника.

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

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение21.04.2015, 23:18 


24/12/13
351
Пусть $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$ точно такое же противоречие выходит. ?

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение22.04.2015, 00:31 


18/04/15
38
rightways
Вот оно! Это именно то, что я искал :D

rightways в сообщении #1006595 писал(а):
При $k=4$ точно такое же противоречие выходит. ?

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

 Профиль  
                  
 
 Re: Полные квадраты
Сообщение23.04.2015, 08:33 


05/10/10
71
lopkityu в сообщении #1006622 писал(а):
rightways
Вот оно! Это именно то, что я искал :D

rightways в сообщении #1006595 писал(а):
При $k=4$ точно такое же противоречие выходит. ?

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group