Делимость чисел.Теория 7-8 класс.

7­8 классы  Тема 3. Делимость чисел Делимость ­  способность одного числа делиться на другое. Свойства делимости зависят от того, какие множества чисел рассматривают. Если рассматривают только целые положительные (натуральные) числа, то говорят, что одно число делится на другое (является кратным другого), если частное от деления первого числа на второе будет также целым числом.  Число называется простым, если у него нет делителей, отличных от него самого и от единицы (например, числа 2, 3, 5, 7, 97, 199 и т.д.), и составным в противном случае. Число 1 не является ни простым числом, ни составным. Обратим внимание, что среди простых чисел только одно четное – 2.  Доказано,   что   простых   чисел   ­   бесконечно   много.   Таблицы   простых   чисел   печатаются   в математических справочниках и учебниках, их можно найти в Интернете.  Учителю. Напомните ученикам о методе нахождения простых чисел – решете Эратосфена. Таблица простых чисел до 1500. 2 67 157 257 367 467 599 709 829 967 1087 1217 1327 1483 3 71 163 263 373 479 601 719 839 971 1091 1223 1361 1487 5 73 167 269 379 487 607 727 853 977 1093 1229 1367 1489 7 79 173 271 383 491 613 733 857 983 1097 1231 1373 1493 11 83 179 277 389 499 617 739 859 991 1103 1237 1381 1499 13 89 181 281 397 503 619 743 863 997 1109 1249 1399 17 97 191 283 401 509 631 751 877 1009 1117 1259 1409 19 101 193 293 409 521 641 757 881 1013 1123 1277 1423 23 103 197 307 419 523 643 761 883 1019 1129 1279 1427 29 107 199 311 421 541 647 769 887 1021 1151 1283 1429 31 109 211 313 431 547 653 773 907 1031 1153 1289 1433 37 113 223 317 433 557 659 787 911 1033 1163 1291 1439 41 127 227 331 439 563 661 797 919 1039 1171 1297 1447 43 131 229 337 443 569 673 809 929 1049 1181 1301 1451 47 137 233 347 449 571 677 811 937 1051 1187 1303 1453 53 139 239 349 457 577 683 821 941 1061 1193 1307 1459 59 149 241 353 461 587 691 823 947 1063 1201 1319 1471 61 151 251 359 463 593 701 827 953 1069 1213 1321 1481 Задание 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; простое число; Материалы разработаны методистами Новосибирского центра  продуктивного  обучения 1 Задание 2. Найдите первых шесть чисел Мерсена и определите, есть ли среди них составные числа. Решение.  М5 = 25­ 1 = 31; простое число. М7 = 127 ­ простое число. М11 = 2047 – составное (23∙89). М13 =8191 –простое. Ответ. М11 – составное число. Математикам всегда было интересно найти самое большое простое число. Леонард Эйлер в своё время  нашел большое простое число 231 − 1 = 2147483647. p Число цифр в числе p Год открытия Кто открыл 2127 – 1 (2148 + 1)/17 114(2127 – 1) + 1 180(2127 – 1)2 + 1 2521 – 1 2607 – 1 21279 – 1 22203 – 1 22281 – 1 23217 – 1 24253 – 1 24423 – 1 29689 – 1 29941 – 1 211213 – 1 219937 – 1 … 39 44 41 79 157 183 386 664 687 969 1281 1332 2917 2993 3376 6002 1876 1951 1951 Люка Феррье Миллер + Уиллер + EDSAC 1 1952 Лемер + Робинсон + SWAC 1957 1961 1963 1971 Ризель + BESK Хурвитц + Селфридж +  IBM 7090 Гиллис + ILIAC 2 Таккермэн + IBM 360 На сегодняшний день известно более 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. Материалы разработаны методистами Новосибирского центра  продуктивного  обучения 2 Любое целое число можно представить в виде произведения простых чисел или разложить на простые множители. Например, 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. Материалы разработаны методистами Новосибирского центра  продуктивного  обучения 3 Установлено, что если число делится на два взаимно простых числа, то оно делится и на их произведение. На этом факте основаны простые признаки делимости на 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, и т.д. Учителю.  Попросите   учеников   самим   придумать   и   сформулировать   новые   признаки делимости и примеры (например, на 21=37,  45 =59 и т.п.) Полезно помнить и следующие свойства делимости чисел. 1. Если каждое из слагаемых делится на какое­то число, то и сумма их обязательно делится на это же число. 2. Если каждое слагаемое, кроме одного делится на какое­нибудь число, а одно не делится, то сумма не делится на это число. 3. Если уменьшаемое и вычитаемое делится на какое­нибудь число, то и разность разделится на это же число. 4. Если только одно из чисел – уменьшаемое или вычитаемое ­ делится на какое­нибудь число, а другое не делится,  то  и разность не делится на это же число. 5. Если хоть один из сомножителей делится на какое­нибудь число, то и произведение их также разделится на это число. Задание 5. Используя свойства делимости и данные о делимости на число к каждого слагаемого, определите, делится ли на к  сумма или произведение.  1 число 2 число 3 число Сумма Произведение д н д д н н д н д д н д н д н н д д д н д н н н Решение.  Материалы разработаны методистами Новосибирского центра  продуктивного  обучения 4 1 число 2 число 3 число Сумма Произведение д н д д н н д н д д н д н д н н д д д н д н н н д н н н Может делиться,  может не делиться Может делиться,  может не делиться Может делиться,  может не делиться Может делиться,  может не делиться д д д д д д д н Задание 6. Придумайте по два примера на каждое свойство делимости. Задание 7.  Укажите, какие из следующих утверждений ложные. А) Если слагаемые не делятся на какое­то число, то и сумма не делится на это число. Б) Если произведение двух чисел делится на какое­либо число, то хотя бы один из множителей делится на это число.  В) Если множители не делятся на какое­нибудь число, то и произведение не делится на это число.  Г) Если разность делится на какое­нибудь число, то и уменьшаемое, и вычитаемое делится на это число. Решение.  А) Ложное. Пример: 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 примера взаимно простых чисел и чисел, имеющих несколько общих делителей, найдите для них НОД. Материалы разработаны методистами Новосибирского центра  продуктивного  обучения 5 Общим кратным  данных  чисел  называется   любое  натуральное   число,  которое  делится   на каждое   из   данных   чисел   (без   остатка).   Например,   числа   18,   12,   6,   120,   60   являются   общими кратными для чисел 2 и 3. Наименьшим общим кратным нескольких чисел называется наименьшее натуральное число, которое делится на каждое из данных чисел. Например, 6 – наименьшее общее кратное для 2 и 3. Обратим внимание, что   НОК ),( ba  ab НОД ),( ba Обычно   НОД   и   НОК   нескольких   чисел   находят,   используя   разложения   чисел   на   простые множители.   НОД   равен   произведению   множителей,   входящих   в   каждое   разложение;   НОК   – произведению всех множителей,  входящих хотя бы в одно разложение. Рассмотрим множество делителей числа 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 частей? Материалы разработаны методистами Новосибирского центра  продуктивного  обучения 6 Решение. Так как Вася все время рвет на 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(k2­1) = 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, где n  кратно четырем, всегда оканчивается на 1. Разделим степень числа 3 на 4: 2010=4∙500 +10 = 4∙500 +8 + 2, отсюда, 32008 оканчивается на 1, а 32010 оканчивается на 9. Ответ: 9. Задание 13. Найдите знаменатель дроби, полученной после сокращения  !100 100 10 . Решение. 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, отличный от этого числа? Материалы разработаны методистами Новосибирского центра  продуктивного  обучения 7 Решение. Число 32004 + 6 не делится на 2, так как 6 делится на 2, а 32004 – не делится. Но 32004 + 6 делится на 3. Поэтому наименьший делитель этого числа равен 3. Чтобы получить наибольший делитель, отличный от самого числа, надо это число разделить на наименьший делитель. Поэтому наибольший делитель равен (32004 + 6) : 3 = 32003 + 2. Ответ: 32003 + 2. Свойства остатков. Мы уже знаем, что для любого натурального числа  n  существует представление его в виде n=km + r, где 0 r