# What is Gcd: Definition and 101 Discussions

In mathematics, a GCD domain is an integral domain R with the property that any two elements have a greatest common divisor (GCD); i.e., there is a unique minimal principal ideal containing the ideal generated by two given elements. Equivalently, any two elements of R have a least common multiple (LCM).A GCD domain generalizes a unique factorization domain (UFD) to a non-Noetherian setting in the following sense: an integral domain is a UFD if and only if it is a GCD domain satisfying the ascending chain condition on principal ideals (and in particular if it is Noetherian).
GCD domains appear in the following chain of class inclusions:

rngs ⊃ rings ⊃ commutative rings ⊃ integral domains ⊃ integrally closed domains ⊃ GCD domains ⊃ unique factorization domains ⊃ principal ideal domains ⊃ Euclidean domains ⊃ fields ⊃ algebraically closed fields

View More On Wikipedia.org
1. ### I Question on Primitive Roots and GCDs

I have a question about a certain fact from the book of Nussbaumer "Fast Fourier Transform and Convolution Algorithms" in the chapter of Number-theoretic transformation. I have quoted the relevant passage once. There it says: This quotation refers to ##q## being a prime number. But then it...
2. ### Find the GCD of the given complex numbers (Gaussian Integers)

Hello guys, I am able to follow the working...but i needed some clarification. By rounding to the nearest integer...did they mean? ##z=1.2-1.4i## is rounded down to ##z=1-i##? I can see from here they came up with simultaneous equation i.e ##(1-i) + (x+iy) = \dfrac{6}{5} - \dfrac{7i}{5}## to...
3. ### Coloring each k-th unit in a circle of n units

suppose you write, clockwise, n numbers (or "units", doesn't matter) in a circle. you then color, clockwise, each k-th number. you do this until you've colored all n numbers, or until you've reached an already colored number. let x be the number of colored numbers. i've figured that if...
4. ### Can anyone please review/verify my proofs for gcd problem?

Proof: (a) Suppose that gcd(a, b)=1. Let d=gcd(a+b, a-b). By definition of the greatest common divisor, we have that d##\mid##(a+b) and d##\mid##(a-b). This means d##\mid##[(a+b)+(a-b)] and...
5. ### I Understanding the Results of gcd(x,n)

Hello, I read something about to which I have a small question of understanding. Before I would like to outline it a little. So we have the primes ##p## and ##q## and we know ##p|x## and ##n = p\cdot q## furthermore it follows that ##p|n## also holds. Now it was said that if ##p|x##, then...
6. ### MHB Calculating LCD and GCD of 2 Sets of Numbers

Determine $\textit{gcd}(2^4 \cdot 3^2 \cdot 5 \cdot 7^2,\quad 2 \cdot 3^3 \cdot 7 \cdot 11)$ and $\textit{lcm}(2^3 \cdot 3^2 \cdot 5,\quad 2 \cdot 3^3 \cdot 7 \cdot 11)$ ok the example appeared to have combine the 2 sets on gcd but I am still ? there is no book answer for this:confused:
7. ### Why is Excel telling me the GCD of 1.13*100 and 100 is 4?

In Microsoft Excel, if I type in the formula =GCD(113,100) then it gives me the correct answer of 1. However, if I type in =GCD(1.13*100,100), which means the same thing, it tells me 4. What's going on and how can I fix it? Thanks
8. ### Finding 5 Positive Integers with GCD Difference

Homework Statement Do five positive integers exist such that the positive difference between any two is the greatest common divisor of those two numbers? Homework EquationsThe Attempt at a Solution I found four such numbers, ##\{6,8,9,12\}##. I did this in an ad hoc way though without any real...
9. ### I How do computers evaluate the GCD of two integers?

Do they use the Euclidean Algorithm?
10. ### MHB How to Find the GCD and LCD in Mathematics?

$$\tiny{g1.1.2 \qquad UHW412}$$ \begin{align*}\displaystyle S&=gcd(2^4\cdot3^2\cdot 5\cdot 7^2,2\cdot3^3\cdot 7\cdot 11)\\ &=gcd(35280,4158)\\ W|A&=126\\ \end{align*} ok I tried to find a direct example but the powers and bases are mixed the answer came from W|A just interested in...

40. ### GCD & LCM of 6 Integers: Exponential Form

Homework Statement What is the greatest common divisor and least common multiple of the integers below (answer should be left in exponential form)? 2^{3}, 3^{3}, 5^{1}, 11^{2}, 13^{3} and 2^{1}3^{3}5^{2}7^{4}13^{1}Homework Equations The Attempt at a Solution This is exactly the way the...
41. ### Number of positive divisiors with gcd condition

Let n be a positive integer and a be a positive divisor of n. Is there any general formula to find the number of positive divisors b of n such that (a,b)=1 ?.
42. ### Proving Linear Manipulation to Reduce to GCD of Two Numbers

Given two numbers m and n, I need to prove that if a linearly manipulate them I can reduce them to their gcd. example:- 5 and 3. 3+3-5=1 which is their gcd. For that I assumed m as gx and n as gy where g is their gcd and x&y are co-prime. So if I am able to prove that linear combination of...
43. ### Find GCD of a and b: Express as Integer Combination

RESOLVED Homework Statement Let a = 123, b = 321. Compute d = gcd(a,b) and express d as an integer combination of ra + sb.Homework Equations This is a question (3.1, page 70 of Michael Artin's Algebra). For those who do not have the book, this problem is relevant to the section on subgroups...
44. ### Question on finding the GCD of 4 numbers

Homework Statement a_1, a_2, b_1, b_2 are all positive integers greater than one. Given that (a_2-1)/(a_1*a_2-1)=(b_2-1)/(b_1*b_2) Show that GCD(a_2-1,a_1*a_2-1,b_2-1,b_1*b_2)=1 Homework Equations (a_2-1)/(a_1*a_2-1)=(b_2-1)/(b_1*b_2) The Attempt at a Solution If I let...
45. ### The GCD forms a subgroup of the integers

Let r and s be positive integers. Show that {nr + ms | n,m ε Z} is a subgroup of Z Proof: ---- "SKETCH" ----- Let r , s be positive integers. Consider the set {nr + ms | n,m ε Z}. We wish to show that this set is a subgroup of Z. Closure Let a , b ε {nr + ms | n,m ε...
46. ### MHB Is there an algorithm for finding x and y in a GCD problem?

Since 2 is gcd of 2008 and 8002, I can write 2=2008x+8002y for integers x and y. Is there an algorithm for finding x and y?
47. ### Finding Solutions for LCM and GCD Equations in Number Theory

Homework Statement Solve in N^2 the following system of equations: 1- gcd(x,y)=7 and Lcm(x,y)=91 2- x+y=24 and Lcm =40 The Attempt at a Solution Let d=gcd(x,y) I said there exists an α and β so that x=dα and y=dβ and gcd(α,β)=1 And after doing some work i reached that α divides αβ=13...
48. ### Abstract algebra: monic gcd of polynomials in a subfield problem

Homework Statement Let K \subseteq L be fields. Let f, g \in K[x] and h a gcd of f and g in L[x]. To show: if h is monic then h \in K[x]. The Attempt at a Solution Assume h is monic. Know that: h = xf + yg for some x, y \in K[x]. So the ideal generated by h, (h) in L[x] equals...
49. ### Is (a,b) the GCD of a and b in a Divisibility Proof?

Figured it out nvm
50. ### Proving De Morgan's Laws for GCD and LCM: A Natural Number Proof

Let n be a natural number, and let S be the set of all natural numbers that divide n. For a, ,b in S, let gcd(a, b) = a /\ b and lcm(a, b) = a \/ b. For each x in S, let x' denote n/x. Do de Morgan's laws hold for this system? (gcd = greatest common divisor, lcm = lowest common...