Editing Greatest common divisor (section)

== Overview ==

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

=== Example ===

The number 54 can be expressed as a product of two integers in several different ways:
: <math> 54 \times 1 = 27 \times 2 = 18 \times 3 = 9 \times 6.</math>

Thus the complete list of ''divisors'' of 54 is 1, 2, 3, 6, 9, 18, 27, 54.
Similarly, the divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24.
The numbers that these two lists have ''in common'' are the ''common divisors'' of 54 and 24, that is,
: <math> 1, 2, 3, 6. </math>

Of these, the greatest is 6, so it is the ''greatest common divisor'':
: <math> \gcd(54,24) = 6. </math>

Computing all divisors of the two numbers in this way is usually not efficient, especially for large numbers that have many divisors. Much more efficient methods are described in ''{{slink|#Calculation}}''.

=== Coprime numbers ===
{{Main|Coprime integers}}
Two numbers are called relatively prime, or [[coprime]], if their greatest common divisor equals {{math|1}}.<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Greatest Common Divisor|url=https://mathworld.wolfram.com/GreatestCommonDivisor.html|access-date=2020-08-30|website=mathworld.wolfram.com|language=en}}</ref> For example, 9 and 28 are coprime.

=== A geometric view ===
[[File:24x60.svg|thumb|upright|alt="Tall, slender rectangle divided into a grid of squares. The rectangle is two squares wide and five squares tall."|A 24-by-60 rectangle is covered with ten 12-by-12 square tiles, where 12 is the GCD of 24 and 60. More generally, an ''a''-by-''b'' rectangle can be covered with square tiles of side length ''c'' only if ''c'' is a common divisor of ''a'' and ''b''.]]
For example, a 24-by-60 rectangular area can be divided into a grid of: 1-by-1 squares, 2-by-2 squares, 3-by-3 squares, 4-by-4 squares, 6-by-6 squares or 12-by-12 squares. Therefore, 12 is the greatest common divisor of 24 and 60. A 24-by-60 rectangular area can thus be divided into a grid of 12-by-12 squares, with two squares along one edge ({{math|1=24/12 = 2}}) and five squares along the other ({{math|1=60/12 = 5}}).