Gcd Definition and 101 Threads

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
Recent contents Top users
  1. A

    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. chwala

    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. Y

    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. M

    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. P

    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. karush

    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. SamRoss

    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. Mr Davis 97

    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. matqkks

    I How do computers evaluate the GCD of two integers?

    Do they use the Euclidean Algorithm?
  10. karush

    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...
  11. evinda

    MHB Show GCD of x,y,z is 1: Wave Hello!

    Hello! (Wave) We suppose that the integers $x,y,z$ satisfy $x^2+2y^2=z^2$ and $(x,y)=1$ . I want to show that $(x,z)=(y,z)=1$, and that $x$ is odd and $y$ even. I have tried the following: Let $(x,z)=d>1$. Then there exists a prime number $p$ such that $p \mid d$. Since $d \mid x$ and $d \mid...
  12. Arman777

    How to Create a Flowchart for Calculating GCD?

    1. The problem statement, all variables, and given/known data So we need to make a flowchart of GCD 2. Homework Equations The Attempt at a Solution Here my codes but something bothers me, 1-Take two positive integers N and M 2-If N>M go to step 3 3-K=M 4=K=K-1 5-Check, If K=1 go to...
  13. RoboNerd

    Finding GCD with Fibonacci: Base Case

    Homework Statement Suppose that m divisions are required to find gcd(a,b). Prove by induction that for m >= 1, a >= F(m+2) and b>= F(m+1) where F(n) is the Fibonacci sequence. Hint: to find gcd(a,b), after the first division the algorithm computes gcd(b,r). Homework Equations Fibonacci...
  14. J

    MHB GCD Proving Assistance - Get Help Now!

    I have encountered difficulties in solving this question. Your help is greatly appreciated!
  15. S

    O(log k) GCD Algorithm which yields x and y |GCD(a,b)=ax+by

    Homework Statement For some reason, my book's solution for this problem is given in a very wordy way, rather than in (Pascal-style) pseudo-code (which is what this book usually gives its solutions in). Here is the problem's statement and solution.: PROBLEM STATEMENT: PROBLEM SOLUTION...
  16. lfdahl

    MHB Can You Prove the GCD Inequality for Natural Numbers?

    Prove, that for all natural numbers, $a$ and $b$, with $b > a$: \[\frac{ab}{(a,b)}+\frac{(a+1)(b+1)}{(a+1,b+1)}\geq \frac{2ab}{\sqrt{b-a}}\] where $(m,n)$ denotes the greatest common divisor of the natural numbers $m$ and $n$.
  17. lfdahl

    MHB Finding GCD of $(1+\sqrt2)^{2017}$

    Find the greatest common divisor of the natural numbers, $a$ and $b$, satisfying: $$\left(1+\sqrt{2}\right)^{2017} = a + b \sqrt{2}.$$
  18. J

    Does the GCD of a set divide the GCD of any subset?

    Homework Statement If A is a set of integers and B is a set properly contained in A, does the greatest common denominator of all of the integers in A divide the greatest common denominator of all elements in B? Homework Equations None. The Attempt at a Solution Obviously gcd(A) divides any...
  19. RJLiberator

    [Abstract Algebra] GCD and Relatively Prime Proof

    Homework Statement If gcd(f(x),g(x)) = 1 and m,n ∈ ℕ, show that gcd(f(x)^m, g(x)^n) = 1. Homework EquationsThe Attempt at a Solution So I had previously proved this for non-polynomials: gcd(a,b)=1 then gcd(a^n,b^n)=1 Proof: a = p1*p2*...*pn b = p1*p2*...*pm then a^n = p1^n*p2^n*...*pn^n...
  20. C

    MHB Finding the Greatest EVEN Factor of X: Solving the GCD of m,n=2

    this one got me thinking for a while it starts like this: X=6m2+4n2 and Greatest Common Divisor(GCD) of (m,n)=2 what is the greatest EVEN number that must be a factor of X I started this question by thinking what they asked, the gratest number that is a factor of X then I need to calcualte X...
  21. Saitama

    MHB How can we use the concept of GCD to solve this problem?

    Hello all! I was trying to solve this problem which is supposed to be easy: Traversing Grid | CodeChef I couldn't solve it so I looked at some solutions, they seem to be using the concept of GCD. I am unable to understand why this works, please help. Thanks!
  22. PsychonautQQ

    Number theory GCD relatively prime question

    Homework Statement let m|d, n|d and gcd(m,n) = 1. show mn|d Homework Equations gcd(m,n) = d = mx + ny for x and y in integers The Attempt at a Solution d = mr d = ns 1 = mx + ny 1 = (d/r)x + (d/s)y I don't know, a bit lost, just moving stuff around and not making any real progress. Any tips?
  23. Colleen G

    Modular Congruence and GCD Proof

    Homework Statement If a≡b(mod n) and d=gcd(a.n), prove that d=gcd(b,n).[/B]Homework Equations If a≡b(mod n) → n|(a-b) → a-b =nk, for some k∈ℤ → a=nk+b If d=gcd(a.n) → d=ax+ny gcd(b,n)=d ↔ d|b and d|n, and if c|b and c|n, then c ≤ a. The Attempt at a Solution Since a=nk+b and d=ax+ny, then...
  24. PsychonautQQ

    How to prove that d|c in gcd(ac,b) = gcd(c,b) if gcd(a,b) = 1?

    Homework Statement if gcd(a,b) = 1, show that gcd(ac,b) = gcd(c,b) Homework Equations gcd(x,y) = xm + yn for integers n and m The Attempt at a Solution ax + by = 1 gcd(ac,b) = d gcd(c,b) = g ac = dr b = ds c = gm b = gn I've been setting up equations and rearranging things but can't make...
  25. PsychonautQQ

    Proving gcd(a+b,ab) = 1 for Relatively Prime Numbers

    Homework Statement Let a and b be relatively prime. Show that gcd(a+b,ab) = 1 Homework Equations ax+by = 1 for some integers x and y The Attempt at a Solution I set gcd(a+b,ab) = d. I'm now trying to show that d = 1 using elementary algebra techniques. a+b = rd ab = sd ax + by = 1I'm kind...
  26. PsychonautQQ

    Why Does gcd(a+b, a-b) Only Equal 1 or 2?

    Homework Statement Show that gcd(a+b,a-b) is either 1 or 2. (hint, show that d|2a and d|2b) Homework Equations d = x(a+b)+y(a-b) The Attempt at a Solution so by the definition of divisibility: a+b = dr a-b = ds adding and subtracting these equalities from each other we can arrive at where...
  27. PsychonautQQ

    Can I Use Factor Sets to Solve GCD Problems?

    Homework Statement if 1 = gcd(a,b), show that gcd(ac,b) = gcd(c,b) Homework Equations None The Attempt at a Solution My attempt at a solution: Let d = gcd(ac,b), Let g = gcd(c,b), I want to show that g|d and that d|g. I then went on to make a bunch of circular writing and get nowhere... I...
  28. Amcote

    Elementary Number Theory - GCD problems and proofs

    Problem 1 Suppose ab=cd, where a, b, c d \in N. Prove that a^{2}+b^{2}+c^{2}+d^{2} is composite. Attempt ab=cd suggests that a=xy, b=zt, c=xz. d=yt. xyzt=xzyt. So (xy)^{2}+(zt)^{2}+(xz)^{2}+(yt)^{2}=x^{2}(y^{2}+z^{2})+t^{2}(z^{2}+y^{2})=(x^{2}+t^{2})(z^{2}+y^{2}) Therefore this is...
  29. K

    Greatest Common Divisor of Four Distinct Positive Integers

    Homework Statement Give an example of a set S of four (distinct) positive integers such that the greatest common divisor of all six pairs of elements of S is 6. Homework Equations The Attempt at a Solution Can I say that my numbers are in the form? 6 12 18 30 Is this ok?
  30. 1

    What is the GCD of A and B on a Union Magma?

    Homework Statement Consider the following magma, S is not empty; P(S) is the power set. (P(S), U) Now, let A and B be in P(S). What is the GCD of A and B? Homework Equations The Attempt at a Solution If I choose a common divisor of A and B under unions, call it X, I get...
  31. B

    Expressing gcd of two polynomials as a linear combination

    Homework Statement Find the ##gcd(x^3+x^2-x, x^5+x^4+2x^2-x-1) ##and write it as a linear combination. Homework Equations The Attempt at a Solution I know the ##gcd(x^3+x^2-x, x^5+x^4+2x^2-x-1)=1## What I have so far is ##1. x^5+x^4+2x^2-x-1=(x^3+x^2-x)(x^2+1)+(x^2-1)## ##2...
  32. ArcanaNoir

    MHB Finding GCD in Gaussian Integers

    The problem asks to find a generator of the principal ideal <6+7i, 5+3i> in Z[i]. It is my understanding that such a generator must be a greatest common divisor of 6+7i and 5+3i. So, let's call this guy d, we should have d(a+bi)=6+7i and d(c+di)=5+3i. I'm not really sure how to find d. If I...
  33. T

    MHB Eulers phi function, orders, gcd

    Let a, k , l , m e Z>1 and let a^k=1 (mod m) and a^l= 1 (mod m). Let d=gcd(k,l) Prove that a^d=1 (mod m). I get already confused at the start: Is it true that k|phi(m) (Lagrange) but k can also be a multiple of the order of a (mod m) and then it can be the other way round. Can anybody clarify...
  34. I

    MHB Question about problem involving gcd

    HelloI am studying the problem given in the attachement. In the solution given, it says "Similarly \( d|\gcd(a,-b) \) ". I could not understand why this is so.thanks
  35. M

    Direct Proof of gcd(a,b) Corollary: ax+by=d

    Corollary from book: if d= gcd(a,b), then there exists integers x and y such that ax + by = d. This is not an obvious statement to me. Are there any direct proofs to prove this statement? The book proves this by induction. My proof: Suppose d = gcd(a,b) and a and b are positive integers. a...
  36. caffeinemachine

    MHB GCD is same in a field and its superfield.

    Let $K$ be an extension field of a field $F$ and let $p(t),q(t)\in F[t]$. Show that the monic greatest common divisors of $p(t)$ and $q(t)$ in $F[t]$ is same as the monic greatest common divisor of $p(t)$ and $q(t)$ in $K$.
  37. S

    MHB GCD Discrete Math: Proving GCD(a,b)=1

    Given that GCD(na,nb) = n * GCD(a,b) for a,b,n ∈ Z+ a) Prove that, if GCD(a,b) = 1 then GCD(a+b, a-b) = 1 or GCD(a+b,a-b) = 2 Hint: Let D = GCD(a+b, a-b), show that D | 2a and D | 2b thus D | GCD(2a,2b) then use the given b) Prove that, if GCD(a,B) = 1, then GCD(2a+b, a+2b) = 1 or GCD(2a+b...
  38. Petrus

    MHB GCD: Fastest Method to Simplify Fractions

    Hello, I wounder if there is more method Then using euclides algoritmen to solve this problem Simplifie/shorten(I Dont know how to say in english) \frac{196707}{250971} and I get GCD=6783 and get the answer \frac{29}{37} is there more method? Is there à method that is a lot more faster Then this...
  39. caffeinemachine

    MHB Gcd of polynomials is 1. There is an nxn matrix with determinant....

    Let $F$ be any field. Let $p_1,\ldots, p_n\in F[x]$. Assume that $\gcd(p_1,\ldots,p_n)=1$. Show that there is an $n\times n$ matrix over $F[x]$ of determinant $1$ whose first row is $p_1,\ldots,p_n$. When $n=2$ this is easy since then there exist $a_1,a_2\in F[x]$ such that $p_1a_1+p_2a_2=1$...
  40. N

    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. T

    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. A

    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. A

    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. N

    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. J

    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. P

    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. M

    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. R

    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. W

    Is (a,b) the GCD of a and b in a Divisibility Proof?

    Figured it out nvm
  50. A

    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...
Back
Top