Математика на cleverstudents.ru

Делимость, признаки делимости

Понятие делимости целых чисел, свойства делимости.

Материалом этой статьи начинается теория делимости целых чисел. Здесь мы введем понятие делимости и укажем принятые термины и обозначения. Это нам позволит перечислить и обосновать основные свойства делимости.

Понятие делимости

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

Целое число a делится на целое число b, которое отлично от нуля, если существует такое целое число (обозначим его q), что справедливо равенство a=b·q. В этом случае также говорят, что b делит a. При этом целое число b называется делителем числа a, целое число a называется кратным числа b (для получения более детальной информации о делителях и кратных обращайтесь к статье делители и кратные), а целое число q называют частным.

Если целое число a делится на целое число b в указанном выше смысле, то можно сказать, что a делится на b нацело. Слово «нацело» в этом случае дополнительно подчеркивает, что частное от деления целого числа a на целое число b является целым числом.

В некоторых случаях для данных целых чисел a и b не существует такого целого числа q, при котором справедливо равенство a=b·q. В таких случаях говорят, что целое число a не делится на целое число b (при этом имеется в виду, что a не делится на b нацело). Однако в этих случаях прибегают к делению целых чисел с остатком.

Разберемся с понятием делимости на примерах.

Целое отрицательное число −81 делится на целое отрицательное число −27, так как −81=(−27)·3 (равенство (−27)·3=−81 имеет место в силу правила умножения целых чисел с разными знаками). Здесь же можно сказать, что число −27 делит −81. В этом примере целое число −81 – это кратное числа −27, а число −27 – делитель числа −81.

Рассмотрим еще один пример. Целое число −16 не делится на целое число 5, так как не существует такого целого числа q, при котором справедливо равенство −16=5·q. Таким образом, число −16 не является кратным числа 5, а число 5 не является делителем числа −16.

Теперь введем обозначения, принятые для удобства описания делимости.

Тот факт, что целое число a является кратным целого числа b (a кратно b, или a делится на b), записывают с помощью символа, представляющего собой три расположенные по вертикали точки «», в виде ab. Например, запись 9729 означает, что целое положительное число 972 делится на 9.

С другой стороны, то обстоятельство, что целое число b делит целое число a, записывают с использованием символа «|», имеющего вид вертикальной черты, следующим образом: b|a. К примеру, запись 3|27 означает, что число 3 делит 27. Также можно встретить записи вида b\a (посмотрите на обыкновенную дробь a/b справа налево), которые являются лишь разновидностью записи b|a и означают то же самое (что b делит a).

Если символы делится и делит | зачеркнуть, то получим символы вида и , которые означают не делится (не является кратным, не кратно) и не делит соответственно. Приведем примеры. Запись 457 утверждает, что 45 не делится на 7 (45 не является кратным числа 7, 45 не кратно 7). Целое число −3 не делит целое число 11, кратко можно записать (−3)11.

Итак, записи ab и b|a по сути являются различными формами записи одного и того же факта - делимости целого числа a на целое число b, а записи вида ab и ba опровергают делимость a на b.

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

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

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 равно нулю. В буквенном виде это свойство делимости записывается так: если ab и , то a=0.

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

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

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

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. То есть, если am и mb, то ab.

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

   Так как 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.

На этом закончим обзор основных свойств делимости.