Results 1 to 8 of 8

Math Help - Primitive Root Problem.

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Primitive Root Problem.

    Show that if p is prime and p = 2q + 1, where q is an odd prime and a is
    a positive integer with 1 < a < p - 1, then p - a^2 is a primitive root modulo p.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571

    Re: Primitive Root Problem.

    Note that the only numbers dividing p-1 = 2 \cdot q are 1,2,q,2q=p-1.

    So we just have to check that (p-a^2)^2\not\equiv 1 (\bmod. p) and  (p-a^2)^q \not\equiv 1 (\bmod. p) and (p-a^2)^1 \not \equiv 1(\bmod. p).

    The latter is simple enough, now for the first (p-a^2)^2 \equiv a^4 \equiv 1(\bmod. p) means that p| (a^4 -1) = (a^2 - 1)\cdot (a^2 + 1) so (by Euclid's Lemma) a^2\equiv \pm 1(\bmod. p) which we know is impossible since a\in\{2,3,...,p-2\}.

    Now try the remaining one!

    EDIT: Erroneous post, save for the first 2 lines.
    Last edited by PaulRS; July 5th 2011 at 09:12 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Primitive Root Problem.

    Quote Originally Posted by VinceW View Post
    Show that if p is prime and p = 2q + 1, where q is an odd prime and a is
    a positive integer with 1 < a < p - 1, then p - a^2 is a primitive root modulo p.
    You need to show that:

    (*) ((2q+1)-a^2)^{\phi(2q+1)}\equiv 1(\mod 2q+1)


    But, ((2q+1)-a^2)^{k}\not\equiv  1(\mod 2q+1) for k<\phi(2q+1)

    Remember that \phi(2q+1)=2q and for (*) use Euler theorem.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Re: Primitive Root Problem.

    PaulRS, I understand your strategy, however I don't think this works:

    so (by Euclid's Lemma) a^2\equiv \pm 1(\bmod. p) which we know is impossible since a\in\{2,3,...,p-2\}
    One example that would violate that logic is p=17 and a=4. Now that specific example is actually invalid since it it doesn't fit the form 2q + 1 where q is prime as specified by the problem, but I need to form a proof that this is the case.

    I don't see how to prove the (-a^2)^2 \not\equiv 1 \pmod {p} case and the (-a^2)^q \not\equiv 1 \pmod {p} case.

    Zarathustra... You're response is implicit from the initial problem and the basic definition of a primitive root... You really didn't add anything or help solve this.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571

    Re: Primitive Root Problem.

    Suppose (-a^2)^2 = a^4 \equiv 1 (\bmod.p), let o be the order of a module p. Then o | 4 and o | (p-1) = 2\cdot q.

    Since q is an odd prime, this means that o | \text{gcd}(4,2\cdot q) = 2 so we must have a^2 \equiv 1 (\bmod. p) which means a \equiv 1(\bmod.p) or a \equiv -1(\bmod.p) ... now this is absurd since a\in\{2,..,p-2\}.

    For the remaining one, since q is odd (-a^2)^q = - a^{2\cdot q}  = - a^{p-1} \equiv - 1(\bmod.p) by Fermat's Little Theorem.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Re: Primitive Root Problem.

    Thanks. Those cases make sense.

    But how do you prove that -a^2 \not\equiv 1 \pmod {p}. As I said earlier, a=4 and p=17 seem to violate that and you would need to use the fact that q is an odd prime.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571

    Re: Primitive Root Problem.

    Quote Originally Posted by VinceW View Post
    Thanks. Those cases make sense.

    But how do you prove that -a^2 \not\equiv 1 \pmod {p}. As I said earlier, a=4 and p=17 seem to violate that and you would need to use the fact that q is an odd prime.
    You need to have that q is an odd prime.

    As I said in the previous post : (-a^2)^q \equiv -1 (\bmod. p) so in fact -a^2\equiv 1 (\bmod. p) is impossible (because it'd imply -1\equiv 1 (\bmod.p) ).
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Re: Primitive Root Problem.

    How does -a^2 \equiv 1 \pmod {p} imply -1 \equiv 1 \pmod {p}. That doesn't seem right at all.

    (-a^2)^q \equiv -1 \pmod {p} is very clear (it's one step from Euler's Theorem) and I don't see how that relates.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Primitive Root Problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: November 20th 2010, 06:01 PM
  2. Primitive Root problem
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 20th 2009, 03:13 PM
  3. Primitive root problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 8th 2008, 07:28 AM
  4. Primitive root problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 5th 2008, 04:50 PM
  5. Primitive root of unity problem
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: March 28th 2008, 05:38 AM

/mathhelpforum @mathhelpforum