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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Докажите, если целые числа $a$ и $b$ взаимно просты в $ℤ,$ то они взаимно просты и в $ℤ[i].$

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

Будем искать их НОД в $ℤ[i]$ с помощью алгоритма Евклида. Рано или поздно мы получим, что $(a;b)= 1,$ поскольку они взаимно просты в $ℤ.$ Тогда их НОД в $ℤ[i]$ содержит лишь четыре делителя единицы, а значит они взаимно просты в $ℤ[i].$

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

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

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

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

Докажите, что если $N(α)$ является простым числом в $ℤ,$ то $α$ является простым числом в $ℤ[i].$

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

Предположим противное, пусть $α = γ⋅β$ ( $γ$ и $β$ не являются делителями $1$ ), но тогда $N (α)= N (γ)⋅N(β),$ значит либо $N (γ),$ либо $N (β)$ равна $1.$ Но тогда одно из этих чисел является делителем $1,$ противоречие, что и требовалось.

Ответ:

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

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

(a) Пусть $p$ — простое число вида $4k +3.$ Докажите, что $p$ является простым гауссовым числом.

(b) Пусть $p$ — простое число вида $4k +1.$ Докажите, что существуют натуральные числа $a$ и $b$ такие, что $a$ и $b$ не делятся на $p,$ но $a2 +b2$ кратно $p.$

(c) Пусть $p$ — простое число вида $4k+ 1.$ Докажите, что в кольце гауссовых чисел число $p$ является составным и имеет разложение на множители вида $p= (a+ bi)(a− bi).$

(d) Докажите, что простое гауссово число может быть либо натуральным простым вида $4k+ 3,$ либо числом $a +bi,$ где $a2+ b2$ — простое число вида $4k+ 1$ или $2.$

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

(a) Предположим противное, пусть $p= ab,$ где $a$ и $b$ — простые числа, отличные от делителей $1,$ тогда $N(p)= N(a)N (b).$ То есть $2 p = N(A)N(b).$ Нормы не равны $1,$ значит $N(a)= N(b)= p,$ но каждая из норм представляет из себя сумму квадратов двух целых чисел. Таким образом, $2 2 p= x +y ,$ но число $4k+ 3$ не представимо в виде суммы квадратов, пришли к противоречию, что и требовалось.

(b) Подойдут $a =(p−21)!$ и $b= 1,$ поскольку:

( )2 (p-− 1)! +1 =(p−-1)!⋅1⋅2⋅...⋅ p-− 1 +1 ≡(p−-1)!⋅(−1)p−21⋅ p+-1⋅ p+-3⋅...⋅(p− 1)+ 1= 2 2 2 2 2 2

= (p− 1)!+1 ≡0 (mod p)

последнее сравнение верно по теореме Вильсона.

(c) Используем результат прошлого пункта, пусть $2 p−1- a +1 =kp,a= ( 2 )!,b,k∈ℤ,a$ и $b$ не делятся на $p,$ тогда $kp =(a+ i)(a− i).$ Если $p$ — простое гауссово число, то одна из скобочек правой части делится на него. Не умаляя общности, пусть $a+ i$ кратно $p,$ тогда $a+ i= p(x +yi)=px+ pyi.$ Таким образом, $py =1,$ противоречие.

В первом пункте мы поняли, что если число не простое, то оно представимо в виде суммы квадратов, но тогда $2 2 p =a + b = (a+ bi)(a − bi).$

(d) Насчёт целых гауссовых чисел известно следующее, что $± p$ и $p⋅(±i)$ являются простым и что если норма гауссового числа проста в $ℤ,$ то само оно простое в $ℤ[i].$

Пусть у гауссового числа либо вещественная, либо мнимая часть равна $0,$ а другая равна составному числу или простому числу вида $4k+ 1,$ тогда оно, очевидно, не является простым.

Пусть у гауссового числа $a+ bi$ ненулевые вещественная и мнимая части, при этом норма не является простым числом, однако само оно — простое. Тогда число $a − bi$ также простое. Но тогда норма $N(a+ bi)= (a+bi)(a− bi)$ раскладывается на простые множители, на которые выражение $(a +bi)(a− bi)$ делиться не может, противоречие.

Ответ:

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

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

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

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

Предположим противное, тогда $p =x2+ y2 = a2+b2,$ откуда $(x +yi)(x− yi)= (a+bi)(a− bi).$ Числа $x+ yi,x− yi,a+ bi$ и $a− bi$ являются простыми в $ℤ[i].$ Получается, что произведение двух простых чисел равно произведению двух других простых чисел, в $ℤ[i]$ так не бывает.

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

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

Докажите, что число $5n$ раскладывается в сумму двух квадратов целых чисел $[n]+ 1 2$ различными способами.

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

Заметим, что $5= (1 +2i)(1− 2i),$ откуда $5n =(1+ 2i)n(1− 2i)n.$ Рассмотрим для любого целого $0 ≤k ≤ n 2$ число $k n−k ak+ bki=(1+ 2i) (1− 2i) .$ При замене $i$ на $− i$ получим, что $k n− k ak− bki= (1− 2i)(1+ 2i) .$ Следовательно,

2 2 n n n ak+ bk = (ak+ bki)(ak− bki)= (1+2i)(1− 2i) = 5

Осталось заметить, что все пары $(a ,b) k k$ будут различны, откуда и получаем $[n]+1 2$ различных способов разложения числа $5n$ в сумму двух квадратов целых чисел.

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

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

Для натурального числа $n$ есть ровно два из чисел $1,2,...,2022,$ на которые оно не делится. Пусть эти числа — $a$ и $b.$ Может ли оказаться, что $a− b =13?$

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

Подсказка 1

Попробуем идти от противного. Сразу ясно, что одно из чисел a или b четно. Назовем это число 2k. Может ли n не делиться на k?

Подсказка 2

Если n не делится на k, то k и 2k — те самые числа, на которые n не делится. Тогда k = 13. Может ли так получиться?

Подсказка 3

Верно, не может! Тогда n не делится на 39 и многие другие числа. Тогда выходит, что n не делится именно на 2k. А по какой причине?

Подсказка 4

Верно! Из-за того, что степень вхождения двойки в 2k больше, чем в n. А какой вывод можно сделать тогда о делимости n на степени двойки?

Подсказка 5

Верно! Тогда n не делится на наибольшую степень двойки 1024, которая есть среди наших чисел. А на какое число тогда наше n еще не делится?

Подсказка 6

Верно, n не делится на 1011 и 1037! Являются ли эти числа простыми?

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

Будем рассуждать от противного. Тогда одно из чисел $a$ и $b$ — чётное. Обозначим это число через $2k.$ Если $n$ не делится на $k,$ то $k$ и $2k$ как раз и есть два числа из $1,2,...,2022,$ на которые не делится $n.$ Поэтому $2k− k= 13,$ откуда $k= 13.$ Но тогда $n$ не делится также на число $39,$ и чисел, на которые не делится $n,$ хотя бы $3.$

Значит, $n$ не делится на $2k$ потому, что в $2k$ двойка содержится в большей степени, чем в $n.$ Тогда $n$ не делится на наибольшую степень двойки среди $1,2,...,2022,$ то есть на $1024.$ Таким образом, пара чисел, на которые не делится $n$ — это $(1024,1037)$ или $(1011,1024).$ Но $1037= 17⋅61$ и $1011= 3⋅337,$ поэтому в обоих случаях $n$ не делится также на одно из простых чисел $17,61,3$ или $337.$

Ответ:

Нет, не может

Курсы

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

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

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

Найдите наименьшее натуральное $n$ такое, что натуральное $n2+14n+ 13$ делится на $68.$

Источники: ВСОШ - 2022, школьный этап, 8 класс

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

Разложим выражение на множители:

2 n + 14n+ 13= (n+1)(n+13).

Так как $68= 2⋅2⋅17$ , то исходное выражение должно быть чётным, значит, $n$ —нечетное число и

⌊n+ 1= 17a, a∈ ℤ ⌈ n+ 13= 17b, b∈ ℤ

Так как нужно найти минимальное нечётное $n$ , то $b= 2$ , то есть

n +13= 17⋅2⇒ n =21.

Осталось проверить,что исходное выражение будет кратно 4. Действительно,

.. 212+14⋅21+ 13= 768.4

Ответ: 21

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

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

Ваня загадал два натуральных числа, произведение которых равняется $7200.$ Какое наибольшее значение может принимать НОД этих чисел?

Источники: ВСОШ - 2022, школьный этап, 9 класс

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

Поскольку каждое из этих чисел делится на их НОД, то их произведение делится на квадрат этого НОД. Наибольший точный квадрат, на который делится число $5 2 2 7200= 2 ⋅3 ⋅5 ,$ это $( 2 )2 3600= 2 ⋅3⋅5$ , поэтому НОД двух искомых чисел не превосходит 60. При этом НОД может равняться 60, если искомые два числа это 60 и 120.

Ответ: 60

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

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

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

Источники: ВСОШ - 2022, школьный этап, 10 класс

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

Наибольший делитель $n$ равен $n.$ Так как $n$ нечетно, то средний по величине не превосходит $n, 3$ а, поскольку делители различны, третий по величине не превосходит $n 5.$ Тогда имеем

n n 23n 10327= d1 +d2+ d3 ≤ n+ 3 + 5 = 15

Таким образом, $n≥ 6735.$ Заметим, что $6375$ подходит, так как оно нечетно, делится на $3$ и $5,$ и $6375 6375 6375+ -3- + -5-= 10327.$

Ответ: 6735

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

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

Назовём главными делителями составного числа $n$ два наибольших его натуральных делителя, отличных от $n.$ Составные натуральные числа $a$ и $b$ таковы, что главные делители числа $a$ совпадают с главными делителями числа $b.$ Докажите, что $a =b.$

Источники: ВСОШ, ЗЭ, 2022, 9.1, 10.1 и 11.1 (см. olympiads.mccme.ru)

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

Подсказка 1:

Если известны главные делители, то можно найти и два наименьших делителя, отличных от 1.

Подсказка 2:

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

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

Пусть $n >k$ — главные делители числа $a;$ тогда $a n$ и $a k$ — два наименьших делителя числа $a,$ больших единицы. Пусть $p$ — наименьший простой делитель числа $a,$ а $q$ — наименьший простой делитель $a,$ кроме $p$ (если такой существует). Тогда $a∕n= p.$ Далее, $a∕k$ — либо простое число (тогда это $q$ ) либо составное. Во втором случае единственным простым делителем числа $a∕k$ является $p,$ и потому $2 a∕k= p;$ этот случай реализуется ровно тогда, когда $a$ делится на $2 p ,$ причём $2 p <q$ или $q$ не существует.

Итак, главные делители числа $a$ — это либо $a p$ и $a q,$ либо $a p$ и $a- p2.$ Покажем теперь, что по двум главным делителям $n >k$ составное число $a$ восстанавливается однозначно (откуда и следует требуемое). Если $n$ кратно $k,$ то выполнен второй случай, и тогда $n2 a =-k .$ Иначе выполнен первый случай, и тогда $a= HOK (n,k).$

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

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

Натуральное число $n$ таково, что числа $4n$ и $6n$ имеют поровну натуральных делителей. Могут ли числа $12n$ и $18n$ тоже иметь поровну натуральных делителей?

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

Первое решение. Пусть число $4n$ имеет в разложении на простые множители число $3k$ , тогда $6n$ имеет $3k+1$ . Пусть общее число делителей равно $M$ . Тогда делители числа $4n$ разбиваются на $k+ 1$ одинаковых групп по степени вхождения $3$ , а делители числа $12n$ будут разбиваться на $k+ 2$ таких же групп. Т.е. число $12n$ содержит $k+2 M ⋅k+1$ натуральных делителей. Аналогично, число $18n$ будет содержать $k+3 M ⋅k+2$ натуральных делителей. Эти количества не равны.

Второе решение. Пусть в разложении числа $2n$ по основной теореме арифметики двойка содержится в степени $k$ , а тройка в степени $m$ . Если у числа $2n$ натуральных делителей $D$ штук, то по формуле количества натуральных делителей:

у числа $4n$ их $k+2 D ⋅k+1$ ,

у числа $6n$ их $m+2 D ⋅m+1-$ ,

у числа $12n$ их $k+2 m+2 D ⋅k+1 ⋅m+1$ ,

у числа $18n$ их $D ⋅ mm++32$ .

По условию $kk++21 = mm++21$ , поэтому $kk++21 ⋅ mm++21-= (mm++21)2$ , что не равно $mm++32-$ , потому что уравнение $(x+ 1)3 =x2(x+2) ⇐⇒ x2+ 3x +1 =0$ не имеет решений в натуральных числах.

Ответ:

нет

Интенсивы

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

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

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

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

Источники: Муницип - 2021, 10 класс

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

Подсказка 1

Попробуйте посмотреть на разные числа и их сумму делителей. Если брать не простое число большее 7, то чаще всего сумма делителей числа минус само число будет сильно больше 5. То есть, нам нужно искать эти числа именно по тому признаку, что сумма их делителей достаточно маленькая, но это не простые числа, так как сумма делителей простого чисел отличается всего на 1 от него самого. Подумайте, на что тогда может делиться наше число.

Подсказка 2

Давайте рассуждать. Пусть оно делиться, к примеру на 7 и не равно 7. Тогда сумма делителей числа n - это 1, n, 7, n/7… и еще какие-то, которые мы не знаем. Но сумма делителей в данном случае хотя бы n + 1 + 7, то есть, больше чем n + 6(как требует задача). Значит, на 7 оно не может делиться. А на что-то большее может? Тоже нет. Значит, осталось рассмотреть случаи когда n делиться только на какие-то числа от 2 до 6. При этом, как мы поняли, сумма делителей, которые не равны 1 и n, равна 5. Какие тогда числа могут быть делителями n?

Подсказка 3

Верно, числа 2, 3, 5. Если 5 , то больше делителей отличных от 1 и n нет, а значит - это число 25. А если на 2 делиться, то другой делитель это как раз 3, и поскольку тогда n делиться на 6, но это не может быть его делителем, отличным от 1 и n, значит n = 6. Победа.

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

Заметим, что один из делителей числа $n$ — самое число $n$ . Поэтому условие на самом деле означает, что сумма остальных делителей $n$ равна 6. Среди делителей точно есть 1, значит, сумма остальных делителей равна 5. Три делителя не могут давать сумму 5. Два делителя, больших 1, дают в сумме 5, только когда это 2 и 3, а один делитель равен 5, только если это само число 5.

В первом случае все делители числа — это 1, 2, 3 и само число. Так как у числа, делящегося на 2 и 3, точно есть делитель 6, то $n =6$ .

Во втором случае все делители числа — это 1, 5 и само число. Значит, $n= 5k$ . Но $k ⁄=1$ , а при $k⁄= 5$ у числа $n$ был бы ещё делитель $k$ , отличный от выписанных. Значит, $k = 5$ и $n = 25$ .

Ответ: 6 25

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

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

Найдите наибольшее значение выражения

(5n− 18)НОД-(n-+9,n+-2) F = НОК(n+ 9,n +2)

на множестве натуральных чисел. При каком $n$ оно достигается?

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

Подсказка 1

Числа n+2 и n+9 это же достаточно близкие числа, при этом их разность равна 7. Что тогда можно сказать про их НОД?

Подсказка 2

Да, их НОД либо равен 1, либо равен 7. Обозначим его за d. Какая замена тогда просится, если у нас есть НОК и НОД одних и тех же чисел?

Подсказка 3

Ну конечно, замена НОК(a,b)=ab/НОД(a,b). Тогда наше выражение принимает понятный вид. Осталось исследовать функцию, которая получается делением нашего выражения на d^2 и понять, где она принимает максимальное значение.

Подсказка 4

Да! В точке 12. А что еще принимает максимальное значение в точке 12? Поймите это и получите ответ!

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

Обозначим $d= НОД (n +9,n+ 2).$ Так как $n+ 9$ и $n+ 2$ делятся на $d,$ то их разность $(n +9)− (n +2)= 7$ делится на $d.$ Тогда $d =1$ или $d= 7.$

Как известно, $НОК(a,b)⋅НО Д(a,b)= a⋅b,$ откуда выражение из условия принимает вид

(5n− 18)⋅d2 F (n)= (n+-2)(n+-9)

Поскольку $d$ может принимать значения только двух констант: $1$ или $7,$ то нам достаточно будет максимизировать функцию

G (x)= ---5x-− 18-, x> 0 (x+ 2)(x+ 9)

Эта функция определена уже при всех действительных $x$ , потом учтём, что у нас было натуральное $n$ . Для максимизации посмотрим на её производную:

′ 5(x2+-11x+-18)−-(5x−-18)(2x+-11)- (x-− 12)(5x+-24) G(x)= (x +9)2(x+ 2)2 =− (x+ 2)2(x+9)2

Производная при $x> 0$ имеет ровно одну точку экстремума $x =12$ (это кстати натуральное число), которая является точкой максимума, потому является глобальным максимумом при $x> 0.$ А ещё удачным образом при $n= 12$ имеем $d =7$ — также принимает максимальное значение, потому при $n = 12$ достигает максимума и функция $F.$ Равен этот максимум

--5⋅12−-18-- F(12)= (12+9)(12+ 2) ⋅49= 7

Ответ:

$7$ при $n= 12$

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

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

Сколько существует пар натуральных чисел $(a,b)$ , у которых $НО К(a,b)= 23 ⋅32⋅5⋅72 = 17640$ , а $НОД(a,b)= 12$ ? (пары неупорядоченные, то есть $(a,b)$ и ( $b,a)$ считайте одинаковыми)

Среди всех таких пар укажите ту, для которой $a +b$ принимает минимально возможное значение, и найдите это значение.

Источники: Росатом - 2021, 11.3, комплект 1 (см. olymp.mephi.ru)

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

Подсказка 1

Вспомним основную теорему арифметики - из нее следует, что НОК и НОД это взятие соответственно максимума и минимума по степеням простых множителей в наших двух числах. У наших чисел всего максимум 4 вида простых множителей -2,3,5,7. Попробуйте с этим знанием понять, какие степени этих множителей могут быть в наших числах.

Подсказка 2

Например, в 12 двойка входит во 2 степени, а в 17640 в 3. Тогда получаем min(степень 2 в первом числе, степень 2 во втором числе}= 2,max = 3. Попробуйте применить аналогичное рассуждение к остальным делителям и посчитать количество вариантов!

Подсказка 3

Подумаем о минимальной сумме: Мы знаем, что из основной теоремы арифметики следует, что a⋅b= НОК (a,b)⋅НОД(a,b)= 12⋅17640! Тогда мы знаем произведение чисел. Давайте попробуем понять, когда сумма двух чисел минимальна, если произведение фиксировано!

Подсказка 4

Это происходит, когда числа максимально близки друг к другу! Например, 4*5 = 20 = 10*2, то 4+5 < 2+10. Для того, чтобы строго это доказать, можем обратить к производной этого выражения. Осталось подобрать числа, которые будут максимально близки, при этом давать в произведении 12*17640! И проверку не забыть :)

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

Из основной теоремы арифметики следует, что $НО К$ и $НО Д$ двух чисел можно рассматривать как взятие соответственно максимума и минимума по степеням простых множителей в этих двух числах. Пусть $a2,a3,a5,a7$ — степени соответствующих простых в числе $a$ . Пусть $b2,b3,b5,b7$ — степени соответствующих простых в числе $b$ .

Поскольку $2 12= 2 ⋅3$ , то получаем $min{a2,b2}= 2,max{a2,b2}= 3$ , то есть для степеней двоек есть два случая $(a2,b2)= (2,3),(3,2)$ , которые мы считаем одним. Для степеней троек аналогично получаем $(a3,b3)= (1,2),(2,1)$ , для остальных действуем полностью аналогично. В итоге получается $4 2$ случаев. В условии написано, что пары $(a,b)$ неупорядоченные, т.е. $(a,b) =(b,a)$ , поэтому общее число пар должно быть уменьшено вдвое.

Для поиска наименьшей суммы приведём два способа:

Первый способ.

Из основной теоремы арифметики следует, что $a⋅b= НОК (a,b)⋅Н ОД(a,b)= 12⋅17640$ . По неравенству о средних при фиксированном произведении чисел их сумма тем больше, чем больше одно число отличается от другого (сумма вида $x+ 1764x0⋅12$ , производная которой равна $1− 1764x0⋅212$ возрастает при $√------- √---- x> 17640 ⋅12= 12 1470$ ). Поэтому нам нужно найти максимально близкое значение к корню из этого произведения. $12$ это общий НОД, так что остаётся составить из имеющихся множителей ближайшее к $√---- 1470≈ 38$ число.

a′ = 2⋅3⋅5= 30→ b′ =49→ a1+ b1 = 79→ a+ b= 12 ⋅79= 948

Второй способ.

Просто сделаем полный перебор для этих восьми пар, чтобы быстро посчитать и забрать свои баллы за задачу

2 1 0 0 3 2 1 2 22 ⋅31⋅50⋅72+23⋅32⋅51⋅70= 12 +17640 =17652 2 ⋅3 ⋅5 ⋅7 +2 ⋅3 ⋅5 ⋅7 = 588+ 360= 948 22 ⋅31⋅51⋅70+23⋅32⋅50⋅72 = 60 +3528= 3588 22 ⋅31⋅51⋅72+23⋅32⋅50⋅70 = 2940+ 72= 3012 22 ⋅32⋅50⋅70+23⋅31⋅51⋅72 = 36 +5880= 5916 22 ⋅32⋅50⋅72+23⋅31⋅51⋅70 = 1764+ 120 =1884 22 ⋅32⋅51⋅70+23⋅31⋅50⋅72 = 180+ 1176 =1356 22 ⋅32⋅51⋅72+23⋅31⋅50⋅70 = 8820+ 24= 8844

Осталось выбрать наименьшую сумму и выписать ответ.

Ответ:

$8$ пар, наименьшее значение суммы равно $948$

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

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

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

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

$n =1$ — точный квадрат, такое значение пойдет в ответ.

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

Далее докажем, что для составных $n$ на доске появится точный квадрат. Пусть $n$ — наименьшее составное число, для которого это не так. Разложим его на простые множители и получим $α1 α2 αm n= p1 ⋅p2 ⋅...⋅pm .$ Так как $n$ составное, либо $m ≥2,$ либо $m = 1$ и $α1 ≥2.$

Тогда у $n$ будет ровно $(α1 +1)⋅(α2+1)...(αm +1)$ делителей. Если все числа $α1,...,αm$ — четные, тогда $n$ будет точным квадратом, так как $α1 αm- n =(p12⋅...⋅pm2 )2$ и такое $n$ подойдет.

Иначе число делителей $(α1+ 1)⋅(α2+ 1)...(αm + 1)$ — четное число, при этом оно не равно $2,$ так как либо $m ≥2,$ либо $α1+ 1≥ 2+ 1= 3.$ Значит, $(α1 +1)⋅(α2 +1)...(αm+ 1)$ — составное число.

Также $(α1+1)⋅(α2+1)...(αm +1)< n$ для $n> 2,$ так как количество делителей числа $n$ не больше, чем количество чисел от $1$ до $n.$ И при этом все числа от $1$ до $n$ не могут быть делителями числа $n> 2,$ иначе $2k ≤ n< 2k+1$ для некоторого натурального $k> 1,$ тогда либо $n$ не делится на $2k,$ либо $n= 2k$ и тогда оно не делится на $3.$

В итоге, количество делителей числа $n$ — какое-то составное число меньшее $n,$ но $n$ — наименьшее составное число не дающее точного квадрата. После появления на доске $(α1 +1)⋅(α2 +1)...(αm+ 1)< n$ через некоторое время на доске будет точный квадрат. Противоречие. Значит, не существует составных чисел, от которых на доске не появляется точный квадрат.

Ответ:

Для составных $n$ и $n= 1$

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

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

Дано натуральное число $n,$ большее $2.$ Докажите, что если число $n!+ n3+ 1$ — простое, то число $n2 +2$ представляется в виде суммы двух простых чисел.

Источники: Олимпиада Эйлера, 2021, РЭ, 9 задача(см. old.mccme.ru)

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

Как известно, $n3+ 1= (n+ 1)(n2− n+ 1).$ Так как оба сомножителя в правой части тут меньше, чем $(n+ 1)2,$ если один из них — составное число, то у него есть делитель $d,$ больший $1,$ но не больший $n.$ Но тогда и число $3 n!+ n + 1$ делится на $d,$ что противоречит его простоте. Значит, числа $2 n − n+ 1$ и $n+ 1$ — простые, а в сумме они как раз дают $2 n + 2.$

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

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

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

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

Представить число 2021 в виде суммы трех взаимно простых чисел.

Источники: Росатом - 2021, 11.3, комплект 2 (см. olymp.mephi.ru)

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

Подсказка 1

Давайте попробуем идейно сконструировать, что мы вообще хотим. То есть, какая бы ситуация нас устраивала. А устраивала бы нас ситуация, если бы у нас было число x, потом число кратное х, мы бы вычли 1 из второго числа и получили бы искомую тройку. Осталось подобрать такой х.

Подсказка 2

Поскольку все знают разложение на простые номеров ближайших лет(одно из самых полезных знаний на любой олимпиаде), то всем известно, что 2021 = 43 * 47(не очень то сложный был год), а значит можно представить 2021 как сумму 43, 1 и 43 * 46 - 1 и это будет выполнять условие задачи.

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

2021 =43⋅47= 43+ 43 ⋅46= 43+ 1+ (43⋅46− 1)

Ответ:

$43+ 1+ (43⋅46− 1)$

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

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

Про натуральные числа $a,b,c$ известно, что $a+ b+ НОД(a,b)= b+ c+ НОД(b,c)= a+ c+Н ОД(a,c).$ Верно ли, что какие-то два числа равны?

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

Первое решение. Предположим, что все числа разные. Без ограничения общности можно считать, что $a< b< c.$ Заметим, что $(a,b)≤ b− a,$ то есть $a+ b+ (a,b)≤2b.$ С другой стороны $b+ c+(b,c)> 2b,$ поэтому равенство невозможно.

Второе решение. Предположим, что все числа различны. Пусть $(a,b)$ — наибольший из трёх НОДов, при этом $b >a.$ Из второго равенства получаем $(a,c)− (b,c)= b− a ≥(a,b).$ Что противоречит максимальности.

Ответ:

Верно

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

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

Обозначим через $d(k)$ количество натуральных делителей натурального числа $k.$ Докажите, что для каждого натурального $n,$

d(1)+d(3)+d(5)+...+ d(2n − 1)< d(2)+ d(4)+ d(6)+ ...+d(2n)

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

Рассмотрим произвольное нечётное натуральное число $t$ от $1$ до $2n.$ Оно является делителем чисел $t,2t,3t,....$ Число $t$ как делитель $t$ посчитано в левой части неравенства, как делитель $2t$ — в правой части, как делитель $3t$ — в левой части, и так далее, то есть то, в какой части посчитан делитель $t,$ чередуется, начиная с левой части. Нас интересует $t$ как делитель чисел, не превосходящих $2n.$ Поэтому цепочка в какой-то момент оборвётся, и в итоге $t$ будет посчитано слева максимум на $1$ раз больше, чем справа.

Таким образом, за счёт нечётных делителей левая часть больше правой максимум на $n.$ Но мы ещё никак не учли чётные делители, коих хотя бы $n:2,4,...,2n.$ Все они посчитаны как делители только в правой части. В итоге правая часть не меньше левой. Заметим, что при $n = 1$ неравенство верно, а при $n ≥2,$ в левой части будет ещё хотя бы один раз посчитан делитель $2$ у числа $4,$ поэтому правая часть строго больше левой

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

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

Сколько существует делителей числа $20212021$ , кубический корень из которых является натуральным числом?

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

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

Подсказка 1:

2021 — большое число и рассуждать про него в целом неудобно, надо как-то разбить его на множители, как?

Подсказка 2:

Разложим его на простые! 2021 = 43*47. Какой тогда вывод можно сделать про делители числа 43²⁰²¹47²⁰²¹?...

Подсказка 3:

Именно! Они все имеют вид 43^α * 47^β, где α, β — натуральные и α, β ∈ [0; 2021]. Какие из них будут искомыми делителями?

Подсказка 4:

Те, что представимы в виде 43^{3n}*47^{3m}, где n, m — натуральные и n, m ∈ [0, 673]. Сколько тогда есть способов выбрать такой делитель? Осталось посчитать количество делителей. Успехов!

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

Так как $2021= 43⋅47$ , все делители числа $20212021$ имеют вид $43α⋅47β$ , где $α,β ∈[0;2021]$ . При этом точными кубами являются числа вида $3n 3k 43 ⋅47$ , где $3n,3k∈ [0;2021]$ , то есть $n,k ∈[0;673]$ . Таких чисел $2 674 = 454276$ .

Ответ:

$6742 = 454276$

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