Олимпиадная задача по теории чисел о взаимно простых числах для 8–10 класса
Задача
Дано натуральное число n > 6. Рассматриваются натуральные числа, лежащие в промежутке (n(n – 1), n²) и взаимно простые с n(n – 1).
Докажите, что наибольший общий делитель всех таких чисел равен 1.
Решение
Пусть p – минимальное простое число, на которое не делится n(n – 1). Покажем, что p < n – 1. Действительно, рассмотрим числа n – 2, n – 3,
n – 4. Среди них не больше одного числа, кратного 3, и не больше одного числа, являющегося степенью двойки (так как n – 4 > 2). Таким образом, у одного из них есть нечётный простой делитель q, больший 3. Числа n и n – 1 не могут делиться на q, поэтому p ≤ q ≤ n – 2.
Ясно, что среди рассматриваемых чисел есть число A = n(n – 1) + 1. Из доказанного следует, что среди них также есть число B = n(n – 1) + p.
НОД(A, B) = НОД(A, B – A) = НОД(A, p – 1) = 1, так как согласно выбору p каждый простой делитель числа p – 1 является делителем числа
n(n – 1) = A – 1 и потому взаимно прост с A. Итак, НОД уже двух чисел A и B равен 1, откуда и следует утверждение задачи.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь