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

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

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

Определение 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. То есть, если a0 и 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, то существует некоторое целое число a1 такое, чтоa=m·a1. Аналогично, так как m делится на b, то существует некоторое целое число m1 такое, что m=b·m1. Тогда a=m·a1=(b·m1)·a1=b·(m1·a1). Так как произведение двух целых чисел является целым числом, то m1·a1 - это некоторое целое число. Обозначив его q, приходим к равенству a=b·q, которое доказывает рассматриваемое свойство делимости.

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

Из делимости a на b и b на a можно говорить о существовании целых чисел q1и q2 таких, что a=b·q1 и b=a·q2. Подставив во второе равенство b·q1 вместо a, или подставив в первое равенство a·q2 вместо b, получим, что q1·q2=1, а учитывая, что q1 и q2 – целые, это возможно лишь при q1=q2=1 или приq1=q2=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··q1 и b=c·q2. Тогдаa+b=c·q1+c·q2=c·(q1+q2) (последний переход возможен в силураспределительного свойства умножения целых чисел относительно сложения). Так как сумма двух целых чисел является целым числом, то равенство a+b=c·(q1+q2) доказывает делимость суммы a+b на c.

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

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

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

Допустим, этим членом является p (мы можем взять любой из членов равенства, что не повлияет на рассуждения). Тогда p=k+l+…+nq…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·k1·k2·…·kn, где k1, k2, …, kn – некоторые целые числа, делится на b.

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

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