Разделы 
Дополнительно
Задача по математике - 2046
2019-01-23 
Натуральные числа $x, y, z (x > 2, y > 1)$ таковы, что $x^y + 1 = z^2$. Обозначим через $p$ количество различных простых делителей числа $x$, через $q$ - количество различных простых делителей числа $y$. Докажите, что $p \geq q + 2$.
Решение:
Имеем $(z - 1)(z + 1) = xy,\:НОД(z - 1,z +1) = 1$ при нечетном $x$, $\:НОД(z - 1, z +1) = 2$ при четном $x$. В первом случае $z - 1 = u^y, z + 1 = v^y,$ где $u,v \in \mathbb{N};$ отсюда $v^y - u^y = 2$. Но, поскольку $v > u, y > 1$, имеем $v^y - u^y = (v - u)(v^{y-1} + \cdots + u^{y-1}) \geq (v - u)(2^{y-1} + 1) \geq 3$. Противоречие: $2 \geq 3$. Значит, число $x$ четно. В этом случае одно из чисел $z - 1$ и $z + 1$ делится на 2 и не делится на 4, а второе делится на $2^{y-1}$ и не делится на $2^y$. Таким образом, $A = 2u^y, B = 2^{y-1}v^y (u, v$ - нечетные натуральные числа), где $A$ и $B$ равны, в некотором порядке, числам $z - 1$ и $z + 1$ (при этом $AB = x^y$). Получили $|2u^y - 2^{y-1}v^y \ = 2, |u^y - 2^{y-2}v^y| = 1$. Отсюда, при некотором выборе знака, $u^y \pm 1 = 2^{y-2}v^y$.
Заметим, что $u > 1$. В самом деле, если $u = 1,$ то$ A = 2, A = z - 1, z = 3, x = 2$ - противоречит условию. Кроме того, число $у$ нечетно, в противном случае, если $у = 2n, z^2 - (x^n)^2 = 1$, что невозможно.
Лемма 1. Пусть $a \geq 2, p$ - нечетное простое число. Тогда число $a^p - 1$ имеет хотя бы один простой делитель, не являющийся делителем числа $a - 1$.
Доказательство. Рассмотрим разложение
$a^p - 1 = (a - 1)(a^{p-1} + a^{p-2} + \cdots + a^2 + a +1) = (a - 1)b$.
Докажем вначале, что числа $a - 1$ и $b$ не могут иметь общего делителя $q$, отличного от 1 и от $p$. Действительно, если $a - 1$ делится на $q$, то и $a^m - 1$ делится на $q$ при любом натуральном $m$. Значит, $b = ql + p,$ где $l$ - некоторое целое число. Поэтому $b$ делится на $q$ лишь при $q = 1$ или $p$.
Таким образом, для завершения доказательства леммы осталось рассмотреть случай, когда $b = p^n$ и $a - 1$ делится на $p$. Докажем, что этот случай невозможен. Поскольку $b > p$, достаточно доказать, что $b$ не делится на $p^2$. Докажем это. Если $a = p^{ \alpha}k + 1$, где $k$ не делится на $p$, то
$а^p = (p^{ \alpha}k + 1)^p = 1 + p^{ \alpha +1}k + p \cdot \frac{p-1}{2}\cdot p^{2 \alpha }k^2 + \cdots = 1 + p^{ \alpha +1}k + p^{ \alpha +2}d$,
где $d$ целое. Отсюда $a^p - 1 = p^{ \alpha +1}(k + pd)$. Поскольку $k$ не делится на $p$, то очевидно, что $b$ делится на $p$ и не делится на $p^2$. Лемма доказана.
Лемма 2. Пусть $a \geq 2, p$ - нечетное простое число и выполнено хотя бы одно из неравенств $a \neq 2$ и $p \neq 3$. Тогда $a^p + 1$ имеет простой делитель, не являющийся делителем числа $a + 1$.
Доказательство. Рассмотрим разложение
$a^p + 1 = (a + 1)(a^{p-1} - a^{p-2} + \cdots + a^2 - a +1) = (a + 1)b$.
Докажем вначале, что числа $a +1$ и $b$ не могут иметь общего делителя $r$, отличного от 1 и от $p$. Действительно, если $a + 1$ делится на $r$, то и $a^k + 1$ делится на $r$ при любом нечетном $k$; если же $k = 2m$, то $a^k - 1$ делится на $a^2 - 1$, которое, в свою очередь, делится на $r$. Значит, $b = rl + p,$ где $l$ - некоторое целое число. Поэтому $b$ делится на $r$ лишь при $r = 1$ или $p$.
Таким образом, для завершения доказательства леммы осталось рассмотреть случай $b = p^n, a + 1$ делится на $p$. Докажем, что этот случай невозможен. Докажем вначале, что, как и в доказательстве леммы 1, $b > p$. Имеем $b \geq a^2 - a + 1 \geq a + 1 \geq p$. Из условий леммы следует, что среди неравенств этой цепочки есть строгие. С другой стороны, как и в доказательстве леммы 1, можно получить, что число $b$ не делится на $p^2$, что и завершает доказательство леммы.
Из доказанных лемм следует, что правая часть равенства $u^y \pm 1 = 2^{y-2}v^y$ имеет не менее $q +1$ различных простых делителей. Поскольку $\:НОД(u, 2v) = 1, u > 1$, получаем отсюда неравенство задачи.
Замечание. Фактически мы доказали следующее, более сильное, чем утверждение задачи,
Предложение. Пусть число $y$ разлагается в произведение $n$ отличных от 1 натуральных чисел. Тогда $x$ имеет не менее $n + 2$ различных простых делителей.
Натуральные числа $x, y, z (x > 2, y > 1)$ таковы, что $x^y + 1 = z^2$. Обозначим через $p$ количество различных простых делителей числа $x$, через $q$ - количество различных простых делителей числа $y$. Докажите, что $p \geq q + 2$.
Решение:
Имеем $(z - 1)(z + 1) = xy,\:НОД(z - 1,z +1) = 1$ при нечетном $x$, $\:НОД(z - 1, z +1) = 2$ при четном $x$. В первом случае $z - 1 = u^y, z + 1 = v^y,$ где $u,v \in \mathbb{N};$ отсюда $v^y - u^y = 2$. Но, поскольку $v > u, y > 1$, имеем $v^y - u^y = (v - u)(v^{y-1} + \cdots + u^{y-1}) \geq (v - u)(2^{y-1} + 1) \geq 3$. Противоречие: $2 \geq 3$. Значит, число $x$ четно. В этом случае одно из чисел $z - 1$ и $z + 1$ делится на 2 и не делится на 4, а второе делится на $2^{y-1}$ и не делится на $2^y$. Таким образом, $A = 2u^y, B = 2^{y-1}v^y (u, v$ - нечетные натуральные числа), где $A$ и $B$ равны, в некотором порядке, числам $z - 1$ и $z + 1$ (при этом $AB = x^y$). Получили $|2u^y - 2^{y-1}v^y \ = 2, |u^y - 2^{y-2}v^y| = 1$. Отсюда, при некотором выборе знака, $u^y \pm 1 = 2^{y-2}v^y$.
Заметим, что $u > 1$. В самом деле, если $u = 1,$ то$ A = 2, A = z - 1, z = 3, x = 2$ - противоречит условию. Кроме того, число $у$ нечетно, в противном случае, если $у = 2n, z^2 - (x^n)^2 = 1$, что невозможно.
Лемма 1. Пусть $a \geq 2, p$ - нечетное простое число. Тогда число $a^p - 1$ имеет хотя бы один простой делитель, не являющийся делителем числа $a - 1$.
Доказательство. Рассмотрим разложение
$a^p - 1 = (a - 1)(a^{p-1} + a^{p-2} + \cdots + a^2 + a +1) = (a - 1)b$.
Докажем вначале, что числа $a - 1$ и $b$ не могут иметь общего делителя $q$, отличного от 1 и от $p$. Действительно, если $a - 1$ делится на $q$, то и $a^m - 1$ делится на $q$ при любом натуральном $m$. Значит, $b = ql + p,$ где $l$ - некоторое целое число. Поэтому $b$ делится на $q$ лишь при $q = 1$ или $p$.
Таким образом, для завершения доказательства леммы осталось рассмотреть случай, когда $b = p^n$ и $a - 1$ делится на $p$. Докажем, что этот случай невозможен. Поскольку $b > p$, достаточно доказать, что $b$ не делится на $p^2$. Докажем это. Если $a = p^{ \alpha}k + 1$, где $k$ не делится на $p$, то
$а^p = (p^{ \alpha}k + 1)^p = 1 + p^{ \alpha +1}k + p \cdot \frac{p-1}{2}\cdot p^{2 \alpha }k^2 + \cdots = 1 + p^{ \alpha +1}k + p^{ \alpha +2}d$,
где $d$ целое. Отсюда $a^p - 1 = p^{ \alpha +1}(k + pd)$. Поскольку $k$ не делится на $p$, то очевидно, что $b$ делится на $p$ и не делится на $p^2$. Лемма доказана.
Лемма 2. Пусть $a \geq 2, p$ - нечетное простое число и выполнено хотя бы одно из неравенств $a \neq 2$ и $p \neq 3$. Тогда $a^p + 1$ имеет простой делитель, не являющийся делителем числа $a + 1$.
Доказательство. Рассмотрим разложение
$a^p + 1 = (a + 1)(a^{p-1} - a^{p-2} + \cdots + a^2 - a +1) = (a + 1)b$.
Докажем вначале, что числа $a +1$ и $b$ не могут иметь общего делителя $r$, отличного от 1 и от $p$. Действительно, если $a + 1$ делится на $r$, то и $a^k + 1$ делится на $r$ при любом нечетном $k$; если же $k = 2m$, то $a^k - 1$ делится на $a^2 - 1$, которое, в свою очередь, делится на $r$. Значит, $b = rl + p,$ где $l$ - некоторое целое число. Поэтому $b$ делится на $r$ лишь при $r = 1$ или $p$.
Таким образом, для завершения доказательства леммы осталось рассмотреть случай $b = p^n, a + 1$ делится на $p$. Докажем, что этот случай невозможен. Докажем вначале, что, как и в доказательстве леммы 1, $b > p$. Имеем $b \geq a^2 - a + 1 \geq a + 1 \geq p$. Из условий леммы следует, что среди неравенств этой цепочки есть строгие. С другой стороны, как и в доказательстве леммы 1, можно получить, что число $b$ не делится на $p^2$, что и завершает доказательство леммы.
Из доказанных лемм следует, что правая часть равенства $u^y \pm 1 = 2^{y-2}v^y$ имеет не менее $q +1$ различных простых делителей. Поскольку $\:НОД(u, 2v) = 1, u > 1$, получаем отсюда неравенство задачи.
Замечание. Фактически мы доказали следующее, более сильное, чем утверждение задачи,
Предложение. Пусть число $y$ разлагается в произведение $n$ отличных от 1 натуральных чисел. Тогда $x$ имеет не менее $n + 2$ различных простых делителей.
