# Why does this congruence hold?

• April 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?

$g^{nu} \equiv g^i(mod p) \iff nu \equiv i (mod (p-1))$
• April 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?

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

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

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

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

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