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

    The problem related to GCD and LCM.

    Homework Statement Find the representation of 1 in terms of linear combination of 2003 and 205Homework Equations The previous questions ask me to find GCD and LCM, which is 1 and 410 615 respectivelyThe Attempt at a Solution And yes, I don't have any freaking idea to solve this :(
  2. U

    Abstract Algebra: GCD proof

    Homework Statement If (a,c) = 1 and (b,c) = 1, prove that (ab,c) = 1. Note that (x,y) refers to the greatest common divisor between x and y. 2. The attempt at a solution There is a theorem that says since (a,c) = 1, there exist integers u and v such that au + cv = 1. Likewise, there...
  3. E

    GCD of a and b Prime and Odd: 1 or p?

    Show that if a,b\in\mathbb{N}^+,\ \gcd(a,b) = 1 and p is an odd prime, then \gcd\left(a+b,\frac{a^p+b^p}{a+b}\right)\in \{1,p\}
  4. AlexChandler

    A Proof involving the GCD and divisibility

    Homework Statement If two integers a and b are relatively prime and if each divides an integer n, prove that their product ab divides nHomework Equations 1=sa+tb for some integers s and t (thm 1.35) gcd(a,b)=1 n=aa'=bb' The Attempt at a Solution I have tried many many different ways to...
  5. Z

    GCD Proof Check: 2 Problems Involving GCDs in Z

    I was doing a couple proofs (since I'm new to them) involving gcds and I just would like you guys to check them to see if I actually proved anything. There are 2 separate problems here. For both problems, a,b,c are in Z with a and b not both zero. PROBLEM 1 Homework Statement Prove...
  6. I

    GCD of ab,c = 1: Implications for a & b

    Homework Statement If gcd(ab,c) = 1 then gcd(a,c)=1 and gcd(b,c)=1 2. The attempt at a solution Well, if gcd(ab,c) = 1 we know that abk + cl = 1 for some integers k and l not really sure where to go from here... any hints?
  7. C

    GCD of two powers of 2, minus 1

    Hi everyone, this is not a homework question just a math puzzle I came across. Let a and b be any two natural numbers. And let (m,n) denote the GCD of m and n as usual. Prove (2^{a}-1,2^{b}-1) = 2^{(a,b)}-1 I'm thinking of double induction on a and b but I'm having trouble with the...
  8. R

    Proving LCM Formula and GCD for Non-Integers

    Hi, I encountered the following formula while reading, can anyone prove this: lcm(a,b)=gcd(a^{-1},b^{-1})^{-1} Also, how could one do the gcd for non-integer? for example we know that lcm(1/3,2/5)=2. then if we use the formula above then lcm(1/3,2/5)=1/gcd(3,5/2). then gcd(3,5/2) should be...
  9. Shackleford

    Can you prove this statement for any values of a and b?

    I'm not exactly sure how to prove or disprove this statement. Just by looking at the c, I'd say it's not true, but I'm not sure how to show it either way. If (a,b) = 1 and (a,c) = 1, then (ac,b) = 1. http://i111.photobucket.com/albums/n149/camarolt4z28/IMG_20110719_192439-1.jpg?t=1311127377
  10. AlexChandler

    Proof about primes and gcd

    Homework Statement prove that p is prime iff for any integer "a" either (a,p)=1 or p divides a (where (a,p) denotes the gcd of a and p) Homework Equations (a,b)= the greatest common factor of a and b The Attempt at a Solution I had no trouble with proving the forward direction...
  11. L

    Euclide's Algorithm to Calculate GCD

    Homework Statement Using Euclid's algorithm write a program with a function that determines and returns the GCD of two integer arguments. This is what i wrote, when i print the remainder is zero, How can i get the last remaninder before the zero value? :confused: Thanks Homework...
  12. M

    Algebra: Proving (a^2,b^2)=1 Using GCD Proof

    (a,b)=d means d is the GCD of a and b Question: Let (a,b)=1 Prove: (a^2,b^2)=1 The hint that we were given is to prove this by contradiction ... but, I have no idea how to go about even starting this proof ... Any and all help would be greatly appreciated!
  13. S

    Finding GCD of x,c,y,z: Fast & Easy

    can we find the value of gcd(x c y , z) easily and very fast using a computer. where 1. "c" represents "combinations" used in 'permutations and combinations'. 2. x is very very large number (ex: may be of 100 or 1000 numerical digits) 3. y is also large having 2 to 5 digits less than x...
  14. D

    Number theory: simple gcd question

    Homework Statement If ax+by=1, then (a,b)=1. Homework Equations The Attempt at a Solution I am just wondering if this is true. Because I know it is not true if ax+by=c, then (a,b)=c. Here is a proof I came up with: Suppose (a,b)=c, c>1.Then c|a and c|b, but then from our...
  15. D

    Number Theory: Simple Divisibility & GCD

    Homework Statement Prove that if N=abc+1, then (N,a)=(N,b)=(N,c)=1. Homework Equations The Attempt at a Solution Assume N=abc+1. We must prove (N,a)=(N,b)=(N,c)=1. Proceeding by contradiction, suppose (N,a)=(N,b)=(N,c)=d such that d\not=1 . Then we know, d | N and d | abc. Thus...
  16. A

    Can the GCD of Polynomials in a Field Always Be Reduced to 1?

    Homework Statement We know that the gcd of two polynomials can be written as gcd(p(x),q(x))=p(x)m(x) + q(x)n(x) for some n(x) and m(x) in F[x] F a fieldI want to show gcd(n(x),m(x))=1 for a fixed gcd(p(x),q(x)) The Attempt at a Solution Well, what I tried was to let D(x)=gcd(p(x),q(x))...
  17. T

    Showing elements in an extension field Z[sqrt(-5)] have gcd = 1

    Homework Statement Show that the elements 3 and 2+\sqrt{-5} in \textbf{Z}[\sqrt{-5}] have a greatest common divisor of 1, but the ideal I = (3, 2+\sqrt{-5}) is not the total. Conclude that I is not principle. Homework Equations The Attempt at a Solution I have got as far as...
  18. A

    Relationship among LCM, GCD, and coprimes

    Hi everybody, I am having an extremely hard time understanding a specific relationship that originates from the least common multiple of two or more numbers. According to "Number Theory and Its History" by Oystein Ore, it is not difficult to see that when one writes lcm(a,b,c) = p*a =...
  19. K

    Proving the GCD Property: A Challenge for Algebra Students

    urgent algebra GCD Proof problem Homework Statement let d=gcd(m,n). Prove that d=am+bn, where a,b are integers. Homework Equations use of induction and euclidean algorithm. The Attempt at a Solution i know when d being a generator and d=am+bn where m,n are generators, then...
  20. Y

    Largest GCD of consequtive elements in a sequence.

    Say I have a sequence a(n) = 100 + n^2 with n ranging through the positive integers. I want to find the largest number g(n) such that g(n) = gcd(a(n), a(n+1)). Let g be a number that divides both a(n) and a(n+1) g | 100 + n^2 and g | 100 + n^2 + 2n + 1 therefore g | 2n + 1. This means that g...
  21. S

    Understanding the Euclidean Algorithm for Finding GCDs in Q[sqrt 3]

    Hi. I need to find the GCD of two numbers in Q[sqrt 3]. Let's suppose these two numbers are 12 and 35. How would you go about finding the GCD of those in Q[sqrt 3]? thanks~
  22. I

    Is the gcd function symmetric?

    Just a quick theory question. I'd assume it is, but usually the bigger number goes first. e.g. gcd(10, 5) = 2 but does gcd (5, 10) = 2? My guess is yes. Thanks for the help.
  23. F

    Is my solution for this gcd correct?

    For the first part of this question: So if everything was done correctly is -55/16 my answer?
  24. E

    Degree of polynomial gcd

    Problem: Let R=Q[y] and suppose f,g \in F[x] both have degree 10 with respect to x and degree 6 with respect to y. Suppose h = gcd(f,g) has degree 4 with respect to x and degree 2 with respect to y. Derive an upper bound (as good as possible) on the number of distinct integers i such that...
  25. CalleighMay

    GCD in PROOF - Solving the Puzzle

    GCD in PROOF?? Hey everyone, I'm taking this course called "Number Theory" and am having a lot of difficulty with it. We're currently on "proofs" and i am having some issues. Last week was my first weeks classes. The first day my professor jumped right into the material without giving...
  26. R

    Number theory - gcd and linear diophantine equations

    Homework Statement Suppose that gcd(a, b) = 1 with a, b > 0, and let x0, y0 be any integer solution to the equation ax + by = c. Find a necessary and sufficient condition, possibly depending on a, b, c, x0, y0 that the equation have a solution with x > 0 and y > 0. Homework Equations...
  27. D

    Question about gcd and Mersene Numbers

    Hi, I've been going through an intro number theory book and trying to prove everything but I am stuck on this one exercise it says to show that gcd(M_e,M_f)=M_gcd(e,f) for all positive integers e and f where M_n=2^n-1. Is there a simple proof for this? I see these questions a...
  28. T

    Proving the Theorem: (b,c)=1 implies (a,bc)=(a,b)(a,c) in Number Theory

    Homework Statement Let a,b,c be integers. If (b,c)=1, then (a,bc)=(a,b)(a,c) Homework Equations This is difficult to answer because some theorems that we haven't proven yet, we can't use. The Attempt at a Solution Let g=(a,b) and h=(a,c), g and h are integers. That means g|a and g|b...
  29. H

    G x H: Proving Cyclicity with GCD = 1

    Homework Statement Let G and H be cyclic groups, with |G| = m and |H| = n. If gcd(m,n) =1, show that G x H is cyclic. The Attempt at a Solution Let a = (g,h) in G x H. Then |a| = lcm (|g|,|h|). Since gcd(m,n)=1, then lcm (m,n) = mn. Thus lcm (|g|,|h|) = lcm (m,n) = mn. so <a> = G x...
  30. D

    Isomorphism between groups, direct product, lcm, and gcd

    1. The problem statement, all variables and given/known data Let a,b, be positive integers, and let d=gcd(a,b) and m=lcm(a,b). Show ZaXZb isomorphic to ZdXZm Homework Equations m=lcm(a,b) implies a|m, b|m and if a,b|c then m|c. d=gcd(a,b) implies d|a, d|b and if c|a and c|b then d|c...
  31. T

    GCD of Polynomials: Is 1 Always the Solution?

    Would the GCD of x^2+x+c and (x-a)^2+(x-a)+c always be 1?
  32. B

    Proving GCD and LCM: A Step-by-Step Guide for Beginners

    I am *totally* blanking on how to even begin on this one. I need to prove that the gcd(a,b) | lcm[a,b]. I know that means that a| lcm[a,b] and that b | lcm[a,b] but I don't really know where to go from there. I think a small kickstart is all I really need for now. :) Thanks!
  33. H

    GCD(a+h,b+k) - Formula Given GCD(a,b) & GCD(h,k)?

    Is there a formula for gcd(a+h,b+k) given gcd(a,b) and gcd(h,k)?...jus wondering
  34. A

    Proving gcd(r,s)=1 with gcd(r^2-s^2, r^2+s^2)

    Can anyone help me with this? If gcd(r,s)=1 then prove that gcd(r^2-s^2, r^2+s^2)=1 or 2. i'm so confused.
  35. K

    Exploring the Role of GCD as a Generator of Ideals in Polynomial Rings

    Hi. Given a field F and the space of polynomials over it, F[x], I was wondering why it is that the monic generator of the ideal generated by any two polynomial f, g from F[x] is exactly the gcd of f and g. Thank you! Kriti
  36. T

    GCD approximation for type double numbers

    Hi, I am doing a phys experiment, and I find myself trying to obtain some pattern of quantization of some measurements, i.e., I'm trying to find a number (double) that divides at least a significant portion of my data, with an arbitrary remainder. Does anyone know of any algorithm that does this...
  37. MathematicalPhysicist

    Is my code for gcd function valid?

    i have to write the function gcd for c programme. here's my code: int gcd(int m, int n) { int s,r,x,y; if (m>=n) { r=m-(m/n)*n; for(x=m,y=n;r!=0;x=y,y=r) r=x-(x/y)*y; } if(n>m) { r=n-(n/m)*n; for(x=n,y=m;r!=0;x=y,y=r) r=x-(x/y)*y; }...
  38. J

    Finding the Greatest Common Divisor in Java: A Beginner's Guide

    I am a beginner programmer in Java. Just started learning the past few weeks. I'm taking a class and need to create a method that finds the greatest common divisor of two integers. I can assume that both are positive, but I cannot use the Euclidean Algorithm. I'm sort of lost, but I...
  39. L

    Solve Hard GCD Problems: Prove d=d1d2 with d1|a and d2|b

    1. If d|ab and gcd(a,b)=1, prove that d=d1d2 where d1|a and d2|b and gcd(d1,d2) = 1 Homework Equations 3. Let d1 = gcd(d,a). Thats all I know
  40. L

    Solving the GCD of 2^10 and 10!: A Number Trick?

    large number! 1. Finding gcd(2^10,10! Homework Equations 3. I attempted to try the Euclidean algorithm, but it would take forever. Is there a certain number trick?
  41. L

    GCD Associativity: Proving gcd(a,b,c) with Linear Combinations

    1.Show gcd(a,b,c) = gcd(a, gcd(b,c)) Homework Equations 3. My attempt is that gcd(a,b,c) can be written as the product of their prime factors. Let's say x is that product. The thing is, I know how to prove this using prime factorization but there has to be another method concerning...
  42. O

    Learn How to Find the GCD of 24 and 49 in Q[sqrt(3)] - Quick Help!

    A GCD question- urgent help! Find the GCD of 24 and 49 in the integers of Q[sqrt(3)], assuming that the GCD is defined. (Note: you need not decompose 24 or 49 into primes in Q[sqrt(3)]. Please teach me . Thank you very much.
  43. Z

    Proving the Relationship between GCD and Linear Combinations

    I remember this from awhile back but can't seem to find any justification. Why is the smallest positive linear combination of two numbers necessarily the GCD of the two numbers?
  44. M

    GCD proof in Number Theory

    Here is my problem: Prove or disprove: If gcd(m, n) = d, then the gcd(a, mn) = gcd(a,m) * gcd(a.n)/d. I can seem to get it started, sort of, but it just does not seem to get anywhere. I know by definition d | m and d | n. Then arbitrary integers x and y can be used such that m = xd and...
  45. A

    2 elevators problem, gcd

    Hello everyone, I have such problem: there are 2 elevators which go only upwards, and stop on only particular floors, each elevator is described by 2 numbers: (a,r) where a is a number of floor on which the elevator starts and r is a number which is a period of elevator's stops. For example, if...
  46. W

    GCD of x and y: Definition and Examples

    What does the notation gcd(x,y) means?
  47. A

    Help Needed: Solving Integer Equations with GCD = 1 - Angelo Spina

    I am a visitor of this beautiful site, my name is Angelo Spina, I would like to resolve the three following problems, in fact after many attempts I have not succeeded in it, for this reason I kindly ask you to give me a help. PROBLEM 1. If the equation y² + a p² = 2 x² (where a is a...
  48. honestrosewater

    Why is gcd important in number theory?

    I saw someone say this in another thread. Why is it so important? My best guess is that it has something to do with prime factorization, but that's a pretty wild guess.
  49. B

    Prove: GCD of a, b and d is Equal to GCD of a and b

    For a, b, c, d positive integers, and d = a + bc, prove that gcd(b, d) = gcd(a, b). I don't know about this. I can use the definition of gcd, the diophantine equation of the form as + bt = c and how it relates to the gcd, and the division algorithm theorem. I know that gcd(a, b) divides d...
  50. 1

    What is the relationship between GCD, LCM, and relatively prime numbers?

    Let a, b, and c be positive integers. I need to prove two items... 1. abc = GCD(a,b,c) * LCM(ab,bc,ac) 2. abc = GCD(ab,ac,bc) * LCM(a,b,c) where the GCD is the Greatest Common Divisor and the LCM is the Least Common Multiple. Could I go ahead and say that (a,b,c)=1, that...
Back
Top