Tag Archives: greatest common divisor

Compute the greatest common divisor of two ideals in ZZ[sqrt(-5)]

Compute the greatest common divisor of the ideals (1-2\sqrt{-5}) and (2) in \mathbb{Z}[\sqrt{-5}].

Recall that ((1-2\sqrt{-5}),(2)) = (1-2\sqrt{-5},2). Since 1 = 1-2\sqrt{-5} + 2\cdot \sqrt{-5}, this ideal contains 1, and so ((1-2\sqrt{-5}),(2)) = (1).

Factor some ideals in ZZ

Find the prime factorizations of the ideals A = (70) and B = (150) in \mathbb{Z}. Compute ((70),(150)).

Evidently 70 = 2 \cdot 5 \cdot 7 and 150 = 2 \cdot 3 \cdot 5^2, so that (70) = (2)(5)(7) and (150) = (2)(3)(5)^2. Since \mathbb{Z} is a unique factorization domain, (2), (3), (5), and (7) are prime since 2, 3, 5, and 7 are prime.

Now ((70),(150)) = (70,150) = (10), since 70 = 7 \cdot 10, 150 = 15 \cdot 10, and 10 = 150 - 2 \cdot 70.

Over ZZ, if (a,b) is maximal then gcd(a,b) is prime

Let a,b \in \mathbb{Z} such that (a,b) is maximal as an ideal in \mathbb{Z}. What can be said about a and b?

Since \mathbb{Z} is a principal ideal domain, (a,b) = (d) for some d. If (d) is maximal, then it is prime, so that d is a prime element. Moreover, d is a greatest common divisor of a and b. So \mathsf{gcd}(a,b) is prime.

Compute the greatest common divisor of two polynomials over QQ

Compute the greatest common divisor of p(x) = x^4 + 3x^3 + 10x^2 + 18x + 24 and q(x) = x^4 + 2x^3 + 13x^2 + 12x + 42 in \mathbb{Q}[x].

We will carry out the Euclidean algorithm. Note that p(x) = q(x) + (x^3-3x^2+6x-18), q(x) = (x^3-3x^2+6x-18)(x+5) + (22x^2+132), and x^3-3x^2+6x-18 = (22x^2+132)(\frac{1}{22}x - \frac{3}{22}). In particular, 22x^2+132 is a greatest common divisor of p(x) and q(x) in \mathbb{Q}[x]. Since 22 is a unit, we see that x^2 + 6 is also a greatest common divisor.

Indeed, p(x) = (x^2+6)(x^2+3x+4) and q(x) = (x^2+6)(x^2+2x+7). Note that x^2+3x+4 is irreducible in \mathbb{Z}[x] (hence \mathbb{Q}[x]) since \{a+b=3, ab=4 \} has no integer solutiions, and similarly x^2+2x+7 is irreducible, and these are not associates.

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.

A fact about divisibility in ZZ[i]

Prove that if a and b are relatively prime in \mathbb{Z}, then they are relatively prime in \mathbb{Z}[i].

Suppose a,b \in \mathbb{Z} are relatively prime. Then there exist x,y \in \mathbb{Z} such that ax + by = 1. Suppose now that \gamma is a common divisor of a and b; say a = \gamma \xi and b = \gamma \eta. Then \gamma(x \xi + y \eta) = 1 in \mathbb{Z}[i], so that \gamma is a unit. In particular, a and b are relatively prime in \mathbb{Z}[i].

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.

Find the common divisors of two Gaussian integers

FInd all of the nonunit, nonassociate, and nonconjugate common divisors of \alpha = 9+3i and \beta = -3+7i in \mathbb{Z}[i].

Note that 9+3i = 3(3+i). Since 3 is irreducible and does not divide -3+7i, we have \mathsf{gcd}(9+3i, -3+7i) = \mathsf{gcd}(3+i, -3+7i). Note that 3+i = (1+i)(2-i), and that these factors are irreducible since their norms are prime. Now -3+7i = (1+i)(2+5i), and these factors are also irreducible. Thus the greatest common divisor of \alpha and \beta is 1+i. Since this element is irreducible, it is (up to associates) the only nontrivial common divisor of \alpha and \beta.

Compute the GCD of 123 and 152

Compute the greatest common divisor d of 123 and 152. Moreover, find a and b such that 123a + 152b = d.

By repeated application of the division algorithm, we see that 152 = 1 \cdot 123 + 29, 123 = 4 \cdot 29 + 7, and 29 = 4 \cdot 7 + 1. Thus \mathsf{gcd}(123,152) = 1. Back-substituting to eliminate 29s and 7s, we see that 17 \cdot 152 - 21 \cdot 123 = 1.

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.