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

Проект МЦНМО
при участии
школы 57
Задача 109752
Темы:    [ Основная теорема арифметики. Разложение на простые сомножители ]
[ НОД и НОК. Взаимная простота ]
[ Принцип крайнего (прочее) ]
Сложность: 5-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Автор: Джукич Д.

Найдите все такие нечётные натуральные  n > 1,  что для любых взаимно простых делителей a и b числа n число  a + b – 1  также является делителем n.


Решение

  Пусть p – наименьший простой делитель числа n. Представим n в виде pmk, где k не делится на p. По условию число  p + k – 1  является делителем n.
  Если  (p + k – 1, k) > 1,  то  (p – 1, k) = (l, k) > 1.  Таким образом, число k имеет какой-то делитель d,  2 ≤ d ≤ p – 1.  Противоречие с выбором числа p. Следовательно,  p + k – 1 = pα.
  Пусть  α ≥ 2.  Тогда p² и k – взаимно простые делители числа n, то есть  p² + k – 1  – делитель числа n. При этом  p² + k – 1  взаимно просто с k, поскольку в противном случае k имеет общий делитель с  p² – 1 = 2(p – 1)· ½(p + 1),  что снова противоречит выбору числа p. Значит,  p² + k – 1 = pβ,  где  β ≥ 3.  Но тогда  pβ = p² + k – 1 = p² + (p + k – 1) – p = p(p + pα–1 – 1),  что не делится на p². Противоречие.
  Следовательно,  k = 1,  то есть  n = pm.  Нетрудно убедиться, что все такие числа удовлетворяют условию.


Ответ

n – степень нечётного простого числа.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2001
Этап
Вариант 5
Класс
Класс 9
задача
Номер 01.5.9.8

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

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