info prev up next book cdrom email home

Greatest Common Divisor

The greatest common divisor of $a$ and $b$ GCD($a,b$), sometimes written $(a,b)$, is the largest Divisor common to $a$ and $b$. Symbolically, let

$\displaystyle a$ $\textstyle \equiv$ $\displaystyle \prod_i {p_i}^{\alpha_i}$ (1)
$\displaystyle b$ $\textstyle \equiv$ $\displaystyle \prod_i {p_i}^{\beta_i}$ (2)

Then the greatest common divisor is given by
\begin{displaymath}
(a,b)=\prod_i {p_i}^{\min(\alpha_i,\beta_i)},
\end{displaymath} (3)

where min denotes the Minimum. The GCD is Distributive
\begin{displaymath}
(ma,mb)=m(a,b)
\end{displaymath} (4)


\begin{displaymath}
(ma,mb,mc)=m(a,b,c),
\end{displaymath} (5)

and Associative
\begin{displaymath}
(a,b,c)=((a,b),c)=(a,(b,c))
\end{displaymath} (6)


\begin{displaymath}
(ab,cd)=(a,c)(b,d)\left({{a\over (a,c)}, {d\over (b,d)}}\right)\left({{c\over (a,c)}, {b\over (b,d)}}\right).
\end{displaymath} (7)


If $a=a_1(a,b)$ and $b=b_1(a,b)$, then

\begin{displaymath}
(a,b)=(a_1(a,b),b_1(a,b))=(a,b)(a_1,b_1),
\end{displaymath} (8)

so $(a_1,b_1)=1$ and $a_1$ and $b_1$ are said to be Relatively Prime. The GCD is also Idempotent
\begin{displaymath}
(a,a)=a,
\end{displaymath} (9)

Commutative
\begin{displaymath}
(a,b)=(b,a),
\end{displaymath} (10)

and satisfies the Absorption Law
\begin{displaymath}[a,(a,b)]=a.
\end{displaymath} (11)


The probability that two Integers picked at random are Relatively Prime is $[\zeta(2)]^{-1}=6/\pi^2$, where $\zeta(z)$ is the Riemann Zeta Function. Polezzi (1997) observed that $(m,n)=k$, where $k$ is the number of Lattice Points in the Plane on the straight Line connecting the Vectors (0, 0) and $(m, n)$ (excluding $(m, n)$ itself). This observation is intimately connected with the probability of obtaining Relatively Prime integers, and also with the geometric interpretation of a Reduced Fraction $y/x$ as a string through a Lattice of points with ends at (1,0) and $(x,y)$. The pegs it presses against $(x_i, y_i)$ give alternate Convergents $y_i/x_i$ of the Continued Fraction for $y/x$, while the other Convergents are obtained from the pegs it presses against with the initial end at (0, 1).


Knuth showed that

\begin{displaymath}
(2^p-1, 2^q-1)=2^{(p,q)}-1.
\end{displaymath} (12)


The extended greatest common divisor of two Integers $m$ and $n$ can be defined as the greatest common divisor $(m, n)$ of $m$ and $n$ which also satisfies the constraint $(m,n)=rm+sn$ for $r$ and $s$ given Integers. It is used in solving Linear Diophantine Equations.

See also Bezout Numbers, Euclidean Algorithm, Least Prime Factor


References

Polezzi, M. ``A Geometrical Method for Finding an Explicit Formula for the Greatest Common Divisor.'' Amer. Math. Monthly 104, 445-446, 1997.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-25