Тема ТЕОРИЯ ЧИСЕЛ

Остатки и сравнения по модулю → .01 Базовый аппарат сравнений по модулю

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

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

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

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

Подтемы раздела теория чисел

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

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

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

Малая теорема Ферма

Функция Эйлера и теорема Эйлера из ТЧ

Китайская теорема об остатках

Обратные остатки

Квадратичные вычеты

Показатели и первообразные корни

Лемма об уточнении показателя

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

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

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

Коля выписал каждый натуральный делитель числа $2025n$ по одному разу, после чего покрасил некоторые из них в красный цвет, а остальные — в синий. При этом он действовал так, чтобы разность между суммой всех красных делителей и суммой всех синих делителей оказалась минимально возможным (при данном $n$ ) положительным числом. Какими могут оказаться две последние цифры этой разности? (Найдите все варианты и докажите, что других нет.)

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

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

Подсказка 1

Разложите 2025 на простые множители. Как выглядит сумма всех его делителей? Почему максимальный делитель 2025ⁿ больше суммы остальных? Сумма делителей растёт медленнее, чем само число, из-за степеней в разложении.

Подсказка 2

Чтобы разность сумм красных и синих делителей была минимальной положительной, как нужно раскрасить делители? Что произойдёт, если покрасить только 2025 в красный, а остальные — в синий? Разность будет 2 × 2025ⁿ.

Подсказка 3

Докажите, что искомая разность = 70n + 81 (mod 100). Какие остатки при делении на 100 могут быть у 70n + 81 при разных n? Переберите n от 1 до 20. Остатки будут циклически повторяться!

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

Если $n = 0,$ разность равна $1.$ Пусть $n >0.$ Сумма всех делителей числа 2025 равна

2 4n 2 2n (1 +3+ 3 + ...+ 3 )(1+ 5+ 5 +...+5 )=

n−1 n−1 =(1+ 120(1+ 81+...+81 ))(1 +30(1 +25+ 25 ))≡

≡ 1+ 120n+ 30(6+ 5n)≡ 81 +70n (mod 100)

По формуле суммы геометрической прогрессии, сумма делителей меньше, чем

( ) ( ) 34n⋅ 3 52n⋅ 5 =2025n⋅ 15 2 4 8

Значит, максимальный делитель (само число $2025n)$ превосходит сумму остальных, поэтому для получения минимального положительного результата перед ним должен стоять плюс, а перед остальными делителями — минус. Получается, что ответ имеет вид $50− 81− 70n (mod 100) ∈$ ${9;19;29;39;49;59;69;79;89;99}.$ Заметим, что разность больше $2025 8 > 9,$ то есть по крайней мере двузначная.

Ответ:

1, 09, 19, 29, 39, 49, 59, 69, 79, 89, 99

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

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

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

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

Как изменятся частное и остаток, если делимое и делитель увеличить в $5$ раз?

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

Пусть число $a$ даёт остаток $r$ при делении на $b,$ то есть $a= b⋅c+ r.$ Увеличим делимое в пять раз, тогда получим $5a= 5b⋅c+ 5r.$ Так как по условию делитель стал равен $5b,$ видим, что частное осталось неизменным, а остаток увеличился в пять раз. Важно отметить, что так как $0 ≤r <b,$ $0≤ 5r< 5b,$ то есть $5r$ действительно является остатком при делении на $5b.$ В силу однозначности определения остатка полученный нами результат — единственно возможный.

Ответ:

Остаток увеличиться в пять раз

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

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

Число $a$ даёт остаток $3$ при делении на $5.$ Какой остаток оно может давать при делении на $15?$

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

По условию $a= 5c+ 3,$ пусть частное при делении $a$ на 15 равно $x,$ а остаток равен $r,$ то есть $a =15x+ r.$ Приравняем правые части имеющихся равенств:

5c+ 3= 15x+ r

5c− 15x= r− 3

Заметим, что $5c− 15x$ кратно пяти, а, значит, $r− 3$ тоже нацело делится на 5. Учитывая, что $r$ — остаток при делении на 15, то есть $0 ≤r< 15,$ получаем три возможных варианта: $r= 3;$ $8;$ $13.$

В самом деле, число $a =3$ имеет остаток 3 при делении на 5 и 15, число $a= 8$ имеет остаток 3 при делении на 5 и остаток 8 при делении на 15, и наконец, число $a= 13$ имеет остаток 3 при делении на 5 и остаток 13 при делении на 15.

Ответ:

3; 8; 13

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

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

Конфеты пытались раздать по $2,$ по $3,$ по $4$ и по $5$ конфет, но каждый раз оставалась одна лишняя конфета. Сколько конфет было всего, если известно, что их было точно больше одной, но меньше $100?$

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

Пусть $a$ — количество конфет. По условию задачи:

(| a =2c+ 1 |||{ a =3d+ 1 | |||( a =4e+ 1 a =5f + 1

То есть число $a − 1$ делится на 2, 3, 4 и 5. Так как числа 3, 4 и 5 не имеют общих делителей, можно сделать вывод, что число $a − 1$ делится на $3⋅4⋅5= 60,$ то есть число $a$ даёт остаток 1 при делении на 60. Среди чисел, больших 1, но меньших 100, есть всего одно число, удовлетворяющее данному условию — это число 61.

Ответ:

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

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

Даша и Ксюша делят одно и то же натуральное число с остатком. Даша делит его на $8,$ а Ксюша на $9.$ Частное, которое получила Даша, и остаток, который получила Ксюша, в сумме дают $13.$ Какой остаток получился у Даши?

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

Запишем условие задачи в виде системы:

{ a =8x+ r, гдe 0≤ r< 8 a =9y+ (13− x), гдe 0 ≤13− x< 9

Приравняем правые части уравнений:

8x+ r= 9y+13− x

9(x− y) =13− r

Так как левая часть уравнения делится на 9, то $13− r$ также делится на 9, то есть 13 и $r$ дают одинаковые остатки при делении на 9. Так как $13 =1⋅9+ 4,$ то $r$ даёт остаток 4 при делении на 9. Учитывая ограничение $0≤ r<8,$ получаем $r= 4.$

Ответ:

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

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

Около таверны стоят 100 эльфов, 100 гномов и 100 орков. Сначала в неё заходят 10 эльфов, 10 гномов и 10 орков. Затем каждую минуту из неё выходит одно существо и тут же заходит другое, причём всегда после выхода эльфа заходит гном, после выхода гнома — орк, а после выхода орка — эльф. Могло ли оказаться так, что в какой-то момент в таверне побывали все возможные компании из 30 существ ровно по одному разу? Все 300 существ различны.

Источники: ММО - 2025, 10.6 (см. mmo.mccme.ru)

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

Подсказка 1

Простым шагом будет вычислить количество всевозможных компаний из 30 существ. Не совсем ясно, зачем нам дан порядок выхода из таверны, как это можно перенести на математический язык?

Подсказка 2

Посмотрим на остаток разности количества эльфов и количества гномов при делении на 3, пусть это будет тип компании. Что можно сказать про компании относительно этой характеристики?

Подсказка 3

Докажем, что компаний с типом 1 и с типом 2 равное количество. А как компании чередуются относительно типа?

Подсказка 4

Вспомним, что мы знаем общее количество компаний из 30 существ, значит, нам известен и остаток при делении на 3. Попробуйте увидеть противоречие.

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

Первое решение.

Назовём типом компании остаток разности количества эльфов и количества гномов при делении на три. Заметим, что компаний типа 1 и 2 одинаковое количество, так как между ними можно построить взаимооднозначное соответствие: пронумеруем эльфов и гномов от 1 до 100 и поменяем одних на других с теми же номерами. Далее заметим, что компании меняются по циклу $0→ 1→ 2 → 0,...,$ причём, так как компаний типов 1 и 2 поровну, мы не можем закончить на 1, то есть количество всех компаний не может давать остаток 2 при делении на 3. Вычислим $30 C 300$ по модулю 3.

300⋅299⋅298⋅...⋅273⋅272 ⋅271 299⋅298⋅296⋅...⋅274⋅272⋅271 100⋅99⋅...⋅92⋅91 C33000 =----30⋅29⋅28-⋅...⋅3-⋅2-⋅1---- =----29⋅28⋅26-⋅...⋅4⋅2-⋅1---- ≡ -10⋅9⋅...⋅2⋅1--=

= 100⋅99⋅...⋅92⋅91= 100⋅98-⋅...⋅94⋅92⋅91⋅ 33⋅32⋅31≡ 10⋅9⋅...⋅2⋅1 10⋅8⋅...⋅4⋅2⋅1 3 ⋅2 ⋅1

≡ 10⋅8⋅...⋅4⋅2⋅1⋅ 33⋅32⋅31-= 11 ⋅16⋅31≡ 2 (mod 3) 10⋅8⋅...⋅4⋅2⋅1 3⋅2⋅1

Противоречие, значит, так оказаться не могло.

Замечание. Есть другой способ посчитать остаток $C30 300$ при делении на 3. Теорема Люка утверждает, что если $p$ — простое число, а числа $n$ и $k$ записываются в $p$ -ичной системе счисления как $n = ∑ nipi$ и $k= ∑ kipi,$ то $Ck≡ ∏ Ckni(mod p). n i$ Запишем 300 и 30 в троичной системе счисления: $300= (102010)3$ и $30= (1010)3.$ Таким образом,

30 1 0 1 0 1 0 C 300 ≡ C1C0C2C0C1C0 ≡2 (mod 3)

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Как и в прошлом решении разделим все компании на три типа. Если описанное в задаче возможно, то количества компаний разных типов отличается не более чем на 1, так как типы компаний меняются по циклу. Пронумеруем представителей всех рас от 1 до 100. Разобьем на тройки все компании, в которых множества номеров хотя бы каких-то двух рас различны, следующим образом. Возьмем некую компанию данного вида и рассмотрим максимальный номер, представленный хотя бы одной, но не всеми расами. Дважды прокрутим всех существ с этим номером, поменяв каждое существо на существо следующей расы с таким же номером. Легко видеть, что исходная и две полученные компании различных типов, причем с помощью данной операции они могут быть получены только друг из друга. При этом все компании не данного вида, коих всего $C10 , 100$ имеют тип 0, то есть компаний типа 0 ровно на $C10 100$ больше, чем других — противоречие.

Ответ:

Не могло

Курсы

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

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

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

Натуральное число $A$ при делении на $1981$ дало в остатке $35,$ при делении на $1982$ оно дало в остатке также $35.$ Каков остаток от деления числа $A$ на $14?$

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

Если число $A$ при делении на 1981 дало остаток 35, его можно записать в следующем виде:

A =1981a+35

Аналогично для деления на 1982:

A =1982b+35

Приравняем эти выражения:

1981a+ 35= 1982b+ 35

1981a= 1982b

Так как правая часть делится на 2, $a$ должно быть четным. Заметим, что 1981 кратно 7, следовательно, $1981a$ кратно 14. Посмотрим на остаток $A= 1981a +35$ при делении на 14:

( ) ( ) 1981a+ 35= 14 ⋅ 1981a- +14⋅2+ 7= 14⋅ 1981a-+2 +7 14 14

Следовательно, остаток от деления $A$ на 14 равен 7.

Ответ:

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

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

Докажите, что в любой “таблице умножения” вычетов по простому модулю $p$ в каждой строке все остатки различны.

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

Нам нужно показать, что при простом $p$ и $a ⁄≡ 0 (mod p)$ все вычеты $a,2a,...,pa$ будут различны. Предположим, что это не так и нашлись такие $x1 ⁄= x2,$ что

ax1 ≡ ax2 (mod p)

Перенесём всё в левую часть:

a(x1− x2) ≡0 (mod p)

Тогда или $a$ делится на $p,$ что не выполняется по условию, или $x1 − x2$ делится на $p,$ чего так же не может быть, поскольку $x1 ⁄= x2.$ Значит, все остатки в строчке таблицы умножения различны, что и требовалось доказать.

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

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

При каких натуральных $n$ число $20n+ 16n− 3n − 1$ делится на 323?

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

__________________________________________________________________________________________________

Лемма. Число $n n a − b$ кратно числу $a− b,$ где $a,b$ — натуральные, $n$ — неотрицательное целое.

Доказательство. По формуле сокращенного умножения

n n n−1 n−2 n−2 n−1 a − b =(a− b)(a + a b+ ...+ ab + b )

Значит, $an− bn$ кратно $a − b.$

______________________________________________________________________________________________________________________________________________________

Заметим, что $323= 17⋅19,$ при этом 17 и 19 взаимнопростые, откуда число делится на 323 тогда и тогда тогда, когда оно делится на 17 и на 19.

Для начала рассмотрим делимость на 17. По лемме $n n 20 − 3$ кратно $20− 3= 17,$ то есть наше число делится на 17 тогда, когда $n 16 − 1$ кратно 17. При этом $n n 16 ≡ (− 1) (mod 17),$ то есть $n 16 − 1$ кратно 17 только при чётном $n.$

Теперь рассмотрим делимость на 19. По лемме $n n 20 − 1$ делится на $20− 1= 19,$ а при $n =2k$ число $n n 2k 2k 16 − 3 = 16 − 3$ делится на $2 2 16 − 3 =13⋅19.$

Итак, исходное число делится на 323 при чётных $n.$

Ответ:

При четных $n$

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

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

Даны простое число $p$ и три различных натуральных числа $a,b$ и $c$ таких, что $ab+ 3,bc+ 3,ac+ 3$ и $abc+ 11$ делятся на $p.$ Чему может быть равно $p?$

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

Подсказка 1

Для начала стоит переписать условие в виде сравнений по модулю. А что получится, если все получившиеся сравнения перемножить?

Подсказка 2

Тогда получится, что (abc)² ≡ -27. Но из условия мы знаем, что (abc)² ≡ 121. Что тогда можно сказать о p?

Подсказка 3

Действительно, тогда p — простой делитель 121 - (-27) = 138. Осталось разложить на множители и найти примеры!

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

Давайте запишем условия на делимость в виде сравнений:

ab≡ −3 (mod p)

bc≡ −3 (mod p)

ac≡ −3 (mod p)

abc≡ −11 (mod p)

Теперь мы можем перемножить первые три сравнения и получить, что $(abc)2 ≡ −27 (mod p).$ Но из условия $(abc)2 ≡ 121 (mod p).$ Значит, $p$ является делителем числа $121 − (−27)= 148= 22⋅37,$ и может быть равен либо $2,$ либо $37.$ Для $p= 2$ можно взять просто три нечётных числа $a,b,c.$ А для $p =37$ существуют числа $a= 16,b= 16+37,c= 16 +37⋅2.$ Действительно, легко проверить, что все сравнения выполняются, потому что по модулю $37$ они равны $16,$ а $. 163+ 11 ..37.$

Ответ:

$p =2,p= 37$

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

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

Число $1001$ выписали на доску $1001$ раз подряд. Получили натуральное число $a.$ Найдите остаток от деления $a$ на $9999.$

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

Подсказка 1

С числом из условия работать трудно, попробуйте его записать в более удобном виде.

Подсказка 2

Чем число меньше, тем проще искать его остаток. Попробуйте как-нибудь разложить изначальное число на множители и найти остатки этих множителей при делении на 9999.

Подсказка 3

Если внимательно посмотреть, то можно заметить, что это число делится на 1001. Подумайте, каким будет второй множитель и какой у него остаток при делении на 9999.

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

Заметим, что это число можно записать в следующем виде:

0 4 8 4000 4 8 4000 1001⋅10 +1001⋅10 +1001⋅10 + ...+ 1001⋅10 = 1001(1+ 10 + 10 +...+10 )

Все слагаемые в скобке сравнимы с $1$ по модулю $9999,$ а значит скобка сравнима с $1001,$ то есть всё число сравнимо с $10012.$ Нетрудно посчитать, что $10012 ≡ 2101 (mod 9999).$

Ответ:

$2101$

Интенсивы

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

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

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

Известно, что $a− 2b$ делится на $m$ и $c− 3d$ делится на $m$ . Докажите, что $ac− 6bd$ делится на $m$ .

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

По условию $a− 2b$ делится на $m$ и $c− 3d$ делится на $m.$ Тогда

a ≡2b (mod m)

c≡ 3d (mod m)

Воспользуемся свойством, что сравнения по одному модулю можно перемножить:

ac≡ 6bd (mod m )

Значит, что $ac− 6bd$ делится на $m.$

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

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

Докажите, что $(3n+ 1)n− 2$ делится на $3n− 2$ для любого натурального $n.$

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

Так как

n n 3 + 1≡ 3 (mod 3 − 2),

то

n n n n (3 +1) − 2 ≡ 3 − 2≡ 0 (mod 3 − 2)

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

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

Известно, что $abc+1$ делится на $ab− b+ 1$ . Докажите, что $ac− a+1$ и $bc− c+1$ — тоже.

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

Подсказка 1

Проводить сравнения в этой задаче будем по модулю ab-b+1. Тогда по условию abc+1 ≡ 0(mod ab-b+1). Доказать же хотим, что bc-c+1≡ 0(mod ab-b+1) и что ac-a+1≡ 0(mod ab-b+1).

Подсказка 2

Одного условия мало, и пока непонятно, что делать с выражением abc+1. Но мы знаем, что число всегда делится на себя само(ноль, конечно, не учитывается). Тогда ab-b+1≡ 0(mod ab-b+1). Как можно использовать полученное сравнение?

Подсказка 3

ab-b+1≡ 0(mod ab-b+1) тоже самое, что ab≡ b - 1(mod ab-b+1).
А вот ab мы уже встречали в abc+1. Тогда можно сделать замену ab на b-1 по модулю ab-b+1 в выражении abc+1≡ 0(mod ab-b+1). Раскройте скобки и получите одну из искомых делимостей!

Подсказка 4

В предыдущей подсказке получили, что bc-c+1≡ 0(mod ab-b+1), а это тоже самое, что bс≡ с-1(mod ab-b+1). Тогда аналогично предыдущей подсказке подставьте полученное сравнение в abc+1≡ 0(mod ab-b+1) и получите вторую из искомых делимостей!

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

Заметим, что

ab− b+ 1≡ 0 (mod ab − b+ 1)

ab≡ b− 1 (mod ab− b+1)

Значит, раз $abc+ 1$ делится на $ab− b +1,$ то

abc+ 1≡ 0 (mod ab − b+ 1)

(b− 1)c+ 1≡0 (mod ab− b+1)

bc − c+ 1≡ 0 (mod ab− b+ 1)

Следовательно, $bc− c+ 1$ делится на $ab− b+ 1,$ а также

bc≡ c− 1 (mod ab− b+1)

Благодаря этому получаем

abc+ 1≡ 0 (mod ab − b+ 1)

a(c− 1)+ 1≡ 0 (mod ab− b+1)

ac − a+ 1≡ 0 (mod ab− b+ 1)

Следовательно, $ac − a+ 1$ делится на $ab− b+1.$

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

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

Докажите, что $11n+2 +122n+1$ делится на 133 при любом натуральном $n$ .

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

Подсказка 1

Рассмотрите 12² и 11² по модулю 133. Может получиться что-то красивое?

Подсказка 2

12² ≡ 11(mod 133), а 11² ≡ -12(mod 133)! Подумайте, как это можно использовать в исходном выражении 11ⁿ⁺² + 12²ⁿ⁺¹.

Подсказка 3

11ⁿ⁺² — это же 11ⁿ⋅11², а 12²ⁿ⁺¹ — это (12²)ⁿ⋅12.

Подсказка 4

Тогда, используя полученные сравнения в подсказке 2, попробуйте сделать в исходном выражении слагаемые вида 11ⁿ⋅12.

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

Заметим, что

2 2 12 ≡11 (mod 133) и 11 ≡− 12 (mod 133)

Тогда

n 2 2n n n 11 ⋅11 +12 ⋅12≡ −12⋅11 +12⋅11 = 0 (mod 133)

Значит, $11n+2+ 122n+1$ делится на 133.

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

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

Вася хочет заполнить квадратную таблицу (криптографическую мозаику) размера $4× 4$ целыми числами от 1 до 16 по следующему правилу. Сначала он выбирает четыре целых числа $b1,b2,b3,b4 ∈{0,1,...,16}$ . Затем первую строку Вася заполняет числами

(1) ai ≡ (bi+1)(mod17), i=1,2,3,4;

вторую строку — числами

(2) ai ≡ (bi+4)(mod17), i=1,2,3,4;

третью

(3) ai ≡(bi+13)(mod17), i= 1,2,3,4

и, аналогично, четвертую

(4) ai ≡ (bi+ 16)(mod17), i=1,2,3,4.

При этом числа $b1,b2,b3,b4$ Вася выбрать должен так, чтобы все числа в таблице оказались различными. Сумеет ли Вася это сделать? Если да, то чему равны $b1,b2,b3,b4$ ?

Источники: Верченко - 2024, 11.6 (см. ikb.mtuci.ru)

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

Подсказка 1

Видите вопрос "сможет ли...?" и сразу руки чешутся как-нибудь доказать, что не получится? :) Давайте сначала успокоимся и попробуем посмотреть на то, что от нас просят. В табличке должны получиться различные остатки по модулю 17, причем эти aᵢ очень подозрительно выглядят... 1 и 16 в сумме дают 17, 3 и 14 тоже.... Что можно сказать?

Подсказка 2

Да, в одном столбце получаются числа bᵢ + 1, bᵢ + 4, bᵢ - 4, bᵢ - 1 (mod 17). Полученная симметрия так и бросается в глаза, правда? Вот бы можно было выбрать какое-нибудь b и наглядно видеть остатки от чисел, которые оно образует... Вам же наверняка тоже не хочется долго перебирать и считать аᵢ

Подсказка 3

А что если остатки по модулю 17 изобразить по кругу? И правда, если мы выберем какое-нибудь число b из круга, то число b+r пойдет по кругу на r шагов от него в сторону увеличения, а b-r, на те же r шагов в сторону уменьшения. Получается, если выбрать какое-нибудь число b, то оно вычеркивает два числа рядом с собой и два числа на расстоянии 4. Получится ли у нас подобрать еще 3 числа так, чтобы вычеркнутые числа не пересекались?

Подсказка 4

Да, получится. Если это вызывает затруднения, заметьте, что само число b в табличку не входит, поэтому оно может быть среди вычеркнутых. Если вы пойдете по кругу от самого первого выбранного вами числа и выберете числа на расстоянии 1, 7 и 11, то у вас точно никакие вычеркнутые числа не пересекутся :)

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

Заметим, что

bi+16= bi+1(mod17)

bi+13= bi− 4(mod17)

Представим остатки полученных $a(ij)$ от $bi$ в виде круга остатков. Числа получаются от $bi$ смещением на $1$ или $4$ шага по часовой или против часовой стрелки в зависимости от знака.

Крестиком выделены полученные числа a(j)то есть столбец в табл&#x0438 i i

$PIC$

Заметим, что важен лишь набор $b1,b2,b3,b4$ , а не их порядок, тогда без ограничения общности выберем пару $b1$ , $b2$ — одно из чисел $(j) a1$ или такое число, которого нет в таблицы. Докажем, что $b2$ тогда обязательно соседняя с $b1$ .

Предположим противное, то есть что ни одна пара $bi$ , $bj$ не являются соседями (так как иначе можем взять их в качестве $b1$ , $b2$ ).

$1$ случай ( $b2 = b1+4(mod 17)$ ): возьмём $b1 =6$ (если все различные числа сдвинуть на одинаковое число по модулю $17$ , то они останутся одинаковыми, а значит мы можем взять $b1 =6$ ), в таблицу уже попали числа: $1,2,3,5,6,7,10,15$ , тогда “запрещённые” позиции — $0,..,11,14,15,16$ (они получены путём прибавления и вычитания $1$ , $4$ по модулю $17$ к полученным клеткам в таблице), а значит, $b3,b4$ — $12,13$ , но тогда они соседи — противоречие.

$2$ случай ( $b2 = b1− 4(mod 17)$ ): переименуем $b1$ , $b2$ в $b2$ , $b1$ и получится случай 1.

$PIC$

$3$ случай ( $b2 = 6$ аналогично, без ограничения общности, не входит в таблицу): Все остальные числа входят, так как с каждой $bi$ в таблицу добавляются по 4 числа. Рассмотрим число $3$ , у нас уже "запрещены"числа $2,5,7,10$ для $b1$ , иначе $b2$ входит в таблицу и $1,3,4,6,8,9,11,15$ , иначе в таблице есть повторяющиеся числа, тогда $b1+ 1!= 3(mod 17)(b1 = 2),b1− 1!= 3(mod 17)(b1 =4),b1− 4!=3(mod 17)(b1 = 7)$ , получается, что $b2+ 4= 3(mod 17)$ , т.е. $b2 = 16)$ .

Посмотрим на “запрещённые” числа для $b3$ : $0,..,12,15,16$ , но $13,14$ снова соседние.

Мы получили, что обязательно должны быть 2 соседних числа. С одной стороны, зачёркнутые ячейки на расстоянии $4$ от $b1$ и $b2$ образуют место для $b 3$ и $b 4$ (поскольку есть две свободные ячейки вокруг двух зачеркнутых чисел). С другой стороны, при выборе двух $b$ , набор двух оставшихся определяется однозначно, поэтому итого вариантов выбора комбинации столько же, сколько и выбор двух подряд идущих чисел в круге, т.е. $17$ .

Один из возмож ных случаев:

$PIC$

Ответ:

$0 1 7 11, 1 2 8 12, 2 3 9 13, 3 4 10 14, 4 5 11 15, 5 6 12 16, 0 6 7 13, 1 7 8 14, 2 8 9 15, 3 9 10 16, 0 4 10 11, 1 5 11 12, 2 6 12 13, 3 7 13 14, 4 8 14 15, 5 9 15 16, 0 6 10 16$

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

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

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

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

Найдите все целые $b$ такие, что при любом натуральном $a$ число $(a2+ 1)100 +b− a$ делится на $a2+ a+1.$

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

Подсказка 1

Давайте посмотрим на сравнения по модулю а² + а + 1. С чем будет сравнимо (а² + 1)? С чем будет сравнимо (а² + 1)¹⁰⁰?

Подсказка 2

(а² + 1) сравнимо с (-а) по модулю а²+а+1. Тогда (а² + 1)¹⁰⁰ будет сравнимо с а¹⁰⁰. Что тогда мы можем сказать про слагаемые с а? Про b?

Подсказка 3

Тогда мы можем свернуть слагаемые с а в произведение а(а⁹⁹ - 1). Давайте докажем, что это число всегда будет делиться на а² + а + 1. Но как нам это сделать?

Подсказка 4

Надо воспользоваться формулой разности кубов! Осталось лишь понять, какие b нам будут подходить. Не забудьте, что в условии написано «при любом натуральном а»!

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

Заметим, что $a2+1$ сравнимо с $− a$ по модулю $a2+ a+ 1,$ а значит, $(a2+1)100+ b− a$ сравнимо с

100 100 99 (−a) + b− a= a + b− a =a(a − 1)+ b

Заметим, что $a99 − 1$ делится на $a3− 1= (a − 1)(a2+ a+ 1).$ То есть необходимое и достаточное условие — делимость $b$ на $a2+ a+ 1$ для любого натурального $a,$ что возможно лишь при $b= 0.$

Ответ:

$b= 0$

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

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

Натуральные числа $a,b,c$ таковы, что $ab− cd$ делится на $a +b+ c+ d.$ Докажите, что $a+ b+ c+d$ — составное.

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

Предположим противное, тогда число

p =a +b+ c+ d — простое

и имеет место сравнение

d≡ −(a+ b+c) (mod p)

Из условия получим сравнение

ab≡ cd (mod p)

следовательно,

ab≡ −c(a+b+ c) (mod p)

что после преобразование равносильно

(a+ c)(b+ c)≡ 0 (mod p)

но тогда по крайней мере одно из чисел $a+ c< p$ и $b+c< p$ делится на $p,$ что влечет противоречие.

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

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

(a) Известно, что $2 2 (4a − 1)$ делится на $4ab − 1.$ Докажите, что $2 (a− b)$ — тоже.

(b) Известно, что $n3+ 1$ делится на $mn − 1.$ Докажите, что $m3+ 1$ — тоже.

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

(a) Перепишем условие на делимость в виде сравнения и домножим обе части на $2 b$

2 2 2 b(4a − 1) ≡ 0 (mod 4ab− 1)

Заметим, что $4ab≡1 (mod 4ab− 1),$ следовательно,

2 2 2 2 2 2 0≡ b(4a − 1) ≡ (4a b− b) ≡ (a − b) (mod 4ab− 1)

что влечет требуемое.

(b) Перепишем условие на делимость в виде сравнения и домножим обе части на $m3$

3 3 m (n + 1)≡0 (mod mn − 1)

Заметим, что $mn ≡ 1 (mod mn − 1),$ следовательно,

0≡ m3(n3+ 1) ≡(mn)3+ m3 ≡ 1+ m3 (mod mn − 1)

что влечет требуемое.

Ответ:

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

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

Пусть $a$ и $b$ - целые числа. Докажите, что если $a2+ 9ab+ b2$ делится на $11$ , то и $a2 − b2$ делится на $11.$

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

Так как выражение из условия делится на $11$ , то после вычитания из него $11ab$ получится кратное $11$ число.

2 2 2 a + 9ab− 11ab+b = (a− b)

Итак, $(a− b)2$ кратно $11$ , откуда $a− b$ также делится на $11$ , поскольку это число простое. Остаётся заметить, что $a2− b2 = (a− b)(a+ b)$ кратно $a − b$ , потому также кратно $11$ .

Ответ:

что и требовалось доказать

Следующая подтема