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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Все натуральные делители составного натурального числа $n$ выписаны по возрастанию $1 =d < d < ...< d = n. 1 2 k$ Оказалось, что

(d2− d1):(d3− d2):...:(dk− dk−1)= 1:2:...:(k− 1).

Найдите все такие $n.$

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

Подсказка 1.

Обозначим за a разность первых двух делителей. Тогда разность второго и третьего по условию 2a, третьего и четвёртого 3a и так далее.

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

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

a= d2− d1 =d2− 1

Тогда

d − d = 2a, d − d = 3a 3 2 4 3

и так далее. Таким образом, каждый делитель числа $n$ можно выразить через $a,$ как

dk =1 + ak(k−-1) 2

Обозначим через $m$ количество делителей числа $n.$ Заметим, что число $n$ является произведением своих наименьшего и наибольшего собственных делителей, то есть мы можем написать уравнение

a(m-+1)m- (am-(m-−-1)) 2 = n= (a+1)⋅ 2

Сократив левую и правую часть на $am 2-,$ получаем

m-+-1= (a+1)⋅ (m-− 1) 2 2

Получается, что умножение на $a +1$ увеличивает некоторое число на 1. Такое может быть только при условии, что $m = 2,$ $a= 1.$ То есть у числа $n$ есть ровно два делителя, а его наименьший простой делитель равен $a+ 1= 2.$ Отсюда $n =4.$

Ответ:

$n =4$

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

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

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

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

Пусть $1= d < d < ...< d = n 1 2 k$ — все натуральные делители натурального числа $n.$ Докажите, что если $d 3$ не делится на $d , 2$ то $dk−1+ dk−2$ делится на $d3+ d2.$

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

Пусть $n =pα1pα2...pαk 1 2 k$ — разложение $n$ на простые множители, причём $p < 1$ $p < 2$ …< $p . k$ Ясно, что $d =p , 2 1$ а $d = min(p2,p). 2 1 2$ По условию $d3$ не делится на $d2,$ поэтому $d3 = p2.$ Вспомним, что делители $n$ разбиваются на пары $( n) d,d .$ Отсюда следует, что

n n n n n(p1+p2) n dk−1+ dk−2 = d1-+ d2 = p1 + p2 =-p1p2-= p1p2(d1+ d2).

Так как $p1p2 |n,$ то это выражение делится на $d1+ d2.$

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

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

Пусть $n ≥2$ — натуральное число, с делителями $1= d < d < ...< d = n. 1 2 k$ Могло ли оказаться, что для некоторого натурального $s$ оба числа $ds$ и $ds+1$ являются точными квадратами?

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

Предположим противное. Пусть $d = a2, s$ $d = b2, s+1$ причем $a <b.$ Рассмотрим число $ab.$ Заметим, что $a2 <ab< b2,$ то есть $ds < ab< ds+1.$ В частности, число $ab$ не может являться делителем $n.$ Зафиксируем произвольное простое число $p.$ Обозначим через $α$ степень вхождения $p$ в $a,$ через $β$ — степень вхождения $p$ в $b.$ Тогда степень вхождения $p$ в число $ab$ равна $α+ β,$ что точно не превосходит большего из чисел $2α$ и $2β.$ Значит, число $ab$ также является натуральным делителем $n$ — противоречие.

Ответ:

не могло

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

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

Алгоритм Евклида. Чтобы найти $НОД (a,b)$ , где $a$ и $b$ — два натуральных числа, мы можем заменять большее число на разность между двумя числами. Алгоритм останавливается, когда новые числа будут равны. Тогда НОД исходных чисел равен этим оставшимся числам.

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

Для начала докажем такой факт: $(a,b)= (a − b,b)$ для целых $a$ и $b.$ Пусть $(a,b)= d 1$ и $(a − b,b)= d . 2$ Тогда, поскольку $a$ и $b$ делятся на $d1,$ то и $a− b$ делится на $d1,$ то есть $d1 ≤ d2,$ поскольку является общим делителем $a − b$ и $b.$ Аналогично $d2 ≤ d1,$ то есть они равны.

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

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

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

Найдите

(a) $(99!+100!,101!);$

(b) $(11◟. ◝5.◜1.1◞,1◟1.◝8..◜11 ◞).$

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

(a) Заметим, что $101!= 101⋅100⋅99!,$ а $99!+100!=101⋅99!.$ Значит,

(99!+100!,101!)= 101⋅99!⋅(1,100)= 101 ⋅99!

(b) Через $En$ обозначим $11 ...1. ◟ ◝◜n-◞$ Для начала заметим, что $(En,10k)= 1,$ поскольку $10k$ имеет в качестве простых делителей только 2 и 5, $En$ ни того, ни другого. Теперь докажем, что при $n≥ k$

(En,Ek)= (En−k,Ek)

$k En− Ek = En−k⋅10$ и

(En,Ek)= (En−k ⋅10k,Ek)= (En−k,Ek)

Таким образом, можно применять алгоритм Евклида для числа единиц и $(En,Ek)=E (n,k).$ Тогда, поскольку $(51,81)= 3,$ ответом на задачу будет 111.

Ответ:

(a) $101⋅99!;$ (b) $111.$

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

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

Известно, что $(m,n)= 1.$ Каково наибольшее возможное значение

(m + 2017n,n +2017m)?

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

Пусть искомый НОД равен $d.$ Избавимся от $n$ в первой скобке:

2 (m +2017n,2017m + n)= ((1− 2017 )m,2017m +n)

Пусть $(m,d)= d′.$ Тогда $2017m + n$ также делится на $d′,$ тогда и $n$ делится на $d′,$ из взаимной простоты $m$ и $n$ получаем $d′ = 1.$ Тогда

2 2 2 ((1 − 2017)m,2017m + n)=(2017− 1,2017m +n)≤ 2017 − 1

Для получения равенства достаточно взять $m =2015$ и $n= 4033.$ Тогда $2017m + n= 20172− 1.$ Нетрудно видеть, что $(m,n)= (2015,2018)=1.$

Ответ:

$20172 − 1$

Курсы

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

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

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

Докажите, что для любых натуральных $m$ и $n$ верно $(2m − 1,2n− 1) =2(m,n)− 1.$

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

Обозначим за $E k$ число $2k − 1.$ Тогда нужно получить, что $(E ,E )= E . n k (n,k)$ Для этого докажем, что при $n≥ k$

(En,Ek)= (En−k,Ek)

$En− E = E ⋅2k k n−k$ и

k (En,Ek)= (En−k⋅2 ,Ek)= (En−k,Ek)

Значит, можно применить алгоритм Евклида для индексов и завершить доказательство.

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

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

Докажите, что

02 12 n2 n (C n)+ (Cn)+ ...+ (Cn) =C 2n

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

Подсказка 1

Решение будем строить комбинаторно, а, значит, пора определяться, для какого множества (из скольки элементов) и какие объекты будем считать.

Подсказка 2

Правая часть чётко говорит брать 2n элементов и считать число подмножеств из n элементов. Слева же в каждом слагаемом перемножают цешки из n. Что бы это могло значить?

Подсказка 3

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

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

Пусть имеется множество $N$ из $n$ элементов. Тогда справа $Cn 2n$ количество его подмножеств мощности $n.$

Посмотрим теперь, что будет слева. Разделим $N$ на два непересекающихся подмножества $A$ и $B$ по $n$ элементов в каждом. В силу $k n−k Cn = Cn$ верно $k2 k n−k (Cn) =(Cn)⋅(C n ).$ Тогда $k 2 (Cn)$ количество способов выбрать в $N$ подмножество мощности $n,$ что $k$ элементов лежат в $A,$ остальные $n − k$ в $B.$ Проходясь по всем $k$ получаем всевозможные подмножества $N$ мощности $n.$

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

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

Сумма всех натуральных делителей числа $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-$

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

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

Можно ли вычеркнуть из произведения $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!.$

Ответ:

Да, можно

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

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

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

Интенсивы

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

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

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

Найдите все такие составные числа $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$

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

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

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

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

Подсказка 1

Видим, что задача на остатки! Тогда сразу же нужно разложить число 24 на степени простых и понять, какие остатки имеет n при делении на эти числа.

Подсказка 2

Число n имеет остаток 2 при делении на 3 и остаток 7 при делении 8. Теперь наша задача — понять что-то про сумму всех делителей числа n. Поскольку мы ничего не знаем про эти делители в совокупности, можно попробовать разбить их на пары определённым образом. (Почему делителей у n чётное число?)

Подсказка 3

Наши пары делителей — d и n/d. Произведение каждой пары равно n и имеет соответствующие остатки при делении на 3 и 8. Осталось осуществить небольшой перебор и понять, какие пары остатков могут давать d и n/d при делении на 3 и 8!

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

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

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

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

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

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

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

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

Давайте докажем, что если числа $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$ , то есть в любом случае найдутся хотя бы два равных числа, противоречие, значит, равенства быть не могло. Таким образом, сумма всех НОДов меньше суммы всех чисел.

Ответ:

Нет

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

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

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

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

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

Найти сумму максимальных нечетных делителей каждого из целых чисел на отрезке $[61;120]$ .

Источники: Росатом - 2024, московский вариант, 11.3 (см. olymp.mephi.ru)

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

Подсказка 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

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

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

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

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

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

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

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

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

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

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

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

Заметим, что

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$ больше произведения НОДов.

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

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

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

5m2−-n n2+ 3m =1

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

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

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

Подсказка 1

Для начала просто решим уравнение 5m^2 - 3m = n^2 + n. У нас есть квадраты обеих переменных, а значит нужно попробовать выделить два полных квадрата.

Подсказка 2

Заменим один получившийся квадрат на х, а другой на y. Должно получиться уравнение x^2 - 5y^2 = 4. Нам нужно доказать, что у уравнения бесконечное число решений. В таком случае, решение уравнения может быть связано с каким-либо бесконечным числовым рядом. Какую известную последовательность чисел вы знаете?

Подсказка 3

Числа Фибоначчи! Подумайте, как через них можно выразить решения этого уравнения. Это можно сделать, например, поподставляя последовательные числа Фибоначчи и их комбинации в уравнение.

Подсказка 4

В конце не забудьте проверить, что m и n получаются целые. Для этого можно заметить, что последовательность остатков чисел Фибоначчи по модулю 10 периодична. Так же нужно понять, зануляется ли в этих случаях знаменатель.

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

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

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)$ нам подходят.

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

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

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

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

Источники: Межвед - 2024, 11.1 (см. v-olymp.ru)

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

Подсказка 1

Давайте сначала попробуем найти верхнюю границу (число больше которого искомое точно быть не может)
Перемножим минимальные натуральные числа получаем 1 * 2 * 3 * 4 * 5 * 6 = 6! = 720

Подсказка 2

Теперь осталось доказать что (n + 1)(n + 2)...(n + 6) делится на 720 для любого натурального n. Давайте вспомним сочетания из комбинаторики

Подсказка 3

Действительно,
(n + 1)(n + 2)...(n + 6) / 720 равно количеству сочетаний из n + 6 по 6

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

Поскольку произведение первых 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

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