## Tag Archives: relatively prime

### There are m distinct pᵏmth roots of unity over a field of characteristic p, for p a prime not dividing m

Let $n = p^km$, where $p$ is a prime not dividing $m$, and let $F$ be a field of characteristic $p$. Prove that there are $m$ distinct $n$th roots of unity over $F$.

Note that $x^n-1 = x^{p^km}-1$ $= (x^m)^{p^k}-1$ $= (x^m-1)^{p^k}$. That is, the distinct $n$th roots of unity over $F$ are precisely the distinct roots of $x^m-1$ over $F$.

If $m=1$, then certainly there is only 1 root of $x-1$.

Suppose $m > 1$. Now $D(x^m-1) = mx^{m-1}$, which has only the root 0 with multiplicity $m-1$. Clearly 0 is not a root of $x^m-1$, so that $x^m-1$ and its derivative are relatively prime, and thus $x^m-1$ is separable. Hence there are $m$ distinct $m$th roots of unity over $F$, and so $m$ distinct $n$th roots of unity over $F$.

### In an algebraic integer ring, two elements whose norms are relatively prime generate the whole ring

Let $\mathcal{O}$ be the ring of algebraic integers in a number field $K$. Suppose $\alpha,\beta \in \mathcal{O}$ such that $N(\alpha)$ and $N(\beta)$ are relatively prime. Prove that $(\alpha,\beta) = (1)$.

Recall that $N(\alpha)$ and $N(\beta)$ are rational integers. By Bezout’s identity, there exist rational integers $h$ and $k$ such that $hN(\alpha) + kN(\beta) = 1$. Note that $N(\alpha)/\alpha$ is an algebraic integer (being a product of algebraic integers) and is in $K$; hence $N(\alpha)/\alpha \in \mathcal{O}$. Likewise, $N(\beta)/\beta \in \mathcal{O}$. So $h(N(\alpha)/\alpha) \alpha + k(N(\beta)/\beta) \beta = 1$, and we have $(1) \subseteq (\alpha,\beta)$. Hence $(1) = (\alpha,\beta)$.

### Exhibit a pair of algebraic integers in QQ(sqrt(-5)) which are relatively prime but for which Bezout’s identity does not hold

Show that $3$ and $1 + \sqrt{-5}$ are relatively prime as algebraic integers in $\mathbb{Q}(\sqrt{-5})$, but that there do not exist algebraic integers $\lambda,\mu \in \mathbb{Q}(\sqrt{-5})$ such that $3\lambda + (1+\sqrt{-5})\mu = 1$.

Let $a+b\sqrt{-5}$ be an arbitrary integer in $\mathbb{Q}(\sqrt{-5})$. Since $-5 \equiv 3 \not\equiv 1$ mod 4, $a$ and $b$ are integers. Note that $N(a+b\sqrt{-5}) = a^2 + 5b^2$. If this element has norm 3, then taking this equation mod 5 we have $a^2 \equiv 3$. Note, however, that the squares mod 5 are 0, 1, and 4. In particular, no algebraic integer in $\mathbb{Q}(\sqrt{-5})$ has norm 3.

Now $N(3) = 9$ and $N(1+\sqrt{-5}) = 6$; if these elements have a factorization, then some factor must be a unit. Thus both $3$ and $1 + \sqrt{-5}$ are irreducible as integers in $\mathbb{Q}(\sqrt{-5})$. By Theorem 7.7 in TAN, the units in this ring are precisely $\pm 1$, so that 3 and $1 + \sqrt{-5}$ are not associates.

If $\delta|3$ and $\delta|(1+\sqrt{-5})$, then since $N(\delta) \neq 3$, $N(\delta) = \pm 1$, and thus by Lemma 7.3 in TAN $\delta$ is a unit. That is, every common divisor of $3$ and $1+\sqrt{-5}$ is a unit, so that these elements are relatively prime.

Suppose now that there are integers $a,b,c,d$ such that, with $\lambda = a+b\sqrt{-5}$ and $\mu = c+d\sqrt{-5}$, we have $3\lambda + (1+\sqrt{5})\mu = 1$.Comparing coefficients, we have $3a+c-5d = 1$ and $3b+c+d = 0$. Mod 3, these equations reduce to $c+d \equiv 1$ and $c+d \equiv 0$, a contradiction. So no such $\lambda$ and $\mu$ exist.

### Relatively prime polynomials over a field have no common roots

Let $F$ be a field and let $p,q \in F[x]$ be relatively prime. Prove that $p$ and $q$ can have no roots in common.

We noted previously that $F[x]$ is a Bezout domain. In particular, if $p$ and $q$ are relatively prime then there exist $a,b \in F[x]$ such that $ap + bq = 1$. If $\zeta$ is a root of both $p$ and $q$, then we have $1 = 0$, a contradiction.

### Gaussian integers having relatively prime norms are relatively prime

Let $\alpha,\beta \in \mathbb{Z}[i]$. Prove that if $N(\alpha)$ and $N(\beta)$ are relatively prime integers, then $\alpha$ and $\beta$ are relatively prime in $\mathbb{Z}[i]$.

Suppose $\gamma$ is a common factor of $\alpha$ and $\beta$. Say $\gamma\xi = \alpha$ and $\gamma\eta = \beta$. In particular, note that $N(\gamma)|N(\alpha)$ and $N(\gamma)|N(\beta)$. Since $N(\alpha)$ and $N(\beta)$ are relatively prime, $N(\gamma) = 1$. Thus $\gamma$ is a unit, and so $\alpha$ and $\beta$ are relatively prime in $\mathbb{Z}[i]$.

### Gaussian integers which are relatively prime need not have relatively prime norms

Exhibit two Gaussian integers $\alpha$ and $\beta$ which are relatively prime in $\mathbb{Z}[i]$ but such that $N(\alpha)$ and $N(\beta)$ are not relatively prime integers.

Note that $1+2i$ and $1-2i$ have norm 5. Using this previous exercise, $1+2i$ and $1-2i$ do not divide each other, and thus are relatively prime. In particular, $1+2i = (-1+i)(1-2i) + (-i)$. However, these elements both have norm 5, and so their norms are not relatively prime.

### A fact about residue systems

Fix a natural number $n$. A residue system mod $n$ is a set $S$ of integers such that every integer is congruent mod $n$ to a unique element of $S$. Suppose $S$ and $bS$ are both residue systems mod $n$; prove that $b$ and $n$ are relatively prime.

First suppose $n = 0$. In this case, the only residue system is $\mathbb{Z}$. Certainly then $b\mathbb{Z}$ is only a residue system if $b = \pm 1$; thus 1 is a greatest common divisor of $n$ and $b$, and hence these two are relatively prime.

Now suppose $n > 0$ and that $S$ and $bS$ are residue systems mod $n$. In particular, there exists $s \in S$ such that $bs \equiv 1$ mod $n$. Say $kn = bs - 1$, so that $bs - kn = 1$. Thus 1 is a greatest common divisor of $b$ and $n$, so that these are relatively prime.

### Compute the GCD of 7 and 0

Determine whether 7 and 0 are relatively prime. More generally, compute their greatest common divisor.

Note that 7 divides 7 since $1 \cdot 7 = 7$ and 7 divides 0 since $0 \cdot 7 = 0$. Now suppose $k$ is an integer dividing both 7 and 0; certainly $k$ divides 7. Thus 7 is a greatest common divisor of 7 and 0.

In particular, since $7 \neq \pm 1$, 7 and 0 are not relatively prime.

### Solve the Postage Stamp Problem in two denominations over the integers

Let $a$ and $b$ be relatively prime positive integers. Prove that every sufficiently large integer $N$ can be expressed as a linear combination $ax + by = N$ where $x$ and $y$ are nonnegative. That is, prove that there is an integer $N_0$ such that whenever $N \geq N_0$, such a linear combination exists. More specifically, prove that $ab - a - b$ cannot be expressed in this way but that every integer greater than $ab-a-b$ can. (So, every “postage” greater than $ab-a-b$ can be obtained using only stamps of denominations $a$ and $b$.)

We begin with a lemma.

Lemma: Let $a$ and $b$ be positive integers with $\mathsf{gcd}(a,b) = 1$. Then there exist integers $x$ and $y$ such that $ax + by = 1$ and $0 \leq x < b$. Moreover, if $b > 1$, $x \neq 0$. Proof: A solution $(x,y)$ exists since $a$ and $b$ are relatively prime by Bezout’s Identity. By this previous exercise, all solutions $(x,y)$ have the form $(x_0 + mb, y_0 - ma)$ where $(x_0,y_0)$ is a particular solution and $m \in \mathbb{Z}$. In particular, we may choose $(x_0,y_0)$ so that $x_0$ is a least residue mod $b$. Finally, $x_0 \neq 0$ if $b \neq 1$ since otherwise $y_0b = 1$ has a solution in the integers, a contradiction. $\square$

Now we wish to show that $ax+by = ab-a-b$ has no nonnegative solutions $(x,y)$. Suppose to the contrary that such a solution exists. Rearranging, we see that $a(x-b) = -(a+b)$. Since $b$, $y$, and $a$ are positive, $x-b < 0$. Thus $x < b$. On the other hand, reducing the equation $ax + by = ab-a-b$ mod $b$, we have $ax \equiv -a$ mod $b$. Since $\mathsf{gcd}(a,b) = 1$, $x \equiv -1$ mod $b$. Thus we have $x = b-1$. Similarly, $y = a-1$. But then $ab-a-b = a(b-1) + b(a-1) = 2ab-a-b$, so that $ab= 0$. This is a contradiction since $a$ and $b$ are both positive; thus no such solution $(x,y)$ exists.

Note that if $a = 1$, then for all $N \geq ab-a-b+1$ we have $aN + b0 = N$. Similarly if $b=1$. Thus we may assume from now on that $a,b \geq 2$. We now proceed by induction to show that for all $N \geq ab-a-b+1$, there exist nonnegative $x$ and $y$ such that $ax+by=N$.

For the base case, we show that $ax+by = N_0 = ab-a-b+1$ has a solution $(x,y)$ in the nonnegative integers. By the lemma, since $b \neq 1$ we have $ax_0+by_0 = 1$ for some integers $x_0$ and $y_0$ with $0 < x_0 < b$. Note that $a(x_0-1) + b(y_0+a-1) = ab-a-b+1$. We wish to show that $x_0-1$ and $y_0+a-1$ are nonnegative. First, since $x_0 > 0$, we have $x_0 \geq 1$, so that $x_0-1 \geq 0$. Now suppose $y_0+a-1 < 0$. Then $y_0+a \leq 0$, and thus $y_0 \leq -a$. Then $by_0 \leq -ab$, so that $1 = ax_0+by_0 \leq ax_0-ab = a(x_0-b) < 0$, a contradiction. Thus $y_0+a-1 \geq 0$, as desired.

For the inductive step, suppose that for some $N \geq ab-a-b+1$ we have $ax+by=N$ with $x,y \geq 0$. Also write $ax_0 + by_0 = 1$ as in the base case. Now $a(x+x_0) + b(y+y_0) = N+1$, and $x+x_0 > 0$. If $y+y_0 \geq 0$, then $a(x+x_0) + b(y+y_0) = N+1$ is a nonnegative linear combination of $a$ and $b$. Suppose then that $y+y_0 < 0$. Note the following.

 $ab-a-b+1$ < $N+1$ $ab-a-b+1-b(y+y_0)$ < $N+1 - b(y-y_0)$ $ab-a-b+1 - b(y+y_0)$ < $a(x+x_0)$ $b-1-\dfrac{b}{a} + \dfrac{1}{a} - \dfrac{b}{a}(y+y_0)$ < $x+x_0$ (since $a > 1$) $b-1+\dfrac{1}{a} - \dfrac{b}{a}(y+y_0+1)$ < $x+x_0$

Now since $y+y_0 < 0$, we have $y+y_0+1 \leq 0$. Thus $\dfrac{b}{a}(y+y_0+1) \leq 0$. Thus $b-1+\frac{1}{a} < x+x_0$, and we have $b \leq x+x_0$. Moreover, since $0 \leq a+y_0-1$, we have $y+1 \leq a+y_0+y$, and since $y \geq 0$, $0 \leq a+y_0+y$. Thus $a(x+x_0-b) + b(y+y_0+a) = N+1$ is a nonnegative linear combination of $a$ and $b$.

Note that our algorithm is constructive. As an example, consider $a = 8$ and $b = 5$. Then $ab-a-b+1 = 28$, and we have $(4)5 + (1)8 = 28$ and $(5)5 + (-3)8 = 1$. That is, $x_0 = 5$ and $y_0 = -3$. Since $1+(-3) = -2 < 0$, we write $(4+5-8)5 + (1-3+5)8 = (1)5 + (3)8 = 29$, and so forth.

### In a finite solvable group with no nontrivial normal subgroups relatively prime to p, the p-core contains its centralizer

Let $p$ be a prime dividing the order of the finite solvable group $G$. Assume $G$ has no nontrivial normal subgroups of order prime to $p$. Let $P = O_p(G)$ be the largest normal $p$-subgroup of $G$ (cf. this previous exercise). Prove that $C_G(P) \leq P$; i.e., that $C_G(P) = Z(P)$.

If $G$ is simple, then $G \cong Z_p$ for some prime $p$. In this case, $P = G$ (by definition), and we have $C_G(P) = Z(P) = G$.

Suppose $G$ is not simple. Then nontrivial normal subgroups of $G$ exist. Let $K \leq G$ be a minimal nontrivial normal subgroup; by this previous exercise, $K$ is an elementary abelian $q$-group for some prime $q$. By our hypothesis, in fact $q = p$. In particular, $P = O_p(G)$ is nontrivial.

Let $N = C_G(P)$, and let $\pi$ denote the set of primes dividing $|N|$ except $p$. ($p$ indeed does divide $N$ since, as a $p$-group, $Z(P)$ is nontrivial.) Note that $Z(P) \leq C_G(P)$ is normal and that $C_G(P) \leq N_G(P) = G$ is normal. Letting $H$ be a Hall $\pi$-subgroup of $N$ and $Q$ a Sylow $p$-subgroup, we have $N = QH$ by Lagrange. Note that $Z(P) \leq Q$. Suppose this inclusion is strict; that is, there are elements in $Q$ which are not also in $Z(P)$. Then these elements are not in $O_p(G)$. However, note that if $xO_p(G) \in G/O_p(G)$. (@@@)

We now consider $Z(P) H$. Since $Z(P) \leq P$, $H \leq C_G(Z(P))$. Now if $zh \in Z(P) H$, note that $(zh)H(zh)^{-1} = zhHh^{-1}z^{-1}$ $= zHz^{-1} = Hzz^{-1} = H$. Thus $H \leq Z(P) H$ is normal; since $H \leq Z(P) H \leq N$ is a Hall subgroup, it is in fact the unique subgroup of $Z(P) H$ of order $|H|$. Thus $H$ is characteristic in $Z(P) H$.

Recall that $C_G(P) \leq N_G(P) = G$ is normal, so that $H$ is normal in $G$. Since $|H|$ is prime to $p$ by construction, $H = 1$. Thus $C_G(P) = Z(P)$.