Задача о взаимно простых числах

1. Сколько неупорядоченных пар взаимно простых чисел среди 2,3,...,30?

Решение: если воспользоваться функцией Эйлера φ(n)φ(n). Для её вычисления имеется формула, а сама она показывает количество чисел списка 11, 22,..., nn, взаимно простых с nn.

Удобно временно добавить единицу, и просуммировать значения φ(2)+φ(3)+…+φ(30)φ(2)+φ(3)+….+φ(30), вычитая в конце 29, так как пары с единицей мы не берём. Вместо формулы можно опираться на свойства: для простых чисел pp получается φ(p)=p−1φ(p)=p−1, и эти данные можно сразу внести в таблицу. Для степеней простых выполняется равенство φ(pk)=pk−pk−1φ(pk)=pk−pk−1, так как из общего количества надо вычесть количество чисел, делящихся на pp. Теперь вносим данные для степеней 2, 3 и 5.

Для остальных чисел пользуемся свойством мультипликативности функции: если nn разложить в произведение степеней простых, то φ(n)φ(n) будет равно произведению значений функции от этих сомножителей. Далее всё складываем, вычитаем 29, и получаем ответ.

2. Какое наибольшее число простых чисел может быть среди 15 последовательных натуральных чисел, больших 2?

Решение

Очевидно, простые числа нужно искать среди нечетных. Из 15 последовательных натуральных чисел имеется 7 или 8 нечетных. Среди любых трех последовательных нечетных чисел ровно одно делится на 3 (докажите!), поэтому среди 7 или 8 последовательных нечетных натуральных чисел имеются 2 или 3 числа, делящихся на 3. Если их отбросить, то останется 5 или 6 нечетных чисел. Нужно еще убедиться, что 6 простых чисел возможны. Например, если взять такие 15 последовательных натуральных чисел: 3,4, 5, 6,...,17, то среди них 6 простых: 3,5,7,11,13,17.

3. Найдите все натуральные a, при которых число а2 – 10 a + 21 простое.

Решение

Разложим этот квадратный трехчлен на линейные множители: а2 – 10 a + 21=(а-3)(а-7) Отсюда видно, что данное число, вообще говоря, составное. Когда один из множителей равен 1, а другой — простому числу или когда один из них равен — 1, а другой равен — р, где число р — простое. Переберем все случаи.

1)Пусть а-3= 1. Тогда а = 4, откуда а -7 = -3. Получилось, что число а2 – 10а + 21 отрицательно. Значит, этот случай невозможен.

2)Пусть а-7= 1. Тогда а = 8, а - 3 = 5, где 5 — число простое. Следовательно, значение а = 8 удовлетворяет требованию задачи.

3) Положим а — 3 = — 1. В этом случае а = 2, а — 7 = — 5. Так как число 5 — простое, то значение а = 2 также подходит.

4) Пусть а- 7 = -1. Тогда а = 6, а — 3 = 3. Поскольку здесь (а — 3)(а — 7) < 0, то этот случай невозможен. Ответ: 8,2.

Вывод: в процессе выполнения лабораторной работы были изучены алгоритмы решения задачи коммивояжера и P-сложных задач. Получены навыки работы с P и NP-трудными задачами.