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]$.

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.