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 nth 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 nth 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 mth roots of unity over F, and so m distinct nth 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).