Tag Archives: divisibility

If ζ is a primitive nth root of unity and d divides n, then ζᵈ is a primitive (n/d)th root of unity

Let \zeta be a primitive nth root of unity and let d|n. Prove that \zeta^d is a primitive n/dth root of unity.


Certainly (\zeta^d)^{n/d} = 1. Now if (\zeta^d)^t = 1, we have n|dt, and so n/d divides t. So n/d is the order of \zeta^d, and thus \zeta^d is a primitive n/dth root of unity.

If a is an integer greater than 1, then aᵈ-1 divides aⁿ-1 if and only if d divides n

Fix an integer a > 1. Prove that for all d,n \in \mathbb{N}, d divides n if and only if a^d-1 divides a^n-1. Conclude that \mathbb{F}_{p^d} \subseteq \mathbb{F}_{p^n} if and only if d|n.


If d|n, then by this previous exercise, x^d-1 divides x^n-1 in \mathbb{Z}[x], and so a^d-1 divides a^n-1 in \mathbb{Z}.

Conversely, suppose a^d-1 divides a^n-1. Using the Division Algorithm, say n = qd+r. Now a^n-1 = (a^d)^qa^r - a^r + a^r - 1 = a^r((a^d)^q-1) + (a^r-1). If q = 1, then we have a^r-1 = 0, so that r = 0 and d|n. If q > 1, then a^n-1 = a^r(a^d-1)(\sum_{i=0}^{q-1} (a^d)^i) + (a^r-1), and again we have r = 0, so that d|n as desired.

Recall that \mathbb{F}_{p^k} is precisely the roots (in some splitting field) of x^{p^k}-x. Now d|n if and only if p^d-1 divides p^n-1 by the above argument, if and only if x^{p^d-1}-1 divides x^{p^n-1}-1 by a previous exercise, if and only if x^{p^d}-x divides x^{p^n}-x, if and only if \mathbb{F}_{p^d} \subseteq \mathbb{F}_{p^n}.

xᵈ-1 divides xⁿ-1 if and only if d divides n

Prove that x^d-1 divides x^n-1 if and only if d divdes n.


Suppose d|n; say n = dt.

If t = 1, there is nothing to show. Suppose t > 1; then x^n-1 = (x^d)^t - 1 = (x^d-1)(\sum_{i=0}^{t-1} (x^d)^i), so that x^d-1 divides x^n-1.

Now suppose x^d-1 divides x^n-1. By the Division Algorithm in \mathbb{N}, we have q and r such that n = qd+r. Now x^n-1 = x^{qd}x^r - 1 = x^{qd}x^r -x^r + x^r - 1 = x^r(x^{qd}-1) + (x^r-1). If q=1, then (by the uniqueness part of the division algorithm in \mathbb{Q}[x]) x^r-1 = 0, so r = 0 and d|n. If q > 1, then x^n - 1 = x^r(x^d-1)(\sum_{i=0}^{q-1} (x^d)^i) + (x^r-1), and again we have r = 0, so d|n.

Exhibit an extended principal generator for an ideal in an algebraic integer ring

Let A = (3,1+2\sqrt{-5}) be an ideal in the ring of integers of K = \mathbb{Q}(\sqrt{-5}). Find an algebraic integer \kappa such that A = (\kappa) \cap \mathcal{O}_E, where E = K(\kappa).


We saw in the text that the class number of K is 2. Note that A^2 = (3), as indeed 3 = (1+2\sqrt{-5})^2 - 2 \cdot 3^2. Let \kappa = \sqrt{3}. By our proof of Theorem 10.6, A = \{ \tau \in \mathcal{O}_K \ |\ \tau/\kappa \in \mathcal{O}_K \}.

The exponent of the smallest power of an ideal which is principal divides the class number

Let \mathbb{O} be the ring of integers in an algebraic number field K of class number k. Let A be an ideal. Show that if k is minimal such that A^k is principal, then k|h.


This k is precisely the order of [A] in the class group of K. The result then follows by Lagrange’s Theorem.

On the set of ideals in a ring, divisibility is antisymmetric

Let A and B be ideals in a commutative unital ring R. Show that if A|B and B|A then A = B. Characterize the ideals which divide (1).


If A|B, then B = AC for some C. So B \subseteq A. Likewise, if B|A then A \subseteq B. Thus if A|B and B|A, then A = B.

Suppose A is an ideal such that (1) = AB for some ideal B. Now (1) \subseteq A, so that A = (1). That is, the only unit in the semigroup of ideals in R under ideal multiplication is (1) = R itself.

Over an algebraic integer ring, if (a)|(b) then a|b

Let \mathcal{O} be the ring of integers in an algebraic number field K, and let \alpha,\beta \in \mathcal{O}. Prove that if (\alpha)|(\beta), then \alpha|\beta in \mathcal{O}.


Recall that (\alpha)|(\beta) means that (\beta) = C(\alpha) for some ideal C. Now (\beta) \subseteq (\alpha), so that \beta \in (\alpha), and thus \beta = \alpha\gamma for some \gamma. Thus \alpha|\beta in \mathcal{O}.

Every algebraic integer divides a rational integer

Prove that every algebraic integer divides a rational integer. (Here we mean divisibility in the extended sense that \beta|\alpha if \alpha/\beta is an algebraic integer, not necessarily in a given field.)


Let \alpha be an algebraic integer with conjugates \alpha_1, \ldots, \alpha_k. (Recall that the \alpha_i are also algebraic integers.) Let N(\alpha) denote the norm of \alpha.

By Theorem 7.1 in TAN, N(\alpha) is a rational integer. By definition, \alpha|N(\alpha).

A fact about divisibility in a splitting field

Let E = \mathbb{Q}(\theta) be an algebraic extension of \mathbb{Q}, and let K = \mathbb{Q}(\theta_1,\ldots,\theta_k), where the \theta_i are the conjugates of \theta. Let \alpha,\beta \in E, and denote by \alpha_i and \beta_i the ith conjugate of \alpha and \beta (respectively). Show that if \beta|\alpha in E, then \beta_i|\alpha_i in E.


Suppose \alpha/\beta is an algebraic integer in K. In particular, \alpha/\beta \in F(\theta), so that \alpha/\beta = r(\theta) for some polynomial r(x).

Now \alpha/\beta is a root of some irreducible monic polynomial h(x) with rational integer coefficients. That is, h(r(\theta)) = 0. In particular, \theta is a root of h \circ r, so that the conjugates \theta_i are also roots of h \circ r. So h(r(\theta_i)) = 0 for each \theta_i, and thus \alpha_i/\beta_i = r(\theta_i) is a root of a monic polynomial with rational integer coefficients. So \alpha_i/\beta_i is an algebraic integer in K (in fact in \mathbb{Q}(\theta_i)).

Divisibility among rational integers in an algebraic number field

Let E = \mathbb{Q}(\theta) be an algebraic extension of \mathbb{Q} and let a,b \in \mathbb{Z}. Recall that if \alpha,\beta \in E are algebraic integers, we say that \beta|\alpha if the quotient \alpha/\beta is an algebraic integer. Prove that b|a in E if and only if b|a in \mathbb{Q}.


If b|a in \mathbb{Q}, then a/b is a rational integer. Certainly a/b \in E is an algebraic integer; so b|a in E.

Now suppose b|a in E. Since a/b is an algebraic integer and a rational number, a/b is a rational integer. So b|a in \mathbb{Q}.