Делимость чисел

Ноя 16 2014 Опубликовал в Олимпиада

Делимость чисел

Делимость — способность одного числа делиться на другое. Свойства делимости зависят от того, какие множества чисел рассматривают. Если рассматривают только целые положительные (натуральные) числа, то говорят, что одно число делится на другое (является кратным другого), если частное от деления первого числа на второе будет также целым числом.

Число называется простым, если у него нет делителей, отличных от него самого и от единицы (например, числа 2, 3, 5, 7, 97, 199 и т.д.), и составным в противном случае. Число 1 не является ни простым числом, ни составным. Обратим внимание, что среди простых чисел только одно четное – 2.

Доказано, что простых чисел — бесконечно много. Таблицы простых чисел печатаются в математических справочниках и учебниках, их можно найти в Интернете.

Задание 1. Если простые числа отличаются на 2, то их называют числами-близнецами. Например, в первой сотне это 3 и 5, 5 и 7, 11 и 13, 17 и 19, 29 и 31, 41 и 43, 59 и 61, 71 и 73. Назовите числа-близнецы из пятой сотни.

Ответ: 419 и 421, 431 и 433, 461 и 463.

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

 

Числа Мерсенна.

Марен Мерсенн (1588 — 1648) —  французский математик и философ. Со времен учебы дружил  с Декартом. Переписывался с Галилеем, Паскалем, Торричелли и Ферма.  Когда он жил  в Париже, то в его доме еженедельно происходили собрания математиков и физиков, сообщавших результаты своих исследований. Позднее при содействии Кольбера в 1666 году  из этого кружка образовалась парижская академия наук. Сочинения самого Мерсенна были посвящены богословию, физике и теории чисел.

Мерсенн исследовал числа вида Мр = 2р— 1, где р – простое число.

М2 = 22— 1 = 3; простое число;

М3= 23— 1 = 7; простое число;

 Задание 2. Найдите первых шесть чисел Мерсена и определите, есть ли среди них составные числа.

Решение.

М5 = 25— 1 = 31; простое число.

М7 = 127 — простое число.

М11 = 2047 – составное (23∙89).

М13 =8191 –простое.

Ответ. М11 – составное число.

На сегодняшний день известно более 40 простых чисел Мерсенна. Современная техника позволяет ускорить процессы вычислений, однако все равно это трудоемкий процесс, и тому, кто найдет простое число из более чем 100 000 000 цифр обещана большая премия.

Число называется совершенным, если оно равно сумме своих делителей, отличных от него самого. Например, 6 – совершенное число, так как 6 = 1 + 2 + 3.

Евклид обнаружил, что если число 2p – 1 – простое, то число 2p–1(2p – 1) будет совершенным. Например, для  р =2,      2р— 1 = 22— 1 = 3;       2p–1(2p – 1) = 22–1(22 – 1) =2∙3 =6.

Через века Эйлер доказал, что все чётные совершенные числа имеют указанный вид. Существуют ли вообще нечётные совершенные числа науке до сих пор неизвестно.

Задание 3. Найдите три совершенных числа.

Решение.

Если р = 3,    2р— 1 = 23— 1 = 7,      2p–1(2p – 1) = 23–1(23 – 1) = 4∙7 = 28.   28 = 1 + 2 + 4 + 7 + 14.

Если р = 5,    2р— 1 = 25— 1 = 31,    2p–1(2p – 1) = 25–1(25 – 1) =16∙31 =496.

496 = 1 + 2 + 4 + 6 + 16 + 31 + 62 + 124 + 248.

Если р = 7,    2р— 1 = 27— 1 = 127,      2p–1(2p – 1) = 27–1(27– 1) =64∙127 =8128.

8128 = 1 +  2 + 4 +8 + 16 + 32+ 64 + 127 + 254 + 508 +1016 + 2032 + 4064.

Ответ: 28, 496, 8128.

Любое целое число можно представить в виде произведения простых чисел или разложить на простые множители. Например, 504 = 2×2×2×3×3×7, причём это разложение единственно с точностью до порядка множителей (как говорят, однозначно). Так, разложение числа 504 на множители может быть записано также следующим образом:  504 = 3×2×7×3×2×2 = 7×3×2×2×3×2 и т.д., однако все эти разложения отличаются только порядком множителей.

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

Запись числа в виде произведения степеней в порядке возрастания их оснований называетсяканоническим разложением числа: 504 = 23×32×71

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

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

  1. Число делится на 2, если оно оканчивается на 0, 2, 4, 6 или 8, то есть, если оно четное.
  2. Число делится на 5, если оно оканчивается на 0 или 5.
  3. Число делится на 3 или на 9, если сумма цифр числа делится на 3 или на 9 соответственно. Например, число 414 делится и на  3 и на 9 (сумма цифр равна 9), а число 417 делится на 3, но не делится на 9 (сумма цифр равна 12, делится на 3 и не делится на 9).
  4. Число делится на 11, если разность суммы цифр, стоящих на чётных местах, и суммы цифр, стоящих на нечётных местах, делится на 11. Например, число 1969 делится на 11 (сумма цифр, стоящих на четных местах равна 18, а на нечетных — 7).

Есть более сложные признаки делимости, но иногда полезно знать и о них.

5. Число делится на 7 или на 13, если на эти числа делится разность числа тысяч и числа, выражаемого последними тремя цифрами; эта операция уменьшает число знаков в числе, и последовательное её применение приводит к трёхзначному числу. Например, 825 678 делится на 7, т.к. 825-678 = 147 делится на 7.

 Задание 4: Припишите к числу 1 000 000 три цифры справа так, чтобы число делилось на 7, 8 и 9.

Решение. Чтобы искомое число делилось на 8, число, составленное из приписанных цифр должно делиться на 8; чтобы делилось на 9 – сумма цифр искомого числа должна делиться на 9. Получить такое число (делится на 8 и 9) самым простым способом можно приписав 008. Получится число 1000 000 008. Проверим делимость его на 7.

По признаку делимости на 7: 1000000 – 8 = 999992;

999 -992 = 7; 7 делится на 7.

Или просто делим, 1 000 000 008: 7= 142 857 144. Мы получили искомое число.

Ответ: 1000 000 008.

Кроме признаков делимости на простые числа существуют также признаки делимости на составные числа. Например:

  1. Число делится на 4,  если число, записываемое двумя последними цифрами этого числа, делится на 4.
  2. Число делится на 8,  если число, записываемое тремя последними цифрами этого числа, делится на 8.

Установлено, что если число делится на два взаимно простых числа, то оно делится и на их произведение. На этом факте основаны простые признаки делимости на 6 = 2×3, на 12 = 3×4, на 15 = 3×5,  на 18 = 2×9 и т.д.

  1. На 6 делятся те и только те числа, которые делятся и на 2 и на 3. Например, 12432 делится на 6, так как делится и на 2 и на 3.
  2. На 12 делятся те и только те числа, которые делятся и на 3 и на 4 (но не 2 и на 6, так как 2 и 6 имеют общий множитель). Например, 75348 делится на 12, так как делится и на 3 и на 4.
  3. На 15 делятся те и только те числа, которые делятся и на 3 и на 5. Например, 23520 делится на 15, так как делится и на 3 и на 5.
  4. На 18 делятся те и только те числа, которые делятся и на 2 и на 9. Например, 13518 делится на 18, так как делится и на 2 и на 9, и т.д.

Полезно помнить и следующие свойства делимости чисел.

  1. Если каждое из слагаемых делится на какое-то число, то и сумма их обязательно делится на это же число.
  2. Если каждое слагаемое, кроме одного делится на какое-нибудь число, а одно не делится, то сумма не делится на это число.
  3. Если уменьшаемое и вычитаемое делится на какое-нибудь число, то и разность разделится на это же число.
  4. Если только одно из чисел – уменьшаемое или вычитаемое — делится на какое-нибудь число, а другое не делится,  то  и разность не делится на это же число.
  5. Если хоть один из сомножителей делится на какое-нибудь число, то и произведение их также разделится на это число.

 

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

1 число 2 число 3 число Сумма Произведение
д д д
н д д
д н д
д д н
н н д
н д н
д н н
н н н

Решение.

1 число 2 число 3 число Сумма Произведение
д д д д д
н д д н д
д н д н д
д д н н д
н н д Может делиться,может не делиться д
н д н Может делиться,может не делиться д
д н н Может делиться,может не делиться д
н н н Может делиться,может не делиться н

 

 

 

 

 

 

 

   Задание 6.  Укажите, какие из следующих утверждений ложные.

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

Б) Если произведение двух чисел делится на какое-либо число, то хотя бы один из множителей делится на это число.

В) Если множители не делятся на какое-нибудь число, то и произведение не делится на это число.

Г) Если разность делится на какое-нибудь число, то и уменьшаемое, и вычитаемое делится на это число.

Решение.

А) Ложное. Пример: 7+3 = 10;  7 и 3 не делятся на 5, а 10 делится на 5.

Б) Ложное. Пример: 6 × 10 = 60; 60 делится на 15, а ни 6, ни 10 не делятся.

В) Ложное. Пример: 6 × 10 = 60; ни 6, ни 10 не делятся на 15, а 60 делится на 15.

Г) Ложное. Пример: 23 — 21 = 2. Разность 2 делится на 2, а 23 и 21 на 2 не делятся.

Общие делители и кратные.

  Общим делителем нескольких чисел называется число, на которое все данные числа делятся без остатка. Например, числа 1, 2, 3, 4, 6, 12 являются общими  делителями для чисел 36 и 24,  а числа 14 и 15 имеют только один общий делитель – 1.

Для двух и более чисел среди всех их общих делителей существует наибольший, называемый наибольшим общим делителем (НОД).  Например, НОД (48, 36, 24)=12.

Если наибольший общий делитель двух чисел равен единице, то числа называются взаимно простыми. Например, НОД (16, 27) =1, значит, 16 и  27 – взаимно простые числа.

 Задание 7. Приведите 2-3 примера взаимно простых чисел и чисел, имеющих несколько общих делителей, найдите для них НОД.

 Общим кратным данных чисел называется любое натуральное число, которое делится на каждое из данных чисел (без остатка). Например, числа 18, 12, 6, 120, 60 являются общими кратными для чисел 2 и 3.

Наименьшим общим кратным нескольких чисел называется наименьшее натуральное число, которое делится на каждое из данных чисел. Например, 6 – наименьшее общее кратное для 2 и 3.

Обратим внимание, что

Обычно НОД и НОК нескольких чисел находят, используя разложения чисел на простые множители. НОД равен произведению множителей, входящих в каждое разложение; НОК – произведению всех множителей,  входящих хотя бы в одно разложение.

Рассмотрим множество делителей числа 20 и множество делителей числа 30:

Д(20) = {1, 2, 4, 5, 10, 20}, Д(30) = {1, 2, 3, 5, 6, 10, 15, 30}.

Найдем пересечение этих множеств.

Д(20) È Д(30) = {1, 2, 3, 4, 5, 6, 10, 15, 30}, а Д(20) Ç Д(30) = {1, 2, 5, 10}.

НОД (20,30) = 10, то есть НОД нескольких чисел – это наибольший элемент из пересечения множеств делителей этих чисел.

Задание 8. Найдите НОД и НОК для чисел:

А) 18, 63;

Б) 18, 84;

В) 63, 84;

Г) 18, 63, 84.

Ответ.

А) НОД = 9;  НОК = 126.

Б)  НОД = 6; НОК =252.

В) НОД = 21; НОК =252.

Г) НОД = 3; НОК = 252.

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

Он основан на следующих свойствах делимости:

  1. Любой общий делитель чисел а и в (а > в) является делителем числа (а — в).
  2. Любой общий делитель чисел в и (а — в) является делителем числа а.

Тогда НОД (а, в)= НОД (в, а — в ).

Например, НОД (451, 287) = НОД (451-287, 287) = НОД (164, 287) = НОД (164, 123) = НОД (41, 123) = НОД (41, 82) = НОД (41, 41) = 41.

Несмотря на свою простоту, алгоритм Евклида является важным элементом математического образования.

Рассмотрим несколько задач.

Задание 9: Вася рвет газету на 8 частей, одну из получившихся частей — еще на 8, и так далее. Сможет ли он разорвать газету на 2011 частей?

Решение. Так как Вася все время рвет на 8 частей, то в первый раз у него получится 8 частей, во второй раз — 15 разных частей (1∙7+8), в третий раз 22 части (2×7+8) и т.д., то есть каждый раз у него увеличивается на 7 частей, общее количество частей всегда имеет вид К×7+8. Посмотрим на число 2011, его нельзя представить в виде К×7+8. (2011 – 8 =2003, а 2003 не делится на 7). Значит, Вася не сможет разорвать газету на 2011 частей.

Ответ: нет.

Задание 10: Докажите, что k3 — k делится на 6 при любом целом k.

Решение. k3 – k = k(k21) = k(k-1)(k+1). Получили произведение трех последовательных чисел, из них одно всегда будет делиться на 3, и хотя бы одно будет делиться на 2, значит, произведение будет делиться на 6.

 Задание 11. Докажите, что если р – простое нечетное число, то р2 – 1 делится на 4.

Решение. р2 – 1 = (р — 1)(р +1). Получили произведение двух чисел, одно из них больше на 1 нечетного числа, другое — меньше на 1, значит, оба четные. Произведение двух четных чисел делится на 4.

Учителю. В восьмом классе усложните задачу – докажите делимость на 8.

Произведение двух последовательных четных чисел всегда будет делиться на 8. Первое четное 2n, второе (2n + 2) , их произведение 2n(2n + 2) =2n∙2(n + 1) =4n∙(n + 1)делится на 4  и хотя бы одно из чисел n или (n + 1) будет делиться на 2, значит, произведение будет делиться на 8.

Задание 12. На какую цифру оканчивается число 32010?

Решение. Попробуем найти закономерность: 31=3, 32=9; 33=27; 34=81; 35=243; 36=729, 37=2187 и т.д. Очевидно, что последние цифры степени числа 3 начинают повторяться в определенном порядке: 3, 9, 7, 1, 3, 9, 7, 1… и т. д. Обратим внимание, что повторяются всего 4 цифры (3, 9, 7, 1), то есть, число равное 3n, где кратно четырем, всегда оканчивается на 1. Разделим степень числа 3 на 4: 2010=4∙500 +10 = 4∙500 +8 + 2, отсюда, 32008 оканчивается на 1, а 32010 оканчивается на 9.

Ответ: 9.

Задание 13. Найдите знаменатель дроби, полученной после сокращения .

Решение. 10100 = 2100∙5100. Следовательно, в числителе нас интересуют только множители, кратные 2 и 5.

100! = 1 ∙ 2∙ 3 ∙ 4 ∙ …..∙ 98 ∙ 99 ∙ 100 – произведение 100 первых натуральных чисел. Среди них половина четные, это дает 50 множителей равных 2. Ровно 25 чисел делятся на 4, это дает еще дополнительно 25 множителей, равных 2. На 8 делятся 12 чисел, еще 12 множителей, равных 2. На 16 делятся 6 чисел, на 32  —  3 числа, на 64 — 1. Итого 97 множителей равных 2. Значит, в каноническом разложении числителя присутствует 297. Аналогично∙рассуждая, находим 24 множителя равных 5. Значит, в каноническом разложении присутствует 524. После сокращения в знаменателе останется 23 ∙576.

Ответ: 23 ∙576.

 Задание 14 (Кенгуру-2004):  Каков наибольший делитель числа 32004 + 6, отличный от этого числа?

Решение. Число 32004 + 6 не делится на 2, так как 6 делится на 2, а 32004 – не делится. Но 32004+ 6 делится на 3. Поэтому наименьший делитель этого числа равен 3. Чтобы получить наибольший делитель, отличный от самого числа, надо это число разделить на наименьший делитель. Поэтому наибольший делитель равен (32004 + 6) : 3 = 32003 + 2.

Ответ: 32003 + 2.

 Свойства остатков.

Мы уже знаем, что для любого натурального числа n существует представление его в виде n=km + r, где 0£ r <mk, r  целые числа.

k называется неполным частным от деления n на m, а r остатком.

Задание 15. Запишите:

а) формулу четного числа;

б) формулу нечетного числа;

в) формулу  числа, кратного числу b;

г) Формулу числа, которое делится на 17 с остатком 11.

Решение.       а) n = 2m;

б) n = 2m+1;

в) n = km;

г) n = 17m+11.

 Задание 16. При делении натуральных чисел на 4, образуются подмножества натуральных чисел, делящихся на 4 с разными остатками. Изобразите схематично, как множество натуральных чисел и эти подмножества связаны между собой. Приведите примеры чисел из каждого подмножества.

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

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

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

 Основные свойства остатков:

Пусть остаток от деления целого числа n1 на m равен r1, а остаток от деления n2 на m равен r2. Тогда:

  1. Остаток от деления n1+n2 на m равен остатку от деления r1+r2 на m;
  2. Остаток от деления n1n2 на m равен остатку от деления r1r2 на m;
  3. Остаток от деления n1´n2 на m равен остатку от деления r1´r2 на m.

Задание 17. Не производя вычислений, докажите, что сумма 84 + 85 + 86 + 87 + 88 + 89 + 90 делится на 7 и на 87.

Решение. Если рассмотрим попарно первое и седьмое, второе и шестое, третье и пятое слагаемые, то очевидно, что их сумма (пара чисел) будет делиться на 87 (и равна 2×87). Тогда вся сумма равна 7×87.

 Задание 18. Не используя калькулятор и вычисления в столбик, найдите остаток от деления на 25 значения выражения  53×55 + 27×24 — 101×29.

Решение. Остаток от деления на 25 числа 53  равен 3, числа 55 равен 5, числа 27 — 2, числа 24 – 24, числа 101 — 1, числа 29 – 4.

Используя основные свойства остатков, получаем:

  1. Остаток от деления на 25 произведения 53×55 равен  15  (3×5 =15, 15 : 25 =0(ост.15)).
  2. Остаток от деления на 25 произведения 27×24 равен  23 (2×24 =48, 48 : 25 = 1(ост.23)).
  3. Остаток от деления на 25 произведения101×29 равен  4  (1×4=4, 4 : 25 = 0(ост.4)).

Тогда остаток от деления на 25  значения выражения  53×59 + 101×29 — 27×24 равен

остатку от деления  на 25 числа 34  (23 + 15 – 4), то есть 9.

Ответ: 9.

 Задача 19  Каков остаток от деления 1997-значного числа 100…00 на 15?

Очевидно, что в результате деления остаток будет равен 10.
Решение. Попробуем начать делить число 100…00 на 15.

Ответ. 10.

Нет ответов пока

Вы должны ввойти чтобы оставить комментарий.