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