Talk:Greatest common divisor/Archive 1

This page is an archive of past discussions. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Name

I don't know about you, but as far as I know (and forgive my Year 11 barin) in West Australian schools at least, this is known as the 'Highest Common Factor', not 'Greatest Common Divisor' - Mark Ryan

True... and its not just WA, its NSW (and VIC i think) as well -- in primary and high school they call it a HCF... but get to university, and they call it a GCD... I think GCD is the proper maths term, and HCF is just something the teaching profession in Australia invented, because they thought it would be easier to understand than GCD... -- SJK

When I was taught this in a British school, it was referred to as highest common factor, so this alternative nomenclature is not exclusive to Australia. It seems odd that nobody calls it greatest common factor or highest common divisor. Furby100 02:58, 31 May 2007 (UTC)

It is called 'highest common factor' in Indian schools as well. --Joshua Issac (talk) 12:22, 31 May 2010 (UTC)

When analyzing the runtime of Euclid's algorithm, it turns out that the inputs requiring the most steps are two successive Fibonacci numbers, and the worst case runtime is O(n), where n is the number of digits in the input (see Big O).

That's the case in Modified Euclid's Algorithm (with division modulo), not in Original Euclid's Algorithm (with subtraction). --Taw

What's this GCD algorithm called ? --Taw

def bgcd(a,b)
    g=0
    while(a&1==0 && b&1==0)
        g++
        a>>=1
        b>>=1
    end
    while b!=0
        if a&1 == 0
            a>>=1
        elsif b&1 == 0
            b>>=1
        else
            if (a>b)
                a-=b
                a>>=1
            else
                b-=a
                b>>=1
            end
        end
    end
    return a<<g
end

I don't know, but it is cool. Runtime is O(lg(n)); I wonder if it is faster than the ordinary division method? (I changed one line to make it a tiny bit simpler.) --AxelBoldt

It's much faster on most hardware because it doesn't use these slow modulo divisions, only ultra-fast shifts and substractions. If we're simplifying, here's an additional simplification. --Taw

Changed a multiplication to a bitshift. Also (I had to stare at it for a second to notice), the above algorithm loops infinitely if a is 0. So implementors beware; either don't pass a=0 in or add a check for it (what is GCD(0,n) and GCD(0,0) defined as anyway?) --JCipriani

GCD(0,n)=n for n>0 to the extent it is meaningful; GCD(0,0) is undefined or infinite. --Henrygb 11:44, 22 May 2006 (UTC)

Quicker GCD method

There is a possible quicker way to calculate Greatest Common Divisor at least on a computer anyway. This is because division by 2 in a computer is one of the quickest operations. The base ideas behind this algorithm are shown on the following link im not sure what the time complexity is but it should run faster. [1]

This person is actually talking about the exact same algorithm detailed above. It's the "binary GCD" algorithm, also described at [2] (which gives a link to the cut-the-knot.org) page. --JCipriani

Examples of no gcd

Would this article be the right place to put an example of an integral domain with two elements that don't have a gcd?

I think of this example:

R=\mathbb {Z} [{\sqrt {-3}}],a=4=2\cdot 2=(1+{\sqrt {-3}})(1-{\sqrt {-3}}),b=(1+{\sqrt {-3}})\cdot 2

where $1+{\sqrt {-3}}$ and $2$ are two "maximal common divisors" but they are not associated, so there is no greatest common divisor.

--SirJective 17:40, 25 Nov 2004 (UTC)

I now inserted the example. --SirJective 22:53, 26 Jan 2005 (UTC)

greatest common denominator

KneeLess wrote:

rv, a denominator IS a divisor, just another name.

You are of course right! What you are not right about is saying that a greatest common divisor is a greatest common denominator.

For example, I give you two integers, 6 and 9. Their greatest common divisor if of course 18. How about their greatest common denominator? There is none, because there are no denominators and no fractions around whatsoever.

So, I explained in my edit summary, the greatest common divisor is a more general thing than the greatest common denonminator. They coincide only when we talk about fractions, but the notion of greatest common divisor has meaning way beyond that. As such, these concepts are not equivalent, and are not synonimous. Oleg Alexandrov 16:56, 2 Apr 2005 (UTC)

Oh, I see. Thanks for actually telling me what the problem is, instead of having a revert war. I did make a redirect from Greatest common denominator to this article, is that a problem? -- KneeLess 18:42, 2 Apr 2005 (UTC)

No revert wars (TM) :) The redirect is all right. Oleg Alexandrov 18:53, 2 Apr 2005 (UTC)

Actually we were both wrong. Greatest common divisor of 6 and 9 is 3. We meant the least common multiple, which for 6 and 9 is 18. Oleg Alexandrov 19:29, 2 Apr 2005 (UTC)

Error in property

It is stated in the page that:

If m is any integer, then gcd(m·a, m·b) = m·gcd(a, b) and gcd(a + m·b, b) = gcd(a, b). If m is a nonzero common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m.

However, this is only true if m is a non-negative integer, since gcd is a non-negative integer.

Example: -1 x gcd(a,b) =< 0 , but, gcd(-a,-b) >= 0.

jff 13:46, 26 September 2006 (UTC)

Can you find it by scientific calculator?

Is there a function for finding the GCD in a calculator? The current way takes too much time, guessing which two/three numbers...etc.--80.227.100.62 09:42, 13 November 2006 (UTC)

You can use the Euclidean_algorithm. You don't even need a scientific calculator for that. There is no quick and easy formula. In the future, please ask questions at the wikipedia reference desk [3]. Article discussion pages are meant for discussions concerning the article, not the subject. S Sepp 23:23, 13 November 2006 (UTC)

removing the link to Greatest common divisor of two polynomials

i removed this link because the referenced article talks about some tricks from "vedic mathematics" to calculate the the gcd of some simple polynomials. this "vedic mathematics" cannot be found in the mathematical literature (see http://www.sacw.net/DC/CommunalismCollection/ArticlesArchive/NoVedic.html)

Lowest common factor

Why does lowest common factor redirect here? As I understand it, the lowest common factor between two natural numbers will always be 1. This is completely different from the highest common factor/greatest common divisor. Furby100 02:59, 31 May 2007 (UTC)

"Lowest common factor" is pointless, and is only seen when "highest common factor" is meant --Rumping (talk) 00:06, 24 April 2008 (UTC)

I'd argue that "lowest common factor" is equally likely to be used (incorrectly) to indicate the lowest common multiple. Perhaps it should be a disambiguation page, or not exist at all. Dcoetzee 04:17, 7 January 2009 (UTC)

Expected value?

I need some help making sense of this (I know almost no number theory). Our text says:

Clearly, the probability of two integers sharing a factor d is $\propto d^{-2}$ . Thus, the normalization constant is given by the limiting probability that two integers are coprime, which is 1/ζ(2) = 6/π², where ζ is the Riemann zeta function. Further, the limiting probability that k independently chosen integers are coprime is 1/ζ(k).

Shouldn't the first sentence say that this probability is equal to d^-2? As in, the probability that two random integers are both divisible by 3 is equal to 3^-2. This, I agree would be clear. It seems like what is needed is that the probability that d is the gcd is proportional to d^-2, since this is what seems to be used below. But it's not clear to me why this is true. Any help?

Does anyone have a reference for this material? Is it in Nymann, "On the probability that k positive integers are relatively prime"? (I can't get the PDF of that paper.) Staecker (talk) 00:23, 6 July 2009 (UTC)

OK I've found the reference, and I think that the argument in the article is bogus, so I'm removing it. Replacing with just the statement and the reference. Please if anybody can address my question above feel free to re-add the argument. Staecker (talk) 17:27, 11 July 2009 (UTC)

Probabilities / Expected Value

The section on probabilities and expected value should define how the integers in question are randomly selected. Without this, the information in this section has very little meaning. ATBS 04:10, 21 September 2009 (UTC)ATBS

Image & integers

The image was removed with the comment "Removed unexplained image because it makes no sense, and does not correspond to gcd." The only thing I could find in the article is that GCD is defined as requiring two integers. Hyacinth (talk) 08:01, 25 March 2013 (UTC)

Actually, GCD can be defined for any commensurate figures; if gcd(m,n) = k, then gcd(mα, nα) = k&salpha;. I'll see what I can do with the article. — Preceding unsigned comment added by Arthur Rubin (talk • contribs) 08:10, 27 March 2013

Is 0 a divisor of 5 ?

GCD(48, 18) = 6. It means that 6 is a divisor of both 48 and 18. It is even the greatest divisor of both 48 and 18.

GCD (0, 5) = 0. It means that 0 is a divisor of both 0 and 5. It is even the greatest divisor of both 0 and 5.

My questions : Is 0 really a divisor of 0? Is 0 really a divisor of 5 ? C.W. Vugs (talk) 08:08, 16 April 2013 (UTC)

Actually, GCD(0, 5) = 5. Every integer is a divisor of 0.—Emil J. 10:36, 16 April 2013 (UTC)

Sorry you are right. I mis'read GCD (a, 0) = 0.C.W. Vugs (talk) 14:59, 16 April 2013 (UTC)

Let us compare the different methods the writer uses to calculate GCD (a, b) in the section "Using Euclid's algorithm".

(i) The "modulo" method. The method subtracts multiples and stops when GCD (a, 0) = a or GCD (0, b) = b.

GCD (103, 23) = GCD(103 - 4•23, 23) = GCD (11, 23) = GCD (11, 23 - 2•11) = GCD (11, 1) = GCD (0, 1) = 1.

(ii) The "one by one" method. The method subtracts each time a single number and stops when GCD (a,a) = a.

GCD (103, 23) = GCD (80, 23)..... = GCD (34, 23) = GCD (11, 23) = GCD (11, 12) = GCD (11, 1) = GCD (10, 1) = ..... = GCD(1,1) = 1.

(iii) Euclid's algorithm. The algorithm subtracts multiples and stops when GCD (a, a) = a.

GCD (103, 23) = GCD (103 - 4•23, 23) = GCD ( 11, 23) = GCD (11, 23 - 2•11) = GCD (11, 1) = GCD (1, 1 ) = 1

Euclid didn't calculate a - a. His philosophy was : taking away a from a I have nothing left and how can I tell something about nothing?C.W. Vugs (talk) 18:43, 16 April 2013 (UTC)

Examples are too easy

The examples of the writer GCD (8, 12), GCD (54, 24), GCD (42, 56), GCD (9, 28), GCD (24, 60), GCD (18, 28) can easily be determined by mental arithmetic and no one will go for Venn-diagrams or factorization. Also too easy is GCD (48, 180). The factors here are too small and can easily be found. They will skip the explanation of Euclid's algorithm. Work out a difficult one, for instance GCD (11021, 11449). It will show that factorization is a time consuming activity and that Euclid's algorithm is a quick method.C.W. Vugs (talk) 08:02, 22 April 2013 (UTC)

How to calculate GCD (11021, 11449)

(i) Make successive long divisions : 11449 - 11021•1 = 428 11021 - 428•25 = 321 428 - 321•1 = 107 321 - 107•2 = 107 We prove that GCD (11449, 11021) = 107.

(ii) Go through the three identities from right to left : 107 is a common divisor of 107 and 321 ----> 107 is a common divisor of 321 and 428 ----> 107 is a common divisor 428 and 11021 ----> 107 is a common divisor of 11021 and 11449. In general: GCD(a, b) is a common divisor of a and b.

(iii) Go through the three identities from left to write : let d be a common divisor of 11449 and 11021 ----> d a common divisor of 11021 and 428 ----> d a common divisor of 428 en 321 ----> d a common divisor of 321 and 107 ----> In general : each common divisor of a and b is a divisor of GCD(a, b). (ii) and (iii) explain the name greatest common divisor and have to be used frequently.

(iv) Go through the identities from right to left : 107 = 428 - 321•1 = 428 - [11021 - 428•25]•1 = 428•26 - 11021•1 = [11449 - 11021•1]•26 - 11021•1 = 11449•26 - 11021•27 = 107. In general : the equation ax - by = GCD(a, b) has an unique solution in Z⁺ x Z⁺.

Summerizing Theorem of Euclid's algorithm. Each a en b ε Z⁺ have a GCD (a, b) with the following properties (i) GCD(a, a) = a (ii) If a ≠ b then GCD (a, b) can be calculated by Euclid's algorithm. (iii) GCD(a, b) ε Z⁺. (iv) GCD(a, b) is a common divisor of a and b. (v) Each common divisor of a and b is a divisor of GCD(a, b) [(iv) and (v) explain the name greatest common divisor] (vi) The equation ax - by = GCD(a, b) has a unique solution in Z⁺ x Z⁺. C.W. Vugs (talk) 15:10, 28 April 2013 (UTC)

Extensions

A property of GCD (a, b) : the linear Diophantine equation ax - by = GCD (a, b), a and b positive integers can be solved for x and y positive integers. The unique solution (x₁, y₁) can be found by Euclid's algorithm. C.W. Vugs (talk) 12:06, 6 May 2013 (UTC)

Extension 1 : the linear Diophantine equation ax + by = GCD (a, b), a and b positive integers doesn't have a solution for x and y positive integers, because ax ≥ GCD (a, b) and by ≥ GCD(a, b). However the equation has a solution for x and y integers. Rewrite the equation ax - b(-y) = GCD (a, b) and apply Euclid's algorithm. The solution (x₂, -y₂) can be found as a pair of positive integers. Thus x₂ is positive and y₂ is negative. C.W. Vugs (talk) 12:22, 6 May 2013 (UTC)

Extension 2 : If the linear Diophantine equation ax + by = GCD (a, b) has the solution (x₂, y₂) it has infinite many solutions, namely (x₂, y₂) + t•(a/GCD (a, b), -b/GCD (a, b)), t ε Z . C.W. Vugs (talk) 12:33, 6 May 2013 (UTC)

Extension 3 : the linear Diophantine equation ax - by = c, a, b and c positive integers has an unique solution (x₃, y₃) if GCD (a, b) is a divisor of c. If not then no solution. C.W. Vugs (talk) 12:42, 6 May 2013

Extension 4 : the linear Diophantine equation ax + by = c, a anb b positive integers and c an integer can be written as a(-x) - b(y) = |c| or as a(x) - b(-y) = |c| and Euclid's algorithme can be applied to find an unique solution in integers (x₄, y₄), if GCD (a, b) is a divisor of |c|. If not then no solution. C.W. Vugs (talk) 15:05, 6 May 2013 (UTC)

Extension 5 : If the linear Diophantine equation ax + by = c has a solution (x₅, y₅) then it has infinite many solutions namely (x₅, y₅) + t•(a/GCD (a, b), -b/GCD (a, b)). C.W. Vugs (talk) 15:14, 6 May 2013 (UTC)

Extension 6 : Wikipedia extension GCD (a, 0) = GCD (0, a) = a and GCD (0, 0) = 0 C.W. Vugs (talk) 15:36, 6 May 2013 (UTC)

Your basic property, extension 1, extension 3, extension 4 are all wrong. extension 2 and extension 5 are identical, and correct. extension 6 probably should be in the article somewhere. — Arthur Rubin (talk) 08:05, 9 May 2013 (UTC)

To see the correctness of extension 1, try to solve 899x + 841y = 29, x and y integers C.W. Vugs (talk) 11:25, 10 May 2013 (UTC)

See extension 2 to see why the positive/negative solution is not unique. — Arthur Rubin (talk) 16:24, 10 May 2013 (UTC)

Here you are correct. It is a sloppy mistake. Sorry. In extension 1 I write now a instead of an unique . I have to change my exercise as well. It is now : find a solution of 899x + 841y = 29, x and y integers. C.W. Vugs (talk) 18:05, 10 May 2013 (UTC)

Solution of 899x + 841y = 29 in Z. Write the equation in the form 899•(x) - 841•(-y) = 29. Calculate GCD (899, 841), applying Euclid's algorithm (1) 899 - 841•1 = 58 (2) 841 - 58•14 = 29. Thus GCD (899, 841) = 29. Further 29 = 841 - [899 - 841•1]•14 = 899•(-14) - 841•(-15). Solution of the original equation 899x + 841y = 29 : x = -14 and y = 15 C.W. Vugs (talk) 16:49, 12 May 2013 (UTC)

To see the difference between 2 and 5 you have to make even two exercises. Give the general solutions in Z of the two equations 39x + 51y = 3 and 39u + 51v = 21. C.W. Vugs (talk) 17:22, 12 May 2013 (UTC)

Extension 2 : Solve, if possible, the Diophantin equation 39x + 51y = 4 in Z. Rewrite this equation 39(x) - 51(-y) = 4 and calculate GCD (51, 39) by Euclid's algorithm : 51 - 39•1 = 12 ; 39 - 12•3 = 3. Stop. Work back 3 = 39 - 12•3 = 39 - [51 - 39•1]•3 = 39•(4) - 51•(-3) = 3. Comparing this with the equation 39(x) - 51(-y) = 4 we conclude that there isn't a solution for 39x + 51y = 4 in Z, because GCD (51, 39) is not a divisor of 4.

Extension 5 : Solve, if possible, the Diophantin equation 39x + 51y = 21. We can divide this equation by 3 to get 13x + 17y = 7 and rewrite in 13(x) - 17(-y) = 7. Find GCD (17, 13) : 17 - 13•1 = 4 ; 13 - 4•3 = 1. Stop. Work back 1 = 13 - 4•3 = 13 - [17 - 13•1]•3 = 13•(4) - 17•(3) = 1. Multiply this last identity by 7 to get 13•(28) - 17•(21) = 7. We have a solution of the equation 13•(x) - 17•(-y) = 7 namely (x, y) = (28, -21). The homogeneous equation 13x + 17y = 0 has as solutions t•(17, -13), t ε Z. Conclusion : The given equation 39x + 51y = 21 has an infinite number of solutions (x, y) = (28, -21) + t•(17, -13) in Z. C.W. Vugs (talk) 12:27, 16 May 2013 (UTC)

Extension 1 is correct. Example : the equation 5x + 9y = GCD (5, 9) = 1 doesn't have a solution in Z⁺, because 5x > 1 and 9y > 1. However the equation has a solution in Z, namely (x, y) = (2, –1). It has even an infinite number of solutions in Z, but that is extension 2 . This extension is also correct. In this example the general solution is (x, y) = (2, -1) + t•(9, -5), t ε Z . Both extensions can easely be generalized, as shown earlier. 84.24.10.61 (talk) 09:53, 20 May 2013 (UTC)

Definition of GCD

Writer's definition : greatest common divisor of two or more integers (at least one of which is not zero) is the largest positive integer that divides the integers without a remainder.

Comment : What about GCD (0, 0) = 0 ?

For centuries and still now was the GCD defined by the theorem of Euclid's algorithm. Your definition gives too little information and is therefore not workable. For instance :how to prove point 4 of your properties list If a divides the product bc and GCD (a, b) = d then a/d divides c ? C.W. Vugs (talk) 03:59, 9 May 2013 (UTC)

Wrong, and wrong. The "writer's definition" is the standard definition, and point 4 follow from the fact that the integers form a unique factorization domain.

If a divides bc, then we can write ax = bc
if GCD(a,b) = d, then we can write du = a and dv = b, with u and v relatively prime, producing dux = dvc, or ux = vc.
from ux = vc, using the UFD property, we can obtain:
1. u = αβ
2. x = γδ
3. v = αγ
4. c = βδ
Since u and v are relatively prime, α = 1, and u=β divides c = βδ. But u = a/d, and we are done.

Can you prove that using "Euclid's algorithm"? — Arthur Rubin (talk) 08:13, 9 May 2013 (UTC)

ax - by = GCD (a, b) = d. Divide this equation by d. This is possible because d is a common divisor of a and b.

(a/d)x - (b/d)y = 1. Multiply this equation by c.

(ac/d)x - (bc/d)y = c. Substitute ak = bc

(a/d)cx - (a/d)ky = c or (a/d)[cx - ky] = c. Thus (a/d) a divisor of c 84.24.10.61 (talk) 09:56, 9 May 2013 (UTC)

I agree up to and included 3. ux = vc. Using the fundamental theorem of arithmetic you factorize ux = vc = αβγδ. I assume that this are prime numbers. You factorize u = αβ, x = γδ, v = αγ (why not αβγ) and c = βδ (in my case c = δ). Then you conclude that α = 1. But I did assume that α was a prime number. Is my assumption not correct or is there something else wrong, and wrong. C.W. Vugs (talk) 12:01, 9 May 2013 (UTC)

Yes, it does follow from the fundamental theorem of arithmemtic, but α, β, γ, and δ are products of 0 or more primes, not primes, themselves. — Arthur Rubin (talk) 16:13, 9 May 2013 (UTC)

Please can somebody, writers, readers or users explain me what the meaning is of this statement. Especially what the meaning is of more primes, not primes themselves. C.W. Vugs (talk) 17:25, 9 May 2013 (UTC)

The Wikipedia extension GCD (0, 0) = 0 and GCD (a, 0) = a

(i) GCD (0, 0) = 0; never ever. The GCD , greatest common divisor is always still a divisor and one can't divide by 0.

(ii) GCD (a, 0) = a. Certainly not according to the theorem of Euclid's algorithm, which defines all properties of the GCD, because there you start dividing the largest of the two numbers, a, by the smallest of the two, 0, and again you can't divide by 0.

It is defendable taking the definition of the present article : the greatest positive integer that divides both a and 0. But this definition is too poor. Using that definition you can't prove the first property : all common divisors of a and b are divisors of GCD (a, b). C.W. Vugs (talk) 12:18, 25 May 2013 (UTC)

Absolutely wrong; it's not an extension; it's part of the definition. This may show how your attempt to make Euclid's algorithm the definition fails, but it may not even do that. First, a note on division.

a divides 0 for any a, as a × 0 = 0.

In particular, 0 divides 0, as 0 × x = 0 for any x.

One can then define GCD as c = GCD (a, b) if:

c divides a and b, and
If d divides a and b, then d divides c, and
c is nonnegative.

(This "alternative" definition, unlike your definition using Euclid's algorithm, should be in the article.)

Statements (i) and (ii) then become obvious. "Greatest" is a misnomer for GCD, unless you specify that "0" is greater than any integer, as all integers divide 0. — Arthur Rubin (talk) 18:30, 25 May 2013 (UTC)

I wouldn’t go as far as to call it misnomer. GCD is the common divisor greatest with respect to the partial order (or preorder, in general rings) given by divisibility. This happens to be almost the same thing as being greatest with respect to the usual order on the natural numbers, due to the fact that the usual order extends the divisibility order on positive integers, with the spectacular exception of zero, which is the greatest element in the divisibility order, but the smallest element in the usual order.—Emil J. 14:00, 27 May 2013 (UTC)

Writer's definition : greatest common divisor of two or more integers (at least one of which is not zero) is the largest positive integer that divides the integers without a remainder.

Arthur's definition : c = GCD (a, b) if 1. c divides a and b. 3. c is non-negative (my comment : writer tells us that c is positive, which corresponds with Euclid's algorithm) 2. If d divides a and b then d divides c (my comment : the writer is saying among all common divisors is c the greatest and not that each of them is a divisor of c. Pay attention to the ordening remarks of Emil.J. Nevertheless your point 2 is correct and follows not from writer's definition, but indeed from Euclid's algorithm.)

Further comment : Why not add some more properties that follow from Euclid's algorithm? For instance : the equation ax – by = GCD (a, b) is solvable in Z⁺ C.W. Vugs (talk) 19:41, 27 May 2013 (UTC)

GCD (0, 0) is not defined. Apply the slow but correct grade 7 method to find GCD (0, 0). Z is the set of the divisors of the first 0 and Z is the set of the divisors of the second 0. Z intersection Z = Z is the set of the common divisors of 0 and 0. But Z doesn't have a greatest number. C.W. Vugs (talk) 20:06, 28 May 2013 (UTC)

You are seriously misinterpreting Emil. I was saying that "greatest (common) divisor" should be replaced by "divisible by all common divisors"; Emil was saying that "greatest" should be reinterpreted as 0 being greater than all positive integers, while you are just ignoring the problem, by using the vulgar "definition", inaccurate for edge conditions, such as GCD(0,0). — Arthur Rubin (talk) 17:15, 29 May 2013 (UTC)

Emil too is talking about this vulgar definition. For instance the common divisors of 60 and 90 are {1, 2, 3, 5, 6, 10, 15, 30}. According to the smaller or equal relation (≤) it is a totally ordered set but according to the divisibility relation (|) it is a partially ordered set. For instance 6 ≤ 15 but 6 is not a divisor of 15. He added that they are almost equal. They are isomorphic. C.W. Vugs (talk) 15:20, 2 June 2013 (UTC)

Perhaps Emil is talking about the modified "vulgar" definition. However, in either case, use of the term "greatest" requires the theorem that there is a "greatest" one, which is obvious for the vulgar (or modified vulgar) definition except GCD(0,0). It's till important that the fact that "any common divisor divides the "greatest" common divisor" is prominently placed in the article, whether or not part of the definition. — Arthur Rubin (talk) 18:06, 2 June 2013 (UTC)

It is part of the definition, that follows from Euclid's algorithm. C.W. Vugs (talk) 08:25, 4 June 2013 (UTC)

It may be defendable to accept gcd(5,0)=5, but it certainly is counter intuitive, and not according to the historical approach. A divisor, also called factor, of a number is normally seen as not greater than the number. 82.75.155.228 (talk) 10:47, 13 October 2013 (UTC)

I just inserted some citations of number theory textbooks and some text to clarify the issues of gcd(0,0) and gcd(a,0). Hopefully this will make things clear to the readers of this article. — Anita5192 (talk) 21:19, 14 October 2013 (UTC)

Your recent changes confuse the issue. You can accurately say that some number theory textbooks undefine gcd(0,0); but you cannot support most, or that any reference works fail to define gcd(0,0)=0. — Arthur Rubin (talk) 18:35, 23 October 2013 (UTC)

Removed image

See File talk:Greatest common divisor chart.png for my objections on accuracy and usefulness of image. Waerloeg (talk) 00:14, 16 June 2014 (UTC)

Rational numbers

As the extension to rational numbers has been removed from the article as being unsourced, I've removed the image which only relates to that extension. See Image:Greatest common divisor.png. — Arthur Rubin (talk) 05:23, 31 October 2014 (UTC)

GCD or gcd?

The article is not consistent about whether the acronym GCD is upper case or lower case. My own preference would be all upper case. Any thoughts on that? --Pleasantville (talk) 16:04, 22 October 2015 (UTC)

It depends on the context. In running prose we should write "GCD" per MOS:CAPSACRS and MOS:ALLCAPS. But if used as the name of a mathematical function, we would normally use "gcd()" (unless a different notation would be established, as f.e. for sin() and Sin(), which mean different things). In "command line" examples, we typically use application/implementation-specific capitalization, if it deviates from that of the mathematical function.

--Matthiaspaul (talk) 19:04, 22 October 2015 (UTC)

Unhelpful image in lead

This image, added to the lead on 22 January, seems unreadable and unhelpful. At any given horizontal value, the various other values giving a gcd shown by any vertical distance are indicated by logos superimposed unreadably on top of each other. Can we delete it? Loraof (talk) 19:50, 17 April 2016 (UTC)

I agree completely. A gcd table like below could be helpful but may not belong in the lead. PrimeHunter (talk) 20:57, 17 April 2016 (UTC)

gcd	1	2	3	4	5	6	7	8	9	10	11	12
1	1	1	1	1	1	1	1	1	1	1	1	1
2	1	2	1	2	1	2	1	2	1	2	1	2
3	1	1	3	1	1	3	1	1	3	1	1	3
4	1	2	1	4	1	2	1	4	1	2	1	4
5	1	1	1	1	5	1	1	1	1	5	1	1
6	1	2	3	2	1	6	1	2	3	2	1	6
7	1	1	1	1	1	1	7	1	1	1	1	1
8	1	2	1	4	1	2	1	8	1	2	1	4
9	1	1	3	1	1	3	1	1	9	1	1	3
10	1	2	1	2	5	2	1	2	1	10	1	2
11	1	1	1	1	1	1	1	1	1	1	11	1
12	1	2	3	4	1	6	1	4	3	2	1	12

I agree that this diagram is unreadable and unhelpful. I can’t even figure out how to read it. Some diagrams in the leads of mathematics articles are difficult to read, but if explained well, often provide insights into the structure of the set of all possibilities. This diagram (the one in the lead), however, does nothing for me. — Anita5192 (talk) 21:02, 17 April 2016 (UTC)