View source for Greatest common divisor

{{TEX|done}}

''highest common factor''

The largest of the common divisors of a set of integers or, in particular, of natural numbers $a_1,\ldots,a_n$. The greatest common divisor of a set of numbers not all of which are zero always exists. The greatest common divisor of $a_1,\ldots,a_n$ is usually denoted by $(a_1,\ldots,a_n)$.

Properties of the greatest common divisor are:

1) The greatest common divisor of $a_1,\ldots,a_n$ is divisible by any common divisor of these numbers.

2) $(a_1,\ldots,a_n,a_{n+1}) = ((a_1,\ldots,a_n),a_{n+1})$.

3) If $a_1,\ldots,a_n$ are expressed as
$$
a_1 = p_1^{\alpha_1} \cdots p_s^{\alpha_s}\ ,\ \ \ \ldots\ a_n = p_1^{\nu_1} \cdots p_s^{\nu_s}
$$
where $p_1,\ldots,p_s$ are distinct primes, $\alpha_i \ge 0\,\,\ldots\,\,\nu_i \ge 0$, $i=1,\ldots,s$ and $\delta_i = \min\{\alpha_i,\ldots,\nu_i\}$, then
$$
(a_1,\ldots,a_n) = p_1^{\delta_1} \cdots p_s^{\delta_s} \ .
$$

The greatest common divisor of two natural numbers can be determined by the [[Euclidean algorithm]]. The number of steps necessary to do this is bounded from above by five times the number of digits in the smaller of the two numbers (in decimal notation).

A greatest common divisor of two polynomials over a given field is a polynomial of greatest degree that divides both polynomials.  In this case again, a greatest common divisor is divisible by any other common divisor of the polynomials: cf [[Factorization of polynomials]].  The Euclidean algorithm may be used in this setting also to obtain the highest common factor, with a number of steps bounded by the smaller of the degrees of the polynomials: cf [[Euclidean ring]]

A greatest common divisor of elements of an [[Integral domain|integral domain]] is defined as a common divisor of these elements that is divisible by any other common divisor.  In general, a greatest common divisor of two elements of an integral domain need not exist (cf [[Divisibility in rings]], but if one exists, it is unique up to multiplication by an invertible element. The greatest common divisor of two ideals $\mathfrak{a}$ and $\mathfrak{b}$ in a ring is the ideal $(\mathfrak{a},\mathfrak{b})$ generated by the union of the sets$\mathfrak{a}$ and $\mathfrak{b}$ (see [[Factorial ring]]).

====References====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  I.M. Vinogradov,   "Elements of number theory" , Dover, reprint  (1954)  (Translated from Russian)</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  A.A. Bukhshtab,   "Number theory" , Moscow  (1966)  (In Russian)</TD></TR>
<TR><TD valign="top">[3]</TD> <TD valign="top">  A.I. Markushevich,   "Division with remainder in arithmetic and algebra" , Moscow-Leningrad  (1949)  (In Russian)</TD></TR>
<TR><TD valign="top">[4]</TD> <TD valign="top">  R. Faure,   A. Kaufman,   M. Denis-Papin,   "Mathématique nouvelle" , Dunod  (1964)</TD></TR>
<TR><TD valign="top">[5]</TD> <TD valign="top">  S. Lang,   "Algebra" , Addison-Wesley  (1974)</TD></TR>
<TR><TD valign="top">[6]</TD> <TD valign="top">  K. Ireland,   M. Rosen,   "A classical introduction to modern number theory" , Springer  (1982)</TD></TR>
</table>

====Comments====
More generally, if $R$ is a domain, a greatest common divisor $d$ of a set $S \subset R$, not all $x \in S$ zero, is a common divisor of the elements of $S$ with the property that any common divisor of all $x \in S$ divides $d$. If for any $S \subset R$ with not all $x \in S$ zero such a $d$ exists, $R$ is called a principal ideal domain (cf. [[Principal ideal ring]]).  Examples of such domains are the ring $\mathbb{Z}$ of rational integers or polynomial rings $F[X]$, where $F$ is a [[field]] (e.g., $\mathbb{C}$ or $\mathbb{R}$ or $\mathbb{Q}$). It is known that a principal ideal domain is also a unique factorization domain.   If a greatest common divisor exists for all finite sets $S$, then $R$ is a [[Bezout domain]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B.L. van der Waerden,   "Algebra" , '''1''' , Springer  (1967)  (Translated from German)</TD></TR></table>

[[Category:Number theory]]