structure in modular arithmetic I was playing around with modular arithmetic when I noticed something. 

\begin{align}
g^k &amp;= a \bmod n\\
g^{k+0.5(n-1)} &amp;= b \bmod n
\end{align}

Then $a + b = n$, so you can also write

$$g^{k+0.5(n-1)} = n - a \bmod n$$

This seems to hold if $n$ is prime and $g$ is the primitive element of $n$, according to randomly trying sets of $n$ and $g$. I have tried to see the theory behind this, but was not able to do so. None of the properties (Wikipedia: Modular arithmetic properties) of modular arithmatic seems to relate to this. Can someone explain why this holds?
If you know the Fermat's little theorem, that is, $g^{n-1} = 1 \mod n$, then you can understand what you found. 

The point is that 

$$b^2 = g^{2k + n-1} = g^{2k}g^{n-1} = g^{2k} = a^2 \mod n$$

Therefore, $b = a$ or $b = -a$ in $\mathbb{Z}_n$. But $b = -a$ means that $b = n-a$, since $n = 0$ modulo $n$.