Дискретно-непрерывная математика (стр. 25 )

(1)

в которой при любом п. По рефлексивности и транзитнвности отношения отсюда следует, что тогда и только тогда, когда i ≥ j. Нам остается показать, что последовательность (1) охватывает все рассматриваемые нами объекты. Это достигается довольно тонким рассуждением по индукции. Предположим, что b0 не принадлежит последовательности (1). Получение этого b0 будем считать первым шагом нашего индуктивного рассуждения. Пусть п его шагов уже проведены, в результате чего нами получен некоторый элемент bn-1.

Если bn-1 =а0, то наш процесс будем считать законченным; если же bn-1 ≠а0, то элемент bn-1 имеет непосредственно предшествующий, который мы и возьмем в качестве bn. В результате мы получаем последовательность различных элементов

На основании 4е эта последовательность должна иметь по­следний член. Но по самому принципу построения этой последо­вательности ее последним членом может быть только а0. Пусть для определенности bn = а0.

Нетрудно проверить, что если некоторое а непосредственно предшествует b, то b непосредственно следует за а. Значит,

Последнее означает, что а0 принадлежит последовательности (1), но это противоречит предположенному. Следовательно, по­следовательность (1) содержит все рассматриваемые нами объекты.

11. Пусть а — некоторое число. Всякую последовательность различных чисел для которых

(2)

где ап минимально в смысле упорядочения , назовем цепью предшественников а0. Число п называется длиной этой цепи. Покажем сначала, что при тех условиях, которые мы наложили на упорядочение , каждое конкретное число не может иметь сколь угодно длинных цепей предшественников. В самом деле, пусть а — некоторое число, а b1, b2,.....,bk — непосредственно предшествующие ему числа. Если а1 не предшествует а0 непосредственно, мы можем на основании 9° вставить в цепь (2) некоторое непосредственно предшествующее а число. Поэтому если имеются сколь угодно длинные цепи предшественников а, должны найтись и такие его сколь угодно длинные цепи предшественников, которые начина­ются с чисел, непосредственно предшествующих а. Будем далее рассматривать только такие цепи.

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

Значит, при нашем предположении хотя бы одно из чисел, непосредственно предшествующих а0, имеет сколь угодно длинные цепи предшественников. Обозначим это число через а1 и повторим в применении к нему все только что проведенные рас-суждечия. Это даст нам некоторое число а2, непосредственно редшествующее а1 и имеющее сколь угодно длинные цепи пред­шественников. Повторяя этот процесс, мы приходим к последо­вательности

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

Следовательно, для каждого числа а среди его цепей предшественников можно выбрать самую длинную. Обозначим ее длину через п(а). Если b непосредственно предшествует а, то очевидно, п(b)=п(а)—1, а для всех минимальных а п(а)=0.

Пусть, наконец, А(а) — высказывание, зависящее от а. Обо­значим через В(п) высказывание «А(а) верно для всех чисел а, для которых п(а) = п». Тогда, как легко видеть, формулировка принципа индукции в новой форме для утверждений А(а) совпадает с формулировкой этого принципа в старой форме для утверждений В(п).

12. Каковы бы ни были четные числа а и b, существуют такие четные числа q и r, что

Такие числа q и r единственны.

Доказательство. Разделим а на 2b с остатком обыч­ным образом:

(3)

При этом числа q и r определяются однозначно. Из четности а и 2bq следует четность их разности, т. е. числа r. Нам остается, положив 2q = q', переписать (3) в виде

и заметить, что оба числа q' и r четные и определяются един­ственным образом.

13. Пусть р — наименьший простой делитель числа а. Отсюда следует, что а = pb. Всякий простой делитель q числа b является вместе с тем и делителем а. Поэтому q ≥ р, значит, и b ≥ р, так что

а ≥ р2 и, наконец,

14. Пусть p1, р2, ..., рk — полный список всех простых чисел, входящих хотя бы в одно из канонических разложений а и b. Положим

(Если а не делится на pi, то αi = 0; если b не делится на pi, то βi = 0.) Пусть γi — наибольшее из чисел αi и βi для i== 1, 2, ..., k, а δi — наименьшее из них.

Тогда, на основании теоремы 17, наибольший об­щий делитель а и b есть а их наимень­шее общее кратное —

15. Как следует из теоремы 17, каждый делитель числа а с каноническим разложением должен иметь вид

где β1 принимает α1 + 1 значений: 0, 1, 2, ..., α1, β2 принимает α2 + 1 значений и т. д. Так как любые комбинации этих значений возможны и дают нам все делители а, причем; каждый по одному разу (если бы какой-нибудь делитель повто­рился несколько раз, то это означало бы наличие у него не­скольких канонических разложений), число делителей а равно

(4)

16. Пусть каноническое разложение а есть Очевидно, можно положить

Далее, согласно (4), мы имеем

Отсюда Таким образом, α=26∙3=192.

17. Мы имеем

так что есть разложение числа 81 на два множителя. Так как нумерация простых делителей а зависит от нас, ограничимся рассмотрением следующих возможностей:

В первом из этих случаев α1 = 0, что противоречит предпо­ложенной положительности числа α1. Оставшиеся случаи дают нам

Значит, либо

либо

18. Пусть — каноническое разложение числа а.

Условие задачи дает нам

или

(5)

Заметим, что