Какие есть свойства делимости

Алгебра и начала математического анализа, 10 класс

Урок №7. Делимость. Свойства и признаки делимости.

Перечень вопросов, рассматриваемых в теме:

• наибольший общий делитель пары чисел;
• признаки делимости и метод математической индукции для доказательства делимости.

Глоссарий по теме

Натуральные числа – это числа, возникающие естественным образом при счете предметов.

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

Число n – делитель числа m, делимое m – кратное числа n, а число q – частное от деления m на n.

Простое число – это натуральное число, у которого есть лишь два различающихся натуральных делителя – самого число и единица.

Взаимно простые числа – два натуральных числа, у которых есть лишь один общий делитель, единица.

Наибольший общий делитель (НОД) чисел n и m – самое большое из натуральных чисел, которые являются одновременно делителями натуральных чисел n и m.

Алгоритм Евклида – алгоритм для нахождения наибольшего общего делителя пары чисел.

Знакочередующаяся сумма – это сумма чисел, в которой каждый второй член помножен на –1.

Трехзначные грани числа – это числа, которые получены разбиением исходного числа на трехзначные числа, начиная с его конца.

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

Основная литература:

Колягин Ю.М., Ткачева М.В., Федорова Н.Е., Шабунин М.И., под ред. Жижченко А.Б. Алгебра и начала математического анализа (базовый и профильный уровни) 10 кл. – М.: Просвещение, 2011.

Дополнительная литература:

Баданин А. С., Сизова М. Ю. Применение метода математической индукции к решению задач на делимость натуральных чисел // Юный ученый. — 2015. — №2. — С. 84-86.

Открытые электронные ресурсы:

Решу ЕГЭ образовательный портал для подготовки к экзаменам https://ege.sdamgia.ru/

Теоретический материал для самостоятельного изучения

Целое число

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

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

Натуральные числа – это числа, возникающие естественным образом при счете предметов.

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

Поставим в соответствие каждой из точек, отмеченной на прямой, свой порядковый номер. Эти номера являются натуральными числами, возникающими при счете числа точек на луче (рис. 1).

Рисунок 1 – числовой луч

Число точек на луче бесконечно и каждой ставится в соответствие свое натуральное число.

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

Дополним нашу числовую ось ненатуральными целыми числами. Отложим второй луч в противоположном первому направлении от точки начала первого луча. И также отложим на нем единичные отрезки (рис. 2)

Рисунок 2 – числовой луч

Добавим на ноль и отрицательные числа, чтобы получить иллюстрацию множества целых чисел (рис. 3).

Рисунок 3 – числовой луч

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

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

Целое число m делится на натуральное число n (или n делит m), если для числа m и числа n существует такое целое число q, что m = n · q.

Число n – делитель числа m, делимое m – кратное числа n, а число q – частное от деления m на n.

Например, целое число – 10 делится на натуральное число 5, так как для этих двух чисел существует целое число –2, такое, что –10 = 5 · –2. При этом –10 – кратное числа 5, 5 – делитель 10, а –2 является частным от деления 10 на 5.

Заметим, что делимость можно определить по-разному. Вместо натурального числа n в определении выше, можно было бы задать n как целое число. Однако мы будем придерживаться определения, введенного в данном уроке.

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

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

Перечислим некоторые свойства делимости:

1. Все целые числа делятся на единицу.

2. Каждое целое число, неравное нулю делится на натуральное число равное модулю от данного целого.

3. Все натуральные числа являются делителями нуля.

4. Если целое число a делится на натуральное число b и модуль числа a меньше b, то a равно нулю.

5. Если целое число a отлично от нуля и делится на натуральное число b, то модуль числа a не меньше числа b.

6. Единственный делитель единицы – сама единица.

7. Чтобы целое число a делилось на натуральное число b необходимо и достаточно, чтобы модуль числа a делился на b.

8. Пусть целое число a делится на натуральное число m, а число m в свою очередь делится на натуральное число k, тогда a делится на k (свойство транзитивности деления).

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

Свойства делимости удобно использовать при доказательстве теорем и решении задач.

Взаимно простые числа.

Простое число – это натуральное число, у которого есть лишь два различающихся натуральных делителя – самого число и единица.

Перечислим некоторые первые простые числа в порядке их возрастания: 2, 3, 5, 7, 11, 13. Любое натуральное число можно представить в виде произведения простых чисел. Это называется факторизацией натурального числа.

Взаимно простые числа – два натуральных числа, у которых есть лишь один общий делитель, единица.

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

Наибольший общий делитель (НОД) чисел n и m – самое большое из натуральных чисел, которые являются одновременно делителями натуральных чисел n и m.

Например, для чисел 77 и 14 наибольший общий делитель равен 7: НОД (77, 14) = 7.

НОД чисел n и m равен 1 тогда и только тогда, когда числа n и m взаимно просты.

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

Рассмотрим свойства делимости суммы разности и произведения чисел. Пусть a и b – целые числа, а m, n и k – натуральные числа.

1) Пусть оба числа a и b делятся на m, тогда числа a + b и a – b также делятся на m.

2) Пусть оба числа a и b делятся на m, тогда при любых k и n число k · a + n · b делится на m.

3) Пусть число a делится на m, а число b не делится на m, тогда числа a + b и a – b не делятся на m.

4) Пусть число a делится на m, а число b делится на n, тогда ab делится на mn.

5) Пусть число a делится на m и n, и при этом m и n – взаимно простые числа, тогда a делится на mn.

6) Пусть число a делится на m, тогда ak делится на mk.

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

Натуральное число n можно представить в виде:

n = q · m + r ИЛИ n / m = q (остаток r)

где q – целое неотрицательное число (0, 1, 2, …), m – натуральное число, r – целое неотрицательное число, меньшее m (0, 1, 2, …, m – 1).

Число n называют делимым, m – делителем, q – (неполным) частным, r – остатком (от деления).

Например, число 23 представимо в виде: 23 = 2 · 10 + 3, где 23 – делимое, 10 – делитель, 3 – остаток.

Алгоритм Евклида.

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

Пусть a и b– натуральные числа, не равные одновременно нулю, и верна последовательность чисел

где каждое – это остаток от деления числа, предшествовавшего предыдущему числу, на предыдущее число:

ИЛИ (остаток )

ИЛИ (остаток )

ИЛИ (остаток )

ИЛИ (остаток )

…

ИЛИ (остаток rk)

…

ИЛИ(остаток rn)

ИЛИ (остаток 0)

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

НОД(a, b), равен , то есть последнему ненулевому члену этой последовательности.

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

Зачастую в задаче требуется ответить, делится ли число на определенное целое число.

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

Знакочередующаяся сумма – это сумма чисел, в которой каждый второй член помножен на –1.

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

0 – 1 + 2 – 3 + 4 – 5 + 6 – 7 + 8 – 9 = – 5.

Трехзначные грани числа – это числа, которые получены разбиением исходного числа на трехзначные числа, начиная с его конца.

Например, трехзначные грани числа 6579813 это 6, 579, 813.

Таблица 1 – Признаки делимости

Заметим, что в формулировке признаков фигурирует выражение «тогда и только тогда». Это означает, что эти признаки являются также и свойствами чисел, которые однозначно делятся на одно из перечисленных чисел.

Метод математической индукции для доказательства делимости.

Схема метода:

1. Базис индукции.

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

2. Индукционное предположение.

Предполагаем, что утверждение верно для некоторого натурального значения k.

3. Шаг индукции (индукционный переход).

Доказываем, что утверждение справедливо для значения k+1.

4. Вывод.

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

Примеры и разбор решения заданий тренировочного модуля

Задача №1

Условие:

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

65, 30, 110, 1001, 273, 35, 14, 26

Решение:

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

По признаку делимости на 2, число делится на 2 тогда и только тогда, когда его последняя цифра является четной. Значит, можно выделить первую группу чисел: 30, 110, 14, 26. Каждое из них делится на 2.

По признаку делимости на 5, число делится на 5 тогда и только тогда, когда его последняя цифра равна 5 или 0. Значит, можно выделить вторую группу чисел: 65, 30, 110, 35. Каждое из них делится на 5.

По признаку делимости на 7, число делится на 7 тогда и только тогда, когда знакочередующаяся сумма трехзначных граней этого числа делится на 7. Значит, можно выделить третью группу чисел: 1001, 273, 35, 14. Каждое из них делится на 7.

По признаку делимости на 13, число делится на 13 тогда и только тогда, когда знакочередующаяся сумма трехзначных граней этого числа делится на 13. Значит, можно выделить четвертую группу чисел: 65, 1001, 273, 26. Каждое из них делится на 13.

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

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

Получим возможные пары:

(65; 14)

(30; 273) или (30; 1001)

(110; 1001) или (110; 273)

(35; 26)

Чтобы быть уверенными в найденной паре, необходимо удостоверится, что НОД пары равен 1.

Проверим, действительно ли 65 и 14 являются взаимно простыми. Разложим каждое из них на простые множители. 65 = 5 · 13, 14 = 7 · 2. НОД(65, 14) = 1, они действительно взаимно простые.

Проверим, действительно ли 35 и 26 являются взаимно простыми. Разложим каждое из них на простые множители. 35 = 5 · 7, 26 = 13 · 2. НОД(35, 26) = 1, они действительно взаимно простые.

Проверим пару (30; 273). По признаку делимости на 3 они оба делятся на это число. Значит, они не взаимно простые.

Проверим, действительно ли 30 и 1001 являются взаимно простыми. Разложим каждое из них на простые множители. 30 = 3 · 2 · 5, 1001 = 13 · 11· 7. НОД(30, 1001) = 1, они действительно взаимно простые.

Осталось проверить пару (110; 273). Разложим каждое из них на простые множители. 110 = 2 · 5 · 11, 273 = 3 · 91 = 3 · 7 · 13. НОД(110, 273) = 1, они действительно взаимно простые.

Ответ: (65; 14), (30; 1001), (110; 273), (35; 26).

Задача №2.

Условие:

Найдите НОД(2457, 1473).

Решение:

Решим задачу с помощью алгоритма Евклида.

Составим последовательность, включающую оба эти числа и остатки от деления предыдущих членов последовательности друг на друга:

2457 = 1 · 1473 + 984

1473 = 1 · 984 + 489

984 = 2 · 489 + 6

489 = 81 · 6 + 3

6 = 3 · 2

Последний ненулевой член этой последовательности оказался равен 3. Следовательно, НОД(2457, 1473) = 3.

Ответ: НОД(2457, 1473) = 3.

Задача №3.

Условие:

Определите, делится ли число 17943646 на 7.

Решение:

Для начала разобьем это число на грани: 17|943|646. Получили числа 17, 943, 646. Найдем их знакочередующуюся сумму: 17 – 943 + 646 = –280. Число –280 делится на 7 нацело. Следовательно, по признаку делимости числа на 7 число 17943646 также делится на 7 нацело.

Ответ: число 17943646 делится на 7 без остатка.

Задача №4.

Условие:

Докажите делимость + 6n – 10 на 18при любом натуральном n.

Решение:

Воспользуемся методом математической индукции для решения задачи.

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

+ 6 – 10 = 10 – 10 = 0

Ноль делится на любое натуральное число, значит на 18 тоже. Утверждение справедливо при n = 1.

2. Предположим, что утверждение верно для некоторого натурального значения k. Тогда + 6k – 10 делится на 18. То есть, по определению: + 6k – 10 = 18 · m, где m – целое число.

3. Рассмотрим выражение при n = k +1.

+ 6(k + 1) – 10 = 4 ⋅ + 6k + 6 – 10 = 4 ·+ 6k – 4

Воспользуемся нашим предположением о верности рассматриваемого утверждения для значения k:

+ 6k – 10 = 18m, следовательно = –6k + 10 + 18m.

Подставим полученное значение для в выражение при n = k + 1:

+ 6(k + 1) – 10 = 4(–6k + 10 + 18m) + 6k – 4 = –24k + 40 + 4 · 18m + 6k – 4 = –18k + 4 · 18m + 36 = 18(–k + 4m + 2) = 18 · q, где q – некоторое целое число. Из этой записи следует, что + 6(k + 1) – 10 делится на 18 по определению. Следовательно, данное утверждение верно при значении n = k + 1.

4. Утверждение оказалось справедливым при наименьшем натуральном числе n = 1 и при n = k + 1 с условием его верности при n = k. По методу математической индукции следует, утверждение справедливо при любом натуральном n. Что и требовалось доказать.