What is Greatest common divisor: Definition and 34 Discussions

In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted



gcd
(
x
,
y
)


{\displaystyle \gcd(x,y)}
. For example, the GCD of 8 and 12 is 4, that is,



gcd
(
8
,
12
)
=
4


{\displaystyle \gcd(8,12)=4}
.In the name "greatest common divisor", the adjective "greatest" may be replaced by "highest", and the word "divisor" may be replaced by "factor", so that other names include greatest common factor (gcf), etc. Historically, other names for the same concept have included greatest common measure.This notion can be extended to polynomials (see Polynomial greatest common divisor) and other commutative rings (see § In commutative rings below).

View More On Wikipedia.org
Recent contents Top users
  1. M

    Can anyone please review/verify this proof of greatest common divisor?

    Proof: Suppose gcd(a, b)=d. Then we have d##\mid##a and d##\mid##b for some a, b##\in## ##\mathbb{Z}##. This means a=md and b=nd for some m, n##\in## ##\mathbb{Z}##. Now we have lcm(a, b)=##\frac{ab}{gcd(a, b)}##...
  2. matqkks

    MHB Greatest common divisor

    What are the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two numbers? Should you use Euclid’s algorithm in some cases and prime decomposition in others?
  3. matqkks

    I How to evaluate the Greatest Common Divisor?

    What are the advantages of using Euclid's algorithm over prime decomposition to find the gcd of two numbers? Should you use Euclid’s algorithm in some cases and prime decomposition in others?
  4. V

    MHB GCD of Two Specified Sequences of Numbers: Conditions for Equality

    I consider two sequences of numbers $A=\{a_1,...,a_n\}$ and $B=\{k-a_1,...,k-a_n\}$, where $a_1 \le a_2 \le ... \le a_n \le k$. I am looking for such conditions under which: $gcd(a_1,...,a_n) = gcd(k-a_1,...,k-a_n)=1$. In more general form: $gcd(a_1,...,a_n) = gcd(k-a_1,...,k-a_n) \ge 1$. I...
  5. matqkks

    MHB Finding the Greatest Common Divisor of Two Integers

    How do computers evaluate the gcd of two integers?
  6. K

    Greatest Common Divisor Theorems definition clarification.

    Hi, I read definition of GCD theorem, from book and from mathWorld website. " There are two different statements, each separately known as the greatest common divisor theorem. This does not make sanse 1. Given positive integers and , it is possible to choose integers and such that ...
  7. K

    Greatest common divisor proof

    Hi, I need opinion about this problem. ================================================== question :Prove: If(a,b)= l and if ( "(a,b)=1" mean greatest common divisor of integers and b is 1 ) c|a (c divides a) and d|b (d divides b ) then (c,d)= 1. ( "(c,d)=1" mean...
  8. S

    I If pair of polynomials have Greatest Common Factor as 1 ....

    NOTE: presume real coefficients If a pair of polynomials have the Greatest Common Factor (GCF) as 1, it would seem that any root of one of the pair cannot possibly be a root of the other, and vice-versa, since as per the Fundamental Theorem of Algebra, any polynomial can be decomposed into a...
  9. S

    I Don't understand lemma about primitive polynomial product

    I was reading about Gauss's Lemma here: https://cims.nyu.edu/~kiryl/Algebra/Section_3.10--Polynomials_Over_The_Rational_Field.pdf Unfortunately, I am stuck on Lemma 3.10.1 that concludes that the product of a pair of primitive polynomials is itself primitive. I understand about how there is...
  10. S

    B Is there a lemma named for this?

    I'll call it the "Wheel Lug Lemma" for now. If there are a pair of integers p & q such that the Greatest Common Denominator is 1, and there is some number s that is product of p and an increasing whole number n, then the remainder of the division of s by q will cycle through all values of from...
  11. G

    MHB Is $\gcd(n, n+2) = 1$ or $2$ for any integer $n$?

    Decide which of the following is true or false. If false, provide a counterexample. (a) For any integer $n$, $\gcd(n, n+1) = 1$. (b) For any integer $n$, $\gcd(n, n+2) = 2$. (c) For any integer $n$, $\gcd(n, n+2) = 1$ or $2$. (d) For all integers $n, m:$ $\gcd(n, n^2+m) = \gcd(n,m)$. I...
  12. D

    Greatest common factor with exponents of first input

    ok so is there a function that exists (for all intents and purposes let's call it G(x,y) )where x= a^2*b^4*c y=a^4*b^2*d G(x,y) = a^2*b^4 basically gcd, but the exponents match those of the common prime factors of the first input (x) ******** equally useful would be a function where the...
  13. A

    Monic Greatest Common Divisor

    Homework Statement Find the monic greatest common divisor of two polynomials a = 6x6 + 12x5 - 6x4 -12x +12 and b = 3x4 - 3. Homework Equations The Euclidean Algorithm. The Attempt at a Solution Applying the Euclidean Algorithm, I have a = 6x6 + 12x5 - 6x4 -12x +12 = (3x4 - 3)(2x2 + 4x -2)...
  14. evinda

    MHB Greatest common divisor of polynomials

    Hello! :cool: I want to find the greatest common divisor of $x^4+1$ and $x^2+x+1$. I applied the Euclidean division and found that $x^4+1=(x^2+x+1) \cdot (x^2-x)+(x+1)$. So,isn't it like that: $gcd(x^4+1,x^2+x+1)=x+1$ ? But.. in my textbook,the result is $1$! Which of the both results is...
  15. S

    MHB How can I prove that gcd(a,b) is an integer and gcd(a/b, b/h) = 1?

    can I get hints on how to prove this question: let a,b be in Z(integer) with h=gcd(a,b) not equal to zero then [(a divide b), (b divide h)] are in Z. and gcd[ (a divide h, b divide h)]=1
  16. M

    MHB Greatest common divisor of a and b

    Hey! :o The greatest common divisor of $a$ and $b$ can be written as a linear combination of $a$ and $b$. Let the set $D=\{xa+yb|x,y \in Z\}$. a) $D$ contains non-zero elements. b) $D$ contains also positive numbers. c) The set of positive numbers of $D$ (let $D^+$) is $ \neq \varnothing$...
  17. matqkks

    MHB Greatest Common Divisor: Applications in Tiling and Number Theory

    Are there any real life applications of greates common divisor of two or more integers?
  18. matqkks

    Can the GCD and Euclidean Algorithm Solve Real Life Problems?

    Are there any real life applications of the greatest common divisor of two or more integers?
  19. Math Amateur

    MHB Greatest common divisor of two polynomials

    I am working on Exercise 8 of Dummit and Foote Section 9.2 Exercise 8 ==================================================================================== Determine the greatest common divisor of a(x) = x^3 - 2 and b(x) = x + 1 in \mathbb{Q} [x] and write it as a linear...
  20. B

    Proof using greatest common divisor.

    Homework Statement The problem went "If c|a and c|b then c|gcd(a,b) where cεN and a,bεZ" Homework Equations The Attempt at a Solution My proof went like this " Let a=cr and b=cs where r,sεZ. We want to show c|gcd(a,b). Lets start with cd=ax+by where d,x,yεZ since the gcd(a,b) can...
  21. R

    The greatest common divisor of n integers

    Homework Statement define the gcd of a set of n integers, S={a_1...a_n} Prove that exists and can be written as q_1 a_1+...+q_n a_n for some integers, q_1...q_n Homework Equations Euclid's Algorithm? The Attempt at a Solution I have the statement that gcd(a_1...a_n) = min( gcd(a_i, a_j)...
  22. M

    Greatest common divisor.

    Homework Statement prove that: x^y=(5x+3y)^(13x+8y) Homework Equations The Attempt at a Solution Can I say that x^y divides both 5x+3y and 13x+8y and go on from there or what? Then in case one u could multiply 5x+3y by 13 and 13x+8y by 5 and do the difference and you'll get that x^y divides...
  23. H

    What is the proof for a = gcd(a, b) when a|b?

    Homework Statement Suppose a, b ∈ N and a|b. Prove that a = gcd(a, b). Homework Equations Seems easy intuitively but actually proving it is giving me problems. The Attempt at a Solution I have been trying to use the fact that gcd(a,b)=na + mb here m and n are integeres but got stuck.
  24. T

    Greatest Common Divisor in a strange extension ring.

    Homework Statement I need to show that two elements in \textbf{Z}[\sqrt{-5}] have gcd = 1. The elements are 3 and 2+\sqrt{-5} Homework Equations The Attempt at a Solution My way of thinking was if I can show that both elements are irreducible, then they are both prime and hence...
  25. J

    A proof involving the greatest common divisor

    Homework Statement Don't have the book with me, but the problem basically asked me to prove that gcd(a,b)=1 \Rightarrow gcd(an,bn)=n Homework Equations Since gcd(a,b)=1 is a fancy way of saying a and b are relatively prime (or is "a and b are relatively prime" a fancy way of...
  26. A

    Can (2) Be Proved Without Knowing (1)?

    Homework Statement (1). If gcd(a,b) = d , gcd(a/d,b/d)=1 (2). If gcd(a,b) = d , then gcd(m,n) = 1 , where dm=a, dn=b (i don't know wether this statement is correct) Homework Equations n/a The Attempt at a Solution i kow how to prove (1) and (2), but i only proof (2) using...
  27. D

    Greatest common divisor question

    Homework Statement (b) Suppose a certain student’s ID number M satisfies gcd(M, 2010) > gcd(M, 271) > 1. Find all possible values for gcd(M, 2010). Be sure to explain your reasoning. [Note: both 271 and 67 are prime.] (c) Suppose that the ID number...
  28. K

    Greatest common divisor | Relatively prime

    Claim: n! + 1 and (n+1)! + 1 are relatively prime. How can we prove this? Can we use mathematical induction? Base case: (n=1) gcd(2,3)=1 Therefore, the statement is true for n=1. Assuming the statement is true for n=k: gcd(k! + 1,(k+1)! + 1)=1 (induction hypothesis), we need to show...
  29. R

    So the statement you made is true, but does not prove what you want it to prove.

    If there are integers s,t with as+bt=6, this implies that gcd(a,b)=6, right? And if gcd(a,b)=6, does this necessarily mean that a and b are not relatively prime since their gcd is not 1? (I have read that two integers a and b are relatively prime if gcd(a,b)=1).
  30. J

    Greatest common divisor

    Homework Statement if (a,c)=1 and (b,c)=1 prove that (ab,c)=1 Homework Equations I know that (a,c)=1 says that au+cv=1 and bs+ct=1 prove abq+cr=1 The Attempt at a Solution I set au+cv=bs+ct now I don't know what to do
  31. M

    Greatest common divisor problem help

    Homework Statement Given gcd(a,b)=1, what is the gcd(a^2+b^2, a+b) where ^=square. Homework Equations The Attempt at a Solution gcd(a^2+b^2, a+b) = gcd ( (a+b)^2 -2ab, a+b) which i think, we can reduce to gcd(2ab, a+b). Here is where I stucked. I am not sure how to proceed. Please...
  32. T

    Greatest common divisor of fractions and decimals

    Is it possible to calculate the greatest common divisor of decimals and fractions? As far as I know, the greatest common divisor is a number you can calculate for integers, but I wonder if it's possible to calculate it for decimals and fractions.
  33. P

    Greatest common divisor of polynomials

    HI there, I have a tiny question concerning the gcd of polynomials. Assume, \chi is the greatest common divisor of the polynomails p_{ij}, i,j=1,2. I then form q_{11}=p_{11}^2+p_{12}^2,\quadd q_{12}=p_{11}p_{21}+p_{12}p_{22},\quadd q_{21}=p_{21}p_{11}+p_{22}p_{12},\quadd...
  34. K

    What Is the Flaw in This Proof of the Greatest Common Divisor?

    Homework Statement Suppsoe a, b\innatural numbers, and d=GCD(a,b). Then d^2=GCD(a^2,b^2). I need to find where the proof goes wrong. Homework Equations The Attempt at a Solution By hypothesis, we have that d divides a and d divides b, so there are integres s and t with a=ds and...
Back
Top