Results 1 to 11 of 11

Math Help - Primitive roots & Reduced residue system

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Primitive roots & Reduced residue system




    [also under discussion in math link forum]
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    About part b:

    Since g is a primitive root mod p, the order of g (mod p) must be p-1, and we have g^{p-1}=1(mod p)

    In part b, we have to show that if gcd(k,p-1)=d>1, then {1^k,2^k,...,(p-1)^k} does NOT form a reduced residue system mod p. If we can show that some distinct elements in the set are congruent to each other, then we're done. But how to prove show this???

    Can someone kindly help me, please? I'm still puzzled...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Since  \{1^k, 2^k,\cdot\cdot\cdot, (p-1)^k\} are all distinct, then  x^k \equiv a \mod{p} is solvable for all  a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^* .

    Let's suppose  (k,p-1)=d>0 , now look at  a^{\frac{p-1}{d}}\mod{p} :

     a^{\frac{p-1}{d}} \equiv \left(x^k\right)^{\frac{p-1}{d}} = x^{c\cdot(p-1)} \equiv 1 \mod{p} for all  a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^* .

    Hence we've shown the order of the group  \left(\mathbb{Z}/p\mathbb{Z}\right)^* , which is  p-1 , divides  \frac{p-1}{d}
    This forces  d=1 .
    Last edited by chiph588@; March 3rd 2010 at 03:44 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    hmm...I have no background in abstract algebra. I haven't learnt anything about groups and things like Z/pZ, so I can't follow your proof. Can you explain the proof in more basic terms, please?

    Quote Originally Posted by chiph588@ View Post
    Since  \{1^k, 2^k,\cdot\cdot\cdot, (p-1)^k\} are all distinct, then  x^k \equiv a \mod{p} is solvable for all  a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^* .
    I don't see why this is true...could you explain a little more on this, please??
    Also, what is "a"?

    Let's suppose  (k,p-1)=d>0 , now look at  a^{\frac{p-1}{d}}\mod{p} :

     a^{\frac{p-1}{d}} \equiv \left(x^k\right)^{\frac{p-1}{d}} = x^{c\cdot(p-1)} \equiv 1 \mod{p} for all  a\in \left(\mathbb{Z}/p\mathbb{Z}\right)^* .

    Hence we've shown the order of the group  \left(\mathbb{Z}/p\mathbb{Z}\right)^* , which is  p-1 , divides  \frac{p-1}{d}
    This forces  d=1 .
    How do you know that x^{c(p-1)} = 1 (mod p) ???


    Thanks for your help!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    hmm...I have no background in abstract algebra. I haven't learnt anything about groups and things like Z/pZ, so I can't follow your proof. Can you explain the proof in more basic terms, please?
    First note that  \left(\mathbb{Z}/p\mathbb{Z}\right)^* = \{1,2,\cdot\cdot\cdot, p-1\} .

    We're given that  \{1^k,2^k,\cdot\cdot\cdot, (p-1)^k\} \equiv \{1,2,\cdot\cdot\cdot, p-1\} \mod{p}. Hence for every  a \in \{1,2,\cdot\cdot\cdot, p-1\} , there is a corresponding  x^k \in \{1^k,2^k,\cdot\cdot\cdot, (p-1)^k\} such that  x^k \equiv a \mod{p} . (A surjective map onto itself is injective too, if you like set theory.) That's what I meant when saying  x^k \equiv a \mod{p} is solvable.

    I don't see why this is true...could you explain a little more on this, please??
    Also, what is "a"?


    How do you know that x^{c(p-1)} = 1 (mod p) ???


    Thanks for your help!
    Since  (x,p)=1 , by Fermat's little theorem,  x^{p-1} \equiv 1 \mod{p} . Hence  x^{c\cdot (p-1)} = \left(x^{p-1}\right)^c \equiv 1^c \equiv 1 \mod{p} .


    Let me try this proof a little bit differently.

    Above, I showed for all  a \in \{1,2,\cdot\cdot\cdot, p-1\}, \; a^{\frac{p-1}{d}} \equiv 1 \mod{p} , where  d=(k,p-1) .

    Choose  g such that it's a primitive root (we know one exists here). If  d>1 , we would have  g^{\frac{p-1}{d}} \equiv 1 \mod{p} , which is a contradiction since  \frac{p-1}{d} < p-1 and for all  c<p-1, \; g^c\not\equiv 1 \mod{p} .

    Our contradiction forces  d=1 as desired.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by chiph588@ View Post
    Choose  g such that it's a primitive root (we know one exists here). If  d>1 , we would have  g^{\frac{p-1}{d}} \equiv 1 \mod{p} , which is a contradiction since  \frac{p-1}{d} < p-1 and for all  c<p-1, \; g^c\not\equiv 1 \mod{p} .

    Our contradiction forces  d=1 as desired.
    "If  d>1 , we would have  g^{\frac{p-1}{d}} \equiv 1 \mod{p} " <-----hmm...Why is this true?

    I know this may be obvious to you, but to me it's not...

    Thanks for your time and patience in explaining this!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by kingwinner View Post
    "If  d>1 , we would have  g^{\frac{p-1}{d}} \equiv 1 \mod{p} " <-----hmm...Why is this true?

    I know this may be obvious to you, but to me it's not...

    Thanks for your time and patience in explaining this!
    It's because  g\in \{1,2,\cdot\cdot\cdot , p-1\} and it was established that  a^{\frac{p-1}{d}}\equiv 1 \mod{p} for all  a , so the same applies to  g .
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by chiph588@ View Post
    It's because  g\in \{1,2,\cdot\cdot\cdot , p-1\} and it was established that  a^{\frac{p-1}{d}}\equiv 1 \mod{p} for all  a , so the same applies to  g .
    OK, but is it always true that any primitive root mod p must lie in the set {1,2,...,p-1}?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Yes, there always will exist a primitive root modulo a prime.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by chiph588@ View Post
    Yes, there always will exist a primitive root modulo a prime.
    But is it possible that the primitive root exists, but lies outside the set {1,2,...,p-1}?? Why or why not?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    I'm not sure you know what a primitive root is...

    A primitive root  g of a prime number  p is an element of  \{1,2,\cdot\cdot\cdot, p-1\} such that  g^c \not\equiv 1 \mod{p} for all  0<c<p-1 .
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Reduced residue system modulo m
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: January 20th 2010, 08:12 PM
  2. Proof with reduced residue systems
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: November 11th 2009, 12:33 PM
  3. Help with reduced row echelon form/solving system
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: March 23rd 2009, 06:35 AM
  4. Reduced system of representatives
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 5th 2007, 07:43 PM
  5. primitive root and quadratic residue
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 3rd 2006, 07:12 PM

Search Tags


/mathhelpforum @mathhelpforum