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

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

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

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

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

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

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

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

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

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

Задача 1#85917

Дано натуральное $n >1.$ Докажите, что существуют $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)

что и требовалось.

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

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

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

Задача 2#89212

Натуральные числа $a$ и $b$ таковы, что $ab+ 1$ делится на $b+2.$ Докажите, что $2a> b.$

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

Подсказка 1

Подумайте, за счëт чего одно натуральное число может быть больше другого.

Подсказка 2

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

Подсказка 3

Если применять предыдущие подсказки к задаче, то становится ясно, что нужно доказать некоторую делимость, из которой будет следовать, что 2a > b. Попробуйте рассмотреть число ab+1 по модулю b + 2. Что можно про него сказать, с какими числами оно сравнимо?

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

Заметим, что $b≡ −2 (mod b+2),$ откуда $ab+ 1≡ −2a+ 1 (mod b+2).$ Значит, $2a− 1$ кратно $b+2,$ откуда $2a− 1 ≥b+ 2,$ то есть $2a≥ b+ 3> b,$ что и требовалось.

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

Задача 3#89217

Даны натуральные числа $a,b,c.$ Оказалось, что $b2+ c2− a2$ делится на $a+ b+ c.$ Докажите, что $a+ b+ c$ — составное.

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

Подсказка 1:

Попробуйте рассуждать от противного, пусть a + b + c - простое, поищите противоречие. Подумайте, каким оно может быть в этой задаче.

Подсказка 2:

Вспомним известный факт. Если некоторое число mn делится на простое число p, то либо m кратно p, либо n. Попробуйте получить подобную делимость, используя условие.

Подсказка 3:

Если оба числа m и n будут меньше p, то делимость будет невозможна. Попробуйте найти такое число mn, делящееся на a + b + c, и вы решите задачу.

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

Вспомним известное тождество $(a+ b+c)2 = a2+b2+ c2 +2(ab+bc+ ac).$ Перепишем его в следующем виде:

2 2 2 2 2 (a+b+ c) =b + c − a + 2(ab+ bc+ac+ a)

Числа $(a+ b+ c)2$ и $b2+c2− a2$ делятся на $a+ b+c,$ а значит и число $2(ab+ bc+ac+ a2)$ также будет делиться на $a+ b+c.$ Заметим, что

2 2(ab+ bc+ ac+a )= 2(a +c)(a+ b)≡2bc (mod a+b+ c)

То есть $2bc$ делится на $a+ b+ c.$

Предположим, что $a+ b+ c$ — простое. Тогда есть $3$ случая:

$1)2$ кратно $a+ b+ c,$ но тогда $2= a+ b+ c,$ что невозможно, потому что $a+ b+ c≥ 3,$ потому что числа натуральные.

$2)b$ кратно $a+ b+c,$ что также невозможно, потому что $b< a+ b+ c.$

Аналогично разбирается случай, когда $c$ кратно $a+ b+ c.$

Пришли к противоречию, значит $a+ b+c$ — составное.

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

Задача 4#89222

Докажите, что существует лишь конечное число натуральных $n,$ для которых $10n10+ 9n9+...+2n2+ n+ 1$ делится на $n − 10.$

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

Подсказка 1

Попробуйте рассмотреть задачу попроще. Докажите, что существует конечное количество натуральных n таких, что 10 кратно n - 10. Это очевидно, так как 10 конкретное число, оно имеет лишь конечное число делителей.

Подсказка 2

Посмотрите на многочлен из условия по модулю n - 10. Подумайте, с чем он сравним. Возможно, он сравним с каким-то конкретным числом, тогда задача станет похожа на задачу из подсказки 1.

Подсказка 3

Ясно, что если мы найдем остаток при делении n на n - 10, то мы найдем и остаток при делении многочлена n - 10. Чему он равен?

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

Обозначим многочлен $10n10 +9n9+ ...+ 2n2 +n +1$ через $f(n).$ Ясно, что $n≡ 10 (mod n− 10).$ Значит, $f(n)≡f(10) (mod n − 10).$ То есть делимость $f(n)$ на $n− 10$ равносильна делимости $f(10)$ на $n− 10.$ Очевидно, что существует лишь конечное количество $n,$ подходящее под эту делимость, потому что у $f(10)$ конечное количество делителей.

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

Задача 5#89225

Докажите, что $pp+2 +(p+ 2)p ≡ 0 (mod 2p+2),$ где $p> 2$ — простое число.

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

Подсказка 1

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

Подсказка 2

Их сумма равна 2p+2 и равна модулю, по которому ведется сравнения. Как это можно использовать?

Подсказка 3

В частности, это значит, что одно из чисел сравнимо с числом, противоположным по знаку со вторым, так p+2≡-p по модулю 2p+p. Какой вид теперь имеет сравнение?

Подсказка 4

Левая часть p^{p+2}-p^p=p^p(p^2-1). Как теперь можно закончить решение?

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

p+2 p p+2 p p + (p+2) ≡ p +(−p) (mod 2p+ 2)

Поскольку $p> 2$ простое, то оно и нечетное. Значит,

p+2 p p+2 p p 2 p p + (−p) ≡ p − p ≡ p (p − 1)≡ p(p− 1)(p+1) (mod 2p+2)

Поскольку $p+ 1...p+ 1$ и $p− 1 ...2,$ то $pp(p− 1)(p+1)≡ 0 (mod 2p+2)$

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

Задача 6#89227

Натуральные числа $x$ и $y$ таковы, что $(ax+ by)2022+ (bx+ ay)2022$ делится на $a+ b$ для любых натуральных $a,b.$ Докажите, что $x =y.$

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

a сравнимо с -b по модулю a+b. Этот факт сильно упрощает выражение. Подумайте, как теперь свести задачу к противоречию из 1 подсказки.

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

Заметим, что $a≡ −b (mod a+b).$ Значит,

2022 2022 2022 2022 (ax +by) +(bx+ay) ≡ 2b (x− y) (mod a+ b)

Получается, что $2b2022(x − y)2022$ кратно $a+ b$ при любом $a$ и $b.$ Давайте зафиксируем $b.$ Тогда понятно, что если число $2b2022(x − y)2022$ ненулевое, то тогда найдётся такое $a,$ что $a+ b$ будет больше, чем $2b2022(x− y)2022,$ то есть делимости не будет. Значит, $2b2022(x − y)2022 = 0,$ откуда $x =y.$

Курсы

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

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

Задача 7#89228

Натуральные числа $x,y,z$ и $n$ таковы, что $n= xy+ yz+zx,$ а число $(x+ y)50+ (y +z)50 +(z+ x)50$ делится на $n.$ Докажите, что существуют натуральные числа $a,b$ и $c,$ меньшие $n,$ и такие, что число $100 100 100 a + b + c$ делится на $n.$

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

Подсказка 1:

Попробуйте провернуть некоторые манипуляции с изначальным выражением, чтобы получить выражение формата a^100 + b^100 + c^100, делящееся на n.

Подсказка 2:

С выражениями x + y, y + z, z + x очень трудно работать по модулю xy+xz+yz. Попробуйте превратить их в более удобные.

Подсказка 3:

Умножьте изначальное выражение на некоторый многочлен от x, y, z, чтобы реализовать предыдущую подсказку.

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

Домножим выражение из условия на $(xyz)50.$ Заметим, что

50 50 50 50 50 50 100 (xyz) (x +y) ≡(xy) (xz+yz) ≡(xy) (− xy) ≡ (xy) (mod n)

Аналогично два других слагаемых сравнимы с $(yz)100$ и $(zx)100.$ Тогда получаем, что выражение $(xy)100+ (yz)100 +(zx)100$ делится на $n.$ Значит, можно взять $a= xy,b= yz,c=zx.$

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

Задача 8#89721

Докажите, что для каждого натурального $n$ число $19⋅8n +17$ — составное.

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

Подсказка 1

Явно найти делитель числа — вероятно, самый простой способ доказать, что оно не является простым. Еще проще будет проверять делимость на число, не зависящее от n. Найдите значения при первых нескольких n, это может найти постоянные делители (возможно, с дополнительным условием на n), если они зависят от n.

Подсказка 2

8^n растет довольно быстро, тем не менее значения выражения при n = 1, 2, 3 посчитать несложно, они равны соответственно 169, 1233, 9745. Проверять делимость по большому модулю затруднительно, поэтому стоит начать с минимальных делителей - соответственно 13, 3, 5. Например, чему должно удовлетворять число n, чтобы 19*8^n+17 было кратно 3 (заметьте, что n=2 должно удовлетворять этому условию)?

Подсказка 3

Покажите, что при всех четных n число кратно 3. С чем должно быть сравнимо 8^n при этом условии?

Подсказка 4

С 1. Вообще доказывать сравнимость с 1 числа вида a^b довольно просто - для каждого числа a взаимнопростого с числом m существует b такое, что a^b сравнимо с 1 по модулю m, но тогда для любого k число a^{kb} так же сравнимо с 1. Так, 8^2=64 сравнимо с 1 по модулю. Какие условия можно наложить на число n, чтобы оно делилось на 13 и 5?

Подсказка 5

Мы уже доказали утверждения задачи для всех четных n. Доказать делимость на некоторое фиксированное число для любого нечетного n будет трудно, ведь это неправда - числа 169, 9745 взаимнопросты. Остается надеяться, что это можно сделать, для всех n сравнимых с фиксированным остатком по модулю 4.

Подсказка 6

Таким образом, осталось показать, что выражение делится на 13 при всех n=4k+1 и на 5 при всех n=4k+3.

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

Рассмотрим $3$ случая:

(a) $n= 2k,$ где $k∈ℤ,$ тогда

2k 2k k 19 ⋅8 + 17= 18 ⋅8 + 1⋅(1 +63) +(18− 1)≡ 0+ 1+ (− 1)≡ 0 (mod 3)

то есть в данном случае $19⋅8n+ 17$ делится на $3.$

(b) $n= 4k+ 1,$ где $k ∈ℤ,$ тогда

4k+1 4k+1 2k 19⋅8 +17= 13⋅8 + 6⋅8⋅64 +17=

13⋅84k+1+ 39 ⋅642k+ 9⋅(1− 65)2k+ (26− 9)≡

0+ 0+ 9+(−9)≡ 0 (mod 13)

то есть в данном случае $19⋅8n+ 17$ делится на $13.$

19⋅84k+3+ 17= 15⋅84k+3+ 4⋅83 ⋅642k+ 17 =

15⋅84k+3 +4⋅510⋅642k+ 4⋅2⋅(1− 65)2k +(25− 8)≡

0 +0+ 8+ (− 8)≡0 (mod 5)

то есть в данном случае $19⋅8n+ 17$ делится на $5.$

Рассмотренные случаи покрывают все натуральные $n.$

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

Задача 9#89722

Петя выписал на доску натуральное число $N.$ Каждую минуту он приписывает справа к числу $87.$ Докажите, что в течение каждого часа на доске хотя бы раз будет появляться составное число.

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

Подсказка 1

Какие модули бывает полезно рассматривать в задачах на десятичную запись числа?

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

Пусть $N = aa-...a- 12 n$ и $P = a − a +a − ...+ (− 1)na . n n− 1 n−2 1$

Пусть прошло $k$ минут. Тогда на доске записано число вида $-------------- Nk = a1a2...an87...87.$ Обозначим за

n Pk = 8− 7 +8− 7+ ...+ 8− 7 +an− an−1+ an− 2− ...+(−1)a1 =k +P

Получается, что за ближайшие $11$ минут $P k$ будет иметь всевозможные остатки по модулю $11.$ Значит, за эти $11$ минут, какое-то из $P k$ поделится на $11.$ Но по признаку делимости на 11 $N ≡ P (mod 11). k k$ Т.е. начиная с какого-то момента, каждые $11$ минут, $N k$ будет делиться на $11,$ что и требовалось доказать.

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

Задача 10#89723

Решите в натуральных числах уравнение:

2022 b c a + 2015 = 2022 − 2

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

Подсказка 1

Разность чисел 2015 и 2022 относительно небольшая. Этим можно воспользоваться при выборе модуля, по которому мы будем рассматривать исходное уравнение.

Подсказка 2

Число a²⁰²² является одновременно квадратом и кубом натурального числа. По какому модулю квадраты и кубы дают "приятные" остатки? Помните, что мы хотим отловить разницу чисел 2015 и 2022 за счет выбора модуля.

Подсказка 3

Под каждый из отмеченных критериев подходит модуль 8. Какие может давать левая часть по данному модулю?

Подсказка 4

Левая часть сравнима с 4 при с=1, с 2 при с=2, с -2 при всех следующих значениях с. Какие может правая часть по модулю 8 в зависимости от четности чисел a и b? При каких значениях (a, b, c) достигается равенство остатков?

Подсказка 5

Равенство возможно лишь в случае, когда a — нечетное, b — четное и c =2. То есть левая часть равна 2²⁰²²-1. Что можно сказать о левой части в случае, если a>1 или b>2?

Подсказка 6

Покажите, что в каждом из этих случаев левая часть больше, чем правая.

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

⌊ −1, при a четное, b нечетное 1 − (−1)a || 0, при a нечетное, b нечетное a2022 +2015b ≡----2-- + (− 1)b = || (mod 8) ⌈ 1, при a четное, b четное 2, при a нечетное, b четное

⌊ 4, при c= 1 2022c− 2≡ (−2)c− 2= |⌈ 2, при c= 2 (mod 8) −2, при c≥3

Получается, что правая и левая части могут быть сравнимы по модулю $8$ только в случае, когда $a$ нечетное, $b$ четное и $c =2.$ Тогда обе части уравнения сравнимы с $2$ по модулю $8.$

При $a> 1:a2022+ 2015b > 22022 > 20222− 2.$

При $b> 2:a2022+ 2015b > 20153 > 20222 − 2.$

Т.е. единственный возможный вариант: $a= 1,b= 2.$ Но тогда $12022+ 20152 ⁄= 20222− 2.$ Т.е. решений данное уравнение в натуральных числах не имеет.

Ответ:

нет решений

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

Задача 11#90453

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

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

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

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

Интенсивы

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

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

Задача 12#90454

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

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

Решение скрыто

Ответ:

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

Задача 13#91135

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

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

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

Ответ: нет

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

Задача 14#97687

Докажите, что не существует натуральных чисел $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,$ поэтому является составным числом.

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

Задача 15#97692

Вадим выписывает числа на доску. Изначально он пишет на доске какое-то число, большее $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.$

Ответ:

Не может

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

Задача 16#61462

Миша выписал все остатки от деления некоторого числа $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$ .

Ответ:

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

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

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

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

Задача 17#73169

Натуральное число $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∈ ℕ$

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

Задача 18#75307

Докажите, что число $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)

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

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

Задача 19#31387

Докажите, что число $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$ , поэтому мы получили искомое представление.

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

Задача 20#32151

Докажите, что сумма $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.$ А квадрат целого числа не может давать такой остаток. Значит, сумма не является квадратом, что и требовалось.

Предыдущий раздел

Следующий раздел