Namespaces
Variants
Actions

Difference between revisions of "Greatest common divisor"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (ce)
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
The largest of the common divisors of a set of integers or, in particular, of natural numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g0450601.png" />. The greatest common divisor of a set of numbers not all of which are zero always exists. The greatest common divisor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g0450602.png" /> is usually denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g0450603.png" />.
+
{{TEX|done}}
  
Properties of the greatest common divisor are:
+
''highest common factor''
  
1) The greatest common divisor of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g0450604.png" /> is divisible by any common divisor of these numbers.
+
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)$.
  
2) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g0450605.png" />.
+
Properties of the greatest common divisor are:
  
3) If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g0450606.png" /> are expressed as
+
1) The greatest common divisor of $a_1,\ldots,a_n$ is divisible by any common divisor of these numbers.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g0450607.png" /></td> </tr></table>
+
2) $(a_1,\ldots,a_n,a_{n+1}) = ((a_1,\ldots,a_n),a_{n+1})$.
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g0450608.png" /> are distinct primes, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g0450609.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506010.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506011.png" />, then
+
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} \ .
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506012.png" /></td> </tr></table>
+
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).
  
The greatest common divisor of two natural numbers can be determined by the [[Euclidean algorithm|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]]
  
The greatest common divisor of elements of an [[Integral domain|integral domain]] is defined as the common divisor of these elements that is divisible by any other common divisor. Thus, the greatest common divisor of two polynomials over a given field is the common divisor that is divisible by any other common divisor of the polynomials. If the greatest common divisor of two elements of an integral domain exists, it is unique up to multiplication by an invertible element. The greatest common divisor of two ideals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506013.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506014.png" /> in a ring is the ideal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506015.png" /> generated by the union of the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506016.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506017.png" /> (see [[Factorial ring|Factorial 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====
 
====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>
+
<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====
 
====Comments====
More generally, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506018.png" /> is a domain, a greatest common divisor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506019.png" /> of a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506020.png" />, not all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506021.png" /> zero, is characterized by the fact that any common divisor of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506022.png" /> divides <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506023.png" />. If for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506024.png" /> with not all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506025.png" /> zero such a <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506026.png" /> exists, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506027.png" /> is called a principal ideal domain (cf. [[Principal ideal ring|Principal ideal ring]]). Examples of such domains are the ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506028.png" /> of rational integers or polynomial rings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506029.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506030.png" /> is a [[Field|field]] (e.g., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506031.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506032.png" /> or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/g/g045/g045060/g04506033.png" />). It is known that a principal ideal domain is also a unique factorization domain.
+
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====
 
====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>
 
<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]]

Latest revision as of 17:01, 26 October 2014


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

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

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

[a1] B.L. van der Waerden, "Algebra" , 1 , Springer (1967) (Translated from German)
How to Cite This Entry:
Greatest common divisor. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Greatest_common_divisor&oldid=17623
This article was adapted from an original article by A.A. BukhshtabV.I. Nechaev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article