# structure in modular arithmetic

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

\begin{align} g^k &= a \bmod n\\ g^{k+0.5(n-1)} &= 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$$.

• Thank you for explaining. This shows that the first 0.5n numbers of the order influences the second 0.5n numbers, right? So, there is some structure in the 'random' modular arithmetic – user71649 Sep 4 at 15:26
• I don't understand what you mean by the "first 0.5n numbers of the order", sorry. – Hilder Vítor Lima Pereira Sep 5 at 6:40