Как уже отмечалось, натуральное число а делится нацело на натуральное число b, если существует натуральное число с, при умножении которого на b получается а:

Слово «нацело» обычно опускают – для краткости.

Если а делится на b, то говорят еще, что а кратно b. Например, число 48 кратно числу 24.

Теорема 1. Если один из множителей делится на некоторое число, то и произведение делится на это число .

Например, 15 делится на 3, значит, и 15∙11 делится на 3, потому что 15∙11=(3∙5)∙11=3∙(5∙11).

Эти рассуждения подходят и для общего случая. Пусть число а делится на с, тогда найдется такое натуральное число n, что a = n∙c. Рассмотрим произведение числа а и произвольного натурального числа b. a∙b = n∙(c∙b) =
= n∙(b∙c) = (n∙b)∙c. Отсюда, по определению, вытекает, что произведение a∙b тоже делится на с. Что и требовалось доказать.

Теорема 2. Если первое число делится на второе, а второе делится на третье, то первое число делится на третье .

Например, 777 делится на 111, потому что 777=7∙111, а 111 делится на 3, потому что 111 = 3∙37. Из этого следует, что 777 делится на 3, так как 777 = 3∙(37∙7).

В общем случае эти рассуждения можно повторить почти дословно. Пусть число а делится на число b, а число b делится на число с. Это означает, что найдутся такие натуральные числа n и m, что a = n∙b и b = m∙c. Тогда число а можно представить в виде: а = n∙b = n∙(m∙c) = (n∙m)∙c. Равенство а = (n∙m)∙c означает, что число а тоже делится на с.

Теорема 3. Если каждое из двух чисел делится на некоторое число, то их сумма и разность делятся на это число .

Например, 100 делится на 4, потому что 100=25∙4; 36 тоже делится на 4, потому что 36 = 9∙4. Из этого следует, что 136 делится на 4, потому что

136 = 100+ 36 = 25∙4+ 9∙4 = (25+ 9)∙4 = 34∙4.

Можно также заключить, что число 64 делится на 4, потому что

64 = 100 – 36 = 25∙4 – 9∙4 =(25 – 9)∙4= 16∙4.

Докажем теорему в общем случае. Пусть каждое из чисел а и b делится на число с. Тогда, по определению, найдутся такие натуральные числа n и m, что
а = n∙c и b = m∙c. Рассмотрим сумму чисел а и b.

a + b = n∙c + m∙c = (n + m)∙c.

Отсюда следует, что а + b делится на с.

Аналогично, а – b = n∙c – m∙c = (n – m)∙c. Следовательно, а – b делится на с.

Теорема 4. Если одно из двух чисел делится на некоторое число, а другое на него не делится, то их сумма и разность не делятся на это число .

Например, 148 делится на 37, потому что 148 = 4∙37, а 11 не делится на 37. Очевидно, что сумма 148 + 11 и разность 148 – 11 не делятся на 37, иначе это противоречило бы свойству 3.

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

Если число оканчивается цифрой 0, то оно делится на 10 .

Например, число 4560 оканчивается цифрой 0, его можно представить в виде произведения 456∙10, которое делится на 10 (по теореме 1).

Число 4561 не делится на 10, потому что 4561 = 4560+1 – сумма числа 4560, делящегося на 10, и числа 1, не делящегося на 10 (по теореме 4).

Если число оканчивается одной из цифр 0 или 5, то оно делится на 5 .

Например, число 2300 делится на 5, потому что это число делится на 10, а 10 делится на 5 (по теореме 2).

Число 2305 оканчивается цифрой 5, оно делится на 5, так как его можно записать в виде суммы чисел, делящихся на 5: 2300 + 5 (по теореме 3).

Число 52 не делится на 5, потому что 52 = 50 + 2 – сумма числа 50, делящегося на 5, и числа 2, не делящегося на 5 (по теореме 4).

Если число оканчивается одной из цифр 0, 2, 4, 6, 8, то оно делится на 2.

Например, число 130 оканчивается цифрой 0, оно делится на 10, а 10 делится на 2, следовательно, 130 делится на 2.

Число 136 оканчивается цифрой 6, оно делится на 2, так как его можно записать в виде суммы чисел, делящихся на 2: 130 + 6 (по теореме 3).

Число 137 не делится на 2, потому что 137 = 130 + 7 – сумма числа 130, делящегося на 2, и числа 7, не делящегося на 2 (по теореме 4).

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

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

Например, числа 152 и 790 – четные, а числа 111 и 293 – нечетные.

Если сумма цифр числа делится на 9, то и само число делится на 9 .

Например, сумма цифр 7 + 2 + 4 + 5 = 18 числа 7245 делится на 9. Число 7245 делится на 9, потому что его можно представить в виде суммы 7∙1000 +
+ 2∙100 + 4∙10 + 5 = 7 (999 + 1) + 2∙(99 + 1) + + 4∙(9 + 1) + 5 = (7∙999 + 2∙99 +
+ 4∙9) + (7 + 2 + 4 + 5), где сумма в первых скобках делится на 9, а во вторых скобках – сумма цифр данного числа – также делится на 9 (по теореме 3).

Число 375 не делится на 9, так как сумма его цифр 3 + 7 + 5=15 не делится на 9 Это можно доказать следующим образом: 375 = 3∙(99 + 1) + 7∙(9+1) + 5 =
+ (3∙99 + 7∙9) + (3 + 7 + 5), где сумма в первых скобках делится на 9, а во вторых скобках – сумма цифр числа 375 – не делится на 9 (по теореме 4).

Если сумма цифр числа делится на 3, то и само число делится на 3 .

Например, у числа 375 сумма цифр 3 + 7 + 5=15 делится на 3, и оно само делится на 3 потому, что 375 = (3∙99 + 7∙9) + (3 + 7 + 5), где сумма в первых скобках делится на 3, а во вторых скобках – сумма цифр числа 375 – также делится на 3.

Сумма цифр числа 679, равная 6 + 7 + 9 = 22, не делится на 3, и само число не делится на 3, потому что 679 = (6∙99 + 7∙9) + (6 + 7 + 9), где сумма в первых скобках делится на 3, а во вторых скобках – сумма цифр числа 679 – не делится на 3.

Примечание . Когда говорят «число оканчивается цифрой...» имеют в виду «десятичная запись числа заканчивается цифрой...»

Простые и составные числа

Каждое натуральное число р делится на 1 и само на себя:

р:1=р, р:р=1.

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

Вот первые десять простых чисел:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Непростые натуральные числа, большие единицы, называют составными . Каждое составное число делится на 1, само на себя и еще хотя бы на одно натуральное число.

Вот все составные числа, меньшие 20:

4, 6, 8, 9, 10, 12, 14, 15, 16, 18.

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

Простых чисел бесконечно много, есть первое число – 2, но нет последнего простого числа.

Делители натурального числа

Если натуральное число а делится на натуральное число b, то число b называют делителем числа а.

Например, делителями числа 13 являются числа 1 и 13, делителями числа 4 – числа 1, 2, 4, а делителями числа 12 – числа 1, 2, 3, 4, 6, 12.

Каждое простое число имеет только два делителя – единицу и само себя, а каждое составное число, кроме единицы и себя, имеет и другие делители.

Если делитель – простое число, то его называют простым делителем. Например, число 13 имеет простой делитель 13, число 4 – простой делитель 2, а число 12 – простые делители 2 и 3.

Каждое составное число можно представить в виде произведения его простых делителей. Например,

28 = 2∙2∙7 = 2 2 ∙7;

81 = 3∙3∙3∙3 = З 4 ;

100 = 2∙2∙5∙5 = 2 2 ∙5 2 .

Правые части полученных равенств называют разложением на простые множители чисел 28, 22, 81 и 100.

Разложить данное составное число на простые множители – значит представить его в виде произведения различных его простых делителей или их степеней.

Покажем, как можно разложить число 90 на простые множители.

1) 90 делится на 2, 90:2 = 45;

2) 45 не делится на 2, но делится на 3, 45:3= 15;

3) 15 делится на 3, 15:3 = 5;

4) 5 делится на 5, 5:5 = 1.

Таким образом, 90 = 2∙45 = 2∙3∙15 = 2∙3∙3∙5.

Наибольший общий делитель

Число 12 имеет делители 1, 2, 3, 4, 12. Число 54 имеет делители 1, 2, 3, 6, 9, 18, 27, 54. Мы видим, что числа 12 и 54 имеют общие делители 1, 2, 3, 6.

Наибольшим общим делителем чисел 12 и 54 является число 6.

Наибольший общий делитель чисел а и b обозначают: НОД (а, b).

Например, НОД (12, 54) = 6.

Наименьшее общее кратное

Число, делящееся на 12, называется кратным числу 12. Числу 12 кратны числа 12, 24, 36, 48, 60, 72, 84, 96, 108 и т.д. Числу 18 кратны числа 18, 36, 54, 72, 90, 108, 126 и т. д.

Мы видим, что имеются числа, кратные одновременно 12 и 18. Например, 36, 72, 108, ... . Эти числа называются общими кратными чисел 12 и 18.

Наименьшим общим кратным натуральных чисел а и b называют наименьшее натуральное число, делящееся нацело на а и b. Это число обозначают: НОК (а, b).

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

Найдем НОК(18, 24).

I способ. Будем выписывать числа, кратные 24 (большему из данных чисел), проверяя, делится ли каждое из них на 18: 24∙1=24 – не делится на 18, 24∙2 = 48 – не делится на 18, 24∙3 = 72 – делится на 18, поэтому НОК (24, 18) =
= 72.

II способ. Разложим числа 24 и 18 на простые множители: 24 = 2∙2∙2∙3,
18 = 2∙3∙3.

НОК(24, 18) должно делиться и на 24, и на 18. Поэтому искомое число содержит все простые делители большего числа 24 (т. е. числа 2, 2, 2, 3) и еще недостающие множители из разложения меньшего числа 18 (еще одно число 3). Поэтому НОК(18, 24) = 2∙2∙2∙3∙3 = 72.

Так как взаимно простые числа не имеют общих простых делителей, то их наименьшее общее кратное равно произведению этих чисел. Например, 24 и 25 – взаимно простые числа. Поэтому НОК (24, 25) = 24∙25 = 600.

Если одно из двух чисел делится нацело на другое, то наименьшее общее кратное этих чисел равно большему из них. Например, 120 делится нацело на 24, следовательно, НОК (120, 24)= 120.

Целые числа

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

В этой разделе будут введены новые числа – целые отрицательные .

Целые отрицательные числа

Базовый пример из жизни – термометр. Предположим, он показывает температуру 7° тепла. Если температура понизится на 4°, то термометр будет показывать 3° тепла. Уменьшению температуры соответствует действие вычитания: 7 – 4 = 3. Если температура понизится на 7°, то термометр покажет 0°: 7 – 7 = 0.

Если же температура понизится на 8°, то термометр покажет –1° (1° мороза). Но результат вычитания 7 – 8 нельзя записать с помощью натуральных чисел и нуля, хотя он имеет реальный смысл.

Отсчитать в ряду неотрицательных целых чисел от числа 7 влево 8 чисел нельзя. Чтобы действие 7 – 8 стало выполнимым, расширим ряд неотрицательных целых чисел. Для этого влево от нуля запишем (справа налево) по порядку все натуральные числа, добавляя к каждому из них знак «–», показывающий, что это число стоит слева от нуля.

Записи –1, –2, –3, ... читают «минус 1», «минус 2», «минус 3» и т. д.:

–5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5, ... .

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

Справа от числа 0 в этом ряду расположены числа, которые называют натуральными или целыми положительными.

Если первое число делится на второе, а второе на третье, то первое число делится на третье.

Например, дано три числа 777, 111 и 3. Число 777 делится на 111, а 111 делится на 3, значит 777 также делится на 3:

Делимость суммы и разности

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

Например, дано два числа: 27 и 12. Число 27 делится на 3, и 12 делится на 3. Из этого следует, что сумма 27 и 12 и разность 27 и 12 делятся на 3:

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

Например, дано два числа: 64 и 10. Число 64 делится на 8, а 10 не делится на 8, значит сумма 64 и 10 и разность 64 и 10 не делятся на 8:

10: 8 = 1 (остаток 2)

74: 8 = 9 (остаток 2)

54: 8 = 6 (остаток 6)

Делимость произведения

Если один из множителей делится на некоторое число, то и произведение делится на это число.

Например, дано два числа: 8 и 9. Число 8 делится на 4, значит и произведение 8 и 9 делится на 4.

Лекция 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, то и их сумма a 1 + а 2 + ... + а n делится на это число.

Доказательство. Так как а 1 ⁞ b, то существует такое на­туральное число q 1 , что а 1 =bq 1 . Так как а 2 ⁞ b, то существует такое натуральное число q 2 , что а 2 = bq 2 . Продолжая рассуж­дения, получим, что если а n: . b, то существует такое натуральное число q n , что а п = bq n . Эти равенства позволяют преобразовать сумму а 1 + а 2 + ... +а п в сумму вида bq 1 + bq 2 + ... + bq n . Вынесем за скобки общий множитель b, а получившееся в скобках натуральное число q 1 + q 2 + ... + q n обозначим буквой q. Тогда a 1 + a 2 + ... + a n = b(q 1 + q 2 +... + q n) = 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;

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

Определение. Число а делится на число в тогда и только тогда, когда существует такое число q, что а = в × q. а в ( q N 0) [а = вq].

Обозначают: а в. Читают: «число а кратно числу в», «число в – делитель числа а», «а кратно в».

Равенство а=вq называют формулой кратности числа а числу в.

Число а, кратное 2, называют четным. Общий вид четного числа: а = 2n, n N 0 .

Число, кратное 3 имеет формулу: а = 3n, n N 0 .

Определение. Отношение делимости на множестве N 0 N содержит те и только те пары чисел (а, в), у которых первая координата кратна второй. Обозначают: « ».

« » = {(а, в)| (а, в) N 0 N а в}.

Если отношение делимости обозначить , то N 0 N ={(а, в)| (а, в) N 0 N а=вq}.

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

Доказательство. Так как а в, то ( q N 0) [а = вq] а – в=вq-в=в(q – 1), так как q N q 1.

Тогда в (q – 1) 0 в а. Из определения отношения делимости и равенства а = 1 × а, следует, что 1 является делителем для любого натурального числа.

Следствие. Множество делителей данного числа конечно.

Например, делители числа 18 является конечное множество: {1, 2, 3, 6, 9, 18}.

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

1. Отношение делимости рефлексивно, то есть любое натуральное число делится само на себя: ( а N) [(а,а) ], то есть а: а = 1.

Доказательство. ( а N)[а = а × 1] по определению отношения делимости а: а.

2. Отношение делимости антисимметрично, то есть для различных чисел а и в из того, что а в, следует, что в не кратно а. ( а, в N 0 N)[а в а в ].

Доказательство. Допустим, что в а, тогда в а. Но по условию а в, так как а в.

Неравенства в а а в истины только в том случае, если а = в. пришли к противоречию с условием. Следовательно, допущение, что в а Л. Таким образом, отношение делимости антисимметрично.

3. Отношение делимости транзитивно. ( а,в,с N 0 N)[а в в с а с].

Доказательство. Если а в ( q N)[а = вq] (1) Из того, что в с ( t N)[в = сt] (2)

Подставим в = сt в равенство (1), получим: а = (сt)q = c(tq), t,q N tq N tq = р а = ср, р N. А это значит, что а с.

Признаки делимости. Делимость суммы, разности, произведения

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

Теорема (признак делимости суммы). Если числа а и в делится на число n, то их сумма делится на это число, ( а,в, n N 0 N)[а n в n (а + в) n].

Доказательство. Из того что а n в n (по определению отношения делимости)

а=nq 1 (1), q 1 N. в=nq 2 (2), q 2 N. Преобразуем сумму (а + в) к виду:

а + в = nq 1 + nq 2 = n (q 1 + q 2) = nq,q = q 1 + q 2 . а + в = nq.

Следовательно, по определению отношения делимости, что (а + в) n.

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

( а,в,n N 0 N)[а n в n а в (а – в) n].

Теорема (признак делимости произведения). Если один из множителей произведения делится на число n, то и все произведение делится на число n.

( а,в,n N 0 N)[а n (ав) n].

Доказательство. Из того, что а n а = nq (1). Умножим обе части равенства (1) на в N, получим: ав = nqв (по ассоциативности умножения) ав = n(qв) = nt, где t = qв ав = nt. А это значит, что ав n (по определению отношения делимости). Таким образом, для делимости произведения на число достаточно чтобы на данное число делился хотя бы один из множителей этого произведения.

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

( а,в,m,n N)[а m в n ав mn].

Доказательство. Из того, что а m а = mq 1 , q 1 N; в n в = nq 2 , q 2 N

ав = mq 1 × nq 2 , = mn(q 1 × q 2) = mnq, q 1 × q 2 = q N. ав = mnq ав mn.

Теорема (признак делимости на 2). Для того, чтобы число х делилось на 2 необходимо и достаточно, чтобы его десятичная запись оканчивалась одной из цифр: 0, 2, 4, 6, 8.

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

х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 , где а n , a n –1 , …, а 1 – цифры, принимающие значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и а n 0, а 0 – принимает значения 0, 2, 4, 6, 8.

Докажем, что число х 2. Так как 10 2, то любая степень числа 10 2. Десятичную запись числа х представим в виде: х = (а n 10 n + a n –1 10 n –1 + …+a 1 10) + a 0

I слагаемое II слагаемое

В этой сумме первое слагаемое по признаку делимости суммы делится на 2. Второе слагаемое а 0 2 (по условию). Следовательно, по признаку делимости суммы на число х делится на 2.

Обратно, если число х делится на 2, то его десятичная запись оканчивается цифрой 0, 2, 4, 6, 8.

Запишем число х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 в виде: а 0 = х – (а n 10 n + a n –1 10 n –1 + …+a 1 10).

В этой разности число х 2 (по условию), вычитаемое (а n 10 n + a n –1 10 n –1 + …+a 1 10) 2 (по признаку делимости суммы). Следовательно, по теореме о делимости разности а 0 2. Чтобы однозначное число а 0 делилось на 2, оно должно принимать значения 0, 2, 4, 6, 8.

Признак делимости на 2. На 2 делятся те и только те числа, в разряде единиц которых содержится число, делящееся на 2 или на 2 делятся те и только те числа, десятичная запись которых оканчивается одной из цифр 0, 2, 4, 6, 8.

Теорема (признак делимости на 5). Для того, чтобы число х делилось на 5, необходимо и достаточно, чтобы его десятичная запись оканчивалась цифрой 0 или 5.

Лемма . ( n N) .

Доказательство. Так как 100 = 4 × 25, то по признаку делимости произведения

100 4. Тогда ( n N n > 1) 10 n = 100 × 10 n–2 и по признаку делимости произведения 10 n 4.

Теорема (признак делимости на 4). Натуральное число х делится на 4 тогда и только тогда, когда две последние цифры его десятичной записи образуют двузначное число, делящееся на 4.

Пусть х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 и пусть десятичная запись двух последних цифр a 1 10 + a 0 выражает число , которое делится на 4.

Доказательство. Представим число х в виде суммы двух слагаемых:

х = (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) + (а 1 10 + а 0),

I слагаемое II слагаемое

где первое слагаемое, по доказанной выше Лемме, делится на 4, второе слагаемое делится на 4 по условию. Следовательно, согласно признака делимости суммы на число, число х делится на 4.

Обратно, если число х 4, то – двузначное число, образованное последними цифрами его десятичной записи, делится на 4.

По условию х 4. Докажем, что (а 1 10 + а 0) 4.

Доказательство. Десятичная запись числа х имеет вид:

х = а n 10 n + a n –1 10 n –1 + …+а 2 10 2 + a 1 10 + a 0 , представим число х в виде суммы двух слагаемых:

х = (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) + (а 1 10 + а 0) и запишем равенство в виде:

х – (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) = а 1 10 + а 0 , где х 4 (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) 4 (по лемме).

Следовательно, по признаку делимости разности а 1 10 + а 0 4. выражение а 1 10 + а 0 = – есть запись двузначного числа, образованного последними цифрами записи числа х.

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

Теорема. Для того чтобы число х делилось на 25 необходимо и достаточно, чтобы на 25 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х.

Доказывается аналогично.

Признак делимости на 25. На 25 делятся те и только те числа, у которых две последние цифры в записи числа 00, 25, 50, 75.

Лемма. ( n N) [(10 n – 1) 9].

Докажем методом математической индукции.

1. Проверим справедливость утверждения для n = 1, И 3

Признак делимости на 3. На 3 делятся те и только те числа, сумма цифр которых делится на 3.