# Why does this congruence hold?

• Apr 3rd 2011, 09:58 AM
paupsers
Why does this congruence hold?
This is just one line from a larger proof about nth power solutions, but I don't understand how/why it's true. Any help?

$\displaystyle g^{nu} \equiv g^i(mod p) \iff nu \equiv i (mod (p-1))$
• Apr 3rd 2011, 02:21 PM
tonio
Quote:

Originally Posted by paupsers
This is just one line from a larger proof about nth power solutions, but I don't understand how/why it's true. Any help?

$\displaystyle g^{nu} \equiv g^i(mod p) \iff nu \equiv i (mod (p-1))$

I suppose $\displaystyle (g,p)=1\Longrightarrow g^{p-1}=1\!\!\pmod p\mbox{ , by Fermat's Little Theorem }\Longrightarrow$

$\displaystyle \Longrightarrow g^{nu}=g^{i}\!\!\pmod p\iff g^{nu-i}=1\!\!\pmod p\iff nu-i=0\!\!\pmod{p-1}$

Tonio
• Apr 3rd 2011, 03:16 PM
Bruno J.
This isn't true. For example $\displaystyle (-1)^2 \equiv 1 \mod p$, but $\displaystyle 2 \neq 0 \mod p-1$ for $\displaystyle p>2$.

It's true if $\displaystyle g$ is a primitive root.