If $p\equiv 1 \mod 4$ then $|k_i - k_j|=\frac{p-1}{4}$

Question

The Title basically says it already. Maybe this is simple, but I don't see it yet. If $p\equiv 1 \mod 4$ is a prime, then for every $i\equiv g^{k_i} \mod p$ with $i\in \{1,2,...,\frac{p-1}{2}\}$, where $g$ is a generator of $\mathbb{Z}_p$, there exists $j\in\{1,2,...,(p-1)/2\}$ s.t. $$|k_i-k_j|=\frac{p-1}{4}\,.$$

The question is equivalent to saying that the elements $i=1,2,...,\frac{p-1}{2}$ of the group $\mathbb{Z}_p$ are mapped onto itsself under the map $$f:(1,2,...,(p-1)/2) \rightarrow (1,2,...,(p-1)/2)\\i\mapsto g^{\pm \frac{p-1}{4}} \cdot i \mod p $$ where the sign $\pm=\pm_i$ is different for each $i$. This follows from $$j=g^{k_{j}}=f(i)=i\cdot g^{\pm \frac{p-1}{4}}=g^{k_i\pm \frac{p-1}{4}} \mod p \, .$$ So essentially I'm saying that $f$ is a bijection.

The reason why I'm interested in this is, because for such pairwise $i,j\in\{1,2,...,(p-1)/2\}$ we always have $$i^2+j^2 = i^2 \left(1+g^{\pm\frac{p-1}{2}}\right)=i^2(1-1)=0 \mod p \, .$$ But how can you prove this?

Answer 1

• According to your definition, we have: $g^{k_i}=i$, and $g^{k_j}=j$.
• Let $t=g^{\dfrac{p-1}{4}}$. Note that $t^2 \cong -1 \mod p$, so multiplying both sides by $-t^{-1}$ we have $-t \cong t^{-1} \mod p$.
• Also we can choose exactly one of $t$ and $-t$, such that it is congruent to a number $k$, with $1 \leq k \leq \dfrac{p-1}{2}$. So we can choose exactly one of $t$ and $t^{-1}$, such that it is congruent to a number $k$, with $1 \leq k \leq \dfrac{p-1}{2}$. (In other words, we can choose exactly one of $t$ and $-t$, such that it has a remainder $k$, with $1 \leq k \leq \dfrac{p-1}{2}$. So we can choose exactly one of $t$ and $t^{-1}$, such that it has a remainder $k$, with $1 \leq k \leq \dfrac{p-1}{2}$.) Let's call this good choice (from the set $\{ t, t^{-1} \}$) by $T$.

---

You are looking for some $i$ and $j$ such that:

$$k_i-k_j=\pm \dfrac{p-1}{4} \Longleftrightarrow$$

$$g^{k_i-k_j}=g^{\pm \dfrac{p-1}{4}}.$$

But the later is equivalent to

$$\dfrac{i}{j}=\dfrac{g^{k_i}}{g^{k_j}}=g^{k_i-k_j}=g^{\pm \dfrac{p-1}{4}}=t^{\pm 1}.$$

---

Clearly $i=T$, and $j=1$ satisfies $\dfrac{i}{j}=t^{\pm 1}$ (for suitable choice of sign of power of $t$).

---

Edited:

Now Let $i \in \{ 1, 2, \cdots, \dfrac{p-1}{2} \}$ be arbitrary, we are looking for some $j \in \{ 1, 2, \cdots, \dfrac{p-1}{2} \}$ such that $\dfrac{i}{j}=t^{\pm 1}$. It suffices to find a $j \in \{ 1, 2, \cdots, \dfrac{p-1}{2} \}$, such that $\dfrac{i\times (i^{-1}T)}{j\times (i^{-1}T)}=t^{\pm 1}$. Equivalently it suffices to find $j \in \{ 1, 2, \cdots, \dfrac{p-1}{2} \}$ such that $\dfrac{T}{j\times (i^{-1}T)}=t^{\pm 1}$. Lets denote the solution of the equation $j\times i^{-1}T \cong 1 \mod p$ by $s$. similarly we know that exactly one of $s$ and $-s$, has a remainder $k$, with $1 \leq k \leq \dfrac{p-1}{2}$. So we can choose exactly one of $s$ and $-s$, such that it has a remainder $k$, with $1 \leq k \leq \dfrac{p-1}{2}$. Let's call this good choice (from the set $\{ s, -s \}$) by $S$.

Now $\dfrac{i}{S} \cong \dfrac{i\times (i^{-1}T)}{S\times (i^{-1}T)} \cong \dfrac{T}{\pm 1} \cong \pm \dfrac{T}{1} \cong \pm (t^{\pm 1})$.

Notice that the set $\{ t, t^{-1} \}$ is the same as the set $\{ -t, -t^{-1} \}$, so for the suitable choice of $T'$ we are done. (Consider this phrase: "$\pm (t^{\pm 1})$", notice that the $\pm$ signs out of parantheses is not depended on the $\pm$ signs at the power of $t$.) Also notice that the result of all four cases in the phrase "$\pm (t^{\pm 1})$" would be $\pm t$. (Because if we let $t=g^{\dfrac{p-1}{4}}$, then we have that $t^2 \cong -1 \mod p$, so multiplying both sides by $-t^{-1}$ we have $-t \cong t^{-1} \mod p$.)