Results 1 to 3 of 3

Thread: 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 $\displaystyle \Phi_n(x)$ be the $\displaystyle n$th cyclotomic polynomial. Show that $\displaystyle r$ is a primitive root $\displaystyle \mod p$ if and only if $\displaystyle \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 $\displaystyle \Phi_n(x)$ be the $\displaystyle n$th cyclotomic polynomial. Show that $\displaystyle r$ is a primitive root $\displaystyle \mod p$ if and only if $\displaystyle \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 $\displaystyle r$ is a primitive root modulo p, then modulo $\displaystyle p: \ r^d - 1 \neq 0,$ for any 0 < d < p - 1. therefore modulo $\displaystyle p: \ \Phi_d(r) \neq 0$ because $\displaystyle \Phi_d(r) \mid r^d - 1.$

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

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

    for some $\displaystyle f(x) \in (\mathbb{Z}/p)[x].$ then taking (formal) derivative we'll get $\displaystyle (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: Apr 27th 2010, 07:27 PM
  2. cyclotomic polynomials
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Jan 9th 2010, 07:25 AM
  3. primitive pth root of unity and cyclotomic fields
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Dec 14th 2009, 10:32 PM
  4. Primitive roots modulo 101
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: Nov 10th 2009, 07:25 PM
  5. problem in primitive roots
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 14th 2008, 07:14 PM

Search Tags


/mathhelpforum @mathhelpforum