Problem 1359

First we prove that for all positive integers $y$, there exist infinitely many primes $p \equiv 3 \pmod 4$ such that $p$ divides some number of the form $2^n y + 1$.

Clearly it suffices to consider the case where $y$ is odd. Let
$$2y + 1 = p_1^{e_1} \cdots p_r^{e_r}$$
be the prime factorization of $2y+1$. Suppose there exist finitely many primes $p_{r+1}, \cdots, p_{r+s} \equiv 3 \pmod 4$ that divide some number of the form $2^n y + 1$ but do not divide $2y + 1$.

We want to find an $n$ such that $p_i^{e_i} \mid 2^n y + 1, 1 \le i \le r$ and $p_i \nmid 2^n y + 1, r+1 \le i \le r+s$. For this it suffices to take
$$n = 1 + \varphi(p_1^{e_1+1} \cdots p_r^{e_r+1} p_{r+1}^1 \cdots p_{r+s}^1),$$
since then we would have
$$2^n y + 1 \equiv 2y + 1 \pmod{p_1^{e_1+1} \cdots p_r^{e_r+1} p_{r+1}^1 \cdots p_{r+s}^1}.$$

The last congruence means that $p_1^{e_1}, \cdots, p_r^{e_r}$ exactly divide $2^n y + 1$ and that $p_{r+1}, \cdots, p_{r+s}$ all do not divide $2^n y + 1$. Hence the prime factorization of $2^n y + 1$ contains $p_1^{e_1}, \cdots, p_r^{e_r}$ and powers of primes congruent to $1 \pmod 4$. Since $y$ is odd, we obtain
$$2^n y + 1 \equiv p_1^{e_1} \cdots p_r^{e_r} \equiv 2y + 1 \equiv 3 \pmod 4.$$
Since $n > 1$, this is a contradiction. Hence we obtain $2^n y + 1 \equiv 1 \pmod 4$.

If $p$ is a prime factor of $2^n y + 1$, then for $d = 2^n$, we have $x^d \equiv 1 \pmod 4$. By Fermat's little theorem, the same congruence holds for $d = p-1$, so it also holds for $d = (2^n, p - 1)$. For $p \equiv 3 \pmod 4$ we have $(2^n, p - 1) = 2$, hence in this case $x^2 \equiv 1 \pmod p$.

In summary, we have shown that every $p \equiv 3 \pmod 4$ that divides some number of the form $2^n y + 1$ also divides $x^2-1$. This is only possible when $x=1$, otherwise the positive integer $x^2-1$ would have infinitely many prime factors.