Делимость нацело с остатком.

Понятие делимости – это одно из основных понятий арифметики и теории чисел. Мы будем говорить о делимости целых чисел и в частных случаях - о делимостинатуральных чисел. Итак, дадим представление о делимости на множестве целых чисел.

Делимость натуральных чисел. Деление с остатком

Определение 1. Говорят, что натуральное число a делится на натуральное число b, если существует такое натуральное число c, что выполняется равенство

a = bc.

В противном случае говорят, что число a не делится начисло b.

Если число a больше, чем число b, и не делится на число b, то число a можно разделить на число b с остатком.

Определение 2.Деление числа a на число b с остатком означает, что найдутся такие натуральные числа c и r, что выполняются соотношения

a = bc + r, r < b.

Число b называется делителем, число c – частным, а число r – остатком от деления a на b.

Еще раз особо подчеркнем, что остаток r всегда меньше, чем делитель b.

Например, число 204 не делится на число 5, но, разделив число 204 на 5 с остатком, получаем:

Таким образом, частное от деления равно 40, а остаток равен 4.

Определение 3. Числа, делящиеся на 2, называют четными, а числа, которые не делятся на 2, называют нечетными.

Признаки делимости

Для того, чтобы быстро выяснить, делится ли одно натуральное число на другое, существуют признаки делимости.

Признак делимости на	Формулировка	Пример
	Число должно оканчиваться четной цифрой: 0, 2, 4, 6, 8
	Сумма цифр числа должна делиться на 3	745, (7 + 4 + 5 = 15)
	Число, образованное двумя последними цифрами, должно делиться на 4
	Число должно оканчиваться цифрой 0 или 5
	Число должно делиться на 2 и на 3	234, (2 + 3 + 4 = 9)
	На 7 должно делиться число, полученноевычитанием удвоенной последней цифры из исходного числа с отброшенной последней цифрой	3626, (362 – 12 = 350)
	Число, образованное тремя последними цифрами, должно делиться на 8
	Сумма цифр должна делиться на 9	2574, (2 + 5 + 7 + 4 = 18)
	Число должно оканчиваться 0
	Сумма цифр, стоящих на четных местах, либо равна сумме цифр, стоящих на нечетных местах, либо отличается от нее на число, делящееся на 11	1408, (4 + 8 = 12; 1 + 0 = 1; 12 – 1 = 11)
	На 13 должно делиться число, полученноедобавлением учетверенной последней цифры к исходному числу с отброшенной последней цифрой	299, (29 + 36 = 65)
	Число должно оканчиваться на 00, 25, 50 или 75
	Число должно оканчиваться на 00 или 50
	Число должно оканчиваться на 00
	Число должно оканчиваться на 000

 

 

Свойства делимости

Делимость обладает рядом характерных свойств. Перечислим и обоснуем основные свойства делимости, которые следуют из понятия делимости и свойств операций над целыми числами.

1. Любое целое число a делится на число a, на число −a, противоположное числу a, на единицу и на число −1.

Докажем это свойство делимости.

Для любого целого числа a справедливы равенства a=a·1 и a=1·a, из которых следует, что a делится на a, причем частное равно единице, и что a делится на 1, причем частное равно a. Для любого целого числа a также справедливы равенства a=(−a)·(−1) и a=(−1)·(−a), из которых следует делимость a на число, противоположное числу a, а также делимость a на минус единицу.

Отметим, что свойство делимости целого числа a на себя называют свойством рефлексивности.

2. Следующее свойство делимости утверждает, что нуль делится на любое целое число b.

Действительно, так как 0=b·0 для любого целого числа b, то нуль делится на любое целое число.

В частности, нуль делится и на нуль. Это подтверждает равенство 0=0·q, где q – любое целое число. Из этого равенства вытекает, что частным от деления нуля на нуль является любое целое число.

Также нужно отметить, что на 0 не делится никакое другое целое число a, отличное нуля. Поясним это. Если бы нуль делил целое число a, отличное от нуля, то должно было бы быть справедливо равенство a=0·q, где q – некоторое целое число, а последнее равенство возможно только при a=0.

3. Если целое число a делится на целое число b и модуль числа a меньше модуля числа b, то a равно нулю. В буквенном виде это свойство делимости записывается так: если a b и , то a=0.

Доказательство.

Так как a делится на b, то существует целое число q, при котором верно равенство a=b·q. Тогда должно быть справедливо и равенство , а в силу свойств модуля числа должно быть справедливо и равенство вида . Если q не равно нулю, то , откуда следует, что . Учитывая полученное неравенство, из равенства следует, что . Но это противоречит условию . Таким образом, q может быть равно только нулю, при этом получим a=b·q=b·0=0, что и требовалось доказать.

4. Если целое число a отлично от нуля и делится на целое число b, то модуль числа a не меньше модуля числа b. То есть, если a≠0 и a b, то . Это свойство делимости непосредственно вытекает из предыдущего.

5. Делителями единицы являются только целые числа 1 и −1.

Во-первых, покажем, что единица делится на 1 и на −1. Это следует из равенств 1=1·1 и 1=(−1)·(−1).

Осталось доказать, что никакое другое целое число не является делителем единицы.

Предположим, что целое число b, отличное от 1 и −1, является делителем единицы. Так как единица делится на b, то в силу предыдущего свойства делимости должно выполняться неравенство , которое равносильно неравенству . Этому неравенству удовлетворяют только три целых числа: 1, 0, и −1. Так как мы приняли, что b отлично от 1 и −1, то остается лишь b=0. Но b=0 не может быть делителем единицы (что мы показали при описании второго свойства делимости). Этим доказано, что никакие числа, отличные от 1 и −1, не являются делителями единицы.

6. Чтобы целое число a делилось на целое число b необходимо и достаточно, чтобы модуль числа a делился на модуль числа b.

Докажем сначала необходимость.

Пусть a делится на b, тогда существует такое целое число q, что a=b·q. Тогда . Так как является целым числом, то из равенства следует делимость модуля числа a на модуль числа b.

Теперь достаточность.

Пусть модуль числа a делится на модуль числа b, тогда существует такое целое число q, что . Если числа a и b положительные, то справедливо равенство a=b·q, которое доказывает делимость a на b. Если a и b отрицательные, то верно равенство −a=(−b)·q, которое можно переписать как a=b·q. Если a – отрицательное число, а b – положительное, то имеем −a=b·q, это равенство равносильно равенству a=b·(−q). Если a – положительное, а b – отрицательное, то имеем a=(−b)·q, и a=b·(−q). Так как и q и −q являются целыми числами, то полученные равенства доказывают, что a делится на b.

Следствие 1.

Если целое число a делится на целое число b, то a также делится на число −b, противоположное числу b.

Следствие 2.

Если целое число a делится на целое число b, то и −a делится на b.

Важность только что рассмотренного свойства делимости сложно переоценить - теорию делимости можно описывать на множестве целых положительных чисел, а это свойства делимости распространяет ее и на целые отрицательные числа.

7. Делимость обладает свойством транзитивности: если целое число a делится на некоторое целое число m, а число m в свою очередь делится на некоторое целое число b, то a делится на b. То есть, если a m и m b, то a b.

Приведем доказательство этого свойства делимости.

Так как a делится на m, то существует некоторое целое число a₁ такое, что a=m·a₁. Аналогично, так как m делится на b, то существует некоторое целое число m₁ такое, что m=b·m₁. Тогда a=m·a₁=(b·m₁)·a₁=b·(m₁·a₁). Так как произведение двух целых чисел является целым числом, то m₁·a₁ - это некоторое целое число. Обозначив его q, приходим к равенству a=b·q, которое доказывает рассматриваемое свойство делимости.

8. Делимость обладает свойством антисимметричности, то есть, если a делится на b и одновременно b делится на a, то равны либо целые числа a и b, либо числа a и −b.

Из делимости a на b и b на a можно говорить о существовании целых чисел q₁ и q₂ таких, что a=b·q₁ и b=a·q₂. Подставив во второе равенство b·q₁ вместо a, или подставив в первое равенство a·q₂ вместо b, получим, что q₁·q₂=1, а учитывая, что q₁ и q₂ – целые, это возможно лишь при q₁=q₂=1 или при q₁=q₂=−1. Отсюда следует, что a=b или a=−b (или, что то же самое, b=a или b=−a).

9. Для любого целого и отличного от нуля числа b найдется такое целое число a, не равное b, которое делится на b.

Таким числом будет любое из чисел a=b·q, где q – любое целое число, не равное единице. Можно переходить к следующему свойству делимости.

10. Если каждое из двух целых слагаемых a и b делится на целое число c, то сумма a+b также делится на c.

Так как a и b делятся на c, то можно записать a=c··q₁ и b=c·q₂. Тогда a+b=c·q₁+c·q₂=c·(q₁+q₂) (последний переход возможен в силураспределительного свойства умножения целых чисел относительно сложения). Так как сумма двух целых чисел является целым числом, то равенство a+b=c·(q₁+q₂) доказывает делимость суммы a+b на c.

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

Если еще вспомнить, что вычитание из целого числа a целого числа b представляет собой сложение числа a с числом −b (смотрите правило вычитания целых чисел), то данное свойство делимости справедливо и для разности чисел. Например, если целые числа a и b делятся на c, то разность a−b также делится на с.

11. Если известно, что в равенстве вида k+l+…+n=p+q+…+s все члены, кроме какого-то одного, делятся на некоторое целое число b, то и этот один член делится на b.

Допустим, этим членом является p (мы можем взять любой из членов равенства, что не повлияет на рассуждения). Тогда p=k+l+…+n−q−…−s. Выражение, получившееся в правой части равенства, делится на b в силу предыдущего свойства. Следовательно, число p также делится на b.

12. Если целое число a делится на целое число b, то произведение a·k, где k – произвольное целое число, делится на b.

Так как a делится на b, то справедливо равенство a=b·q, где q – некоторое целое число. Тогда a·k=(b·q)·k=b·(q·k) (последний переход осуществлен в силу сочетательного свойства умножения целых чисел). Так как произведение двух целых чисел есть целое число, то равенство a·k=b·(q·k) доказывает делимость произведения a·k на b.

Следствие: если целое число a делится на целое число b, то произведение a·k₁·k₂·…·k_n, где k₁, k₂, …, k_n – некоторые целые числа, делится на b.

13. Если целые числа a и b делятся на c, то сумма произведений a·u и b·v вида a·u+b·v, где u и v – произвольные целые числа, делится на c.

Доказательство этого свойства делимости аналогично двум предыдущим. Из условия имеем a=c·q₁ и b=c·q₂. Тогда a·u+b·v=(c·q₁)·u+(c·q₂)·v=c·(q₁·u+q₂·v). Так как сумма q₁·u+q₂·v является целым числом, то равенство вида a·u+b·v=c·(q₁·u+q₂·v) доказывает, что a·u+b·v делится на c.