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

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

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

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

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

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

Подтемы раздела делимость и делители (множители)

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

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

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

Для натурального числа $n$ обозначим через $S n$ наименьшее общее кратное всех чисел $1,2,3,...,n.$ Существует ли такое натуральное число $m,$ что $Sm+1 = 4Sm?$

Источники: Всеросс., 2023, РЭ, 9.6(см. olympiads.mccme.ru)

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

Подсказка 1

Предположим, что это возможно и посмотрим на максимальную степень двойки, которую можно найти среди первых n+1 чисел. А что можно сказать о степени двойки, которую можно найти среди первых n чисел?

Подсказка 2

Верно! Если максимальная степень двойки среди первых n+1 чисел равна k, то среди первых n точно не меньше k/2. Какой вывод можно сделать?

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

Предположим, что такое $m$ существует. Пусть $S m+1$ делится на $2s,$ но не делится на $2s+1.$ Тогда $s≥ 2.$ Значит, среди чисел $1,...,m+ 1$ есть число $a$ , делящееся на $s 2 .$ Но тогда число $a∕2$ делится на $s−1 2 ,$ поэтому $Sm$ делится на $s−1 2 .$ Тогда, поскольку $Sm+1 = 4Sm,$ то $Sm+1$ делится на $s+1 2 ,$ что неверно.

Ответ:

Нет

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

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

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

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

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

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

Рассмотрим 16 различных простых чисел. Обозначим их через $p,p ,...,p 1 2 16$ . Через $x$ обозначим квадрат их произведения. Возьмем наши 16 чисел, равными $x--x -x- p1,p2,...,p16$ . Заметим, что в произведение двух любых наших чисел каждое из 16 простых чисел входит хотя бы во второй степени. Но в каждом из наших чисел каждое простое входит в 1 или во второй степени, поэтому произведение любых 2 чисел будет делиться на любое число. Сами числа друг на друга очевидно не делятся (у каждого свое уникальное простое входит в разложение в первой степени, остальные простые — во второй).

Ответ: Существуют

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

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

Про натуральные числа $m$ и $n$ известно, что $3n3 = 5m2$ . Найдите наименьшее возможное значение $m +n$ .

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

Обозначим через $n 3$ и $m 3$ степени вхождения числа $3$ в $n$ и $m$ соответственно. Тогда из равенства степени вхождения 3 в правую и левую части получаем, что $3n3+1 =2m3$ . Из этого условия легко видеть, что $m3 ≥ 2$ , $n3 ≥1$ . Проделаем аналогичные рассуждения для числа 5. Введя аналогичные обозначения, получаем, что $2m5+ 1= 3n5$ , откуда $n5 ≥ 1$ , $m5 ≥1$ . Таким образом, мы доказали, что $n ≥3⋅5 =15$ , $m ≥ 9⋅5 =45$ . Тогда $m + n≥ 15 +45= 60$ . Легко видеть, что такая сумма могла оказаться, так как $3 2 3⋅15 = 5⋅45$ .

Ответ: 60

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

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

Ответ:

Нет, не может

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

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

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

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

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

Подсказка 1

Каким способом можно доказать, что состояние фиксированного объекта в процессе его изменения не приведёт к тому, что он примет начально состояние?

Подсказка 2

Найти полуинвариант! Давайте найдем величину, которая будет меняться монотонно в ходе процесса, и, как следствие, не вернется к изначальному состоянию.

Подсказка 3

Как найти полуинвариант в данной задаче? В условии задачи сказано, что при замене двух чисел x и y на их сумму x+y, второе число равно x-y или y-x. Было бы хорошо, если бы наш полуинвариант вел себя одинаково вне зависимости от этого выбора. Ясно, что данные числа равны по модулю. Как это помогает найти полуинвариант?

Подсказка 4

Пусть S является искомым полуинвариантом. Ясно, что S - это функция от набора чисел, написанных на доске в данный момент. Если мы положим в качестве S функцию от их квадратов, то значение S будет совпадать при выборе любой из разности чисел (x-y или y-x), что является хорошим знаком. Осталось доопределить S.

Подсказка 5

Самые естественные функции от набора переменных - их сумма или произведение. С суммой в данном случае работать проще (итак, в качестве предполагаемого полуинварианта мы пока положим S - сумму квадратов чисел написанных на доске), поскольку мы можем легко получить значения данного полуинварианта на каждом ходу. Поймите, как это можно сделать.

Подсказка 6

Если на доске были написаны числа x² и y², то сумма их квадратов измениться на (x-y)²+(x+y)²=2(x²+y²). Таким образом, значение S после каждого шага увеличивается вдвое. Осталось показать, что не существует двух различных последовательностей из 2n идущих подряд чисел таких, что отношение сумм их квадратов равно степени двойки. Каким способом это возможно сделать?

Подсказка 7

Мы можем показать, что степень вхождения двойки в сумму квадратов 2n последовательных чисел является инвариантом для данного n. Для этого можно явно показать, как степень вхождения двойки в рассматриваемую сумму зависит от n.

Подсказка 8

Пусть 2n=l*2^k, где l - нечетное натуральное число, k - натуральное число, не меньшее 1. Докажите, что степень вхождения двойки в сумму квадратов 2n последовательных чисел равна k-1.

Подсказка 9

Искомую сумму можно представить как l сумм 2^k последовательных квадратов натуральных чисел. Если мы докажем, что каждая из них имеет вид 2^{k-1}t, для некоторого нечетного числа t, то явно получим, что и вся сумма делится на 2^{k-1}, но не делится на 2^k. Сделайте это!

Подсказка 10

Рассмотрим сумму последовательных 2^k квадратов по модулю 2^k. Квадраты этих чисел имеют тот же набор остатков при делении на 2k, что и набор чисел 1², 2², 3²,..., (2^k)², а значит сравнимо по этому модулю c суммой 1²+2²+...+(2^k)². Каким образом ее можно преобразовать?

Подсказка 11

По известной формуле суммы квадратов первых n чисел, 1²+2²+...+(2^k)²=2^{k-1}(2^k+1)(2^{k+1}+1)/3 - кратно 2^{k-1}, но не кратно 2^k. Это как раз то, что мы хотели показать!

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

Рассмотрим набор из $2k$ подряд идущих чисел, квадраты этих чисел имеют тот же набор остатков при делении на $2k,$ что и набор чисел $2 2 2 ( k)2 1 ,2,3,..., 2 .$ Поскольку

2 2 2 ( k)2 1 +2 + 3 + ...+ 2 (= )( ) ( )( ) = 2k-2k+-1-2-⋅2k+-1-= 2k−12k+-1-2⋅2k-+1-- 6 3

сумма квадратов $k 2$ подряд идущих чисел делится на $k−1 2 ,$ но не делится на $k 2 .$

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

В то же время сумма квадратов имеющихся чисел после замены удваивается. Действительно, заменив числа $a$ и $b$ на $a− b$ и $a+ b,$ получим:

( ) (a− b)2+ (a+ b)2 = 2a2+2b2 = 2 a2 +b2

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

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

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

Найдите все натуральные $m$ и $n,$ удовлетворяющие равенству

n n n n−1 (2 − 1)(2 − 2)...(2 − 2 )= m!

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

Далее в решении, как обычно, $v (N) p$ — показатель наибольшей степени простого числа $p,$ делящей $N.$

Пусть $n n n ( n n− 1) Ln = (2 − 1)(2 − 2)(2 − 4)...2 − 2 .$ Тогда

n n (n n−1) 1+2+⋅⋅⋅+(n−1) n (n−1 ) ( 1 ) Ln =(2 − 1)(2 − 2)⋅⋅⋅2 − 2 = 2 (2 − 1)2 − 1 ⋅⋅⋅ 2 − 1

следовательно,

n(n−-1) v2(Ln)= 1+2 +⋅⋅⋅+ (n− 1) = 2

С другой стороны, по формуле Лежандра, верно неравенство

∞∑ ⌊ ⌋ ∑∞ v2(m!)= mi < mi = m i=1 2 i=12

Приравнивая показатели, имеем

n(n-− 1) 2 = v2(Ln)= v2(m!)< m

Кроме этого заметим, что

Ln = (2n− 1)(2n− 2)⋅⋅⋅(2n − 2n−1)< (2n)n = 2n2

Мы хотим показать, что для всех $n ≥6$ верно

( ) 2n2 < n(n-− 1) 2

что влечет невозможность равенства $Ln = m!$ для указанных $n.$

Для $n =6$ имеем

( ) 262 < 6.9⋅1010 < 1.3 ⋅1012 < 15!< n(n−-1) 2

Пусть $n≥ 7,$ тогда

( n(n − 1)) n(n− 1) n(n−1)−15 --2----!= 15!⋅16⋅17 ⋅⋅⋅--2---->236⋅16 2 = 22n(n− 1)−24 = 2n2 ⋅2n(n−2)−24 >2n2

Таким образом, необходимо проверить выполнение исходного равенства для $n ≤5.$ Имеем

L1 = 1= 1!, L2 = 6= 3!, 5!< L3 = 168 <6!, 7!< L4 = 20160< 8! и 10!< L5 = 9999360< 11!

Наконец, уравнение имеет два решения

(m,n)∈ {(1,1),(3,2)}

Ответ:

$(1,1),(3,2)$

Курсы

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

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

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

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

Источники: Олимпиада Эйлера, 2019, дистанционный тур

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

Подсказка 1

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

Подсказка 2

Верно! Число 97 входит только в 4 факториала. Тогда, чтобы создать куб, один из них нужно вычеркнуть. А можно ли посмотреть теперь на какое-то другое простое число?

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

Если произведение оставшихся факториалов — куб натурального числа, то для любого простого числа степень, в которой оно входит в это произведение, должна делиться на $3.$ Простое число $97$ входит ровно в четыре факториала: от $97!$ до $100!,$ и в каждый — в первой степени. Поэтому вычеркнут должен быть один из этих четырех факториалов. Но тогда простое число $89$ будет входить ровно в $11$ факториалов: от $89!$ до $100!,$ исключая вычеркнутый. Противоречие.

Ответ:

нельзя

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

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

Тройка целых чисел $(x,y,z),$ наибольший общий делитель которых равен $1,$ является решением уравнения

2 2 3 2 2 y z+ yz =x + x z− 2xz

Докажите, что $z$ является кубом целого числа.

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

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

Подсказка 1

В исходном выражении уже есть куб. Можно ли как-то его переписать так, чтобы получилось, что z делит этот куб?

Подсказка 2

Верно! z(y² + yz - x² + 2xz) = x³. Теперь, если доказать, что НОД z и y² + yz - x² + 2xz равен 1, то задача будет решена. Как это сделать?

Подсказка 3

По алгоритму Евклида можно получить, что НОД этих чисел такой же, как НОД z и y² - x². Пойдем от противного: может ли этот НОД быть равен t > 1?

Подсказка 4

Точно! Если t > 1, то x³ делится на t. Кроме того, t делится на некоторое простое q, а тогда и x делится на это q. Какой вывод можно сделать?

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

Запишем равенство в следующем виде: $z(y2+ yz− x2 +2xz)= x3.$ Если мы докажем, что НОД $z$ и $y2+yz− x2+ 2xz$ равен $1,$ то тогда $z$ будет кубом. Предположим, что $z$ в этой ситуации не является кубом. Тогда в разложение $z$ входит какое-то простое число $p$ в степени, не кратной $3.$ Скобка $2 2 y + yz− x +2xz$ на $p$ не делится, значит $p$ входит в $3 x$ в степени, не кратной $3,$ чего быть не может.

Итак, докажем взаимною простоту $z$ и $2 2 y + yz− x + 2xz.$ Ясно, что НОД этих чисел равен НОДу $z$ и $2 2 y − x .$ предположим, что этот НОД равен $t> 1.$ Тогда $3 x$ делится на $t.$ Пусть $t$ делится на некоторое простое число $q,$ тогда на $q$ делится $x$ и $2 2 y − x .$ Значит, $y$ также делится на $q.$ Также $z$ делится на $t,$ а значит и на $q.$ Получается, что НОД $x,y$ и $z$ больше $1,$ противоречие. Значит, НОД $z$ и $2 2 y − x$ равен $1,$ что и требовалось.

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

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

Назовём натуральное число убывающим, если каждая цифра в его десятичной записи, кроме первой, меньше или равна предыдущей. Существует ли такое натуральное $n,$ что число $n 16$ — убывающее?

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

Подсказка 1

Попробуйте собрать по больше информации про это число. Какие содержит цифры, на что делится?

Подсказка 2

Стоит определять цифры с конца, но как это сделать. Что может помочь в этом.

Подсказка 3

Это число делится на все степени до 2^n. А какой признак делимости на степени двойки?

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

Заметим, что десятичная запись числа $16n$ оканчивается на $6.$ Кроме того, это число делится на все степени двойки с показателями от $1$ до $4n.$ Следовательно, число составленное из $k$ последних цифр в записи $n 16$ должно делиться на $k 2 .$

Рассмотрим число, составленное из двух последних цифр в десятичной записи числа $n 16 .$ Если число $n 16$ — убывающее, то это $66,76,86$ или $96.$ Но числа вида $...66$ или $...86$ не делятся на $4,$ а число вида $99...96$ (других цифр впереди быть не может) делится на $3,$ а $n 16$ на $3$ не делится. Следовательно, число составленное из двух последних цифр, это $76.$

Рассуждая аналогично для чисел, составленных из трёх, четырёх, пяти и шести последних цифр, получим, что число $n 16$ должно оканчиваться на $987776.$ Это число не делится на $2 16 =256,$ поэтому не может быть степенью $16,$ а число $9987776$ не делится на $27 = 128.$ Значит, чисел, удовлетворяющих условию задачи, не существует.

Ответ:

нет

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

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

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

Источники: Всеросс., 2016, РЭ, 9.3(см. olympiads.mccme.ru)

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

Подсказка 1

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

Подсказка 2

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

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

Рассмотрим степени двойки, на которые делятся выписанные числа; пусть $2k$ — наибольшая из них. Если хотя бы два выписанных числа делятся на $k 2,$ то два соседних таких числа будут различаться на $k 2 .$ Значит, одно из них делится на $k+1 2 ,$ что невозможно в силу выбора $k.$ Следовательно, среди выписанных чисел ровно одно делится на $k 2 .$

Наименьшее общее кратное группы, содержащей это число, будет делиться на $k 2,$ а НОК оставшейся группы — не будет. Значит, сумма этих НОК не делится на $k 2 ;$ с другой стороны, эта сумма больше чем $k 2 .$ Поэтому эта сумма не может быть степенью двойки.

Ответ:

Нет

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

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

Пусть $p> 2$ — натуральное число, не делящееся на $3.$ Рассмотрим все целые числа $a,a ,...,a 1 2 k$ из интервала $(− p,p) 22$ такие, что $ai ≡ p (mod 3)$ для всех $i=1,2,3,...,k.$ Докажите, что произведение

p− a1 p− a2 p− ak -|a1|-⋅-|a2|-⋅...⋅-|ak|-

является натуральной степенью тройки.

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

Подсказка 1

Рассмотрим, например, p - a₁. Выделим из него максимальную степень тройки. То есть представим в виде p - a₁ = k₁b₁, где k₁ — степень тройки, а b₁ не делится на 3. Если так сделать для всех i, то получится, что нужно разделить произведение степеней тройки и каких-то чисел b₁b₂..., не делящихся на 3, на произведение чисел, не делящихся на 3, |a₁a₂...|. Если доказать, что эти произведения равны, то все получится. Как можно это сделать?

Подсказка 2

Чисел b₁... столько же, сколько чисел a₁... Попробуем доказать, что на самом деле они равны. Для этого сначала исследуем числа |a₁|... Можно ли доказать, что они различны?

Подсказка 3

Верно! Они не равны, поскольку тогда мы бы получили, что какие-то два из них противоположны, что означало бы, что 2p делится на 3, что по условию неверно. А можно ли теперь доказать, что |a₁|... — на самом деле и есть все числа в интервале (0;p/2), не делящиеся на 3.

Подсказка 4

Верно! Если возьмем число t, не делящееся на 3 в промежутке (0;p/2), то либо t, либо -t совпадает с p по модулю 3. А, если вспомнить определение чисел a₁..., то получится, что t или -t с одним из них совпадает. А тогда и получится нужное утверждение. А можно ли теперь и про числа b₁... доказать то же самое?

Подсказка 5

Легко проверить, что все b₁... лежат в интервале (0;p/2). А можно ли теперь проверить, что все они различны?

Подсказка 6

Предположим, что какие-нибудь два из этих чисел совпали и обозначим их e и f, а соответствующие им числа из a₁, ... g и h. Как мы знаем, g и h различны. Тогда что можно сказать о величине (p - g)/(p - h)?

Подсказка 7

Верно! Мы предположили, что e = f, а поскольку g и h различны, можно считать, что p - g > p - h. Тогда это отношение не меньше трех. С другой стороны, поскольку g и h — числа из промежутка (-p/2;p/2) получаем, что это отношение строго меньше трех. Тогда все числа b₁... различны. Как теперь доказать, что эти числа являются ровно теми числами, которые не делятся на 3 из промежутка (0; p/2)?

Подсказка 8

Возьмем некоторое t, не делящееся на 3, из промежутка (0;p/2). Тогда можно указать такую степень тройки k, что p - kt тоже число из промежутка (0;p/2), при этом p - kt имеет тот же остаток, что и p при делении на 3. Какой вывод можно сделать?

Подсказка 9

Верно! Тогда p - kt является одним из чисел a₁... Тогда и t является одним из чисел b₁. Как теперь доказать, что значение искомого выражения является степенью тройки?

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

Ясно, что все $|a | i$ принадлежат интервалу $(0,p) 2$ и различны, поскольку если $a = −a , i j$ то $a +a = 0, i j$ откуда $2p ≡0 (mod 3),$ что неверно по условию задачи.

Еще заметим, что каждое число, не делящееся на $3,$ из интервала $p (0,2)$ совпадает с одним из $|ai|.$ Действительно, пусть $p t∈ (0,2)$ и $t$ не делится на $3.$ Тогда либо $t≡ p (mod 3),$ либо $− t≡ p (mod 3).$ Тогда одно из чисел $± t$ совпадает с $ai,$ откуда получаем, поскольку $t> 0$ , что $t= |ai|.$ Тогда получаем, что множество всех $|ai|$ совпадает с множеством всех чисел из интервала $p (0;2),$ не делящихся на $3.$

Пусть $c 3 i$ — максимальная степень тройки, делящая $(p− ai).$ Поскольку $p ≡ai (mod 3),$ имеем $ci > 0.$ Пусть $c p− ai = 3ibi,$ где $bi$ не делится на $3.$ Заметим, что все $bi$ лежат в интервале $p (0,2),$ поскольку $p p − 2 < ai < 2$ и, следовательно $p−ai p 0< -3ci-< 2.$ Докажем, что все $bi$ различные. Предположим противное: $bi = bj$ для некоторых $i,j.$ Мы знаем, что $p− ai ⁄= p− aj,$ поэтому $ci ⁄= cj.$ Пусть $ci >cj$ Тогда

ci pp−− aai-= 33cjbbi≥ 3 j j

С другой стороны,

p−-ai< 3p∕2-< 3 p− aj p∕2

Таким образом, мы получаем противоречие, и $bi ⁄= bj$ для всех $i,j.$ Докажем теперь, что любое число, не делящееся на $3$ из интервала $p (0,2)$ совпадает с одним из $bi.$ Действительно, пусть $p t∈ (0,2),$ $3⁄|p.$ Тогда существует такое $c,$ что $c p 3p t⋅3 ∈(2,2 ),$ следовательно, $c p p p− t⋅3 ∈(−2,2)$ и при этом $c p− t⋅3 ≡p (mod 3).$ Тогда $c p− t⋅3 = ai$ при некотором $i.$ Но тогда $c p − t⋅3 = ai,$ откуда $t= bi.$

Итак, множество всех чисел $bi$ совпадает с множеством всех чисел, не делящихся на $3$ в интервале $p (0,2),$ поэтому совпадает с множеством $|ai|.$

Тогда имеем

c1+c2+...+ck p− a1-⋅ p− a2-⋅...⋅ p−-ak-= 3-----⋅b1b2...bk= 3c1+c2+...+ck |a1| |a2| |ak| |a1||a2|...|ak|

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

Интенсивы

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

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

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

По кругу стоят $101000$ натуральных чисел. Между каждыми двумя соседними числами записали их наименьшее общее кратное. Могут ли эти наименьшие общие кратные образовать $1000 10$ последовательных чисел (расположенных в каком-то порядке)?

Источники: Всеросс., 2014, РЭ, 10.7(см. olympiads.mccme.ru)

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

Пусть $n =101000.$ Обозначим исходные числа (в порядке обхода) через $a ,...,a ; 1 n$ мы будем считать, что $a = a. n+1 1$ Положим $bi = HOK (ai,ai+1).$ Предположим что числа $b1,...,bn$ — это $n$ подряд идущих натуральных чисел.

Рассмотрим наибольшую степень двойки $m 2 ,$ на которую делится хотя бы одно из чисел $ai.$ Заметим, что ни одно из чисел $b1,...,bn$ не делится на $m+1 2 .$ Пусть для определённости $.. m a1.2 ;$ тогда $.. m b1.2$ и $.. m bn.2 .$ Значит, $m b1 = 2 x$ и $m bn = 2 y$ при некоторых нечётных $x$ и $y.$ Без ограничения общности можно считать, что $x <y.$ Тогда, поскольку $b1,...,bn$ образуют $n$ последовательных чисел, среди них должно быть и число $m 2 (x +1)$ (поскольку $m m m 2 x <2 (x+ 1)< 2 y).$ Но это число делится на $m+1 2$ (так как $x +1$ четно), что невозможно. Противоречие.

Ответ:

Не могут

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

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

На доске в строчку написано $n$ подряд идущих натуральных чисел в порядке возрастания. Под каждым из этих чисел написан его делитель, меньший этого числа и больший $1.$ Оказалось, что эти делители тоже образуют строчку подряд идущих натуральных чисел в порядке возрастания. Докажите, что каждое из исходных больше, чем $nk p1p2...pk-,$ где $p1,$ $p2,...,pk$ — все простые числа, меньшие $n.$

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

Подсказка 1

Попробуйте выделить некоторый инвариант для всех пар (a, b) чисел верхней строчке и числа под ним.

Подсказка 2

Для всех пар разность a-b фиксирована. Пусть она равна c. Что можно сказать про с?

Подсказка 3

Для любой пары (a, b) число c делится на НОД(a, b). Как можно оценить снизу значение c?

Подсказка 4

В нижней строчке встречается по крайней мере одно число, которое кратно числу k при всех k <= n. Как эти рассуждения можно связать с простыми числами меньшими n?

Подсказка 5

Число c делится на наибольшую не превосходящую n степень любого простого числа p, меньшего n, а, значит, и на произведение этих степеней по всем таким p. Как это помогает получить искомую оценку?

Подсказка 6

Пусть p^s — наибольшая степень p, не превосходящая n, тогда любое из исходных чисел не меньше чем, с > p^s > n/p для любого p.

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

Заметим, что все разности между числами и записанными под ними их делителями равны одному и тому же числу $c.$ Пусть $p$ — простое число, меньшее $n,$ а $s p$ — наибольшая его степень, не превосходящая $n.$ Тогда среди чисел во второй строке найдется делящееся на $s p.$ Но тогда на $s p$ делится и записанное над ним число в первой строке, а, значит, и число $c.$ Таким образом, число $c$ делится на наибольшую не превосходящую $n$ степень любого простого числа $p,$ меньшего $n,$ а, значит, и на произведение этих степеней по всем таким $p.$ Осталось заметить, что $s p > n∕p$ и любое число в исходной строке больше $c.$

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

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

Для натурального $n$ обозначим $S =1!+ 2!+ ...+ n!. n$ Докажите, что при некотором $n$ у числа $S n$ есть простой делитель, больший $2012 10 .$

Источники: Всеросс., 2012, ЗЭ, 11.8(см. olympiads.mccme.ru)

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

Для простого $p$ и натурального $n$ обозначим через $v (n) p$ степень, в которой $p$ входит в разложение $n$ на простые множители. Заметим, что если $vp(n)⁄= vp(k)$ , то $vp(n ±k)= min(vp(n),vp(k)).$

Предположим противное, обозначим $2012 P = 10 .$ Тогда все простые делители чисел вида $Sn$ не превосходят $P.$

______________________________________________________________________________________________________________________________________________________

Лемма: Пусть $vp(Sn)< vp((n+ 1)!)$ при некотором $n.$ Тогда $vp(Sk) =vp(Sn)$ при всех $k≥ n.$

Доказательство: Обозначим $a= vp(Sn),b=vp((n +1)!),$ тогда $b ≥a+ 1.$ Заметим, что если $Sk = Sn+ (n+ 1)!+...+k!.$ В этой сумме все слагаемые, кроме первого, делятся на $a+1 p .$ а первое делится лишь на $a p .$ но не на $a+1 p .$ Значит и $Sk$ делится на $a p ,$ но не на $a+1 p .$

______________________________________________________________________________________________________________________________________________________

Рассмотрим некоторое простое $p≤ P.$ Ввиду леммы, если $vp(Sn)< vp((n+ 1)!)$ при некотором $n,$ то существует число $ap$ такое, что $vp(Sn) ≤ap$ при всех натуральных $n.$ Назовём такое простое число $p$ маленьким, все остальные простые числа, меньшие $P,$ назовём большими. Так как маленьких простых конечное количество, существует натуральное $M,$ большее любого числа вида $pap,$ где $p$ — маленькое.

Пусть теперь $p$ — большое простое число, а $n$ — такое число, что $p|n+ 2.$ Тогда из леммы имеем $vp(Sn+1)≥ vp((n +2)!)> vp((n+ 1)!),$ а это означает, что $vp(Sn)= vp(Sn+1− (n +1)!)= vp((n+ 1)!)=vp(n!).$ Последний переход верен, так как $n+ 1$ не кратно $p.$

Рассмотрим теперь $N = M ⋅P!− 2.$ По доказанному, $vp(SN)= vp(N!)$ для любого большого простого $p.$ Кроме того, поскольку $N ≥ M,$ то $vp(SN)≤ vp(pap)≤vp(N!)$ для любого маленького простого $p.$ Поскольку все простые делители числа $SN$ — либо большие, либо маленькие, отсюда следует, что $SN ≤ N!,$ что, очевидно, неверно. Противоречие.

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

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

Натуральные числа $b$ и $n,$ большие 1, таковы, что для каждого натурального $k > 1$ существует натуральное число $a k$ такое, что $b− an k$ делится на $k.$ Докажите, что $n b =A$ для некоторого натурального $A.$

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

Пусть $b= pα1...pαs, 1 s$ где $p i$ — различные простые числа. Тогда нам нужно показать, что все $α i$ делятся на $n.$ Рассмотрим $k= b2.$ Тогда $n b− ak$ делится на $2 b,$ в частности, на каждое $2αi pi ,$ что больше, чем $αi pi .$ Тогда

n αi ak ≡ b≡ 0 (mod pi )

n αi+1 ak ≡b⁄≡ 0 (mod pi )

Значит, степень вхождения $pi$ в $αn k$ — это в точности $αi,$ но эта степень делится на $n,$ что и требовалось доказать.

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

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

Найдите все наборы из $100$ чисел таких, что сумма четвёртых степеней любых четырёх чисел делится на их произведение.

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

Подсказка 1

Пусть a — НОД всех чисел из набора. Рассмотрите любые 4 элемента этого набора и обозначьте их за ax, ay, az, at. Попробуйте записать условие на эти числа...Ого! Да ведь a сократилось и набор x, y, z, t тоже подходит под условие задачи.

Подсказка 2

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

Подсказка 3

И правда, нетрудно получить, что единственный простой делитель элементов множества — 3. Также можно оценить степень вхождения 3 в элементы набора. В конце не забудьте сделать проверку!

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

Пусть ${a }100 ii=1$ — один из искомых набров. Пусть $α = НОД{a }100> 1. ii=1$ Тогда для любых четырех элементов $αx,αy,αz,αt$ верно

4 4 4 4 4 α xyzt | (αx)+ (αy)+ (αz) + (αt)

что равносильно

4 4 4 4 xyzt | x +y + z + t

таким образом набор ${ai}1i0=01 α$ так же удовлетворяет условию. Тем самым, мы показали, что достаточно найти лишь те наборы, НОД всех элементов которого равен $1.$

Пусть $НОД{ai}100= 1 i=1$ и нашлись два не взаимно простых элемента набора $x$ и $y,$ пусть $s$ — некоторый общий простой делитель. Пусть $p,q,r$ — некоторые элементы набора. Тогда

4 4 4 4 s | x + y + p +q

s | x4+ r4+ p4 +q4

вычитая, получим, что $s | r.$ В силу произвольности выбора $r,$ мы можем показать, что каждый элемент набора кратен $p,$ что влечет противоречие, таким образом, все элементы набора попарно взаимно просты.

Пусть в наборе присутствует число $x,$ в разложении которого присутствует простой делитель $p⁄= 3.$ Тогда для любых элементов $a,b,u,v,l$ набора верно, что

4 4 4 4 p | x + a + b +u

4 4 4 4 p | x +a + b +v

p | x4+a4+ b4+l4

следовательно, $u4 ≡ v4 ≡ l4(modp),$ кроме этого

p |x4 +u4+ v4+ l4

следовательно,

p | x4 +3u4

в силу $p⁄= 3,$ получили противоречие.

Таким образом, единственным простым делителем элементов множества может является $3,$ несложно показать, что степень вхождения $3$ в элемент набора, отличный от $1,$ равна $1.$ Прямой проверкой убедимся, что множества ${1}10i=01,{3,{1}99i=1}$ являются подходящими.

Ответ:

${α}100 i=1$ или ${3α,{α}99 } i=1$ для любого натурального $α$

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

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

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

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

На доску выписаны $1985$ различных натуральных чисел, никакое из которых не имеет простых делителей, больших $26.$ Докажите, что среди выписанных чисел можно выбрать четыре числа, произведение которых является точной четвертой степенью.

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

Каждому элементу $x= 2e13e219e823e9,$ из множества $M$ поставим в соответствие набор ${e mod 2,...,e mod 2}. 1 9$ Всего существует $9 2 = 512$ возможных наборов, следовательно, по принципу Дирихле, найдутся два, наборы которых совпадают, а значит произведение этих чисел есть точный квадрат.

Удалим данные числа из исходного множества и добавим их произведение в множество $N.$ Такую операцию возможно делать до тех пор, пока мощность $M$ не станет меньше или равно $512,$ следовательно, мы можем добавить еще $1985−512 [ 2 ]= 734$ произведений в множество $N.$

Рассмотрим множество $N,$ каждый его элемент является квадратом и имеет в своем разложении множители, не превосходящие $23.$ Вычислим квадратный корень каждого из этих чисел. Снова поставим каждому из полученных чисел $e e e e x= 2 132198239$ в соответствие набор ${e1 mod 2,...,e9 mod 2}.$ Поскольку $734 >512$ мы снова сможем выбрать два элемента, произведение которых есть точный квадрат, а значит произведение двух пар чисел, корнями из произведений которых, являются данные, есть точная четвертая степень числа.