Примени математику (Гашков, Сергеев) - страница 29
127, 131, 137, 139, 149. 4.10. Число не делится ни на 2, ни на 3, ни на 5 в том и только в том случае, если его остаток от деления на 30=2x3x5 не делится ни на одно из этих чисел. Так как
то, вычеркнув из всех возможных значений остатков от деления на 30, т. е. из чисел от 0 до 29, числа, кратные 2, 3 или 5, мы получим число 1 и все простые числа (см. задачу 4.7). Следовательно, набор искомых остатков выглядит так:
1, 7, 11, 13, 17, 19, 23, 29. Благодаря этому наблюдению при отыскании простых чисел (больших 5) можно выписывать не все числа подряд, а только те, которые дают указанные здесь восемь остатков от деления на 30, что позволяет сэкономить работу по выписыванию в >30/>8 = 3,75 раза. Именно так можно было поступить, например, при решении задачи 4.9.
4.11. Так как
473, 479, 481, 487, 491, 493, 497, 499, 503, 509, 511, 517. Из этих чисел теперь остается только вычеркнуть числа, кратные 7 (497, 511), кратные 11 (473, 517), кратные 13(503), кратные 17 (493) и кратные 19 (таких нет), и получить окончательный набор
479, 481, 487, 491, 499, 509.
§ 5. Вокруг наибольшего общего делителя
Одна из простейших задач, для решения некоторой понадобится найти наибольший общий делитель пары натуральных чисел а и b,- это 1 задача сокращения дроби >a/>b. Напомним, что если числа а и b делятся на одно и то же натуральное число d, то число d называется общим делителем пары чисел а и b. Любая пара натуральных чисел имеет хотя бы один общий делитель (а именно, d = 1), причем любой общий делитель не превосходит каждого из этих чисел. Поэтому среди всех делителей чисел а и b можно выбрать наибольший общий делитель, который обозначается через (а, b), например (20, 100) = 20, (65, 39) = 13. Если (а, b) = 1, то числа а и b называются взаимно простыми. При этом взаимно простые числа а и b совсем не обязательно сами по себе должны быть простыми числами; так, (33, 35) = 1, но 33 = 3*11 и 35 = 5*7.
У читателя, возможно, сложилось впечатление, что нахождение наибольшего общего делителя пары чисел представляет собой очень простую задачу. Ведь если разложить на простые множители каждое из данных чисел, то сразу станет ясно, как составить из этих простых множителей наибольшее произведение, на которое делятся оба данных числа. Однако все дело в том, что разложить число на простые множители иногда бывает довольно трудно, тогда как нахождение наибольшего общего делителя можно осуществить намного проще - с помощью несложной процедуры. Эта процедура известна уже более 2 тысяч лет и носит название