Задача с натуральными числами

[maxandreev]

Добрый день. Подскажите, пожалуйста, идею решения такой задачи.
Не очень понятно, с чего начать...

[Hottabych]

Source of the post
Добрый день. Подскажите, пожалуйста, идею решения такой задачи.
Не очень понятно, с чего начать...

Надо посчитать число квадратичных вычетов по модулю 561 и воспользоваться принципом Дирихле.

[vicvolf]

Разность квадратов двух чисел равна произведению их суммы на разность. Минимальным натуральным числом, при котором среди n натуральных чисел найдутся два, сумма которых делится на 581 будет 281 (280+281=581). При n<281 таких двух натуральных чисел нет.

[астрон]

Source of the post
Разность квадратов двух чисел равна произведению их суммы на разность. Минимальным натуральным числом, при котором среди n натуральных чисел найдутся два, сумма которых делится на 581 будет 281 (280+281=581). При n<281 таких двух натуральных чисел нет.

а как доказать, что при n=281 условие задачи выполняется (если например брать пятое по счёту нат. число начиная с 19, или ещё как-нибудь произвольно выбирать 281-о натуральное число)?

[vicvolf]

Source of the post
а как доказать, что при n=281 условие задачи выполняется (если например брать пятое по счёту нат. число начиная с 19, или ещё как-нибудь произвольно выбирать 281-о натуральное число)?

Не требуется для любого n, а требуется найти пару чмсел среди n. В данном случае пара 280 и 281

[астрон]

Не требуется для любого n, а требуется найти пару чмсел среди n

.. среди "любого набора" n(281) натуральных чисел, т.е. числа 281 там может и не оказаться

[bas0514]

Source of the post
Разность квадратов двух чисел равна произведению их суммы на разность. Минимальным натуральным числом, при котором среди n натуральных чисел найдутся два, сумма которых делится на 581 ...

В условии 561.
Почему сумма должна делиться на 561? Это число не простое. Например, сумма может делиться на 51, а разность на 11.

[астрон]

наименьшая пара натуральных чисел, разность квадратов которых делится на 561, будет пара 31 и 20. Из этого можно сделать вывод, что искомое число n не меньше 31

[астрон]

и вообще, для произвольного набора n натуральных чисел, задача решения не имеет, потому что, числу в качестве пары нужно сопоставить число $$è=\frac {51k-11} {2}$$, которого в произвольном наборе чисел может не оказаться

[VAL]

Идею изложил Hottabych.
Чуть подробнее так:
Если - нечетное простое число, то по модулю , очевидно, будет квадратов.
Если , то число является квадратом по модулю тогда и только тогда, когда оно будет квадратом по модулям и .

Поэтому 109 чисел за глаза хватит.