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

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

Условие

Дано равенство  (am1 – 1)...(amn – 1) = (ak1 + 1)...(akl + 1),  где a, n, l и все показатели степени – натуральные числа, причём  a > 1.
Найдите все возможные значения числа a.


Решение

  Предположим, что при некотором  a > 3  A = (am1 – 1)...(amn – 1) = (ak1+1)...(akl + 1).
  Докажем сначала, что как любое mi, так и число  a – 1  являются степенями двойки. Пусть γ – нечётный делитель числа mi, а p – любой простой делитель числа  aγ – 1.  Тогда в правом произведении найдётся множитель  akj + 1,  кратный p. Поэтому число  (aγkj + 1) – (aγkj – 1) = 2  кратно p, то есть все простые делители числа  aγ – 1  – двойки и  (aγ–1 + ... + a + 1)(a – 1) = aγ – 1 = 2s.  Поскольку  a > 3,  то  s > 1  и γ нечётно, поэтому выражение в первой скобке – нечётный делитель числа 2s. Значит, γ и  a – 1 = 2s.  В частности,  a – 1  делится на 4, поэтому  ak + 1 ≡ 2 (mod 4).
  Каждое число в левой части исходного равенства представляется в виде  a2d – 1 = (a – 1)(a + 1)(a² + 1)(a4 + 1)...(a2d–1 + 1) = 2s·2da0...ad–1 , где
ai = ½ (a2i + 1)  – нечётные числа. Заметим, что при  m > n  число  a2m – 1  делится на  a2n + 1,  поэтому  НОД(am, an) ≤ (a2m + 1) – (a2m – 1) = 2;  поскольку ai нечётны, они попарно взаимно просты. Пусть q – максимальная степень двойки, входящая в mi или kj. Тогда     причём
N > N0 + ... + Nq,  так как это справедливо для любого представления  a2d – 1.
  Ни один из множителей  akj + 1  не делится на 4, поэтому их в представлении числа A не меньше N. Но каждое из них делится на одно из чисел ai: если  kj = 2rb,  где b нечётно, то  akj + 1  делится на ar. Поскольку  N > N0 + ... + Nq,  то на какое-то число ai делится больше, чем Ni чисел  akj + 1,  а следовательно, A делится на большую степень ai, чем Ni. Противоречие с тем, что ai нечётны и попарно взаимно просты.


Ответ

2 и 3.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 66
Год 2003
вариант
Класс 11
задача
Номер 7

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

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