Editing Greatest common divisor (section)

=== Definition ===
The ''greatest common divisor'' (GCD) of [[integer]]s {{mvar|a}} and {{mvar|b}}, at least one of which is nonzero, is the greatest [[positive integer]] {{mvar|d}} such that {{mvar|d}} is a [[divisor]] of both {{mvar|a}} and {{mvar|b}}; that is, there are integers {{mvar|e}} and {{mvar|f}} such that {{math|1=''a'' = ''de''}} and {{math|1=''b'' = ''df''}}, and {{mvar|d}} is the largest such integer. The GCD of {{mvar|a}} and {{mvar|b}} is generally denoted {{math|gcd(''a'', ''b'')}}.{{refn|Some authors use {{math|(''a'', ''b'')}},<ref name="Long 1972 33" /><ref name="Pettofrezzo 1970 34" /><ref name="Hardy&Wright 1979 20" /> but this notation is often ambiguous. {{harvtxt|Andrews|1994|p=16}} explains this as: "Many authors write {{math|(''a'', ''b'')}} for {{math|g.c.d.(''a'', ''b'')}}. We do not, because we shall often use {{math|(''a'', ''b'')}} to represent a point in the Euclidean plane."}}

When one of {{math|''a''}} and {{math|''b''}} is zero, the GCD is the absolute value of the nonzero integer: {{math|1=gcd(''a'', 0) = gcd(0, ''a'') = {{abs|''a''}}}}. This case is important as the terminating step of the [[#Euclidean algorithm|Euclidean algorithm]].

The above definition is unsuitable for defining {{math|gcd(0, 0)}}, since there is no greatest integer {{math|''n''}} such that {{math|1=0 × ''n'' = 0}}. However, zero is its own greatest divisor if ''greatest'' is understood in the context of the divisibility relation, so {{math|gcd(0, 0)}} is commonly defined as {{math|0}}. This preserves the usual identities for GCD, and in particular [[Bézout's identity]], namely that {{math|gcd(''a'', ''b'')}} [[generating set of an ideal|generates]] the same [[ideal (ring theory)|ideal]] as {{math|{{mset|''a'', ''b''}}}}.<ref>Thomas H. Cormen, ''et al.'', ''Introduction to Algorithms'' (2nd edition, 2001) {{isbn|0262032937}}, p. 852</ref><ref>Bernard L. Johnston, Fred Richman, ''Numbers and Symmetry: An Introduction to Algebra'' {{isbn|084930301X}}, p. 38</ref><ref>Martyn R. Dixon, ''et al.'', ''An Introduction to Essential Algebraic Structures'' {{isbn|1118497759}}, p. 59</ref> This convention is followed by many [[computer algebra system]]s.<ref>e.g., [[Wolfram Alpha]] [https://www.wolframalpha.com/input/?i=gcd%280%2C+0%29 calculation] and [[Maxima computer algebra system|Maxima]]</ref> Nonetheless, some authors leave {{math|gcd(0, 0)}} undefined.<ref>Jonathan Katz, Yehuda Lindell, ''Introduction to Modern Cryptography'' {{isbn|1351133012}}, 2020, section 9.1.1, p. 45</ref>

The GCD of {{mvar|a}} and {{mvar|b}} is their [[greatest element|greatest]] positive common divisor in the [[preorder]] relation of [[divisibility]]. This means that the common divisors of {{mvar|a}} and {{mvar|b}} are exactly the divisors of their GCD. This is commonly proved by using either [[Euclid's lemma]], the [[fundamental theorem of arithmetic]], or the [[Euclidean algorithm]]. This is the meaning of "greatest" that is used for the generalizations of the concept of GCD.