Results 1 to 8 of 8

Thread: Primitive Root Problem.

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    59

    Primitive Root Problem.

    Show that if $\displaystyle p$ is prime and $\displaystyle p = 2q + 1$, where $\displaystyle q$ is an odd prime and $\displaystyle a$ is
    a positive integer with $\displaystyle 1 < a < p - 1$, then $\displaystyle p - a^2$ is a primitive root modulo $\displaystyle 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 $\displaystyle p-1 = 2 \cdot q$ are $\displaystyle 1,2,q,2q=p-1$.

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

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

    Now try the remaining one!

    EDIT: Erroneous post, save for the first 2 lines.
    Last edited by PaulRS; Jul 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 $\displaystyle p$ is prime and $\displaystyle p = 2q + 1$, where $\displaystyle q$ is an odd prime and $\displaystyle a$ is
    a positive integer with $\displaystyle 1 < a < p - 1$, then $\displaystyle p - a^2$ is a primitive root modulo $\displaystyle p$.
    You need to show that:

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


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

    Remember that $\displaystyle \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) $\displaystyle a^2\equiv \pm 1(\bmod. p)$ which we know is impossible since $\displaystyle a\in\{2,3,...,p-2\}$
    One example that would violate that logic is $\displaystyle p=17$ and $\displaystyle a=4$. Now that specific example is actually invalid since it it doesn't fit the form $\displaystyle 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 $\displaystyle (-a^2)^2 \not\equiv 1 \pmod {p}$ case and the $\displaystyle (-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 $\displaystyle (-a^2)^2 = a^4 \equiv 1 (\bmod.p)$, let $\displaystyle o$ be the order of $\displaystyle a$ module p. Then $\displaystyle o | 4$ and $\displaystyle o | (p-1) = 2\cdot q$.

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

    For the remaining one, since $\displaystyle q$ is odd $\displaystyle (-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 $\displaystyle -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 $\displaystyle -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 $\displaystyle q$ is an odd prime.

    As I said in the previous post : $\displaystyle (-a^2)^q \equiv -1 (\bmod. p)$ so in fact $\displaystyle -a^2\equiv 1 (\bmod. p)$ is impossible (because it'd imply $\displaystyle -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 $\displaystyle -a^2 \equiv 1 \pmod {p}$ imply $\displaystyle -1 \equiv 1 \pmod {p}$. That doesn't seem right at all.

    $\displaystyle (-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: Nov 20th 2010, 06:01 PM
  2. Primitive Root problem
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Dec 20th 2009, 03:13 PM
  3. Primitive root problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 8th 2008, 07:28 AM
  4. Primitive root problem
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 5th 2008, 04:50 PM
  5. Primitive root of unity problem
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Mar 28th 2008, 05:38 AM

/mathhelpforum @mathhelpforum