## 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 $n$th root of unity and let $d|n$. Prove that $\zeta^d$ is a primitive $n/d$th 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/d$th 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 $i$th 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}$.