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

Делимость и делители (множители) → .02 Разложение на множители, основная теорема арифметики

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сколько существует семизначных натуральных чисел, у которых произведение трёх первых цифр равно $30,$ произведение трёх цифр, стоящих в центре, равно $7,$ а произведение трёх последних цифр равно $15?$

Источники: Муницип - 2022, Красноярский край, 7.3

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

Подсказка 1

Произведение 30 и 15 получить несложно...а вот получить 7 - есть всего один вариант! Какими тогда должны быть 3 центральные цифры?

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

Обозначим число $abcdefg.$ По условию $cde =7,$ значит, одна из этих цифр равняется $7,$ а две другие равны $1.$ Поскольку $30$ и $15$ не делятся на $7,$ $d= 7,c=e =1.$ Число $30= 5⋅6⋅1,$ поэтому получаем два трёхзначных числа $--- abc:561$ и $651.$ Число $15= 1⋅3⋅5,$ откуда получаем два трёхзначных числа $--- efg :135$ и $153.$ Окончательно получаем $2 ⋅2 =4$ числа.

Ответ: 4

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

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

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

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

Пусть $a + ...+ a = n 1 m$ , где $a ,...,a 1 m$ - натуральные числа. Докажите, что $n$ ! делится на произведение

a1!⋅a2!⋅...⋅am!

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

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

Подсказка 1

Мы знаем, как представить n в виде суммы. Попробуем представить n! в виде произведения, используя данные о сумме.

Подсказка 2

Заметим, что мы можем выразить n! как произведение a_1 подряд идущих чисел на a_2 подряд идущих чисел…и так далее…теперь нужно доказать делимость на произведение каждого из факториалов.

Подсказка 3

Быть может, мы сможем разбить произведение на группы, в каждой из которых произведение делится на определенный факториал?

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

Давайте для начала докажем вспомогательную лемму: произведение $k$ подряд идущих чисел делится на $k!$

.. (n+ 1)(n+ 2)⋅...⋅(n +k).k!

Заметим, что количество способов выбрать $k$ человек из $k +n$ равно

(n+-k)(n+-k−-1)⋅...⋅(n-+1) k!

Но количество способов - целое число, поэтому числитель делится на знаменатель. Лемма доказана.

Так как $a1+ a2+...+am = n,$ то $n!$ можно представить в виде произведения $a1$ подряд идущих чисел на $a2$ следующих чисел $...$ на $am$ последних чисел:

n!= (1⋅2⋅...a1)⋅((a1+ 1)⋅(a1+ 2)⋅...⋅(a1+ a2))⋅...⋅((n − am +1)⋅...⋅n)

Произведение $ai$ подряд идущих чисел делится на $ai!,$ поэтому $n!$ делится на произведение факториалов $a1!⋅...⋅am!$

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

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

Найдите наименьшее натуральное $n,$ для которого $(n +1)(n +2)(n +3)(n +4)$ делится на $1000.$

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

При любом натуральном n данное произведение делится на $8$ , так как среди любых четырёх последовательных натуральных чисел одно делится на $4$ и еще одно – на $2$ . Следовательно, достаточно найти наименьшее $n$ , для которого данное произведение делится на $3 125= 5$ . Так как на $5$ может делиться только один из множителей, то $n$ – наименьшее, если множитель, делящийся на $125$ , –– наибольший. Значит, $n +4 =125$ , то есть $n= 121$ .

Ответ: 121

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

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

Натуральные числа $a,b$ и $c$ таковы, что $c= b b a$ , а число $b2− a− c +1$ простое. Докажите, что $a$ и $c$ — удвоенные квадраты натуральных чисел.

Источники: КМО - 2022, первая задача первого дня для 8-9 классов, авторы Антропов А.В. и Белов Д.А. (cmo.adygmath.ru)

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

Из первого условия следует $b2 = ac$ . Подставим во второе условие, получим, что $ac− a− c+1= (a− 1)(c− 1)$ простое. При натуральных $a$ и $c$ это возможно только тогда, когда одна из скобок равна 1.

Пусть, не умаляя общности, $a− 1= 1$ , тогда $a =2$ и $2 b = ac= 2c$ . Следовательно, $b= 2k$ при некотором натуральном $k$ , и $2 c= 2k .$

Значит, и $a= 2$ , и $2 c =2k$ удвоенные квадраты натуральных чисел, что и требовалось.

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

Задача 45#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

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

Задача 46#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).$

Курсы

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

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

Задача 47#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.$

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

Задача 48#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)$

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

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

Пусть $m < n$ — натуральные числа. Доказать, что среди произвольных последовательных $n$ натуральных чисел всегда найдутся два, произведение которых делится на $mn$ .

Источники: Всесиб - 2021, 10.4 (см. sesc.nsu.ru)

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

Подсказка 1

Давайте немного усложним себе задачу (на самом деле облегчив этим поиск) и будем пытаться найти число которое делится на n, и ещё одно, которое делится на m.

Подсказка 2

Очевидно, среди n последовательных чисел всегда найдется число, делящееся на n, а так как m<n, то и для m найдется. Но есть загвоздка…

Подсказка 3

Что делать, если эти числа совпадают? Попытайтесь найти ещё одно такое число.

Подсказка 4

Пусть НОД(m,n)=d. Докажите, что среди n последовательных натуральных чисел найдется число 2d.

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

Среди $n$ последовательных чисел точно найдется то, которое делится на $n$ и то, которое делится на $m$ (так как $m < n$ ). Если это разные числа, то их произведение делится на $mn$ . Пусть это одно число $a$ , $НОД (m,n)= d$ и $′ m = dm$ , $′ n = dn$ . Тогда $.. ′ ′ a.dm n$ . Значит, нам нужно найти еще одно число, которое делится на $d$ . Так как $n> m ≥d$ , то $n ≥2d$ . Значит, среди $n$ последовательных чисел есть еще хотя бы одно, которое делится на $d.$

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

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

На доске написано число $1200$ . Петя приписал к нему справа $10n+ 2$ пятерок, где $n$ — неотрицательное целое число. Вася подумал, что это шестеричная запись натурального числа $x$ , и разложил $x$ на простые множители. Оказалось, что среди них ровно два различных. При каких $n$ это возможно?

Источники: СПБГУ-21, 11.4 (см. olympiada.spbu.ru)

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

Подсказка 1

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

Подсказка 2

Отлично! Теперь мы получаем, что наше число равно (102*7776ⁿ - 1)(102*7776ⁿ - 1). Попробуем подставить небольшие значения n. Что можно заметить про делители нашего числа?

Подсказка 3

Мы понимаем, что n = 0 точно подходит. Скобки (102*7776ⁿ - 1) и (102*7776ⁿ - 1) взаимно простые, а также наше число всегда делится на 101. Тогда стоит рассмотреть его по mod 101.

Подсказка 4

Попробуйте отдельно посмотреть на случаи, когда n чётно и нечётно, и в каждом из них применить неиспользованное ранее условие про количество различных простых множителей!

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

x =(1200 55...5) = (120100...0) − 1 =289⋅610n+2− 1= ◟1 ◝0n◜+2◞6 ◟10◝n◜+ ◞2 6 ( 5n )( 5n ) n n = 17⋅6⋅6 − 1 17⋅6⋅6 +1 = (102⋅7776 − 1)(102⋅7776 +1).

Если $n= 0$ , то $x= 101⋅103$ , что нам подходит. Пусть $n ≥1$ . Заметим, что

102mod 101 =1, 7776n mod 101= (77⋅101− 1)n mod101= (−1)n.

Положим $n n a= 102⋅7776 − 1,b =102⋅7776 +1$ . Эти числа взаимно просты, так как они нечётны и различаются на 2. Рассмотрим два случая.

1) $n$ чётно. Тогда $a$ делится на 101. Но $a$ и $b$ не имеют общих простых делителей, откуда $p a =101$ при некотором натуральном $p$ . Мы получим

p n n 101 − 1= 102 ⋅7776 − 2= 2(51⋅7776 − 1),

что невозможно, поскольку левая часть кратна 4 , а правая — нет.

2) $n$ нечётно. Тогда $b$ делится на 101 и аналогично $b= 101q$ при некотором натуральном $q$ . Поэтому

q n 101 − 1 =102⋅7776 ,

что невозможно, поскольку левая часть кратна 5 , а правая — нет.

Ответ: только при n = 0

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

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

Натуральные числа $n > 20$ и $k >1$ таковы, что $n$ делится на $k2.$ Докажите, что найдутся натуральные $a,$ $b$ и $c$ такие, что $n =ab+ bc+ca.$

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

Подсказка 1

Изначально у нас "слишком много свободы". Работать с тремя независимыми переменными трудно. Давайте считать, что число a уже дано. Как это помогает причесать исходное условие?

Подсказка 2

Числа b и c встречаются в исходном равенстве дважды, поэтому следить за ними не так просто. Можно ли преобразовать исходное равенство таким образом, чтобы они встречались в новом не более одного раза (число а при этом может встречаться произвольное число раз, мы же считаем его данным)?

Подсказка 3

Да, исходное равенство можно представить в виде n+a² = (b+a)(c+a). Как теперь можно сформулировать условие представимости для данных n и а?

Подсказка 4

Необходимо и достаточно, чтобы число n+a² представлялось в произведение двух натуральных, где каждое больше а. Вспоминая, что а произвольное, достаточно показать, что для данного n существует хотя бы одно a, для которого число n+a² раскладывается в произведение двух натуральных, где каждое больше а. Как исходя из этого, можно воспользоваться условием делимости n на k²?

Подсказка 5

Хотим положить a таким образом, чтобы каждое из двух множителей делилось на k. При этом a мы хотим сделать не очень большим, чтобы сделать множители большими, чем a было не очень сложно. Как это можно сделать?

Подсказка 6

Можно взять a наименьшим делителем k. Пусть n = lp² при некотором простом p. Докажите, что при l+1 > p работает соображение предыдущей подсказки. Как выглядят остальные случаи?

Подсказка 7

Число n представимо в виде (q-1)p² при некотором простом q < p+1. Разберем случай q < p. Воспользуйтесь представлением p = mq+r для натуральных m и q и преобразуйте полученное равенство.

Подсказка 8

Осталось разобраться со случаем p = q. Помните, что мы еще не пользовались условием на n>20.

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

Заметим, что из равенства $n+ a2 =(a+ b)(a+ c)$ следует равенство $n= ab+bc+ ca.$ Поэтому для решения задачи достаточно найти такое натуральное $a,$ что число $2 n+a$ раскладывается в произведение двух натуральных чисел $x$ и $y,$ больших $a$ (тогда можно положить $b= x− a$ и $c=y − a).$ Согласно условию, $2 n = ℓp$ для некоторых простого $p$ и натурального $ℓ.$

Если $ℓ+1 >p,$ то в силу разложения $2 2 n+ p = (ℓ+ 1)⋅p$ в качестве $a$ можно взять число $p.$ Также, если число $ℓ+ 1−$ составное, то $ℓ+ 1= st$ при $s,t>1;$ тогда снова можно положить $a= p,$ так как $2 2 n+ p = (ℓ+ 1)p = sp⋅tp.$

В оставшемся случае имеем $2 n= (q− 1)p$ при некоторых простом $q ≤ p.$ Если $p> q,$ то $p= mq+ r$ при некотором положительном $r< q$ и натуральном $m.$ Тогда число

n+ r2 = (q− 1)(r+ mq)2+r2 = q(p +mq)2− mq(2r+mq)

делится на $q,$ а частное от деления больше $r,$ поскольку $2 n= (q− 1)p > 1⋅q⋅r.$ Поэтому можно положить $a= r.$

Наконец, если $p= q,$ то $3 2 n = p − p ,$ причём $p≥ 5$ по условию. Тогда $2 3 2 ( 2 ) n +6 = p − p +36= (p+ 3) p − 4p +12 ,$ где обе скобки больше $6;$ в этом случае работает $a= 6.$

Интенсивы

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

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

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

Имеется дробь $1 n$ . Семиклассник Семёнов каждую минуту прибавляет к её числителю и знаменателю по $1$ и смотрит, можно ли сократить полученную дробь. Семёнов утверждает, что первый раз сократимая дробь получилась после $1000$ шагов. Стоит ли ему верить?

Источники: Высшая проба - 2020, 7.3 (см. olymp.hse.ru)

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

Подсказка 1

Давайте сначала поверим юному математику и посмотрим на дробь через 1000 минут. Какой вывод можно тогда сделать о делимости её знаменателя?

Подсказка 2

Верно, знаменатель кратен какому-то из простых делителей числа 1001. Пусть этот делитель равен p. Если бы мы хотели опровергнуть слова семиклассника, то скорее всего слова о том, что дробь сократилась впервые, верно?

Подсказка 3

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

Подсказка 4

Мы обнаружили число n + p - 1, которое делится на р. Это как будто знаменатель дроби через р-1 минуту. А что с её числителем? Найдём противоречие, которое искали в подсказке 2?

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

Предположим, что Семёнов сказал правду, то есть в первый раз числитель и знаменатель $1+k n+k$ имеют общий делитель больше единицы через $k= 1000$ минут.

Получится $-1001- 7⋅11⋅13 n+1000 = n+1000$ , откуда $n +1000$ делится на какое-то число из множества ${7,11,13},$ давайте это число обозначим буквой $p.$

Заметим, что $1001$ делится на $p$ (если непонятно, то посмотрите, что такое $p$ ). Тогда $p+ (n+ 1000)− 1001= n+ p− 1$ тоже делится на $p$ .

Но отсюда сразу следует, что дробь уже через $p− 1$ шагов сократима: $1+p−1- --p-- n−1+p = n+p−1$ . А Семёнов сказал, что первый раз дробь сократима будет через $1000$ шагов. Но $p− 1 <1000$ . Семёнов, ты не прав!

Ответ:

нет

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

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

Найдите количество восьмизначных чисел, произведение цифр которых равно $1400.$ Ответ необходимо представить в виде целого числа.

Источники: Физтех - 2020, 10 класс (см. olymp.mipt.ru)

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

Подсказка 1

Разложим 1400 на простые множители, чтобы посмотреть, какие вообще наборы цифр есть для того, чтобы составить нужные по условию числа.

Подсказка 2

Отлично, получается 3 набора: "22255711", "42557111" и "85571111". Перестановкой цифр в каждом наборе мы получаем нужное число. Поработаем с первым набором: допустим, в нем все цифры разные, тогда подошло бы 8! чисел. Но теперь заметим, что не все цифры одинаковые, например, двойки повторяются 3 раза. Это значит, что на самом деле подходящих чисел в 3! раз меньше. То же проделаем и с пятерками (и с единичками тоже).

Подсказка 3

Отлично, в первом наборе получили 8! / (3! * 2! * 2!) вариантов. Аналогично считаем варианты и в втором, и в третьем наборах. Теперь остается сложить все эти варианты и получить итоговый ответ.

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

Разложим $1400$ на множители. $1400 =5⋅280= 52⋅56 =52⋅7⋅8= 23⋅52⋅7.$ Значит, искомые числа могут состоять из следующих цифр:

1) три двойки, две пятёрки, одна семёрка и две единицы,

2) четвёрка, двойка, две пятёрки, одна семёрка и три единицы,

3) восьмёрка, две пятёрки, одна семёрка и четыре единицы.

В первом случае способов выбрать места для двоек можно $3 8⋅7⋅6 C8 = 3!$ способами, так как нам нужно выбрать три места из восьми для двоек. Затем выбрать места для пятёрок $2 5⋅4 C5 = 2!$ вариантов, затем одно из трёх оставшихся мест для семёрки $3$ способами, а остальные места займут единицы, поэтому всего в этом случае $8⋅7⋅6 5⋅4 -3!-⋅-2! ⋅3= 1680$ вариантов.

В втором случае способов рассуждения абсолютно аналогично для трёх единиц, двух пятёрок, семёрки, но дальше есть ещё 2 способа выбрать место двойке, а оставшееся место занимает четвёрка. В этом случае $1680⋅2$ вариантов.

В третьем случае выбрать места для единиц можно $C48 = 8⋅7⋅64!⋅5$ способами, далее для двух пятёрок $C24 = 4⋅32$ способа, оставшиеся восьмёрку и семёрку ставим двумя способами. Всего получается $70⋅6⋅2= 840$ вариантов.

Итого $1680⋅3+ 840 =5880$ вариантов.

Ответ:

$5880$

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

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

Приведите пример числа, делящегося на $2020,$ в котором каждая из десяти цифр встречается одинаковое количество раз.

Источники: ММО - 2020, первый день, 11.1 (см. mmo.mccme.ru)

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

Подсказка 1

В этой задаче достаточно привести хотя бы один пример и обосновать его корректность. Попробуем подойти к такому примеру! Первым шагом нужно понять, а на что должно делиться число. Ага, сразу можем назвать последнюю цифру числа, уже что-то. Сможем привести пример, где все цифры встречаются только один раз?

Подсказка 2

Обратим внимание на 101. Нам нужен просто пример (необязательно наименьшее число), надо взглянуть на числа, которые делятся на 101. У многих из них повторяются цифры (2020, 2121, 3030, 4343 и др), а ведь нам как раз нужен пример, где всех цифр одинаковое количество!

Подсказка 3

Мы на финишной прямой! Осталось только собрать такой пример (мы уже поняли, что каждой цифры должно быть по две), осталось не забыть, что число должно не только оканчиваться на ноль, но и делиться на 4

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

Рассмотрим число

98987676545431312020

(существуют и другие примеры).

Поскольку $2020 =4 ⋅5 ⋅101,$ число делится на $2020,$ если оно делится на $4,$ $5$ и $101.$ Приведённое число оканчивается на $20,$ следовательно, делится на $4$ и $5.$ Числа вида $abab$ равны $101⋅ab.$ А поскольку приведённое число раскладывается в сумму чисел вида $abab⋅10k,$ оно делится на $101.$

Ответ:

$98987676545431312020$

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

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

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

Источники: Всесиб-2019, 8.2 (см. sesc.nsu.ru)

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

Подсказка 1

В таких задачах стоит иногда попробовать подобрать какие-то варианты. И здесь начнем замечать интересное: если есть простым делителем 5 или, например, 7, тогда новое число не делится на 5 или 7. Обобщим эту догадку.

Подсказка 2

И действительно, при р > 3 всегда будут проблемы при делении числа N на р. Представьте N в виде произведения двоек и троек, где двойки войдут со степенью, например, k.

Подсказка 3

Да, получится N = 2^k * 3^(10-k), а теперь фокус: двойки превращаются в тройки, а тройки - в четверки, то есть в двойки в квадрате! Остается найти k, и так получим ответ!

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

Рассмотрим наибольший простой делитель $p$ числа $N.$

Если $p> 3$ , то все остальные делители меньше его хотя бы на $2$ (иначе есть чётное просто число больше двойки).

После увеличения всех простых множителей на $1$ получатся:

$p+ 1$ : это не кратно $p$ , ведь $p+1-=1 + 1 p p$ , а $1< p.$
любое другое простое после увеличения на $1$ будет меньше $p$ (ведь изначально оно было меньше $p$ хотя бы на $2$ ), значит, также не кратно $p$ .

Отсюда заключаем, что случай $p >3$ невозможен, поскольку новое число не поделится на $p$ и соответственно не поделится на $N.$

Тогда можно представить $N$ в виде $N =2k⋅310− k$ . Увеличим все простые множители на $1$ , получим $3k ⋅410−k = 3k⋅220−2k$ , по условию это кратно $2k ⋅310−k$ .

Значит, $20 − 2k≥ k,k≥ 10 − k ⇐ ⇒ k ∈[5,20∕3]$ . Подходят только $k∈ {5;6}$ . Осталось привести пример этих чисел и написать ответ.

Ответ:

$25⋅35,26⋅34$

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

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

В ряд выписывают дроби $-1-,-2-,-3-,...,4060,4061. 4061 4060 4059 2 1$ Сколько всего целых чисел встретится в таком ряду?

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

Подсказка 1

Наши числа имеют вид (4062-x)/x. Нам надо найти количество целых чисел, когда x пробегает от 1 до 4061. Как вы думаете, при каком условии на x это число будет целым?

Подсказка 2

(4062-x)/x = 4062/x - 1. Тогда нужно всего лишь обеспечить целость числа 4062/x. Стало быть x- делитель 4062. Посчитайте количество делителей числа 4062 (только не забудьте, что x<4062) и радуйтесь жизни!

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

Сумма числителя и знаменателя каждой дроби равна $4062$ , то есть каждая дробь имеет вид $4062−x x$ , где $x$ – натуральное число, не превосходящее $4061$ . Число $4062−x 4062 x = x − 1$ будет целым, когда число $x$ - делитель $4062$ .

Поскольку $4062 =2 ⋅3 ⋅677$ , где числа $2$ , $3$ и $677$ – простые, у числа $4062$ будет $8$ делителей. И так как $x< 4062$ , $x$ может принимать одно из $7$ значений (все делители $4062$ , кроме самого числа), чтобы дробь $4062−x x$ была целой.

Ответ: 7

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

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

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

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

Найдите все натуральные числа, у которых разность между суммой двух самых больших собственных делителей и суммой двух самых маленьких собственных делителей является простым числом. (Делитель натурального числа называется собственным, если он отличен от $1$ и самого этого числа.)

Источники: Высшая проба - 2019, 9.5(см. olymp.hse.ru)

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

Подсказка 1

Ну, во-первых, нужно обрести понимание о том, как устроены наименьшие собственные делители. Для этого вспомним, что по Основной Th. Арифметики n = p₁^a₁*p₂^a₂*...*p_k^a_k (p₁ < ... < p_k) для любого натурального n. Тогда какой наименьший собственный делитель?

Подсказка 2

Верно! Это p₁. Что насчёт следующего по величине собственного наименьшего делителя?

Подсказка 3

Очевидно, что это не p₃, p₄ и т.д. Значит это что-то связанное с p₂ или p₁, причём очевидно, что степень тоже не больше 2. Итого?

Подсказка 4

Верно, либо p₁^2, либо p₂. Пусть эти два наим. делителя это a и b. Что тогда можно сказать про наибольшие собственные делители?

Подсказка 5

Так точно! Это n/a и n/b. Теперь стоит рассмотреть случаи.

Подсказка 6

1-ый случай. a = p₁, b = p₂ - простые. Тогда p = (n/a + n/b) - a - b, где p - простое. То есть pab = (n - ab)(a+b). Посмотрим на делимость, не забывая о том, что a, b, p - простые.

Подсказка 7

Проделайте это сами и поймите, что p = (p₁+p₂). Отсюда в силу чётности и простоты: p₁ = 2, n = 4p₂. Отсюда найдите ответ. Попробуйте разобрать второй случай самостоятельно.

Подсказка 8

2 случай. a = p₁, b = p₁^2. Тогда аналогично получаем, что p₁^2*p = (p₁ + 1)(n - p₁^3). Теперь осталось немного.

Подсказка 9

Воспользуйтесь взаимной простотой p₁ и p₁ + 1 и решите задачу) Успехов!

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

Имеет место один из двух случаев.
(a) Пусть оба наименьших делителя $p$ и $q$ — простые числа. Тогда простым будет число $n n r= (p + q)− (p+ q),$ откуда $pqr= (p +q)(n − pq).$ Поскольку числа $p+q$ и $pq$ взаимно просты, то $r =p +q,$ откуда $p= 2$ и $n = 4q.$ Но тогда в силу выбора $q$ получаем $q = 3$ и $n= 12.$
(b) Пусть наименьшие делители имеют вид $p$ и $2 p ,$ где $p$ простое. Тогда простым будет число $n n- 2 r= (p + p2)− (p+ p),$ откуда $2 3 p r= (p +1)(n − p ).$ Поскольку числа $p$ и $p+1$ взаимно просты, то $r= p+ 1.$ Это возможно только в случае $p= 2,r =3.$ В этом случае $2 3 p =n − p ,$ откуда $n= 12.$ Но этот случай невозможен, так как у $12$ один из двух наименьших делителей это $3.$

Ответ:

$12$

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

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

Может ли сумма объёма, длин всех рёбер и площадей всех граней некоторого прямоугольного параллелепипеда, длины рёбер которого являются целыми числами, равняться $866?$

Источники: Всесиб-2018, 11.3 (см. sesc.nsu.ru)

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

Подсказка 1

Давайте для начала введём неизвестные (скажем, стороны это a,b,c) и попробуем записать сумму из условия через эти неизвестные. По условию эта сумма равна 866

Подсказка 2

Так, Вы должны были получить abc+4(a+ b+c)+ 2(ab+ bc+ ac)=866. Теперь полезно разложить на множители левую часть уравнения. Нужно добавить такое число, чтобы левая часть хорошо свернулась на симметричные относительно a,b,c скобочки. Ну же, не зря мы ботали тождественные преобразования!

Подсказка 3

Добавить нужно 8. У Вас должно получиться (а+2)(b+2)(c+2) = 2*437. Осталось совсем чуть-чуть, подумайте над этим равенством в терминах разложения на множители!

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

Пусть длины сторон $a,b,c.$ Они положительные (как длины сторон) и целые (по условию), значит, натуральные. Сумма объёма, длин всех рёбер и площадей всех граней равна $866,$ то есть:

abc+ 4(a +b+ c)+2(ab +bc+ ac)= 866

3 (a+2)(b+ 2)(c+ 2)=866+ 2 = 2⋅437

Правая часть является произведение простых чисел $2,19$ и $23,$ так что по основной теореме арифметики следует, что это единственное разложение данного числа в произведение трёх натуральных чисел, больших единицы, и одно из них равно $2.$ Однако левая часть уравнения является произведением трёх натуральных чисел, каждое из которых не меньше трёх, что приводит к противоречию. Следовательно, равенство из условия задачи невозможно.

Ответ:

нет

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

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

По определению $n!= 1⋅2⋅3⋅...⋅n$ . Является ли выражение $1008!⋅1009!⋅2017!⋅2018!$ квадратом натурального числа?

В ответ внесите “да” или “нет”.

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

Подсказка 1

Давайте попробуем преобразовать наше выражение в более удобный вид, где мы сразу поймём квадрат это или нет. У нас есть две пары соседних факториалов. Как тогда можно записать их по-другому?

Подсказка 2

Верно, можем записать 1009! в виде 1008!*1009, а 2018! — 2017!*2018. Тогда у нас получаются два факториала в квадрате умножить на 1009 и 2018. Может ли такое число быть квадратом?

Подсказка 3

Верно, раскладывая ещё эти числа на множители мы получаем квадрат, умноженный на 2. Теперь понятно, что это число не может быть полным квадратом. Победа!

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

Заметим, что

2 1008!⋅1009!= (1008!) ⋅1009

2 2017!⋅2018!= (2017!) ⋅2018

Получаем, что

1008!⋅1009!⋅2017!⋅2018!=(1008!)2⋅(2017!)2⋅1009⋅2018= (1008!⋅2017!⋅1009)2⋅2

Число вида $2a2$ не может быть точным квадратом по основной теореме арифметике, ведь степень вхождения множителя $2$ в число $2a2$ всегда нечётна.

Ответ: нет

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

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

Числа от $1$ до $50$ написаны на карточках. Можно ли разложить эти карточки в $11$ мешков (чтобы в каждый мешок попала хотя бы одна карточка) так, чтобы в каждом мешке произведение чисел на карточках делилось на $9$ ?

В ответ внесите “да” или “нет”.

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

Подсказка 1

Давайте, прочитав условие, поймём, а когда вообще произведение чисел в мешке будет делиться на 9? Какие возможны варианты?

Подсказка 2

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

Подсказка 3

Ага, у нас получается пять чисел, кратных 9, и 11 чисел, кратных 3, но не кратных 9. Но получится ли тогда у нас раскидать их по мешкам, чтобы соблюдалось условие? Проверьте это, и задача решена!

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

Чтобы произведение чисел на карточках делилось на $9$ , то в мешке либо должна быть хотя бы одна карточка, число на которой делится на $9$ , либо хотя бы две карточки, числа на которых делятся на $3$ , но не делятся на $9$ . Среди чисел от $1$ до $50$ есть пять чисел кратных $9$ — $9$ , $18$ , $27$ , $36$ и $45$ . Их хватит на не более чем пять мешков. Чисел от $1$ до $50$ , которые кратны $3$ , но не кратны $9$ , всего $11$ — $3$ , $6$ , $12$ , $15$ , $21$ , $24$ , $30$ , $33$ , $39$ , $42$ , $48$ . Этих чисел также хватит не более чем на пять мешков. Получается, что максимум в десяти мешках произведение чисел может делиться на $9$ — противоречие.

Ответ: нет

Предыдущая подтема

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