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
(a,b)=\prod_i {p_i}^{\min(\alpha_i,\beta_i)},
\end{displaymath} (3)

where min denotes the Minimum. The GCD is Distributive
\end{displaymath} (4)

\end{displaymath} (5)

and Associative
\end{displaymath} (6)

(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

\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
\end{displaymath} (9)

\end{displaymath} (10)

and satisfies the Absorption Law
\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

(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


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