ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 111776
Темы:    [ Делимость чисел. Общие свойства ]
[ НОД и НОК. Взаимная простота ]
[ Основная теорема арифметики. Разложение на простые сомножители ]
Сложность: 4
Классы: 8,9,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, откуда и следует утверждение задачи.

Источники и прецеденты использования

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2007
Этап
Вариант 4
Класс
Класс 10
задача
Номер 07.4.10.7

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .