Results 1 to 3 of 3

Math Help - Primitive roots modulo p, cyclotomic polynomials - Challenge problem!

  1. #1
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1

    Primitive roots modulo p, cyclotomic polynomials - Challenge problem!

    Let \Phi_n(x) be the nth cyclotomic polynomial. Show that r is a primitive root \mod p if and only if \Phi_{p-1}(r) \equiv 0 \mod p.

    I suspect NonCommAlg will be the first to bite!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Bruno J. View Post
    Let \Phi_n(x) be the nth cyclotomic polynomial. Show that r is a primitive root \mod p if and only if \Phi_{p-1}(r) \equiv 0 \mod p.

    I suspect NonCommAlg will be the first to bite!
    haha ... it's not really a challenge, is it? anyway, if r is a primitive root modulo p, then modulo p: \ r^d - 1 \neq 0, for any 0 < d < p - 1. therefore modulo p: \ \Phi_d(r) \neq 0 because \Phi_d(r) \mid r^d - 1.

    but \Phi_{p-1}(r)\prod \Phi_d(r)=r^{p-1} - 1 \equiv 0 \mod p, where the product is over the set \{d: \ \ d \mid p-1, \ d < p-1 \}. thus \Phi_{p-1}(r) \equiv 0 \mod p.

    conversely, suppose \Phi_{p-1}(r) \equiv 0 \mod p and r^d - 1 \equiv 0 \mod p, for some d < p-1, \ d \mid p-1. then in (\mathbb{Z}/p)[x] we'll have x-r \mid \Phi_d(x), \ x-r \mid \Phi_{p-1}(x). thus x^{p-1} - 1=(x-r)^2f(x),

    for some f(x) \in (\mathbb{Z}/p)[x]. then taking (formal) derivative we'll get (p-1)r^{p-2} \equiv 0 \mod p, which is obviously impossible.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Quote Originally Posted by NonCommAlg View Post
    haha ... it's not really a challenge, is it?
    For you it isn't!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. One small problem with cyclotomic polynomials
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 27th 2010, 07:27 PM
  2. cyclotomic polynomials
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: January 9th 2010, 07:25 AM
  3. primitive pth root of unity and cyclotomic fields
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: December 14th 2009, 10:32 PM
  4. Primitive roots modulo 101
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 10th 2009, 07:25 PM
  5. problem in primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 14th 2008, 07:14 PM

Search Tags


/mathhelpforum @mathhelpforum