ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65189
Темы:    [ Арифметика остатков (прочее) ]
[ Доказательство от противного ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

Автор: Креков Д.

Будем называть натуральное число почти квадратом, если это либо точный квадрат, либо точный квадрат, умноженный на простое число.
Могут ли 8 почти квадратов идти подряд?


Решение

  Пусть такие числа нашлись.

  Первый способ. Cреди восьми последовательных натуральных чисел найдутся числа, дающие остатки 2 и 6 при делении на 8. Они делятся на 2, но не делятся на 4, так что они обязаны иметь вид 2k² и 2m². Тогда  2k² – 2m² = 4,  то есть  k² – m² = 2,  что невозможно. Противоречие.

  Второй способ. Снова рассмотрим число n, дающее остаток 6 при делении на 8. Тогда  n = 8k + 6 = 2m², то есть  m² = 4k + 3. Но квадрат целого числа не может давать остаток 3 при делении на 4.


Ответ

Не могут.

Замечания

1. Пять почти квадратов подряд идти могут, например,  (1, 2, 3, 4, 5).  Более того, в первом миллионе чисел таких последовательностей из пяти почти квадратов ровно 4:  (1, 2, 3, 4, 5),  (16, 17, 18, 19, 20);  (97, 98, 99, 100, 101)  и  (241, 242, 243, 244, 245).  Автору задачи неизвестно, могут ли идти подряд шесть или семь почти квадратов.

2. Можно показать, что почти квадраты не могут давать остатки 6, 10, 15, 21, 22, 24, 30, 33 и 34 при делении на 36. Таким образом, если найдётся 7 подряд идущих почти квадратов, то они могут давать только остатки –1, 0, 1, ..., 5 при делении на 36. Те среди них, что дают остатки 2 и 3, могут быть только лишь вида 2x² и 3y² соответственно, таким образом, семерка подряд идущих почти квадратов даёт решение уравнения  3y² – 2x² = 1,  которое сводится к уравнению Пелля. Более того, ни одно из наших чисел 2x² и 3y² не делится на 5. Действительно, если какое-то из них делится на 5, то второе имеет вид  5k ± 1,  что невозможно для чисел вида 2x² и 3y². Значит, это два подряд идущих ненулевых остатка по модулю 5. Но 2 и 3 – квадратичные невычеты по модулю 5, а 1 и 4 – вычеты, значит, 2x² и 3y² тоже невычеты и они идут подряд. Итак, это в точности 2 и 3 по модулю 5. Отсюда получаем, что то число, кратное 36, среди найденной семерки почти квадратов делится еще и на 5, значит, то, сравнимо с 5 (mod 36), тоже делится на 5 и одно из этих двух кратных пяти чисел не делится на 25, а следовательно, имеет вид 5z². Таким образом, существование семи идущих подряд почти квадратов влечет за собой решение системы уравнений, сводящихся к уравнениям Пелля, а именно  3y² – 2x² = 1  и
5z² – 2x² = 3  или –2.  Отметим, что у одной из этих систем (где  5z² – 2x² = 3) – есть решения, например,  (1, 1, 1)  или  (11, 9, 7).

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Год 2015
Номер 78
класс
Класс 8
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .