Results 1 to 2 of 2

Thread: Number theory Question 2

  1. #1
    Member
    Joined
    Aug 2008
    Posts
    97

    Number theory Question 2

    Show that if p is not a Fermat prime, then there is a such that
    $\displaystyle

    \left(\frac {a}{p}\right)=-1
    $

    and [a]_p is not a generator of $\displaystyle (\mathbb Z/p)^* $.

    Here $\displaystyle

    \left(\frac {2}{p}\right)=-1
    $
    is legendre symbol.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Quote Originally Posted by peteryellow View Post
    Show that if p is not a Fermat prime, then there is a such that
    $\displaystyle

    \left(\frac {a}{p}\right)=-1
    $

    and [a]_p is not a generator of $\displaystyle (\mathbb Z/p)^* $.
    Recall the fact that all primes of the form $\displaystyle 2^n+1$ -save from the number 2- are fermat primes -and conversly- (* that is easy to show, if you have not seen it, ask)

    Okay, first remember that there are $\displaystyle
    \phi \left( {\phi \left( p \right)} \right) = \phi \left( {p - 1} \right)
    $ primitive roots ( or generators) in $\displaystyle (\mathbb Z/p)^* $

    And there are $\displaystyle
    \tfrac{{p - 1}}
    {2}
    $ non-quadratic residues.

    So we'd like to show that $\displaystyle
    \tfrac{{p - 1}}
    {2} > \phi \left( {p - 1} \right)
    $ occurs in our case. -remember that the set of generators is included in the set of non-quadratic residues, see here-

    We can write: $\displaystyle
    p - 1 = 2^\alpha \cdot m
    $ with $\displaystyle
    \alpha;m \in \mathbb{Z}^ +
    $ such that $\displaystyle
    \left( {m,2} \right) = 1
    $ - since p>2, the case p=2 is trivial-

    Then: $\displaystyle
    \phi \left( {p - 1} \right) = \phi \left( {2^\alpha } \right) \cdot \phi \left( m \right) = 2^{\alpha - 1} \cdot \phi \left( m \right) \leqslant 2^{\alpha - 1} \cdot m = \tfrac{{p - 1}}
    {2}
    $ equality occurs iff $\displaystyle
    m = 1
    $

    Hence if $\displaystyle p$ is not of the form $\displaystyle 2^{\alpha}+1$ (that is $\displaystyle m>1$) there's always a non-quadratic residue that is not a generator.

    But, if p is of the form $\displaystyle 2^{\alpha}+1$, then all non-quadratic residues are also generators.
    Last edited by PaulRS; Jan 14th 2009 at 05:03 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. elementary number theory question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 9th 2011, 09:23 AM
  2. Probability/Number Theory question
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Nov 30th 2009, 08:46 PM
  3. number theory question
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 21st 2009, 05:09 AM
  4. Number theory Question 1
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 14th 2009, 04:04 AM
  5. General number theory question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 22nd 2007, 05:17 PM

Search Tags


/mathhelpforum @mathhelpforum