Метод спуска, индукция и последовательное конструирование в ТЧ

a) Усилим утверждение, покажем, что для четных нет решений. Предположим, что решение есть, и рассмотрим четверку с минимальной суммой

по модулю 2, очевидно, что тогда либо делятся на либо только одно из них, но тогда

противоречие. Пусть тогда приходим к равенству:

тогда у решения сумма меньше, противоречие.

b) Сначала предположим, что существует решение удовлетворяющее

______________________________________________________________________________________________________________________________________________________

Утверждение. Числа попарно различны.

Предположим противное: пусть Тогда:

где — натуральное число, поскольку левая часть натуральна. Это означает:

Подставим:

Следовательно, или В обоих случаях:

что противоречит условию

______________________________________________________________________________________________________________________________________________________

Теперь можно считать, что Заметим, что если — решение, то также является решением, так как:

Рассмотрим квадратное уравнение:

Известно, что Вычислим:

Оценим:

Поскольку — квадратный трёхчлен с положительным старшим коэффициентом, и то корни и лежат по разные стороны от Учитывая получаем:

Таким образом, для решения с мы получаем меньшее решение с:

Применяя метод бесконечного спуска, получаем противоречие, так как не может существовать бесконечной последовательности уменьшающихся натуральных чисел.

c) В предыдущем пункте, доказали, что если – решение, то и – решение. Будем считать, что все решения упорядочены, то есть для любого решения

Пусть Тогда из решения получается решение с большим максимальным элементом ведь Тогда для любого натурального из тройки можно получить решение где то есть решений бесконечно много.

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