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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для каждого натурального $n$ докажите равенство

02 12 22 n 2 n−1 0⋅(Cn) + 1⋅(C n)+ 2⋅(Cn)+ ...+ n⋅(Cn) = n⋅C2n− 1

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

Для удобства перепишем каждое слагаемое левой части в виде $(Ci)2 = Ci ⋅Cn− i. n n n$ Рассмотрим задачу: выбрать из двух групп суммарно $n$ человек, и затем из выбранных людей первой группы назначить одного капитаном. Тогда каждое слагаемое левой части во вновь представленном виде

0 n 1 n−1 n 0 0 ⋅C nCn + 1⋅Cn⋅Cn + ...+ nCn ⋅C n

соответствует решению нашей задачи, когда в первой группе выбирается $i$ человек, а во второй $n − i,$ а сумма в точности соответствует решению задачи. Теперь посчитаем это по-другому: сначала из первой группы выбираем $1$ человека — это можно сделать $n$ способами, после чего из двух групп ( $2n− 1$ человек) выберем еще $n − 1$ человека. Тогда общий ответ $n−1 nC2n−1.$ Таким образом, тождество доказано.

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

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

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

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

Для каждого натурального $n$ докажите равенство

2 0 2 1 2 2 2 n n−2 0 ⋅Cn+ 1 ⋅Cn+ 2 ⋅Cn+ ...+ n ⋅Cn = n(n+ 1)⋅2

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

Рассмотрим следующую задачу: найти количество способов выбрать нескольких среди $n$ человек, и затем отдать каким-то двум из них по шарику (возможно, два шарика одному человеку). Слева в точности написан ответ на эту задачу: сначала выбирается $k$ человек, а затем для каждого из двух шариков есть $k$ возможностей. С другой стороны, можно сначала отдать два шарика, а потом в группу к этим людям добавить некоторое количество людей. Если оба шарика отданы одному человеку, то выбирается человек и еще $n − 1$ человек, количество таких объектов равно $n−1 n2 .$ Если же оба шарика отданы разным людям, то всего есть способов отдать два шарика $n(n− 1)$ (шарики отличаются). После этого нужно выбрать подмножество из $n− 2$ людей. Число таких объектов равно $n−2 n(n− 1)⋅2 .$

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

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

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

Дано простое число $p.$ Пусть $n$ — наименьшее натуральное число, большее 1, такое, что $n6− 1$ делится на $p.$ Докажите, что тогда одно из чисел $6 (n+ 1) − 1$ или $6 (n +2) − 1$ также делится на $p.$

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

Подсказка 1

Известно, что n — наименьшее натуральное, большее 1... Может ли оно быть большим? Есть ли какой-то очевидный "подозреваемый" среди чисел меньше p, который точно удовлетворяет сравнению n⁶ − 1 ≡ 0 (mod p)?

Подсказка 2

n⁶ − 1, это же не монолит! Можно же разломать на более мелкие кусочки, на несколько множителей.

Подсказка 3

n⁶ − 1 = (n + 1)(n − 1)(n² + n + 1)(n² − n + 1). Значит, p делит один из данных множителей.

Подсказка 4

Многочлены x² + x + 1, x² − x + 1 очень похожи. Можно ли простым преобразованием переменной один превратить в другой?

Подсказка 5

x² + x + 1 = (x + 1)² − (x + 1) + 1. Что можно сказать о (n − 1)⁶ − 1, (n + 1)⁶ − 1, в случае когда p делит (n² + n + 1)(n² − n + 1)?

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

Для $p= 2$ утверждение задачи очевидно, ведь числа $(n+ 1)6− 1,(n+ 2)6− 1$ — разной четности. Далее считаем $p> 2.$

Сразу заметим, что

6 6 (p− 1)− 1≡ (−1)− 1≡ 0 (mod p),

при этом $p− 1>1,$ то есть $p− 1$ подходит на роль $n,$ значит, $n≤ p− 1.$

Заметим, что

6 2 2 n − 1= (n − 1)(n +n +1)(n +1)(n − n+ 1).

Значит, $p$ делит один из множителей. Если $n − 1$ делится на $p,$ то $n ≥p +1$ — противоречие. Если $n+ 1$ делится на $p,$ то $n +2≡ 1 (mod p),$ откуда $(n+ 2)6− 1≡ 0 (mod p).$ Если

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

делится на $p,$ то $(n− 1)6− 1$ также делится на $p,$ что противоречит минимальности $n.$ Наконец, если

n2+ n+ 1= (n+ 1)2− (n+ 1)+1

делится на $p,$ то $(n+ 1)6− 1$ делится на $p.$

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

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

Найдите все тройки (не обязательно различных) натуральных чисел $a,b,c$ такие, что каждое из чисел $a+ bc,$ $b+ ca,$ $c+ab$ является простым делителем числа $2 2 2 (a +1)(b + 1)(c +1).$

Источники: ВСОШ, РЭ, 2024, 10.9 (см. olympiads.mccme.ru)

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

Подсказка 1:

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

Подсказка 2:

Нет, ведь произведение любых двух чисел больше любой скобки. Докажите это. Значит, каждая скобка делится на какое-то из этих чисел. Давайте заметим, что условие задачи инвариантно относительно перестановки переменных. Поэтому давайте их упорядочим и рассмотрим наименьшую скобку. В каких случаях наименьшая скобка может делиться на какое-то из чисел?

Подсказка 3:

Пусть теперь какие-то из чисел совпали. В каком случае это возможно и как будет выглядеть условие?

Подсказка 4:

Итак, вы пришли к тому, что среди a, b, c точно есть единица. Пусть это c. Тогда 2(a² + 1)(b² + 1) должно делиться на простое число a + b. Обратите внимание на НОД скобочек.

Подсказка 5:

Итак, вы пришли к тому, что хотя бы два числа из a, b, c должны быть 1. Пусть это b и c. Тогда 4(a² + 1) должно делиться на a + 1. Посмотрите на НОД a² + 1 и a + 1.

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

Видим, что

a= b= c=1

удовлетворяет условию. Далее будет доказано, что других ответов нет.

1) Предположим, что

s= (a2+ 1)(b2+1)(c2+ 1)

делится на $pqr,$ где

p= a+ bc,q = b+ ca,r= c+ab

это следует из условия, если дополнительно предполагать, что $p,q,r$ различны.

Заметим, что один из трех сомножителей $a2+ 1,$ $b2+ 1,$ $c2 +1$ не может делиться на произведение двух из чисел $p,q,r,$ так как он меньше этого произведения. Действительно, рассмотрим, например, $pq.$ Из раскрытия скобок видим, что

pq > c2(ab)+ab≥ c2 +1, pq > b2c+ ab≥ b2+ 1

и аналогично

pq > a2+ 1.

Следовательно, каждый из сомножителей $a2+ 1,$ $b2+ 1,$ $c2+1$ должен делиться ровно на одно из чисел $p,q,r.$ Пусть, для определенности, $a$ — наименьшее из чисел $a,b,c.$ Тогда $a2 ≤ bc$ и $1≤ a,$ поэтому $a2 +1$ может делиться на $p= bc +a$ только в случае $a2 = bc$ и $a = 1,$ т.е в случае

a = b=c =1.

Далее, $2 a ≤ ac$ и $1≤ b,$ поэтому $2 a +1$ может делиться на $q = ac+ b$ только в случае $2 a = ac$ и $b= 1,$ т.е в случае

a = b=c =1.

Аналогично, $a2+ 1$ может делиться на $r= ab+c$ только при

a = b=c =1.

2) Пусть какие-то два из трех чисел $p,q,r$ совпадают, скажем, $p =q.$ Тогда

0= q− p= b+ca− a− bc= (a− b)(c− 1).

Значит, либо $a= b,$ либо $c= 1.$ Первый случай возможен лишь при $a= b=1,$ иначе

p= a+bc= a+ ac= a(a+ c)

— составное число, что дает противоречие. Значит, в любом случае среди $a,b,c$ присутствует единица, скажем, $c= 1.$

Тогда наши данные простые числа — это $p= a+ b,$ $q = a+ b$ и $r= ab+ 1,$ и они должны быть делителями

s= 2(a2+ 1)(b2+1).

Если хотя бы одно из чисел $a,b$ больше 1, то $p> 2$ и на $p= a+b$ обязан делиться хотя бы один из сомножителей $a2+1$ и $b2+ 1.$ А поскольку разность

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

делится на $p= a+ b,$ получаем, что оба числа $a2+1,$ $b2+ 1$ делятся на $p.$ Тогда если $r$ отлично от $p= q,$ то $s$ делится на $pqr,$ что разобрано в случае $1.$

Остается вариант

p= q = r.

Рассуждаем как в предыдущем случае и получаем, что хотя бы два из трех чисел $a,b,c$ обязаны равняться $1.$ Пусть, например,

a =b =1,p= q = r= c+1,s= 4(c2+ 1).

Случай $c=1$ уже был ранее. Если $c> 1,$ то $c+ 1$ — нечетное простое, значит $c2+1$ должно делиться на $c+ 1.$ Отсюда

(c2+ 1)− (c+1)= c(c− 1)

должно делиться на $c+ 1.$ Но это невозможно, так как

0< c− 1< c<c +1

и $c+ 1$ — простое.

Ответ:

$(1,1,1)$

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

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

У натурального числа ровно 50 делителей. Может ли оказаться, что никакая разность двух различных его делителей не делится на 100?

Источники: ВСОШ, ЗЭ, 2024, 9.2 (см. olympiads.mccme.ru)

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

Подсказка 1:

Ясно, что нужно смотреть на последние две цифры всех чисел. Если у каких-то двух они совпадают, то их разность будет делиться на 100.

Подсказка 2:

Давайте назовём последние две цифры числа "хвостом". Заметим, что хвост числа n даёт такие же остатки при делении на некоторые числа, что и само n.

Подсказка 3:

Если число делится на 5, может ли оно обладать таким свойством? Сколько у него будет делителей, кратных 5? А сколько всего существует "хвостов", кратных 5?

Подсказка 4:

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

Подсказка 5:

Итак, кажется, вы пришли к тому, что такое число не делится на 5 и делится на 2 хотя бы во второй степени. Попробуйте обозначить через r степень вхождения 2 в n и поработать с ней.

Подсказка 6:

Докажите, что количество делителей кратно r + 1. Для этого достаточно разбить делители некоторым образом на цепочки по r + 1 делителю в каждой.

Подсказка 7:

Используя всю информацию, попробуйте оценить количество нечётных делителей, делителей, кратных 2, но не 4, и кратных 4.

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

Предположим, что такое число $n$ существует. Условие равносильно тому, что все числа, образованные последними двумя цифрами делителей, различны (мы считаем, что к однозначным числам спереди приписаны нули). Назовём такую пару последних цифр хвостом числа. Заметим, что хвост числа имеет те же остатки от деления на $4$ и на $5,$ что и исходное число.

Предположим, что $n$ делится на 5. Тогда для любого его делителя $d,$ не кратного $5,$ существует и делитель $5d,$ кратный $5.$ При этом для разных делителей $d$ мы получаем разные делители $5d;$ поэтому количество кратных $5$ делителей не меньше половины, то есть не меньше $25.$ Но такие делители имеют хвосты, оканчивающиеся либо на $0,$ либо на $5.$ Таких возможных хвостов не больше $20,$ поэтому два из них совпадают. Это противоречие показывает, что $n$ не делится на $5,$ и хвосты его делителей не могут оканчиваться на $0$ или $5.$

Если число $n$ нечётно, то все его делители также нечётны. Однако существует всего $50$ возможных нечётных хвостов, и $10$ из них оканчиваются на $5,$ то есть не могут появиться. Поэтому и в этом случае найдутся два одинаковых хвоста.

Если число $n$ делится на $2,$ но не на $4,$ то все его делители разбиваются на пары $(d,2d),$ где $d$ — нечётный делитель $n.$ При этом все числа вида $2d$ имеют хвосты, не делящиеся на $4,$ а таких хвостов (при этом не делящихся на $5$ ) всего $20.$ Значит, два из этих хвостов одинаковы.

Наконец, пусть наибольшая степень двойки, на которую делится $n,$ равна $2r,$ где $r≥ 2.$ Тогда, если $d$ — нечётный делитель $n,$ то числа $d,$ $2d,$ $22d,$ …, $2rd$ также будут делителями $n,$ и этим исчерпываются все делители $n.$ Поэтому общее число делителей $n$ будет кратно $r+1.$ Таким образом, $50$ делится на $r+ 1$ и, значит, $r ≥4.$

Тогда $n$ имеет

-50-≤ 10 r+ 1

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

Ответ:

нет

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

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

Дано число $22024⋅32023⋅52022.$ Можно ли расставить все его делители, кроме единицы, по кругу так, чтобы любые два соседних числа не были взаимно просты?

Источники: Курчатов - 2024, 10.1 (см. olimpiadakurchatov.ru)

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

Подсказка 1

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

Подсказка 2

Хочется расставить несколько чисел по кругу, а для остальных сразу станет понятно, где они должны находится.

Подсказка 3

Давайте расставим по кругу попарные произведения простых чисел (2⋅3, 2⋅5, 3⋅5). Как теперь можно расставить остальные числа?

Подсказка 4

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

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

Поставим сначала числа $d = 2⋅3, 1$ $d =3 ⋅5 2$ и $d = 5⋅2, 3$ а затем будем расставлять оставшиеся делители между ними. Между числами $d1$ и $d2$ в произвольном порядке поставим все делители, кратные $3.$ Ясно, что все такие делители не взаимно просты друг с другом, а также с делителями $d1$ и $d2,$ поскольку все они делятся на $3.$

Далее, между числами $d2$ и $d3$ поставим все оставшиеся делители, кратные $5.$ Все эти делители вместе с числами $d2$ и $d3$ не взаимно просты, так как кратны $5.$ Наконец, поставим между $d3$ и $d1$ все оставшиеся делители. Поскольку все делители, кратные $3$ или $5,$ уже расставлены, то эти оставшиеся делителя на самом деле в точности степени двойки. Поэтому они и делители $d1$ и $d3$ все делятся на $2$ и также не взаимно просты. Значит, полученная нами расстановка удовлетворяет условию.

Ответ: Да, можно

Курсы

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

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

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

12 человек пришли на представление в шляпах. Фокусник поменял местами их шляпы. Затем он велел каждому из присутствующих найти свою шляпу и запомнить того, у кого она оказалась. Каждую минуту каждый участник должен был передавать находящуюся у него шляпу человеку, которого он запомнил (все время одному и тому же). В какой-то момент все шляпы вернулись к своим исходным владельцам. Через какое наибольшее число минут это могло произойти в первый раз?

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

Источники: ИТМО - 2024, 10.8 (см. olymp.itmo.ru)

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Нет, не обязательно. Можно подобрать примеры с разными циклами обращения шляп. Осталось подумать, при каких циклах нам придётся дольше всего ждать восстановления порядка.

Подсказка 4

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

Подсказка 5

Конечно же, это НОК маленьких циклов. При этом суммарное количество людей во всех циклах равно 12. Какая теперь перед нами стоит задача?

Подсказка 6

А задача такая: у нас 12 человек, значит, суммарная величина всех циклов —12. Каких циклов и сколько должно быть, чтобы НОК этих циклов был максимален?

Подсказка 7

Попробуем пораскладывать 12 на слагаемые и посчитать их НОК. Заметим, что если каждое слагаемое — это делитель 24, то НОК не больше 24. А если есть слагаемое, не являющееся делителем 24, то вариантов не так много при условии, что сумма всех слагаемых равна 12. Аккуратно переберём все возможные варианты.

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

Рассмотрим некоторого человека, назовем его $A . 0$ Пусть его шляпа изначально оказалась у какого-то $A , 1$ шляпа $A 1$ оказалась у $A 2$ и т.д.. Рассмотренный нами процесс нумерации рано или поздно закончится тем, что для какого-то $An−1$ его шляпа окажется у какого-то $Ak,$ который был уже нами пронумерован ранее. Заметим, что это $A0,$ так как про всех остальных мы уже знаем, откуда взялись находящиеся у них шляпы. Значит, шляпа $An−1$ в начале представления оказалась у $A0$ и мы получим цикл из $n$ человек. Каждый раз каждый из участников передает свою шляпу следующему по циклу. Таким образом, шляпы в этом цикле вернутся к своим хозяевам через $n − 1$ минуту, затем через каждые следующие следующие $n$ минут.

Таких циклов может быть несколько. Тогда если все шляпы вернутся к своим хозяевам через $t$ минут, число $t+1$ должно делиться на длины всех этих циклов. Таким образом, нам нужно разложить число 12 в сумму нескольких слагаемых так, чтобы их наименьшее общее кратное было максимальным. Возьмем следующее разложение:

12= 5+ 4+ 3

НОК этих чисел — 60, значит, шляпы вернутся к своим хозяевам через 59 минут. Если все слагаемые являются делателями числа 24, то их НОК не больше 24. Значит, для большего НОК нужно хотя бы одно число, не являющееся делителем 24, например, 5, 7, 9, 10 или 11. Варианты, в которых все слагаемые, кроме одного, равны единице, нам не нужны. Переберем оставшиеся варианты для слагаемых, больших 5:

$10+ 2,$ НОК $=10.$
$9+ 3,$ НОК $=9.$
$9+ 2+ 1,$ НОК $=18.$
$7+ 5,$ НОК $=35.$ Для вариантов $7+ 4+1$ и $7+ 3+ 1+ 1$ НОК, очевидно, еще меньше.
$7+ 3+ 2,$ НОК $=42.$

Осталось рассмотреть варианты с 5. Если все остальные делители не больше 6, НОК не больше, чем 60, а вариант с 7 мы уже разобрали. Значит, ответ — 59.

Ответ: 59

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

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

В произведении $1 ⋅2 ⋅...⋅n (n≥ 2)$ разрешается приписать некоторым сомножителям восклицательный знак (при этом сомножитель $k$ заменяется на $k!$ ). При каких $n$ в результате можно получить точный квадрат?

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

Подсказка 1

Давайте прикинем, какие вообще числа подойдут. Перебираем ручками и понимаем, что простые числа вроде 2,3,5 не подходят в качестве n. А, например, сами квадраты вроде 4 или 9 подойдут, ведь можно поставить после числа !, то есть получить 1 * 2 * 3 * ... * 7 * 8 * 9! два раза произведение чисел от 1 до 8 и саму девятку, а в итоге (8!)² * 9 = (3 * 8!)²

Подсказка 2

Надо подумать в терминах множителей, что вообще добавляет в произведение эта операция постановки восклицательного знака после множителя k.

Подсказка 3

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

Подсказка 4

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

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

Первое решение.

Операция постановки восклицательного знака, применённая к числу $k ≥2,$ даёт возможность добавить в произведение множители от $1$ до $k − 1$ включительно.

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

При составном $n$ будем действовать следующим образом. Разложим произведение $1⋅2⋅...⋅n$ в виде произведения степеней простых и посмотрим, какие простые числа входят в нечётных степенях. Если таких чисел нет, то перед нами уже квадрат. Иначе обозначим наибольшее из этих простых за $p1.$ Поставим восклицательный знак после числа $p1+1.$ Так мы добавили в произведение все числа от $1$ до $p1,$ так что степень простого числа $p1$ увеличилась на $1$ и стала чётной. Кроме того, степени вхождения простых чисел, больших $p1,$ не изменились. Для нового произведения сделаем ту же операцию, то есть пересчитаем степени вхождения простых чисел и упорядочим те простые, что входят в нечётных степенях, в порядке убывания, и снова “исправим” наибольшее. Такими операциями мы в итоге придём к числу, являющимся точным квадратом.

Второе решение.

Предположим, что $n$ простое. Тогда степень вхождения $n$ в произведение будет равна $1$ (как бы мы ни приписывали восклицательные знаки). Тогда число не является точным квадратом. Предположим, что $n= k2.$ Тогда можно приписать факториал после $n.$ В итоге останется $((n − 1)!)2⋅n$ — точный квадрат.

Теперь предположим, что $n = ab,$ где $a⁄= b$ и $a,b <n.$ Не нарушая общности, $a> b.$ Рассмотрим два случая.

Если $a= b+1,$ то припишем факториал к $a+1,n$ и $b$ (эти три числа различны). Останется

((b− 1)!)2⋅b⋅a⋅((n− 1)!)2⋅n= n2⋅((b− 1)!(n− 1)!)2

Если же $a >b+ 1,$ то припишем факториал к $b,b+1,a,a +1,n$ (все эти числа различны). Получится

((b− 1)!)2⋅b⋅((a− 1)!)2 ⋅a ⋅((n− 1)!)2⋅n =n2⋅((b− 1)!(a− 1)!(n− 1)!)2

что также является точным квадратом.

Ответ:

при составных

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

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

Через терминал оплаты на мобильный телефон можно перевести деньги, при этом взимается комиссия — натуральное число процентов. Федя положил целое количество рублей на мобильный телефон, и его счёт пополнился на $847$ рублей. Сколько денег положил на счёт Федя, если известно, что комиссия менее $30%$ ?

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

Пусть Федя положил $N$ рублей на свой телефон и комиссия составила натуральное число $p <30$ процентов. Тогда от его суммы вычитается $p-- 100$ рублей. Получается $Nx- 100$ рублей, где $100 >x = 100− p> 70.$

Итак,

Nx 7⋅10 ⋅10⋅11⋅11 100 =847 =⇒ x = -----N------∈ ℕ∩ (70;100)

По основной теореме арифметике из сократимости дроби следует, что $x$ это произведение каких-то множителей из числителя. Простым перебором можно убедиться, что в заданный интервал $(70;100)$ попадает только произведение $7⋅11.$ Так что $N = 7⋅107⋅0⋅11211 =100⋅11= 1100.$

Ответ:

$1100$

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

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

Известно, что делители всякого “неквадратного” (не является точным квадратом) числа можно разбить на пары (у “квадратного” числа нечётное количество делителей, в связи с чем разбить на пары невозможно) так, чтобы произведения делителей в каждой паре были равными. Например, $18= 1⋅18= 2⋅9= 3⋅6.$ А существуют ли “неквадратные” числа, все делители которых можно разбить на тройки так, чтобы произведения делителей в каждой тройке были равными?

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

Подсказка 1

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

Подсказка 2

Перемножаем все эти k троек делителей и получаем x в степени k. А теперь воспользуемся утверждением из условия о том, что любое "неквадратное" можно разбить на пары делителей с равными произведениями! Давайте посчитаем аналогично: чему равно произведение тех же самых всех 3k делителей, если в каждой паре произведение n?

Подсказка 3

Перемножаем и получаем n в степени 3k/2 (пополам 3k делителей разбиваются на пары). Осталось найти какое-то противоречие, что произведение всех делителей равно x^k и одновременно n^(3k/2). Попробуйте свести это к тому, что квадрат равен кубу "неквадратного" числа, и порассуждать в терминах разложения на простые множители :)

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

Предположим, что существует такое не являющееся точным квадратом натуральное число $n> 1,$ у которого $k$ делителей бьются на тройки с произведением $t$ в каждой тройке. Тогда произведение $P$ всех делителей равно $k∕3 t .$

С другой стороны, если число $n$ не является точным квадратом, то его делители можно разбить на пары с произведением $n$ (если число $n$ делится нацело на $√ - m < n,$ то оно делится нацело и на $n- -n- √- m > √ n = n$ ). Так что делители бьются на пары с произведением $n$ в каждой, откуда $k∕2 P = n .$

В итоге

P = tk∕3 = nk∕2 =⇒ t2 = n3

Так как число $n$ не является точным квадратом, то в его разложении на простые множители найдётся какой-то простой делитель в нечётной степени. При возведении в куб степень этого простого делителя останется нечётной. Получаем противоречие с равенством $t2 = n3$ (в левой части равенства все простые делители должны быть в чётной степени, а справа есть делитель в нечётной степени).

Ответ:

нет

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

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

Натуральные числа $a,b,c$ таковы, что $1≤ a< b< c≤ 3000.$ Найдите наибольшее возможное значение величины

НОД(a,b)+ НОД (b,c)+ НОД (c,a)

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

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

Подсказка 1

Хочется получить какую-то оценку на эти НОДы. Понятно, что НОД(а,b) не больше чем a. Может попробовать что-то поделать с такой оценкой?

Подсказка 2

Если оценить так каждый НОД, получается как-то слишком грубо. Какой алгоритм приходит в голову, когда речь идёт о НОДах? Конечно же, алгоритм Евклида! Может, как-то улучшить оценку для НОД(a,b) с помощью него?

Подсказка 3

Если воспользоваться алгоритмом Евклида получиться, что: НОД(a,b)=НОД(a,b-a). Тогда т.к. НОД(a,b-a) не больше чем b-a, то и НОД(a,b) будет не больше чем b-a. если сделать тоже самое с НОД(b,c), что получится?

Подсказка 4

Итак, мы имеем что НОД(a,b) не больше b-a, а НОД(b,c) не больше c-b. Если их сложить, получится, что их сумма не больше чем (b-a)+(c-b)=с-а. Если оценить, что НОД(а,с) не больше чем a, то окончательно сумма всех НОДов будет не больше с, которое не больше 3000. Осталось только придумать пример...

Подсказка 5

Понятно, что с=3000. Чтобы достигалась оценка, необходимо, чтобы НОД(a,c)=a. Тогда с делится на a. Если мы сделаем так, что b тоже поделится на a, то, возможно, придумаем пример

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

Воспользуемся алгоритмом Евклида для $Н ОД(a,b),$ получим

НОД(a,b)= НО Д(a,b− a)

Заметим, что, так как НОД двух натуральных чисел не превосходит каждое из них,

НОД (a,b− a)≤ b− a⇒ НО Д(a,b)≤b − a

Аналогично получаем, что

НО Д(b,c)≤c− b

А также

Н ОД(c,a)≤ a

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

Н ОД(a,b)+ НОД(b,c)+ НОД(c,a)≤ (b− a)+ (c− b)+a = c≤3000

В качестве примера на $3000$ можно предъявить, например, $a= 1000,b= 2000,c= 3000.$ В этом случае

НО Д(a,b)+Н ОД(b,c)+Н ОД(c,a)= 1000+ 1000 +1000= 3000

Ответ: 3000

Интенсивы

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

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

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

Для натурального числа $N$ выписаны все его натуральные делители $p i$ в порядке возрастания $1< p <p ...<p = N. 1 2 k$

Обозначим количество натуральных делителей числа $N$ через $σ(N ).$

Найдите все возможные значения $3 σ(N ),$ если известно, что

2 p3⋅p4⋅p1696⋅p1697 ≥N

Источники: ПВГ-2023, 10.5 (см. pvg.mk.ru)

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

Подсказка 1

Давайте подумаем, что можно сделать с большими по номеру делителями. Например мы знаем, что если p - наибольший делитель, а q - наименьший, то p = N/q. Как развить эту идею?

Подсказка 2

Вот пусть у N ровно n ≥ 1697 делителей. Тогда p₁₆₉₇ = N/pₙ₋₁₆₉₇₊₁, p₁₆₉₆ = N/pₙ₋₁₆₉₆₊₁. Тут уже при перемножении мы получаем N² и это хорошо. Но еще получаем в знаменателе два подряд идущих делителя. При каких n это все еще будет выполняться условие?

Подсказка 3

Если n уже ≥ 1700, то внизу будет стоять ≥ p₄⋅p₅, что больше чем p₃⋅p₄, то есть наше выражение будет уже < N². Остается n < 1700, и несложным перебором можно найти примеры на эти n и найти число делителей у N³)

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

По основной теореме арифметики $N$ представляется единственным образом в виде:

α1 α2 αn N = q1 ⋅q2 ⋅⋅⋅qn ,где qi− простое число

Тогда из правила произведения, поскольку мы каждую степень простого числа $q i$ выбираем $α +1 i$ способами, то $σ(N)= (α + 1)⋅(α + 1)⋅⋅⋅(α + 1). 1 1 n$ Из условия следует, что $σ(N)≥ 1697.$ Разберем несколько случаев:

1.

Пусть $σ(N)= 1697.$ Тогда:

N 1 =p1 < p2 < ⋅⋅⋅< p1696 = p2 < p1697 = N.

Значит, $p3⋅p4⋅p1696⋅p1697 = p3⋅p4N2 ≥ N2. p2$ То есть условие выполняется.
Так как $1697−$ простое число, то из формулы для $σ(N )$ следует, что $N = q1696$ (в противном случае 1697 было бы составным).Таким образом,

σ(N3) =(3⋅1696+ 1)= 5089.

2.

Пусть $σ(N)= 1698.$ Тогда:

N- N- 1 =p1 < p2 < ⋅⋅⋅< p1696 = p3 < p1697 = p2 < p1698 = N.

Значит, $p3⋅p4⋅p1696⋅p1697 = pp42N2 ≥ N2.$ То есть условие выполняется.
Так как $1698 =(1697+ 1)= (1 +1)(848+ 1)= (2+ 1)(565+ 1)$ и
$1698= (5+ 1)(282+ 1)= (1+ 1)(2+1)(282+ 1),$ то:

3 σ(N ) =(3⋅1697+ 1)= 5092;

σ(N3)= (3 ⋅1 +1)(3⋅848+ 1) =10180;

3 σ(N )= (3 ⋅2 +1)(3⋅565+ 1) =11872;

3 σ(N )= (3 ⋅5 +1)(3⋅282+ 1) =13552;

σ(N3 )=(3⋅1+ 1)(3⋅2+ 1)(3⋅282+ 1)= 23716.

3.

Пусть $σ(N)= 1699.$ Тогда:

1 =p1 < p2 < ⋅⋅⋅< p1696 = N-< p1697 = N-< p1698 < p1699 = N. p4 p3

Значит, $p3⋅p4⋅p1696⋅p1697 = N2 ≥ N2.$ То есть условие выполняется.
Так как $1699−$ простое число, то из формулы для $σ(N )$ следует, что $N = q1698$ (в противном случае 1699 было бы составным).Таким образом,

σ(N3) =(3⋅1698+ 1)= 5095.

4.

Пусть $σ(N)≥ 1700.$ Тогда $p1696 < Np,p1697 < Np-. 3 2$ Следовательно, $p3⋅p4⋅p1696 ⋅p1697 <N2.$ Таким образом, этот случай невозможен.

Ответ:

$5089,5092,5095,10180,11872,13552,23716$

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

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

Найдите все простые $p,$ для которых числа $p+ 1$ и $p2+1$ являются удвоенными квадратами натуральных чисел.

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

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

Подсказка 1

Пусть p+1 = 2x², p²+1 = 2y². Вот давайте вычтем эти два выражения: будет p(p-1) = 2(y-x)(y+x). Про что можно тут подумать, раз слева стоит простой множитель?

Подсказка 2

Про делимости! У нас делится на p либо 2, либо y-x, либо y+x. Если проверить p = 2, то он не подойдет. А может ли y-x делится на p?

Подсказка 3

Можно заметить, что т.к. p+1 = 2x², то x<p, а также y<p и x<y. Тогда y-x тем более < p и он на него не делится. Остается, что y+x делится на p. Используя наши оценки на x и y, поймите, чему равно y+x и решите полученную системку!

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

Пусть

2 2 2 p+1 =2x и p +1 =2y ,

тогда

2 2 p(p− 1)= 2(y − x )= 2(y− x)(y+ x)

Поэтому одно из чисел 2, $y− x$ и $y+ x$ кратно $p.$ Если 2 кратно $p,$ то $p= 2,$ что невозможно, поскольку $p+1 =3$ не является удвоенным квадратом.

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

Из неравенства $x < y < p$ следует, что

x+ y = p

Таким образом, имеем систему из двух уравнений

( { x +y = p ( 2(y− x) =p− 1

Решаем её

( ( { x+ y = p { 2x +2y = 2p p+1- ( 2(y − x)= p− 1 ⇒ ( 2y − 2x= p− 1 ⇒ 4x =p+ 1⇒ x = 4

Значит,

( p+1-)2 p +1= 2 4

Следовательно, $p= 7.$

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

Если $y− x$ делится на $p,$ то

y +x >y− x≥ p⇒ 2(y− x)(y+ x)≥2p2 > p(p − 1)

Значит, это невозможно. Следовательно, $y+x$ делится на $p.$ Заметим, что

y2= p2+-1> p2−-1= p− 1 x2 p +1 p +1

Тогда если $p ≥11,$ то

y2 > 10x2 ⇒ y > 3x

Значит,

2(y− x)> y+ x≥ p

Стало быть,

2(y− x)(y+ x) >p2 > p(p +1)

Но этого не может быть. Таким образом, осталось рассмотреть случаи $p= 3,p =5$ и $p= 7.$ В первых двух из них $p+ 1$ не является удвоенным квадратом, а $p= 7$ подходит.

Ответ: 7

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

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

У Пети есть $n$ карточек с $n$ последовательными натуральными числами (на каждой карточке написано ровно одно число). Он выложил эти карточки в ряд в некотором порядке.

У каждых двух чисел на соседних карточках Петя нашёл наибольший общий делитель. При каком наибольшем $n$ все эти наибольшие общие делители могут оказаться различными числами?

Источники: Курчатов-2023, 11.5 (см. olimpiadakurchatov.ru)

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

Подсказка 1

НОД различных чисел обязательно не превосходит их разности, а в задаче даны n последовательных чисел и их НОДы различны. Что это означает?

Подсказка 2

НОДы принимают значения от 1 до n-1, а их как раз n-1 штука. Значит, все числа от 1 до n-1 встретятся в НОДах. Теперь рассмотрим чётные НОДы. Какое должно выполниться условие, чтобы их все получить?

Подсказка 3

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

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

Пример. Возьмём числа $12,13,14,15,16$ и расставим их в следующем порядке:

13,15,12,16,14

Тогда НОДы будут $1,3,4,2.$

Оценка. Здесь и далее $(a,b)$ — это НОД $(a,b).$ Прежде всего отметим, что:

(a,b)= (a− b,b)≤|a− b|

То есть НОД двух соседних чисел не превосходит модуля их разности. Но модуль разности любых двух из $n$ последовательных натуральных чисел принимает значения от $1$ до $n− 1.$ Всего Петя получит как раз $n− 1$ пару соседних чисел. Значит, в качестве НОДов должны встретиться все числа от $1$ до $n− 1$ по одному разу.

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

1.: Пусть $n$ четно: $n = 2k.$ Тогда произвольная пара чисел отличается на величину от $1$ до $2k− 1,$ то есть всего четных разностей $k− 1,$ а самих четных чисел — $k.$ Значит они должны стоять подряд.
2.: Пусть $n$ нечетно: $n = 2k +1.$ Тогда произвольная пара чисел отличается на величину от $1$ до $2k.$ всего четных разностей $k.$ Но заметим, что четных чисел на карточках может быть всего $k$ или $k +1.$ Если их $k,$ то мы получим максимум $k − 1$ четных разностей. Тогда их ровно $k+ 1$ и они должны стоят подряд.

Заметим, что НОД двух различных нечётных чисел не больше половины от их разности, поскольку разность чётная делит НОД, при этом сам НОД нечётный.

Теперь снова рассмотрим случаи в зависимости от чётности $n.$

1.: $n =2k+ 1.$ Тогда, как мы уже знаем, чётных чисел $k+1.$ Пусть они $x,x+ 2,...,x+ 2k.$ НОД $2k$ можно получить только поставив рядом $x$ и $x +2k.$ Получить НОД $2k− 1$ можно или парой $x,x+ 2k − 1$ или $x+ 1,x +2k,$ поскольку наибольшая нечётая разность как раз $2k− 1,$ а НОД не может быть больше разности. Будем считать, что выбрана первая пара. Покажем, что так можно сделать без ограничения общности. Заменим все числа на противоположные, а потом добавим $xn!$ . От этого НОДы соседних чисел не поменяются (поскольку мы добавили $n!$ несколько раз, что в любом случае делится на НОД (ведь он не более $n− 1).$ Числа всё ещё натуральные и последовательные ( $xn!− (x+ n− 1)> 0).$ При этом теперь наибольшее число перешло в наименьшее, то есть выбор пары тоже сменился. Тогда посмотрим, как идут в другую сторону чётные элементы. Для НОДа $2k − 2$ рядом с $x+ 2k$ обязательно стоит $x+ 2,$ поскольку наибольшая из доступных на текущий момент разностей как раз $2k− 2,$ а НОД не может быть больше разности. Для НОДа $2k − 4$ далее стоит $x+ 2k− 4.$ Далее мы снова будем чередовать самое маленькое из оставшихся чётных чисел и самое большое. В итоге, придём к $x+ k$ или к $x+ k+ 1$ (в зависимости от чётности $k).$ Попробуем получить НОД $2k− 3.$ НОД нечётных чисел не более $k− 1,$ поскольку их максимальная разность $2k− 2$ (наименьшее — $x+ 1,$ наибольшее — $x+ 2k − 1).$ С крайним чётным числом разность не более чем $k.$ Для $k≥ 4,2k − 3> k,$ поэтому такого НОД не получится. Противоречие. Для $k =3$ получаем последовательность $x +5,x,x +6,x+ 2,x +4,x+ 1.$ Но $(x+ 6,x)$ и $(x +4,x+ 1)$ не могут одновременно делится на $3.$ Противоречие.
2.: $n =2k.$ Без ограничения общности будем считать $x$ чётным. Рядом с $x$ должно стоять $x +2k− 1,$ чтобы получить НОД $2k− 1.$ Аналогично, другим крайним элементом последовательности чётных будет $x+k$ или $x+ k− 1$ в зависимости от чётности $k.$ Тогда снова попробуем получить НОД $2k− 3.$ Для двух нечётных он снова не более $k− 1.$ С крайним чётным числом разность не более $k − 1,$ ведь максимальное нечётное $x +2k− 1$ уже занято с другой стороны, а наименьшее нечётное $x +1.$ Для $k≥ 3,$ получаем $2k− 3> k− 1.$ противоречие.

Ответ:

$5$

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

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

Обозначим

a= 3481,b= 4120,N = 26069

Известно, что остаток от деления числа $b2$ на $N$ равен $a.$ Найдите разложение числа $N$ на простые множители.

Источники: Межвед-2023, 11.7 (см. www.academy.fsb.ru)

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

Подсказка 1

Каким-то образом у нас в условии есть утверждение про квадрат, а числа у нас какие-то странные…быть может, поискать какие-то свойства у них?

Подсказка 2

Число а - квадрат! Тогда мы можем записать условие на остаток от деления на N и выполнить некоторые преобразования, чтобы понять, какие числа имеют с N общие делители.

Подсказка 3

Оказывается, (b-59)(b+59) делится на N! Тогда хотя бы одна из этих скобок имеет с N общие множители, а, значит, мы можем найти их НОД с N) Как это сделать?

Подсказка 4

По алгоритму Евклида находим НОД((b-59), N), остаётся лишь понять, а на что ещё делится N?)

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

Первое решение.

Заметим, что $26069= 131⋅199.$ Далее проверкой до целой части от соответствующего арифметического корня проверяем оба множителя на простоту. Разложение получено.

Второе решение.

Заметим, что $2 a= 59.$ Тогда

b2 ≡N 592

(b− 59)(b+ 59)≡N 0.

Следовательно, пары чисел $(b− 59) и N$ или $(b+ 59) и N$ имеют общие делители, отличные от 1. Найдём наибольший общий делитель чисел $(b+59) и N$ по алгоритму Евклида:

26069= 6⋅4179+ 995

4179= 4⋅995 +199

995= 5⋅199

Следовательно, $НОД((b+59),N )=199$ — простое число. Остаётся разделить $N$ на $199.$

Ответ:

$131⋅199$

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

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

Натуральные числа вида $11 ...1 ◟ ◝◜n-◞$ (десятичная запись состоит из $n$ единиц) будем обозначать $R . n$ Докажите, что существует такое натуральное число $k,$ что $Rn$ делится на 41 тогда и только тогда, когда $n$ делится на $k.$

Источники: Иннополис-2023, 10-12 (см. dovuz.innopolis.university)

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

Подсказка 1

Сложно анализировать число только из единиц, т.к. сложно разобрать даже его делители...тогда было бы по хорошему его как-то преобразовать в более приятный вид. И подумаем над вопросом: "А откуда тут вообще 41? Почему не 42, например?"

Подсказка 2

Число, состоящее из единиц, можно записать как (10^n - 1)/9. А использовать 41 хочется только как простое число... Выходит, что (10^n - 1)/9 должно делиться на 41. Когда это возможно?

Подсказка 3

Когда 10^n - 1 делится на 41. Хмм, 41 простое... Какая известная теорема может помочь нам в нахождении хотя бы одного n, удовлетворяющему предыдущему предложению?

Подсказка 4

Малая теорема Ферма утверждает, что при n = 40 10^40 - 1 делится на 41. Теперь хочется как-то найти k из условия... а на что должно делиться n, чтобы 10^n - 1 делилось на 41? Мы не можем найти все такие случаи, но может попробовать найти хотя бы одного такое k и доказать, что утверждение работает в обе стороны.

Подсказка 5

Рассмотрим все такие d, что 10^d - 1 делится на 41 и выберем среди них наименьшее m. Докажем, что если n делится на m, то 10^n - 1 делится на 10^m - 1, а, значит, и на 41. Если это получится, то у нас найдено k, но условие "тогда и только тогда" пока не доказано. Теперь попробуем доказать, что если 10^n - 1 кратно 41, то n кратно m.

Подсказка 6

Мы взяли m наименьшим, т.к. обычно это помогает в поиске противоречий. Для того чтобы доказать утверждение из подсказки 5, попробуем найти НОД(10^n - 1, 10^m - 1).

Подсказка 7

В процессе поиска c помощью алгоритма Евклида можно заметить, что у нас в конце концов появится 10^(НОД(m, n)) - 1. Предположим, что n не делится на m, тогда НОД(n, m) < m. Осталось лишь найти противоречие с тем, что m - наименьшее взятое число из набора.

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

Заметим, что

10n−-1 Rn = 9

Так как числа $9$ и $41$ взаимно просты, то $Rn$ кратно $41$ тогда и только тогда, когда $n 10 − 1$ кратно $41.$ Поскольку $41$ — простое, согласно малой теореме Ферма

1040− 1 ... 41

Рассмотрим все натуральные $d,$ при которых $10d − 1$ кратно $41;$ наименьшее такое $d$ обозначим за $m.$

Если $n$ делится на $m,$ то

10n− 1= 10tm − 1= (10m − 1)(10(t− 1)m +10(t−2)m + ⋅⋅⋅+10m +1)

Значит, $n 10 − 1$ делится на $m 10 − 1,$ а значит, и на $41,$ что и требовалось.

В обратную сторону: если $n 10 − 1$ кратно $41,$ то рассмотрим $n m НО Д(10 − 1,10 − 1).$ Воспользуемся алгоритмом Евклида, т.е. свойством НОД

НО Д(a,b)= НОД(a− kb,b),где a,b,k∈ ℕ

Теперь

НОД(10n− 1,10m− 1)= НОД(10n− 1− 10n−m(10m− 1),10m− 1)

НОД(10n− 1− 10n+ 10n− m,10m − 1)= НО Д(10n−m − 1,10m− 1)

Повторяя эти действия, убеждаемся, что в конце получается число $НОД(n,m) 10 − 1.$

Если $n$ не делится на $m,$ то

НОД(n,m)< m

Значит, $m$ — не минимальное натуральное число, при котором $m 10 − 1$ кратно $41$ — противоречие. Значит, $n$ кратно $m,$ что и требовалось доказать.

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

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

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

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

Пусть $a,b,c$ — взаимно простые в совокупности натуральные числа, и

( 2 2 2 n n n) Dn = a+ b+ c,a + b+ c ,a + b + c

Найдите все возможные значения $D , n$ где $n−$ натуральное число, кратное 3. Запись $(a,a ,a,...,a ) 1 2 3 k$ обозначает наибольший общий делитель целых чисел $a ,a,a ,...,a . 1 2 3 k$ Целые числа $a ,a,a ,...,a 1 2 3 k$ называются взаимно простыми в совокупности, если $(a ,a,a ,...,a )= 1. 1 2 3 k$

Источники: Иннополис-2023 (см. dovuz.innopolis.university)

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

Подсказка 1

А давайте для начала попробуем ручками проверить различные a, b, c - чтобы понять, каким вообще может быть D.

Подсказка 2

Пупупу… а теперь посмотрим внимательно на условие. Каким свойством обладают скобки вида: (aⁿ + bⁿ + cⁿ)?

Подсказка 3

Да, эти скобки симметричны! Если поменять какие-то две переменные местами, то выражение не изменится. А теперь, учитывая, что мы получили какие-то значения D - попробуйте перейти к симметрическим многочленам. К какому противоречию мы придём?

Подсказка 4

Верно, мы придём к тому, что существует какое-то просто p, которое делит произведение abc. Теперь нужно аккуратно доказать, что в таком случае простое p делит каждое из чисел a, b, c! Тогда, мы докажем, что возможны только D = {1, 2, 3, 6}.

Подсказка 5

Остаётся только привести пример чисел a, b, c для каждого возможного D!

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

Пусть $σ,σ ,σ 1 2 3$ — элементарные симметрические многочлены и $n n n sn = a + b + c.$ Воспользуемся формулой Ньютона

sk = σ1sk−1− σ2sk−2+ σ3sk−3

Докажем, что $D ∈ {1,2,3,6}. n$ Предположим, что существуют такие взаимно простые в совокупности $a,b,c$ , что $D n$ отличен от $1,2,3,6.$ Докажем, что тогда $σ ,σ,σ 1 2 3$ имеют общий делитель, больший 1. В самом деле, из формул Ньютона следует, что при разложении $s n$ через $σ ,σ ,σ 1 2 3$ моном, не содержащий $σ 1$ и $σ, 2$ с точностью до знака имеет вид $3σ n3. 3$ Поэтому если $D n$ делит $s = σ 1 1$ и $D n$ делит $2 s2 = σ1 − 2σ2,$ то $Dn$ делит $σ1,2σ2,3σ3.$

При $Dn,$ отличном от $1,2,3,6$ у чисел $σ1,σ2,σ3$ есть общий делитель, больший 1. Пусть $p$ — простой множитель, входящий в этот делитель. Тогда $p$ делит $abc,$ откуда (без ограничения общности) $p$ делит a. Но тогда $p$ делит $(ab+ bc+ ca)$ и $p$ делит $bc,$ т.е. (без ограничения общности) $p$ делит $b.$ Наконец, из того, что $p$ делит $(a+b+ c),$ получаем, что $p$ делит $c.$ Значит, $(a,b,c)≥ p,$ но по условию $(a,b,c)= 1$ — противоречие.

Итак, $Dn ∈ {1,2,3,6}.$ Набор $(1,1,2)$ реализует $Dn = 2,$ набор $(1,1,1)$ — $Dn = 3,$ набор $(1,4,7)$ — $Dn = 6.$ Для $Dn = 1$ возьмем простое число $p >3$ и положим $a =b =1, c =p− 2.$ Тогда $a+ b+c =p$ и $p$ не делит $2 2 2 2 a +b + c =p − 4p+ 6,$ откуда $Dn = 1.$

Ответ:

${1,2,3,6}$

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

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

При каком условии на $k$ и $n$ уравнение

kx+ yn= 1

имеет решение в целых числах?

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

Совершенно очевидно, что если $НОД(k,n)=d >1$ , то левая часть делится на $d$ , значит, и правая часть должна делиться на $d$ , но 1 точно на $d >1$ не делится.

Если же $НОД(k,n)=1$ , то применим алгоритм Евклида к числам $k$ и $n$ . При этом на очередном шаге будем выражать новые числа линейным образом через $k$ и $n$ . Например, после первого шага мы ищем $НОД(n− k,k)$ , если $n> k$ , потом снова вычитаем из большего меньшее, и так далее. В итоге мы придем к тому, что одно из чисел в скобках станет равно 1, и при этом будет выражено линейно через $k$ и $n$ . Значит, мы смогли выразить 1 в виде $kx +yn =1$ , что и требовалось.

Замечание. А что произойдет, если справа написать не 1, а $s$ ? Во-первых, на $НОД(n,k,s)$ можно сократить. Если после этого $s$ не делится на $НО Д(n,k)$ , то решений, очевидно, нет. Если делится, то решения есть по тому же алгоритму Евклида. В конце надо лишь домножить на $s НОД(n,k)$ . Более интересен вопрос найти все решения подобного ЛДУ, но этот вопрос мы оставим для самостоятельных размышлений.

Ответ:

при взаимно простых $k$ и $n$

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

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

На прямой сидит блоха, которая может прыгать либо на 15 сантиметров, либо на 21 сантиметр (в обе стороны). В каких точках прямой она может побывать?

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

Пусть прыжков длиной 15 сантиметров вправо было сделано на $x$ больше, чем таких же прыжков влево, аналогично введем $y$ как разницу между количеством прыжков вправо и влево на 21 сантиметр.

Тогда блоха оказалась в точке с координатой $15x+ 21y$ (если это число отрицательно, то левее изначальной точки).

Таким образом, нас интересует, при каких $s$ уравнение $15x+ 21y =s$ имеет решение.

Если $.. s. НОД (15,21)= 3$ , то такие $x$ и $y$ существуют. Наоборот, если $s$ не делится на 3, то блоха в такой точке оказаться не может.

Ответ: во всех точках, отстоящих от изначальной на кратное 3 число сантиметров

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

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

Существует ли бесконечная арифметическая прогрессия с ненулевой разностью, состоящая только из степеней (выше первой) натуральных чисел?

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

Подсказка 1

Работать напрямую с условием, что число — степень выше первой, неудобно. Лучше перейти к простым множителям: как выглядит разложение на простые у таких чисел?

Подсказка 2

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

Подсказка 3

Вспомните, что если арифметическая прогрессия покрывает все остатки по модулю p², то среди её членов найдётся число, которое делится на p, но не на p². Как организовать покрытие всех остатков? Какое простое p стоит для этого выбрать?

Подсказка 4

Рассмотрите простое p, взаимно простое с первым членом прогрессии и её разностью. Возьмите достаточно много первых членов прогрессии и посмотрите на их остатки по модулю p².

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

Если натуральное число делится на некоторое простое число $p,$ но не делится на $p2,$ то оно точно не является степенью выше первой. Попробуем найти такой член в прогрессии. Пусть $a1$ — первый член, $d$ — разность. Возьмём простое число, на которое не делятся $a1$ и $d.$ Среди первых $p$ членов точно найдётся такой член $x,$ который делится на $p$ (потому что эти члены дают попарно разные остатки при делении на $p$ ). Этот член является хотя бы второй степенью, значит, он делится и на $2 p .$ Рассмотрим член $x+pd.$ Ясно, что он делится на $p,$ но не на $2 p.$ То есть такой последовательности нет.

Ответ:

Не существует

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