При каком наименьшем натуральном n>1 верно утверждение: из любых n натуральных чисел можно выбрать два, разность квадратов которых делится на 399?

задан 30 Май '17 15:38

10|600 символов нужно символов осталось
1

Разложим число на множители: $%399=3\cdot7\cdot19$%. При делении на 3 квадрат целого числа может давать в остатке два значения: 0 и 1. При делении на 7 получается четыре значения: 0, 1, 2, 4. При делении на 19 значений получится десять. Их можно все выписать явно, а можно заметить, что при делении квадрата на нечётное простое $%p$% возможно в точности $%\frac{p+1}2$% значений. Это 0, а также половина из значений ненулевых остатков, получаемых при возведении в квадрат чисел от 1 до $%\frac{p-1}2$%. Легко проверяется, что там все остатки разные.

Осталось заметить, что если мы загадаем тройку возможных остатков $%(x,y,z)$% от деления квадрата числа на 3, 7, 19 соответственно, то по китайской теореме об остатках существует число, которое именно эти остатки и даёт. Правда, наше число должно быть квадратом целого, поэтому рассматривать надо остатки от деления до возведения в квадрат, а не после. Троек у нас имеется $%2\cdot4\cdot10=80$%, поэтому квадраты целых чисел при делении на 399 могут давать ровно 80 различных значений. Это значит, что при $%n=80$% можно построить пример, когда никакая разность квадратов не будет делиться на 399, а при $%n=81$% уже будет -- по принципу Дирихле.

ссылка

отвечен 30 Май '17 15:59

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×108

задан
30 Май '17 15:38

показан
247 раз

обновлен
30 Май '17 15:59

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru