Метод спуска, индукция и последовательное конструирование в ТЧ
Готовиться с нами - ЛЕГКО!
Ошибка.
Попробуйте повторить позже
— непустое подмножество множества натуральных чисел. Для любых 
существует 
такое, что 
делится на 
Докажите, что в 
найдется элемент, на который делятся все элементы 
Подсказка 1
Единственным кандидатом на число, которое делит все остальные является самое маленькое число множества. Рассмотрите его в качестве a, какое число можно взять в роли b?
Подсказка 2
В качестве b рассмотрите b₀ наименьшее число, которое не делится на a. Что вы можете сказать про b?
Подсказка 3
Рассмотрите последовательность b₀, b₁, …, где b_{k+1} | a(a+b_k). Что вы можете сказать про результаты частного? В каких степенях могут входить простые делители a в b_i?
Пусть 
— наименьший элемент в множестве, 
— наименьший элемент множества не кратный 
По условию существует 
такой, что
делит 
аналогично определим 
Докажем по индукции, что 
Заметим, что 
не может делиться на 
иначе 
тогда
то есть база индукции проверена.
Докажем, что 
Аналогично
то есть переход выполнен и 
или 
Пусть 
обозначим за 
степень вхождения 
в 
за 
степень вхождения 
в 
Пусть 
означает 
или 
Тогда имеем 
Пусть существует
тогда 
— противоречие. Пусть существует 
если 
такого
бесконечно быть не может, так как 
значит, с какого-то момента 
откуда, с какого-то момента
— противоречие, так как 
Тогда 
откуда выходит, что 
и 
Значит, 
—
противоречие.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
