НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ. АЛГОРИТМ ЕВКЛИДА

НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ. НАИБОЛЬШИЙ  ОБЩИЙ ДЕЛИТЕЛЬ. АЛГОРИТМ ЕВКЛИДА 1. Спортсменов, приехавших на соревнования, можно построить в колонну по 4 или в колонну по 6. Сколько спортсменов приехало на соревнования, если известно, что их больше 90, но меньше 100? Р е ш е н и е . Найдем НОК(4; 6) = 12. Искомое число должно делиться на 12 и быть больше 90, но меньше 100. Разделим 100 на 12 с остатком: 100 = 12 ∙  8 + 4. Таким образом, на соревнования приехало 96 спортсменов. 2. Каково должно быть наименьшее количество участников парада, чтобы их можно было построить как в колонну по 6, так и в колонну по 7 человек? Р е ш е н и е . НОК(6; 7) = 42. 3. Найдите наименьшее пятизначное число, которое делится на 3, 7, 11 без остатка. Р е ш е н и е . Искомое число можно представить в виде 3 ∙  7 ∙  11 ∙  а, причём а  – натуральное   число   и  а  ≥ 10000 : (3 ∙   7 ∙   11). Таким образом,  а  = 44, и искомое число – 10164. 4. [19] Найдите наименьшее число, которое при делении на 3, на 5 и на 7 дает в остатке 1. Р е ш е н и е . Это число 3 ∙  5 ∙  7 + 1, то есть 106. 5. [19] Найдите наименьшее число, которое при делении на 3, на 4, на 5 и на 7 дает в остатке 2. Р е ш е н и е . Это число 3 ∙  4 ∙  5 ∙  7 + 1, то есть 422. 6. Найдите наименьшее число, которое при делении на 2, 3, 4, 5, 6, 7, 8, 9 дает в остатке 1. Р е ш е н и е . Это число 5 ∙  7 ∙  8 ∙  9 + 1, то есть 2521. 7. Для новогодних подарков приготовили 48 мандаринов и 64 конфеты. В какое наибольшее число подарков можно разложить эти мандарины и конфеты, чтобы во всех подарках было поровну мандаринов и конфет? Р е ш е н и е .   Найдём   НОД(48,   64)   =   16.   Таким   образом,   получится   16 подарков по 3 мандарина и 4 конфеты в каждом. 8. [4] Числа 100 и 90 разделили на одно и то же число, в результате в первом случае получили остаток 4, а во втором – 18. На какое число делили? Р е ш е н и е . Если при делении 100 на искомое число получили остаток 4, то 96 делится на это число без остатка. Если при делении 90 на искомое число получили   остаток   18,   то   72   делится   на   это   число   без   остатка.   Кроме   того, делитель больше остатка, то есть искомое число больше 18.  Найдем делители 96 и 72: 96 = 2 ∙  2 ∙  2 ∙  2 ∙  2 ∙  3 и 72 = 2 ∙  2 ∙  2 ∙  3 ∙  3. НОД (96; 72) = 2 ∙   2 ∙   2 ∙   3 = 24 – искомое число. Любой общий делитель, меньший 24, не будет больше 18, а значит, не удовлетворяет условию задачи.  9. Четверо девочек выбирали водящую с помощью считалки. Та, на которую падало последнее слово, выходила из круга, и счёт повторялся вновь. Считающая девочка каждый круг начинала с себя и в результате стала водящей, причём счёт каждый раз кончался перед ней. Какое наименьшее число слов могло быть в считалке? Р е ш е н и е . Если, когда девочек было 4, счет закончился на 1­м круге, то слов в считалке было 4, если на 2­м, то 8. Аналогично: 12, 16, 20… То есть число слов в считалке должно делиться на 4. Если, когда девочек было 3 и 2, счет закончился перед водящей, то число слов в считалке должно делиться на 3 и на 2. Таким образом, нужно найти наименьшее число, делящееся на 3 и на 4 (оно будет делиться и на 2). Это число 12. 10. Найдите с помощью алгоритма Евклида: а) НОД(3139, 1752); б) НОД(1261; 3432); в) НОД(14406; 16317).  О т в е т . а) 73; б) 13; в) 147. 11. [5] Найдите наибольший общий делитель чисел 2n+13 и n+7. Р е ш е н и е . НОД(2n + 13, n + 7) = НОД(n + 7, n + 6) = НОД(n + 6, 1) = 1. 12. [5] Докажите, что дробь  несократима ни при каком натуральном n. Р е ш е н и е . Найдем НОД(30n  + 2, 12n  + 1) = НОД(18n  + 1, 12n  + 1) == НОД(12n + 1, 6n) = НОД(6n + 1, 6n) = НОД(6n, 1) = 1. Таким образом, данная дробь несократима ни при каком натуральном n.