Отношение делимости и его свойства
Определение.Пусть даны натуральные числа а и b. Говорят, что число а делится на число b, если существует такое натуральное число q, что а = bq.
В этом случае число b называютделителем числа а, а число а - кратным числа b.
Например, 24 делится на 8, так как существует такое q = 3, что 24 = 8×3. Можно сказать иначе: 8 - это делитель числа 24, а 24 есть кратное числа 8.
В том случае, когда а делится на b, пишут: а M b. Эту запись часто читают и так: «а кратно b».
Заметим, что понятие «делитель данного числа» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 - делитель, но 5 не является делителем числа 18. Если 18 делят на 6, то в этом случае понятия «делитель» и «делитель данного числа» совпадают.
Из определения отношения делимости и равенства a = 1 × а, справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.
Выясним, сколько вообще делителей может быть у натурального числа а. Сначала рассмотрим следующую теорему.
Теорема 1. Делитель b данного числа а не превышает этого числа, т. е. если а M b, то b £ а.
Доказательство. Так как а M b, то существует такое qÎ N, что а = bq и, значит, а - b = bq - b = b ×(q - 1). Поскольку qÎ N, то q ³ 1. . Тогда b ×(q - 1) ³ 0 и, следовательно, и b £ а.
Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. Они образуют конечное множество {1,2,3,4,6,9, 12, 18,36}.
В зависимости от числа делителей среди натуральных чисел различают простые и составные числа.
Определение.Простым числом называется такое натуральное число, большее 1, которое имеет только два делителя - единицу и само это число.
Например, 13 – простое, поскольку у него только два делителя: 1 и 13.
Определение.Составным числом называется такое натуральное число, которое имеет более двух делителей.
Так число 4 составное, у него три делителя: 1, 2 и 4. Число 1 не является ни простым, ни составным числом в связи с тем, что оно имеет только один делитель.
Чисел, кратных данному числу, можно назвать как угодно много, -их бесконечное множество. Так, числа, кратные 4, образуют бесконечный ряд: 4, 8, 12, 16, 20, 24, .... и все они могут быть получены по формуле а = 4q, где q принимает значения 1, 2, 3,... .
Нам известно, что отношение делимости на множестве N обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно. Теперь, имея определение отношения делимости, мы можем доказать эти и другие его свойства.
Теорема 2. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя.
Доказательство. Для любого натурального а справедливо равенство а = а×1. Так как 1 Î N то, по определению отношения делимости, аMа.
Теорема 3. Отношение делимости антисимметрично, т.е. если а M b и а ¹ b, то 
.
Доказательство. Предположим противное, т. е. что bMа. Но тогда а£ b, согласно теореме, рассмотренной выше.
По условию а M b и а ¹ b. Тогда, по той же теореме, b £ а.
Неравенства а £ b и b £ а.будут справедливы лишь тогда, когда а = b, что противоречит условию теоремы. Следовательно, наше предположение неверное и теорема доказана.
Теорема 4. Отношение делимости транзитивно, т.е. если аM b и b M с, то а M с.
Доказательство. Так как а M b, то существует такое натуральное число q, что а = b q , а так как bM с, то существует такое натуральное число р, что b = ср. Но тогда имеем: а = b q = (ср)q = с(рq). Число рq - натуральное. Значит, по определению отношения делимости, а. M с.
Теорема 5 (признак делимости суммы). Если каждое из натуральных чисел а1,а2,…ап делится на натуральное число b, то и их сумма а1 + а2 +… + ап делится на это число.
Например, не производя вычислений, можно сказать, что сумма 175 + 360 +915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.
Теорема 6 (признак делимости разности). Если числа а1 и а2 делятся на b и а1 ³ а2 , то их разность а1 - а2 делится на b.
Теорема 7 (признак делимости произведения). Если число а делится на b, то произведение вида ах, где х е N. делится на b.
Из теоремы следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b.
Например, произведение 24×976×305 делится на 12, так как на 12 делится множитель 24.
Рассмотрим еще три теоремы, связанные с делимостью суммы и произведения, которые часто используются при решении задач на делимость.
Теорема 8. Если в сумме одно слагаемое не делится на числоb, а все остальные слагаемые делятся на число b, то вся сумма на число b не делится.
Например, сумма 34 + 125 + 376 + 1024 на 2 не делится, так как 34:2,376:2,124:2,но 125 не делится на 2.
Теорема 9. Если в произведении аb множитель а делится на натуральное число т, а множитель b делится на натуральное число п то а b делится на тп.
Справедливость этого утверждения вытекает из теоремы о делимости произведения.
Теорема 10. Если произведение ас делится на произведение bс, причем с - натуральное число, то и а делится на b.