Олимпиадная задача по теории чисел: делимость, простые делители и квадрат (Сендеров В. А.)

  Имеем  (z – 1)(z + 1) = x^y,  НОД(z – 1, z + 1) = 1  при нечётном x,  НОД(z – 1, z + 1) = 2  при чётном x.

  В первом случае  z – 1 = u^y,  z + 1 = v^y,  где  u, v ∈ N,  отсюда  v^y – u^y = 2.  Но, поскольку  v > u,  y > 1,  то

v^y – u^y = (v – u)(v^y–1 + ... + u^y–1) ≥ (v – u)(2^y–1 + 1) ≥ 3.  Противоречие:  2 ≥ 3.

  Во втором случае одно из чисел  z – 1  и  z + 1  чётно, но не делится на 4, а второе делится на 2^y–1 и не делится на 2^y. Таким образом,  A = 2u^y,  B = 2^y–1v^y  (u, v – нечётные натуральные числа), где A и B равны, в некотором порядке, числам  z – 1  и  z + 1  (при этом  AB = x^y).  Итак,  |2u^y – 2^y–1v^y| = 2,

|u^y – 2^y–2v^y| = 1.  Отсюда, при некотором выборе знака,  u^y ± 1 = 2^y–2v^y.

  Заметим, что  u > 1.  В самом деле, если  u = 1,  то  A = 2 = z – 1,  z = 3,  x = 2,  что противоречит условию. Кроме того, число y нечётно (в противном случае

y = 2n,  z² – (xⁿ)² = 1,  что невозможно.   Лемма 1. Пусть  a ≥ 2,  p – нечётное простое число. Тогда число  a^p – 1  имеет хотя бы один простой делитель, не являющийся делителем числа  a – 1.

  Доказательство.  a^p – 1 = (a – 1)(a^p–1 + a^p–2 + ... + a² + a + 1) = (a – 1)b.

  Докажем вначале, что числа  a – 1  и b не могут иметь общего делителя q, отличного от 1 и от p. Действительно, если  a ≡ 1 (mod q),  то  b ≡ p (mod q).  Поэтому b делится на q лишь при  q = 1 или p.

  Осталось доказать, что случай, когда  b = pⁿ  и  a – 1  делится на p невозможен. Поскольку  b > p,  достаточно доказать, что b не делится на p².

  Если  a = p^αk + 1,  где k не делится на p, то  a^p = (p^αk + 1)^p = 1 + p^α+1k + ½ p(p – 1)p^2αk² + ... = 1 + p^α+1k + p^α+2d,  где d целое. Отсюда  a^p – 1 = p^α+1(k + pd),  bk = p(k + pd),  то есть b делится на p и не делится на p².   Лемма 2. Пусть  a ≥ 2,  p – нечётное простое число и выполнено хотя бы одно из неравенств  a ≠ 2  и  p ≠ 3.  Тогда  a^p + 1  имеет простой делитель, не являющийся делителем числа  a + 1.

  Доказательство.  a^p + 1 = (a + 1)(a^p–1 – a^p–2 + ... + a² – a + 1) = (a + 1)b.

  Как в лемме 1 доказывается, что числа  a + 1  и b не могут иметь общего делителя r, отличного от 1 и от p.

  Осталось доказать, что невозможен случай, когда  b = pⁿ,  a + 1  делится на p.

  Заметим, что  b ≥ a² – a + 1 ≥ a + 1 ≥ p.  Из условий леммы следует, что среди неравенств этой цепочки есть строгие, то есть  b > p.  С другой стороны, как и в доказательстве леммы 1, можно получить, что число b не делится на  p².   Из доказанных лемм следует, что правая часть равенства  u^y ± 1 = 2^y–2v^y  имеет не менее  q + 1  различных простых делителей. Поскольку  НОД(u, 2v) = 1,

u > 1,  получаем отсюда неравенство задачи.

Ответ задачи отсутствует