Problem 1737

1. Given Conditions and Initial Setup:
- We are given a set $S$ of all positive integers that can be represented as $a^2 + 5b^2$ for some integers $a$ and $b$ such that $a \perp b$ (i.e., $\gcd(a, b) = 1$).
- We need to show that if $kp \in S$ for some positive integer $k$ and a prime $p \equiv 3 \pmod{4}$, then $2p \in S$.

2. Existence of Solutions:
- Since $kp \in S$, there exist integers $a$ and $b$ such that $kp = a^2 + 5b^2$ and $\gcd(a, b) = 1$.
- We need to show that $2p$ can also be written in the form $x^2 + 5y^2$ for some integers $x$ and $y$ with $\gcd(x, y) = 1$.

3. Properties of Quadratic Residues:
- Since $p \equiv 3 \pmod{4}$, we know that $-1$ is not a quadratic residue modulo $p$. However, we need to consider the quadratic residue properties of $-5$ modulo $p$.
- If $kp = a^2 + 5b^2$, then $a^2 \equiv -5b^2 \pmod{p}$. This implies that $-5$ is a quadratic residue modulo $p$.

4. **Constructing the Set $A$:**
- Let $m = \lfloor \sqrt{p} \rfloor$.
- Consider the set $A = \{ x + ay \mid x, y = 0, 1, \ldots, m \}$.
- The size of $A$ is $(m+1)^2$, which is greater than $p$ since $(m+1)^2 > p$.

5. Pigeonhole Principle:
- By the Pigeonhole Principle, there exist distinct pairs $(x_1, y_1)$ and $(x_2, y_2)$ such that $x_1 + ay_1 \equiv x_2 + ay_2 \pmod{p}$.
- This implies $x_1 - x_2 \equiv a(y_2 - y_1) \pmod{p}$.

6. Forming New Solutions:
- Let $x = |x_1 - x_2|$ and $y = |y_1 - y_2|$. Then $p \mid x^2 + 5y^2$.
- Since $0 < x^2 + 5y^2 < 6p$, we have $x^2 + 5y^2 \in \{p, 2p, 3p, 4p, 5p\}$.

7. Eliminating Impossible Cases:
- Since $p \equiv 3 \pmod{4}$, $p$ cannot be written as $x^2 + 5y^2$ because $p \equiv 3 \pmod{4}$ implies $p \equiv 1 \pmod{4}$ if it were of the form $x^2 + 5y^2$.
- Similarly, $4p$ and $5p$ cannot be written as $x^2 + 5y^2$ because $4p \equiv 0 \pmod{4}$ and $5p \equiv 1 \pmod{4}$.

8. Possible Cases:
- Therefore, $x^2 + 5y^2$ must be either $2p$ or $3p$.

9. Case Analysis:
- If $x^2 + 5y^2 = 2p$, we are done.
- If $x^2 + 5y^2 = 3p$, we need to show that $2p$ can still be written in the form $x^2 + 5y^2$.

10. **Detailed Case Analysis for $x^2 + 5y^2 = 3p$:**
- Consider the congruence conditions modulo 3:
- $x \equiv 1 \pmod{3}$ and $y \equiv 1 \pmod{3}$
- $x \equiv 1 \pmod{3}$ and $y \equiv -1 \pmod{3}$
- $x \equiv -1 \pmod{3}$ and $y \equiv 1 \pmod{3}$
- $x \equiv -1 \pmod{3}$ and $y \equiv -1 \pmod{3}$
- For each case, we can find integers $k$ and $l$ such that:
- $x = 3k + 1$ or $x = 3k - 1$
- $y = 3l + 1$ or $y = 3l - 1$
- Substituting these into $x^2 + 5y^2 = 3p$ and simplifying, we can show that $2p$ can be written as $x^2 + 5y^2$.

11. Conclusion:
- Therefore, we have shown that if $kp \in S$, then $2p \in S$ as well.

$\blacksquare$