Editing Greatest common divisor (section)

== Properties ==
* For positive integers {{math|''a''}}, {{math|1=gcd(''a'', ''a'') = ''a''}}.
* Every common divisor of {{math|''a''}} and {{math|''b''}} is a divisor of {{math|gcd(''a'', ''b'')}}.
* {{math|gcd(''a'', ''b'')}}, where ''a'' and ''b'' are not both zero, may be defined alternatively and equivalently as the smallest positive integer ''d'' which can be written in the form {{math|1=''d'' = ''a''⋅''p'' + ''b''⋅''q''}}, where ''p'' and ''q'' are integers. This expression is called [[Bézout's identity]]. Numbers ''p'' and ''q'' like this can be computed with the [[extended Euclidean algorithm]].
* {{math|1=gcd(''a'', 0) = {{abs|''a''}}}}, for {{math|''a'' ≠ 0}}, since any number is a divisor of 0, and the greatest divisor of ''a'' is {{math|{{abs|''a''}}}}.<ref name="Pettofrezzo 1970 34" /><ref name="Hardy&Wright 1979 20">{{harvtxt|Hardy|Wright|1979|p=20}}</ref>  This is usually used as the base case in the Euclidean algorithm.
* If ''a'' divides the product ''b''⋅''c'', and {{math|1=gcd(''a'', ''b'') = ''d''}}, then ''a''/''d'' divides ''c''.
* If ''m'' is a positive integer, then {{math|1=gcd(''m''⋅''a'', ''m''⋅''b'') = ''m''⋅gcd(''a'', ''b'')}}.
* If ''m'' is any integer, then {{math|1=gcd(''a'' + ''m''⋅''b'', ''b'') = gcd(''a'', ''b'')}}. Equivalently, {{math|1=gcd(''a'' mod ''b'',''b'') = gcd(''a'',''b'')}}.
* If ''m'' is a positive common divisor of ''a'' and ''b'', then {{math|1=gcd(''a''/''m'', ''b''/''m'') = gcd(''a'', ''b'')/''m''}}.
* If {{math|1=gcd(''a'', ''b'') = ''d''}}, then {{math|1=gcd(''a''/''d'', ''b''/''d'') = 1}}.
* The GCD is a [[Commutativity|commutative]] function: {{math|1=gcd(''a'', ''b'') = gcd(''b'', ''a'')}}.
* The GCD is an [[Associativity|associative]] function: {{math|1=gcd(''a'', gcd(''b'', ''c'')) = gcd(gcd(''a'', ''b''), ''c'')}}. Thus {{math|1=gcd(''a'', ''b'', ''c'', ...)}} can be used to denote the GCD of multiple arguments.
* The GCD is a [[multiplicative function]] in the following sense: if ''a''<sub>1</sub> and ''a''<sub>2</sub> are relatively prime, then {{math|1=gcd(''a''<sub>1</sub>⋅''a''<sub>2</sub>, ''b'') = gcd(''a''<sub>1</sub>, ''b'')⋅gcd(''a''<sub>2</sub>, ''b'')}}.
* {{math|gcd(''a'', ''b'')}} is closely related to the [[least common multiple]] {{math|lcm(''a'', ''b'')}}: we have
*: {{math|1=gcd(''a'', ''b'')⋅lcm(''a'', ''b'') = {{abs|''a''⋅''b''}}}}.
: This formula is often used to compute least common multiples: one first computes the GCD with Euclid's algorithm and then divides the product of the given numbers by their GCD.
* The following versions of [[distributivity]] hold true:
*: {{math|1=gcd(''a'', lcm(''b'', ''c'')) = lcm(gcd(''a'', ''b''), gcd(''a'', ''c''))}}
*: {{math|1=lcm(''a'', gcd(''b'', ''c'')) = gcd(lcm(''a'', ''b''), lcm(''a'', ''c''))}}.
* If we have the unique prime factorizations of  {{math|1=''a'' = ''p''<sub>1</sub><sup>''e''<sub>1</sub></sup> ''p''<sub>2</sub><sup>''e''<sub>2</sub></sup> ⋅⋅⋅ ''p''<sub>''m''</sub><sup>''e''<sub>''m''</sub></sup>}} and {{math|1=''b'' = ''p''<sub>1</sub><sup>''f''<sub>1</sub></sup> ''p''<sub>2</sub><sup>''f''<sub>2</sub></sup> ⋅⋅⋅ ''p''<sub>''m''</sub><sup>''f''<sub>''m''</sub></sup>}} where {{math|1=''e''<sub>''i''</sub> ≥ 0}} and {{math|1=''f''<sub>''i''</sub> ≥ 0}}, then the GCD of ''a'' and ''b'' is
*: {{math|1=gcd(''a'',''b'') = ''p''<sub>1</sub><sup>min(''e''<sub>1</sub>,''f''<sub>1</sub>)</sup> ''p''<sub>2</sub><sup>min(''e''<sub>2</sub>,''f''<sub>2</sub>)</sup> ⋅⋅⋅ ''p''<sub>''m''</sub><sup>min(''e''<sub>''m''</sub>,''f''<sub>''m''</sub>)</sup>}}.
* It is sometimes useful to define {{math|1=gcd(0, 0) = 0}} and {{math|1=lcm(0, 0) = 0}} because then the [[natural number]]s become a [[complete lattice|complete]] [[distributive lattice]] with GCD as meet and LCM as join operation.<ref>
{{cite book
 | last1 = Müller-Hoissen | first1 = Folkert
 | last2 = Walther | first2 = Hans-Otto
 | editor1-last = Müller-Hoissen | editor1-first = Folkert
 | editor2-last = Pallo | editor2-first = Jean Marcel
 | editor3-last = Stasheff | editor3-first = Jim | editor3-link = Jim Stasheff
 | contribution = Dov Tamari (formerly Bernhard Teitler)
 | isbn = 978-3-0348-0405-9
 | pages = 1–40
 | publisher = Birkhäuser
 | series = Progress in Mathematics
 | title = Associahedra, Tamari Lattices and Related Structures: Tamari Memorial Festschrift
 | volume = 299
 | year = 2012
}}. Footnote 27, p.&nbsp;9: "For example, the natural numbers with ''gcd'' (greatest common divisor) as meet and ''lcm'' (least common multiple) as join operation determine a (complete distributive) lattice." Including these definitions for 0 is necessary for this result: if one instead omits 0 from the set of natural numbers, the resulting lattice is not complete.</ref> This extension of the definition is also compatible with the generalization for commutative rings given below.
* In a [[Cartesian coordinate system]], {{math|gcd(''a'', ''b'')}} can be interpreted as the number of segments between points with integral coordinates on the straight [[line segment]] joining the points {{math|(0, 0)}} and {{math|(''a'', ''b'')}}.
* For non-negative integers {{math|''a''}} and {{math|''b''}}, where {{math|''a''}} and {{math|''b''}} are not both zero, provable by considering the Euclidean algorithm in base&nbsp;''n'':<ref>{{cite book |first1=Donald E. |last1=Knuth |author-link1=Donald Knuth |last2=Graham |first2=R. L. |last3=Patashnik |first3=O. |title=[[Concrete Mathematics: A Foundation for Computer Science]] |date=March 1994 |publisher=[[Addison-Wesley]] |isbn=0-201-55802-5}}</ref>
*: {{math|1=gcd(''n''<sup>''a''</sup> − 1, ''n''<sup>''b''</sup> − 1) = ''n''<sup>gcd(''a'',''b'')</sup> − 1}}.
* An [[Identity (mathematics)|identity]] involving [[Euler's totient function]]:
*: <math> \gcd(a,b) = \sum_{k|a \text{ and }k|b} \varphi(k) .</math>
* GCD Summatory function (Pillai's arithmetical function): 
<math>\sum_{k=1}^n \gcd(k,n)
= \sum_{d|n} d \varphi \left( \frac n d \right)
=n\sum_{d|n}\frac{\varphi(d)}{d}
=n\prod_{p|n}\left(1+\nu_p(n)\left(1-\frac{1}{p}\right)\right)</math> where <math>\nu_p(n)</math> is the {{math|''p''}}-adic valuation. {{OEIS|A018804}}