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

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

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

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

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

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

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

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

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

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

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

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

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

Предположим, что $x= n2$ — число, состоящее из $21$ единициы и нескольких нулей. Тогда сумма цифр этого числа равна $21.$ По признаку делимости на $3$ и $9$ данное число делится на $3,$ но не делится на $9.$ (так как сумма цифр делится на $3,$ но не делится на $9$ )

Однако $2 n$ либо не делится на $3,$ либо делится сразу на $9.$ Следовательно, возникает противоречие, и мы приходим к выводу, что числа, состоящего из $21$ единицы и некоторого количества нулей, не существует.

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

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

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

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

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

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

Рассмотрим таблицу остатков при делении квадратов на 4:


$x$	$x2$

$0$	$0$

$1$	$1$

$2$	$0$

$3$	$1$

Заметим, что нечётные числа могут давать остатки 1 и 3 при делении на 4, соответственно, квадраты нечётных чисел будут давать осаток 1. Таким образом, сумма квадратов трёх нечётных чисел будет сравнима с $1+ 1+1 =3$ по модулю 4, а квадрат целого числа не может давать остаток 3 при делении на 4. Отсюда, сумма квадратов трёх нечётных чисел не может быть квадратом целого числа.

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

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

Можно ли в числе 123456 переставить цифры так, чтобы оно стало квадратом?

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

Предположим, что это возможно. Тогда сумма цифр этого квадрата $21.$ Следовательно, число делится на $3.$ Но раз это квадрат, то он должен делиться на $9,$ но сумма цифр не делится на $9,$ значит, это невозможно.

Ответ: нет

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

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

Докажите, что не существует натуральных чисел $b> a+ 1,$ для которых число $b(2a+ b)2023− a(2b+ a)2023$ является простым.

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

Подсказка 1

Можем ли мы найти какой-то модуль, по которому остаток выражения будет 0?

Подсказка 2

В условии не просто так дано, что b>a+1. Это даёт нам, что b-a>1. Конечно, подходящий для делимости модуль должен быть больше 1.

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

Пусть $x =b− a.$ Покажем, что значение выражения делится на $x.$ Далее все сравнения по модулю $x.$

2023 2023 2023 2023 (a+ x)(3a+x) − a(2x+ 3a) ≡a(3a) − a(3a) ≡ 0

То есть это выражение делится на $x> 1.$ Оно больше, чем $x,$ поэтому является составным числом.

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

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

Вадим выписывает числа на доску. Изначально он пишет на доске какое-то число, большее $100.$ Далее Вадим берет число $x,$ выписанное последним, и дописывает на доску число $2 x − 1.$ Может ли Вадим выбрать начальное число так, чтобы для любого простого числа рано или поздно на доске появилось число, которое делится на это простое?

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

Подсказка 1

Предположим, что изначально остаток по модулю р для какого-то р был произвольным? Каким он должен стать, чтобы прийти в итоге к делимости через х²-1?

Подсказка 2

Мы должны прийти к остатку 1 по модулю р (почему к -1 не получится?). Для этого должно быть разрешимо уравнение x²≡2 (mod p). Для каких р это сравнение неразрешимо?

Подсказка 3

Сравнение неразрешимо для p=8k+3 или p=8k+5. Чтобы это доказать, стоит рассмотреть произведение чётных чисел, меньших р и нечётных, меньших р. Можем ли мы выбрать такое р, чтобы остаток у n по его модулю был не 1?

Подсказка 4

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

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

Далее все сравнения по модулю $p.$ Заметим, что если исходно $x$ не делилось на $p,$ то мы должны на каком-то шаге получить $x2 ≡ 1.$ Значит, или $x≡ 1$ или $x ≡− 1.$ Во втором случае остаток $− 1$ мы могли получить только из $2 x − 1≡ −1,$ но тогда $p|x,$ чего не бывает. Значит, на каком-то шаге $2 x ≡ 2.$

______________________________________________________________________________________________________________________________________________________

Найдём для начала такие простые числа, для которых не существует решения такого уравнения в целых числах.

p−1- p− 1 p−1- 2 2 ⋅(1⋅2⋅...⋅-2--)= 2⋅4 ⋅...⋅(p− 1)≡ (−1)⋅(p− 2)⋅...⋅(−1)⋅1= 1⋅3⋅...⋅(p− 2)⋅(−1)2

Теперь заменим четные числа $a$ из левой скобки на $(− 1)⋅(p− a).$ Пусть $p= 8k+ 3.$ Тогда этих чётных чисел $2k.$

p−1 2-2-⋅(1⋅3⋅...⋅(p− 2))⋅(− 1)2k ≡ 1⋅3⋅...⋅(p− 2)⋅(−1)4k+1

Значит, $p−1- 2 2 ≡ −1$ для $p=8k +3.$ Пусть $p= 8k+ 5.$ Тогда этих чётных чисел $2k+ 1.$

p−1 2 2 ⋅(1⋅3⋅...⋅(p− 2))⋅(− 1)2k+1 ≡ 1⋅3⋅...⋅(p− 2)⋅(−1)4k+2

Значит, $p−1- 2 2 ≡ −1$ для $p=8k +5.$

______________________________________________________________________________________________________________________________________________________

Покажем, что простых вида $8k+ 4± 1$ бесконечно много. Пусть их конечно, они $p1,p2,...,pn.$ Рассмотрим число $72p1p2...pn+ 3.$ Оно даёт остаток $3$ по модулю $8,$ при этом не делится на $9,$ поскольку первое слагаемое делится, а второе — нет. Также оно не делится на все из простых чисел нужного вида (кроме тройки, но она только в первой степени). Значит, имеется ещё какой-то делитель нужного вида (ведь мы не можем получить остаток $3$ по модулю $8$ произведением остатков $±1).$

______________________________________________________________________________________________________________________________________________________

Пусть есть решение у $x2 ≡ 2.$ Возведём в степень $p−1 -2-.$ Тогда для $p= 8k+ 4± 1:$

1≡ xp−1 ≡ 2p−21≡ −1

Противоречие, поэтому такого $x$ не найдётся. Для выбранного Вадимом начального числа $a$ найдём достаточно большое $p$ вида $8k+ 4± 1,$ тогда изначально остаток по модулю $p$ у числа $a$ не $0,1$ и не $− 1.$ Значит, после наших операций никогда не получится числа, делящегося на $p.$

Ответ:

Не может

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

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

Дана последовательность целых чисел $a ,a,.... 1 2$ Оказалось, что для каждого натурального $n$ можно указать такое натуральное $m,$ что члены $ai$ и $aj$ дают одинаковые остатки при делении на $n$ тогда и только тогда, когда $i$ и $j$ дают одинаковые остатки при делении на $m.$ Докажите, что последовательность $a1,a2, ...$ периодична или является арифметической прогрессией.

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

Обозначим число $m$ из условия через $f(n).$ Предположим, что существуют такие натуральные числа $x > y,$ что $a =a . x y$ Тогда поскольку $.. (ax− ay).n$ для любого $n,$ разность $x− y$ делится на $f(n).$ При всех $n$ числа $i+ x− y$ и $i$ дают одинаковые остатки при делении на $f(n),$ следовательно, при всех $n$ числа $ai+x−y$ и $ai$ дают одинаковые остатки при делении на $n.$ Значит, $ai = ai+x−y$ при всех $i,$ т.е. последовательность $(ai)$ периодическая с периодом $x− y.$

Теперь предположим, что последовательность $(ai)$ состоит из различных чисел. Так как $.. (a2− a1).1,$ то $.. (2− 1).f(1),$ т.е. $f(1) =1.$ Далее, при $n> a2− a1$ получаем, что $(a2 − a1)$ не кратно $n,$ следовательно, $(2− 1)$ не кратно $f(n).$ В частности, $f(n)⁄= 1$ при $n> a2− a1.$ Пусть $t1 > t2 > ⋅⋅⋅>tℓ = 1$ — это все решения уравнения $f(x)= 1.$ Так как $.. (i− j).f(ts) =1,$ то $.. (ai− aj).ti.$ Значит, все числа в последовательности $(ai)$ дают одинаковый остаток при делении на $ti,$ а значит, и при делении на $НОК (t1,t2,...,tℓ).$ Следовательно, $f(НОК (t1,t2,...,tℓ))= 1.$ То есть $t1 = НОК (t1,t2,...,tℓ)$ и $.. t1.ti$ для любого $i.$

Предположим, что $|az+1− az|⁄=t1$ для некоторого $z.$ Так как все $ai$ дают одинаковый остаток при делении на $t1,$ выполняется равенство $|az+1− az|=ht1,$ где $h > 1,h∈ ℕ.$ Но тогда $. ((z+1)− z)..f(ht1),$ то есть $f(ht1)=1.$ Но $ht1 >t1,$ противоречие. Значит, $|ai+1− ai|= t1$ при всех $i.$ Тогда или $(ai)$ — это арифметическая последовательность с разностью $t1,$ или найдётся такое $i,$ что $ai = ai+2.$ Во втором случае мы уже доказали в начале решения, что последовательность получится периодическая. Что и требовалось доказать.

Курсы

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

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

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

Сумма цифр числа $n$ равна сумме цифр числа $2n +1.$ Может ли и у числа $7n+ 3$ быть такая же сумма цифр?

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

Если суммы цифр двух чисел равны, то равны и их остатки при делении на $9,$ откуда $2n+ 1− n = n+ 1$ делится на $9.$ Поэтому $n$ дает остаток $8$ при делении на $9,$ но тогда число $7n+ 3$ дает остаток $5$ при делении на $9$ — противоречие.

Ответ:

Не может

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

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

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

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

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

Подсказка 1

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

Подсказка 2

Остатки при делении на 2, 3, 4 у чисел одной прогрессии будут одинаковы, ведь 12 делится на 2, 3 и 4. Остатки на какое число следует рассмотреть?

Подсказка 3

Остатки при делении на 5 у всех пяти чисел прогрессии будут отличаться между собой, но ведь есть лишь 5 различных остатков при делении на 5.

Подсказка 4

Следовательно, одно из чисел гарантированно делится на 5. Все числа прогрессии простые, тогда число 5 в ней есть. Осталось найти остальные числа прогрессии, зная разность.

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

Посмотрим на остатки по модулю $5,$ заметим что все остатки различны, поэтому из пяти членов арифметической прогрессии обязательно встретится число кратное $5,$ так как оно простое, то оно равно $5,$ поэтому если такая прогрессия существует, то она начинается с $5.$ И вправду в ряду $5,$ $17,$ $29,$ $41,$ $53$ все числа просты.

Ответ: 5; 17; 29; 41; 53

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

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

Миша выписал все остатки от деления некоторого числа $N$ на $120,121,...,160$ . При этом оказались выписаны в каком-то порядке все числа от $43$ до $83$ . Докажите, что число $N$ составное.

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

Подсказка 1

Введите переменные, обозначающие остатки от деления N на 120 и 160. Это два числа, у которых общий множитель 40 — поэтому остатки должны быть одинаковы и при делении на 40. Какими числами они могут быть из остатков из условия?

Подсказка 2

Да, это 43 и 83 в каком-то порядке. А что мы можем сказать об остатке при делении N на 140? 120, 140, 160… Что между ними общего?

Подсказка 3

Конечно, 120, 140, 160 делятся на 20. Надо, чтобы остаток по делении на 120 отличался от 43 и 83 только на 20k, где k - целое число. Такой только 63. Отлично, получилось, что N = 140k + 63. Составное ли это число?

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

Рассмотрим остатки при делении на $120,160$ . Заметим, что они сами должны давать одинаковый остаток при делении $40$ , поскольку

N = 120n +p =160m +q =⇒ N =40⋅3n+ p= 40⋅4m + q

То есть числа $p,q$ дают тот же остаток при делении на $40$ , что и само число $N$ . Отсюда делаем вывод, что это обязательно числа $43$ и $83$ в каком-то порядке (все остальные остатки при делении на $40$ встречаются в единственном экземпляре). Теперь рассмотрим остаток при делении на $140$ . Заметим, что

N = 140k+t =40⋅3n+ 43 или 40⋅3n+ 83

из доказанного выше. В каждом из случаев первое слагаемое кратно $20$ , как и $140k$ , то есть числа $t$ и $43$ (или, что то же самое, $83$ ) дают один и тот же остаток при делении на $20$ . Получили, что $t$ даёт остаток $3$ при делении на $20$ .

Отсюда $t= 63$ , то есть остаток $N$ при делении на $140$ может быть равен только $63$ (другие остатки, дающие $3$ при делении на $20$ , уже закончились). Итак, $N = 140k+ 63$ и кратно $7$ . Поскольку оно, очевидно, больше $7$ , то является составным.

Замечание. Про заключительную делимость $7$ можно было догадаться, если придумать несложный пример $N = 203= 7⋅29$ , откуда становится понятно, что мы хотим думать именно про $7$ .

Ответ:

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

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

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

Натуральное число $m$ разбили на сумму нескольких натуральных слагаемых $m= a + a +...+a 1 2 n$ (не обязательно различных). Оказалось, что $3 3 3 a1+ a2+...+an = 6m$ . При каких $m$ такое могло произойти?

Источники: 61 УТЮМ

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

Легко проверить, что $a3 ≡ a (mod 6)$ , поэтому если сумма кубов чисел делится на 6, то и просто сумма делится. Для $m = 6k$ подойдет пример из $k$ единиц, $k$ двоек и $k$ троек.

Ответ:

при $m = 6k$ , где $k∈ ℕ$

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

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

Докажите, что число $A= 2n+ 3n+ 5n +6n$ не является точным кубом ни при каком натуральном $n.$

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

Предположим противное. Пусть $n$ четно. Несложно видеть, что $A$ кратно $2,$ а значит кратно $8.$ С другой стороны при $n >2$ верно, что

n n n n n n n (2 + 6 )+3 +5 ≡ 0+ (−5) +5 ≡ 2⋅5 ⁄= 0(mod8)

при $n= 1$ имеем $A = 16,$ что не является кубом натурального числа.

Пусть $n$ нечетно. Заметим, что ${−1,1,0}$ — множество остатков кубов по модулю $7,{3,5,6}$ — множество остатков, которые дают нечетные степени 3 при делении на $7.$ Осталось заметить, что

n n n n n n n n n 2 +3 + 5 + 6 ≡ 2 +3 − 2 − 1 ≡ 3 − 1= {2,4,5}(mod7)

тем самым получили противоречие.

Интенсивы

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

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

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

На доску записывают пары чисел. Сначала на доску записали пару чисел $(1,2).$ Если на доске написана пара чисел $(a,b),$ то на доску можно дописать пару $(−a,− b),$ а также пару $(−b,a+ b).$ Кроме того, если на доске написаны пары чисел $(a,b)$ и $(c,d),$ то на доску можно дописать пару $(a+c,b+d).$ Могла ли через некоторое время на доске оказаться пара $(2022,2023)?$ Порядок чисел в паре существенен, например, пары чисел (1, 2) и (2, 1) считаются различными.

Источники: ВСОШ, РЭ, 2023, 11.4 (см. olympiads.mccme.ru)

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

Подсказка 1:

Попробуйте найти какой-нибудь инвариант при таких операциях.

Подсказка 2:

Рассмотрите выражение 2a – b. Как оно меняется при применении операций к паре (a, b)?

Подсказка 3:

Обратите внимание на остаток от деления 2a – b на 7. Как он меняется?

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

Первое решение. Докажем, что для любой пары $(x,y),$ записанной на доске, число $2x− y$ делится на $7.$

Действительно, для пары $(1,2)$ число $2⋅1− 2= 0$ делится на 7.

Пусть для пары $(a,b)$ число $2a − b$ делится на $7.$ Тогда для пары $(−a,− b)$ число

2⋅(− a)− (−b)=− (2a− b)

делится на $7,$ и для пары $(−b,a +b)$ число

2⋅(−b)− (a +b)= −a− 3b=3(2a− b)− 7a

делится на $7.$

Пусть для пар $(a,b),(c,d)$ числа $2a − b,2c − d$ делятся на 7. Тогда для пары $(a+c,b+ d)$ число

2(a+ c)− (b+ d)= (2a− b)+ (2c− d)

делится на $7.$

Так как для пары $(2022,2023)$ число

2⋅2022− 2023= 2021

не делится на $7,$ эта пара на доске появиться не может.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Будем к каждой паре $(a,b)$ на доске добавлять третье число $c= −a − b.$ Тогда сумма чисел в каждой тройке будет равна нулю, а правила дописывания новых пар будут такими: если на доске записана тройка $(a,b,c),$ то можно дописать тройки $(−a,−b,− c)$ и $(−b,−c,−a),$ а если записаны тройки $(a,b,c)$ и $(d,e,f),$ то можно дописать тройку $(a +d,b+ e,c+ f)$ — назовём эту тройку суммой троек $(a,b,c)$ и $(d,e,f).$ Также для тройки $(a,b,c)$ и целого числа $k$ обозначим через $k ⋅(a,b,c)$ тройку $(ka,kb,kc).$

______________________________________________________________________________________________________________________________________________________

Утверждение. Докажем, что все тройки, появляющиеся на доске, имеют вид

(a,b,c)=k ⋅(1,2,−3)+ ℓ⋅(2,−3,1)+ m ⋅(−3,1,2) (∗)

с целыми $k,$ $ℓ$ и $m.$ В начальный момент времени это верно:

(1,2,−3)= 1⋅(1,2,−3)+0 ⋅(2,− 3,1)+ 0⋅(− 3,1,2).

Теперь достаточно показать, что из троек, имеющих вид $(∗),$ также получаются лишь такие тройки. Для операции взятия суммы троек это очевидно. Для остальных операций это тоже несложно проверить: если $(a,b,c)$ имеет вид $(∗),$ то

(−a,−b,− c)= (−k)⋅(1,2,− 3)+ (−ℓ)⋅(2,−3,1)+ (− m)⋅(−3,1,2),

(−b,−c,−a)= (−m)⋅(1,2,−3)+ (−k)⋅(2,− 3,1)+ (−ℓ)⋅(−3,1,2).

Утверждение доказано.

_________________________________________________________________________________________________________________________________________________________________________________

Предположим теперь, что на доске появилась тройка (2022, 2023, -4045), то есть она имеет вид $(∗).$ Тогда имеем

2022= k+2ℓ− 3m и 2023= 2k− 3ℓ+ m.

Выражая из первого равенства $k =2022− 2ℓ+ 3m$ и подставляя во второе, получаем

2023= 2⋅2022− 7ℓ+7m,

то есть

7(m − ℓ)= 2023− 2⋅2022 =− 2021.

Однако это невозможно, поскольку $2021$ не делится на $7.$

Ответ:

не могла

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

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

Изначально на доске написано 10 единиц. Гриша и Глеб играют в игру, делая ходы по очереди. Своим ходом Гриша возводит некоторые 5 чисел на доске в квадрат. Глеб своим ходом выбирает несколько (возможно, ни одного) чисел на доске и увеличивает каждое из них на 1. Если в течение 10 000 ходов на доске появится число, делящееся на 2023, то побеждает Глеб, иначе побеждает Гриша. Кто из игроков имеет выигрышную стратегию, если первым ходит Гриша?

Источники: ВСОШ, ЗЭ, 2023, 11.5 (см. olympiads.mccme.ru)

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

Подсказка 1:

Для начала будет полезно изучить само число 2023, 2023 = 7*17². Теперь нужно попытаться угадать ответ, кто же победит?

Подсказка 2:

Пусть Глеб имеет выигрышную стратегию. Тогда он всегда за 10000 ходов успевает добиться делимости. Не кажется ли Вам, что 10000 просто для красоты?

Подсказка 3:

Действительно, это просто красивое число. Значит, побеждает Глеб, и он должен добиваться делимости за не более чем какое-то количество ходов, причём предварительно количество нужно будет угадать и только потом доказывать, что он это сможет сделать. Либо побеждает Гриша, и тогда нужно доказать, что он всегда может поддерживать НЕделимость чисел на 2023. Кажется, проще сначала попробовать доказать второй вариант, ибо достаточно просто придумать алгоритм.

Подсказка 4:

Итак, хотим доказать, что Гриша может всегда "сломать" делимость на 2023, но рассуждать именно про делимость 2023 сложновато, не зря же мы вначале разложили его на множители) Будем пробовать доказать, что Гриша может всегда "сломать" делимость на 7 (7 < 17 и они оба простые, поэтому логичнее начать с 7).

Подсказка 5:

Информации о конкретном числе в ключе "делится или не делится на 7" нам недостаточно. Что же может нам помочь, когда речь идёт о делимости?

Подсказка 6:

Конечно же, модульная арифметика! Рассмотрите, как операция Гриши влияет на остатки.

Подсказка 7:

Если число не делилось на 7 до хода Гриши, то после оно будет давать остаток 1 либо 2, либо 4 по модулю 7. В то же время Глеб может прибавить 1 к остатку своим ходом. На какие мысли об алгоритме Гриши это наталкивает?

Подсказка 8:

Подумаем вот о чём... Гриша возвёл в квадрат некоторое число а, получил a². На какое максимальное количество ходов он может забыть про него? То есть сколько раз подряд он может позволить Глебу изменить число a²?

Подсказка 9:

Если на ≥ 3 хода. То есть a² сравнимо с 4, то за 3 хода Глеб может победить. Значит, забывать про число Гриша может максимум на два хода Глеба. Что это значит?

Подсказка 10:

Если зафиксировать какое-то число, то минимум каждые два хода Гриша должен с ним взаимодействовать (осознайте, что этого достаточно). Осталось придумать такую стратегию... Вам может помочь идея разбиения на группы. Успехов!

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

Заметим, что $2023= 7⋅172.$ Гриша разобьёт числа на доске на две группы по 5 и будет возводить в квадрат числа из первой группы и из второй группы по очереди. Легко видеть, что квадраты целых чисел, не кратных 7, при делении на 7 могут давать лишь остатки 1, 2 и 4. Следовательно, после увеличения максимум на 2 числа на доске будут давать при делении на 7 лишь остатки 1, 2, 3, 4, 5 и 6. Значит, ни одно из чисел не будет делиться на 7, а потому не будет делиться и на 2023.

Ответ:

побеждает Гриша

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

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

Докажите, что число $22022+41$ можно представить в виде произведения четырёх натуральных чисел, каждое из которых больше единицы.

Источники: по мотивам задачи 3 из ОММО - 2013

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

Покажем, что число из условия делится на $3,5,7$ :

Начнём с $3$ :

$2 2022 1011 2022 2 ≡1 (mod 3)=⇒ 2 ≡ 1 ≡ 1 (mod 3)⇐ ⇒ 2 + 41 ≡42≡ 0 (mod 3)$

Аналогично с $5$ и $7$ :

$4 2020 2022 2022 2 ≡1 (mod 5)=⇒ 2 ≡ 1 (mod 5)⇐⇒ 2 ≡ 4 (mod 5) ⇐⇒ 2 + 41 ≡0 (mod 5)$

$3 2022 2022 2 ≡1 (mod 7)=⇒ 2 ≡ 1 (mod 7)⇐⇒ 2 + 41 ≡42 ≡0 (mod 7)$

Очевидно, что $2022 2 + 41 >3⋅5⋅7$ , поэтому $2022 2 +41 =3⋅5⋅7⋅n,$ причём $n >1$ , поэтому мы получили искомое представление.

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

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

Докажите, что сумма $22+ 44+ ...+ 5050$ не является квадратом целого числа.

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

Подсказка 1

Что интересного можно сказать про каждое из слагаемых? Чем оно является?

Подсказка 2

Конечно, квадратом! А по какому модулю нам выгодно смотреть на четное число, которое является квадратом?

Подсказка 3

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

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

В данной сумме все числа и показатели степеней чётные, поэтому все числа являются квадратами. Известно, что квадраты целых чисел по модулю $3$ могут давать остатки только $0$ и $1$ ( $2 2 ≡3 1$ ).

Среди $25$ слагаемых в этой сумме $8$ чисел делятся на $3$ ( $6 12 48 6,12 ...48$ ), а остальные $17$ дают остаток $1$ (ещё раз: квадрат, не кратный $3,$ даёт остаток $1$ ). Отсюда $2 50 2 +...+50 ≡3 17⋅1+ 8⋅0≡3 2.$

Сумма даёт остаток $2$ по модулю $3.$ А квадрат целого числа не может давать такой остаток. Значит, сумма не является квадратом, что и требовалось.

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

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

Является ли число

10102013 102013 2013 10 + 10 +10 − 1

простым?

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

На эти десятки в огромных степенях удобно посмотреть по модулю $11:$

2013 10k 10 10 ≡11−1 =⇒ 10 ≡11− 1 ≡1110, 10 ≡11(−1) = 1

Отсюда для исходного выражения

102013 2013 1010 +1010 + 102013− 1 ≡111+1 − 1− 1= 0

Число из условия больше $11$ и делится на $11$ , потому не является простым.

Ответ:

нет

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

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

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

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

Может ли десятичная запись точного квадрата состоять из 100 нулей, 100 единиц, 100 двоек и 100 троек?

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

Сумма цифр данного числа равна 600. По признаку делимости на 3, это число делится на 3, но по признаку делимости на 9, оно не делится на 9. А любой квадрат, делящийся на 3, делится еще и на 9, значит, любое составленное число не является квадратом.

Ответ: Нет, не может

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

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

У числа $2100$ нашли сумму цифр, у результата снова нашли сумму цифр, и т. д. В конце концов получилось однозначное число. Найдите его.

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

Заметим, что при описанной операции остаток число по модулю 9 не меняется. Поэтому найдем остаток исходного числа при делении на 9. Мы занимались подобными вычислениями в Примере 2, и получали цикл длины 6: 2, 4, 8, 7, 5, 1. Число $100≡ 4 (mod 9)$ , поэтому $100 2$ будет четвертым числом в этом цикле, то есть давать остаток 7 при делении на 9. Тогда и полученное в конце однозначное число должно давать остаток 7 при делении на 9, а такое число только одно — сама семерка.

Ответ: 7

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

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

Найдите все натуральные $n$ , при которых числа $n+ 1$ , $n+ 71$ и $n +99$ — простые.

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

Заметим. что для любого натурального $n$ три наших числа дают разные остатки по модулю 3, тогда какое-то из трех чисел делится на 3, но единственное простое число, делящееся на 3, это число 3. Тогда $n+ 1= 3$ , то есть $n= 2$ . Легко видеть, что число 2 нам подходит.

Ответ: 2

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

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

Найдите все числа вида $22...2,$ которые можно представить в виде суммы двух точных квадратов. Если ответов несколько, введите их через пробел в порядке возрастания.

Источники: Муницип - 2022, Тульская область, 8.5

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

Подсказка 1

Может, можно выбрать какой-то хороший модуль, по которому можно провести сравнение для суммы двух квадратов и для числа такого вида?

Подсказка 2

Рассмотрите все по модулю 8)

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

Пусть $22...2 =a2+ b2$ для некоторых целых чисел $a$ и $b.$ Если числа $a$ и $b$ чётны, то сумма их квадратов делится на $4$ , а число $22...2$ — нет. Таким образом, числа $a$ и $b$ могут быть только нечетными:

a= 2k+1, b=2l+ 1 (k, l∈Z )

Следовательно, сумма

2 2 2 2 a +b = (2k+1) + (2l+ 1) = 4k(k+ 1)+ 4l(l+ 1)+2

при делении на $8$ дает в остатке $2.$

С другой стороны, среди чисел вида $222...2$ только число $2$ при делении на $8$ дает в остатке $2$ , поскольку если число двоек в этом числе больше $1$ , то $22...2 =22...2200+ 22$ , при этом первое слагаемое полученной суммы делится на $8$ , а второе при делении на $8$ дает в остатке $6.$

Ответ: 2