Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Выбор модуля для доказательства делимости / простоты / степени

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

Выбор модуля для доказательства делимости / простоты / степени

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

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

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

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

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

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

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

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

Дано натуральное $n >2.$ Докажите, что существуют $n$ натуральных чисел таких, что произведение любых $n− 1$ из них даёт остаток $1$ при делении на оставшееся число.

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

Положим $a = 2,a = 3,a =a a ...a + 1 1 2 k 1 2 k−1$ при $3 ≤k <n$ и, наконец, $a = aa ...a − 1. n 12 n−1$ Тогда $aa ...a ≡1 (mod a ) 12 n−1 n$ очевидным образом. Рассмотрим члены нашей последовательности по модулю $ak$ при $k < n.$ Если $k< j < n,$ имеем $aj ≡ 1 (mod ak),$ а $an ≡ −1 (mod ak).$ Поэтому $a1a2...ak− 1ak+1...an ≡−a1a2...ak−1 ≡$ $≡− (−1)≡ 1 (mod ak),$ что и требовалось.

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

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

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

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

Докажите, что сумма квадратов пяти последовательных чисел не может быть квадратом целого числа.

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

Обозначим пять чисел через $n− 2,n − 1,n,n+ 1,n+ 2.$ Их сумма квадратов равна $5n2+ 10= 5(n2+ 2).$ Предположим, что она является полным квадратом. Сумма делится на $5,$ значит она обязана делиться и на $25.$ Следовательно, $2 n + 2≡ 0 (mod 5),$ откуда $2 n ≡ 3 (mod 5).$ Осталось заметить, что квадрат не может давать остаток $3$ при делении на $5.$ В этом можно убедиться с помощью полного перебора остатков при делении на $5.$ Пришли к противоречию.

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

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

Докажите, что число $12017+22017+ ⋅⋅⋅+ n2017$ не может делиться на $n +2.$

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

Разобьём слагаемые на пары $(i,n +2− i).$ Заметим, что

2017 2017 2017 2017 2017 2017 i + (n+ 2− i) ≡ i + (−i) ≡ i − i ≡0 (mod n+ 2)

То есть сумма чисел в каждой из пар делится на $n+ 2.$ Нетрудно видеть, что на пары разбились все слагаемые, кроме $12017.$ Следовательно, вся сумма сравнима с $12017$ по модулю $n+ 2,$ то есть при делении на $n+ 2$ она даёт остаток $1,$ из этого незамедлительно следует требуемое.

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

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

К некоторому натуральному числу, кратному семи, справа приписывают девятки. Докажите, что когда-нибудь получится составное число.

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

Пусть к числу дописали $n$ девяток, тогда его можно записать в виде $a⋅10n+ 10n − 1,$ где $a$ — число, делящееся на $7,$ а $10n− 1$ — $n$ девяток. По модулю $7$ это число сравнимо с $n 10 − 1,$ что, в свою очередь, сравнимо с $n 3 − 1.$ Заметим, что $3 3 ≡− 1 (mod 7).$ Следовательно, $6 3 ≡ 1 (mod 7),$ то есть $6 3 − 1≡ 0 (mod 7).$ Значит, если дописать шесть девяток, то получится число, которое кратно $7$ и, очевидно, больше $7.$ Что и требовалось.

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

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

Докажите, что есть такое число $2n,$ что $2n− 1 ..2017. .$

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

Рассмотрим числа $21− 1,22 − 1,...,22017 − 1.$ Предположим, что среди них нет ни одного, кратного $2017.$ Следовательно, среди них найдутся два различных числа $i 2 − 1$ и $j 2 − 1,$ дающих один и тот же остаток при делении на $2017,$ поскольку всего остатков $2017$ и остаток $0$ среди чисел не встречается. То есть $i j 2 − 1≡ 2− 1 (mod 2017).$ Таким образом, $i j−i 2 (2 − 1)≡ 0 (mod 2017)$ (не умаляя общности $j > i).$ Нетрудно видеть, $i 2$ не имеет общих делителей с $2017.$ Значит, $j−i 2 − 1$ делится на $2017.$ Но это число принадлежит набору $1 2 2017 2 − 1,2− 1,...,2 − 1,$ и мы предположили, что ни одно из этих чисел не кратно $2017,$ пришли к противоречию.

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

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

Пусть $x$ и $y$ — взаимно простые числа. Холо хочет купить яблоко за $1$ люмион, но у неё есть только очень много монет достоинством в $x$ люмионов, а у продавца очень много монет достоинством в $y$ люмионов. Докажите, что Холо может порадовать себя фруктом.

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

Рассмотрим числа $0,1,2,...,y− 1.$ Этот набор состоит из всевозможных остатков по модулю $y.$ Умножим каждое из чисел на $x.$ Покажем, что новый набор по-прежнему представляет набор из всевозможных остатков. Предположим противное, тогда найдутся такие два различных числа $ix$ и $jx$ ( $j > i$ ), что $ix≡ jx (mod y).$ По условию $x$ и $y$ взаимно просты, а значит на $x$ можно сократить: $i≡j (mod y).$ Но по нашему предположению $i$ и $j$ — это какие-то различные остатки при делении на $y,$ противоречие.

Значит, среди чисел $0⋅x,1⋅x,...,(y− 1)⋅x$ есть число $tx,$ дающее остаток $1$ при делении на $y.$ В таком случае Холо может отдать $t$ монет и продавец сможет выдать ей сдачу.

Курсы

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

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

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

Существует ли степень двойки, из которой перестановкой цифр ( $0$ ставить на первое место нельзя) можно получить другую степень двойки?

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

Предположим, что да. Тогда эти степени двойки сравнимы по модулю $9,$ так как их суммы цифр равны. Вместе с этим заметим, что степени двойки имеют цикл остатков $2,4,8,7,5,1$ по модулю $9.$ Значит, эти степени двойки отличаются как минимум в $6 2 = 64$ раза, то есть у них разное количество цифр, противоречие.

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

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

Пусть $m$ и $n$ — натуральные числа. Докажите, что число $5n+ 5m$ можно представить в виде суммы двух точных квадратов тогда и только тогда, когда число $n − m$ чётное.

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

Если $m$ и $n$ оба четны, то $m = 2k,n =2l$ и

2k 2l (k)2 ( l)2 5 +5 = 5 + 5

Если $m$ и $n$ оба нечетны, то $m = 2k +1,n= 2l+1$ и

( )2 ( )2 52k+1+ 52l+1 = 5k+2 ⋅5l + 5l− 2⋅5k

Если $m$ и $n$ имеют разную четность, то $5n +5m = 52k+1+ 52l ≡ 6(mod8)$ . Но остатки точных квадратов по модулю 8 могут принимать лишь значения 0, 1 и 4. Остаток их суммы по модулю 8 не может быть равен 6.

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

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

Пусть $a ,a,a ,... 1 2 3$ — последовательность натуральных чисел, определенная как

3 a1 = 1, ak+1 = ak +1

при всех натуральных $k.$ Докажите, что каждое простое $p$ вида $3ℓ+ 2,$ где $ℓ$ натуральное, является делителем $an$ при некотором натуральном $n.$

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

Рассмотрим полную систему вычетов по модулю $p.$ Докажем, что если каждый вычет поменять по правилу $x→ x3+ 1,$ то снова получится полная система вычетов. Для этого достаточно доказать, что $3 3 x ⁄≡y (mod p)$ (1), если $x⁄≡ y (mod p).$ Понятно, что при $x$ или $y,$ кратном $p,$ это верно. Предположим, что для каких-то $x$ и $y$ это неверно; возведём сравнение (1) в степень $p−-2 3 .$ Получим $xp−2 ≡ yp−2 (mod p).$ Но также $xp−1 ≡yp−1 (mod p),$ поэтому $x≡ y (mod p),$ противоречие.

Из доказанного следует, что последовательность $ai$ зацикливается по модулю $p$ без предпериода. Пусть $at ≡1 (mod p)$ при $t⁄= 1.$ Тогда $at−1 ≡ 0 (mod p),$ что и требовалось доказать.

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

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

Существуют ли 4 различных натуральных числа, больших единицы, таких, что сумма квадратов любых трёх из них делится на оставшееся число, увеличенное на единицу?

Источники: Изумруд - 2021, 11.1 (см. izumrud.urfu.ru)

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

Подсказка 1

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

Подсказка 2

Если мы хотим использовать числа 2 и 3, то удачно было бы использовать числа, которые им кратны. То есть, к примеру, 6 или что-то большее (чтобы были общие делители у каждого слагаемого из суммы квадратов). Давайте возьмем 6 и посмотрим, чему равна сумма квадратов этих трёх чисел. Она равна 49. Тогда нам либо надо брать оставшееся число равным 48, либо 6, но 6 уже взято. Поэтому давайте возьмем 48. Подходит ли такая четвёрка?

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

Посмотрим на числа 2, 3, 6, 48:

1) сумма квадратов 2, 3, 6 равна 48+1;

2) числа 3, 6, 48 делятся на 2+1, поэтому и сумма квадратов;

3) $2 2 2 2+ 6 + 48 ≡3+10$

4) $22+ 32+ 482 ≡6+14 +2+ 1≡7 0$

Ответ: да

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

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

Последовательность $(a ) n$ задана условиями

a1 = 1, a2 = 2 и an+2 = an(an+1 +1) при n ≥1.

Докажите, что $aa n$ делится на $(an)n$ при $n ≥100.$

Источники: СпбОШ - 2020, задача 11.6(см. www.pdmi.ras.ru)

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

Подсказка 1

Будем исследовать степень вхождения простого p в элементы последовательности. Пусть k - первый номер, для которого a_k делится на p. Тогда что можно сказать про k+2-й член последовательности?

Подсказка 2

Степень вхождения p в него хотя бы на 1 больше, чем в a_k. Аналогично можно получить, что степень вхождения в (k+2n)-ый член последовательности, больше хотя бы на n. Нам нужно проверить, что для всех p a_m-ый член последовательности имеет степень вхождения p хотя бы в m раз больше, чем m-ый.

Подсказка 3

Заметим, что m и a_m одной чётности, тогда мы хотим понять, что (a_m - m) это достаточно много, чтобы степень вхождения p точно получилась большой.

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

Пусть простое число $p$ входит в $a n$ в $k$ -й степени. Докажем, что $a an$ делится на $pkn.$ Тогда утверждение задачи будет выполнено.

Пусть $ai$ — первое число в нашей последовательности, кратное $p.$ Если $p⁄= 2,$ то $i> 2$ и $ai = ai−2(ai−1+ 1).$ Следовательно,

ai−1 ≡ −1 (modp)

Заметим, что для $p= 2$ будет $i= 2,$ и выведенное сравнение тоже выполнено.

Итак, $ai−1 ≡ −1,ai ≡ 0,$ а тогда дальше в последовательности чередуются остатки $− 1$ и $0$ от деления на $p:$

a = a (a + 1)≡ −1 ⋅(0+ 1)=− 1 (modp) i+1 i−1 i ai+2 = ai(ai+1+ 1)≡ 0⋅(−1+ 1)=0 (modp) и т.д.

Более того, как видно из последнего вычисления, степени числа $p,$ на которые делятся члены последователыности, растут: если $ai$ делилось на $p,$ то $ai+2$ делится на $2 p$ и т. д. Отсюда следует, что если $an$ делится на $k p,$ то $an+2t$ делится на $k+t p .$ Кроме того, учтем, что числа $an$ и $n$ одинаковой четности, поскольку $a1 =1,$ $a2 = 2$ и остатки по модулю $2$ чередуются. Следовательно, $aan$ делится на $k+(a −n)∕2 p n .$ Остается заметить, что $n an > 2$ при $n≥ 5$ (это значит, что $an$ существенно крупнее $n$ ) и $k an ≥2 ,$ так как делится на $k p$ (это значит, что $an$ существенно крупнее $k$ ), поэтому $an− n >2kn$ , откуда следует требуемое.

Интенсивы

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

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

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

Докажите, что число $33n+ 173n +313n$ при нечётном $n$ раскладывается в произведение хотя бы четырёх (не обязательно различных) натуральных чисел, больших единицы.

Источники: ИТМО - 2020, 11.1 (см. olymp.itmo.ru)

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

Подсказка 1

Нам нужно найти числа, на которые делится наше выражение. Попробуйте рассмотреть маленькие числа: на 2 выражение не делится, а на 3?

Подсказка 2

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

Подсказка 3

О, оно делится на 9, здорово. Теперь надо найти ещё какой-нибудь делитель. Мы знаем, что одно из трёх слагаемых делится на 17. А кратна ли 17 сумма остальных двух слагаемых?

Подсказка 4

Попробуйте доказать, что a^m+b^m кратно a+b при нечётном m. Тогда доказать делимость на 17 будет совсем просто:) Вот, у нас есть уже три множителя, а четвёртый можно явно не искать, достаточно показать, что он будет больше единицы.

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

$3+ 31= 34$ делится на $17,$ а значит то же самое выполняется и для суммы любых нечётных степеней. Это верно, т.к. $am + bm$ на $a+ b$ при нечётном $m.$ По-другому можно это доказать так: $31≡ −3(mod 17),$ значит $3n 3n 3n 31 ≡ (−3) ≡ −3 ,$ т.к. $3n$ нечётно.

Теперь рассмотрим остатки по модулю $9.$ $3n 3$ делится на $9.$ $17$ в нечётной степени даёт при делении на $9$ остаток $8$ , а в чётной - остаток $1.$ Число $3 31$ даёт остаток $1$ при делении на $9,$ а значит и любая нечётная степень куба даёт такой же остаток. Таким образом, сумма $3n 3n 3n 3 + 17 + 31$ делится на $9.$

Мы получили уже три множителя: $3,3 и 17.$ Кроме того $3n 3n 3n 3 + 17 + 31 >3⋅3⋅17= 153,$ поэтому есть хотя бы ещё один делитель.

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

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

Сколько существует натуральных чисел $n≤ 2020$ , для которых дробь

6n3-+n2−-5n+-12 6n2+7n +2

сократимая?

Источники: Росатом - 2020, 11.1 (см. olymp.mephi.ru)

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

Подсказка 1

Первое, что стоит сделать, когда хотим сократить дробь — выделить её целую часть! Поэтому попробуем поделить числитель на знаменатель и будем работать уже с новой дробью, у которой числитель является остатком от деления ;)

Подсказка 2

Итак, имеем новую дробь с числителем, равным 14. А на какие числа вообще может сокращаться такая дробь?

Подсказка 3

У числа 14 всего 3 делителя, больших 1, поэтому можно разобрать случаи НОДа числителя и знаменателя.

Подсказка 4

Если наибольший общий делитель равен 2, то можно сделать выводы о чётности n.

Подсказка 5

Если НОД равен 7, то какой остаток будет давать 6n²+1 при делении на 7? Что можно сказать про n?

------

Подсказка 6
Можно рассмотреть табличку остатков по модулю 7 у числа, его квадрата и квадрата, умноженного на 6.

------

Подсказка 7
В случае НОДа, равного 14, можно попробовать разложить знаменатель и разобрать случаи его делителей!

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

Распишем числитель дроби следующим образом:

3 2 3 2 2 2 6n +n − 5n+ 12= 6n +7n + 2n− 7n − 2n+ n − 5n − 2 +2+ 12=

= n(6n2 +7n+ 2)− (6n2+ 7n +2)+ 14= (n − 1)(6n2+ 7n+ 2)+ 14

Выделим целую часть в дроби:

6n3+-n2− 5n-+12= (n−-1)(6n2+-7n-+2)+-14= n− 1+----14----- 6n2+ 7n+ 2 6n2+ 7n+ 2 6n2+7n+ 2

Если исходная дробь сократимая, то дробь $--14--- 6n2+7n+2$ так же сократимая, то есть числа $(6n2 +7n+ 2)$ и 14 имеют общий делитель, больший 1. При этом у 14 есть три натуральных делителя, больших 1: 2, 7, 14. Пусть $p$ — наибольший общий делитель 14 и $(6n2+7n+ 2).$ При этом, так как у 14 есть три натуральных делителя, больших 1: 2, 7, 14, — то у нас есть три варианта:

$1)p= 2.$ Заметим, что $2 6n + 2n$ — чётное при любом натуральном $n,$ а значит, чтобы все число $2 (6n + 7n +2)$ делилось на 2, $7n$ должно делиться на 2, откуда $n$ — чётное. Существует 1010 четных натуральных чисел, не превосходящих 2020.

$2)p= 7.$ Заметим, что $2 6n + 2$ должно делиться на 7, чтобы $2 (6n + 7n+ 2)$ делилось на 7, так как $7n$ делится на 7 при любом натуральном $n.$ Отсюда, $2 6n$ должно иметь остаток 5 при делении на 7. Посмотрим, при каких $n$ это возможно, рассмотрев все остатки по модулю 7. Для этого начертим таблицу, где слева будет число, а справа его остаток при делении на 7.


$n$	0	1	2	3	4	5	6

$n2$	0	1	4	2	2	4	1

$6n2$	0	6	3	5	5	3	6

Получается, если $n$ имеет остаток 3 или 4 при делении на 7, то $2 (6n +7n+ 2)$ делится на 7. Существует 145 нечётных натуральных чисел, не превосходящих 2020 и имеющих остаток 3 по модулю 7, и 144 нечётных натуральных числа, не превосходящих 2020 и имеющих остаток 4 по модулю 7.

$3)p= 14.$ Заметим, что $2 (6n +7n+ 2)= (3n+ 2)(2n+ 1).$ Если $(3n+ 2)$ делится на 14, то оно делится ещё и на 2, то есть $n$ — чётное, а все четные $n$ мы уже учли. А $(2n+ 1)$ на 14 делиться не может, так как это нечётное число. Получается, если $(3n+ 2)(2n+ 1)$ делится на 14, то $(3n +2)$ делится на 2, а $(2n+ 1)$ делится на 7, но это верно только при чётный $n,$ которые мы уже посчитали.

Итак, всего чисел, при которых исходная дробь сократима: $1010+ 144 +145= 1299.$

Ответ:

1299

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

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

Назовём число $n$ волшебным, если оно делит число

( 1 1 -1--) (n− 1)!× 1+ 2 +3 +...+ n− 1 .

Найдите все волшебные числа $n$ в промежутке от $10$ до $100.$

Источники: Турнир Ломоносова - 2020, 11.4 (см. turlom.olimpiada.ru)

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

Подсказка 1

Задача на делимости, а после раскрытия скобок появится некоторая сумма, которую надо рассмотреть по модулю n. Удобнее всего как-то классифицировать различные значения n. Например, по простоте. А что, если n раскладывается на множители a и b? Такие случаи тоже можно классифицировать в зависимости от a и b.

Подсказка 2

Разберите случай простого n. Для этого можно, например, посмотреть на остатки каждого из слагаемых по такому модулю. А что делать, если n — "почти простое"? Скажем, у него есть ещё ровно 3 делителя, кроме простого p.

Подсказка 3

Разберите случай n = p*2, где p — простое. Что можно сказать о каждом из слагаемых после раскрытия скобок?

Подсказка 4

И, наконец, можно разобрать случай, когда n можно разложить в произведение a и b, где оба эти множителя больше 2. Как можно оценить a и b? Какие множители точно будут в числителях слагаемых?

Подсказка 5

Хотя бы одно из них небольшое, так что в числителях, кроме a и b, будут ещё числа, которые делятся на них ;)

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

Докажем, что в общем случае при $n> 9$ не являются волшебными числа только вида $n =2p$ , где $p$ — простое.

Для этого разберём три случая: когда $n$ является простым, когда $n∕2$ является простым, и когда ни $n$ , ни $n∕2$ не являются простыми (в частности, если $n$ нечётно, то $n∕2$ не является простым).

_________________________________________________________________________________________________________________________________________________________________________________

Первый случай. Если $n$ является простым. Рассмотрим выражение

( 1 1 1 ) (n− 1)! (n− 1)! (n− 1)!× 1+ 2 + 3 +...+ n-− 1 = (n − 1)!+--2--+ ...+ -n−-1-

по модулю $n.$ Утверждается, что среди слагаемых в этой сумме встретятся все возможные ненулевые остатки по модулю $n$ . Так как различных ненулевых остатков по модулю $n$ ровно $n− 1$ и слагаемых столько же достаточно показать, что все слагаемые дают различные остатки по модулю $n$ . Это действительно так, потому что в противном случае для некоторы $a$ и $b$ таких, что $1≤ a<$ $b≤ n− 1$ было бы верно сравнение

(n−-1)!≡ (n−-1)!(modn ) a b

Но перенеся в этом сравнении всё в левую часть, получаем

(n−-1)!− (n−-1)!≡ 1⋅2⋅...(a− 1)⋅(a+ 1)⋅...⋅(n− 1)− 1 ⋅2⋅...⋅(b− 1)⋅(b+ 1)⋅...⋅(n− 1)≡ a b

1⋅2⋅...⋅(a− 1)⋅(a+ 1)⋅...⋅(b− 1)⋅(b+1)⋅...⋅(n− 1)⋅(b− a) ≡0(modn),

что невозможно, так как все множители в произведении не делятся на $n$ , а $n$ — простое. Полученное противоречие доказывает, что слагаемые являются всеми возможными остатками по модулю $n$ , а значит, им сумма равна $n(n−1) 2$ , то есть кратна $n$ , так как $n$ простое, большее $9,$ а следовательно, нечётно.

_________________________________________________________________________________________________________________________________________________________________________________

Второй случай. Если $n∕2$ является простым. Обозначим $n∕2$ через $p,$ тогда $n =2p.$ Заметим, что среди чисел от $1$ до $n − 1$ есть только одно, кратное $p$ : это само число $p$ . Тогда при раскрытии скобок в выражении

( 1 --1-) (n− 1)!× 1+ 2 +...+ n − 1

все слагаемые кроме $1 (n− 1)!× p$ будут кратны $p,$ а это слагаемое — не будет. Значит, и вся сумма не будет кратна $p$ , а следовательно, и $2p$ , то есть $n$ . Значит, в этом случае число магическим не является.

_________________________________________________________________________________________________________________________________________________________________________________

Tретий случай. Если ни $n,$ ни $n∕2$ не являются простыми. В этом случае $n$ можно представить в виде произведения (т. к. $n$ непростое), причём оба множителя будут больше $2$ (так как либо $n$ , поделённое на любой нечётный простой делитель будет больше двойки, либо $n$ — степень двойки, но в силу $n >9,$ степень двойки хотя бы четвёртая, и значит, $n =4 ⋅ n4$ , где оба множителя больше $2$ ). То есть для некоторых $a,b>2$ верно $n= a⋅b$ . Тогда раскрывая скобки в выражении

( ) (n− 1)!× 1+ 1 +...+--1- n n − 1

получаем слагаемые вида $(n− 1)!⋅ 1 c$ , где $c⁄= a,b$ , и два слагаемых

(n− 1)!⋅ 1,(n− 1)!⋅ 1. a b

Во всех слагаемых первого вида в произведении $(n− 1)!$ содержатся множители $a,b$ и $c$ , а значит, после сокращения на $c$ оставшееся произведение будет делиться на $ab= n$ . Теперь заметим, что $2a <ab= n$ . Тогда в случае $2a⁄= b$ во втором слагаемом в произведении $(n− 1)!$ содержатся различные множители $a,2a,b,$ а значит, после сокращения на $a$ останется произведение $2a⋅b= 2n$ , кратное $n$ . Если же $2a= b$ , то $2 n= 2a$ , но тогда число $3a< n$ и $1 2 a⋅2a⋅3a⋅a = 6a$ кратно $n$ . Аналогично доказывается, что последнее, третье слагаемое, кратно $n$ , а значит, число является волшебным, так как все слагаемые кратны $n$ .

_________________________________________________________________________________________________________________________________________________________________________________

Осталось заметить, что числами, для которых их половина является простым числом, являются те и только те, что перечислены как исключённые в ответе.

Ответ:

Все числа от $10$ до $100$ кроме $10,14,22,26,34,38,46,58,62,74,82,86,94$ .

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

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

Чётное число $2N > 2$ называется подходящим, если оно делится на модуль разницы между наибольшим из своих чётных делителей, отличных от $2N$ , и наибольшим из своих нечётных делителей. Сколько существует подходящих чётных чисел, не превосходящих $2018?$

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

Подсказка 1

Попробуем записать число в виде 2^k*m, где m - нечетно. Запишем условие и подумаем, какие ограничения можно наложить на переменные!

Подсказка 2

2^k*m должно делиться на m(2^(k-1) - 1). При каких k это возможно? Обратим внимание не четность.

Подсказка 3

При k >= 2 решение только 1 (какое?) А что если k =1? Как нам выделить наибольший четный делитель?

Подсказка 4

Запишем m как p*s, где p - минимальный простой нечетный делитель. Теперь мы можем записать условие с помощью новых переменных и найти p!

Подсказка 5

Число p обязательно равно трём! Получается, что 2N = 2*3*s. Теперь попробуем поискать такие числа среди чисел от 1 до 2018...

Подсказка 6

Обратите внимание на остатки от деления числа 2N на 4 и 6. Тогда все числа от 1 до 2018 можно разбить на последовательности, в которых мы точно знаем количество подходящих чисел!

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

Предположим, что число $2N$ подходящее. Пусть $2N = 2km,$ где $m$ нечётное. Если $k≥ 2,$ то условие говорит, что $k 2 m$ делится на $k−1 k−1 2 m − m= m (2 − 1),$ что возможно только при условии $k= 2.$ Если $k= 1$ и $m =ps,$ где $p$ минимальный простой нечетный делитель $m,$ то $2ps$ делится на $2s− ps= (2− p)s,$ откуда имеем $. p.. (p− 2),$ значит, $p =3.$ Число $N$ или имеет остаток $2$ по модулю $4$ или имеет остаток $3$ по модулю $6.$ Тем самым число $2N$ является подходящим, если число $N$ может иметь остаток $2, 3, 6, 9, 10$ по модулю $12.$ Это значит, что в каждом ряду из $12$ последовательных четных чисел ровно пять подходящих. Используя равенство $2018= 2⋅(12⋅84+ 1),$ получаем ответ $420= 5⋅84.$

Ответ: 420

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

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

Можно ли представить число $112018$ в виде суммы кубов двух натуральных чисел?

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

Подсказка 1

Существует ряд модулей, по которым кубы натуральных чисел дают "приятные остатки". К их числу относиться, например, модуль 8 - куб натурального числа может давать только остатки 0,1,3, -3, -1 по данному модулю. А по какому модулю можно рассмотреть данное уравнение?

Подсказка 2

Ясно, что при этом нам придется рассматривать число 11^2018 по данному модулю, поэтому будет проще, если 11^2018 будет давать какой-то понятный остаток по рассматриваемому модулю (точнее остаток, который мы сможем найти, что не всегда бывает просто).

Подсказка 3

Давайте рассмотрим уравнение по модулю 9. Какие остатки могут давать кубы натуральных чисел по этому модулю?

Подсказка 4

Только остатки 0, 1 или -1. С чем в свою очередь сравнимо число 11^2018 по модулю 9?

Подсказка 5

Ясно, что 11^2018 сравнимо с 2^2018 по данному модулю. Осталось заметить, что 2^6=64 сравнимо с 1 по модулю 9. Вообще говоря, для каждого числа a существует число b такое, что a^b сравнимо с 1 по данному модулю. В некоторых задачах данное число b можно найти перебором, тем более в тех задачах, где в качестве основания рассматриваются 2, потому что ее первые степени считаются довольно быстро. Закончите решение, воспользовавшись этим сравнением.

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

С одной стороны, поскольку $26 = 64≡ 1 (mod 9)$ и $2018 ≡2 (mod 6= φ(9)),$ имеем

2018 2018 2 11 ≡ 2 ≡ 2 = 4 (mod 9)

То есть число $112018$ даёт остаток $4$ при делении на $9.$ С другой стороны, кубы натуральных чисел дают только остатки $0,1$ и $8$ при делении на $9.$ Значит, сумма кубов двух натуральных чисел может дать лишь остатки $0,1,2,7$ или $8$ при делении на $9,$ но не может дать $4.$

Ответ:

Нет

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

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

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

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

Даны натуральные числа $a$ и $b.$ Докажите, что существует бесконечно много натуральных $n$ таких, что число $an+ 1$ не делится на $b n + 1.$

Источники: Всеросс., 2018, ЗЭ, 10.6(см. olympiads.mccme.ru)

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

Назовём натуральное $n$ плохим, если $an+1$ не делится на $nb+1.$ Наша цель — доказать, что плохих чисел бесконечно много.

Первое решение. Докажем, что при любом чётном $n$ одно из чисел $n$ и $3 n$ плохое; из этого, очевидно, следует требуемое. Предположим противное. Тогда $n .. b a + 1.n + 1$ и $n3 .. 3b .. b a +1.n + 1.n +1.$ Иначе говоря, $n ( b ) a ≡− 1 mod n + 1$ и $n3 ( b ) a ≡ −1 mod n + 1.$ Но отсюда следует, что $n3 nn2 n2 ( b ) − 1 ≡a = (a ) ≡ (−1) ≡1 modn + 1 ;$ это невозможно, ибо $b n +1 >2.$ Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. При $a= 1$ утверждение задачи очевидно, поэтому будем считать, что $a> 1.$

______________________________________________________________________________________________________________________________________________________

Лемма. Пусть $a >1,m$ и $n$ — натуральные числа. Предположим, что $an+ 1$ делится на $am+ 1.$ Тогда $n$ делится на $m.$

Доказательство. Пусть $r$ — остаток от деления $n$ на $m,n− r= qm.$ Тогда

0 ≡an +1= aqm+r+ 1≡ (− 1)qar+ 1=±ar +1(mod am+ 1)

то есть одно из чисел $r a ± 1$ делится на $m a + 1.$ Но это невозможно при $r⁄= 0,$ ибо $r m 0< a ±1 <a + 1.$

______________________________________________________________________________________________________________________________________________________

Докажем, что существует бесконечно много плохих чисел вида $ak.$ Действительно, если $k aa +1$ делится на $akb+ 1,$ то по лемме $ak$ должно делиться на $kb.$ Это невозможно, если, например, $k$ — простое число, большее $a.$ Осталось заметить, что таких простых чисел бесконечно много.

_________________________________________________________________________________________________________________________________________________________________________________

Третье решение. Мы опять же исследуем лишь случай $a> 1.$

Пусть $p$ — некоторый простой делитель числа $(a(a− 1))b+1.$ Положим $ni = a(a− 1)+ ip;$ тогда при любом $i$ имеем $nbi + 1≡ (a(a− 1))b+ 1≡ 0(mod p),$ то есть $nbi + 1$ делится на $p.$

С другой стороны, покажем, что числа $ani + 1$ и $ani+1 +1 =ani+p+ 1$ не могут одновременно делиться на $p.$ Действительно, иначе на $p$ делилась бы и их разность $ani(ap − 1);$ но это невозможно, ибо $ap− 1≡ a− 1(mod p)$ по малой теореме Ферма, а числа $a$ и $a− 1$ взаимно просты с $p.$

Итак, либо $ani + 1$ не делится на $p$ (и, значит, на $nbi +1$ ), либо $ani+1 +1$ не делится на $p$ (и, значит, на $nbi+1+ 1$ ). Поэтому среди чисел $n1,n2,...$ бесконечно много плохих.

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

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

Можно ли представить число 2017 в виде суммы двух натуральных чисел, сумма цифр одного из которых вдвое больше суммы цифр другого?

Источники: Всесиб - 2017, 9.3(см. sesc.nsu.ru)

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

Подсказка 1

На что нам намекает сумма чисел? С каким из известных фактов можно попробовать найти противоречие?

Подсказка 2

Сумма чисел намекает на модуль 3! Число дает такой же остаток по модулю 3, что и его сумма цифр :) Разберем случаи!

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

Предположим противное: что $2017$ можно представить как сумму натуральных чисел $A$ и $B,$ причём сумма цифр $A$ вдвое больше суммы цифр $B.$

При сложении двух цифр одного разряда в нём остаётся их сумма (если она меньше $10$ ), либо их сумма минус $10$ (если она больше $10,$ а единица уходит в следующий разряд). Таким образом, сумма цифр $A +B$ равна сумме цифр $A$ плюс сумма цифр $B$ минус число переходов единицы в следующий разряд при сложении, умноженное на $9.$

По условию сумма цифр $A$ вдвое больше суммы цифр $B,$ поэтому их общая сумма делится на $3,$ значит, и сумма цифр $A+ B = 2017$ должна делиться на $3$ — противоречие с тем, что сумма цифр числа $2017$ равна $10.$

Ответ: нет

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

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

Найдите все такие пары натуральных чисел $a$ и $k,$ что для всякого натурального $n,$ взаимно простого c $a,$ число $akn+1 − 1$ делится на $n.$

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

Подсказка 1

Понятно, что a=1 подходит. Пусть теперь a больше 1, попробуйте тогда подобрать какой-то пример для n, который сделает выполнение условия невозможным.

Подсказка 2

Показатель степени у а слишком сложный. Попробуйте подобрать такое n, чтобы внутри этой степени возник остаток 1.

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

Если $a =1,$ то $akn+1− 1= 0,$ а значит, делится на $n.$

Пусть $a≥2.$ Возьмём $k n =a − 1,$ тогда $k a ≡n 1,$ и следовательно,

kn+1 kkn−1 0≡n a − 1≡n (a) ⋅a− 1≡n a− 1

Если $k> 1,$ то в силу неравенства $a >1$ получаем неравенство $k a− 1< a − 1 =n,$ что противоречит $a− 1≡n 0.$

Если $k= 1,$ то $n ak+1 − 1= a2− 1$ должно делиться на все $n,$ что невозможно.

Таким образом, пары, в которых $a≥ 2,$ нам не подходят.

Ответ:

$a =1,k$ - любое натуральное число.

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

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

Пусть $n >3$ — натуральное число. Докажите, что если в записи числа $A$ в системе счисления с основанием $n$ каждая цифра встречается ровно один раз, то $A$ — составное.

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

Посмотрим на число $A$ по модулю $n − 1.$ Очевидно, что оно сравнимо со своей суммой цифр по этому модулю, то есть $A − n(n−1) 2$ кратно $n − 1.$ Откуда число $A$ делится на $n − 1,$ если $n$ чётно, и на $n−1 2 ,$ если нечётно.

Ответ: