1
$\begingroup$

I've been slowly grinding my way through a bunch of finite field/cyclotomic polynomial questions in my assignment, and I'm really stuck here.

The question asks: Prove that if $q$ is a prime modulo such that p is a primitive root modulo q, then $x^{q-1}+...+x+1$ is irreducible over $\mathbb{F}_p$ (Slightly confusing wording?)

From previous questions I've shown $x^n-1$ splits over E, an extension of $\mathbb{F}_p$ iff $n$ divides $p^d-1$, and that the degree of the splitting field of $x^n-1$ over $\mathbb{F}_p$ is the order of $p$ in $(\mathbb{Z}/n\mathbb{Z})^*$ (the multiplicative group).

Also, this related question and its answer makes no sense to me

Thanks

Edit: I totally misunderstood what "primitive root modulo q" meant. I now understand $p^{q-1}\equiv 1 \mod q$ and so $p$ has order $q-1$ in $(\mathbb{Z}/q\mathbb{Z})^*$. Still not sure where to go from here though.

$\endgroup$
5
  • 1
    $\begingroup$ Being a primitive root says that $p^{q-1}\equiv 1 \pmod q$ and $p^{n}\not\equiv 1 \pmod q$ for any $n$ smaller than $q-1$, i.e. the order of $p$ in $(\Bbb{Z}/q\Bbb{Z})^{*}$ is $q-1$, so by your remark the degree of the splitting field of $x^q-1$ over $\Bbb{F}_p$ is $q-1$. $\endgroup$
    – sharding4
    May 13, 2017 at 2:18
  • $\begingroup$ Oh what? I'm slightly more confused now, since I didn't think I was given which primitive root $p$ was. Why is it $p^{q-1}$? @sharding4 $\endgroup$
    – Adrian Hindes
    May 13, 2017 at 2:30
  • $\begingroup$ Nevermind I found the wikipedia page for "primitive root modulo n". Still lost on how to conclude it's irreducible from there using the splitting field note. $\endgroup$
    – Adrian Hindes
    May 13, 2017 at 2:47
  • $\begingroup$ Are you sure you quoted the problem correctly? If it had been “…if $q$ is a prime modulus such that…” I would have understood it. $\endgroup$
    – Lubin
    May 13, 2017 at 3:55
  • 1
    $\begingroup$ "Prove that if $q$ is a prime modulo such that $p$ is a primitive root modulo $q$..." is the exact wording. $\endgroup$
    – Adrian Hindes
    May 13, 2017 at 3:57

1 Answer 1

Reset to default
4
$\begingroup$

Try this:

The hypothesis is that $p^{q-1}$ is the smallest power of $p$ that is congruent to $1$ modulo $q$.

Now, what are the orders of the (cyclic) groups $\Bbb F_{p^m}^\times$? They are, of course, $p^m-1$, and a field $\Bbb F_{p^m}$ contains a primitive $q$-th root of unity if and only if $q|(p^m-1)$, i.e. if and only if $p^m\equiv1\pmod q$. Thus our hypothesis says that $\Bbb F_{p^{q-1}}$ is the first extension of $\Bbb F_p$ that contains a $q$-th root of unity $\zeta_q$. In other words, $\zeta_q$ generates an extension of degree $q-1$, so $X^{q-1}+\cdots+X+1$ is irreducible over $\Bbb F_p$

$\endgroup$
5
  • $\begingroup$ And irreducibility follows because $\zeta_q$ always has minimal polynomial $\Phi_q(x)$? $\endgroup$
    – Adrian Hindes
    May 13, 2017 at 4:28
  • $\begingroup$ Okay now I'm lost, why does that show it's irreducible? $\endgroup$
    – Adrian Hindes
    May 13, 2017 at 4:37
  • $\begingroup$ No, not at all. Irreducibility follows because you have an element $\zeta_q$ that generates an extension of degree $q-1$, so that its minimal polynomial (its irreducible polynomial) is of degree $q-1$, and divides every polynomial vanishing at $\zeta_q$. But $\Phi_q$ is such a polynomial, therefore divisible by that polynomial, and same degree, so equal. $\endgroup$
    – Lubin
    May 13, 2017 at 4:40
  • $\begingroup$ (addendum): note that $\Phi_5$ is not irreducible over $\Bbb F_{11}$, in fact it splits as a product of linears. $\endgroup$
    – Lubin
    May 13, 2017 at 4:45
  • $\begingroup$ Okay great, thanks so much! I was rather confused but that definitely cleared it up. $\endgroup$
    – Adrian Hindes
    May 13, 2017 at 4:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .