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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 261#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$ мы снова сможем выбрать два элемента, произведение которых есть точный квадрат, а значит произведение двух пар чисел, корнями из произведений которых, являются данные, есть точная четвертая степень числа.

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

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

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

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

Доказать, что из $17$ различных натуральных чисел либо найдутся пять таких чисел $a,b,c,d,e,$ что каждое из чисел этой пятёрки, кроме последнего, делится на число, стоящее за ним, либо найдутся пять таких чисел, что ни одно из них не делится на другое.

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

Расставим все числа в последовательность в порядке их возрастания. Пройдём по этой последовательности слева направо и присвоим каждому её элементу числовой индекс следующим образом: индекс числа равен максимальному из индексов его делителей плюс $1$ (если у числа делителей нет, то его индекс равен $1).$ К моменту, когда мы доходим до некоторого числа $n,$ индексы всем его делителям (они могут стоять только слева от $n)$ уже присвоены, поэтому процедура определена корректно. Возможны два случая.

$1)$ В последовательности встретилось число, имеющее индекс $5.$ Тогда у этого числа есть делитель с индексом $4,$ у того, в свою очередь, есть делитель с индексом $3,$ и т. д. Получим пятёрку чисел, в которой каждое следующее делится на предыдущее.

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

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

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

Найдите суммы:
а) $1⋅n +2(n− 1)+ 3(n − 2)+ ...+n⋅1$
б) $Sn,k = k!⋅(n(n − 1)...(n− k+ 1))+ (2⋅3⋅...⋅(k +1))⋅((n− 1)(n− 2)...(n− k))+...+$
$+((n − k +1)(n − k +2)...⋅n)⋅(k(k− 1)⋅...⋅1).$

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

Подсказка 1, пункт а

Заметим, что нашу сумму можно записать в виде (n * n - (n-1)n) + (n(n-1) - (n-2)(n-1)) + (n(n-2) - (n-3)(n-2)) + ... + n * 1. Можно ли разбить ее на две суммы, которые удобно считать?

Подсказка 2, пункт а

Верно! Сумму положительных слагаемых найти просто: вынесем n и появится арифметическая прогрессия. У остальных выносим минус. Тогда надо найти сумму внутри скобок. Можно ли ее телескопировать?

Подсказка 3, пункт а

Заметим, что 3k(k+1) = k(k+1)(k+2) - (k-1)k(k+1). Как теперь найти нужную сумму?

Подсказка 1, пункт б

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

Подсказка 2, пункт б

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

Подсказка 3, пункт б

Каждое слагаемое в скобке выражает ответ на задачу: выбрать k шаров среди первых k + i в ряде из n + k шаров, а затем еще k из последних n - i. А какую задачу тогда решает вся сумма в скобке?

Подсказка 4, пункт б

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

Подсказка 5, пункт б

Верно! Увеличим наш ряд до n + k + 1 шара. Тогда надо выбрать из него 2k + 1 шар и центральный заменить перегородкой. Каково это число способов?

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

(a) Заметим, что $3k(k+ 1)= k(k+ 1)(k+ 2)− (k− 1)k(k+ 1).$ Тогда

n∑−1 n∑−1 3k(k+1)= (k(k+ 1)(k+ 2)− (k− 1)k(k+1))= (n − 1)n(n +1) k=1 k=1

Теперь заметим, что

1 ⋅n +2 ⋅(n− 1)+3 ⋅(n− 2)+...+n ⋅1 =(n⋅n − (n− 1)n)+ (n(n− 1)− (n− 2)(n− 1))+ (n(n − 2)− (n − 3)(n − 2))+...n ⋅1

Раскроем скобки и перегруппируем слагаемые с плюсом и с минусом. Тогда сумма слагаемых с плюсом равна

n⋅n +n ⋅(n− 1)+...+n ⋅1 =n n(n-+1)- 2

Сумма слагаемых с минусом равна

n∑−1 k(k +1)= 13(n− 1)n(n+ 1) k=1

Тогда исходная сумма равна:

n2(n+-1) (n-− 1)n(n-+1) n(n+-1)(n+-2) 2 − 3 = 6

(b) Заметим, что

Sn,k = (k!)2(Ckk ⋅Ckn+ Ckk+1⋅Ckn−1+ Ckk+2⋅Ckn−2+ ...+ Ckn⋅Ckk)

Поймем, какую комбинаторную задачу решает выражение в скобке. Для этого расположим в ряд $n+ k$ шаров. $k k Ck+i⋅Cn−i$ — число способов выбрать $2k$ шаров из этого ряда так, что сначала выбраны $k$ шаров из первых $k +i,$ а затем еще $k$ из оставшихся $n− i.$ Таким образом, сумма в скобке — это число способов вставить перегородку в наш ряд так, что слева и справа от нее не менее $k$ шаров, а затем выбрать по $k$ шаров с каждой стороны.

Эта задача эквивалентна тому, чтобы найти число способов в ряде из $n +k+ 1$ шара выбрать $2k+ 1,$ а затем средний заменить перегородкой. Тогда сумма из скобки равна $C2nk++1k+1.$ Таким образом, $Sn,k =(k!)2C2nk++1k+1.$

Ответ:

а) $n(n+1)(n+2) 6$ б) $(k!)2⋅C2k+1 n+k+1$

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

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

Из первых $k$ простых чисел $2,3,5,...,p k$ $(k> 5)$ составлены всевозможные произведения, в которые каждое из чисел входит не более одного раза (например, $3⋅5, 3⋅7⋅...⋅pk, 11$ и т. д.). Обозначим сумму всех таких чисел через $S.$ Доказать, что $S+ 1$ разлагается в произведение более $2k$ простых сомножителей.

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

Ясно, что $S+ 1= (2+1)(3 +1)...(p +1). k$ Сумма в каждой скобке, кроме первой, чётна, поэтому она разлагается по крайней мере на два простых множителя. Несложные вычисления показывают, что при $k= 5$ число $S+ 1$ разлагается в произведение $11$ простых множителей. Поэтому при $k >5$ число множителей не меньше чем $11+2(k− 5) >2k.$

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

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

Докажите, что количество делителей натурального числа $n$ не превосходит $2√n.$

Источники: ММО - 1960, задача 7.5

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

Если $d$ — делитель числа $n,$ то $n d$ — тоже делитель числа $n.$ Хотя бы одно из этих двух чисел не превосходит $√n.$ Поэтому число делителей не превосходит $√- 2 n.$

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

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

Найдите все натуральные числа $n$ и $m$ такие, что если $a < a <a < ...<a 1 2 3 k$ — все натуральные делители $n,$ кроме 1 и $n,$ и $b1 < b2 < ...< bt$ — все натуральные делители числа $m,$ кроме 1 и $m,$ то $k= t,$ а также $|ai− bi|= 1$ для каждого натурального $1 ≤i≤ k.$

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

Заметим, что числа $a 1$ и $b 1$ — наименьшие простые делители $n$ и $m$ соответственно. Тогда одно из них равно $2,$ а второе — $3.$ Не умаляя общности, $a1 = 2,$ $b1 = 3.$ Тогда у числа $m$ все делители нечётные. Значит, все делители числа $n$ чётные. То есть $ℓ n= 2$ для некоторого натурального $ℓ.$

Если $k= 1,$ то $n= 4,$ $m =9.$ Иначе понятно, что $a2 =4$ и

b2 = 4+ 1= 5.

Если $k= 2,$ то $m =15,$ $n= 8.$ Если $k= 3,$ получаем, что $b3 = 9,$ так как $b3$ должно делиться на $3$ или на $5.$ Но тогда у числа $m$ найдётся ещё один лишний делитель — число $15.$ Противоречие.

Далее считаем, что $k ≥4.$ Тогда, так как $bb = b b , 1k 2k−1$ получаем, что

ℓ−1 ℓ−2 3(2 ± 1)=5(2 ± 1).

По модулю $2ℓ−2$ имеем: $± 3± 5$ делится на $2ℓ−2$ при некоторой расстановке знаков, откуда $ℓ− 2≤ 3,$ то есть $ℓ≤5.$ Но поскольку $k ≥4,$ тогда $ℓ= 5.$ Получаем, что

4 b4 =2 − 1= 15

(так как $b4$ делится на $3$ или на $5),$ то есть, $b3 =9.$ Отсюда получаем: $m = 45,$ $n= 32.$

Ответ:

$(4,9),$ $(8,15),$ $(32,45),$ $(9,4),$ $(15,8),$ $(45,32)$

Курсы

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

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

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

Доказать следующие свойства биномиальных коэффициентов ( для любых $n$ и $k$ таких, что $1 ≤ k ≤ n$ ):

a) $(n) (n ) k = n− k$

b) $(n)+ (n ) = (n+1) k k+1 k+1$

c) $n∑ ( ) ( ) ( ) ( ) ( ) ( ) ( ) nk = nn + nn−1 + nn−2 + ⋅⋅⋅+ nk + ⋅⋅⋅+ n1 + n0 = 2n k=0$ (пользуясь исключительно комбинаторным определением! т.е. без бинома Ньютона)

d) $(n) k$ возрастает по $n$ при фиксированном $k$

e)* Фиксируем $n.$ Найти такое $k,$ при котором $( ) nk$ максимально.

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

a) Как мы помним, $(n) k$ равно числу подмножеств размера $k$ у $n$ -элементного множества $S.$ Но любому $k$ -элементному подмножеству $A ⊂ S$ можно однозначно сопоставить $(n − k)$ -элементное подмножество $¯A$ в $S.$ Другими словами, выбрать $k$ элементов из $n$ возможных – это то же самое, что из $n$ -элементного множества ”выкинуть” $\text{[math]}$ $n − k$ элементов.

По формуле для $(n) k$ всё совсем очевидно.
Поскольку $( ) nk = k!(nn!−k)!,$ то $( ) nn−k = (n−nk!)!(k)! = k!(nn−!k)!,$ так как наша формула $--n!-- k!(n−k)!$ очевидно симметрична относительно замены $k$ на $n− k.$

b) Это легко доказать просто поигравшись с формулой $( ) nk = k!(nn−!k)!.$
Действительно: $(n) (n ) --n!-- -----n!---- приведём к общ. знам. n!(k+1)+n!(n−k) k + k+1 = k!(n− k)! + (k+1)!(n−k−1)! = (k+1)!(n−k)! =$
$( ) = n!(((kk++11))!+(n(−n−k)k!)) = (k+n1!()n!(+n1)−k)! = (k+(1n)+!(1n)!−k)! = n+k+11$

c)В левой стороне равенства мы суммируем количество способов выбрать:

$n$ -элементное подмножество из n-элементного множества
$(n− 1)$ -элементное подмножество из n-элементного множества
...
$1$ -элементное подмножество из n-элементного множества
$0$ -элементное подмножество из n-элементного множества

То есть мы суммируем количество способов выбрать все возможные подмножества из $n$ -элементного множества. Но таких подмножеств будет ровно $n 2 ,$ поскольку подмножество множества $X$ можно задать так: сопоставить 0 тем элементам, которые в подмножество не входят, и 1 - тем элементам, которые в подмножество входят. Тогда различных подмножеств множества $X$ всего столько же, сколько строк длины $|X |,$ составленных из нулей и единиц, то есть $2n$

d) $(nk)$ при фиксированном $k$ - это количество способов выбрать $k$ объектов из всё бОльших и бОльших множеств ( $n$ растёт по условию, а $n$ - это и есть "размер" $\text{[math]}$ множества, из которого мы выбираем). Таким образом, очевидно, что т.к. растёт количество элементов в множестве, из которого мы выбираем элементы, то и вариантов выбрать какие-то $k$ у нас будет становиться всё больше и больше.

e)* Заметим такое очевидное соотношение:

$(n ) = ----n!-----= ---n!- ⋅--k-- = (n)⋅--k-- k−1 (k−1)!(n−k+1)! k!(n−k)! n−k+1 k n−k+1$

Что же оно нам даёт? А даёт оно нам условие, при котором при фиксированном $n$ предыдущий по $k$ биномиальный коэффициент не больше следующего. А именно, если присмотреться, то из нашей формулы следует, что:

( ) ( ) n ≤ n если и только если---k---- ≤ 1 k− 1 k n − k+ 1

Но это последнее условие уже, в свою очередь, эквивалентно тому, что $k ≤ n− k + 1,$ то есть $2k ≤ n + 1,$ то есть $k ≤ n+1. 2$

Отсюда делаем вывод, что биномиальные коэффициенты растут при фиксированном $n$ до тех пор, пока $k ≤ n+21.$ То есть, наибольшее значение $( ) nk$ будет при максимальном $k$ таком, что $k ≤ n+1. 2$ А это есть просто $k = ⌊n+1⌋ 2$ ( $⌊...⌋$ означает округление вниз до ближайшего целого.)

Ответ:

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

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

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

α1 α2 αk n =p1 ⋅p2 ⋅...⋅pk

(где $p i$ — различные простые числа) равно

(α1+ 1)(α2+1)...(αk+ 1).

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

Это так, ведь для делителя мы каждую степень простого числа $p i$ выбираем $α + 1 i$ способами. По правилу произведения получается приведённая в условии формула.

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

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

Среди чисел, превышающих $2017,$ найдите наименьшее чётное число $N,$ при котором дробь $15N-−-7 22N − 5$ сократима.

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

Подсказка 1

Чтобы дробь была сократимой, нам нужно, чтобы НОД у числителя и знаменатель был больше одного.

Подсказка 2

Воспользуйтесь алгоритмом Евклида для числителя и знаменателя, чтобы найти НОД!

Подсказка 3

Отлично, теперь мы понимаем, что дробь может быть сократима на 79. Осталось понять, при каких m это верно ;)

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

Наличие общего множителя у чисел $15N − 7$ и $22N − 5$ влечёт за собой наличие такого же множителя у числа $(22N − 5)− (15N − 7)= 7N + 2,$ а далее последовательно у чисел

(15N − 7)− 2⋅(7N + 2)= N − 11, (7N +2)− 7⋅(N − 11) =79.

Так как 79 — простое число, то дробь сократима на 79, поэтому $N − 11 =79m$ для некоторого целого $m.$ По условию $N$ — чётное, поэтому $m =2p+ 1,$ следовательно, $N = 90+ 158p$ для некоторого целого $p.$ По условию также $N$ больше 2017, поэтому

16 p ≥2018− 90158= 1279.

Наименьшее подходящее значение $p= 13,$ соответственно наименьшее $N$ подходит $90+ 158⋅13= 2144.$

Ответ:

2144

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

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

Пусть $НОД(a,b)= (a,b).$ Докажите, что (a) $(a,b)= (a− b,b);$ (b) $(ac,bc)= c⋅(a,b).$

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

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

(b) Пусть $(ac,bc)= cd1$ и $(a,b)= d2$ (ясно, что $ac$ и $bc$ делятся на $c).$ Тогда $ac- d2c$ и $-bc- d2c$ — целые числа по определению $d2.$ Значит, $d1 ≥ d2.$ Аналогично $-ac d1c$ и $bc- d1c$ — целые, поэтому $d2 ≥ d1,$ то есть $d1 = d2,$ что и требовалось доказать.

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