Деление с остатком
Ключевые слова: теория чисел, примеры решений задач, лекции, ділення з остачею.
Определение. Пусть a , b ∈ Z . Число а делится на число b если найдется такое число q ∈ Z , что а = qb . Синонимы: а кратно b ; b — делитель а .
Запись: b | a .
Легко заметить, что отношение делимости b | a есть бинарное отношение на множестве Z , а если ограничиться рассмотрением только натуральных чисел, то несложно установить, что на множестве N это бинарное отношение является рефлексивным, антисимметричным и транзитивным, т. е. отношением частичного порядка. Легко проверяется также следующее свойство: Пусть а1 + а2 +...+ аn = c1 + c2 +...+ ck – равенство сумм целых чисел. Если все слагаемые в этом равенстве, кроме одного, кратны b , то и оставшееся слагаемое обязано быть кратным b . Перечисленные свойства отношения делимости позволят нам доказать основную теорему первого пункта:
Теорема. Для данного целого отличного от нуля числа b , всякое целое число а единственным образом представимо в виде а = bq + r , где 0 ≤ r < | b |.
Доказательство. Ясно, что одно представление числа а равенством а = bq + r мы получим, если возьмем bq равным наибольшему кратному числа b , не превосходящему а (см. рис. 1)
Определение. Пусть a , b ∈ Z . Число а делится на число b если найдется такое число q ∈ Z , что а = qb . Синонимы: а кратно b ; b — делитель а .
Запись: b | a .
Легко заметить, что отношение делимости b | a есть бинарное отношение на множестве Z , а если ограничиться рассмотрением только натуральных чисел, то несложно установить, что на множестве N это бинарное отношение является рефлексивным, антисимметричным и транзитивным, т. е. отношением частичного порядка. Легко проверяется также следующее свойство: Пусть а1 + а2 +...+ аn = c1 + c2 +...+ ck – равенство сумм целых чисел. Если все слагаемые в этом равенстве, кроме одного, кратны b , то и оставшееся слагаемое обязано быть кратным b . Перечисленные свойства отношения делимости позволят нам доказать основную теорему первого пункта:
Теорема. Для данного целого отличного от нуля числа b , всякое целое число а единственным образом представимо в виде а = bq + r , где 0 ≤ r < | b |.
Доказательство. Ясно, что одно представление числа а равенством а = bq + r мы получим, если возьмем bq равным наибольшему кратному числа b , не превосходящему а (см. рис. 1)
Тогда, очевидно, 0 ≤ r < | b |. Докажем единственность такого представления. Ну пусть а = bq + r и а = bq1 + r1 — два таких представления. Значит 0 = а – а = b ( q – q1 ) + ( r – r1 ). Здесь 0 делится на b ; b ( q – q1 ) делится на b , следовательно ( r – r1 ) обязано делиться на b . Так как 0 ≤ r < b и 0 ≤ r1 < b , то r – r1 < b и r – r1 делится на b , значит r – r1 равно нулю, а, значит и q — q1 равно нулю, т. е. два таких представления совпадают. Сразу после доказательства теоремы, пока не забылись использовавшиеся в нем обозначения, дадим
Определение. Число q называется неполным частным, а число r — остатком от деления а на b .
Похожие материалы:
Примеры решений задач
Готовые работы