I am reading this paper by Adleman,Lenstra on finding Irreducible polynomial over Finite field. Here in Section VI(Proof of correctness of Algo B) I came across this argument:

Let $q_i $ be a prime such that $q_i-1$ is square free. Then $\mathbb{Q}(\zeta_{q_i})$ contain a subfield $K$ such that $[K:\mathbb{Q}]=ord_{q_i}(p)$ and prime p is inert in $K$.

I am aware of following facts :

  1. Cyclotomic polynomial splits in $\mathbb{F}_p$ as degree = $ord_{q_i}(p)$ irreducible factors.
  2. Correspondence between splitting of ideal $ (p) $ in $\mathbb{Q}(\zeta_{q_i})$ and factorization of $\Phi_{q_i}(x)$ in $\mathbb{F}_p$.
  3. Since $ord_{q_i}(p) | q_i-1$, therefore there exist a field K' such that $[K':\mathbb{Q}]=ord_{q_i}(p)$.

But I am not sure of how these things give the claim given in the paper.


1 Answer 1


The galois group of cyclotomic field over $\Bbb Q$ is cyclic hence it will always contain such a subfield $\Bbb K$ and inertness follows from the fact that $\gcd([\Bbb K:\Bbb Q],[\Bbb Q(\zeta):\Bbb K])=1$ as $q-1$ is square free.


You must log in to answer this question.

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