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)$.