Results 1 to 3 of 3

Math Help - Why does this congruence hold?

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    168

    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))
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by paupsers View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 12
    Last Post: January 16th 2011, 06:22 AM
  2. Does the converse hold?
    Posted in the Calculus Forum
    Replies: 6
    Last Post: September 26th 2010, 07:39 AM
  3. Force to hold a spring
    Posted in the Calculus Forum
    Replies: 2
    Last Post: December 10th 2009, 10:57 AM
  4. hold em math
    Posted in the Statistics Forum
    Replies: 5
    Last Post: August 12th 2009, 07:28 PM
  5. Parallelogram law does not hold in C([0,1])
    Posted in the Calculus Forum
    Replies: 0
    Last Post: September 14th 2008, 07:50 AM

Search Tags


/mathhelpforum @mathhelpforum