Problem 2143

Proof. First, we show that there are infinitely many good primes. It is well-known that there are infinitely many primes $p \equiv 3 \pmod 4$. We prove that if $p \equiv 3 \pmod 4$, then $p$ is a good prime. Let $f(0) = 0$. Consider all quadratic residues of $p$, denoted as $r_1, r_2, \dots, r_{(p-1)/2}$. If $r_i^2 \equiv r_j \pmod p$, we draw a directed edge from $r_i$ to $r_j$. If $i = j$, it is considered a self-loop. Then all vertices $r_1, r_2, \dots, r_{p-1}$ in this directed graph have an out-degree of 1. Moreover, for any $r_i$, let $d^2 \equiv r_i \pmod p$. Since $\left(\frac{-1}{p}\right) = -1$, either $d$ or $-d$ (but not both) is a quadratic residue modulo $p$. Thus, every vertex also has an in-degree of 1. This means the directed graph is a disjoint union of cycles.

For a directed cycle $r_{i_1} \to r_{i_2} \to \dots \to r_{i_s} \to r_{i_1}$:
- If $s = 2t + 1$ (odd), we define
$$f(r_{i_1}) = 2u,\ f(r_{i_2}) = 2u+4,\ \dots,\ f(r_{i_{t+1}}) = 2u+4t,\ f(r_{i_{t+2}}) = 2u+4t-2,\ \dots,\ f(r_{i_{2t+1}}) = 2u+2.$$
- If $s = 2t$ (even), we define
$$f(r_{i_1}) = 2u,\ f(r_{i_2}) = 2u+4,\ \dots,\ f(r_{i_{t+1}}) = 2u+4t-4,\ f(r_{i_{t+2}}) = 2u+4t-2,\ \dots,\ f(r_{i_{2t}}) = 2u+2.$$
Here, $u$ is any integer. Since each cycle uses a consecutive sequence of even numbers, we can choose these numbers appropriately to ensure that the values used by different cycles do not overlap. Notice that only even numbers are used. If $w$ is not a quadratic residue, let $v = w^2 \pmod p$, and define $f(w) = f(v) - 1$. This ensures that $f$ remains injective and satisfies $|f(a) - f(b)| \le 2024$ whenever $p \mid a^2 - b$. Therefore, all primes $p \equiv 3 \pmod 4$ are good primes.

Next, we prove that there are infinitely many bad primes. It is well-known that for any positive integer $n$, if an odd prime $p$ divides $A^{2n} + 1$ (where $A$ is an integer), then $p \equiv 1 \pmod{2^{n+1}}$. This is because $\text{ord}_p(A) \mid 2^{n+1}$ but $\text{ord}_p(A) \nmid 2^n$, so $\text{ord}_p(A) = 2^{n+1}$. Thus, there are infinitely many odd primes $p \equiv 1 \pmod{2^{n+1}}$. (If there were only finitely many, let $A$ be twice the product of these primes, which leads to a contradiction.)

Now, let $p \equiv 1 \pmod{2^{100}}$. We prove that $p$ is a bad prime. By the existence of primitive roots, the equation $x^{2^{100}} \equiv 1 \pmod p$ has exactly $2^{100}$ solutions modulo $p$. If there exists an injective function $f$ satisfying the problem's conditions, then for all $x$ satisfying $x^{2^{100}} \equiv 1 \pmod p$ and $x \in \{1, 2, \dots, p-1\}$, we must have $|f(x)-f(1)| \le 2024 \times 100$. However, there are $2^{100}$ such $x$, while the interval $[f(1)-2024 \times 100, f(1)+2024 \times 100]$ contains only $404801 < 2^{100}$ integers. Thus, there must be two distinct $x$ with the same image, contradicting injectivity! Therefore, $p$ is a bad prime.

Hence, there are infinitely many bad primes.