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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подсказка 1

Попробуем идти от противного. Пусть наши числа — это n-1, n и n+1. Тогда нас спрашивают о произведении чисел n и n² - 1, которые взаимно просты. Что тогда можно сказать об этих числах, если их произведение является натуральной степенью выше 2?

Подсказка 2

Верно, n и n^2-1 сами являются точными степенями, причем с одним и тем же показателем b двух взаимно простых чисел x и y. Можно ли найти связь между x и y?

Подсказка 3

Верно! Так как n = x^b и n² - 1 = y^b, получаем x^(2b) - y^b = 1. А можно ли от степеней 2b и b перейти к более простым степеням?

Подсказка 4

Можно! Нетрудно видеть, что x² - y делит левую часть приведенного выше уравнения. А тогда x² - y делит и число 1, то есть равно 1. Таким образом, x² = y + 1. Имеет ли тогда решения уравнение, полученное в предыдущей подсказке?

Подсказка 5

Верно, не имеет! Можно подставить x² = y+1 и заметить, что (y+1)² - y² = 2y + 1 > 1. А можно ли доказать, что при b > 2 разность степеней чисел y+1 и y будет больше?

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

Предположим противное. Пусть последовательные числа имеют вид $n − 1,n,n+1$ ( $n> 1$ ). Их произведение равно $2 (n− 1)n(n+ 1)=n(n − 1).$ Заметим, что числа $n$ и $2 n − 1$ взаимно просты. Следовательно, если их произведение равно $b a ,$ где $b≥ 2$ , то $b 2 b n= x ,n − 1 =y ,$ $(x,y)= 1.$ Таким образом, $2b b x − y = 1.$ Нетрудно видеть, что $2b b x − y$ делится на $2 x − y,$ а значит это число делит единицу. То есть $2 x − y =1.$ Подставим $y+ 1$ вместо $2 x$ в уравнение и получим $b b (y+ 1)− y = 1.$

Ясно, что для натурального $y$ и $b≥ 2$ справедливо неравенство $b+1 b+1 b b (y+ 1) − y ≥ (y+ 1) − y,$ поскольку оно сводится к неравенству $b b (y +1)y >y (y− 1),$ которое очевидно верное. Таким образом, $b b 2 2 (y+ 1)− y ≥ (y +1) − y =2y+ 1> 1$ при $y >0.$ Если же $y =0,$ то $2 n =1,$ откуда $n= 1,$ но тогда число $n − 1$ не натуральное, пришли к противоречию.

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

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

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

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

Найдите все натуральные $m$ такие, что $33+ 66+...+(3m)3m$ является квадратом натурального числа.

Источники: автор И. А. Ефремов

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

Подсказка 1

В первом слагаемом 3 входит в 3 степени. А в остальных?

Подсказка 2

Верно! Все остальные слагаемые делятся 3⁴, а первое не делится. Какой вывод можно сделать?

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

Заметим, что все слагаемые кроме первого делятся на $34$ , а первое слагаемое делится только на $33$ . Тогда и все выражение делится ровно на третью степень тройки, то есть не может быть точным квадратом.

Ответ: таких нет

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

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

Найдите все натуральные числа $a$ , $b$ и $c$ такие, что

(ab−-1)(ac−-1)- bc

является квадратом целого числа.

Источники: 61 УТЮМ

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

Заметим, что $(ab−-1)(ac−-1)-=(a − 1)(a − 1) < a2 bc b c$ . При этом наше выражение не меньше $(a− 1)2$ . Тогда $(a− 1) (a− 1) =(a− 1)2 b c$ . Если $a >1$ , то $b =c= 1$ (иначе левая часть будет строго больше правой). Если же $a =1$ , и $b,c> 1$ , то левая часть снова будет больше правой. Тогда одно из чисел $b$ и $c$ равно 1, а второе может быть любым.

Ответ:

$(1,1,c)$ , $(1,b,1)$ , $(a,1,1)$ для любых натуральных $a$ , $b$ и $c$

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

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

Существует ли такое натуральное число $n$ , что $6n− 1$ имеет ровно $n$ натуральных делителей?

Источники: 24 Кубок Колмогорова

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

Пусть $n =2kt$ , где $t$ нечетно. Тогда

2kt ( 2k−1t )( 2k−2t ) ( t )(t ) 6 − 1= 6 + 1 6 + 1 ... 6 +1 6− 1 .

Заметим, что все множители в этом разложении взаимно просты, так они нечетны и каждый из них, уменьшенный на 2, равен произведению всех следующих. Следовательно, количество делителей числа $n 6 − 1$ равно произведению количеств делителей у множителей. Всего множителей $k+1$ и все они больше единицы, поэтому если ни один из множителей не является точным квадратом, то количество делителей у каждого множителя четно. Тогда количество делителей числа $n 6 − 1$ делится на $k+1 2$ , а $n$ не делится на $k+1 2$ . Таким образом, один из множителей должен являться точным квадратом. Так как среди натуральных чисел не может быть двух последовательных квадратов, то квадратом является или $6t+1$ , или $6t− 1$ . При этом $6t− 1≡ 2 (mod 3)$ и тоже не является квадратом. Значит, $6t+ 1= m2$ , $6t = (m + 1)(m − 1)$ . Обе скобки не могут одновременно делиться на 3, поэтому одна из них делится на $3t$ , откуда разность между скобками хотя бы $3t− 2t > 2$ при $t> 1$ . Очевидно, $t=1$ тоже не подходит.

Ответ: не существует

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

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

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

Источники: Лига Открытий - 2022

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

Подсказка 1

Если какое-то из наших чисел достаточно большое, то один только его куб может быть больше произведения всех чисел. Это наталкивает на мысль, что если условие задачи выполнено, все числа должны быть “не слишком велики”.

Подсказка 2

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

Подсказка 3

Каждый простой множитель числа 20222022 входит как множитель в какое-то из искомых чисел. Если среди простых есть “слишком большое” (то есть такое, куб которого больше произведения всех чисел), то для нас это заведомо значит, что сумма всех кубов тоже будет слишком большой!

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

Разложим число 20222022 на простые множители: $20222022= 2⋅3⋅73⋅137⋅337$ . Предположим, что такой набор существует. Тогда легко видеть, что сумма кубов не меньше, чем $3 337 >20212021$ — противоречие.

Ответ: не существует

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

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

Обозначим за $σ(n)$ сумму всех делителей числа $n$ (включая само число). Для каких $n$ выполняется неравенство $σ(8n)> σ(9n)?$

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

Подсказка 1

Для начала напишите формулу для δ(n) через разложения числа n на степени простых.

Подсказка 2

Попробуйте из этой формулы вывести, что при умножении чисел n, m на число взаимно простое с ними, числа δ(n), δ(m) тоже умножаются на одно и то же число. Из этого следует, что достаточно рассматривать числа какого-то конкретного вида. Какого?

Подсказка 3

Правильно, достаточно найти решения для n = 3^l * 2^k. Теперь рассмотри дробь δ(8n)/δ(9n) и будем выяснять, когда она больше 1. Знаменатель очевидно больше 9, а при каких k числитель не меньше 9?

Подсказка 4

Верно при k ≤ 2. А что будет если l =0? А если больше?

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

Запишем $n$ в каноническом виде: $n= ∏m pki. i=1 i$ Тогда $σ(n)= ∏m (1+ p +...+pki). i=1 i i$

Отсюда видно, что при домножении или делении числа $n$ на какой-то множитель, взаимно простой с числами $8$ или $9$ (то есть, не кратный $2$ и $3$ ), правая и левая части неравенства $σ(8n)>σ(9n)$ изменяются в одинаковое количество раз. Значит, нам достаточно найти все решения вида $kl n= 2 3$ — всё остальное можно получить из них домножением на какое-то число $x,$ не делящееся ни на $2,$ ни на $3.$

Тогда

σ(8n)=(1+ 2+ ...+ 2k+3)(1+ 3+ ...+ 3l)

k l+2 σ(9n)=(1+ 2+ ...+ 2)(1 +3+ ...+ 3 )

Их частное должно быть больше $1:$

1+2+...+2k+3- ----7---+ 8 σ(8n)= 11++32++......++32l+k2-= 1+2+..4.+2k---> 1 σ(9n) -1+3+...+3l 1+3+...+3l + 9

Знаменатель этой дроби всегда больше $9.$ Числитель же равен $9$ при $k =2$ и и меньше $9$ при больших $k.$ Осталось разобрать два случая: $k =1$ и $k =0.$ При $k= 1$ имеем:

7 -----4----- 3 + 8> 1+ 3+...+3l + 9

31 4 3-> 9+ 1+3-+...+-3l

Правая часть равна $13$ при $l= 0.$ При $l≥ 1$ правая часть не больше $10.$ Значит, $σ(8n)> σ(9n)$ при $k =1$ и $l≥ 1.$ При $k =0$ имеем:

15 >9 +-----4-----l 1 +3+ ...+ 3

Это равенство всегда верно. Таким образом, у нас есть две серии ответов.

Ответ:

$n =3lx$ или $n= 6⋅3lx,$ где $l$ — целое неотрицательное число, а $x$ — натуральное число, не делящееся ни на $2,$ ни на $3$

Курсы

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

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

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

Обозначим через $d(n)$ количество натуральных делителей числа $n.$ Последовательность натуральных чисел $a ,a,...,a 1 2 400$ удовлетворяет условию

an+1 = d(an)+ d(n)

Докажите, что в этой последовательности не более $210$ простых чисел.

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

Отметим, что если $n$ не является квадратом натурального числа, то хотя бы одно из чисел $a ,a n n+1$ не является простым. Докажем это утверждение от противного – тогда $an$ простое. Число $. d(n).. 2,$ так как $n$ не квадрат, а $d(an)=2.$ Следовательно, $a = d(a )+d(n) ... 2 n+1 n$ , при этом $a > 2, n+1$ поэтому $a n+1$ не является простым – противоречие.

Вычеркнем из последовательности $an$ все элементы, индексы которых являются квадратами, а все остальные элементы разобьем на пары. Между любыми двумя квадратами находится четное количество чисел ( $. (a+ 1)2− a2− 1= 2a .. 2$ ), поэтому такой способ ставит в пару подряд идущие числа. По доказанному, в каждой паре находится не более одного простого элемента, значит среди $400− 20 =380$ невычеркнутых элементов есть не более, чем $190$ простых. Вычеркнутые элементы могут быть простыми. Их количество равно $20,$ поэтому общее число простых элементов можно оценить как $190+20= 210,$ что и требовалось доказать.

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

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

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

(a) $НОД(Fn,Fn+1)= 1;$

(b) $НОД(Fm+n,Fm) =НО Д(Fm,Fn);$

(d) $.. .. Fn .Fm ⇔ n.m,$ если $m ⁄= 2.$

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

(a) Будем доказывать утверждение по индукции. База $n =1$ очевидна. Переход: согласно алгоритму Евклида, $НОД(Fn,Fn+1)= НО Д(Fn,Fn−1),$ и $Н ОД(Fn,Fn− 1)= 1$ согласно индукционному предположению.

(b) Для доказательства воспользуемся утверждением

Fn+m = Fn− 1Fm + FnFm+1

Если его истинность доказана, то согласно алгоритму Евклида

НОД(Fm+n,Fm) =Н ОД(Fn−1Fm + FnFm+1,Fm)= НОД (FnFm+1,Fm)= НО Д(Fn,Fm )

последний переход выполнен в силу пункта $(a).$

Итак, будем доказывать утверждение индукцией по $n.$ База $n= 1$ очевидна. Покажем переход. $Fm+n = Fm+n−1+ Fm+n−2 = (Fn−2+ Fn− 3)Fm +(Fn−1+ Fn−2)Fm+1$ согласно индукционному предположению, откуда $Fm+n = Fn−1Fm+ FnFm+1,$ что и требовалось доказать.

(c) Результат пункта $(b)$ можно интерпретировать как алгоритм Евклида на индексах чисел Фибоначчи (стандартный алгоритм Евклида утверждает, что
$НОД(m +n,m) =НО Д(m,n)$ ). Как мы знаем, алгоритм Евклида для чисел $m$ и $n$ завершается конфигурацией $НОД(НОД (m,n),0),$ поэтому если применять к паре чисел $Fm$ и $Fn$ пункт $(b)$ так же, как мы бы применяли алгоритм Евклида к $m$ и $n,$ то в конце получится $НОД(FНОД(m,n),F0)=FНОД (m,n),$ что и требовалось доказать.

(d) Воспользуемся пунктом $(c).$ Если $.. Fn.Fm,$ то $НОД (Fn,Fm)= Fm = FНОД(m,n)$ согласно $(c),$ откуда $НОД (m, n)=m$ либо $НОД(m,n)= 1,m = 2.$ Второй вариант невозможен по условию, значит $.. n .m,$ что и требовалось. Обратно аналогично: если $.. n .m,$ то $НОД(n,m)= m,$ откуда $НО Д(Fn,Fm )=Fm,$ и значит $.. Fn.Fm.$

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

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

Для каких натуральных $n$ число $Fn- 2$ простое?

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

Отметим, что число $F ..2 ⇔ n ..3 n. .$ в силу предыдущего пункта, так как $F = 2. 3$ Предположим, что $F = 2p 3k$ для некоторого простого $p$ и $k≥ 1.$ В силу предыдущего пункта, $.. F3k .Fk,$ откуда либо $Fk = p,$ либо $2,$ либо $1,$ так как $F3k >Fk.$ Значит, либо $k =1,2,3,$ либо $Fk =p.$ Однако, если $k ≥4,$ то $F3k = F3k−1+ F3k−2 > 2Fk = 2p,$ поэтому никакие из $k> 3$ заведомо не подходят. Непосредственная проверка показывает, что только $k = 3$ удовлетворяет соотношению $F3k =2p.$

Ответ:

$n =9$

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

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

Докажите тождество $F =F 3+F 3 − F3 . 3n n n+1 n−1$

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

Применим трижды тождество

Fn+m = Fn− 1Fm + FnFm+1

сначала к $F3n$ и паре $n,2n,$ а затем к $F2n$ c парой $n,n$ и к $F2n+1$ c парой $n+ 1,n :$

F3n = Fn−1F2n +FnF2n+1 = Fn−1(Fn−1Fn +FnFn+1)+ Fn(FnFn+ Fn+1Fn+1)=

= F3 +F F F + F (F 2 + F2 ) n n−1 n n+1 n n−1 n+1

Для завершения доказательства осталось проверить, что $F3n+1 − Fn3−1 =Fn ⋅(F2n−1+ Fn−1Fn+1+Fn2+1).$ Разложим левую часть на две скобки по формуле разности кубов, тогда вторые скобки в левой и правой части сразу совпадут, а первые будут равняться так как $Fn+1− Fn−1 = Fn.$

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

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

Докажите, что любое натуральное число $n$ можно единственным образом представить в виде

∞∑ n= bkFk k=2

где все числа $bi$ равны $0$ или $1,$ причём $bkbk+1 = 0.$

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

Рассмотрим произвольное представление произвольного числа $n,$ описанное в задаче. Если $F k$ – его наибольшее слагаемое, то докажем, что $n< Fk+1.$ Будем доказывать это утверждение индукцией по $k.$ База $k= 2$ очевидна. Теперь покажем переход. Действительно, $n <Fk+1$ равносильно $n − Fk <Fk−1.$ Рассмотрим представление числа $n− Fk$ полученное из представления $n$ вычеркиванием слагаемого $k.$ Согласно условию задачи, оно не содержит слагаемого $Fk−1,$ поэтому его наибольшее слагаемое не превосходит $Fk−2$ откуда, по предположению индукции, $n− Fk < Fk−1,$ что и требовалось доказать.

Из доказанного утверждения немедленно следует единственность. Действительно, пусть у какого-то $n$ существует два различных представления. Сократим все их общие слагаемые. Так как представления различны, сократятся не все слагаемые, и мы получим два представления некоторого числа $m < n,$ удовлетворяющих условию задачи, наибольшие слагаемые которых различны. Пусть в одном наибольшее слагаемое это $Fi,$ а в другом $Fj,i> j.$ Тогда, согласно утверждению, $m < Fj+1,$ хотя $Fj+1 ≤ Fi ≤ m$ – противоречие.

Существование представления практически очевидно. Если $Fk ≤n < Fk+1,$ то возьмем в представление $n$ слагаемое $Fk,$ а дальше рекурсивно построим представление для $n− Fk.$ Ясно, что $n− Fk < Fk−1,$ поэтому наибольшее слагаемое его представления не превосходит $Fk−2,$ поэтому полученное представление для $n$ тоже удовлетворяет условию задачи.

Интенсивы

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

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

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

Загадано число от $1$ до $144.$ Разрешается выделить одно подмножество множества чисел от $1$ до $144$ и спросить, принадлежит ли ему загаданное число. За ответ да надо заплатить $2$ рубля, за ответ нет — $1$ рубль. Какая наименьшая сумма денег необходима для того, чтобы наверняка угадать число?

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

Пусть $a = 2,a =3,a = a + a 1 2 i i−1 i−2$ для $i≥3.$ Тогда $a = 144. 10$ Докажем по индукции, что среди не менее, чем $a i$ чисел, загаданное число нельзя угадать, заплатив менее, чем $i+1$ рубль. Из этого утверждения будет следовать, что необходимо потратить хотя бы $11$ рублей.

Для $i= 1$ и $i=2$ это верно.

Пусть чисел не менее, чем $ai.$ Тогда либо множество $M$ чисел, выделенных в первом вопросе, содержит не менее $ai−2$ чисел (первый случай), либо множество чисел, не попавших в $M,$ содержит не менее $ai−1$ чисел (второй случай). В первом случае, если загаданное число попало в $M,$ то за ответ нужно заплатить $2$ рубля, и, по предположению индукции, еще не менее $(i− 2)+1$ рублей для того, чтобы угадать число, т. е. всего не менее $i+ 1$ рублей. Во втором случае, если загаданное число не попало в $M,$ то нужно заплатить $1$ рубль за ответ и не менее чем $(i− 1)+1$ рубль за угадывание числа, т. е. вновь всего не менее чем $i+1$ рублей.

Алгоритм отгадывания числа ясен из предыдущих рассуждений: на каждом шаге множество $M$ из $ai$ чисел, содержащее загаданное число, нужно разбивать на множества $M1$ из $ai−2$ чисел и $M2$ из $ai−1$ чисел, и задавать вопрос о принадлежности числа множеству $M1.$

Ответ:

$11$ рублей

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

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

Дано натуральное число $n.$ Докажите, что произведение любых $n$ подряд идущих чисел Фибоначчи делится на произведение первых $n$ чисел Фибоначчи.

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

Введем обозначение $P(i,n)= F ⋅F ⋅...⋅F . i+1 i+2 i+n$ Фактически, задача свелась к доказательству того, что $P (i,n)..P (0,n) .$ для всех $i≥ 0,n ≥1.$ Проведем доказательство по индукции по парам чисел $(i,n).$ База индукции $(0,k)$ тривиальна для всех $k.$ Теперь допустим, что для всех $′ ′ (i,n ),$ где $′ ′ i≥i,n≥ n$ , кроме пары $′ ′ i=i ,n =n ,$ утверждение уже доказано; покажем утверждение для $(i,n).$ Для этого снова вспомним тождество

Fn+m = Fn− 1Fm + FnFm+1

С помощью него получим, что

P(i,n)=P (i,n− 1)⋅Fi+n = P(i,n− 1)⋅(FnFi+1+ Fn−1Fi)=

= P(i,n − 1)⋅FnFi+1+ P(i− 1,n)⋅Fn−1

Поскольку по предположению индукции $P(i,n− 1)⋅Fn ...P (0,n− 1)⋅Fn = P(0,n)$ и $P(i− 1,n)...P(0,n),$ получаем что и $P (i,n)...P (0,n),$ что и требовалось доказать.

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

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

Дана последовательность Фибоначчи $F (F =0,F = 1). n 0 1$ Докажите, что существует такое натуральное $n,$ имеющее не менее $100$ различных простых делителей, что $Fn$ делится на $n.$

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

Рассмотрим последовательность чисел $A ,A ,..., 0 1$ построенную рекурсивно: $A = 12,A = F 0 k Ak−1$ для всех $k> 0.$ Про такую последовательность известно, что:

(a) $. Ak ..Ak−1$ для всех $k> 0.$ Это утверждение можно доказать индукцией по $k.$ Действительно, $. A1..A0$ так как $. A1 = F12 =144..12= A0.$ Если утверждение уже доказано для $k,$ то для $k+1$ оно следует из пункта $(d)$ задачи $8;$

(b) каждый элемент этой последовательности, кроме нулевого, это число Фибоначчи, которое делится на собственный индекс. Действительно, если для некоторого $kAk = Fm,$ то $m =Ak−1$ по построению и, по доказанному, $Ak...Ak−1;$

(c) для любого $k >1$ элемент $A k$ содержит хотя бы на один простой делитель больше, чем $A . k−1$ Поскольку $A ..A , k. k−1$ то $A k$ содержит все простые делители $A , k− 1$ и для доказательства утверждения достаточно установить существование простого $p,$ такого что $. Ak ..p,$ но $. Ak−1 ⁄.. p.$

Тот факт, что такое простое существует для всех $k,$ мы тоже будем доказывать по индукции по $k.$ Покажем базу для $k =2 :A = 144,A = F ..F =55 1 2 144 . 9$ по пункту $(d)$ задачи 8. При этом, $A ⁄... 5. 1$ Переход: пусть утверждение получено для $k,$ и пусть $p$ – такое простое, что $. Ak− 1 ⁄.. p$ , но $. Ak .. p.$ Тогда, по всему тому же пункту $. (d),Ak+1.. Fp.$ Согласно пункту $(c),НОД (Ak,Fp)= НОД(FAk−1,Fp)= FНОД(Ak−1,p) =F1 =1.$ Таким образом, если $p ⁄=2,$ то так как $Ak+1$ делится на все простые делители $Fp,$ а $Ak$ – ни на какие, утверждение задачи получено. И поскольку все элементы последовательности четные, $. Ak−1 .. 2$ для всех $k> 1,$ поэтому $p ⁄=2.$

Итак, согласно последнему пункту, у числа $A100$ делится хотя бы на 100 различных простых чисел. А согласно второму пункту, $A101 = FA100 ... A100.$

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

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

Для натурального числа $n$ оказалось, что каждое из чисел $C1,C2,...,Ck− 1 n n n$ делится на $n,$ а число $Ck n$ — нет. Докажите, что $k$ — простое число.

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

Докажем чуть больше: что $k$ – наименьший простой делитель $n.$ Для этого обозначим через $p$ наименьший простой делитель $n.$ Ясно, что $. Cpn = n(n−1)...p(n!−p+1)⁄.. n$ так как в противном случае было бы выполнено $. (n − 1)...(n− p+ 1)..p!,$ хотя ни один из сомножителей не делится на $p.$ Таким образом, $p ≥k,$ ведь $k$ – наименьшее такое, что $k .. Cn ⁄. n.$ Теперь предположим, что $k <p.$ Так как $k$ меньше, чем наименьший простой делитель $n$ , $НОД (n,l)= 1$ для любого $l≤k$ Поэтому $НОД(n,k!)= 1,$ откуда $k n(n−1)...(n−k+1).. Cn = -----k!-----.n,$ что противоречит условию задачи. Значит $p =k,$ и утверждение задачи доказано.

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

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

Докажите, что для любого простого $p> 2$ выполнено

(2p) 2 p ≡ 2 (mod p)

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

Используя тождество Вандермонда для $m= n =k =p,$ получаем

(2p) (p)(p) (p)( p ) ( p )(p) (p)(p) p = 0 p + 1 p− 1 +⋅⋅⋅+ p− 1 1 + p 0

Первый и последний члены в правой части равны $1.$ Поскольку $p$ простое число, оно делит каждый биномиальный коэффициент $( ) pk$ при $1 ≤k ≤p− 1.$ Таким образом, каждое из оставшихся слагаемых делится на $p2,$ поэтому выполнено сравнение $( ) 2pp ≡2 (mod p2).$

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

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

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

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

Докажите, что для любой пары натуральных чисел $m$ и $k$ существует единственное представление

(ak) (ak−1) (at) m = k + k− 1 +...+ t

где $ak >ak−1 > ...> at ≥ t≥1.$

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

Сначала докажем единственность. Предположим, что $m$ — минимальное число, представляемое двумя последовательностями $a ,...,a k t$ и $bk,...,br.$ Первая позиция, в которой они различаются — это позиция $k$ (иначе $m$ было бы не наименьшим). Пусть $ak > bk.$ Тогда с помощью тождества $(n) (n−1) (n−1) k = k−1 + k$ и замечания $bk− s≥ bk−s$ для любого $s$ такого, что $k− s≥ r,$ получаем неравенства

(bk) (bk− 1) (bk − k+ 1) (bk+1) (ak) m ≤ k + k− 1 + ...+ 1 < k ≤ k ≤ m

противоречие.

Чтобы доказать существование, применим жадный алгоритм: найдем наибольшее $ak$ такое, что $( ) akk ≤ m,$ и применим тот же алгоритм с заменой $(m,k)$ на $( ) (m− akk,k− 1).$ Нам осталось убедиться, что полученная последовательность действительно уменьшается, но это следует из предположения: $( ) m < ak+k1 ,$ а значит $( ) ( ) m− akk < akk−1.$

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

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

Даны натуральные числа $1≤ k≤ n.$ Докажите, что $k$ является делителем суммы

k−∑1 ( ) n (−1)i n i=0 i

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

Преобразуем выражение:

k∑−1 () k∑−1 (( ) ( )) n (−1)in = n (−1)i n− 1 + n − 1 = i=0 i i=0 i i− 1 k∑−1 i(n − 1) k∑−1 i(n− 1) = ni=0(−1) i + ni=1(− 1) i− 1 = k∑−1 ( ) k∑−2 ( ) = n (−1)in − 1 − n (− 1)i n− 1 = i=0 ( i) i=0 i = n(−1)k−1 n− 1 = (nk)− 1 = k(−1)k−1k

Теперь понятно, что сумма делится на $k.$

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

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

Пусть $n$ — натуральное число. Докажите, что

n 0 0 [n∕2] 1 1 [(n−1)∕2] k k [(n−k)∕2] n n 0 C2n+1 = 2CnC n + 2C nCn−1 + ⋅⋅⋅+ 2 CnCn−k + ⋅⋅⋅+ 2 CnC0

( $k --n!-- Cn = k!(n−k)!$ — число способов выбрать $k$ предметов из $n$ без учёта порядка; $[x]$ — наибольшее целое число, не превосходящее $x.$ )

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

Выражение слева по определению равно количеству способов выбрать из $2n +1$ человек $n$ без учета порядка. Покажем, что этому же числу равна правая часть. Зафиксируем разбиение всех $2n +1$ людей, кроме одного, на пары. Пусть ровно из $k$ пар мы выбрали по одному человеку. Выбрать эти $k$ пар мы можем ровно $k Cn$ способами, а в самих парах $k 2$ – способами выбрать по одному человеку из пары.

Далее, нам осталось выбрать еще $n− k$ человек. Из остальных пар, в силу рассматриваемого случая, мы выбираем либо обоих людей, либо ни одного. Поэтому из оставшихся пар надо выбрать $[(n − k)∕2],$ из которых мы выберем двух людей, а в случае нечетной разности $n − k$ еще одним выбранным человеком будет тот, что остался без пары. Выбрать эти $[(n− k)∕2]$ пар можно $[(n−k)∕2] Cn−k$ способами, и это завершает выбор $n$ человек в данном случае. Все найденные выше способы перемножаются и получается в точности слагаемое $k k [(n−k)∕2] 2 CnCn−k$ из суммы выше. Рассматривая все возможные $k$ от 0 до $n,$ мы получаем в точности сумму из правой части условия.

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

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

Назовём многочлен $P(x)∈ ℤ[x] p$ перестановочным по простому модулю $p,$ если его значения дают все возможные остатки при делении на $p.$ Существует ли перестановочный по модулю $101$ многочлен степени $17?$

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

Подсказка 1

Давайте доказывать, что такой многочлен существует. Более того, давайте доказывать, что x^17 подходит. Как это можно сделать?

Подсказка 2

Для проверки достаточно показать, что сравнение a^17 = b ^17 бывает только при a = b. Как это можно сделать? Вспомните про первообразный корень и докажите это.

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

Докажем, что $x17$ — перестановочный многочлен. Для этого проверим, что $a17 ≡ b17 ⇔ a ≡b.$

Если $a≡ b,$ то утверждение очевидно.

Пусть $17 17 −117 a ≡ b ⇔ (ab ) ≡ 1.$ Пусть $g$ — первообразный корень по модулю 101. Тогда $−1 n ab ≡ g .$ Получаем систему:

{ 17n g100 ≡1 g ≡ 1

Тогда $gНОД(100,17n) ≡ 1.$ Так как $g$ — первообразный корень, то $НО Д(100,17n)= 100.$ Откуда получаем, что $100 | n.$ Тогда $ab−1 ≡ gn ≡ 1⇔ a≡ b.$

Тогда получаем, что $x17$ осуществляет биекцию $Z → Z , p p$ и, следовательно, является перестановочным.

Ответ: да

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