Какими свойствами обладает отношение быть делителем на множестве натуральных чисел

Пусть даны натуральные числа a и b. Говорят, что число a делится на число b, если существует такое натуральное число q, что   a = bq.

В этом случае число b называют делителем числа а, а число а – кратным числа b.

Например, 24 делится на 8, так как существует такое q = 3, что 24 = 8*3. Можно сказать иначе: 8 – это делитель числа 24, а 24 есть кратное числа 8.

В случае, когда а делится на b, пишут: . Эту запись часто читают и так: «а кратно b».

Заметим, что понятие «делитель данного число» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 – делитель, но 5 не является делителем числа 18. Если 18 делят на 6, то в случае понятия «делитель» и «делитель данного числа» совпадают.

Из определения отношения делимости и равенства а = 1*а, справедливого для любого натурального а, вытекает, 1 является делителем любого натурального числа.

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

Теорема. Делитель b данного числа а не превышает этого числа. Если , то .

Доказательство. Так как , то существует такое , что a = bq, значит, a – b = bq – b = b*(q – 1). Поскольку , то . Тогда  и, следовательно, .

Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. Они образуют конечное множество {1, 2, 3, 4, 6, 9, 12, 18, 36}.

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

Нам известно, что отношение делимости на множестве N обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно. Теперь, имея определение отношения делимости, мы можем доказать эти и другие его свойства.

Теорема. Отношение делимости рефлексивно, т.е. любое нату­ральное число делится само на себя.

Доказательство. Для любого натурального а справедливо ра­венство . Так как 1 е N, то, по определению отношения дели­мости, .

Теорема. Отношение делимости антисимметрично, т.е. если  и , то .

Доказательство. Предположим противное, т. е. что . Но тог­да , согласно теореме, рассмотренной выше.

По условию  и . Тогда, по той же теореме,.

Неравенства  и  будут справедливы лишь тогда, когда , что противоречит условию теоремы. Следовательно, наше предпо­ложение неверное и теорема доказана.

Теорема. Отношение делимости транзитивно, т.е. если  и , то .

Доказательство. Так как, то существует такое натуральное число q, что а = bq, а так как ,то существует такое натуральное число p, что . Но тогда имеем: . Число pq – натуральное. Значит, по определению отношения делимости,.

Теорема (признак делимости суммы). Если каждое из натураль­ных чисел а1, а2 …, ап делится на натуральное число b, то и их сумма а1 + а2 + … + ап делится на это число.

Доказательство. Так как , то существует такое натураль­ное число  что . Так как , то существует такое нату­ральное число ,что . Продолжая рассуждения, получим, что если , то существует такое натуральное число , что . Эти равенства позволяют преобразовать сумму а1 + а2 + … + ап в сумму вида bq1 + bq2 + … + bqn. Вынесем за скобки общий множитель b, а получившееся в скобках натуральное число q1 + q2 + … + qn обозначим буквой q. Тогда а1 + а2 + … + ап = b(q1 + q2 + … + qn) = bq , т.е. сумма а1 + а2 + … + ап оказалась представленной в виде произведения числа b и некоторого натурального числа q. А это значит, что сумма а1 + а2 + … + ап  делится на b, что и требовалось доказать.

Например, не производя вычислений, можно сказать, что сумма 175 + 360 + 915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.

Теорема (признак делимости разности). Если  числа а1 и а2 делятся на b и , то их разность делится на b.

Доказательство этой теоремы аналогично доказательству призна­ка делимости суммы.

Теорема  (признак делимости произведения). Если число а де­лится на b, то произведение вида ах, где xÎ N, делится на b.

Доказательство. Так как ,то существует такое натураль­ное число q, что . Умножим обе части этого равенства на нату­ральное число х. Тогда ах = (bq)x, откуда на основании свойства ассоциативности умножения (bq)x = b(qx) и, значит, ах = b(qx), где qx –  натуральное число. Согласно определению отношения делимости, , что и требовалось доказать.

Из доказанной теоремы следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b.

Например, произведение 24

Лекция 44. Делимость целых неотрицательных чисел

ДЕЛИМОСТЬ НАТУРАЛЬНЫХ ЧИСЕЛ

План:

1. Отношение делимости на множестве неотрицательных чисел.

2. Свойства отношения делимости.

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

Как известно, вычитание и деление на множестве нату­ральных чисел выполнимо не всегда. Вопрос о существовании разности натуральных чисел а и b решается просто – доста­точно установить (по записи чисел), что b < а. Для деления такого общего и простого признака нет. Поэтому в математической науке с давних пор пытались найти такие правила, которые позволили бы по записи числа а узнавать, делится оно на число b или нет, не выполняя непосредственного деле­ния а на b. В результате этих поисков были открыты не толь­ко некоторые признаки делимости, но и другие важные свой­ства чисел; познакомимся с некоторыми из них.

В начальных курсах математики Делимость натуральных чисел, как правило, не изучается, но многие факты из этого раздела математики неявно используются. Например, признак делимости суммы, разности и произведения на число тесно связаны с правилами деления суммы, разности и произведения на число, изучаемыми в начальных классах. В ряде курсов изучаются признаки делимости чисел на 2,3,5 и другие.

Вообще знания о делимости натуральных чисел расширя­ют представления о множестве натуральных чисел, позволяют глубже усвоить материал, связанный с делением натуральных чисел, применять полученные ранее знания о способах дока­зательства, о свойствах отношений и др.

Определение. Пусть даны натуральные числа а и b. Гово­рят, что число а делится на число b, если существует та­кое натуральное число q, что a = bq.

В этом случае число b называют делителем числаа, а число а – кратным числаb.

Например, 24 делится на 8, так как существует такое q =3, что 24 = 8·3. Можно сказать иначе: 8 – это делитель числа 24, а 24 есть кратное числа 8. В том случае, когда а делится на b, пишут: а :. b. Эту запись »« читают и так: «а кратно b». Заметим, что понятие «делитель данного числа» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 -делитель, но 5 не является делителем числа 18. Если 18 делят 6, то в этом случае понятия «делитель» и «делитель данного числа» совпадают.

Из определения отношения делимости и равенства а = 1·а, справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.

Выясним, сколько вообще делителей может быть у натурального числа а. Сначала рассмотрим следующую теорему.

Теорема1. Делитель b данного числа а не превышает этого числа, т.е. если

а :. b, то b < а.

Доказательство. Так как а:. b, то существует такое q Є N,что a = bq u, значит, a-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}.

В зависимости от числа делителей среди натуральных чисел различают простые и составные числа.

Определение. Простым числом называется такое нату­ральное число, которое имеет только два делителя – единицу и само это число.

Например, число 13- простое, поскольку, у него только два делителя: 1 и 13.

Определение. Составным числом называется такое нату­ральное число, которое имеет более двух делителей.

Так число 4 составное, у него три делителя: 1,2 и 4.

Число 1 не является ни простым, ни составным числом в связи с тем, что оно имеет только один делитель.

Чисел, кратных данному числу, можно назвать как угодно много, – их бесконечное множество. Так, числа, кратные 4, образуют бесконечный ряд: 4, 8, 12, 16, 20, 24, …, и все они могут быть получены по формуле а = 4q, где q принимает значения 1, 2, 3,….

Нам известно, что отношение делимости обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно. Теперь, имея определение отношения делимо­сти, мы можем доказать эти и другие его свойства.

Теорема 2. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя.

Доказательство. Для любого натурального а справед­ливо равенство а = а·1. Так как 1 Є N, то, по определению отношения делимости, а :. а.

Теорема3. Отношение делимости антисимметрично, т.е. если а :. b и а ≠ b,

то b ⁞͞ a.

Доказательство. Предположим противное, т.е. что b⁞a. Но тогда а ≤ b, согласно теореме, рассмотренной выше.

По условию и а ⁞. b и а ≠ b. Тогда, по той же теореме, b ≤ а.

Неравенства а ≤ b и b ≤ а будут справедливы лишь тогда, когда а = b, что противоречит условию теоремы. Следова­тельно, наше предположение неверное и теорема доказана.

Теорема 4. Отношение делимости транзитивно, т.е. если а⁞ b и b⁞ с, то а⁞ с.

Доказательство. Так как а:. b, то существует такое нату­ральное число q, что a = bq, а так как b⁞ с, то существует такое натуральное число р, что b = ср. Но тогда имеем: a = bq = (cp)q = c(pq)- Число pq – натуральное. Значит, по определе­нию отношения делимости,

а⁞ с.

Теорема5 (признак делимости суммы). Если каждое из натуральных чисел а1, а2, …,ап делится на натуральное число b, то и их сумма a1 + а2 + … + аn делится на это число.

Доказательство. Так как а1 ⁞ b, то существует такое на­туральное число q1, что а1 =bq1. Так как а2 ⁞ b, то существует такое натуральное число q2, что а2 = bq2. Продолжая рассуж­дения, получим, что если аn:. b, то существует такое натуральное число qn, что ап = bqn. Эти равенства позволяют преобразовать сумму а1 + а2 + … +ап в сумму вида bq1 + bq2 + … + bqn. Вынесем за скобки общий множитель b, а получившееся в скобках натуральное число q1 + q2 + … + qn обозначим буквой q. Тогда a1 + a2 + … + an = b(q1 + q2+… + qn) = bq, т.е. сумма а1 + а2 +… + ап оказалась представленной в виде произведения числа b и некоторого натурального числа q. А это значит, что сумма а1 + а2 +… + ап делится на b, что и требовалось доказать.

Например, не производя вычислений, можно сказать, что 175 + 360 + 915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.

Теорема 6 (признак делимости разности). Если числа а1 и а2 делятся на b и а1≥ а2 , то их разность а1 – а2 делится на b.

Доказательство этой теоремы аналогично доказательству признака делимости суммы.

Теорема 7 (признак делимости произведения). Если число а делится на b, то произведениe вида ах, где х Є N, делитcя на b.

Доказательство. Так как а:. b, то существует такое натуральное число q, что a= bq. Умножим обе части этого равенства на натуральное число х. Тогда ах=(bq)x, откуда на основании свойства ассоциативности умножения (bq)x = b(qx)и, значит, ax = b(qx), где qx – натуральное число. Согласно определению отношения делимости, ax :. b, что и требовалось доказать.

Из доказанной теоремы следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b. Например, произведение 24·976·305 делится на 12, так как на 12 делится множитель 24.

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

Теорема 8. Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b, то вся cумма на число b не делится.

Доказательство. Пусть s = а1+ аг + … + ап +” с и известно, что а1 :. B, а2 :. B,

___ ___

а3 :. b, … аn:. b, но с :. b. Докажем, что тогда s :. b

Предположим противное, т.е. Пусть s :. b. Преобразуем сумму s к виду с = s— (а1 + а2 +… + аn). Так как s :. b по предположению, (а1 + а2 +… + аn):. b согласно признаку делимости суммы, то по теореме делимости разности с :.b

____

Пришли к противоречию с тем, что дано. Следовательно, s :. b.

Например, сумма 34 + 125 + 376 + 1024 на 2 не делится, так 34:.2,376:.2,124:.2, но 125 не делится на 2.

Теорема 9. Если в произведении ab множитель a делится на натуральное число т, а множитель b делится на натуральное число n,то ab делится на mn.

Справедливость этого утверждения вытекает из теоремы о делимости произведения.

Теорема 10.Если произведение ас делится на произведе­ние bс, причем с – натуральное число, то и а делится на b.

Доказательство. Так как ас делится на bc, то существует такое натуральное число q, что ас = (bc)q, откуда ас = (bq)c и, следовательно, а = bq, т.е. а:.b.

Упражнения

1.Объясните, почему число 15 является делителем числа 60 и не является делителем числа 70.

2.Постройте граф отношения «быть делителем данного числа», заданного на множестве Х = {2, 6,. 12, 18, 24}. Как от­ражены на этом графе свойства данного отношения?

3. Известно, что число 24 – делитель числа 96, а число 96 -делитель числа 672. Докажите, что число 24 делитель числа 672, не выполняя деления.

4. Запишите множество делителей числа.

а) 24; 6)13; в) 1.

5.На множестве X ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11; 12} задано отношение «иметь одно и то же число делителей». Является ли оно отношением эквивалентности?

6.Постройте умозаключение, доказывающее, что:

а) число 19 является простым;

б) число 22 является составным.

7.Докажите или опровергните следующие утверждения:

а) Если сумма двух слагаемых делится на некоторое число, то и каждое слагаемое делится на это число.

б) Если одно из слагаемых суммы не делится на некоторое число, то и сумма не делится на это число.

в) Если ни одно слагаемое не делится на некоторое число, то и сумма не делится на это число.

г) Если одно из слагаемых суммы делится на некоторое число, а другое не делится на это число, то и сумма не делится на это число.

8. Верно ли, что:

а) а :. т и b :. n =>ab:.mn

___ __ ___

б) а :.п и b:.n => ab:.n;

в) ab:.n => а:.п или b:.n.