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

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?

• !? voting down instead of being constructive to say what is missing? Sep 24 '20 at 20:26
• I think you should show some of your own efforts/thoughts, rather than simply posting the question. Besides, your statement is not very clear to me, especially the sentence $i=1,2,...,\frac{p-1}{2}=g^{k_i}$. Sep 24 '20 at 20:28

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

• Yes, for the number $i=T$ we have $j=1$, but I'm saying that for every $i\in\{1,2,...,(p-1)/2\}$ there exists $j$ s.t. $$i\cdot j^{-1} = g^{k_i-k_j} = t^{\pm1}$$. Sep 24 '20 at 21:34
• @Diger I added a final part to my answer, which finds a suitable $j$ for arbitrary $i$ with the desired property. Sep 24 '20 at 21:57
• @Diger A simpler way to show the final part is your own way: by just a simple calculations you can show that $i$ and $j$ satisfy that special condition if and only if $i^2+j^2 \cong 0 \mod p$. Now starting from $i=T$ and $j=1$ it suffices to multiply both of $i$ and $j$ to some suitable element to reach an arbitrary $i$. Also notice that after you find a $j$ you can change its sign (if needed). Sep 24 '20 at 22:21
• Yes, you are right. It trivially follows from $$(\pm t)^2 + 1 = 0 \mod p$$ and successively multiplying with $x^2$ where $x\in\{1,2,...,(p-1)/2\}$. Then either $tx \in\{1,2,...,(p-1)/2\}$ or if not, then $-tx\in\{1,2,...,(p-1)/2\}$. Sep 25 '20 at 7:40
• @Diger Yes, exactly. You are right. Sep 25 '20 at 7:44