Тема Остатки и сравнения по модулю

Базовый аппарат сравнений по модулю

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела остатки и сравнения по модулю

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 41#99588Максимум баллов за задание: 7

Для зашифрования осмысленного слова его буквы заменили числами $x ,x ,...,x 1 2 n$ по таблице.

Затем выбирали четные натуральные числа $p$ и $q$ и для каждого числа $xi$ из соотношений

xi = yi+ pzi,zi =yi+ qxi

нашли целые числа $yi$ и $zi$ .

Потом по формулам

′ zi = r32(zi),i= 1,...,n

получили числа

z′,...,z′ 1 n

(где $r32(a)$ — остаток от деления числа $a$ на 32), которые вновь заменили буквами согласно таблице:

$|---|---|---|---|----|---|----|---|---|---|----|---|----|---|---|---|----|---|---|----|---|---|---|----|----|---|----|---|---|----|----| |А--|Б--|-В-|-Г-|-Д--|Е--|Ж---|З--|И--|-К-|-Л--|М--|-Н--|О--|-П-|-Р-|-C--|Т--|У--|-Ф--|Х--|Ц--|-Ч-|-Ш--|-Щ--|-Б-|-Ы--|-Б-|-Э-|-Ю--|-Я--| |0 | 1 | 2 | 3 | 4 |5 | 6 |7 | 8 | 9 | 10 |11 | 12 |13 |14 | 15 | 16 |17 |18 | 19 |20 |21 | 22 | 23 | 24 | 25 | 26 |27 | 28 | 29 | 30 | ----------------------------------------------------------------------------------------------------------------------------------------$

В результате получили вот что: ЖЯЮЦКР.

Найдите исходное слово, если известно, что оно начинается на букву В.

Источники: Верченко - 2021, 11.5 (см. v-olymp.ru)

Подсказки к задаче

Подсказка 1

Нам надо явным образом связать x и z’ по модулю 32. Давайте тогда вычтем из первого равенство второе, чтобы у нас лишняя переменная y ушла. Тогда как можно связать x и z’?

Подсказка 2

Тогда выходит, что x(1 + q) = z’(1 + p) (mod 32). Если мы выразим (1 + q) через (1 + p) по модулю 32 с некоторыми константными коэффициентами, то мы сможем домножить на это модульное равенство наше равенство выше и после сокращения (1 + q) и (1 + p) в обеих частях мы получим явную связь x и z’. Стоит вспомнить, что мы ещё не использовали условие на первую букву!

Подсказка 3

Давайте теперь возьмем условие для первой буквы и посмотрим, что оно дает. Получается, что (1 + q) = 3(1 + p) (mod 16). Помножим на 3^-1 mod 16, и получим некоторое равенство, где коэффициент теперь у (1 + q). Тогда выходит, что c(1 + q) = (1 + p) (mod 32), где c = 11 или 27. А значит, получили явную связь на x и z’. Осталось проверить дешифровку на осмысленность и задача решена!

Показать ответ и решение

Рассмотрим произвольную букву открытого и шифрованного текстов. Для соответствующих им (по таблице) чисел $x$ и $z′$ выполняются равенства $x= y+ pz$ и $z =$ $y+ qx$ , при некотором $y,p$ и $q$ . При этом по условию $′ z= r32(z)$ . Используя свойство сравнений по модулю целого числа, получим: $′ ′ x − z = pz− qx(mod32)$ или $x(1+ q)=$ $′ z(1+p)(mod32)$ . Для дальнейшего решения будем пользоваться следующим свойством: если наибольший общий делитель чисел $a$ и $n$ равен $1,$ то сравнение $x= y(modn )$ равносильно $ax=$ $ay(modn)$ . Используя условие задачи для первой буквы открытого и шифрованного текста, получим равенство $2(1+q)= 6(1 +p)(mod32)$ . Заметим, что сравнение $6t= 2(mod32)$ имеет 2 решения по модулю $32:t= 11(mod32)$ , $t= 27(mod32)$ . Тогда получим, что $11⋅(1+q)= (1+p)(mod32)$ или $27⋅(1+ q)= (1+ p)(mod32)$ для каждого $t$ . Таким образом, $′ x =11z(mod32)$ или $′ x =27z(mod32)$ соответственно. Остается воспользоваться полученными соотношениями для остальных букв.

Осмысленное слово получается только при втором варианте. А значит, исходное слово ВЕКТОР.

Ответ:

ВЕКТОР

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 42#42220Максимум баллов за задание: 7

Имеется дробь $1 3$ . Каждую секунду к её числителю прибавляется $1$ , а к знаменателю прибавляется $7$ . Восточное поверье гласит: в тот момент, когда получится дробь, сократимая на $11$ , наступит конец света. Докажите, что не следует бояться наступления конца света.

Источники: Муницип - 2020, Владимирская область, 9.2

Подсказки к задаче

Подсказка 1

Давайте посмотрим, как наша дробь изменяется со временем. Пусть прошло n секунд, тогда чему будет равен числитель и чему будет равен знаменатель дроби?

Подсказка 2

Верно, числитель равен n+1, а знаменатель равен 7n+3. Если дробь сократима на 11, то её числитель и знаменатель делятся на 11, из условия задачи можно понять, что конец света не наступит, а значит не бывает так, что они оба делятся на 11. Как-то тяжело перебирать все n и проверять условия на делимость, не могли бы как-то избавиться от n?

Подсказка 3

Действительно, если A делится на 11 и B делится на 11, то их разность тоже будет делиться на 11, остаётся только применить этот факт и радоваться противоречию!

Показать доказательство

Через $n$ секунд дробь будет иметь вид $1+n- 3+7n$ . Предположим, что она сократима на $11$ , т.е. числа $a= 1+ n$ и $b= 3+ 7n$ делятся на $11$ . Но тогда и число $7a− b$ тоже должно делиться на $11$ , что неверно, так как $7a− b =4$ .

Ошибка.
Попробуйте повторить позже

Задача 43#42221Максимум баллов за задание: 7

Сумма квадратов $n$ простых чисел, каждое из которых больше $5,$ делится на $6$ . Докажите, что и $n$ делится на $6.$

Источники: Муницип - 2020, Калининград, 9.2

Подсказки к задаче

Подсказка 1

Часто в задачах на делимости полезно переходить от чисел к их остаткам. Давайте попробуем понять, какие остатки могут быть у простого числа по модулю 6?

Подсказка 2

Верно, это 1 и 5, иначе наше простое число было бы не таким простым и делилось бы на 2 или на 3. А какие тогда остатки дают квадраты простых чисел по модулю 6?

Подсказка 3

Да, только 1, получается мы каждое из наших n чисел можем заменить на 1, какая тогда получится сумма и что мы про неё знаем?

Показать доказательство

Если сумма нескольких чисел делится на шесть, то и сумма их остатков при делении на шесть тоже будет делится на 6. Простое число, большее пяти, может иметь при делении на 6 только остатки 1 или 5 (иначе это число будет делиться на 2 или 3). Следовательно, квадрат любого простого числа, большего 5, имеет при делении на 6 остаток $1.$ Так как сумма этих остатков равна количеству чисел $n$ , значит $n$ делится на $6.$

Ошибка.
Попробуйте повторить позже

Задача 44#123420Максимум баллов за задание: 7

Юлианский календарь устроен так: каждый год с номером, кратным $4$ — високосный; в обычном году $365$ дней, а в високосном — на $1$ больше; кроме этого, есть семидневная неделя. В результате существуют $14$ видов года: невисокосный год, начинающийся в понедельник, во вторник, . . ., в воскресенье; високосный год, начинающийся в понедельник, во вторник, . . ., в воскресенье.

Когда земляне поселились на планете Ялмез, то ввели календарь, в котором каждый год с номером, кратным $v(v > 1)$ — високосный; в обычном году $x$ дней, а в високосном — на $1$ больше; неделя по-прежнему состоит из $7$ дней. Оказалось, что в таком календаре ровно $n$ видов года. Найдите все возможные значения $n.$

Источники: ФЕ - 2020, 11.2 (см. www.formulo.org)

Подсказки к задаче

Подсказка 1

Сосредоточьтесь на остатках при делении длины года на 7. Обычный год дает остаток х, високосный — х+1. Как это влияет на день начала следующего года? Есть ощущение, что именно остаток определяет, на какой день недели сдвинется начало следующего года

Подсказка 2

Рассмотрите полный цикл из v лет. Суммарный сдвиг составит vx+1 дней. Что происходит, когда это число кратно 7? А когда не кратно?

Подсказка 3

Если сдвиг не кратен 7, за v лет пройдут все возможные варианты начала года. Как это влияет на общее количество типов годов?

Показать ответ и решение

Лемма. Если $a$ не кратно $7,$ то среди чисел

m,m + a,m + 2a,...,m +6a

встречаются числа со всеми остатками от деления на $7.$

Если это не так, то какие-то два из семи остатков совпадают, но разность между соответствующими числами равна $ka,$ где $0< k< 7,$ а $a$ взаимно просто с $7,$ то есть не кратна $7.)$

Заметим, что нас интересует не сама длина года, а только её остаток от деления на $7,$ который далее и будем обозначать (для обычного года) $x.$ Ежегодно номер начального дня недели сдвигается на $x$ для обычного года и на $x +1$ для високосного. Например, если на планете Земля $2019$ год обычный и начинался во вторник, т. е. в день $2,$ то $2020$ год начинается в день $2+ 1= 3$ (где $1$ — остаток от деления $365$ на $7),$ а $2021$ — в день $3+2 =5$ (где $2$ — остаток от деления $366$ на $7).$

Тогда за $v$ лет номер начального дня сдвигается на $vx +1$ (например, для Земли на $5$ ). Если $vx +1$ не кратно $7,$ то встречаются все $7$ типов високосных лет (см. лемму); но тогда все годы перед ними («предвисокосные») тоже различаются, итого имеем все $14$ типов лет. Если $vx+1$ кратно $7,$ то последовательные високосные годы всё время одинаковы. Примеры (указаны длины лет по модулю $7):$

$pict$

Получить ровно $7$ типов лет невозможно: если в цикле $6$ обычных лет и один високосный (то есть $v =7),$ то число дней в цикле $6x+ (x+1)$ не кратно $7;$ если в цикле больше $6$ обычных лет и длина каждого из них не кратна $7,$ то все $7$ типов обычных лет встречаются; если длина бычного года кратна $7,$ то длина цикла не кратна $7.$

Ответ:

$2,3,4,5,6,8,14$

Ошибка.
Попробуйте повторить позже

Задача 45#41759Максимум баллов за задание: 7

Назовем натуральное число $n$ новогодним, если число $n12+ 2018$ делится на $2019.$ Докажите, что среди чисел $1,2,...,2018$ чётное число новогодних чисел.

Источники: Муницип - 2019, Смоленская область, 11.2

Подсказки к задаче

Подсказка 1

Если мы сразу не можем понять, почему требуемое выполнено и у нас есть некоторая сумма/последовательность , то можно попытаться красиво разбить на пары и посмотреть, как связаны два этих элемента. К тому же в задаче, где просят доказать что-то про четность кол-ва элементов с нужным свойством, зачастую требуется каждому числу, которое удовлетворяет условию сопоставить число, которое также удовлетворяет ему. Что и предлагаю вам сделать!

Подсказка 2

Верно, мы можем разбить опять на пары вида k и 2019 - k. Основной наш вопрос в этой задаче - остаток по модулю 2019. Чему он равен у 2019 - k?

Подсказка 3

Конечно, он равен (2019 - k) ^ 12 = k ^ 12(mod 2019), так как все остальные члены при разложении через бином Ньютона, будут кратны 2019. А значит, если число k подходило, то и число 2019 - k подойдет. Значит, таких чисел четное количество.

Показать доказательство

Разобьём все числа $1,2,...,2018$ на пары вида $k$ и $2019− k.$ Найдём остаток от деления числа $(2019− k)12+2018$ на $2019,$ получим:

(2019− k)12+ 2018 = 12 11 11 12 =2019 + 12⋅2019 ⋅(− k)+ ...+ 12⋅2019⋅(−k) + (−k) + 2018 ≡ ≡(−k)12 +2018= k12+ 2018 (mod 2019)

Таким образом, остатки от деления на $2019$ в каждой паре совпадают. Значит, количество новогодних чисел чётно.

Ошибка.
Попробуйте повторить позже

Задача 46#95652Максимум баллов за задание: 7

Вася задумал натуральное число, меньшее $200.$ Он посчитал остатки при делении этого числа на $2,4,6,8,10,12$ и сложил их. У него получилось $36.$ Какое число мог задумать Вася?

Источники: Лига открытий - 2018

Показать ответ и решение

Заметим, что у Васи получилась максимально возможная сумма остатков: $1+3+ 5+ 7+ 9+11 =36.$ Значит, число дает в точности эти остатки, таким образом, при прибавлении $1$ делится на каждое из данных чисел. HOK всех шести чисел равняется $120,$ откуда и следует ответ.

Ответ:

$120$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 47#46229Максимум баллов за задание: 7

Целые числа $2a2$ и $3a$ имеют одинаковые остатки при делении на $18$ . Какие ненулевые остатки может иметь число $a> 0$ при делении на $18$ ?

Источники: Росатом-17, 11.3 (см. rsr-olymp.ru)

Подсказки к задаче

Подсказка 1!

Попробуем рассмотреть некоторый модуль, например, 3! Посмотрите, чему равны остатки наших чисел по модулю три.

Подсказка 2!

Да, 0! У 3а точно ноль, а так как его остаток при делении на 18 тоже делится на 3, то и у 2а^2 тоже!

Подсказка 3!

Вспомните, что если число делится на 3, то его квадрат - делится на 9!

Показать ответ и решение

По условию $2a2− 3a$ делится на $18$ , значит, и на $3$ . Так как $3a$ делится на $3$ , то и $2a2$ делится на $3$ . Так как $2$ и $3$ взаимнопросты, то $2 a$ делится на $3$ , значит, и на $9$ , причём $a$ делится на $3$ .

По условию $2 2a − 3a$ делится на $18$ , значит, и на $2$ . Так как $2 2a$ делится на $2$ , то и $3a$ делится на $2$ . Так как $3$ и $2$ взаимнопросты, то $a$ делится на $2$ .

В итоге $a$ должно делиться на $6$ . Ненулевые остатки по модулю $18$ могут быть только $6$ или $12$ .

Если $a ≡186$ , то $2 2a ≡18 0 ≡183a.$

Если $a ≡1812 ≡18−6$ , то аналогично.

Ответ:

$6$ и $12$

Ошибка.
Попробуйте повторить позже

Задача 48#39354Максимум баллов за задание: 7

Делится ли $132013+ 132014+132015$ на $61$ ?

В ответ внесите “да” или “нет”.

Источники: Школьный этап - 2016, Москва, 11.2

Подсказки к задаче

Подсказка 1

Видим, что в нашей сумме везде в основании число 13. Что тогда хочется сделать? Как можно упростить выражение?

Подсказка 2

Верно, давайте вынесем 13 в наибольшей степени за скобку, как общий множитель. А в оставшейся скобке будет число 183. Но тогда какое условие для делимости должно выполняться?

Подсказка 3

Верно, нужно проверить делится ли 183 на 61, так как 13 и 61 взаимно просты. Осталось только разложить 183 на множители и победа!

Показать ответ и решение

Преобразуем данную сумму:

2013 2014 2015 2013 2013 2013 13 +13 + 13 =13 ⋅(1+13+ 169) =13 ⋅183= 13 ⋅61⋅3.

Теперь очевидно, что данная сумма делится на $61$ .

Ответ: да

Ошибка.
Попробуйте повторить позже

Задача 49#62510Максимум баллов за задание: 7

Найдите количество натуральных чисел $k$ , не превосходящих $242400$ и таких, что $k2+ 2k$ делится нацело на $303.$

Источники: Физтех-2015, 11.3 (см. olymp.mipt.ru)

Подсказки к задаче

Подсказка 1.

Давайте внимательно посмотрим на число 303. Действительно оно представимо как 3 * 101. Получается либо k делится на 101, либо k + 2 делится на 101. Для решения задачи надо рассмотреть оба случая!!!

Подсказка 2.

Пусть k делится на 101, пусть тогда k = 101*p, p ∈ ℕ. C учётом кратности 3 получаем, что k = 303 * n или k = 303 * n + 202. Случай когда на 101 делится k + 2 разбирается аналогично.

Подсказка 3.

Несложными путями получаем, что из каждых 303 подряд идущих чисел подходят ровно 4. А теперь посмотрим внимательно на ограничение из условия задачи. Действительно, 242400 = 303 * 800, а значит мы легко посчитаем сколько чисел нам подходят!!!

Показать ответ и решение

Поскольку $k2+2k =k(k+ 2)$ и $303= 3⋅101$ , то одно из чисел $k$ , $k+ 2$ делится на $101$ . Рассмотрим случаи

$k$ кратно $101$ . Тогда $k= 101p =⇒ 101p(101p+ 2)$ делится на $3$ . Отсюда $p= 3n,p= 3n +2$ . В итоге получаем случаи $k =303n,k = 303n+ 202$ .
$k +2$ кратно $101$ , откуда $k= 101p+ 99$ , откуда $101(p+ 1)(101p+ 99)$ кратно 3. Снова получаем два случая $p =3n,p= 3n+ 2$ , откуда $k= 303n +99,k= 303n +301$ .

Итак, нам подходят остатки $0,99,202,301$ при делении $k$ на $303,$ откуда среди любых $303$ подряд идущих чисел нам подойдут ровно $4$ . Поскольку $242400= 303⋅800$ , то получаем $4 ⋅800= 3200$ подходящих чисел.

Ответ:

3200

Ошибка.
Попробуйте повторить позже

Задача 50#49158Максимум баллов за задание: 7

Положительное целое число $x$ при делении на $7$ имеет остаток $2,$ а его квадрат $x2$ при делении на $49$ имеет в остатке $39.$ Сколько таких чисел находится на отрезке $[100;1000]$ ?

Источники: Росатом-14, 11.4 (см. rsr-olymp.ru)

Подсказки к задаче

Подсказка 1

Если число дает остаток 2 по модулю 7, то какой остаток оно может давать по модулю 49?

Подсказка 2

Да, только остатки 2,9,16,23,30,37,44. Но при этом у нас есть условие и про квадрат этого числа. Все ли остатки из списка выше подходят под условие?

Подсказка 3

Нет, под условие подходит только остаток 23, а это значит, что чтобы записать ответ, осталось лишь найти все числа х=23(mod49) !

Показать ответ и решение

Числа, дающие по модулю $7$ остаток $2$ , могут давать по модулю $49$ только остатки $2,9,16,23,30,37,44$ . При возведении этого остатка в квадрат должно получиться $39$ по модулю $49$ — этому условию удовлетворяет только остаток $23$ . Отсюда нам подходят те и только те числа, которые дают остаток $23$ по модулю $49$ . Это числа $121,170,...954$ , которых $18$ штук.

Ответ:

$18$

Ошибка.
Попробуйте повторить позже

Задача 51#31287Максимум баллов за задание: 7

В группу из 17 детей присланы подарки двух видов: каждый подарок первого вида содержит 4 пряника и 9 конфет, а второго — 3 пряника и 11 конфет. Объединив эти подарки, все пряники разделили между детьми поровну. Могло ли случиться при этом, что конфеты разделить поровну не удалось?

Источники: Ломоносов-2012, 11.3 (см. olymp.msu.ru)

Подсказки к задаче

Подсказка 1

Пусть подарков первого типа a, а второго типа - b. Тогда пряников всего 4a + 3b, а конфет - 9a + 11b. И мы также знаем, что все пряники можно распределить на 17 детей. Что это значит на языке остатков?

Подсказка 2

Это означает, что 4a+3b = 0 по модулю 17. Попробуем выразить a через b по модулю 17: 4a = -3b (mod 17). Вот на что теперь можно умножить это выражение, чтобы слева вышло просто a?

Подсказка 3

Можно на -4) Получится -16a = 12b (mod 17), что равносильно a = 12b (mod 17). Теперь осталось подставить это равенство в выражение 9a+11b и найти его по модулю 17)

Показать ответ и решение

Пусть подарков первого вида $x$ , а второго — $y$ , тогда $a =4x+ 3y$ кратно 17, а спрашивают нас про $b=9x +11y$ . Заметим, что $2a+ b= 17(x+ y)$ , то есть $2a+ b ≡170=⇒ b ≡170$ , так что такого случиться не может.

_________________________________________________________________________________________________________________________________________________________________________________

Интересный факт. Задача придумывалась на основе факта, что определитель матрицы

( ) 4 9 3 11

равен $17$ . По условию эта матрица умножается на целочисленный вектор ( $x$ , $y$ ) и получается ( $17m$ , $n$ ), откуда из целочисленности $x$ сразу следует, что $11⋅17n − 3⋅m$ делится на 17.

Ответ:

нет

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 52#89286Максимум баллов за задание: 7

Найдите все пары взаимно простых натуральных чисел $a$ и $b$ такие, что $a2+3b2$ делится на $a+ 3b$ .

Подсказки к задаче

Подсказка 1

Давайте найдём какое-нибудь выражение, которое точно делится на (a + 3b) и может быть нам полезно в данной задаче. Нам отлично подойдёт a² + 3ab. И правда! Выражение a² + 3b² - a² - 3ab легко сворачивается в 3b(b - a), а также оно должно делиться на (a + 3b).

Подсказка 2

С помощью алгоритма Евклида легко доказать, что (b, a+3b) = 1 ≥ 3*(b - a) делится на (a + 3b). Теперь необходимо сравнить между собой a и b и рассмотреть разные случаи

Подсказка 3

Если a = b, то с учётом взаимной простоты двух чисел, этот случай очевиден. Если же b > a, то решений также не будет по понятным причинам. Остаётся единственный содержательный случай — a > b.

Показать ответ и решение

Заметим, что $a2+3ab$ делится на $a+ 3b$ тогда

2 2 2 3b(b− a)= a +3b − a − 3ab

(добавили и вычли $a2$ ) делится на $a+ 3b,$ так как $(b,a)= 1,$ тогда $(b,a+3b)= 1,$ то есть $3(b− a)$ делится на $a+ 3b.$

Если $b> a,$ то

3(b− a)<3b< 3b+a

при этом они все больше $0,$ откуда следует противоречие.

Если $b= a,$ то это может быть только при $a= b= 1$ иначе $(a,b) >1.$

Если $a> b,$ то так как $3(a− b)$ делится на $a+ 3b,$ то $3(a− b)= k⋅(a+ 3b),$ где $k≤ 2,$ иначе будет противоречие.

Разберем $2$ случая.

(a) Если $k= 1,$ тогда $2a =6b,$ то есть $a= 3b.$ Если $b⁄=1,$ то возникает противоречие с взаимной простотой, значит, $a =3,b= 1.$

(b) Если $k= 2,$ тогда $a= 9b.$ Если $b⁄= 1,$ то возникает противоречие с взаимной простотой, значит, $a= 9,b= 1.$

Итого получили следующие пары ${a,b} :{1,1},{3,1},{9,1}$

Ответ: {1,1}, {3,1}, {9,1}

Ошибка.
Попробуйте повторить позже

Задача 53#116007Максимум баллов за задание: 7

Найдите все такие значения $n$ , что среди любого набора из $n$ натуральных чисел, являющихся точными квадратами, всегда найдутся два числа, разность которых делится на $2017.$

Подсказки к задаче

Подсказка 1

Подумайте, а что означает тот факт, что два квадрата нам подходят?

Подсказка 2

Нужно, чтобы либо сумма, либо разность двух чисел делилась на 2017.

Подсказка 3

Рассмотрите остатки по модулю 2017. Что если разбить их на пары?

Подсказка 4

Разбейте все остатки по модулю 2017 на пары подходящих и посмотрите, куда и как могут попасть выбранные нами числа ;)

Показать ответ и решение

Пусть $a2$ и $b2$ — точные квадраты натуральных чисел $a$ и $b.$ Так как 2017 является простым числом, то разность $2 2 a − b = (a− b)(a+ b)$ делится на 2017 тогда и только тогда, когда разность или сумма чисел $a$ и $b$ делится на 2017, то есть у этих чисел равные или противоположные по знаку вычеты по модулю 2017.

Всего существует 2017 остатков при делении на 2017, при этом 2016 ненулевых из них разбиваются на 1008 пар, дающих в сумме 2017:

1,2016; 2,2015; ...; 1008,1009

Поэтому если $n ≥1010,$ то для любого набора натуральных чисел, являющихся точными квадратами, по принципу Дирихле можно найти равные или противоположные по модулю 2017 остатки.

Если же $n ≤1009,$ то существует набор натуральных чисел, точные квадраты которых имеют при делении на 2017 остатки $0,...,n − 1.$ Так что в этом наборе не найдутся два элемента, разность квадратов которых делится на 2017.

Ответ:

$n ≥1010$

Ошибка.
Попробуйте повторить позже

Задача 54#77981Максимум баллов за задание: 7

Школьник в течение учебного года (который длится не менее $100$ дней) ежедневно получал одну оценку: $3,4$ или $5.$ Ни в какой из дней сумма его оценок (т. е. сумма всех оценок, которые он получил от начала года и до текущего дня) не делилась на $3.$ Докажите, что за год среди всех его оценок было не больше $60%$ четверок.

Подсказки к задаче

Подсказка 1

Задача явно на делимость, но конкретных чисел нет, признаки не очень-то помогут здесь. С чем в таком случае хочется поработать?

Подсказка 2

Конечно же посмотрим на остатки! И на искомые четвёрки: сколько 4 могут идти подряд, чтобы выполнялось условие на сумму оценок?

Подсказка 3

Тогда сколько четвёрок может быть, относительно общего числа отметок? И будьте внимательны: условие про 100 дней здесь не зря дано (посмотрите отдельно на начало последовательности оценок)!

Показать доказательство

Если сумма оценок школьника не делится на $3,$ то следующие две оценки не могут быть четверками. Действительно, если сумма дает остаток $1$ при делении на $3,$ то получение двух четверок увеличит ее на $8$ и результат будет делиться на $3.$ Если же сумма дает остаток $2$ при делении на $3,$ то прибавление к ней $4$ сразу даст число, делящееся на $3.$

Таким образом, среди оценок, полученных школьником, нет двух четверок подряд (кроме самых первых оценок — первые две оценки как раз могут быть четверками; проведенное нами рассуждение не может быть использовано для первого дня учебного года, когда никаких оценок еще нет и поэтому их сумма равна $0,$ т. е. делится на $3$ ). Поэтому четверки составляют практически не более половины (более точно — не более половины всех оценок плюс $1$ ). Так как учебный год весьма продолжителен, количество четверок не может быть равно $60%.$

Ошибка.
Попробуйте повторить позже

Задача 55#127241Максимум баллов за задание: 7

Из Южной Америки в Россию $2010$ кораблей везут бананы, лимоны и ананасы. Число бананов на каждом корабле равно числу лимонов на остальных кораблях вместе взятых, а число лимонов на каждом корабле равно числу ананасов на остальных кораблях вместе взятых. Докажите, что общее число фруктов делится на $31.$

Источники: Тургор - 2010 (см. turgor.ru)

Показать доказательство

Обозначим за $Б , i$ $Л i$ и $А i$ — соответственно количество бананов, лимонов и ананасов на $i−$ том корабле, а за $Б,$ $Л$ и $А$ — соответственно общее количество бананов, лимонов и ананасов. Так как число бананов на каждом корабле равно числу лимонов на остальных кораблях вместе взятых, получаем систему уравнений:

(| |||{ Б1 =Л2 +Л3 +...+Л2010 | Б2 =Л1 +Л2 +...+Л2010 |||( ... Б2010 =Л1 +Л2 +...+ Л2009

Складывая все эти уравнения, получаем

Б= 2009Л

Так как число лимонов на каждом корабле равно числу ананасов на остальных кораблях вместе взятых, получаем систему уравнений:

( ||| Л1 =А2 +А3 +...+А2010 |{ Л2 =А1 +А2 +...+А2010 ||| ... |( Л2010 = А1+ А2+ ...+ А2009

Складывая все эти уравнения, получаем

Л= 2009А

Тогда общее количество фруктов

А+ Б+ Л =А + 2009Л+ Л = А+ 2010Л =(2010 ⋅2009+ 1)А

Число 2010 даёт остаток 26 при делении на 31, а число 2009 даёт остаток 25 при делении на 31, тогда $2010⋅2009+ 1$ сравнимо с $26⋅25+ 1= 651$ по модулю 31. Так как 651 кратно 31, $2010⋅2009+ 1$ также делится на 31, таким образом, общее число фруктов кратно 31.

Ошибка.
Попробуйте повторить позже

Задача 56#133199Максимум баллов за задание: 7

Найдите все натуральные $n$ , для которых многочлен $x2n+ xn+ 1$ делится на многочлен $x2+ x+ 1.$

Показать ответ и решение

Заметим, что $x3 ≡ 1, x2+x+1$ так как

3 2 x − 1= (x − 1)(x + x+ 1).

Тогда, как легко видеть,

2n n 2r r x + x + 1≡x2+x+1 x + x +1,

где $r =0,1,2$ и $r≡3 n.$ Пусть $r= 0.$ Тогда наш многочлен сравним с 3, и никак не может делиться на $x2+x +1.$

При $r= 1$ имеем

2 x +x+ 1≡x2+x+1 0,

то есть наш многочлен делится на нужный.

При $r= 2$ наш многочлен сравним с

4 2 2 x +x + 1≡x2+x+1 x + x+ 1≡x2+x+1 0,

то есть в этом случае наш многочлен снова делится на нужный. Таким образом, необходимо и достаточно, чтобы $n$ не делилось на 3.

Ответ:

все натуральные $n,$ не делящиеся на 3

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 57#33968Максимум баллов за задание: 7

Докажите, что число $1000⋅1001 ⋅1002⋅1003− 24$ делится

(a) на 999;

(b) на 1004.

Показать ответ и решение

(a) Заменим каждое из чисел 1000, 1001, 1002 и 1003 на сравнимое с ним по модулю 999 число:

1000 ⋅1001⋅1002⋅1003− 24 ≡1⋅2⋅3⋅4− 24≡ 0 (mod 999),

значит, указанное число делится на 999.

(b) Здесь также заменим каждое число на сравнимое с ним по модулю 1004, но на этот раз мы заменим 1000 на $− 4$ , 1001 на $− 3$ , 1002 на $− 2$ , и, наконец, 1003 на $− 1$ : наша цель работать именно с маленькими по абсолютному значению числами. Получим

1000⋅1001 ⋅1002⋅1003− 24≡ (− 1)⋅(−2)⋅(− 3)⋅(−4)− 24 ≡0 (mod 1004),

то есть указанное число делится и на 1004.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 58#83137Максимум баллов за задание: 7

Определение: $a≡ b$ (mod $m$ ) $⇔$ числа $a$ и $b$ дают одинаковые остатки по модулю $m$ .

Докажите свойства сравнений:

1. $a≡ b$ (mod $m$ ), $c≡ d$ (mod $m$ ) $⇒$ $a+ c≡ b+ d$ (mod $m$ ).

2. $a≡ b$ (mod $m$ ), $c≡ d$ (mod $m$ ) $⇒$ $a− c≡ b− d$ (mod $m$ ).

3. $a≡ b$ (mod $m$ ) $⇒$ $ka ≡kb$ (mod $m$ ).

4. $a≡ b$ (mod $m$ ), $c≡ d$ (mod $m$ ) $⇒$ $ac≡ bd$ (mod $m$ ).

5. $a≡ b$ (mod $m$ ) $⇒$ $ak ≡bk$ (mod $m$ ) для любого натурального $k$ .

Показать доказательство

1. Раз $a ≡b$ (mod $m$ ), $c≡ d$ (mod $m$ ), то $a− b$ делится на $m$ и $c− d$ делится на $m$ . Значит их сумма $(a − b)+ (c− d)= (a+ c)− (b+ d)$ тоже делится на $m$ , то есть $a +c≡ b+ d$ (mod $m$ )

2. Аналогично раз $a≡ b$ (mod $m$ ), $c≡ d$ (mod $m$ ), то $a− b$ делится на $m$ и $c− d$ делится на $m$ . Значит их разность $(a− b)− (c− d)= (a− c)− (b− d)$ делится на $m$ , то есть $a− c≡ b− d$ (mod $m$ )

3. Так как $a≡ b$ (mod $m$ ), то $.. a− b. m$ (выражение $.. x . y$ означает, что $x$ делится на $y$ ), значит $.. ka− kb= k(a− b). m$ и $ka≡ kb$ (mod $m$ ).

4. Воспользуемся предыдущем свойством. Так как $a≡ b$ (mod $m$ ), то $ac≡bc$ (mod $m$ ) и так как $c≡ d$ (mod $m$ ), то $bc ≡bd$ (mod $m$ ). Значит у $ac$ и $bc$ одинаковые остатки при делении на $m$ и у $bc$ и $bd$ одинаковые остатки при делении на $m$ , поэтому у $ac$ и $bd$ одинаковые остатки при делении на $m$ и отсюда следует, что $ac ≡bd$ (mod $m$ ).

5. Применяем последнее свойство для $a =c$ и $b= d$ и получим, что $2 2 a ≡ b$ (mod $m$ ). Доказали для $k= 2$ . Теперь опять применим последнее свойство для $2 c= a$ и $2 b=d$ и получим, что $3 3 a ≡b$ (mod $m$ ). Так можно делать сколько угодно раз, поэтому $k k a ≡ b$ (mod $m$ ) для любого натурального $k$ .