0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ !? voting down instead of being constructive to say what is missing? $\endgroup$
    – Diger
    Sep 24 '20 at 20:26
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – WhatsUp
    Sep 24 '20 at 20:28
0
$\begingroup$
  • 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$.)

$\endgroup$
5
  • $\begingroup$ 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}$$. $\endgroup$
    – Diger
    Sep 24 '20 at 21:34
  • $\begingroup$ @Diger I added a final part to my answer, which finds a suitable $j$ for arbitrary $i$ with the desired property. $\endgroup$ Sep 24 '20 at 21:57
  • $\begingroup$ @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). $\endgroup$ Sep 24 '20 at 22:21
  • 1
    $\begingroup$ 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\}$. $\endgroup$
    – Diger
    Sep 25 '20 at 7:40
  • $\begingroup$ @Diger Yes, exactly. You are right. $\endgroup$ Sep 25 '20 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.