Делимость и делители (множители) —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Делимость и делители (множители)

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

Делимость и делители (множители)

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

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

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

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

Разделы подтемы Делимость и делители (множители)

Условия про НОД и НОК

Разложение на множители, основная теорема арифметики

Количество, сумма, произведение делителей

Степени вхождения простых

Оценки для доказательства делимости

Алгоритм Евклида

Теоретико-числовые свойства биномиальных коэффициентов

Теоретико-числовые свойства чисел Фибоначчи

Целые гауссовы числа

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

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

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

Задача 1#88137

Найдите сумму максимальных нечётных делителей всех чисел от 601 до 1200 включительно.

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

Подсказка 1

Зададимся вопросом, что означает тот факт, что у двух чисел из отрезка [601; 1200] одинаковый наибольший нечетный делитель. Если это так, как могут отличаться эти два числа?

Подсказка 2

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

Подсказка 3

Такая ситуация невозможна, ведь на отрезке нет чисел, которые отличаются друг от друга хотя-бы в два раза. Какой вывод можно сделать из этого рассуждения?

Подсказка 4

Тогда мы получили, что искомые делители у всех наших чисел различны. Делитель не может быть больше самого числа, поэтому мы не получим делители, превосходящие 1200. Тогда не остаётся выбора, какие нечётные числа брать :)

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

Пусть $S =a +a + ...+a 601 602 1200$ — сумма максимальных нечётных делителей чисел на отрезке $[601,1200]$ , причём $a i$ является максимальным нечётным делителем числа $i$ для всех $i∈{601,602,...,1200}.$

Пусть $n$ — натуральное нечётное число на отрезке $[1;1200]$ . Докажем, что $n$ совпадает с $aj$ для некоторого $j ∈ {601,602,...,1200}$ . Предположим противное. Рассмотрим ряд

2 n,2n,2 n,...

Поскольку $n< 1200$ , то существует натуральное число $i$ такое, что $2in< 601$ , а $2i+1n> 1200$ , что невозможно.

Таким образом, каждое нечётное число на отрезке $[1;1200]$ совпадает с $a j$ для некоторого $j ∈ {601,602,...,1200}$ . Осталось заметить, что на отрезке $[1,1200]$ каждое второе число является нечётным, следовательно, количество нечётных чисел равно 600, ровно из стольких слагаемых состоит $S$ , то есть никаких других чисел там нет. Наконец, по формуле суммы членов арифметической прогрессии

1200 1+ 3+...+1199= 1200⋅-4--= 1200⋅300= 360000.

Ответ: 360000

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

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

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

Задача 2#88133

В тюрьме находятся 100 камер, пронумерованных числами от 1 до 100. Тюремщик Джон Фридом, осуществляя частичную амнистию, поступил следующим образом. Сначала он открыл все камеры. Затем запер каждую вторую камеру. На третьем этапе он повернул ключ в замке каждой третьей камеры (открыл запертые и запер открытые). Продолжая действовать таким образом, на сотом этапе он повернул ключ только в замке последней сотой камеры, а затем выпустил всех заключенных, которые оказались в открытых камерах. Укажите номера камер, в которых сидели счастливчики.

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

Подсказка 1

Подумаем, что с точки зрения теории чисел значит, что в момент k-го прохода (когда тюремщик проходится по камерам k-й раз и поворачивает замок в каждой k-й) повернулся замок в камере с номером n? Например, в третий раз он меняет состояние 3, 6,… 99 двери, что нам это напоминает?

Подсказка 2

Верно, такое действие означает, что n является кратным числа k, или же k — делитель n. Если в конце дверь отказалась открыта, значит замок поворачивали нечетное количество раз. Что мы получим, сопоставив эти две мысли?

Подсказка 3

Таким образом, отрыты в конце те двери, у номеров которых нечетное число делителей. У любого числа все (или почти все) делители можно поделить на пары. Подумаем, когда же реализуется это “почти”, которое нас и приведет к решению задачи!

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

Назовем проходом с номером $k$ изменение состояний каждой $k$ -той камеры. Рассмотрим камеру с номером $n$ . Найдем сколько раз она меня свое состояние с открытой на закрытую или наоборот. Пусть камера поменяла свое состояние на проходе с номером $m$ , тогда номер камеры $n$ делится на $m$ . Таким образом, камера с номером $n$ меняла свое состояние столько раз, сколько различных делителей она имеет.

Заметим, что после каждой нечетной смены состояний камеры она является открытой, а после каждой четной — закрытой. Таким образом, в конце камера будет открыта тогда и только тогда, когда количество смен ее состояний, то есть количество делителей ее номера является нечетным числом. Докажем, что число имеет нечетное количество делитей тогда и только тогда, когда является полным квадратом. Как известно, число делителей числа $a1 a2 al n = p1 p2 ...al$ равно $σ(n)= (1 +a1)(1+ a2)...(1+ al)$ — нечетное число, но тогда число $1+ ai$ нечетно при всех $i= 1,...,l$ , следовательно, каждое из чисел $ai$ при всех $i=1,...,l$ делится на 2, то есть степень вхождения любого простого числа в $n$ четна, а значит $n$ является квадратом. Аналогично, если $n$ суть полный квадрат, то числа $ai$ при всех $i= 1,...,l$ делятся на 2, следовательно, $σ(n)= (1+ a1)(1+a2)...(1+al)$ — нечетно.

Наконец, открытыми будут те и только те камеры, номера которых есть полный квадарт, то есть 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Ответ: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100

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

Задача 3#88062

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

Ответ обоснуйте.

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

Поскольку произведение первых 6 натуральных чисел равно $6!= 720,$ то искомое число не больше $720.$

Осталось доказать, что произведение любых подряд идущих 6 натуральных чисел $n+ 1,n +2,...,n+ 6$ делится на $720$ . Поделим:

(n +1)(n +2)...(n+ 6) (n +6)! 6 --------6!--------= -6!n!--= Cn+6

и получим натуральное число способов выбрать шестёрку из $n+ 6$ элементов. Действительно, делится.

Ответ: 720

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

Задача 4#85914

Докажите, что уравнение

5m2−-n n2+ 3m =1

имеет бесконечно много решений в целых числах.

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

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

Решим сначала уравнение

2 2 5m − n = n +3m

______________________________________________________________________________________________________________________________________________________

5m2 − 3m = n2+ n

Умножим на 4 и прибавим 1 к обеим частям, чтобы выделить полный квадрат справа:

20m2− 12m+ 1= (2n+1)2

Теперь домножим обе части на 5 и выделим полный квадрат слева:

(10m− 3)2 =5(2n+ 1)2+ 4

Сделаем замену $x= 10m− 3,y = 2n +1$ . У получившегося уравнения

x2− 5y2 =4

имеются решения

x= ±(F2k−1+F2k+1),y =±F2k,k≥ 0,

где $Fk$ — числа Фибоначчи (мы пользуемся нумерацией $F0 = 0,F1 = 1,Fk+1 = Fk+ Fk−1$ при всех целых $k$ ). На самом деле

(Fk−1+ Fk+1)2− 5F2k = 4F2k− 1+4Fk−1Fk− 4F 2k

равно $k (−1)4$ для всех $k$ , что легко проверить по индукции: при $k= 0$ это выполняется, а если $2 2 k Fk−1+Fk−1Fk− Fk =(−1)$ , то и

F2k + FkFk+1− F2k+1 =Fk2− Fk−1Fk− F2k−1 = (−1)k+1

(Можно доказать с помощью теории уравнений Пелля, что $2 2 x − 5y = 4$ не имеет других решений.)

Теперь нужно найти бесконечно много $x$ и $y$ таких, для которых соответствующие $x+3 m = 10$ и $y−1 n= 2$ целые. Заметим, что последовательность остатков чисел Фибоначчи по модулю 10 периодична (так как пара ( $Fk−1,Fk$ ) может принимать конечное количество вариантов по модулю 10, а остаток следующего и предыдущего чисел Фибоначчи однозначно определяются по остаткам этой пары). Кроме того, $x =F2 =1$ и $y =F1 +F3 = 3$ подходят, они соответствуют тривиальному решению $m = n= 0$ . Значит, уравнение $5m2 − n =n2 +3m$ имеет бесконечно много решений.

_________________________________________________________________________________________________________________________________________________________________________________

Осталось понять, что они все не могут обнулять знаменатель. Действительно, если $(m,n)$ — решение уравнения $5m2− n= n2+ 3m$ , при котором $n2+ 3m =0$ , то и $5m2− n= 0$ . Следовательно, $25m4 + 3m = 0$ . Так как $m$ целое, то обязательно $m = 0$ (иначе $|| 4|| 25m > |3m|$ ), а значит, и $n= 0$ . Остальные пары $(m,n)$ нам подходят.

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

Задача 5#85451

Для любых натуральных $a,b$ и $c$ докажите неравенство

(a,b− 1)(b,c− 1)(c,a − 1)≤ ab+bc+ ca

(Как обычно, $(x,y)$ обозначает наибольший общий делитель чисел $x$ и $y.$ )

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

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

Заметим, что

ab+ bc+ ca> ab+bc+ ca− a− b− c+1 =abc− (a− 1)(b− 1)(c− 1)

Но эта разность делится на произведение НОДов. Действительно, $a$ делится на $(a,b− 1),b$ делится на $(b,c− 1)$ и $c$ делится на $(c,a− 1),$ следовательно $abc$ делится на произведение НОДов. Аналогично $(a− 1)(b− 1)(c− 1)$ делится на произведение НОДов, а тогда и разность делится. Но тогда эта разность не меньше, а $ab+bc+ ca$ больше произведения НОДов.

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

Задача 6#85447

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

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

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

Рассмотрим произведения первых $k$ чисел в ряду. Всего таких произведений $2n+ 1$ (также учитваем произведение, в котором $0$ простых чисел, будем считать, что оно равно $1$ ).

Ясно, что произведение чисел любой подпоследовательности этого ряда — частное каких-то двух произведений первых чисел.

Пусть ряд состоит из чисел $p1,p2,...,pk(k ≤n − 1).$ Тогда любое произведение первых чисел имеет вид $α1 α2 αk p1 p2 ...pk .$ Если мы найдём два произведения первых чисел, у которых чётности соответствующих $αi$ совпадают, то мы найдём подпоследовательность ряда, произведение чисел которой равно квадрату.

Всего существует $k 2$ наборов чётностей $αi$ (каждое $αi$ либо чётное, либо нет). Осталось заметить, что $k n−1 n 2 ≤ 2 < 2 + 1.$ Значит, найдутся два произведения с одинаковым набором чётностей у $αi,$ получили требуемое.

Курсы

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

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

Задача 7#83298

Найти сумму максимальных нечётных делителей всех чисел от 61 до 120 включительно.

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

Подсказка 1

Интересно, что чисел от 61 до 120 ровно столько же, сколько нечётных от 1 до 120.

Подсказка 2

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

Подсказка 3

Из первого замечания про количество нечётных хочется посмотреть, а сколько чисел вида n * 2ᴷ для каждого нечётного n (меньшего 120) лежит в промежутке от 61 до 120.

Подсказка 4

Оказывается, для каждого такого n одно своё n * 2ᴷ в промежутке от 61 до 120. Попробуйте понять, почему это так, и досчитать искомую сумму нечётных n!

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

Для каждого нечетного числа $n$ в промежутке 1 до 119 рассмотрим числа вида $n⋅2k$ , где $k∈ ℕ∪ {0}.$ Докажем, что для каждого $n$ найдётся ровно одно число вида $k n⋅2$ на промежутке от 61 до 120.

Пусть на нашем промежутке не нашлось нужного числа. Тогда должна найтись такая пара чисел $k k+1 (n⋅2 ;n ⋅2 )$ , что

k k+1 n⋅2 ≤ 60, n⋅2 ≥121,

что невозможно, поскольку из первого следует, что

k+1 n ⋅2 ≤ 120

Тогда из нашего утверждения следует, что для любого нечётного числа $n$ , меньшего 120, найдётся число от 61 до 120, что его наибольшим нечетным делителем будет $n$ . Причём для каждого $n$ такое число уникально. При этом нечётных чисел от 1 до 120 ровно 60, как и чисел от 61 до 120. Получается, что искомая сумма равна сумме всех нечётных чисел от 1 до 120.

1+-119- 1+3+ ...+ 119= 2 ⋅60= 3600

Ответ: 3600

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

Задача 8#82085

Про натуральные числа $a,b,c$ известно, что $ab$ делится на $2c,bc$ делится на $3a$ , а $ac$ делится на $5b$ . Найдите наименьшее возможное значение их произведения $abc$ .

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

Подсказка 1

Обратите внимание, что если w является делителем x и y является делителем z, то xz кратно wy. Как это можно применить относительно нашего условия?

Подсказка 2

Правильно, перемножив попарно все три условия кратности и сократив лишнее, получим, что a² ⫶ 10, b² ⫶ 6 и c² ⫶ 15. Все эти числа не включают в себя полные квадраты. Что это говорит о числах a, b и c?

Подсказка 3

Правильно, сами числа тогда тоже делятся на 10, 6 и 15 соответственно, а значит, не могут быть меньше них. Тогда и abc тоже будет не меньше произведения этих чисел.

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

.. .. 2 .. 2.. ab.2c,bc.3a =⇒ ab c.6ac =⇒ b .6

Но раз квадрат $b$ делится на 2 и на 3, то и само $b$ делится на 2 и на 3. Тогда $b...6$ , значит, $b≥ 6.$

.. .. 2 .. 2.. ab.2c,ac.5b =⇒ a bc.10bc =⇒ a .10

Но раз квадрат $a$ делится на 2 и на 5, то и само $a$ делится на 2 и на 5. Тогда $a...10$ , значит, $a≥ 10.$

bc...3a,ac...5b =⇒ abc2...15ab =⇒ c2...15

Но раз квадрат $c$ делится на 3 и на 5, то и само $c$ делится на 3 и на 5. Тогда $. c..15$ , значит, $c≥ 15.$

В итоге $abc≥ 10⋅6⋅15= 900,$ причём при $a =10$ , $b= 6$ , $c= 15$ достигается равенство.

Ответ: 900

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

Задача 9#79760

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

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

Давайте докажем, что если числа $a$ и $b$ различны, то НОД $(a,b)≤ a+b 3$ . Пусть $a< b$ , тогда НОД $(a,b)≤a$ , а 2НОД $(a,b)≤ b$ (так как $b$ делится на НОД $(a,b)$ , но равно быть не может, так как числа не равны и $b$ большее число, значит, 2НОД $(a,b)≤ b$ ). Получили, что 3НОД $(a,b)≤a +b$ . Давайте для каждого ребра запишем полученную оценку и сложим все неравенства, каждая вершина используется в трех неравенствах, поэтому сумма всех НОДов меньше либо равна суммы всех чисел. Предположим, что эти суммы равны, тогда равенство достигается в каждом неравенстве, выше. То есть равенство возможно только при $b= 2a$ или $a =2b$ (для каждого ребра).

Не теряя общности пусть $a= 2b$ , но тогда: либо $c=b$ , тогда нашлись два равных числа, либо $c= 4b$ , но также $d =b$ или $d= 4b$ , то есть в любом случае найдутся хотя бы два равных числа, противоречие, значит, равенства быть не могло. Таким образом, сумма всех НОДов меньше суммы всех чисел.

Ответ:

Нет

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

Задача 10#79759

Даны натуральные числа $a$ и $b$ такие, что число $a+-1+ b+-1 b a$ является целым. Докажите, что наибольший общий делитель чисел $a$ и $b$ не превосходит числа $√ ---- a+b.$

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

Имеем:

a+-1 b+-1 a2+-b2+a-+b b + a = ab

Пусть $d$ — наибольший общий делитель чисел $a$ и $b.$ Так как $ab$ делится на $2 d ,$ то $2 2 a + b+ a+ b$ делится на $2 d.$ Число $2 2 a +b$ также делится на $2 d .$ Поэтому $a+b$ делится на $2 d$ и $√---- a +b≥ d.$

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

Задача 11#79329

Докажите, что если $n+ 1$ делится на $24,$ то сумма всех делителей натурального числа $n$ тоже делится на $24.$

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

Так как $n+ 1$ делится на $3$ и $8,$ то $n$ при делении на $3$ даёт остаток $2,$ а при делении на $8$ — остаток $7.$

Разобьём делители на пары вида $(n,n∕d),$ так как число $n$ не может быть полным квадратом ввиду противоречия с делимостью на $3.$ Заметим, что если $d$ даёт остаток $1$ при делении на $3,$ то $n∕d$ даёт остаток $2$ и наоборот. Поэтому сумма делителей в каждой такой паре кратна $3.$

Аналогично, сумма делителей в каждой такой паре кратна $8.$

Интенсивы

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

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

Задача 12#78906

Найдите все такие составные числа $n,$ что для любого разложения на два натуральных сомножителя $n= xy$ сумма $x +y$ является степенью двойки.

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

Подставив $x= 1,y = n,$ получим, что $n= 2k− 1$ для некоторого натурального $k.$ Пусть $n =ab,$ где $a≥ b>2,$ и пусть $a +b= 2t$ для некоторого натурального числа $t.$ Очевидно, что $k >t.$ Тогда

k t 2 +2 = ab+ a+b+ 1= (a+ 1)(b+1), 2k− 2t = ab− a− b+ 1= (a− 1)(b− 1)

Перемножив эти равенства, получим, что число $(a − 1)(a +1)× (b− 1)(b+ 1)$ делится на $2t 2 .$ Но двойка входит в одно из чисел $b− 1$ или $b+1$ в первой степени, а во второе — в степени, не большей $t− 1.$ Аналогично для чисел $a − 1$ и $a+ 1.$ Следовательно, делимость на $2t 2$ возможна, только если в обеих упомянутых оценках двойки входит в степени ровно $t− 1.$ Это возможно, лишь если $t−1 t−1 b= 2 − 1,a =2 + 1$ (поскольку $a≥ b$ и $t a+b =2$ ). Тогда $k= 2t− 2$ и $k 2 − 1$ делится на $3.$ Значит, можно считать, что в наших рассуждениях выбрано $b =3.$ Тогда $a= 5,$ и $n= 15$ — единственное подходящее число.

Ответ:

$n =15$

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

Задача 13#78899

Дано $41$ различное натуральное число, меньшее $1000.$ Известно, что среди любых трех из них есть два, дающих в произведении точный квадрат. Докажите, что среди этих чисел есть точный квадрат.

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

Предположим, что среди этих чисел нет точного квадрата. Обозначим через $p ,...,p 1 n$ все простые числа, меньшие $1000.$ Заметим, что по условию каждое выписанных чисел раскладывается в произведение $p1,...,pn$ в некоторых степенях. Каждое из наших простых чисел входит в одно выписанное число в четной или нечетной степени. Сопоставим каждому выписанному числу последовательность из $0$ и $1$ длины $n.$ Число на $i$ - ой позиции будет равно $1,$ если $pi$ в ходит в выписанное число в нечетной степени и $0$ в противном случае (на самом деле это и есть бесквадратная часть, про которую мы говорили в теории). Предположим, что среди последовательностей выписанных чисел есть три различные. Тогда для трех соответствующих этим последовательностям чисел не выполнено условие (два числа в произведении могут давать точный квадрат, только если четности вхождения каждого $pi$ - ого одинаковые).

То есть мы показали, что различных последовательностей может быть не больше $2.$ Обозначим эти последовательности через $a1,...,an$ и $b1,...,bn.$ Обозначим через $a a b b a =p11⋅⋅⋅pnn,b= p11 ⋅⋅⋅pnn .$ Очевидно что $a⁄= b.$ Считаем. что $a< b,$ тогда $a ≥2,b≥ 3,$ так как при $a= 1$ мы получим, что числа являются квадратами, а мы предположили, что их нет. Каждое из выписанных чисел дает точный квадрат либо при делении на $a,$ либо при делении на $b.$ Причем для чисел, которым соответствуют одинаковые последовательности, эти квадраты должны быть различными. Рассмотрим наибольшее выписанное число, которому соответствует последовательность $a$ -шек. Оно равно $a⋅s2$ для некоторого натурального $s,$ откуда $s2 ≤ 500,$ то есть $s≤ 22.$ Но тогда количество выписанных чисел, которым соответствует первая последовательность, не превосходит $22.$ Аналогично поступаем со второй последовательностью. Опять рассматривает наибольшее число $bh2 ≤1000,$ откуда $h2 ≤ 1000∕3,$ то есть $h≤ 18,$ откуда таких чисел не больше $18.$ То есть всего чисел не больше, чем $22+ 18 =40.$ Получили противоречие с количеством данных чисел.

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

Задача 14#78889

Можно ли вычеркнуть из произведения $1!⋅2!⋅3!⋅...⋅56!$ один из факториалов так, чтобы произведение оставшихся было квадратом целого числа?

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

2 2 2 28 2 1!⋅...⋅56!=(1!) ⋅2⋅(3!) ⋅4 ⋅...⋅(55!) ⋅56=2 ⋅(1!⋅3!⋅...⋅55!)⋅28!

Отсюда видно, что, вычеркнув $28!,$ мы получим квадрат числа $214⋅1!⋅3!⋅...⋅55!.$

Ответ:

Да, можно

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

Задача 15#76655

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

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Сначала докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма.

Пусть $φ (n)$ - функция Эйлера числа $n.$ (Количество чисел от $1$ до $n$ взаимно простых с $n.$ ) Тогда для любого натурального числа $n >1$ справедливо неравенство

∑ n2 d < φ(n)- d|n

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство леммы.

Запишем сумму делителей числа через произведение сумм степеней его простых делителей. Если $n =pα1pα2...pαk, 1 2 k$ то

∑ 2 α1 2 α2 2 αk d =(1+ p1+p1+ ...+ p1 )(1+ p2+ p2+ ...+ p2 )...(1+ pk +pk+ ...+ pk ) d|n

Используя формулу суммы геометрической прогрессии, получаем:

∑ d= (1+ p + p2 +...+ pα1)(1+ p +p2+ ...+ pα2)...(1+ p +p2+ ...+ pαk)= d|n 1 1 1 2 2 2 k k k

(pα11+1 − 1)(pα22+1− 1)...(pαk+1− 1) = ----(p1−-1)(p2-− 1)...(pkk− 1)--.

Функция Эйлера вычисляется по формуле $φ(n)=pα11−1(p1− 1)pα22−1(p2− 1)...pαkk− 1(pk− 1).$ Тогда чтобы получить $φ(n)$ в знаменателе, домножим числитель и знаменатель на $pα11−1pα22−1...pαkk−1$

(pα11+1−-1)(pα22+1−-1)...(pαkk+1−-1)= (p1− 1)(p2− 1)...(pk− 1)

α1−1 α2−1 αk−1 α1−1 α2−1 αk−1 = p1--p2α1−.1..pk--(pα12−1-− 1)(p2-α−k−11)...(pk---−-1)= p1 (p1− 1)p2 (p2− 1)...pk (pk− 1)

(p2α1 − pα1−1)(p2α2− pα2−1)...(p2αk− pαk−1) p2α1p2α2...p2αk n2 = --1----1-----2--φ(2n)------k----k----< -1--2φ(n)--k--= φ(n)

_________________________________________________________________________________________________________________________________________________________________________________

Решение задачи.

По условию и лемме

∑ -n2- 100n < d|nd< φ(n).

Тогда

100n< -n2-⇒ φ(n)< n-. φ(n) 100

То есть количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $-n- 100.$

Рассмотрим два случая: $n$ делится на $100$ и $n$ не делится на $100.$

1. Число $n$ делится на $100.$ Тогда можно разбить числа от $1$ до $n$ на $n-- 100$ групп по $100$ идущих подряд чисел. Если количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n-- 100$ , то хотя бы в одной группе не будет числа взаимно простого с $n$

2. Число $n$ не делится на $100.$ Тогда среди чисел $2$ до $n$ можно выделить $-n- [100]$ групп по $100$ идущих подряд чисел. Если в каждой группе будет число взаимно простое с $n$ , то чисел взаимно простых с $n$ хотя бы $n [100]+ 1$ ( $1$ тоже взаимно проста с $n$ ). Это противоречит тому, что количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n 100-$

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

Задача 16#88135

Сумма двух различных натуральных делителей натурального числа $n$ равна 100. Какое наименьшее значение может принимать число $n?$ (Среди указанных делителей могут быть единица и само число.)

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

Подсказка 1

Предположим, что мы взяли какие-то два делителя числа n числа и сложили их. Если каждый из этих двух делителей меньше n, то он меньше n “в сколько-то раз”. Какой вывод мы тогда сможем сделать для их суммы?

Подсказка 2

Да, в таком случае сумма этих двух делителей, равная ста, будет меньше, чем n, следовательно, n больше ста. Это не очень удовлетворительный результат, потому что первый пример, приходящий в голову — 99+1 — это пример меньше, чем на 100. Какой вывод можно отсюда сделать?

Подсказка 3

Тогда получается, что один из делителей заведомо равен самому числу. В таком случае, введя d как меньший делитель, можно записать условие в виде достаточно простого выражения!

Подсказка 4

Из нашей записи получится, что n/d+1 должно быть делителем числа 100. При этом для каждого фиксированного d чем больше n/d, тем больше n. Отсюда и получим искомый ответ!

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

Если один из наших делителей — само число $n$ , а второй — некоторое число $d$ и $n= dk$ , то мы получаем

100= d+ dk =d(k+ 1)

n ( 1) 100= n+ k = n⋅ 1+ k

Чем $k$ больше, тем и само $n$ больше.

Наименьшее $k >1$ такое, что $k+ 1$ является делителем 100, это 3. При таком $k$ получаем $n =75$ .

Если же $n$ нет среди двух наших делителей, то $n n 2 + 3 ≥100$ , откуда $n ≥120$ .

Ответ: 75

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

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

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

Задача 17#77774

Последовательность Фибоначчи задана рекуррентно $a = a = 1,a = a + a ,n≥ 2 1 2 n+1 n n−1$ . С каким остатком число 3 в степени $a 2022$ делится на 13?

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

Чтобы найти остаток при делении $3n$ на $13,$ достаточно знать остаток при делении на $3,$ потому что

3 3k+r r 3 = 27≡ 1(mod 13)⇒ 3 ≡ 3 (mod 13).

По индукции доказывается, что остатки при делении чисел Фибоначчи на $3$ повторяются с периодом $8:$

k 1 2 3 4 5 6 7 8 9 10...

ak 1 1 2 3 5 8 13 21 34 55...

ak(mod 13) 1 1 2 0 2 2 1 0 1 1...

Поскольку $2022$ делится на $8$ с остатком $6,$ имеем

3a2022 ≡ 3a6 =38 ≡ 32 = 9(mod 13).

Ответ: 9

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

Задача 18#75905

Натуральное число $b$ назовем удачным, если для любого натурального $a,$ такого, что $a5$ делится на $b2,$ число $a2$ делится на $b.$ Найдите количество удачных чисел, меньших $2023.$

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

Лемма. Число $b$ является удачным тогда и только тогда, когда каждое простое число входит в разложение $b$ на простые множители с одним из следующих показателей: $0,1,2,3,4,6,8.$

Доказательство. Назовем целое неотрицательное число $k$ счастливым, если не существует такого целого $m,$ что $2m < k≤ 2,5m.$ Заметим, что счастливыми являются в точности числа $0,1,2,3,4,6,8.$ При $k ≤9$ в этом можно убедиться прямой проверкой. Если же $k >9,$ то выберем такое максимальное число $m,$ что $2m< k.$ Тогда $m > 4,$ и $2,5m > 2m+ 2= 2(m + 1)>k$ по выбору $m,$ то есть $k$ несчастливо.

Пусть число $b$ неудачно, то есть $5 a$ делится на $2 b,$ но $2 a$ не делится на $b$ для некоторого $a.$ Тогда некоторое простое $p$ входит в разложение $2 a$ в меньшей степени, чем в разложение $b.$ Пусть $p$ входит в разложения $a$ и $b$ в степенях $m$ и $k$ соответственно; тогда $2m < k,$ но $5m ≥2k.$ Значит, число $k$ — несчастливое. Итак, если все степени вхождения простых чисел в $b$ счастливы, то $b$ удачно.

Если же $b= pkb′,$ где $b′$ не кратно $p$ и $k$ несчастливо $(2m <k ≤2,5m),$ то при $a =pmb′$ число $a5$ делится на $b2,$ а $a2$ не делится на $b,$ то есть $b$ неудачно.

Согласно лемме, каждое неудачное число имеет простой делитель, входящий в разложение на простые множители с показателем $5,7$ или более $8.$ Поскольку $210 < 2023 <211,36 < 2023 <37,25⋅35 >2023$ и $55 >2023,$ каждое неудачное число, меньшее $2023,$ принадлежит одному из следующих непересекающихся классов:

$1)$ Числа вида $25q,$ где $q$ нечётно и $q ≤ 63(25⋅63< 2023< 25⋅65);$

$2)$ Числа вида $27q,$ где $q$ нечётно и $q ≤ 15(27⋅15< 2023< 27⋅17);$

$3)$ Числа вида $29q,$ где $q = 1$ или $3(29⋅3< 2023< 29⋅5);$

$4)$ Число $210;$

$5)$ Числа вида $35q,$ где $q$ не кратно $3$ и $q ≤ 8(35⋅8< 2023< 35⋅10).$

Таким образом, общее количество неудачных чисел, меньших $2010,$ равно $32+ 8+ 2+1 +6= 49,$ а количество удачных чисел равно $2009− 49 =1960.$

Ответ:

$1960$

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

Задача 19#75904

Найдите все натуральные $a$ и $b,$ для которых

----1---- ----1---- --1-- НОК(a2,b3) + НО К(b2,a3) =2023ab

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

Для удобства обозначим первый НОК через $m,$ а второй, через $n.$ Тогда равенство можно записать в виде $2023ab(m + n)=mn.$ Рассмотрим произвольное простое число $p.$ Пусть оно входит в $a$ в степени $x,$ а в $b$ — в степени $y.$ Тогда в $m$ оно входит в степени $max{2x,3y},$ в $n$ — в степени $max{2y,3x}.$ Значит, в $mn$ оно входит в степени $max {2x,3y} +max{2y,3x}.$

Теперь оценим степень вхождения $p$ в левую часть равенства:

vp(2023ab(m + n))= vp(2023)+x +y+ vp(m + n)≥vp(2023)+x +y +min{max{2x,3y},max{2y,3x}}

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

max{2x,3y}+ max{2y,3x}≥ vp(2023)+ x+ y+ min{max{2x,3y},max{2y,3x}}

Запишем $min{max{2x,3y},max{2y,3x}}$ как

max {2x,3y}+max {2y,3x} − max{max{2x,3y},max{2y,3x}}= max{2x,3y}+ max{2y,3x}− max{3x,3y}

и приведём подобные. Получим, что $max{3x,3y} ≥vp(2023)+x +y.$

Заметим, что строгий знак в полученном неравенстве возможен лишь когда $max{2x,3y}= max{2y,3x}.$ Также отметим, что последнее равенство возможно лишь когда $x =y.$ Действительно, если $max{2x,3y}= 2x,$ то $max{2y,3x} =2y,$ иначе равенство $max{2x,3y} =max {2y,3x}$ будет верным лишь при $x =y =0.$ Аналогично рассматривается другой случай. Предположим, что $x= y$ . Если равенство $x =y$ верно для любого простого $p$ , то $a= b$ . Тогда уравнение примет вид: $a3 = 4046a2,$ а значит $a =b= 4046.$

Пусть существует такое $p,$ для которого $x⁄= y,$ тогда $max{3x,3y}= vp(2023)+ x+ y.$ Уравнение симметрично, поэтому пусть $x> y,$ тогда равенство примет вид $2x= y+v (2023). p$ Правую часть можно оценить сверху: $y+v (2023)< x+ v(2023), p p$ то есть $2x< x+ v (2023), p$ откуда $x< v(2023). p$ Простое число может входить в $2023$ в степени $2,$ если оно равно $17,$ в степени $1,$ если оно равно $7,$ в степени $0$ в иных случаях. Однако $x >y ≥0,$ поэтому $v(2023)> 1. p$ Значит, $v (2023)=2,p= 17,x =1,y = 0. p$ Получается, что если такое $p$ существует, то оно равно $17$ и входит в одно число в первой степени, а в другое — в нулевой. То есть либо $a= 17t,b= t,$ где $t$ не кратно $17,$ либо наоборот. Подставим $a= 17t,b= t$ в равенство и получим $t= 126,$ откуда $a= 2142,b= 126.$ Учитывая симметрию, запишем ответ.

Ответ:

$(4046,4046),(126,2142),(2142,126)$

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

Задача 20#75903

Натуральные числа $a,b,c$ таковы, что $a + b+ c b c a$ — целое. Докажите, что $abc$ — точный куб.

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

Приведём дроби к одному знаменателю: $a2c+b2a+c2b. abc$ Будем считать, что переменные взаимно просты, иначе можно просто сократить на НОД. Пусть некоторое простое число $p$ входит в $abc$ в некоторой натуральной степени. Все переменные на $p$ делиться не могут. Пусть на $p$ делится только одна переменная, например $a.$ Чтобы дробь была целой, необходимо, чтобы $2 cb$ делилось на $a,$ но этого не может быть, поскольку $2 cb$ не делится на $p,$ а $a$ — делится.

Значит, число $p$ распределено по двум переменным. Пусть оно входит в $a$ в степени $m,$ а в $b$ — в степени $n.$ Тогда в $2 ac$ оно входит в степени $2m,$ в $2 b a$ — в степени $2n +m,$ в $2 c b$ — в степени $n.$

Ясно, что $2m ≥ n,$ поскольку знаменатель, а также второе и третье слагаемые числителя делятся на $n p ,$ а значит и $2 a c$ делится на $n p .$ Значит степень вхождения $p$ в $2 a c$ не меньше $n.$ Предположим, что $2m ≥n +1.$ Заметим, что знаменатель делится на $n+1 p ,$ так как он делится на $n+m p ,$ а $n+ m ≥n+ 1.$ Также на $n+1 p$ делятся первое и второе слагаемые числителя. Значит, на $n+1 p$ делится и $c2b,$ однако $p$ входит в это число лишь в степени $n.$ Значит, $2m = n,$ то есть $p$ входит в $abc$ в степени $3m.$ В силу произвольности выбора $p$ получаем требуемое.

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

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