Доказать, что для любых натуральных $%2\leqslant k < m\leqslant n$% найдутся $%n$% таких натуральных чисел, что у любых $%k$% из них есть хотя бы один общий простой делитель, а у любых $%m$% из них общих простых делителей нет.

задан 3 Сен '18 23:28

10|600 символов нужно символов осталось
2

Достаточно рассмотреть случай m=k+1<=n. Будем формировать список из n чисел, выдавая каждому из них какие-то простые множители. Перебираем все k-элементные подмножества множества из n элементов. С каждым из них связываем своё простое число p, и выдаем его элементам данного подмножества. Тогда любые k чисел будут иметь общий простой делитель. Ввиду того, что никакое простое число не выдаётся сразу k+1 из n чисел, никакой набор из k+1 числа общего простого делителя иметь не будет.

Скажем, при k=2, m=3, n=4 мы выдаём 6 простых чисел 2, 3, 5, 7, 11, 13, упорядочивая пары лексикографически. Наборы простых делителей этих чисел получатся такие: {2,3,5}, {2,7,11}, {3,7,13}, {5,11,13}. Сами числа равны произведениям.

ссылка

отвечен 4 Сен '18 3:21

@falcao, большое спасибо!

(4 Сен '18 10:46) Казвертеночка
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,393
×17
×17
×5
×3

задан
3 Сен '18 23:28

показан
264 раза

обновлен
4 Сен '18 10:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru