Пусть $%a,b -$% любые натуральные, больше $%2$%. Докажите, что существует натуральное число $%k$% и конечная последовательность $%n_1,n_2,...,n_k$% натуральных чисел, таких что $%n_1=a, n_k=b$% и $%n_in_{i+1}$% делится на $%\left( n_i+n_{i+1}\right)$% для каждого $%i=1,2,...,k$%.

задан 18 Май '16 12:46

Лемма, если кому-то поможет. Если $%f, g, f > g$% — делители числа $%c$%, то число $%\frac{f-g}{g}c$% составляет искомую пару для числа $%c$%. Этак можно из числа изъять любой простой делитель (возможно, единицу), но зато в него нужно и добавить простой делитель (возможно, единицу). PS. У меня получилось довольно заковыристое (для меня) доказательство, но гораздо проще этот факт доказать напрямую: подстановкой и вычислением. :)

(18 Май '16 19:21) abracadabra
10|600 символов нужно символов осталось
2

Рассмотрим граф, вершинами которого являются все натуральные числа, большие двух. Два числа $%m$% и $%n$% соединим ребром, если $%mn$% делится на $%m+n$%. Нужно доказать, что полученный граф связен.

Заметим, что если число имеется число $%k$%, которое делится на $%d\ge3$%, то $%k$% и $%k(d-1)$% соединены ребром, что прямо следует из определения. Из сказанного следует, что любое число $%n$% можно последовательно домножить на $%n-1$%, на $%n-2$% и так далее, соединяя его путём с числом $%n!$%.

Теперь достаточно показать, что любое число вида $%n!$% при $%n\ge3$% соединено в графе с числом $%3$%. При $%n=3$% это ясно сразу. Пусть $%n\ge4$%. Достаточно доказать, что $%n!$% соединено с $%(n-1)!$% некоторым путём.

Предположим, что $%n$% простое. Тогда $%(n-1)!$% делится на $%n+1$% ввиду $%2 < \frac{n+1}2 < n-1$%. По замечанию из второго абзаца, $%(n-1)!$% соединено с $%n!$%.

Теперь пусть $%n$% составное. Разложим его на простые множители. Пусть $%p$% -- один из них. Тогда на него можно сократить в том смысле, что после деления получится число, соединённое с ним ребром. Для этого нам достаточно знать, что $%(n-1)!$% делится на $%p+1$%, но это заведомо так, поскольку $%p+1\le\frac{n}2+1\le n-1$%. Сокращая последовательно на все такие $%p$%, мы в итоге сократим число на $%n$%, получая $%(n-1)!$%.

ссылка

отвечен 19 Май '16 1:12

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×669
×149

задан
18 Май '16 12:46

показан
489 раз

обновлен
19 Май '16 1:12

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

по почте:

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

по RSS:

Ответы

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

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