Results 1 to 4 of 4

Thread: how to prove multiplicative integers (mod p) has at least one generator?

  1. #1
    Junior Member
    Joined
    Aug 2010
    Posts
    25

    how to prove multiplicative integers (mod p) has at least one generator?

    How do you prove the multiplicative integers (mod p) has at least one generator?
    I know how to show a^(p-1) is congruent to 1 using Fermat's Little Theorem but how do you show p-1 is the smallest such integer?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    742
    Thanks
    341

    Re: how to prove multiplicative integers (mod p) has at least one generator?

    Quote Originally Posted by Chad950 View Post
    How do you prove the multiplicative integers (mod p) has at least one generator?
    I know how to show a^(p-1) is congruent to 1 using Fermat's Little Theorem but how do you show p-1 is the smallest such integer?

    Thanks!
    p-1 may not be the smallest such integer. example: in the multiplicative group mod 7,

    2^6=1 by Fermat's Little Theorem but we also have 2^3=1
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Aug 2010
    Posts
    25

    Re: how to prove multiplicative integers (mod p) has at least one generator?

    What I mean is how do I show that there is at least one integer whose smallest power that makes it congruent to 1 must be p-1?
    In other words prove that the group of multiplicative integers (mod p) where p is prime must have at least one generator.

    ...as you say other (non-generator) integers have smaller powers that make them congruent to 1.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    742
    Thanks
    341

    Re: how to prove multiplicative integers (mod p) has at least one generator?

    in other words you want to prove that the multiplicative group of nonzero integers mod p is cyclic

    a proof can be found in an algebra textbook
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Oct 8th 2014, 10:57 PM
  2. Prove that for all integers n, n^2 - n + 3 is odd
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Jul 2nd 2014, 09:36 PM
  3. Replies: 2
    Last Post: Mar 8th 2010, 06:25 PM
  4. Prove their own multiplicative inverses
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Mar 3rd 2010, 12:25 AM
  5. prove that the sum of the integers is
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 14th 2010, 05:59 AM

Search Tags


/mathhelpforum @mathhelpforum