Таблицы Брадиса

Тогда Ъд0 а, Ъд0 1

Тогда Ъд0 а, Ъд0 1

Элементы математики в задачах - Г. А. Мерзон

Итак, вопрос: что будет с определением 1, если условие 2 заменить на одно из следующих условий?

162                     Целые числа 2. Алгоритм Евклида

а)  0 < г < \Ъ\

(Ответ: такое определение нам не подходит, потому что по нему не для любых двух чисел а и Ъ = 0 найдутся частное и остаток. А именно: не найдутся они для чисел, одно из которых делится на другое.)

б)  0 < г ^ \Ъ\

(Ответ: а вот такое определение вполне можно было бы принять. Оно отличается от нашего только тем, что остаток от деления одного числа на другое в случае, когда первое делится нацело на второе, равен второму числу, а не нулю.)

в) 0 ^ г< 2\Ъ\

(Ответ: если бы было такое определение, то частное и остаток были бы определены неоднозначно. Например, 7 = 2 ■ 3 +1 = 1 ■ 3 + 4. В этом случае при делении 7 на 3 мы получаем частное 2 и остаток 1 или частное 1 и остаток 4.)

г) 0 ^ г < Ъ

(Ответ: при таком определении остатка не существует для отри­цательных Ъ.)

д) -\Ъ\^г<\Ъ\

(Ответ: в этом случае у нас опять-таки частное и остаток опреде­лены неоднозначно.)

Решение. Случаи Ъ < 0 и Ъ > 0 разбираются аналогично, поэтому мы приведем решение только для случая Ъ < 0. Поскольку Ь(|а| + 1) < а < < Ь(—|а| — 1), множество целых чисел д, для которых Ъд ^ а, непусто и ограничено снизу. Рассмотрим наименьший элемент д0 этого множе­ства. Тогда Ъд0 ^ а, Ъ(д0 — 1) > а, то есть 0 ^ а — д0Ъ < —Ъ = |Ъ|. Таким образом, можно взять д0 в качестве неполного частного, а г0 = а — д0Ъ в качестве остатка.

Докажем теперь единственность частного и остатка. Пусть суще­ствует две пары (д1, /\) и (д2, г2): а = Ъдг + г1, а = Ъд2 + г2. Вычитая эти равенства, получаем Ъ(дг — д2) = г2 — г1, то есть число г2 — г1 делится на число Ъ. Но при 0 ^ г1 < |Ъ|, 0 ^ г2 < |Ъ| модуль разности г2 — г1 не