ЕГЭ-2019. Математика. Задача 19 (проф. ур.)_Вольфсон_2019 -102с.. Ежедневно, 10. 0020. 00, кроме воскресеньяабрис рф Москва 8 (495) 2296759СанктПетербург 8 (812) 3270450
 Скачать 0.66 Mb.
|
|
§ . НОД и НОК. Основная теорема арифметики Диагностическая работа Найдите наибольший общий делитель и наименьшее общее кратное чисел 462 и На какое натуральное число, большее 1, можно сократить дробь + 7 7n + при натуральных значениях Сумма двух натуральных чисел равна 240, а их наибольший общий делитель равен 30. Найдите эти числа. 4. Найдите наименьшее общее кратное чисел 2011! и 2009! + Произведение двух чисел, каждое из которых не кратно 10, равно. Найдите сумму этих чисел. Краткая теоретическая справка Определение. Наибольшим общим делителем нескольких целых чисел (не все из которых равны 0) называется наибольшее натуральное число, на которое делится каждое из этих чисел. Можно дать равносильное определение. Определение. Наибольшим общим делителем нескольких целых чисел (не все из которых равны 0) называется натуральный общий делитель этих чисел, кратный любому их общему делителю. Примером натурального числа, на которое делится каждое из нескольких целых чисел, является число 1, поэтому множество общих делителей нескольких целых чисел непусто. Обозначение: НОД(a 1 ; …; a n ) или, если нет риска перепутать, просто Например, НОД(2; 4; 6; 8) = Напомним (см. § ), что натуральные числа называются взаимно простыми (если их больше двух, то иногда говорят взаимно простыми в совокупности, если их наибольший общий делитель равен 1. § . НОД и НОК. Основная теорема арифметики Свойства наибольшего общего делителя (Все фигурирующие в свойствах числа предполагаются целыми. Наибольший общий делитель нескольких целых чисел равен наибольшему общему делителю их модулей. Если d = НОД(a; b), то существуют такие целые числа x и y, что выполнено равенство d = ax + by. . Если числа a, b, c и q связаны равенством a=bq+c, то НОД(a; b)= = НОД(b; c). В частности, НОД(a; b) = НОД(a + b; b). . Частные отделения нескольких натуральных чисел на наибольший общий делитель этих чисел взаимно простыв совокупности. Чтобы найти наибольший общий делитель двух натуральных чисел, применяют алгоритм Евклида. А именно делят с остатком большее из чисел на меньшее, затем делят меньшее число с остатком на полученный остаток, а затем делят полученные остатки с остатком друг на друга до тех пор, пока остатки не поделятся нацело. Последний ненулевой остаток будет равен наибольшему общему делителю двух чисел. Пример. Найдём (2576; 154): 1) 2576 = 154 · 16 + 112; 2) 154 = 112 · 1 + 42; 3) 112 = 42 · 2 + 28; 4) 42 = 28 · 1 + Так как 28 кратно 14, получаем, что (2576; 154) = Определение. Наименьшим общим кратным нескольких ненулевых целых чисел называется наименьшее натуральное число, кратное каждому из этих чисел. Для данных ненулевых целых чисел существует общее кратное (например, произведение этих чисел, поэтому множество общих кратных нескольких ненулевых целых чисел непусто. Можно дать равносильное определение. Определение. Наименьшим общим кратным нескольких натуральных чисел называется общее кратное этих чисел, на которое делятся всеобщие кратные этих чисел. Обозначение: НОК[a 1 , …, a k ] или, если нет риска перепутать, просто, Теорема. Справедливо равенство (a; b) · [a; b] = Основная теорема арифметики и количество делителей. Каждое натуральное число n > 1 имеет единственное с точностью до § . НОД и НОК. Основная теорема арифметики порядка множителей) разложение на простые множители = p α 1 1 p α 2 2 · … · p α k k (p 1 , p 2 , …, p n — попарно различные простые числа, α 1 , α 2 , …, натуральные числа. Данная форма записи называется канонической формой записи числа Количество натуральных делителей числа n, записанного в канонической форме, равно (α 2 + 1) · … · (Сумма всех натуральных делителей числа n, записанного в канонической форме, равна 1 − 1 p 1 − 1 · p α 2 + 1 2 − 1 p 2 − 1 · … · p α k + 1 k − 1 p k − 1 .. НОД и НОК Примеры решения задач 1. Найдите наименьшую дробь, при делении которой на каждую из дробей и получаются натуральные числа. Решение. Пусть эта дробь, причём пусть она несократима. Требуется, чтобы a 14 · и a 21 · были натуральными числами. Так как и b взаимно просты, это значит, что 25 .. b, a 14, 40 .. b, a 21. Тогда минимальное a, удовлетворяющее этим условиям, — это 42, а максимальное это Докажите, что дробь + 1 30n + 2 несократима ни при каких натуральных Решение. Нам достаточно доказать, что 12n + 1 взаимно просто с 30n + 2. Пусть это не так. Тогда пусть (12n + 1) .. p и (30n + 2) Заметим, что тогда (30n + 2 − 2(12n + 1)) .. p, те. Это значит, что p — это либо делитель числа n, либо делитель числа 6. Заметим, что 12n + 1 взаимно простои си с n, так как 12n .. n и 12n .. 6, поэтому не может быть делителем числа n или числа Значит, такого p не существует, следовательно, данная в условии дробь несократима. 3. Натуральные числа m и n взаимно просты. Какие значения может принимать НОД чисел 4m + 3n и 6m + Решение. Заметим, что + 5n) − (4m + 3n)) .. . НОД(6m+5n, 4m+3n), § . НОД и НОК. Основная теорема арифметики т. е + n) .. . НОД(6m+5n, Теперь заметим, что, так как m и n взаимно просты, m + n взаимно простои си с n. Далее, 6m + 5n = 3 · 2(m + n) − n, значит, 6m + взаимно просто с m + n, так как m + n взаимно просто с n. Аналогично взаимно просто с m + n. Значит, единственный возможный общий делитель чисел 6m + 5n и 4m + 3n — это 2. Следовательно, НОД(6m + 5n, 4m + 3n) не может быть больше 2. Значение 2, конечно же, достигается, например, если m = 1, а n = Найдите все пары натуральных чисел, разность которых равна, а их НОК равно Решение. Имеем 360 = 2 3 · 3 2 · 5. Пусть a и b — искомые числа. Заметим, что у этих чисел нет никаких простых делителей, кроме, 3 итак как иначе их НОК на них бы тоже делилось. Пусть = 2 x · 3 y · 5 z , b = 2 m · 3 n · 5 k . Тогда НОК(a, b) = 2 max(x,m) · 3 max( y,n) · Значит, нам необходимо лишь, чтобы выполнялось равенство max(x, m) = 3, max( y, n) = 2, max(z, k) = Так как разность чисел a и b делится на 3 и хотя бы одно из них делится на 3, то они оба делятся на 3. Аналогично оба числа делятся на 2, но только одно из них делится на 5, иначе 66 делилось бы на Аналогично только одно из них может делиться назначит, одно из них делится на 8, а другое только на 2. Пусть, например, a делится на 5. Тогда переберём всевозможные и b: a может быть равно, 120, 360, 90, а b может быть равно 6, 72, 18, 24. Простым перебором выясняем, что подходит только пара 90 и Можно было также сразу заметить что a — делитель числа больший 66 (72, 90, 120, 180, 360), что упростит перебор вариантов. Чтобы обойтись без перебора, можно сначала доказать (как в при- ведённом решении, что оба числа делятся на 6 и других общих делителей нет (если бы существовал ещё один общий делитель, тона него делилась бы разность чисел, те. он мог быть равен только 11, нона не делится. Значит, НОД(a; b) = 6, а тогда, так как произведение наименьшего общего кратного двух чисел на их наибольший общий делитель равно произведению этих чисел, получаем, что произведение чисел равно 2160, а затем решаем систему уравнений. 5. Найдите НОД 2 30 − 1, 2 40 − 1 § . НОД и НОК. Основная теорема арифметики Решение. Заметим, что разность двух чисел делится на их НОД. Тогда 2 40 − 1 − 2 30 − 1 ... НОД 2 40 − 1, 2 30 − 1 , 2 30 2 10 − 1 ... НОД 2 40 − 1, 2 30 − Число 2 30 , очевидно, взаимно просто с нашими числами (оба они нечётные), следовательно, 2 10 − 1 .. . НОД 2 40 − 1, 2 30 − 1 . Заметим, что НОД этих чисел тоже делится на 2 10 − 1, так как 40 − 1 = 2 20 − 1 2 20 + 1 = 2 10 − 1 2 10 + 1 2 20 + 1 ... 2 10 − 1, 2 30 − 1 = 2 10 − 1 2 20 + 2 10 + 1 ... 2 10 − Значит, НОД этих чисел и есть в точности 2 10 − 1 = Найдите наибольший общий делитель всех чисел вида p 2 − где p — простое число, большее 3, но меньшее Решение. Заметим, что p 2 − 1 делится на 3 при любом p, не делящемся на 3 (квадрат по модулю 3 даёт остаток 1 · 1 либо остаток 2, что по модулю 3 одно и тоже. Значит, наши числа все будут делиться на 3. Заметим также, что они все будут делиться на 8, так как при делении на 8 может давать только остаток 1 (оно сравнимо либо с 1 · 1, либо с 3 · 3, либо с 5 · 5, либо с 7 · 7, что по модулю одно и тоже. Но заметим, что больше ни на что наш общий делитель делиться не может, так как 5 2 − 1 = 24 = 3 · 8, а общий делитель должен быть меньше либо равен каждому из чисел. Значит, искомый общий делитель — это Подготовительные задачи 1. Найдите НОД чисел 72 и Найдите НОД чисел 2 и Найдите НОД чисел 384 и Найдите НОД чисел 787878 и Найдите НОК чисел 12 и Найдите НОК чисел 4 и Найдите НОК чисел 120 и Сколько существует пар натуральных чисел, НОК которых равно 2000? 9. Найдите наименьшую дробь, при делении которой на каждую из дробей 66 , 28 и получаются натуральные числа. 10. На какое число и при каких натуральных значениях n сократи- ма дробь + 4 2n + 5 ? § . НОД и НОК. Основная теорема арифметики 11. Натуральные числа m и n взаимно просты. Какие значения может принимать НОД чисел m + n и m 2 − mn + Придумайте два различных натуральных числа, произведение которых делится на их сумму. Основные задачи 1. Какие значения может принимать НОД(x, x + 2), где x — натуральное число? 2. Известно, что x, y ∈ N, НОД(x, y) = 13, НОК(x, y) = 52. Найдите и Найдите все пары натуральных чисел, сумма которых равна а их НОД равен Найдите все пары натуральных чисел, сумма которых равна а частное отделения их НОК на их НОД равно Все обыкновенные правильные и несократимые дроби, числители и знаменатели которых — двузначные числа, упорядочили по возрастанию. Между какими двумя последовательно расположенными дробями находится число Среди обыкновенных дробей с положительными знаменателями, расположенных между числами и 36 , найдите такую, знаменатель которой минимален. 7. Какие значения может принимать НОД(x, y), если известно, что при увеличении числа x на 6 НОД увеличивается в 4 раза? 8. Найдите НОД всех девятизначных чисел, в записи каждого из которых каждая из цифр 1, 2, …, 9 встречается ровно по одному разу. 9. Найдите НОД чисел 11111111 (8 единиц) и 11…111 (2012 еди- ниц). 10. На какое число и при каких натуральных n сократима дробь 1 n 4 + n 3 − n 2 + n + Докажите, что дробь + 1 n 4 + n 3 + 3n 2 + 2n + 1 несократима ни при каких натуральных Чему равен НОД всех чисел 4 n+2 + 5 при натуральных значениях При каком наименьшем натуральном n каждая из дробей + 3 , 3 n + 4 , …, 32 n + 33 несократима? 14. Натуральные числа a, b и c таковы, что НОК(a, b) = 60, НОК(a, c) = 270. Найдите НОК(b, c). § . НОД и НОК. Основная теорема арифметики 15. Найдите все натуральные числа, не представимые в виде суммы двух взаимно простых чисел, отличных от единицы. 16. На клетчатой бумаге нарисован прямоугольник размера m × стороны которого идут по линиям сетки. Через какое количество узлов сетки проходит эта диагональ и насколько частей она разбивается линиями сетки, если аи взаимно простые натуральные числа, б) m и n — произвольные натуральные числа? 17. По окружности радиуса R катится колесо радиуса r (R, r ∈ В колесо вбит гвоздь, который, ударяясь об окружность, оставляет на ней отметки. Сколько всего таких отметок оставит гвоздь Сколько раз колесо прокатится по окружности, прежде чем гвоздь попадёт в уже отмеченную ранее точку? 18. Пусть n 1 , n 2 , …, n 10 — различные натуральные числа, сумма которых равна 2013. Какое наибольшее значение может принимать наибольший общий делитель этих 10 чисел. Основная теорема арифметики. Делители Примеры решения задач 1. Найдите НОД и НОК чисел a и b, где a=2 8 ·3 10 ·5·7 2 , а b=2 5 ·3 2 ·7 Решение. НОК чисел — это произведение всех простых делителей обоих чисел, взятых в максимальной из степеней, в которых они встречаются в обоих числах. Тогда НОК(a; b) = 2 8 · 3 10 · 5 · 7 3 . НОД чисел — это произведение всех простых делителей обоих чисел, взятых в минимальной из степеней, в которых они встречаются в обоих числах. Тогда НОД(a; b) = 2 5 · 3 2 · 7 Докажите, что составное число n всегда имеет делитель, не больший Решение. От противного пусть все делители числа n больше p n. Возьмём два таких делителя a и. И a, и n a будут больше pn. Тогда = p n · p n < a · n a = n. Получается, что n < n. Но это противоречие, значит, наше предположение неверно, те. найдётся такой делитель числа n, что он не будет превосходить Докажите, что число является квадратом натурального числа тогда и только тогда, когда у него нечётное число делителей. Решение 1. Все делители натурального числа n разбиваются на пары так, что произведение делителей каждой пары равно n. Таким образом, количество делителей данного натурального числа чётно, за исключением случая, когда водной паре оба числа совпадают (оче- § . НОД и НОК. Основная теорема арифметики видно, что больше одной такой пары быть не может. В этом случае число n равно произведению двух одинаковых делителей из этой пары, те. является точным квадратом. Решение 2. Пусть число n записано в канонической форме = p α 1 1 p α 2 2 · … · Ясно, что число n является точным квадратом тогда и только тогда, когда все показатели степеней α i , в которых входят в разложение простые множители, чётны. (Если n = и m = p α 1 1 p α 2 2 · … · p α k k , то = p 2α 1 1 p 2α 2 2 · … · p 2α k k .) С другой стороны, количество делителей числа равно N = (α 1 + 1) · (α 2 + 1) · … · (α k + 1). Из этой формулы следует, что число делителей N нечётно тогда и только тогда, когда все числа α 1 , …, α n чётны, что и требовалось доказать. 4. Найдите все натуральные числа, последняя цифра которых и которые имеют ровно 15 различных натуральных делителей. Решение. Воспользуемся формулой о количестве делителей у числа, если a = p α 1 1 p α 2 2 · … · p α n n . Количество делителей равно (α 2 + 1) · … · (Тогда в нашем случае имеется такое равенство (α 2 + 1) · … · (α n + 1) = Заметим, что каждая скобка в произведении не меньше двух, поэтому скобок может быть только две, причём одна из них равна 3, а другая Тогда в разложении нашего числа имеются только два простых множителя, один вой степени и один в й степени. Заметим, что наше число делится на 10 (так как оно кончается на 0), а значит, делится на 2 и на 5. Это означает, что два простых множителя в нашем числе и есть двойка и пятёрка. Тогда число может быть только двух видов 2 · 5 или 2 4 · 5 Подготовительные задачи 1. Разложите на простые множители числа 111, 1 111, 11 111, 111 111, 1 111 Произведение двух натуральных чисел, каждое из которых не делится нацело на 10, равно 1000. Найдите их сумму. 3. Существует ли целое число, произведение цифр которого равно А 2010? А Сколько двоек присутствует в разложении на простые множители числа а) 5!; б) 20!; в) n!? § . НОД и НОК. Основная теорема арифметики 5. Докажите, что число является квадратом натурального числа тогда и только тогда, когда каждый его простой делитель входит в его разложение в чётной степени. 6. Докажите, что произведение первых n простых чисел не является полным квадратом. 7. Найдите количество натуральных делителей у числа а) б) 20; в) 500; г) 2000; д) Найдите сумму натуральных делителей у числа а) 10; б) в) 500; г) Основные задачи 1. Множество A состоит из натуральных чисел. Количество чисел в A больше семи. Наименьшее общее кратное всех чисел из A равно. Для любых двух чисел из A их наибольший общий делитель больше единицы. Произведение всех чисел из A делится на 1920 и не является квадратом никакого целого числа. Найдите все числа, из которых состоит множество Найдите наименьшее натуральное число n, для которого не делится на Докажите, что нечётное число, являющееся произведением n различных простых сомножителей, можно представить в виде разности квадратов двух натуральных чисел ровно различными способа- ми. 4. Определите, на какую наибольшую натуральную степень числа делится Найдите наименьшее натуральное число, половина которого квадрат, треть — куба пятая часть — пятая степень. 6. Найдите все натуральные числа, которые делятся на 42 и имеют ровно 42 натуральных делителя |