Категория: Теория чисел Добавил: Admin Дата публикации: 08.08.2014
1083
0

Деление с остатком

Ключевые слова: теория чисел, примеры решений задач, лекции, ділення з остачею.

Определение. Пусть 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 .

 




avatar