1-я Международная Жаутыковская олимпиада, 2005 год, младшая лига

Найдите все простые числа $p$, $q$, не превосходящие $2005$ и такие, что $p^2+4$ делится на $q$, а $q^2+4$ делится на $p$.

Комментарий/решение

Если $p$ или $q$ равно $2$, то $p = 2$, отсюда $q|8$, поэтому $q = 2$. Это означает, что $(p, q) = 2$. В противном случае пусть $p$ и $q$ — нечетные простые числа. У нас есть $q|(p^2 + 4)$, поэтому $p$ и $q$ не равны.

Следовательно, $q|(p^2 + 4)$ и $p|(q^2 + 4)$ тогда и только тогда, когда $\frac {p^2q^2 + 4p^2 + 4q^2 + 16}{ pq}$ — целое число. Это целое число тогда и только тогда, когда $\frac {4p^2 + 4q^2 + 16}{pq}$ является целым числом. Поскольку $p$ и $q$ относительно просты с $4$, мы видим, что это целое число тогда и только тогда, когда $\frac {p^2 + q^2 + 4}{pq}$ является целым числом. Пусть это значение будет $k$.

Тогда мы имеем $p^2 - p(kq) + (q^2 + 4) = 0$. В общем, рассмотрим уравнение $a^2 - a(bk) + (b^2 + 4) = 0$. Пусть $(a, b)$ — решение этого уравнения в натуральных числах с наименьшим возможным $a + b$ и,По Б.О.О скажем, что $a\le b$. Теперь, если $(a, b)$ — решение, то $(\frac {b^2 + 4}{a}, b)$ — решение,

Таким образом, $b + \frac {b^2 + 4}{a} \ge a + b$, поэтому $a^2 - b^2 \le 4\ подразумевает (a + b)(a - b) \le 4$. Теперь это означает, что $a = b$ или $(a, b)$ — это $(1, 2)$. Если $a = b$, то $(k - 2)a^2 = 4$, поэтому $(a, b)$ — это $(1,1)$ или $(2,2)$. Находим $k$ для каждого из этих случаев.

Если $(a, b) = (1, 2)$, то $k$ не является целым числом. Если $(a, b) = (1,1)$, то $k = 6$. Если $(a, b) = (2, 2)$, то $k = 3$. Если $k = 3$, то мы имеем, что $\frac {p^2 + q^2 + 4}{pq}$ нечетно, что невозможно, поскольку числитель четный, а знаменатель нечетный. Отсюда следует, что $k = 6$. Таким образом, $p^2 - 6pq + (q^2 + 4) = 0$. Его дискриминант равен $16(2q^2 - 1)$, поэтому $2q^2 - 1$ — идеальный квадрат. Теперь рассмотрим уравнение Пелла $2m^2 - n^2 = 1$. Мы можем вычислить простые числа $q$, которые работают для уравнения Пелла в $2005$ (они являются решениями рекуррентного уравнения $a_{n + 1} = 6a_n - a_{n - 1}$ с $a_1 = 1$ и $a_2 = 5$), что составляет $5$ и $29$. Подставив это, мы получаем, что $p^2 - 30p + 29 = 0$, поэтому $p = 29$ или $p = 1$ (но $p = 1$ невозможно, поскольку $1$ не является простым числом, поэтому $р = 29$). Если $q = 29$, то $p^2 - 174p + 845 = 0$, поэтому $(p - 169)(p - 5) = 0$, поэтому $p = 5$ или $p = 169$ (но $p = 169$ невозможно, так как $169$ составное). Таким образом, единственными решениями являются $(p, q) = (5, 29), (29, 5), (2,2)$.

У меня тоже есть хорошее решение.Только оно на английском так как мне лень переводить на русский

Stephen

#3Jun 24, 2009, 9:41 AM• 3 Y

The QuattoMaster 6000 wrote:

Solution

If $p$ or $q$ is $2$, then we may let $p = 2$, so $q|8$, so $q = 2$. This means that $(p, q) = 2$. Otherwise, let $p$ and $q$ be odd primes. We have that $q|(p^2 + 4)$, so $p$ and $q$ may not be equal. Therefore, $q|(p^2 + 4)$ and $p|(q^2 + 4)$ if and only if $\frac {p^2q^2 + 4p^2 + 4q^2 + 16}{pq}$ is an integer. This is an integer if and only if $\frac {4p^2 + 4q^2 + 16}{pq}$ is an integer. Since $p$ and $q$ are relatively prime with $4$, we see that this is an integer if and only if $\frac {p^2 + q^2 + 4}{pq}$ is an integer. Let this value be $k$.

Then, we have that $p^2 - p(kq) + (q^2 + 4) = 0$. In general, let us consider the equation $a^2 - a(bk) + (b^2 + 4) = 0$. Let $(a, b)$ be the the solution to this equation in positive integers with the lowest possible $a + b$, and without loss of generality, say that $a\le b$. Now, if $(a, b)$ is a solution, then $(\frac {b^2 + 4}{a}, b)$ is a solution, so $(b, \frac {b^2 + 4}{a})$ must be a solution. Thus, $b + \frac {b^2 + 4}{a} \ge a + b$, so $a^2 - b^2 \le 4\implies (a + b)(a - b) \le 4$. Now, this means that $a = b$ or $(a, b)$ is $(1, 2)$. If $a = b$, then we have that $(k - 2)a^2 = 4$, so $(a, b)$ is $(1,1)$ or $(2,2)$. We find $k$ for each of these cases.

If $(a, b) = (1, 2)$, then $k$ is not an integer. If $(a, b) = (1,1)$, then $k = 6$. If $(a, b) = (2, 2)$, then $k = 3$. If $k = 3$, then we have that $\frac {p^2 + q^2 + 4}{pq}$ is odd, which is impossible since the numerator is even and the denominator is odd. It follows that $k = 6$. Thus, $p^2 - 6pq + (q^2 + 4) = 0$. The discriminant of this is $16(2q^2 - 1)$, so $2q^2 - 1$ is a perfect square. We now consider the Pell's Equation $2m^2 - n^2 = 1$. We can compute the primes $q$'s that work for the the Pell's Equation under $2005$ (they are solutions to the recurrence $a_{n + 1} = 6a_n - a_{n - 1}$ with $a_1 = 1$ and $a_2 = 5$), which are $5$ and $29$. Plugging this in, we get that $p^2 - 30p + 29 = 0$, so $p = 29$ or $p = 1$ (but $p = 1$ is impossible since $1$ is not prime, so $p = 29$). If $q = 29$, then $p^2 - 174p + 845 = 0$, so $(p - 169)(p - 5) = 0$, so $p = 5$ or $p = 169$ (but $p = 169$ is impossible as $169$ is composite). Thus, the only solutions are $(p, q) = (5, 29), (29, 5), (2,2)$.